[armedbear-devel] (lisp) Stack management efficiency

[Erik Huelsmann]

On Tue, Jul 21, 2009 at 4:52 PM, Tobias C. Rittweiler<tcr at freebits.de> wrote:
> Ville Voutilainen writes:
>
>> 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.
>
> To remedy this problem, you typically make a new chunk twice as large as
> the last chunk. And you only deallocate, if your actually consumed
> capacity falls below 1/4 of the total capacity. This results in
> amortized constant time for insertion/deletion.
>
> You don't have to hack that up from scratch, btw: it's what Java's
> ArrayList does. (Which is not synchronized.)

Ok. I can easily hack this into my current pending patch. It would
also eliminate the need to create a Cons for every stack frame,
because I wouldn't be storing the elements in a linked list anymore.

Let's see what this does for performance when I finish later today.


Bye,

Erik.