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
