A hash table implementation benchmark

[bearophile via Digitalmars-d-learn]

Ali Çehreli:

> Found on Reddit:

Where's the Reddit thread?


> Are you motivated enough to compare D's associative arrays with 
> those results? :)

D associative arrays are often even slower than CPython ones, so 
I don't expect D to shine in this comparison.

This is a D port of the Java code, but before using it I suggest 
you to review it well line by line against the other 
implementations, because I have not tested it.


import std.stdio, std.conv, std.random, std.datetime;

ulong lookup(in uint[uint] m, in uint[] b) @safe {
     ulong tot = 0;

     StopWatch sw;
     sw.start;
     foreach (immutable bi; b) {
         const ptr = bi in m;
         if (ptr != null)
             tot += *ptr;
     }
     sw.stop;

     return sw.peek.msecs;
}

void randomizeInput(uint[] a, uint[] b, in double p, ref Xorshift 
rng) @safe {
     foreach (ref ai; a)
         ai = uniform!"[]"(0, uint.max, rng);

     foreach (ref bi; b)
         bi = (uniform01(rng) <= p) ?
              a[uniform(0, $, rng)] :
              uniform!"[]"(0, uint.max, rng);
}

int main(in string[] args) {
     if (args.length != 4) {
         writeln("Usage: benchmark <size> <requests> 
<measurements> <hit probability>");
         return 1;
     }

     immutable n = args[1].to!uint;
     immutable r = args[2].to!uint;
     immutable k = args[3].to!uint;
     immutable p = args[4].to!double;

     auto rng = Xorshift(0);
     auto a = new uint[n];
     auto b = new uint[r];
     ulong t = 0;

     foreach (immutable _; 0 .. k) {
         uint[uint] m;
         randomizeInput(a, b, p, rng);
         foreach (immutable i, immutable ai; a)
             m[ai] = i;

         t += lookup(m, b);
         m.clear; // Deprecated?
     }

     writefln("%.2f MOPS\n", double(r) * k / t);
     return 0;
}


Bye,
bearophile