slip in LargeIntegers >> normalizePositive:

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

slip in LargeIntegers >> normalizePositive:

Nicolas Cellier
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.
Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Eliot Miranda-2
 
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot

LargeIntegersPlugin-methods.st (8K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Eliot Miranda-2
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot

LargeIntegersPlugin-methods.st (9K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Nicolas Cellier-3
 
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?

Nicolas

2015-03-06 0:37 GMT+01:00 Eliot Miranda <[hidden email]>:
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot


Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Nicolas Cellier-3
 


2015-03-06 19:35 GMT+01:00 Nicolas Cellier <[hidden email]>:
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.

<Blush> it's xOr: 255 of course...</Blush>

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?

Nicolas

2015-03-06 0:37 GMT+01:00 Eliot Miranda <[hidden email]>:
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot



Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Eliot Miranda-2
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:
 
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.

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 <[hidden email]>:
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot






--
best,
Eliot
Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Nicolas Cellier
 


2015-03-06 22:41 GMT+01:00 Eliot Miranda <[hidden email]>:
 
Hi Nicolas,

On Fri, Mar 6, 2015 at 10:35 AM, Nicolas Cellier <[hidden email]> 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 <[hidden email]>:
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot






--
best,
Eliot


Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Nicolas Cellier
 
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 <[hidden email]>:


2015-03-06 22:41 GMT+01:00 Eliot Miranda <[hidden email]>:
 
Hi Nicolas,

On Fri, Mar 6, 2015 at 10:35 AM, Nicolas Cellier <[hidden email]> 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 <[hidden email]>:
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot






--
best,
Eliot



Reply | Threaded
Open this post in threaded view
|

Re: slip in LargeIntegers >> normalizePositive:

Eliot Miranda-2
 


On Fri, Mar 6, 2015 at 2:39 PM, Nicolas Cellier <[hidden email]> 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 <[hidden email]>:


2015-03-06 22:41 GMT+01:00 Eliot Miranda <[hidden email]>:
 
Hi Nicolas,

On Fri, Mar 6, 2015 at 10:35 AM, Nicolas Cellier <[hidden email]> 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 <[hidden email]>:
 
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:
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:
 

sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF

sounds like a copy/paste error
I would expect maxSmallInteger here.




--
best,
Eliot



--
best,
Eliot






--
best,
Eliot







--
best,
Eliot