digitalmars.D.dtl - mintl update: AA memory usage
- Ben Hinkle (16/16) Aug 08 2005 I've made a small but effective change to the AAs in MinTL HashAA and
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 arrays is something Java/C# and C++ can't easily match (Java lacks pointers 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.
Aug 08 2005