[phobos] RFC: Sealed RandAA

[David Simcha]

I've also uploaded some documentation to 
http://cis.jhu.edu/~dsimcha/randaasealed.html, though interface-wise 
it's just a standard AA implementation, so there's not much to 
document.  Please comment.

On 11/20/2010 2:14 PM, David Simcha wrote:
> I've created a sealed container implementation of RandAA for inclusion 
> in std.container.  The code is located at:
>
> http://www.dsource.org/projects/aa/browser/trunk/randAA/randaasealed.d
>
> The main advantages RandAA has over builtin AAs are:
>
> 1.  Deterministic, ref counted freeing of memory, which is important 
> for huge AAs or very memory-tight systems.
>
> 2.  Plays nicely with conservative GC.  Keys, values and hashes are in 
> separate arrays, meaning that they don't all get GC scanned just 
> because one needs to be GC scanned.  This also saves on alignment 
> overhead.
>
> 3.  The implementation is based on parallel arrays, and allows for 
> space to be reserved such that a certain number of elements can be 
> added with a guarantee of no reallocation.  Because of this, 
> insertions are much faster for large arrays.
>
> 4.  The linear congruential probing retains its O(1) expected lookup 
> time as long as there are minimal collisions in full (32- or 64-bit) 
> hash space, regardless of how many collisions there are in modulus 
> hash space.
>
> The main disadvantages are:
>
> 1.  The combination of parallel arrays and randomized probing wreak 
> havoc on cache performance, meaning lookups are somewhat slower than 
> with the builtin AA.
>
> 2.  The worst-case lookup time is unbounded, though this is more 
> theoretical trivial than a practical issue (except maybe in high 
> security situations where you shouldn't be using a hash table 
> anyhow).  The distribution of lookup times is geometric, meaning that 
> requiring more than a few probing iterations is absurdly unlikely.
>
> The two main known issues are lack of const correctness (I made no 
> attempt and won't bother until inout works reasonably well) and lack 
> of 64-bit support (because I haven't gotten around to searching for 
> good 64-bit linear congruential parameters yet).
>
> Please review the code and let me know whether it flies for 
> std.container.
>
> --David Simcha