[armedbear-devel] (lisp) Stack management efficiency

[Tobias C. Rittweiler]

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.)

  -T.

-- 
Diese Nachricht wurde auf Viren und andere gefaerliche Inhalte untersucht
und ist - aktuelle Virenscanner vorausgesetzt - sauber.
Freebits E-Mail Virus Scanner