sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF |
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 <[hidden email]> wrote:
best,
Eliot LargeIntegersPlugin-methods.st (8K) Download Attachment |
Hi Nicolas, I found my misunderstanding. Can you review this version instead? On Thu, Mar 5, 2015 at 11:41 AM, Eliot Miranda <[hidden email]> wrote:
best,
Eliot LargeIntegersPlugin-methods.st (9K) Download Attachment |
I'm trying to understand the negative case... We have the magnitude on one side xMagMSB(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.. 2015-03-06 0:37 GMT+01:00 Eliot Miranda <[hidden email]>:
|
2015-03-06 19:35 GMT+01:00 Nicolas Cellier <[hidden email]>:
<Blush> it's xOr: 255 of course...</Blush>
|
In reply to this post by Nicolas Cellier-3
Hi Nicolas,
On Fri, Mar 6, 2015 at 10:35 AM, Nicolas Cellier <[hidden email]> wrote:
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. 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?
best,
Eliot |
2015-03-06 22:41 GMT+01:00 Eliot Miranda <[hidden email]>:
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.
|
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. 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 <[hidden email]>:
|
On Fri, Mar 6, 2015 at 2:39 PM, Nicolas Cellier <[hidden email]> wrote:
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:.
best,
Eliot |
Free forum by Nabble | Edit this page |