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

[Dan Sebald]

Follow-up Comment #2, patch #7825 (project octave):

I've gone over the builtin base2dec/dec2base code and created a second version
of the patch file.  Changes are:

1) Added checks for non-negative and non-fraction.
2) Vary the width of division (via template) based on max size to bump up
efficiency.
3) Modifications to ensure unsigned long numbers are done properly.

I think everything is covered now, and I've verified all the tests and a
little more.

What I propose is that someone with more advanced understanding of the Octave
classes suggesting ways to program this slightly better by utilizing code
reuse or other member functions.

What follows is more detail that will be of value once one is familiar with
the code.

PERFORMANCE
-----------
I've redone some performance tests and found about 10% decrease in times of
for the built-in function due to the added checks described in (1) above. 
Here are some performance results using a 10e6 size vector (strings or random
numbers, depending upon base2dec vs. dec2base).  The specs are seconds of CPU
consumption.

COMMAND                      BUILT-IN        CURRENT
                             VERSION         SCRIPT
                                             VERSION
_______                      ________        _______

bin2dec(<char matrix>)       0.15298         0.56591
bin2dec(<cell vector>)       0.24196         1.7647
hex2dec(<char matrix>)       0.15298         0.55892
hex2dec(<cell vector>)       0.23996         1.7747
base2dec(<char mat>, '01')   0.18997         0.53792
base2dec(<cell vec>, '01')   0.27496         1.7217

dec2bin(<int vector>)        0.25796         1.1488
dec2bin(<cell vector>)       0.26296         3.6314
dec2hex(<int vector>)        0.14098         0.30096
dec2hex(<cell vector>)       0.16097         2.7606
dec2base(<int vec>, '01')    0.25696         1.1498
dec2base(<cell vec>, '01')   0.25896         3.5345

Furthermore, here are some related times:

cellstr(<char matrix>)   0.82187
num2cell(<int vector>)   0.064990


DIVISION SIZE
-------------
I've also done some tests with to check if changing the division size is worth
it.  For example, to investigate 8 bits, I checked 2^8-1, 2^8 and 2^9 -- the
first number is a character divide, the second number is a short divide and
the third number is a short divide by one character wider.  The idea is to try
and get a feel for what portion of CPU consumption increase is due to the one
character longer number and what is due to the wider division.

Judging from the numbers, it seems clear that there is some increase
attributable to the wider division noticeable for the transition from a 32-bit
divide to a 64-bit divide.  The other two cases (8-bit to 16-bit and 16-bit to
32-bit) don't have such strong evidence.  It could be that those divisions are
done using 32-bit division inside the CPU and there really isn't much
difference.  So, maybe in the code the four separate cases could be reduced to
two cases with boundary at UINT_MAX.

Here are some performance results using a 10e6 size vector, but non random and
at the border of transition from 8, 16, 32, 64 bit.  The specs are seconds of
CPU consumption.

COMMAND                 BUILT-IN        CURRENT
                        VERSION         SCRIPT
                                        VERSION
_______                 ________        _______

dec2bin(2^8-1)          0.17397         0.68489
dec2bin(2^8)            0.19097         0.74089
dec2bin(2^9)            0.20797         0.88487 
dec2bin(2^16-1)         0.25996         1.3968
dec2bin(2^16)           0.26996         1.3738
dec2bin(2^17)           0.28396         1.4608 
dec2bin(2^32-1)         0.45993         2.6836
dec2bin(2^32)           0.58791         2.6416
dec2bin(2^33)           0.63190         2.6996
dec2bin(2^64-1)         1.1818          5.2662
dec2bin(2^64)           1.1788          5.2262
dec2bin(2^65)           1.1738          5.2612

dec2bin({2^8-1})        0.17297         3.2095
dec2bin({2^8})          0.18497         3.1865
dec2bin({2^9})          0.20297         3.2615
dec2bin({2^16-1})       0.26596         3.8494
dec2bin({2^16})         0.28996         3.7954
dec2bin({2^17})         0.28696         3.8954
dec2bin({2^32-1})       0.45493         5.1152
dec2bin({2^32})         0.59191         5.0582
dec2bin({2^33})         0.63190         5.3472
dec2bin({2^64-1})       1.1768          7.7158
dec2bin({2^64})         1.1788          7.6908 
dec2bin({2^65})         1.1848          7.6748 


CODE REUSE
----------
There is still a bit of code redundancy.  For example, these two routines are
very similar:

base2dec_str_dbl_op
base2dec_str_str_op

However, they remain distinct because when base is a double we have to account
for the fact that the range of possible inputs includes lower case and upper
case letters (think hexadecimal 'a' and 'A').  One could convert the string
array for the base-double case, but then that is loss of efficiency as well as
introducing a function from a library.  I sided with efficiency of execution
rather than smaller code.

These two are very similar, so much so that I'd love to see a Template created
for this, but I just couldn't see how to do it because of the distinct ways in
dealing with octave_value and cells:

dec2base_array_str_op
dec2base_cell_str_op

It's possible to make the duplicate code more modular, but sometimes that can
get messy looking and hard to follow.

(file #26396, file #26397)
    _______________________________________________________

Additional Item Attachment:

File name: octave-builtin_base2dec-2012aug19.patch Size:28 KB
File name: builtin_base2dec_compare.txt   Size:2 KB


    _______________________________________________________

Reply to this item at:

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

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