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
|