Interpreter refactoring

[Luca Bruno]

Hello,
the development is currently a bit stalled because of university and
other jobs but the project is not dead, don't worry.
I'm working on a new interpreter implementation, a new branch has been
created named "newinterp".
Well, it's not bytecode related but context related.

With latest changes the project currently use one stack per process, but
still takes references from contexts.
I don't know yet but i think removing contexts would both improve speed
and use less resources.

Currently for each new method call or block call a new context is
created, this means more objects in the heap to be garbage collected,
more objects to create, more conversions context-execution to do.

My idea is to remove contexts from normal interpreter usage and to put
all needed informations onto the process stack. This means a huge
refactoring for both the interpreter and the parser, that has been
already done partially in the newinterp branch.

How to get a context?

1) If something external to the interpreter wants to enter a context and
to make any changes to it, a context must be created and pass it to the
interpreter: this avoids the application from dealing with frames/stack
and to make things easier for applications embedding Syx.
The API has been slightly changed for creating contexts.

2) Yet again, if something external wants to access any context, (for
instance the exceptions) this can be always done. thisContext, aProcess
context, aContext parent, etc., will be able to reconstruct a context
from the relative frame.

Hopefully all this work won't break primitives API.

Any hints?

--
http://lethalman.blogspot.com - Thoughts about computer technologies
http://syx.googlecode.com - Smalltalk YX project
http://www.ammazzatecitutti.org - E adesso ammazzateci tutti

[Lethalman]

Preliminary stupid benchmarks (the ones in the tests directory)
against trunk says:
- GC hasn't be called all the time
- Up to 2 times faster
- Up to 1/3 less instructions used

The parser is still the same, and primitives didn't change.
Exception still don't work because i've to refactor the Smalltalk-side
and add primitives to deal with frames.

[fjmilens3]

Going by my relatively limited knowledge, I think that you have a good
idea here; from what I recall, you've already taken care of the
straightforward cases by inlining the blocks in #ifTrue:ifFalse:,
#whileTrue:, #whileFalse:, and so on, so this seems like a logical
next step with context optimization.

Based on what I know, putting contexts on the stack for most
situations is actually a relatively common optimization for Smalltalk
implementations. If you're looking for more information, I think you
might want to do a search in whatever literature you can get on
"context to stack mapping" and see what you can find out. My first
thought would be to check the ACM Online Library (which I no longer
have a membership for) and see what papers were published, probably in
the 1980s and early 1990s, regarding stack optimizations like this.
Some other sources which I don't have access to at the moment are
mentioned in a comp.lang.smalltalk post by Eliot Miranda, which came
up as one of the few results in a search I just did on Google:

http://groups.google.com/group/comp.lang.smalltalk/msg/2805af1fbc4f8548

Another idea that's simpler but less fast than a complete context to
stack mapping alternative is to do what some Smalltalk implementations
have done in the past and maintain a "free list" of context objects; I
know Little Smalltalk did this at one point, and there may be other
"real" Smalltalks out there that still use this technique as well.
The basic idea is that you amortize the cost of allocating a context
by keeping it around on the free list when no longer in use; that way
when you need a new one, hopefully you can just find one of a large
enough size from the free list of already-allocated contexts. I'm not
sure this approach would be that worthwhile, however, since you've
already done so much work refactoring your interpreter to actually
handle the issues for context-to-stack mapping.

I wouldn't worry too much about breaking the primitives API. One, Syx
is still early enough in its development that there shouldn't be a lot
of legacy code for it. Two, any code that relies on the primitives
API was probably written by someone familiar enough with Smalltalk
that they would be able to refactor their code when/if the new changes
are put into the next Syx release.

That said, reading your more recent message, I'm not sure you'll
actually find anything I've sent useful; you seem as though you're way
ahead of what I've posted here, but I thought I would send it along
anyway. :-)

-- Frederick

>  signature.asc
> 1KDownload

[Luca Bruno]

> Based on what I know, putting contexts on the stack for most
> situations is actually a relatively common optimization for Smalltalk
> implementations. If you're looking for more information, I think you
> might want to do a search in whatever literature you can get on
> "context to stack mapping" and see what you can find out. My first
> thought would be to check the ACM Online Library (which I no longer
> have a membership for) and see what papers were published, probably in
> the 1980s and early 1990s, regarding stack optimizations like this.
> Some other sources which I don't have access to at the moment are
> mentioned in a comp.lang.smalltalk post by Eliot Miranda, which came
> up as one of the few results in a search I just did on Google:
>
> http://groups.google.com/group/comp.lang.smalltalk/msg/2805af1fbc4f8548

Thanks very much, i'll take care of that. I read the message in the group and I've
already solved the two problems relative to the mapping.

I solved those for blocks by storing the the entire frame (without the stack) to the outerFrame variable
of the BlockClosure.
And, for what concerns the use of the context object, i create an array that points directly to the
frame.
Obviously i still didn't test it deeply but i hope the current refactoring put everything the right way
for tuture fixes ;)

> Another idea that's simpler but less fast than a complete context to
> stack mapping alternative is to do what some Smalltalk implementations
> have done in the past and maintain a "free list" of context objects; I
> know Little Smalltalk did this at one point, and there may be other
> "real" Smalltalks out there that still use this technique as well.
> The basic idea is that you amortize the cost of allocating a context
> by keeping it around on the free list when no longer in use; that way
> when you need a new one, hopefully you can just find one of a large
> enough size from the free list of already-allocated contexts. I'm not
> sure this approach would be that worthwhile, however, since you've
> already done so much work refactoring your interpreter to actually
> handle the issues for context-to-stack mapping.

I don't think it's both simple and less expensive. First of all you need
to create all such objects.
Everytime you enter a new context, you have to store arguments,
temporaries, ecc., this means accessing variables and data of the
object, which means more C accesses than a straight pointer to the
frame.
And, if the stack size is not enough you have to reallocate.

Well, if you see, i create a Process with fixed size and never
reallocate it to hold new objects. For now i like it so, but I have to
do some more checks on that.
With this system, all in one stack, you can control max recursion limit
and stack size exceeding. This is not possible with contexts, or better,
it's more difficult to handle.
Take for example a recursion with contexts, you will get always more and
more contexts and the GC won't be able to free all objects and always
expand the memory size, but it will be very difficult to know if it's a
wanted recursion and to understand it's a recursion.

With this system i know what's the bottle neck of the stack and raise an
error whenever the stack pointer exceeds this size. Much more like
Python does when you enter an unwanted infinite loop, which IMHO, is
pretty useful to avoid your application hang and lose informations not
yet saved to the image.

> I wouldn't worry too much about breaking the primitives API. One, Syx
> is still early enough in its development that there shouldn't be a lot
> of legacy code for it. Two, any code that relies on the primitives
> API was probably written by someone familiar enough with Smalltalk
> that they would be able to refactor their code when/if the new changes
> are put into the next Syx release.
>
> That said, reading your more recent message, I'm not sure you'll
> actually find anything I've sent useful; you seem as though you're way
> ahead of what I've posted here, but I thought I would send it along
> anyway. :-)

Everything is good to know for me, I always learn new things.
Thanks very much :) feel free to continue replying.