About built-in AAs

[Andrei Alexandrescu]

On 8/17/11 12:43 AM, Walter Bright wrote:
> On 8/16/2011 9:15 PM, Andrei Alexandrescu wrote:
>> Let's please stop this. Many of us, including yourself, noticed the
>> relatively
>> poor performance of D's previous hashtables compared to other languages.
>> Switching to singly-list collision handling marked an improvement. Now
>> a lot of
>> data structure designs have a worst-case that makes them perform worse
>> than
>> others. If you worry about attacks, please implement your own
>> hashtable. If we
>> switch back to the old implementation, you'll complain again about D's
>> hashtables being slower than Python's, thus closing a years-long cycle.
>
> Also, I should point out that the switch from binary trees to linear
> lists involved zero change in user code - not even a recompile.
>
> Hence, any person who is worried about Bearophile's scenario, or that
> believe they can come up with a faster hash, can swap it with their own
> and prove it.
>
> The hash implementation was made to be opaque to the user, and
> pluggable, and this proved it.

Though that's a good point, people would usually recompile projects if 
they want to relink so the point is not as strong a point as it might 
have been.

I still very strongly believe we need to continue aggressively migrating 
built-in hashtables from pluggable to templated. Pluggable hashtables 
incur indirect calls in core functions - the bane of all speed 
optimizers. We can't afford that cost for such a useful data structure.


Andrei