Builtin array and AA efficiency questions

[H. S. Teoh via Digitalmars-d-learn]

On Thu, Oct 15, 2015 at 09:00:36PM +0000, Random D user via Digitalmars-d-learn wrote:
> Thanks for thorough answer.
> 
> On Thursday, 15 October 2015 at 18:46:22 UTC, H. S. Teoh wrote:
[...]
> >The only thing I can think of is to implement this manually, e.g., by
> >wrapping your AA in a type that keeps a size_t "generation counter",
> >where if any value in the AA is found to belong to a generation
> >that's already past, it pretends that the value doesn't exist yet.
> >Something like this:
> 
> Right. Like a handle system or AA of ValueHandles in this case. But
> I'll probably just hack up some custom map and reuse it's mem.
> Although, I'm mostly doing this for perf (realloc) and not mem size,
> so it might be too much effort if D AA is highly optimized.

Haha, the current AA implementation is far from being highly optimized.
There has been a slow trickle of gradual improvements over the years,
but if you want maximum performance, you're probably better off writing
a specialized hash map that fits your exact use case better. Or use a
different container that's more cache-friendly. (Hashes exhibit poor
locality, because they basically ensure random memory access patterns,
so your hardware prefetcher's predictions are out the window and it's
almost a guaranteed RAM roundtrip per hash lookup.)


T

-- 
If I were two-faced, would I be wearing this one? -- Abraham Lincoln