[Octave-patch-tracker] [patch #7825] built-in versions of base2dec and dec2base

[Dan Sebald]

URL:
  <http://savannah.gnu.org/patch/?7825>

                 Summary: built-in versions of base2dec and dec2base
                 Project: GNU Octave
            Submitted by: sebald
            Submitted on: Mon 30 Jul 2012 04:10:25 AM GMT
                Category: None
                Priority: 5 - Normal
                  Status: None
                 Privacy: Public
             Assigned to: None
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

The patch for built-in versions of base2dec() and dec2base() speeds up cell
versions of the routines considerably. Also attached is a file containing some
scripts for comparing performance.

Although the code is fairly well organized and functional, I'm just becoming
familiar with the classes and conventions for return values, and there will
need to be another pass to get the variable types correct. A particular snag
right now is accessing the octave values as long ints as opposed to doubles.
This became evident from the smart hunk of test code:

% test
s0 = "";
for n = 1:13
  for b = 2:16
    pp = dec2base (b^n+1, b);
    assert (dec2base (b^n, b), ['1',s0,'0']);
    assert (dec2base (b^n+1, b), ['1',s0,'1']);
  endfor
  s0 = [s0,'0'];
endfor 

which originally failed with a combination of n and b corresponding to 2^24,
i.e., the limit of the float mantissa. I understand the classes, but it is a
case of finding the right member functions to do the trick.

Also, there is a slight amount of code duplication I'd like to reduce. I'd
like to experiment with strings as well. Somehow it seems like there is a
slight performance loss due to using the strings class, but I may find it not
worth optimizing that portion of things.

Here are some performance results using a 10e6 size vector (strings or
numbers, depending upon base2dec vs. dec2base). The numbers are seconds of CPU
consumption.

COMMAND                      BUILT-IN   CURRENT
                             VERSION    SCRIPT
                                        VERSION
_______                      ________   _______

bin2dec(<char matrix>)       0.13398    0.55891
bin2dec(<cell vector>)       0.21897    1.7447
hex2dec(<char matrix>)       0.14298    0.55192
hex2dec(<cell vector>)       0.22097    1.7277
base2dec(<char mat>, '01')   0.19697    0.52792
base2dec(<cell vec>, '01')   0.28396    1.7387

dec2bin(<int vector>)        0.22697    1.1598
dec2bin(<cell vector>)       0.23996    3.5465
dec2hex(<int vector>)        0.11998    0.30195
dec2hex(<cell vector>)       0.13898    2.7226
dec2base(<int vec>, '01')    0.22497    1.1548
dec2base(<cell vec>, '01')   0.23996    3.5535

Furthermore, here are some related times:

cellstr(<char matrix>) 0.86387
num2cell(<int vector>) 0.062990

Some observations:

1) There is roughly three times improvement at minimum. In the case of cells,
it is a factor of ten or more.

2) In theory the string-based version of base2dec should be fastest because
there is no ASCII cases to deal with. But I think the string classes are a bit
slower than the raw C strings. This could be optimized for further
improvement, but it is to the point where base2dec is so fast that its cost is
small compared to other string manipulations.

3) The builtin version brings the times down such that cellstr() stands out as
a critical time. It does no processing and is five times slower than
base2dec() which does processing. I'm going to look into cellstr() at a later
time.

Questions (and I know the answer is "compatibility"):

1) In dec2base, if the input is a cell array, the output is a character
matrix. I would think that the string cell array would be preferred without
the zero padding in front... unless LEN is set.

2) In base2dec, if the input is a cell array row, the output is a cell array
column. My first inclination was to make the dimensions match (until I tried
the test case that checks this at which point I changed dimensions). To me, it
seems the logical thing to do with a cell array is keep the output dimensions
the same as the input dimensions. That is sort of the point of cells.

Dan



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Mon 30 Jul 2012 04:10:25 AM GMT  Name:
octave-builtin_bin2dec-2012jul29.patch  Size: 25kB   By: sebald
hg diff including strfns.cc and removed dec2base.m and base2dec.m, some
scripts to test performance
<http://savannah.gnu.org/patch/download.php?file_id=26286>
-------------------------------------------------------
Date: Mon 30 Jul 2012 04:10:25 AM GMT  Name: builtin_base2dec_compare.txt 
Size: 2kB   By: sebald
hg diff including strfns.cc and removed dec2base.m and base2dec.m, some
scripts to test performance
<http://savannah.gnu.org/patch/download.php?file_id=26287>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/patch/?7825>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/