Need help avoiding LargeInteger>>*

Chris Muller afunkyobject at yahoo.com
Fri Mar 7 06:21:24 UTC 2003


I have a MagmaCollection with several million entries and have a lot more I
need to get in there using a batch program I wrote.  The problem is, adding to
a MaHashIndex is expensive, so its taking a long time to run this batch
program.

I managed to profile one of the larger commits where the program was adding
lots of new entries to this multi-million-sized collection.  The profile
browser revealed 51.6% was spent in LargeInteger>>*.

What I need is for Andreas Raab (are you the "ar" who wrote
ByteArray>>unsignedLongAt:bigEndian:?) or anyone with as wonderful math skills
to see if they can optimize one of my methods for maximum performance.

The method I need optimized is ByteArray>>maUint:at:.  It's a general method
for reading an unsigned Integer of the specified bit-size out of a ByteArray. 
You get the method when you install Ma client server, or any Magma package.

In this method, I have three guard clauses at the top to delegate to the
existing unsignedByteAt:, unsignedShortAt: and unsignedLongAt: for reading
numbers 32-bits or smaller.  For 64-bit and larger (up to 256-bit), it falls
through to my code.

Here are the benchmarks for reading a 32-bit compared to a 64-bit number:

"32-bit bench"
|ba|
ba _ ByteArray new: 8.
ba maUint: 32 at: 0 put: (0 to: SmallInteger maxVal) atRandom.
[ ba maUint: 32 at: 0 ] maBench    '243124.975004999 per second.'

"64-bit bench"
|ba|
ba _ ByteArray new: 8.
ba maUint: 64 at: 0 put: (SmallInteger maxVal to: (2 raisedTo: 64)) atRandom.
[ ba maUint: 64 at: 0 ] maBench     '13085.18296340732 per second.'

Wow, that's a tremendous difference!  Unfortunately MagmaCollections, by nature
of their design, need to read a LOT of 64-bit sized numbers.

I looked at unsignedLongAt:bigEndian: and noticed the comment, "Minimize
LargeInteger arithmetic".  Good idea!  Unfortunately, I just don't have the
math training to understand how this bitShifting is being applied that I may
copy its premise and arrive at the correct answer for 64-bit numbers.

As always, I am very grateful for the generous help of those in one of the best
OO communities around.  In the meantime, I guess I'll just patiently...  wait. 
:-)

Thank you!
  Chris

PS - I did post a new version of Magma today with Avi's bugs fixed.  I haven't
had a single bug report other than what Avi found in 1.0gamma.  Maybe not many
have tried it, although I haven't found anything else (besides this) in my use
of it either.  So it appears it may be coalescing into a true 1.0 real soon
now!  I still can't verify Linux compatibility myself.  Avi, can you try it
again for me?



__________________________________________________
Do you Yahoo!?
Yahoo! Tax Center - forms, calculators, tips, more
http://taxes.yahoo.com/



More information about the Squeak-dev mailing list