• Ben Hinkle (16/16) Aug 08 2005 I've made a small but effective change to the AAs in MinTL HashAA and

"Ben Hinkle" <ben.hinkle gmail.com> writes:

I've made a small but effective change to the AAs in MinTL HashAA and 
SortedAA. They now allocate nodes in blocks of 10 and store deleted nodes on 
a freelist. If the node size is bigger than 96 bytes it doesn't block 
allocate. The cutoff was determined through testing how long it takes to 
clear the node when recycling vs always allocating. So now if you repeatedly 
add and remove at the same rate from a HashAA or SortedAA the memory usage 
does not increase (at least due to the nodes - the keys and values are the 
user's responsibility). The principle is the same as the block allocation in 
the linked lists containers - the power of GC combined with pointers into 

and C++ lacks a builtin GC).

On simple tests involving builtin AA and HashAA the HashAA is faster by 
anywhere from 10% to 100% depending on how much the AA is the bottleneck and 
how much recycling is going on.

I'll be looking more closely at HashAA and SortedAA performance to see what 
else can be done to speed things up.