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

 
 

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

Submitter:  Dan Sebald <sebald>
Submitted:  Mon 30 Jul 2012 04:10:25 AM UTC
   
 
Category:  Core : other Priority:  5 - Normal
Status:  Wont Do Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 30 Aug 2021 08:19:09 AM UTC, comment #7: 

Agree to comment #6, and sorry for all the hard work back in 2012 😓

Closing item.

Kai Torben Ohlhus <siko1056>
Group Member
Sat 28 Aug 2021 04:30:15 AM UTC, comment #6: 

checking this patch, if obviously no longer applies cleanly. mainly because strfns.cc has changed locations, but also dec2base has been modified a number of times since 2012 for bugs and matlab compatibility that may not be accounted for in the patch's compiled versions of the functions.

Absent enough interest in the speed boost to warrant bringing this up to date, perhaps the bug should be marked closed/won't fix.

Nicholas Jankowski <nrjank>
Group Member
Wed 06 Jul 2016 05:21:52 PM UTC, comment #5: 

This is from around the time when more discussion was done on the maintainers list.  I think where this left off was that maybe some day Rik would have a look at things because he'd just done the optimization to get the scripted version down to the times listed in the data below.  I would then revisit this if he felt it worth working in C versus scripts.  It wasn't a top priority and the scripted versions haven't seen negative feedback from users, so for 4.2.0?  Probably not.

Dan Sebald <sebald>
Wed 06 Jul 2016 12:54:41 PM UTC, comment #4: 

Dan, would you like this patch considered for 4.2.0?  If so, please freshen it (for example, noting the changes in docstring conventions) and submit a Mercurial changeset.

Lachlan Andrew <lachlan>
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 Files:
   
   
Comment:
   

Attached Files
file #26396:  octave-builtin_base2dec-2012aug19.patch added by sebald (29KiB - text/x-patch - New version of patch as well as some code to test performance)
file #26397:  builtin_base2dec_compare.txt added by sebald (3KiB - text/plain - New version of patch as well as some code to test performance)
file #26286:  octave-builtin_bin2dec-2012jul29.patch added by sebald (25KiB - 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 (2KiB - 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
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by sebald (Submitted the item)
  • -email is unavailable- added by sebald (built-in versions of base2dec and dec2base)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-10-21 mtmiller Carbon-CopyRemoved 80942 -
    2021-08-30 siko1056 StatusPostponed Wont Do
        Open/ClosedOpen Closed
    2018-04-10 mtmiller CategoryNone Core : other
        StatusNone Postponed
    2012-08-20 sebald Attached File- Added octave-builtin_base2dec-2012aug19.patch, #26396
        Attached File- Added builtin_base2dec_compare.txt, #26397
    2012-07-30 sebald Attached 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.13-f8d8.
    Corresponding source code