Smalltalk › Squeak › Squeak - Dev

64 bit integer arithmetic

‹ Previous Topic Next Topic ›
 
classic Classic list List threaded Threaded
♦
♦
 5 messages Options
Benoit St-Jean
Reply | Threaded
Open this post in threaded view
♦
♦
|

64 bit integer arithmetic

Benoit St-Jean
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)
Nicolas Cellier
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: 64 bit integer arithmetic

Nicolas Cellier
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 <[hidden email]>:
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)
Nicolas Cellier
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: 64 bit integer arithmetic

Nicolas Cellier
Note that what I wrote for + is not exactly what's going on, because + has a special bytecode and would first invoke interpreter
bytecodePrimAdd
    | rcvr arg result |
    rcvr := self internalStackValue: 1.
    arg := self internalStackValue: 0.
    (objectMemory areIntegers: rcvr and: arg)
        ifTrue: [result := (objectMemory integerValueOf: rcvr) + (objectMemory integerValueOf: arg).
                (objectMemory isIntegerValue: result) ifTrue:
                    [self internalPop: 2 thenPush: (objectMemory integerObjectOf: result).
                    ^ self fetchNextBytecode "success"]]
        ifFalse: [self initPrimCall.
                self externalizeIPandSP.
                self primitiveFloatAdd: rcvr toArg: arg.
                self internalizeIPandSP.
                self successful ifTrue: [^ self fetchNextBytecode "success"]].

    messageSelector := self specialSelector: 0.
    argumentCount := 1.
    self normalSend

And this is not accounting for JIT which is inlining some of those primitives:
genPrimitiveAdd
    | jumpNotSI jumpOvfl |
    <var: #jumpNotSI type: #'AbstractInstruction *'>
    <var: #jumpOvfl type: #'AbstractInstruction *'>
    cogit mclassIsSmallInteger ifFalse:
        [^UnimplementedPrimitive].
    cogit genLoadArgAtDepth: 0 into: Arg0Reg.
    cogit MoveR: Arg0Reg R: ClassReg.
    jumpNotSI := self genJumpNotSmallInteger: Arg0Reg scratchReg: TempReg.
    self genRemoveSmallIntegerTagsInScratchReg: ClassReg.
    cogit AddR: ReceiverResultReg R: ClassReg.
    jumpOvfl := cogit JumpOverflow: 0.
    cogit MoveR: ClassReg R: ReceiverResultReg.
    cogit genPrimReturn.
    jumpOvfl jmpTarget: (jumpNotSI jmpTarget: cogit Label).
    ^CompletePrimitive

Or if you are after bit ops, here is an extract of the primitive table that is not currently used in the image:

        (34 primitiveBitAndLargeIntegers)
        (35 primitiveBitOrLargeIntegers)
        (36 primitiveBitXorLargeIntegers)

So you might want to implement
LargePositiveInteger>>bitAnd: arg
    <primitive: 34>
    ^super bitAnd: arg

and see if it already speed things up for you.

2016-10-14 23:09 GMT+02:00 Nicolas Cellier <[hidden email]>:
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 <[hidden email]>:
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)
Benoit St-Jean
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: 64 bit integer arithmetic

Benoit St-Jean
In reply to this post by Nicolas Cellier
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.

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 <[hidden email]>
To: Benoit St-Jean <[hidden email]>; The general-purpose Squeak developers list <[hidden email]>
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 <[hidden email]>:
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)
Levente Uzonyi
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: 64 bit integer arithmetic

Levente Uzonyi
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 <[hidden email]>
> To: Benoit St-Jean <[hidden email]>; The general-purpose Squeak developers list <[hidden email]>
> 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 <[hidden email]>:
>       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)
>
>
>
>
>
>
>
>
Free forum by Nabble Edit this page