Idea for a possibly better Collection occurrencesOf method.

Hi J J,

on Tue, 12 Sep 2006 14:13:00 +0200, you wrote:

> Nice, sounds like a done deal then.  Will this make 3.9 release? :)

Changing the VM for local purposes is easy (in Squeak!), would like to  
have more time for "my daily Squeak VM change". BTW: how cool that sounds,  
versus "changing the Java / Ruby / Python / put your varorite here / VM,  
for local purposes is easy" </grin>

But I think this is something for a 1.0 Exupery release; if I understand  
Bryce correctly he aims to outperform a certain commercial VM and  
MethodContext>>#apply:from:to: looks like it's worth the effort (of  
course, with fall back to good old #do: code-in case the new primitive is  
missing). My CHF 0.05.

OT[.ch only]: I owed the community CHF 0.03 because last time I wrote CHF  
0.02 :) Payed.

/Klaus

It is another world to be sure. :)

>But I think this is something for a 1.0 Exupery release; if I understand  
>Bryce correctly he aims to outperform a certain commercial VM and  
>MethodContext>>#apply:from:to: looks like it's worth the effort (of  
>course, with fall back to good old #do: code-in case the new primitive is  
>missing). My CHF 0.05.
>

Exupery is a JIT, no?  JIT is certainly important and very needed, but will
future squeaks use it by default?

If we put in the #apply:from:to: in 3.9 or 3.10 or whatever, then we could
go and clean up all the "rolll your own" count:, etc.'s out there.

Hi J J,

on Tue, 12 Sep 2006 16:44:24 +0200, you wrote:

>> From: "Klaus D. Witzel" <[hidden email]>
...
>> But I think this is something for a 1.0 Exupery release; if I  
>> understand  Bryce correctly he aims to outperform a certain commercial  
>> VM and  MethodContext>>#apply:from:to: looks like it's worth the effort  
>> (of  course, with fall back to good old #do: code-in case the new  
>> primitive is  missing). My CHF 0.05.
>>
>
> Exupery is a JIT, no?

Yup, a JIT.

> JIT is certainly important and very needed, but will
> future squeaks use it by default?

I expect cross-fertilization (yes, I'm here in squeak-dev and I use the  
word expect ;-). Imagine that #apply:from:to: runs in Exupery, is tested  
and does what is expected. Then a handful of copy&paste's (or  
fileOut/fileIn)s later the code can be in a non-JIT VM...

> If we put in the #apply:from:to: in 3.9 or 3.10 or whatever, then we  
> could
> go and clean up all the "rolll your own" count:, etc.'s out there.

Smalltalkers usually don't wait for x.y or whatever: the primitive  
associated with #apply:from:to: must be backed by Smalltalk code because  
it (the primitive) may fail or may only be available together with a  
JITter. In both cases the Smalltalk code must already exist and run  
(hopefully) bug free.

Of course, what'd also be needed is a commitment from the VM folks to  
include the new primitive.

/Klaus

Are the VM folks on this list?

>/Klaus

>
> Of course, what'd also be needed is a commitment from the VM folks  
> to include the new primitive.
>
> /Klaus

Oh, if anyone comes up with a suitable primitive that
a) works
b) fails sensibly
c) actually does improve real performance in sensible benchmarks
then I think I  can guarantee inclusion.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful Latin Phrases:- Mellita, domi adsum. = Honey, I'm home.

Klaus D. Witzel writes:

 > But I think this is something for a 1.0 Exupery release; if I understand  
 > Bryce correctly he aims to outperform a certain commercial VM and  
 > MethodContext>>#apply:from:to: looks like it's worth the effort (of  
 > course, with fall back to good old #do: code-in case the new primitive is  
 > missing). My CHF 0.05.

The right way to optimise occurrencesOf: is to write it using count:
then to inline away the overhead of using #do: by using an inlining
JIT as Nicolas suggested. My aim is to add inlining to Exupery in 2.0.

The goal of 1.0 is to provide a useful speed improvement to
Squeak. That involves making Exupery more reliable and implementing
key primitives. Unfortunately, many inner loops in Squeak spend most
of their time calling primitives so improve their performance I need
to reimplement the primitives. Exupery has been faster than
VisualWorks for the bytecode benchmark for over a year now.

I could have also said that the goal for Exupery 1.0 is to provide
everything necessary to benefit from method lining except for method
inlining. Exupery can inline primitives already.

Bryce

Thank you for your statements and suggestions Bryce.

/Klaus

On Tue, 12 Sep 2006 21:07:12 +0200, Bryce Kampjes wrote:

Bryce Kampjes wrote:
> Unfortunately, many inner loops in Squeak spend most
> of their time calling primitives so improve their performance I need
> to reimplement the primitives.

Bryce, does this mean: you rewrite the (c) primitives as squeak methods, so
that exupery can compile them ?

Simon Michael writes:
 > Bryce Kampjes wrote:
 > > Unfortunately, many inner loops in Squeak spend most
 > > of their time calling primitives so improve their performance I need
 > > to reimplement the primitives.
 >
 > Bryce, does this mean: you rewrite the (c) primitives as squeak methods, so
 > that exupery can compile them ?

No, I rewrite the primitives in Exupery to generate intermediate
language. This way Exupery can compile them into native code. This is
the right approach for the heavily used primitives such as #at:, #new,
and #size. Exupery will specialise the primitive for it's receiver
type when it compiles it.

For less frequently called primitives or when it's not possible to
specialise the primitive it would probably be sensible to call the C
primitive function.

Bryce

Ok,

so are there any VM primitive writers out there who would be interested in
tackling this?  I'm afraid that this sort of thing is beyond me at the
moment. :)  It seems like something that could make a big positive impact.

On Tue, 12 Sep 2006 20:27:24 +0000, "J J" <[hidden email]> wrote:

> so are there any VM primitive writers out there who would be interested in
> tackling this?  I'm afraid that this sort of thing is beyond me at the
> moment. :)  It seems like something that could make a big positive impact.

One of the obvious issues with writing this is the VM needs to be able to
evaluate the block (arbitrary Smalltalk code) from within a primitive. I'm
not sure how easy (or even possible) this is in Squeak.

Later,
Jon

--------------------------------------------------------------
   Jon Hylands      [hidden email]      http://www.huv.com/jon

  Project: Micro Seeker (Micro Autonomous Underwater Vehicle)
           http://www.huv.com

My understand was that it is doing that now with some of the other
primitives.  Klaus, did I misunderstand?

On Tue, 12 Sep 2006 22:36:30 +0200, Jon Hylands wrote:
Just activating a block from within the VM is nothing new, there are some  
GOF primitives which do that already; take #value: <primitive: 81> as an  
example-it's there for being reused.

I think that the problems lurk around another corner: all the kangaroo  
cases, i.e. #on:do:, #ensure: and #ifCurtailed:, to name prominent  
examples (also #primitiveTerminateTo and friends). And then there is  
naughty stack manipulator named debugger.

But, fortunately, there is plenty of self-documenting code (with comments,  
also methods based on Blue Book concepts), in the "process primitives"  
message category of class Interpreter :)

> Later,
> Jon

Hi Bryce,

turning the suggested primitive behind BlockContext>>#apply:from:to: into  
a #primitiveValue is, after checking receiver and arguments, easy.

Problems come as soon as the block later sends, whereafter #commonReturn  
does no longer know anything about #primitiveApplyFromTo. This asks for  
something that stores such state, for example by making a  
MethodContext>>#apply:from:to:on: solution (with last argument the block).

I can imagine that Exupery encounters similar situations (i.e. native code  
does a full send for whatever reason). Is there something that can be  
learned (or, perhaps, even copied) from Exupery.

/Klaus

On Tue, 12 Sep 2006 21:07:12 +0200, Bryce Kampjes wrote:

> turning the suggested primitive behind BlockContext>>#apply:from:to: into
> a #primitiveValue is, after checking receiver and arguments, easy.

How does that work together with continuations? I guess the state
(iteration index) is stored in the C stack and cannot be captured by
looking at thisContext, right?

Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Hi Lukas,

on Wed, 13 Sep 2006 14:59:42 +0200, you wrote:

>> turning the suggested primitive behind BlockContext>>#apply:from:to:  
>> into
>> a #primitiveValue is, after checking receiver and arguments, easy.
>
> How does that work together with continuations?

:) Nice question, important as well.

> I guess the state
> (iteration index) is stored in the C stack and cannot be captured by
> looking at thisContext, right?

No, nothing can be stored in the C stack. Say we have ... apply: seqColl  
from: here to: there, then at each iteration the VM does here := here + 1  
(that's a privilege of the VM). Later when #commonReturn comes back, the  
situation is precisely as it was at the time of the first call, expect  
that argument 'here' reflects the progress. And kangaroo and debugger and  
friends are not affected.

It is because of the latter that I'd say that that works in harmony with  
continuations.

/Klaus

>
> Lukas
>

The following two demoes show a factor of ca. 3 in their timeToRun. The  
first sends #to:do: for the iteration, the other does just its inlined  
bytecodes. The blocks are not noop and compute and return the same (same  
also in the respective #to:do:).

Expression (0.5 * SmallInteger maxVal) sqrt truncated * 456 means: just  
use SmallIntegers, no boxed LargeIntegers. You can adjust the 456  
parameter to your machine, timeToRun should not show less than 1,000 in  
either case. Doing a garbageCollect removed some nervousity with smaller  
runs here.

------------
| aBlock |
  aBlock := [:int | int + 1 ].
  Smalltalk garbageCollect.
  [1 to: (0.5 * SmallInteger maxVal) sqrt truncated * 456 do: aBlock]  
timeToRun
=> 3707
------------
  Smalltalk garbageCollect.
  [1 to: (0.5 * SmallInteger maxVal) sqrt truncated * 456 do: [:int | int  
+ 1 ]] timeToRun
=> 1274
------------

I doubt that a primitive implementation would show a significantly better  
factor, because the VM already is fast! and because in practice the  
#to:do: intervals are usually smaller than in the above. The only  
difference I saw in the bytecodes was related to the #to:do: and #value:  
message send.

Is the above what the community expects, have better demoes, how's it on  
your platform (have windoze XP here).

/Klaus

On Tue, 12 Sep 2006 12:19:02 +0200, Jon Hylands wrote:

On Wed, 13 Sep 2006 18:10:30 +0200, "Klaus D. Witzel"
<[hidden email]> wrote:

> I doubt that a primitive implementation would show a significantly better  
> factor, because the VM already is fast! and because in practice the  
> #to:do: intervals are usually smaller than in the above. The only  
> difference I saw in the bytecodes was related to the #to:do: and #value:  
> message send.

The point of the #apply... primitive is so that all the enumeration methods
run as fast as #to:do:, so you don't have to worry about trading off code
clarity and re-use for performance.

Later,
Jon

--------------------------------------------------------------
   Jon Hylands      [hidden email]      http://www.huv.com/jon

  Project: Micro Seeker (Micro Autonomous Underwater Vehicle)
           http://www.huv.com

How hard do you think it would be to impliment this for squeak (native I
mean, not in the JIT)?

But I wonder, if VAST problems with seaside are related to something
like that ;)

Danil