On Wed, 17 Aug 2011 00:15:38 -0400, Andrei Alexandrescu
<[email protected]> 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.
