Need help avoiding LargeInteger>>*

Andreas Raab andreas.raab at gmx.de
Fri Mar 7 13:12:21 UTC 2003


Hi Chris,

Not knowing exactly what you're trying to do (I haven't looked at Magma yet)
there are two ways in which I can think to speed up your problem. 

#1: Don't use byte arrays as numbers. What I mean by this is that if you
essentally have "integer keys" (that is byte arrays which you only use for
identifying objects by identity) you could use (Large)Integers instead. This
will give you the optimized versions for almost every arithmetic operation
you can think about. For example, one could wrap UUIDs into
LargePositiveIntegers of the appropriate size and then use those LPIs for
hashing, comparing etc.

#2: Make up a little plugin that puts the platform-independent accessors
into a primitive. Lex did something alike in the IntegerPokerPlugin which is
used by Nebraska. I can't say if that plugin all by itself would be helpful
for your case but you may want to check it out. A tiny plugin which could
read numbers from byte arrays might be a pretty helpful thing to have in
general - similar to the support functions exported by the FFI (all of these
use platform dependent byte ordering though!). Also: If you only need those
integers for computing hashes you could use the FFI primitives themselves
(since they will preserve the invariant that for equal values it computes
equal hashes). I would generally recommend against this but in order to see
if that has any big impact on your problem it might be very worthwhile to
check it out.

Cheers,
  - Andreas


> -----Original Message-----
> From: squeak-dev-bounces at lists.squeakfoundation.org 
> [mailto:squeak-dev-bounces at lists.squeakfoundation.org] On 
> Behalf Of Chris Muller
> Sent: Friday, March 07, 2003 7:21 AM
> To: Squeak List
> Subject: Need help avoiding LargeInteger>>*
> 
> 
> 
> 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