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