Fun project - faster associative array algorithm

[Steven Schveighoffer via Digitalmars-d]

On 4/8/15 5:11 AM, Martin Nowak wrote:
> On Tuesday, 7 April 2015 at 22:33:52 UTC, Steven Schveighoffer wrote:
>> Until that point, all these discussions on AA updates are useless.

>
> I really don't that all or nothing attitude, it condemns an important
> step, just because something better might be possible. It's also very
> comfortable, because this way nobody will ever have to do anything.

I'm not suggesting nobody ever do anything out of comfort. What I'm 
suggesting is that it's not worth improving something that will be 
discarded anyway. Let's fix the problem hampering people from 
understanding how the AA works so they can work on improving the AA. 
Namely, the discarding of all compile-time info during implementation.

> Improving the AA implementation has a big immediate effect, and will
> also help anyone writing a library implementation, because any candidate
> up to this date was still based on that crappy bucket list implementation.

The "crappy bucket list" implementation is also the simplest. When the 
focus should be on fixing the AA interface with the compiler and 
library, I think having a simple understandable implementation is fine.

Let me remind you of your attitude when I brought up the fact that AA's 
load factor was 4 (just fixing this one number could improve 
performance, even for the bucket list implementation):

 > We'll throw the current implementation away and implement an open 
addressing AA once we get to it. So don't worry about the load factor 
right now.

In other words, don't bother fixing the constant "4" in the code, it's 
going to be thrown away anyways.

> The biggest problems in writing an AA library implementation sorted by
> difficulty are:
> - deprecation of all magic AA behaviors (attributes, as[i][j]++)
> - get the lowering right

I really am surprised that these would be difficult at all. The lowering 
is pretty easy:
a) T[U] => AssociativeArray!(U,T)
b) [a:b, c:d] => AssociativeArray!(typeof(true ? a : c), typeof(true ? b 
: d)).literal(a, b, c, d);

Basically, bikeshed the name "literal" is the difficult part.

And deprecating the magic AA behaviors, isn't this just removing a whole 
lot of code from the compiler? Once the lowering is working, I don't see 
how removing special cases would be difficult. The part where we may 
have issues I see is CTFE support. But I would defer to those who have 
already tried this exercise, perhaps they can share what broke their 
solutions.

-Steve