About built-in AAs

[Steven Schveighoffer]

On Wed, 17 Aug 2011 00:15:38 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> 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.

Yes, but let's not forget the one valid request out of all of this -- if  
trees are no longer being used, opEquals should be used insted of opCmp.   
This allows more possible key types (which don't define an ordering). I  
think this would be a simple druntime change.

-Steve