[Vm-dev] slip in LargeIntegers >> normalizePositive:

Fri Mar 6 23:07:44 UTC 2015

On Fri, Mar 6, 2015 at 2:39 PM, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> wrote:

>
> By the way, I already have part of this optimization in my
> LargeIntegerPlugins v2:
>
> #byteSizeOfLargeInt: and #digitSizeOfLargeInt:
>
> Moving the bounds check out of the loop sounds a good idea.
> The two senders have already done the job in my version.
>
> For the firstIndexableField:, can't we just let the C Compiler do its job?
> We don't write to a pointer in the loop, so it might see the constant by
> itself.
>

Alas the modularity in InterpreterProxy means that the C compiler would
have to do cross-module link-time optimization to eliminate the overhead.
 firstIndexableField: is not a macro, but a function in the interpreter.  I
managed to eliminate the extra level of indirection in invoking it for
internal plugins when I changed plugin generation last year.  But I can't
eliminate the function call altogether without a lot of work and a lot of
blurring of plugin/interpreter boundaries.  So I think the easier thing is
to cache the result of firstIndexableField:.

>
>
> 2015-03-06 23:21 GMT+01:00 Nicolas Cellier <
> nicolas.cellier.aka.nice at gmail.com>:
>
>>
>>
>> 2015-03-06 22:41 GMT+01:00 Eliot Miranda <eliot.miranda at gmail.com>:
>>
>>>
>>> Hi Nicolas,
>>>
>>> On Fri, Mar 6, 2015 at 10:35 AM, Nicolas Cellier <ncellier at ifrance.com>
>>> wrote:
>>>
>>>>
>>>> I'm trying to understand the negative case...
>>>>
>>>> We have the magnitude on one side xMag
>>>> We minSmallInteger in two complement on the other side yTC
>>>> We know that the magnitude of minSmallInteger is yMag=bitInvert(yTC)+1
>>>> We know that all bytes of yTC are 0 but the MSB
>>>> Thus all bytes of bitInvert(yTC) are 16rFF
>>>> Thus all bytes of yMag are 0, but the highest which is (MSB(yTC) xOr:
>>>> 256) + 1.
>>>>
>>>> Thus, assuming same byte length:
>>>> MSB(xMag) < MSB(yMag) => x is a CSI
>>>> MSB(xMag) > MSB(yMag) => x is large
>>>> MSB(xMag) = MSB(yMag) => we must inquire the LSBs of xMag..
>>>> (1 to: len-1) anySatisfy: [:i | (xMag digitAt: i) ~= 0] => x isLarge
>>>> otherwise, x is minSmallInteger
>>>>
>>>> Eliot, I fail to see the bitInvert(MSB(minSmallInteger))+1 in your
>>>> code...
>>>> Did I miss something?
>>>>
>>>
>>> You're talking about normalizeNegative: right?  I haven't changed
>>> anything fundamental here.  The check is in
>>>
>>> len <= sLen ifTrue:
>>> [(len < sLen
>>>   or: [(pointer at: sLen - 1)
>>> < (self cDigitOfCSI: interpreterProxy minSmallInteger at: sLen)])
>>> ifTrue: "interpreterProxy minSmallInteger lastDigit"
>>> ["If high digit less, then can be small"
>>> val := 0 - (pointer at: (len := len - 1)).
>>> len - 1 to: 0 by: -1 do:
>>> [:i | val := val * 256 - (pointer at: i)].
>>> ^val asOop: SmallInteger].
>>>  1 to: sLen do:
>>> [:i | | byte | "If all digits same, then = minSmallInteger (sr:
>>> minSmallInteger digits 1 to sLen - 1 are 0)"
>>> byte := i > len ifTrue: [0] ifFalse: [pointer at: i - 1].
>>> byte ~= (self cDigitOfCSI: interpreterProxy minSmallInteger at: i)
>>> ifTrue: "Not so; return self shortened"
>>> [len < oldLen ifTrue: "^ self growto: len"
>>> [^self bytes: aLargeNegativeInteger growTo: len].
>>>  ^aLargeNegativeInteger]].
>>>  ^interpreterProxy minSmallInteger asOop: SmallInteger].
>>>
>>> The first part deals with the simple case of something shorter than
>>> SmallInteger minVal, or the same length whose top byte is less:
>>>
>>> (len < sLen
>>>   or: [(pointer at: sLen - 1)
>>> < (self cDigitOfCSI: interpreterProxy minSmallInteger at: sLen)])
>>> ifTrue: "interpreterProxy minSmallInteger lastDigit"
>>> ["If high digit less, then can be small"
>>> val := 0 - (pointer at: (len := len - 1)).
>>> len - 1 to: 0 by: -1 do:
>>> [:i | val := val * 256 - (pointer at: i)].
>>> ^val asOop: SmallInteger].
>>>
>>>  The second part deals with the possibility of SmallInteger minVal:
>>>
>>>  1 to: sLen do:
>>> [:i | | byte | "If all digits same, then = minSmallInteger (sr:
>>> minSmallInteger digits 1 to sLen - 1 are 0)"
>>> byte := i > len ifTrue: [0] ifFalse: [pointer at: i - 1].
>>> byte ~= (self cDigitOfCSI: interpreterProxy minSmallInteger at: i)
>>> ifTrue: "Not so; return self shortened"
>>> [len < oldLen ifTrue: "^ self growto: len"
>>> [^self bytes: aLargeNegativeInteger growTo: len].
>>>  ^aLargeNegativeInteger]].
>>>  ^interpreterProxy minSmallInteger asOop: SmallInteger].
>>>
>>> The bit invert is in cDigitOfCSI:at:
>>> cDigitOfCSI: csi at: ix
>>> ^(csi < 0
>>> ifTrue: [0 - csi]
>>> ifFalse: [csi]) >> (ix - 1 * 8) bitAnd: 255
>>>
>>> answers 64 for "self cDigitOfCSI: interpreterProxy minSmallInteger at:
>>> 4" in 32 bits (16 in 64-bits).  So cDigitOfCSI:at: is answering magnitude,
>>> not 2's complement bytes.
>>>
>>
>> Ah, of course, I see it now :)
>>
>> So you don't really use the knowledge that following digits are 0...
>> That could save the repeated shifts and bitAnd:... unless the C compiler
>> unroll that loop.
>>
>>
>>
>>>
>>> Here's the original code before I streamlined it.  I don't see a
>>> significant difference:
>>>
>>> len <= sLen
>>> ifTrue:
>>> ["SmallInteger minVal"
>>> minVal := interpreterProxy minSmallInteger.
>>> (len < sLen or: [(self digitOfBytes: aLargeNegativeInteger at: sLen)
>>> < (self cDigitOfCSI: minVal at: sLen)
>>> "minVal lastDigit"])
>>> ifTrue:
>>> ["If high digit less, then can be small"
>>> val := 0.
>>> len
>>> to: 1
>>> by: -1
>>> do: [:i | val := val * 256 - (self unsafeByteOf: aLargeNegativeInteger
>>> at: i)].
>>> ^ val asOop: SmallInteger].
>>> 1 to: sLen do: [:i | "If all digits same, then = minVal (sr: minVal
>>> digits 1 to 3 are 0)"
>>> (self digitOfBytes: aLargeNegativeInteger at: i)
>>> = (self cDigitOfCSI: minVal at: i)
>>> ifFalse: ["Not so; return self shortened"
>>> len < oldLen
>>> ifTrue: ["^ self growto: len"
>>> ^ self bytes: aLargeNegativeInteger growTo: len]
>>> ifFalse: [^ aLargeNegativeInteger]]].
>>> ^ minVal asOop: SmallInteger].
>>>
>>> Or am I misunderstanding?
>>>
>>>
>>>> Nicolas
>>>>
>>>> 2015-03-06 0:37 GMT+01:00 Eliot Miranda <eliot.miranda at gmail.com>:
>>>>
>>>>>
>>>>> Hi Nicolas,
>>>>>
>>>>>    I found my misunderstanding.  Can you review this version instead?
>>>>>
>>>>>
>>>>>
>>>>> On Thu, Mar 5, 2015 at 11:41 AM, Eliot Miranda <
>>>>> eliot.miranda at gmail.com> wrote:
>>>>>
>>>>>> Hi Nicolas,
>>>>>>
>>>>>>      would you mind also reviewing the attached changes?  There's a
>>>>>> bug in them somewhere, although I think they're close to correct.  The
>>>>>> ideas here are to
>>>>>>
>>>>>> - avoid calling firstIndexableField: on every call
>>>>>> to unsafeByteOf:at: in isNormalized:, normalizePositive: and
>>>>>> normalizeNegative:.  Do this by cacheing firstIndexableField in a local
>>>>>> pointer variable
>>>>>> - move the bounds check in cDigitOfCSI:at: out to clients that aren't
>>>>>> invoking cDigitOfCSI:at: with in-bounds indices
>>>>>> - avoid the immediate test in digitLengthOf: when it is known that
>>>>>> the object is non-immediate.  Do so by adding digitLengthOfNonImmediate:.
>>>>>>
>>>>>> Of course this approach can be extended to other LargeIntegers
>>>>>> methods, but one step at a time :-/
>>>>>>
>>>>>> On Wed, Mar 4, 2015 at 2:49 PM, Nicolas Cellier <
>>>>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF
>>>>>>>
>>>>>>> sounds like a copy/paste error
>>>>>>> I would expect maxSmallInteger here.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> best,
>>>>>> Eliot
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> best,
>>>>> Eliot
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> best,
>>> Eliot
>>>
>>>
>>
>
>

-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20150306/99b6a559/attachment.htm