Cost of assoc array?

[Chris via Digitalmars-d-learn]

On Wednesday, 14 May 2014 at 13:44:40 UTC, John Colvin wrote:
>
> Yes, they are much faster. Normal array indexing is equivalent 
> to *(myArray.ptr + index) plus an optional bounds check, 
> whereas associative array indexing is a much, much larger job.
>
> Why were you using associative arrays in the first place? 
> Unless your keys are somehow sparse* or of a non-integer type 
> there isn't any reason to.

It is very old code (dmd 2.052 times). When I set out to write 
it, I was a) new to the language and b) I could not yet tell 
whether or not I would need it (I think it also had to do with 
the way D was back then, but I don't remember my exact 
reasoning). It has always been in the back of my mind to change 
it into a normal array. It's basically a code corpse.


> * How I see that constraint in that context:
>
> (maxKey - minKey) / nElements > 1 + epsilon
> where epsilon is the maximum proportional wasted space you 
> could afford in a normal array (emptyElements / usedElements). 
> Bear in mind the memory overhead of associative arrays is 
> itself non-zero.
>
> Also, while normal arrays tend to be more cache friendly than 
> associative arrays, this isn't true for very sparse arrays.