On Mon, 22 Mar 2010 16:59:36 -0500, Andrei Alexandrescu wrote: > On 03/22/2010 04:03 PM, Andrei Alexandrescu wrote: >> On 03/22/2010 03:36 PM, Walter Bright wrote: >>> Andrei Alexandrescu wrote: >>>> Better suggestions are always welcome. For integrals I'm unclear on >>>> what we could use to make things better. (Clearly we could and should >>>> get rid of the extraneous field.) >>> >>> Unfortunately, it won't be much of a win. Memory allocation is done in >>> buckets of size 16, 32, 64, etc. Reducing the node size for a >>> uint[uint] from 16 to 12 saves no memory at all. >> >> As we discussed, if nodes are allocated in bunches, you could store 5 >> nodes in a 64-byte block instead of 4. That's more than a 25% increase >> in effectiveness because the per-block bookkeeping is also slashed by >> 5. >> >> Andrei > > One more idea before I forget: the bunches approach requires using a > freelist for nodes that are available but not used. (Freelists are a > good idea whether or not bunches are used.) > > One good possibility is to store the head of the freelist in a static > variable, such that e.g. all int[string] instances use the same > freelist. And there's no thread contention issue because each thread has > its own freelist. > > > Andrei
I just committed a aaA.d version that uses some heap node memory management, although its on a per class instance basis. Also it dispences with a separate hash storage for keys <= size_t. Sharing would mean some working out of which classes share the same sized node blocks. Much easier to implement class sharing using templates. See the code here : http://www.dsource.org/projects/aa/browser/trunk/ druntime/aaA.d See the benchmarks and comments here : http://www.dsource.org/projects/aa/ wiki/DrunTimeAA. The result squeezes some extra performance for integer or less sized keys (about 20% faster for lookups). For the druntime, the generic C interface constrains the kinds of specialized AA versions that can be instantiated using run-time TypeInfo and var-arged calls. Maybe a class / interface direct calls would work better. Just imagine at runtime looking at the TypeInfo_AssociatedArray and trying to work out exactly which template is going to be instantiated. And having a low code size, one or few versions fit all approach, that performance sacrifice is unavoidable in a basic runtime libary. But in template land , options and combinations and gains abound. --- Michael Rynn
