Using #= for integer comparison instead of #==

On Tue, 16 Nov 2010, Juan Vuletich wrote:

Hi Levente,

Levente Uzonyi wrote:

Hi,

I'm mostly ready with this cleanup, only a few methods left in the image that use #== for integer comparison. Some of them must use #==, others may be changed, but I wasn't sure if the code will work if it's changed or not. If you'd like to check these methods, then evaluate the following in a workspace:

... code here...

Cheers,
Levente

Thanks for the snippet! It is now a method in Cuis. I also checked a bit on trunk. In all senders of #nextObject you can apply the pattern in #allObjectsDo:. Instead of assuming == 0 for last #nextObject, it assumes that Object new will go at the end. If that ever changed, a few places would need fixing...

I'm not sure if it's ok to use that pattern in ImageSegment. Even if it's ok, the code is so messy, that it seems to be hard to apply the pattern without breaking the code.

As an experiment, in #allObjectsDo: I tried to remove the Object new stuff and replace with '[ 0 = object and: [ object isMemberOf: SmallInteger ]] whileFalse: ', but my test became extremely slow. I suspect #= is sending the message even if it has its own bytecode... So, the only method that remains with the '0 ==' pattern in Cuis is #critical:ifLocked: , as I'm not sure if we can clean it.

#= is a special selector, so I'm sure it won't send a message if it doesn't have to.

It's possible that #= is a bit slower than #== because it has to do some extra checks, but the difference is probably neglible. Here's a benchmark:

| offset equality identity |
Smalltalk garbageCollect.
offset := [ 1 to: 1000000 do: [ :i | ] ] timeToRun.
equality := [ :x | [ 1 to: 1000000 do: [ :i | 0 = x ] ] timeToRun ].
identity := [ :x | [ 1 to: 1000000 do: [ :i | 0 == x ] ] timeToRun ].
{ 0. 1. SmallInteger maxVal. SmallInteger maxVal + 1. nil. Object new. 0.0. Array new. 1/2 } collect: [ :each |
       each -> ({
               equality value: each.
               identity value: each.
               equality value: each.
               identity value: each.
               equality value: each.
               identity value: each } - offset) ].

And my results on CogVM:

{
       0->#(3 2 3 1 3 2).
       1->#(2 4 3 0 3 4).
       1073741823->#(3 3 2 1 3 5).
       1073741824->#(221 4 223 1 223 4).
       nil->#(14 4 14 0 15 4).
       an Object->#(14 5 13 1 14 4).
       0.0->#(622 5 623 2 624 4).
       #()->#(16 5 14 1 16 4).
       (1/2)->#(260 4 259 1 258 5)
}

So the cause of the slowdown in your #allObjectsDo: implementation is that #= is only fast if both the receiver and the argument are SmallIntegers, otherwise there will be message sends.

Another way to implement #allObjectsDo: without the marker object is to replace the loop condition with: object class == SmallInteger. It's actually the same as your implementation without the #= check. #isMemberOf: is optimized to non-real sends. This is as fast as the current implementation on my pc.


Levente

Cheers,
Juan Vuletich

On Tue, 16 Nov 2010, Eliot Miranda wrote:

Um, on Cog it sends a message if the method containing the #= has been
jitted.  But the issue is /not/ whether there is a send or not.  The issue

Does it mean, that #= can't be used in "atomic" code anymore?

Levente

is what the behaviour of the primitive code is.  In the interpreter #= will
short-circuit (avoid the send) if both the receiver and the argument are
either a SmallInteger or a Float.  In the JIT the primitive will not fail if
the receiver and argument are both SmallIntegers or Floats or if the
receiver is a Float and the argument is an Integer, but will fail if the
receiver is a SmallInteger and the argument is a Float.

snip

On 11/16/2010 8:05 PM, Levente Uzonyi wrote:

I wasn't clear when I said atomic code. I expected #= (and #<, #>, etc)
to _not_ be a real message send when both the receiver and the argument
are SmallIntegers. Otherwise what's the point of having separate
bytecodes for them?

Space. It makes a big difference for the most common selectors (#at:, #at:put:, #size, #+ etc) to be be encoded as bytecodes. It avoids having to allocate a literal every time you see the selector. Often, the special selector bytecodes look like this:

Interpreter>>bytecodePrimNextPut
       messageSelector := self specialSelector: 20.
       argumentCount := 1.
       self normalSend.

I.e., it just dispatches to normalSend where the regular lookup takes place. Of course, that also means it's a prime place for an optimization that will evaluate eagerly for known receiver types and so (over time) optimizations were added, but many of the optimizations that may make sense in an interpreter have very different tradeoffs in the jit. For a jit to generate the level of optimization makes no sense because the code size simply explodes at no benefit if the inline caches are any good (ours *are* the best Eliot knows how to do and that is a meaningful statement).

On to a finer point. The terminology "real message send" is misleading. Generally, we (the VM hackers) mean by "real" send a send that requires a method activation, i.e., the creation of a context, but *not* the lookup of the method. That excludes for example all (successful) primitives from being "real sends", and as a consequence writing "1 + 2" is not a real send by that measure (with or without the bytecode present) since the primitive will be executed successfully and no "real" send (method activation) has taken place.\

To make matters more complicated, when we talk about "real" sends in the context of thread switches, semaphores and critical sections, what we mean is whether there is a suspension point in the send or not. Obviously, some primitives (#suspend, #yield) must have suspension points so not all activation-free methods are also suspension-point-free. I am not entirely sure what the current set of rules for suspension points in Cog is; in the interpreter it was part of the activation sequence so any primitive that isn't process related would not have a suspension point but I don't know if that's still true in Cog.

Cheers,
 - Andreas

On Tue, Nov 16, 2010 at 3:32 PM, Levente Uzonyi <[hidden email]> wrote:

On Tue, 16 Nov 2010, Juan Vuletich wrote:

Hi Levente,

Levente Uzonyi wrote:

Hi,

I'm mostly ready with this cleanup, only a few methods left in the image that use #== for integer comparison. Some of them must use #==, others may be changed, but I wasn't sure if the code will work if it's changed or not. If you'd like to check these methods, then evaluate the following in a workspace:

... code here...

Cheers,
Levente

Thanks for the snippet! It is now a method in Cuis. I also checked a bit on trunk. In all senders of #nextObject you can apply the pattern in #allObjectsDo:. Instead of assuming == 0 for last #nextObject, it assumes that Object new will go at the end. If that ever changed, a few places would need fixing...

I'm not sure if it's ok to use that pattern in ImageSegment. Even if it's ok, the code is so messy, that it seems to be hard to apply the pattern without breaking the code.

As an experiment, in #allObjectsDo: I tried to remove the Object new stuff and replace with '[ 0 = object and: [ object isMemberOf: SmallInteger ]] whileFalse: ', but my test became extremely slow. I suspect #= is sending the message even if it has its own bytecode... So, the only method that remains with the '0 ==' pattern in Cuis is #critical:ifLocked: , as I'm not sure if we can clean it.

#= is a special selector, so I'm sure it won't send a message if it doesn't have to.

Um, on Cog it sends a message if the method containing the #= has been jitted.  

But the issue is /not/ whether there is a send or not.  The issue is what the behaviour of the primitive code is.  In the interpreter #= will short-circuit (avoid the send) if both the receiver and the argument are either a SmallInteger or a Float.  In the JIT the primitive will not fail if the receiver and argument are both SmallIntegers or Floats or if the receiver is a Float and the argument is an Integer, but will fail if the receiver is a SmallInteger and the argument is a Float.

 

In general the VM is free to fail for non-matching numeric types (this is historical, derived from the blue book) so I don't feel Cog is at fault here.  Certainly it is not answering incorrect results; it is simply taking more sends to produce the result in some circumstances. I think in cases like this (where you're enumerating over all objects) using #== is a wiser choice.

HTH

It's possible that #= is a bit slower than #== because it has to do some extra checks, but the difference is probably neglible. Here's a benchmark:

| offset equality identity |
Smalltalk garbageCollect.
offset := [ 1 to: 1000000 do: [ :i | ] ] timeToRun.
equality := [ :x | [ 1 to: 1000000 do: [ :i | 0 = x ] ] timeToRun ].
identity := [ :x | [ 1 to: 1000000 do: [ :i | 0 == x ] ] timeToRun ].
{ 0. 1. SmallInteger maxVal. SmallInteger maxVal + 1. nil. Object new. 0.0. Array new. 1/2 } collect: [ :each |
       each -> ({
               equality value: each.
               identity value: each.
               equality value: each.
               identity value: each.
               equality value: each.
               identity value: each } - offset) ].

And my results on CogVM:

{
       0->#(3 2 3 1 3 2).
       1->#(2 4 3 0 3 4).
       1073741823->#(3 3 2 1 3 5).
       1073741824->#(221 4 223 1 223 4).
       nil->#(14 4 14 0 15 4).
       an Object->#(14 5 13 1 14 4).
       0.0->#(622 5 623 2 624 4).
       #()->#(16 5 14 1 16 4).
       (1/2)->#(260 4 259 1 258 5)
}

I'd do many more iterations.  I wouldn't put any faith any millisecond numbers that are less than 3 digits (100 ms).

 

So the cause of the slowdown in your #allObjectsDo: implementation is that #= is only fast if both the receiver and the argument are SmallIntegers, otherwise there will be message sends.

Another way to implement #allObjectsDo: without the marker object is to replace the loop condition with: object class == SmallInteger. It's actually the same as your implementation without the #= check. #isMemberOf: is optimized to non-real sends. This is as fast as the current implementation on my pc.


Levente

Cheers,
Juan Vuletich

On Wed, Nov 17, 2010 at 1:13 AM, Eliot Miranda <[hidden email]> wrote:

On Tue, Nov 16, 2010 at 3:32 PM, Levente Uzonyi <[hidden email]> wrote:

On Tue, 16 Nov 2010, Juan Vuletich wrote:

Hi Levente,

Levente Uzonyi wrote:

Hi,

I'm mostly ready with this cleanup, only a few methods left in the image that use #== for integer comparison. Some of them must use #==, others may be changed, but I wasn't sure if the code will work if it's changed or not. If you'd like to check these methods, then evaluate the following in a workspace:

... code here...

Cheers,
Levente

Thanks for the snippet! It is now a method in Cuis. I also checked a bit on trunk. In all senders of #nextObject you can apply the pattern in #allObjectsDo:. Instead of assuming == 0 for last #nextObject, it assumes that Object new will go at the end. If that ever changed, a few places would need fixing...

I'm not sure if it's ok to use that pattern in ImageSegment. Even if it's ok, the code is so messy, that it seems to be hard to apply the pattern without breaking the code.

As an experiment, in #allObjectsDo: I tried to remove the Object new stuff and replace with '[ 0 = object and: [ object isMemberOf: SmallInteger ]] whileFalse: ', but my test became extremely slow. I suspect #= is sending the message even if it has its own bytecode... So, the only method that remains with the '0 ==' pattern in Cuis is #critical:ifLocked: , as I'm not sure if we can clean it.

#= is a special selector, so I'm sure it won't send a message if it doesn't have to.

Um, on Cog it sends a message if the method containing the #= has been jitted.  

Hi Eliot. I have just read the whole thread, but I wanted to ask you something about this line. Did I understand correct??  If #= has already been jitted, then Gog doesn't use the short-circuit sends (#bytecodePrimEqual) but it does a normal send (a primitive in this case)?  So...suppose I change SmallInteger >> #=   and I put a halt, then if will be halted (and broke everything, of course) once that method was jitted ?

And I guess the same happens with all special selectors.

Thanks

Mariano

 

But the issue is /not/ whether there is a send or not.  The issue is what the behaviour of the primitive code is.  In the interpreter #= will short-circuit (avoid the send) if both the receiver and the argument are either a SmallInteger or a Float.  In the JIT the primitive will not fail if the receiver and argument are both SmallIntegers or Floats or if the receiver is a Float and the argument is an Integer, but will fail if the receiver is a SmallInteger and the argument is a Float.

 

In general the VM is free to fail for non-matching numeric types (this is historical, derived from the blue book) so I don't feel Cog is at fault here.  Certainly it is not answering incorrect results; it is simply taking more sends to produce the result in some circumstances. I think in cases like this (where you're enumerating over all objects) using #== is a wiser choice.

HTH

It's possible that #= is a bit slower than #== because it has to do some extra checks, but the difference is probably neglible. Here's a benchmark:

| offset equality identity |
Smalltalk garbageCollect.
offset := [ 1 to: 1000000 do: [ :i | ] ] timeToRun.
equality := [ :x | [ 1 to: 1000000 do: [ :i | 0 = x ] ] timeToRun ].
identity := [ :x | [ 1 to: 1000000 do: [ :i | 0 == x ] ] timeToRun ].
{ 0. 1. SmallInteger maxVal. SmallInteger maxVal + 1. nil. Object new. 0.0. Array new. 1/2 } collect: [ :each |
       each -> ({
               equality value: each.
               identity value: each.
               equality value: each.
               identity value: each.
               equality value: each.
               identity value: each } - offset) ].

And my results on CogVM:

{
       0->#(3 2 3 1 3 2).
       1->#(2 4 3 0 3 4).
       1073741823->#(3 3 2 1 3 5).
       1073741824->#(221 4 223 1 223 4).
       nil->#(14 4 14 0 15 4).
       an Object->#(14 5 13 1 14 4).
       0.0->#(622 5 623 2 624 4).
       #()->#(16 5 14 1 16 4).
       (1/2)->#(260 4 259 1 258 5)
}

I'd do many more iterations.  I wouldn't put any faith any millisecond numbers that are less than 3 digits (100 ms).

 

So the cause of the slowdown in your #allObjectsDo: implementation is that #= is only fast if both the receiver and the argument are SmallIntegers, otherwise there will be message sends.

Another way to implement #allObjectsDo: without the marker object is to replace the loop condition with: object class == SmallInteger. It's actually the same as your implementation without the #= check. #isMemberOf: is optimized to non-real sends. This is as fast as the current implementation on my pc.


Levente

Cheers,
Juan Vuletich