AA Implementation Issues

From D Wiki
Jump to: navigation, search

Introduction

This article follows a private e-mail discussion with H. S. Teoh about his new AA (associative array) implementation. He was kind enough to give me permission to share this discussion with the rest of you.

Kudos, H.S. Teoh

Issues & Comments on re-implementation attempt

Basically, I reused the same AA algorithms as the current implementation in druntime's aaA.d; I didn't introduce any clever new algorithms. The main purpose was to move the code out of aaA.d into object_.d (or maybe a separate file that is publically imported by aaA.d). The reason for this is:

  • Currently, the stuff in aaA.d is opaque, meaning that the connections between user code and the AA code is magically inserted by the compiler (in some cases), so aaA.d does not have direct access to the user types in the AA. For example, if you declare "double[float] aa", the aaA.d code only gets the information about 'float' (via a TypeInfo reference), but no information about 'double' (the value type) except the size. As a result, we have bugs about AA values not being initialized to double.init, but just binary-zeroed, which is unexpected, because in D, we expect double.init == double.nan, not 0.0. Also, because aaA.d doesn't know about the value type, it doesn't call postblit ctors, etc., causing more bugs along those lines.
  • Worst of all, the data structure internally used by aaA.d is actually copy-n-pasted into object_.d in order to support the range interfaces byKey and byValue. The main issue here is that aaA.d does not expose a range interface, and any range API requires access to internal AA structures, which is impractical when aaA.d is supposed to be opaque to user code.
  • All of these factors made me decide that I will not spend any time on the AA algorithm itself (there are some enhancement requests related to it), but just focus on decoupling AA's from aaA.d and from internal compiler support (more on this later).

So the core of my current AA implementation is really just a rewriting of aaA.d using the same algorithms, but in user code instead of in an opaque module. This way, there is no unnecessary duplication between aaA.d and object_.d, and the AA implementation has full access to key and value types, so ctors, postblits, dtors, .init, etc., can all be supported correctly.

On top of this core, there have been some enhancement requests. The most notable one is from Andrei Alexandrescu, who wanted implicit type conversions to work nicely. For example, the following should work: 

    alias constCharStr = const(char)[];
    double[constCharStr] aa;
    aa["abc"] = 1.0;        // implicit conversion const(char)[] -> string
    int x = 123;
    aa["def"] = x;          // implicit promotion int -> double

    constCharStr[double] aa2;
    auto ptr = 123 in aa2;  // promote 123 to double and lookup 123.0 in AA

    string[int[]] intAA;
    ubyte[] key = [1,2,3];
    intAA[key] = "abc";     // implicit convert ubyte[] -> int[] via .idup
    auto ptr2 = key in intAA; // no .idup, but compatible comparison of ubyte[] with int[]

    int[string] aa3;
    wstring wkey = "asdf"w;
    auto ptr3 = wkey in aa3; // compatible comparison of wstring with string

The current code supports this partially (there are some missing cases), but it comes at the cost of template bloat. So my last effort on this front was to try to reduce template bloat for these cases, but I didn't finish this task.

There are also a number of AA bugs related to static array keys, which have mostly been fixed in my current AA code (look at the unittests at the end of the file to see which bugs are fixed).

Another unfinished effort was to make a consistent use of toHash to get the hash value of the key. The old AA code had some bugs on this front (for some key types, toHash was not called consistently, so some AA's were broken, you can never find the keys you're looking for because they were inserted with one hash function but looked up with a different hash function). I did make some fixes, but I think there are still cases that are not working.

My attempt to solve this problem was to use UFCS to define different hash functions for various types (because there are different hash functions in druntime currently, I think some are to optimize X[string] because those are the most common usages of AA's; the default toHash may have been too inefficient).

But this interacts badly with Andrei's enhancement request: if string.toHash uses one hash function and wstring.toHash is a different function, then you will never find the correct slot in the AA.

I had some ideas for supporting compile-time AA literals, but due to DMD bugs I never got any code working. Basically, the idea is to do the hash computation of each key in the AA literal using CTFE, and based on that, compute where in the hashtable the slot will fall. Then, again using CTFE + string mixins, declare static global instances of each AA with a consistent naming scheme, then make a compile-time linked-list of the Slots in each hashtable entry by using &slotVarName to refer to the slots. Finally, the main hashtable is declared in the same way, using mixins that reference &slotVarName's to get compile-time references to the right slots. The result will be that the AA is pre-constructed in the object file, so there is no runtime initialization needed, you can just use standard AA functions to do lookups, etc.. (Of course, the resulting AA will be static immutable, because the slots will be static globals and can't be deallocated at runtime.)

The show-stopping issue, though, was how to handle constness correctly. Basically, any AA method that can be const, pure, nothrow, @safe, etc., should be. In theory, this should be simple, but in practice, there are some complications:

  • For read-only methods, we want to share the same code for both const(V[K]) and V[K] in order to reduce template bloat. So we have to use inout for most read-only methods. But inside an inout method, the AA is const, which means the pointers to slots will be const(Slot*), but that means we cannot iterate these pointers because you cannot assign to const(Slot*)! So we have to declare the pointers as inout(Slot)* instead. This issue is relatively easy to resolve, but requires some care if you're modifying the code.
  • The most tricky part is how to deal with V[const(K)] and V[immutable(K)].
  • Then there's the issue of whether AA's should force all key types to be immutable. Here's the reason:
    int[int[]] aa;
    int[] mykey = [1,2,3];
    aa[mykey] = 123;        // the AA stores a *reference* to mykey
    mykey[0] = 2;           // but mykey is mutable! Now the hash value of aa[mykey] is invalid
    assert([1,2,3] in aa);  // so this will fail, the Slot will never be found

However, if we force all keys to be immutable, we run into another problem: 

    struct KeyType {
        int value;
        int* cachedValue;

        // Note: toHash value only depends on this.value, not
        // this.cachedValue.
        hash_t toHash() { return value.toHash(); }

        void updateCache() {
            *cachedValue = &value;
        }
    }

    int[KeyType] aa;
    KeyType key;
    aa[key] = 123;

    // If we implicitly force KeyType to be immutable, then the
    // following line is invalid, even though it is safe (doesn't
    // change the hash value of key):
    key.updateCache();
  • But currently, there's no way in the language to express "the key type can be mutable as long as its toHash value cannot change". So it looks like we *cannot* force AA keys to be immutable. Which means we cannot be fully free from the bugs of altering a key after inserting it into the AA, which causes the AA to malfunction.
  • Furthermore, how to deal with const and immutable value types is another question, because in some places in the AA code, you need to copy a value into the Slot. But if copying is not allowed due to const/immutable, it means some AA's will cause compile errors (the compiler may fail to instantiate, for example, AssociativeArray!(int,immutable(int[])).

Now after all of the above issues have been addressed, there is still the question of how to fix the compiler to use the new AA implementation.

Currently, the AA code is sprinkled in various places in object_.d, aaA.d, and different places in the compiler. You'll need to fix the compiler in all of these places before everything will work properly with the new AA code. Some places in the compiler rewrites V[K] into AssociativeArray!(V,K). But this is not done all in the same place, and in some cases it's not done at all. The new AA implementation is intended to replace the current AssociativeArray!(V,K) in object_.d. But for that to work, *all* AA-related code in the compiler must consistently use that.

So there's a lot of work to do on the compiler side before everything will work properly.

Retrieved from "https://wiki.dlang.org/?title=AA_Implementation_Issues&oldid=6631"