Iterators? (Was: Squeak practical use? ...)

David Simmons David.Simmons at smallscript.com
Thu Jan 31 07:36:35 UTC 2002


Hi All,

I note that this thread is discussion performance of iterators in
Smalltalk. The SmallScript (Smalltalk iteration) based code is pretty
darn performance competitive with C++ code. SmallScript provides
hi-performance blocks and related jit services are available for
eliminating range checks on array bounds that are known, etc. 

Benchmarks a few months back, comparing SmallScript collections like
<Dictionary>, showed that SmallScript was the fastest available
Smalltalk implementation (for this iterator/collection example) in the
JIT category [VW, VAST, MT]. And was a lot faster than any of the
interpreter implementations like Squeak and Dolphin. To get a sense of
what we are talking about, SmallScript was anywhere from 2X-4X faster
than the best of the other jitted Smalltalks, and 100's of times faster
than the interpreted Smalltalks. 

The point here is not that SmallScript is any worse or better than some
other Smalltalk [better is entirely subjective based on numerous
factors]. The importance of my comments here are that it illustrates
that the performance issues are not inherent to the type of language
that Smalltalk represents. I.e., if SmallScript can execute pure-classic
Smalltalk code at speeds that are competitive with C++ then it is not a
Smalltalk language issue, but an implementation question. A big factor
of which can be fundamental algorithm issues resulting from core
language implementation decisions.
---
Here is more discussion of what is possible within the collective set of
available Smalltalk dialects. The point here is to encourage Squeak
developers to see what is done in SmallScript, and what it achieves. It
might yield good patterns for evolving and growing Smalltalk in the
Squeak dialect...

So, on a related note, to the topics in this thread, SmallScript
directly supports tail-recursion in the JIT opcode set.  You can specify
that a message always tail-called, never tail-called, or left up to the
JIT to decide which it should be. The virtual machine also has specific
support for control/exceptions relating to stack overflow (recursion)
management and debugging.

On the less obvious side, I use tail-calls fairly often to hide
intermediate router methods from a stack frame walker as well. Like with
exception routing code.

SmallScript also provides zero cost exception handling which is
supported via its zero-cost downward continuations (as they are called
in scheme).

You just annotate return operations with the keywords "tail:" or
"notail:" for explicit control.

Here is some information from a post I made a while back on the MIT
Dynamic Languages Discussion Group:

==== BEGIN ====
In SmallScript/Smalltalk everything is an object, and every operation is
a message. Which means every operation results in an object. So, as this
discussion is attempting to define things, Smalltalk has no concept of a
"statement". 

The "default" rule in Smalltalk is that the last expression executed
provides the value of an expression. For some expressions, they are
explicitly defined to return/evaluate-as <nil> (the singleton of
<UndefinedObject>).

So we can write expressions like:

    [:i| expr1] whileTrue: [:j| expr2].

Where the <i> value is the result of the last <expr2>, and the <j> value
is the result of the last <expr1>. And the initial seed value if <i> is
<nil>.

We can write:

    |r| := if(expr) 
    [:i| 
        ...
    ] 
    else 
    [:i|
        ...
    ].

Where <i>, for either case, will be the object returned by <expr>. The
value of <r> will be the last expression evaluated in either the
eqv-true or eqv-false block (context/closure).

If we write:

   |r| := if(expr) [...].

Then if <expr> is eqv-true, then <r> is set to the last expression
evaluated in the eqv-true block. But, if <expr> is eqv-false then <r> is
set to the <expr> value itself.

Same rules apply for other sugar forms:

    unless(...)
    assert(...)
    while(...)
    do [...] while(...)
    until(...)
    do [...] until(...)
    switch(...) [...]
    try [...] ...catches...fault...finally.
    etc.

And you can design/write your own control structures to do anything you
want including tail-call looping, etc. 

    Method behavior: Object [
    myLoop(expr)
        ^if (self()) [:v|tail:^myLoop(expr(v))]
    ]

The notion that everything is an object, and that expression results get
injected into "apparent" control forms is often exploited for lazy
initializers. Commonly, this is done using the binary-message #? that
tests to see if a value is <nil>. I say apparent, because all (looping)
control forms are really built from messaging that utilizes tail calls,
and or (optionally-labeled) branches.

   ^var ? [var := initExpr]

    expr !? [v:...].

==== END ====
	

-- Dave S. [SmallScript LLC]

SmallScript for the AOS & .NET Platforms
David.Simmons at SmallScript.com | http://www.smallscript.org


> -----Original Message-----
> From: squeak-dev-admin at lists.squeakfoundation.org [mailto:squeak-dev-
> admin at lists.squeakfoundation.org] On Behalf Of Jimmie Houchin
> Sent: Wednesday, January 30, 2002 11:34 AM
> To: squeak-dev at lists.squeakfoundation.org
> Subject: Re: Iterators? (Was: Squeak practical use? ...)
> 
> Would it be reasonable to implement it in such a way that tail
recursion
> could be explicitly requested by the programmer? The default would
> remain as it is and tail recursion could be an optimizing option.
> 
> Just a thought.
> 
> Jimmie Houchin
> 
> Jesse Welton wrote:
> 
> [snip recursion discussion]
> > I remember this being discussed here on the list some time back.  It
> > sounded like it would not be difficult to change the system to
enable
> > tail recursion optimization, though I don't recall whether a
compiler
> > change would be sufficient, or a VM change would be necessary in the
> > general case.  (I think a compiler change is sufficient, at least,
for
> > self-recursive methods, but possibly not for mutual recusion.)  As
to
> > whether it would be a good idea, the consensus seemed to be that it
> > would interfere too much with the debugger's strengths.  (Tail
> > recursion optimization effectively erases all record of intermediate
> > calls, making it much harder (or impossible) to back-trace the
> > execution of a running program.)
> >
> > -Jesse
> 
> 





More information about the Squeak-dev mailing list