[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
|