Associative arrays in D and default comparators

[Sean Kelly]

Walter Bright wrote:
> 
> Although the current AA implementation only uses opCmp, having both 
> available means that an implementation could use both or either. 
> Sometimes opEquals can be computed a lot more efficiently than opCmp.
> The current implementation uses hashing with binary trees, but an 
> implementation isn't required to do it that way.

This is good to know.  I'd considered playing with the current 
implementation, but was concerned about altering spec-defined behavior.

> Hashing with binary trees has proven in practice to be very efficient. 
> It beats even C++ templated hash tables. I'm sure with some careful 
> coding one can create a faster one customized to a particular data type, 
> but the current general purpose one is pretty darned fast and compact. 
> It's the central algorithm in DMDScript, for example, and DMDScript 
> still beats the other javascript implementations around the block.

I agree that it's got fantastic performance--my concerns here are really 
more practical, as I have objects I want to use as keys that don't 
contain any data which could be used for sorting purposes.  But it 
sounds like there's enough wiggle room in the spec to find some 
reasonable middle ground.  Thanks!


Sean