[squeak-dev] 64 bit integer arithmetic

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Fri Oct 14 21:28:19 UTC 2016


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 <
nicolas.cellier.aka.nice at gmail.com>:

> 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)
>>
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20161014/b98b3e20/attachment-0001.htm


More information about the Squeak-dev mailing list