About built-in AAs

[Andrei Alexandrescu]

On 8/17/11 9:04 AM, Steven Schveighoffer wrote:
> 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

Yah, we should put that on the list of things to do on the Wiki. Wait, 
where the heck is that? :o)

Andrei