Re: A hash table implementation benchmark

[Ali Çehreli via Digitalmars-d-learn]

On 10/01/2014 10:00 PM, thedeemon wrote:

 Here's another benchmark:
 D AAs vs. Vibe.d's open addressing hashes vs. Robin Hood hashing:
 http://www.infognition.com/blog/2014/on_robin_hood_hashing.html

What a coincidence. :) Your blog article was written just two weeks ago.

Ali

A hash table implementation benchmark

[Ali Çehreli via Digitalmars-d-learn]

Found on Reddit:


http://lonewolfer.wordpress.com/2014/03/13/benchmarking-hash-table-implementations-in-different-languages/

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


Ali

Re: A hash table implementation benchmark

[Marco Leise via Digitalmars-d-learn]

Am Wed, 01 Oct 2014 14:40:01 -0700
schrieb Ali Çehreli acehr...@yahoo.com:

 Found on Reddit:
 
  
 http://lonewolfer.wordpress.com/2014/03/13/benchmarking-hash-table-implementations-in-different-languages/
 
 Are you motivated enough to compare D's associative arrays with those 
 results? :)
 
 Ali

The question is ... do you dare with the current state of the
GC :D

-- 
Marco

Re: A hash table implementation benchmark

[Marco Leise via Digitalmars-d-learn]

Oh wit! It is a read-only benchmark.

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

Re: A hash table implementation benchmark

[Ali Çehreli via Digitalmars-d-learn]

On 10/01/2014 03:32 PM, bearophile wrote:

 Ali Çehreli:

 Found on Reddit:

 Where's the Reddit thread?

There was just a single comment on it so I didn't think it was important:


http://www.reddit.com/r/programming/comments/2hzur4/benchmarking_hash_table_implementations_in/

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

Never mind then. I remember posts by the user named 'spir' who used to 
be interested in hash table implementations. I recall that he was 
impressed by the speed of D's associative arrays. I may be wrong.


Ali

P.S. It is a pity that spir seems to have disappeared from online life. (?)

Re: A hash table implementation benchmark

[bearophile via Digitalmars-d-learn]

Ali Çehreli:


Never mind then.


Well, now the D code is present, so why don't you benchmark it 
(but I don't know how much correct it is)? :-)


Bye,
bearophile

Re: A hash table implementation benchmark

[thedeemon via Digitalmars-d-learn]

On Wednesday, 1 October 2014 at 21:40:01 UTC, Ali Çehreli wrote:


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




Here's another benchmark:
D AAs vs. Vibe.d's open addressing hashes vs. Robin Hood hashing:
http://www.infognition.com/blog/2014/on_robin_hood_hashing.html
There's a link to a table with timings, meaning of which 
described in the post.


Also compared a bit with C++'s CAtlMapint, int in MSVC 10 which 
I was told was pretty good. Generated 10 million random ints from 
range of 1 million, made a histogram and then read it. Exactly 
same data for both implementations (CAtlMap and Robin Hood in D). 
 With default settings CAtlMap makes histo in 2.19 sec, reads it 
in 1.19 sec. Robin Hood in D makes same histo in 1.27 sec, reads 
in 1.09 sec (and it's DMD 32-bit!).


After adding Rehash() between making and reading the histogram, 
CAtlMap makes histo in 2.37 sec, reads in 0.92.