AA Performance in Benchmarks

[Chris via Digitalmars-d]

On Friday, 24 April 2015 at 09:18:48 UTC, Chris wrote:
> On Thursday, 23 April 2015 at 14:40:58 UTC, Shammah Chancellor 
> wrote:
>> So, I was tooling around with one of the benchmarks I saw 
>> listed on twitter:
>>
>> https://github.com/kostya/benchmarks/tree/master/brainfuck
>>
>> This D benchmark spends most of it's time on AA lookups.   
>> Discussions about the implementation aside, I am curious as to 
>> why the D AA is so slow even after calling AA.rehash.
>>
>> I took a look at the Nim tables implementation, and it looks 
>> that they use power-of-two vectors and use the property of 
>> primitive roots modulo n to get the next value in the case of 
>> a collision:
>>
>> ```
>> proc nextTry(h, maxHash: THash): THash {.inline.} =
>>  result = ((5 * h) + 1) and maxHash
>> ```
>>
>> So, my questions:
>>
>> 1) What are the general purpose performance implications of 
>> something like this?
>> 2) I saw a thread awhile ago where someone had posted an 
>> updated implementation of the AA with benchmarks and showed 
>> that it was substantially faster in all cases.  I can't find 
>> the thread again -- what happened with this work?
>>
>> -Shammah
>
> Interesting. I noticed while doing some benchmarking that 
> looking up data that is stored in an AA is slower than 
> generating the data on the fly. I was really surprised.

AA lookup is (more often than not) slightly slower than (or at 
least as fast as) generating the data on demand:

import std.datetime : benchmark, Duration;
import std.string : format;
import std.conv : to;
import std.stdio : writeln;

enum {
   string[string] words = [
     "Data1":"Blah",
     "Data2":"Blub",
   ],
   string[] letters = ["B", "l", "a", "h"]
}

void main() {
   words.rehash();
   auto result = benchmark!(lookup, make)(100_000);
   writeln(to!Duration(result[0]));
   writeln(to!Duration(result[1]));
}

string lookup() {
   auto blah = words["Data1"];
   return blah;
}

string make() {
   string res;
   foreach (c; letters)
     res ~= c;
   return res;
}

dmd v2.067.0 -release -O -boundscheck=off -inline