patchGNU Octave - Patches: patch #7825, built-in versions of base2dec and...

 
 

patch #7825: built-in versions of base2dec and dec2base

Submitted by:  Dan Sebald <sebald>
Submitted on:  Mon 30 Jul 2012 04:10:25 AM UTC  
 
Category: NonePriority: 5 - Normal
Status: NonePrivacy: Public
Assigned to: NoneOpen/Closed: Open

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Thu 06 Sep 2012 09:45:10 PM UTC, comment #3:

Noting a discrepancy in behavior for the script-file based bin2dec and the internal bin2dec

Internal wraps at 64-bit

octave:102> bin2dec("111111111111111111111111111111111111111111111111111111111111111111111111")
ans = 255

Script-based doesn't wrap at 64-bit

octave:728> bin2dec("111111111111111111111111111111111111111111111111111111111111111111111111")
ans = 4.7224e+21

The fix is simple: change base2dec_str_dbl_op () to actually return a dbl, as it says, rather than a long unsigned int. I will update the patch later using the new source reorganization.

Dan Sebald <sebald>
Mon 20 Aug 2012 01:47:52 AM UTC, comment #2:

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)

Dan Sebald <sebald>
Mon 30 Jul 2012 04:24:32 AM UTC, comment #1:

I see that there is a standard C++ library routine that returns both the quotient and remainder of a division. So I tried the following:

for (int j = LEN-1; j >= 0; j--)
{
div_t division;
division = div (divisor, BASE);

S[j] = mapstr[division.rem];

divisor = division.quot;
if (divisor == 0)
break;
}

To my surprise, this is slower. Not much of an optimization in that function I guess:

COMMAND BUILT-IN BUILT-IN
DIVIDE div_t
MULTIPLY div()
_____ ______ _____

dec2bin(<int vector>) 0.22697 0.25996
dec2bin(<cell vector>) 0.23996 0.28496
dec2hex(<int vector>) 0.11998 0.12998
dec2hex(<cell vector>) 0.13898 0.16198
dec2base(<int vec>, '01') 0.22497 0.24796
dec2base(<cell vec>, '01') 0.23996 0.28396

Dan Sebald <sebald>
Mon 30 Jul 2012 04:10:25 AM UTC, original submission:

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

Dan Sebald <sebald>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #26396:  octave-builtin_base2dec-2012aug19.patch added by sebald (29kB - text/x-patch - New version of patch as well as some code to test performance)
file #26397:  builtin_base2dec_compare.txt added by sebald (3kB - text/plain - New version of patch as well as some code to test performance)
file #26286:  octave-builtin_bin2dec-2012jul29.patch added by sebald (25kB - text/x-patch - hg diff including strfns.cc and removed dec2base.m and base2dec.m, some scripts to test performance)
file #26287:  builtin_base2dec_compare.txt added by sebald (2kB - text/plain - hg diff including strfns.cc and removed dec2base.m and base2dec.m, some scripts to test performance)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by sebald (Submitted the item)
  • -unavailable- added by sebald (built-in versions of base2dec and dec2base)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 20 Aug 2012 01:47:52 AM UTCsebaldAttached File-=>Added octave-builtin_base2dec-2012aug19.patch, #26396
      Attached File-=>Added builtin_base2dec_compare.txt, #26397
    Mon 30 Jul 2012 04:10:25 AM UTCsebaldAttached File-=>Added octave-builtin_bin2dec-2012jul29.patch, #26286
      Attached File-=>Added builtin_base2dec_compare.txt, #26287
      Carbon-Copy-=>Added sebald

    Back to the top


    Powered by Savane 3.1-cleanup