About built-in AAs

[Jesse Phillips]

On Wed, 17 Aug 2011 10:46:00 -0500, Andrei Alexandrescu wrote:

> 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

Added, do we also want to add don't have compiler generate opCmp 
automatically?

http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel