Golfing with Dict

The question we will explore is: How fast can a dictionary access get?

Yes, it’s a bit weird as code golf goes, but bear with me, we’ll get to the green with this one. Maybe not in the usual manner... but we’ll get there, together, as a team! Just kidding, no teamwork required. I’ll do all the swinging and trudging, and you can just follow along in the cart.

All the code we will discuss is available on GitHub.

(Note that there are multiple branches: “master” for the starting point and “fast-dict” for the final result.)

The Rules

As you’ll see, by the end of this, the rules of golfing will be bent, and we’ll make some up along the way. And I’ll be setting down ground rules, for example what the dictionary must basically look like and the functionality it must provide.

First, I’ll provide a high-level description of the functionality, then a short C++ declaration of what the interface will look like. For a full view of the C++ API, refer to the “master” branch on GitHub. Now, on to the description!

High-level Description

C++ Code

In this article, I will only give the shortest of descriptions; the full code can be found on GitHub. Since the main thing that interests us is the dictionary access, that’s all I’ll show right now:

   // Element retrieval.
   element & operator [](const name &);
   const element & operator [](const name &) const;

Very simple, very standard. The look-up function receives a name and returns an element. To help understand what names are, let’s see how they are created:

   // You need to derive from name to create a concrete name.
   // All instances of a given concrete name are equal.
   struct name
   {
      // Invalid-name, default constructor.
      name() : _name(nullptr) {}

   protected:
      // The text passed for the name by its sub-classes must be static
      // so that each address is unique.
      name(strptr n) : _name(n) {}
   };

While name has a public default constructor, its other constructor is protected. Why is that? You will see the underlying reason later on… Does that mean that all instances have to come from sub-classes? Yes! Every name will be an instance of a sub-class of name! But which sub-class? Gee... all of them, of course!

In fact, if you look in the GitHub repo, you will see that I provide a handy voc.h header. This header declares… a vocabulary of names. As was hinted in the name class declaration, to each name its sub-class… to each sub-class its name! The file goes a bit like this:

   namespace voc
   {
      #define MAKE_NAME(n) struct n ## _n : dak::name { n ## _n() : name(L ## #n) {} };

      MAKE_NAME(apple);
      MAKE_NAME(person);
      // etc…

      const apple_n apple;
      const person_n person;
   }

The element class itself is a simple class that can hold a value of any common type. There is nothing special about it. Now would be a good time to think of just how fast you could make such a dictionary interface. You can look at the “master” branch on GitHub as a starting point. Will it be N log N? N?, log N? Constant time? Faster? Wait, faster than constant time? What does that even mean?

The Bends

Now that we’ve set down the ground rules, it’s time to bend them to our advantage. Of course, like any self-respecting cheat, we carefully thought out the rules to give the (club)house an edge.

For example, there is a good reason why the name class is designed the way it is. You see, having different types for different names means that we can subvert the C++ type system to our advantage. More specifically, we can subvert the function overloading mechanism!

Remember the element access functions? What would happen if they were overloaded like this:

   // Element retrieval.
   element & operator [](const name &);
   const element & operator [](const name &) const;

   // Overload!!!
   inline element& operator [](const voc::rock_n&)
   inline const element& operator [](const voc::rock_n&) const

It means we can return the element without having to look it up! Shameless cheating! But how can the element be found if the voc::rock is accessed through the version taking a simple name and not a voc::rock? How can the dict elements be iterated over during normal iteration? Easy! We create proxy elements in the normal dictionary map, each proxy defers all its behavior to the direct-access copy. Basically, we add a few functions to the element class to record if it is a proxy. We also add a function to the dict class to record each proxy element and the direct-access element it refers to.

   struct dict
   {
   protected:
      std::map _elements;

      // Sub-classes call this during construction
      // to add the permanent proxy elements.
      void add_permanent_proxy(const name& n, element &);
   };

   struct element
   {
      bool is_proxy() const;
      bool is_permanent() const;
   };

The result is that we can access the elements of our choice at compile-time! You simply sub-class the dict class and add the proxy elements that will be accessible under the names of your choice. The resulting class acts just like a dict and can be used everywhere a dict can be used, but if you know the true type of the dict and the true name you want to access, you get compile-time access thanks to function inlining and overloading.

The Twist

We in the madness business are not satisfied with such fairway-variety trickery. This subversion doesn’t go far enough. We want more speed! We do have compile-time access to our element, but what we want is compile-time access to the value contained in the element. Is that even possible? Why, yes, it is!

The sleight-of-hand we will be using is sub-classing the element class where the value resides. If we know in advance the type of value we want to keep under a name, we can force it to always have that type known at compiling time. Knowing the type of value we want to keep under a specific name is not unusual, it’s even typical! That’s how we design types, schema and databases, after all.

So here is a typical example of such sub-classing. (See the “fast-dict” branch on GitHub for all the variation provided.)

   struct eint64 : element
   {
      operator int64&() { return _i; }
      // etc...
   };

As we can see, it can inline the access to the true value contained in the element. Now our dict sub-class can return such an eint64 in its overloaded element-access function, and offer full compile-time access to the direct value, like this:

      inline eint64& operator [](const voc::rock_n&) { return _rock; }
      inline const eint64& operator [](const voc::rock_n&) const { return _rock; }

To support the element sub-classes, an additional function is added to element to let it know that the value type is now fixed:

      bool is_fixed() const { return _fixed == fixedtype::fixed; }

The Proof

Not content with merely claiming that it is compile-time accessible, I prove that it is! Then I double down by comparing it to pure structure access. That’s right! While the dictionary sub-class with its overloaded functions can be used just like a normal dict, and all its elements, including the permanent, proxied-typed ones can be found by normal look-up or by iteration, it is just as fast as a raw struct! See for yourself:

   struct rock_struct
   {
      int64 rock = 42;
   };

In the “fast-dict” branch are unit-tests, including two dummy ones that were used solely to compare the code generation of the sub-dict and the structure. I captured the disassembly of both for your viewing pleasure: as advertised, each is just as fast as the other!

        d1.rock = rand();
call        qword ptr [rand]  
movsxd      rcx,eax  
mov         qword ptr [rsp+38h],rcx  
       use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

       std::wcout << d1.rock;
mov         rbx,qword ptr [d1]  
mov         rcx,qword ptr [std::wcout]  
mov         rdx,rbx  
call        qword ptr [operator<<]  

       d1.rock += rand();
call        qword ptr [rand]  
movsxd      rcx,eax  
add         rbx,rcx  
       use_rock(d1);
lea         rcx,[d1]  
mov         qword ptr [d1],rbx  
call        dak::use_rock

       std::wcout << d1.rock;
mov         rdx,qword ptr [d1]  
mov         rcx,qword ptr [std::wcout]  
call        qword ptr [operator<<]  

       use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

        d1[voc::rock] = rand();
call        qword ptr [rand]  
movsxd      rcx,eax  
mov         qword ptr [rsp+38h],rcx  
        use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

        std::wcout << d1[voc::rock];
lea         rdx,[rsp+38h]  
mov         rcx,qword ptr [std::wcout]  
call        dak::operator<<

        d1[voc::rock] += rand();
call        qword ptr [rand]  
add         eax,dword ptr [rsp+38h]  
movsxd      rcx,eax  
mov         qword ptr [rsp+38h],rcx  
        use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

        std::wcout << d1[voc::rock];
lea         rdx,[rsp+38h]  
mov         rcx,qword ptr [std::wcout]  
call        dak::operator<<

        use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

Conclusion

We looked down the fairway, setting our sights on the dictionary access and trying to see how low par for the course could go. And lo and behold!, how low we went!

But I feel you are tense, confused and cross..

This is a parody of design, an abomination! Deriving from a dict class? Would you derive from a std::vector, a std::map, a std::pair? What kind of respectable golfer would ever do that? And I’d agree! (Wait, what? Who said that?) No, no, no, no, I would really agree! I would, I would, I would, except…

… you see, everything in life is a question of perspective. Of how we perceive the world. And in the case of programming, perception is all about naming. Naming types, naming functions, naming variables. What’s in a name? Names shape our vision of the world, and on this much smaller scale, of our designs. So… what if I told you dict is not the real name of the class? What would happen if we renamed it … object?

Ah, the final key! Yes, now it makes sense to derive from object. Now it makes sense to add fixed permanent elements to an object to hold values of fixed type! It’s no longer even a surprising design. It’s basically how a language like Python works under the hood. In Python, every object of every class is really just a dictionary of values indexed by name. It’s just that now you can do it directly in C++.

It’s also very useful. You no longer need to write and rewrite boiler-plate code for every struct and class. You can have a single implementation for all types for things like serialization, undo/redo, data lookup, hooking-up to UI elements, and many other activities I’m sure you can think up. You write it once for the dict object class. Every sub-class inherits the implementation of object and all data is always accessible via simple iteration over elements or name lookup.

Ain’t that something? So, did we birdie this one or not?