About built-in AAs

[Andrei Alexandrescu]

On 8/16/11 9:29 PM, bearophile wrote:
> Walter Bright:
>
>>> I think there are search trees like the Red-Black ones that guarantee a O(n ln n) worst case. I am wrong?
>>
>> Just feed it more data.
>
> If you feed it more data, even if all items pruce collision because they all hash to the same bucket, if you use Red-Black trees to handle the items in the same bucket you keep having a O(n ln n) behaviour, that's usually fast enough. With Python and the new D AAs you instead get a quadratic one. This quadratic behaviour gives troubles way before the physical RAM is exhausted.
>
> Bye,
> bearophile

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.

Thanks,

Andrei