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

Fri Mar 6 22:39:18 UTC 2015

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.

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