D hash table comparison benchmark

[Nathan S.]

Benchmark code:

dub.sdl
```
name "hashbench"
description "D hashtable comparison."
dependency "emsi_containers" version="~>0.7.0"
dependency "memutils" version="~>0.4.11"
dependency "vibe-d:utils" version="~>0.8.4"
dependency "jive" version="~>0.2.0"
//dependency "collections" version="~>0.1.0"
//dependency "tanya" version="~>0.10.0"
//dependency "kontainer" version="~>0.0.2"
```

app.d
```d
int nthKey(in uint n) @nogc nothrow pure @safe
{
     // Can be any invertible function.
     // The goal is to map [0 .. N] to a sequence not in ascending 
order.
     int h = cast(int) (n + 1);
     h = (h ^ (h >>> 16)) * 0x85ebca6b;
     h = (h ^ (n >>> 13)) * 0xc2b2ae35;
     return h ^ (h >>> 16);
}

pragma(inline, false)
uint hashBench(HashTable, Args...)(in uint N, in uint seed, Args 
initArgs)
{
     static if (initArgs.length)
         HashTable hashtable = HashTable(initArgs);
     else // Separate branch needed for builtin AA.
         HashTable hashtable;

     foreach (uint n; 0 .. N)
         hashtable[nthKey(n)] = n + seed;

     uint sum;
     foreach_reverse (uint n; 0 .. N/2)
         sum += hashtable[nthKey(n)];
     foreach_reverse(uint n; N/2 .. N)
         sum += hashtable[nthKey(n)];
     return sum;
}

pragma(inline, false)
uint hashBenchReuse(HashTable)(in uint N, in uint seed, ref 
HashTable hashtable)
{
     foreach (uint n; 0 .. N)
         hashtable[nthKey(n)] = n + seed;

     uint sum;
     foreach_reverse (uint n; 0 .. N/2)
         sum += hashtable[nthKey(n)];
     foreach_reverse(uint n; N/2 .. N)
         sum += hashtable[nthKey(n)];
     return sum;
}

enum benchmarkCode(string name, string signature = name) =
     `
         {
             sw.reset();
             result = 0;
             sw.start();
             foreach (_; 0 .. M)
             {
                 result += hashBench!(`~signature~`)(N, result);
             }
             sw.stop();
             string s = "`~name~`";
             printf("[checksum %d] %3d msecs %s\n",
                 result, sw.peek.total!"msecs", &s[0]);
         }
     `;

enum benchmarkCodeReuse(string name, string signature = name) =
     `
         {
             sw.reset();
             result = 0;
             sw.start();
             `~signature~` hashtable;
             foreach (_; 0 .. M)
             {
                 result += hashBenchReuse!(`~signature~`)(N, 
result, hashtable);
             }
             sw.stop();
             string s = "`~name~`";
             printf("(checksum %d) %3.2f msecs %s\n",
                 result, sw.peek.total!"usecs" / 1000.0, &s[0]);
         }
     `;

void main(string[] args)
{
     import std.datetime.stopwatch : AutoStart, StopWatch;
     import core.stdc.stdio : printf, puts;
     import std.experimental.allocator.gc_allocator : GCAllocator;
     import std.experimental.allocator.mallocator : Mallocator;

     alias BuiltinAA(K,V) = V[K];
     import containers.hashmap : EMSI_HashMap = HashMap;
     import memutils.hashmap : Memutils_HashMap = HashMap;
     import vibe.utils.hashmap : Vibe_HashMap = HashMap;
     import jive.map : Jive_Map = Map;
     //import stdx.collections.hashtable : Stdx_Hashtable = 
Hashtable;
     //import tanya.container.hashtable : Tanya_HashTable = 
HashTable;
     //import kontainer.orderedAssocArray.orderedAssocArray : 
Kontainer_OrderedAssocArray = OrderedAssocArray;

     immutable uint N = args.length < 2 ? 100 :
         () {
             import std.conv : to;
             auto result = to!uint(args[1]);
             return (result == 0 ? 100 : result);
         }();
     immutable M = N <= 500_000 ? (1000_000 / N) : 2;
     enum topLevelRepetitions = 3;

     printf("Hashtable benchmark N (size) = %d (repetitions) = 
%d\n", N, M);

     StopWatch sw = StopWatch(AutoStart.no);
     uint result;

     version(all)
     {
         puts("\n=Results (new hashtables)=");
         foreach (_repetition; 0 .. topLevelRepetitions)
         {
             printf("*Trial #%d*\n", _repetition+1);

             mixin(benchmarkCode!("built-in AA", "BuiltinAA!(int, 
int)"));
             mixin(benchmarkCode!("containers.hashmap 
w/Mallocator", "EMSI_HashMap!(int, int, Mallocator)"));
             mixin(benchmarkCode!("containers.hashmap 
w/GCAllocator", "EMSI_HashMap!(int, int, GCAllocator)"));
             mixin(benchmarkCode!("memutils.hashmap", 
"Memutils_HashMap!(int,int)"));
             mixin(benchmarkCode!("vibe.utils.hashmap", 
"Vibe_HashMap!(int,int)"));
             mixin(benchmarkCode!("jive.map", 
"Jive_Map!(int,int)"));
             //mixin(benchmarkCode!("stdx.collections.hashtable", 
"Stdx_Hashtable!(int,int)"));
             //mixin(benchmarkCode!("tanya.container.hashtable", 
"Tanya_HashTable!(int,int)"));
             
//mixin(benchmarkCode!("kontainer.orderedAssocArray.orderedAssocArray", "Kontainer_OrderedAssocArray!(int,int)"));
         }
     }

     version(all)
     {
         puts("\n=Results (reusing hashtables)=\n");
         foreach (_repetition; 0 .. topLevelRepetitions)
         {
             printf("*Trial #%d*\n", _repetition+1);

             mixin(benchmarkCodeReuse!("built-in AA", 
"BuiltinAA!(int, int)"));
             mixin(benchmarkCodeReuse!("containers.hashmap 
w/Mallocator", "EMSI_HashMap!(int, int, Mallocator)"));
             mixin(benchmarkCodeReuse!("containers.hashmap 
w/GCAllocator", "EMSI_HashMap!(int, int, GCAllocator)"));
             mixin(benchmarkCodeReuse!("memutils.hashmap", 
"Memutils_HashMap!(int,int)"));
             mixin(benchmarkCodeReuse!("vibe.utils.hashmap", 
"Vibe_HashMap!(int,int)"));
             mixin(benchmarkCodeReuse!("jive.map", 
"Jive_Map!(int,int)"));
             
//mixin(benchmarkCodeReuse!("stdx.collections.hashtable", 
"Stdx_Hashtable!(int,int)"));
             
//mixin(benchmarkCodeReuse!("tanya.container.hashtable", 
"Tanya_HashTable!(int,int)"));
             
//mixin(benchmarkCodeReuse!("kontainer.orderedAssocArray.orderedAssocArray", "Kontainer_OrderedAssocArray!(int,int)"));
         }
     }
}
```