[armedbear-devel] (lisp) Stack management efficiency

[Ville Voutilainen]

On Tue, Jul 21, 2009 at 4:03 PM, Matt Lamari<matt.lamari at gmail.com> wrote:
> I'm kinda new here, and maybe I'm not fully grasping what you mean. . . . .

There are no problems for which ascii graphics don't provide a
solution/explanation. :)

Let's say we have a call stack of three functions, aka we have three frames:

[FFFUUUUUUU]

I'm assuming we have 10 frames per chunk. That's for explanation only,
it's just an example value.
F is a frame object, U is an unused placeholder. We may create the
frame objects when allocating
the chunk, or we may do it in a delayed fashion. That's something an
experiment will reveal.
If we make 8 more calls, we would get

[FFFFFFFFFF][FUUUUUUUUU]

So we needed to allocate a new chunk.

Now, when we unwind one frame, we get

[FFFFFFFFFF][RUUUUUUUUU]

where R is a frame object that can be recycled. So, if we call a
function there, we get

[FFFFFFFFFF][FUUUUUUUUU]

we re-used an existing frame object, without having to recreate it. By
tuning the chunk
granularity in a reasonable manner, we get bulk allocation for the
chunk, which helps the
speed, and we don't need to reallocate when a frame object can be
recycled. Moreover,
we don't need to hold on to the frame objects forever, as this is an
intermediate compromise
solution. In theory, this should result in not having leaks, and
having fewer allocator calls.

For garbage collecting, if we unwind the last example by, let's say,
two frames, we get

[FFFFFFFFFR]

where we get rid of the second chunk and recycle the first. Thus the
second chunk becomes
collected at this point. This obviously means that if there are many
calls at the chunk boundary,
we allocate and collect the second chunk continuously. No solution is
perfect, I guess.