[squeak-dev] 64 bit integer arithmetic

Levente Uzonyi leves at caesar.elte.hu
Sat Oct 15 09:59:33 UTC 2016


On Fri, 14 Oct 2016, Benoit St-Jean wrote:

> But there are many instances, especially when dealing with bit manipulation, where there is a huge penalty.  On most occasions, SmallInteger are 3
> times faster than LargePositiveInteger.  And in my very particular case (bitboards for a chess engine), using all 64 bits is a must.
> 
> 
> To clearly see my problem, try this :
> 
> | n timeSmall timeLarge |
> small1 := 1 << 59.
> small2 := 1 << 49.
> large1 := 1 << 60.
> large2 := 1 << 62.
> 
> n := 100000000.
> timeSmall := Time millisecondsToRun: [n timesRepeat: [ small1 bitXor:  small2]].
> timeLarge := Time millisecondsToRun: [n timesRepeat: [ large1 bitXor:  large2]].
> Transcript cr;show: 'Time LargePositiveInteger : ', timeLarge printString.
> Transcript cr;show: 'Time SmallInteger : ', timeSmall printString.

You'd get more accurate results if you were to use an inlined loop (e.g 1 
to: n do: [ :i | small1 bitXor: small2 ]). If you don't need such 
accuracy, then it's easier to use #bench.

I did some quick measurements with the primitives suggested by Nicolas, 
and for example primitive 36 is 3.8 times quicker than primDigitBitXor 
for 64-bit LargePositiveIntegers. For larger ones primitive 36 becomes too 
slow.
Perhaps the code of the two should be merged. I suspect that the 
performance of primDigitBitXor suffers from incomplete inlining because 
it's in a module.

Levente

> 
> I get this result:
> 
> Time LargePositiveInteger : 11028
> Time SmallInteger : 3315
>  
> -----------------
> Benoît St-Jean
> Yahoo! Messenger: bstjean
> Twitter: @BenLeChialeux
> Pinterest: benoitstjean
> Instagram: Chef_Benito
> IRC: lamneth
> Blogue: endormitoire.wordpress.com
> "A standpoint is an intellectual horizon of radius zero".  (A. Einstein)
> 
> 
> __________________________________________________________________________________________________________________________________________________
> From: Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
> To: Benoit St-Jean <bstjean at yahoo.com>; The general-purpose Squeak developers list <squeak-dev at lists.squeakfoundation.org>
> Sent: Friday, October 14, 2016 5:09 PM
> Subject: Re: [squeak-dev] 64 bit integer arithmetic
> 
> But the 32bits VM is already dealing with 64 bits integers specially.
> Take + for example.
> SmallInteger>>+ calls primitive: 1 (that is primitiveAdd)
> LargePositiveInteger>>+ calls primitive: 21 (that is primitiveAddLargeIntegers)
> Integer>>+ call digitAdd: which calls primitive: 'primDigitAdd' module:'LargeIntegers'
> 
> So what happens if you peform 1<<63+1 ?
> It calls primitive: 21 which is doing this:
> primitiveAddLargeIntegers
>     "Primitive arithmetic operations for large integers in 64 bit range"
>     | a b result oopResult aIsNegative bIsNegative resultIsNegative oopArg oopRcvr |
>     <export: true>
>     <var: 'a' type: 'usqLong'>
>     <var: 'b' type: 'usqLong'>
>     <var: 'result' type: 'usqLong'>
> 
>     oopArg := self stackValue: 0.
>     oopRcvr := self stackValue: 1.
>     aIsNegative := self isNegativeIntegerValueOf: oopRcvr.
>     bIsNegative := self isNegativeIntegerValueOf: oopArg.
>     a := self magnitude64BitValueOf: oopRcvr.
>     b := self magnitude64BitValueOf: oopArg.
>     self successful ifFalse:[^nil].
>     (aIsNegative = bIsNegative)
>         ifTrue:
>             ["Protect against overflow"
>             a > (16rFFFFFFFFFFFFFFFF - b) ifTrue: [self primitiveFail. ^nil].
>             result := a + b.
>             resultIsNegative := aIsNegative]
>         ifFalse:
>             [(a >= b)
>                 ifTrue:
>                     [result := a - b.
>                     resultIsNegative := aIsNegative]
>                 ifFalse:
>                     [result := b - a.
>                     resultIsNegative := bIsNegative]].
>     oopResult := self magnitude64BitIntegerFor: result neg: resultIsNegative.
>     self successful ifTrue:[self pop: 2 thenPush: oopResult].
> 
> So you see, it just perform 64 bits arithmetic primitively.
> 
> However, if you do 1+(1<<63), then you invoke:
> primitiveAdd
> 
>     self pop2AndPushIntegerIfOK: (self stackIntegerValue: 1) + (self stackIntegerValue: 0)
> 
> That will fail because the argument is not a SmallInteger. Then you fallback to Integer>>+ which invokes digitAdd:
> 
> The only thing that changes with 64bits spur VM is that SmallInteger have 61bits and can represent any int in ((1<<60) negated to: (1<<60-1)). So
> 1+(1<<59) would still be a SmallInteger, but the other examples above would run unchanged.
> 
> 
> 
> 2016-10-14 0:22 GMT+02:00 Benoit St-Jean <bstjean at yahoo.com>:
>       I was wondering if the 64-bit VM (such as the one for Squeak 5.1) will support 64-bit integer arithmetic with primitives for positive
>       integers.  Right now, 64 positive integers support bitwise operations but through code (LargePositiveInteger).  Any plan to move those
>       calculations/operations to primitives to speed things up? 
> 
> That would be so wonderful and nice for someone like me wanting to fully use a 64-bit architecture & Squeak/Cog/Pharo/Whatever/VM for a
> chess engine project!
>  
> -----------------
> Benoît St-Jean
> Yahoo! Messenger: bstjean
> Twitter: @BenLeChialeux
> Pinterest: benoitstjean
> Instagram: Chef_Benito
> IRC: lamneth
> Blogue: endormitoire.wordpress.com
> "A standpoint is an intellectual horizon of radius zero".  (A. Einstein)
> 
> 
> 
> 
> 
> 
> 
>


More information about the Squeak-dev mailing list