Re: 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