About built-in AAs

Steven Schveighoffer schveiguy at yahoo.com
Wed Aug 17 20:25:50 PDT 2011


On Wed, 17 Aug 2011 21:07:29 -0400, Jesse Phillips
<jessekphillips+d at gmail.com> wrote:

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

So actually, it's technically a joint effort of the compiler and druntime.

The compiler doesn't *reject* creating AA's using keys that don't define  
opCmp.  It doesn't actually generate a function.  But druntime *does* do a  
"default" opCmp if no opCmp is defined.  See here:

https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L955

In essence, this "bug" is fixed by one of two things:

1. Using a fully templated AA implementation instead of a RTTI-based one  
(which avoids using the TypeInfo.compare function).
2. Not using opCmp anymore.

Since 2 is already happening, I think we are good.

I don't know how we should "fix" the TypeInfo_Struct function.  Should it  
just throw an exception if xOpCmp isn't set?

-Steve


More information about the Digitalmars-d mailing list