On Tue, Jul 21, 2009 at 4:52 PM, Tobias C. Rittweilertcr@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.