Golfing with Dict

<div><p>The question we will explore is: <i><b>How fast can a dictionary access get?</b></i></p><p>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.</p><p>All the code we will discuss is <a href="https://github.com/pierrebai/FastDict">available on GitHub</a>.</p><p>(Note that there are multiple branches: “master” for the starting point and “fast-dict” for the final result.)</p><h2>The Rules</h2><p>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.</p><p>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!</p><h3>High-level Description</h3><table style="width:100%"> <tbody> <tr> <th>C++ Class</th> <th>Purpose</th> <th>API</th> </tr> <tr> <td style="vertical-align: top;"><code>element</code></td> <td style="vertical-align: top;">The dictionary item. Contains a value of any type. For example: an integer, a double, some text, or another dictionary.</td> <td style="vertical-align: top;">Setting values, reading the value, resetting the element, comparing elements, etc.</td> </tr> <tr> <td style="vertical-align: top;"><code>name</code></td> <td style="vertical-align: top;">A label-like type used to access elements in the dictionary.</td> <td style="vertical-align: top;">Constructing new names, comparing names.</td> </tr> <tr> <td style="vertical-align: top;"><code>dict</code></td> <td style="vertical-align: top;">The dictionary, indexed by name, holding elements.</td> <td style="vertical-align: top;">Construction, copying, merging, adding, removing and accessing its elements, over its elements.</td> </tr> </tbody></table><h3>C++ Code</h3><p>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:</p><pre><code> // Element retrieval. element &amp; operator [](const name &amp;); const element &amp; operator [](const name &amp;) const;</code></pre><p>Very simple, very standard. The look-up function receives a <code>name</code> and returns an <code>element</code>. To help understand what <code>names</code> are, let’s see how they are created:</p><pre><code> // 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) {} };</code></pre><p>While <code>name</code> 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 <code>name</code> will be an instance of a sub-class of <code>name</code>! But which sub-class? Gee... <b>all of them</b>, of course!</p><p>In fact, if you look in the GitHub repo, you will see that I provide a handy <code>voc.h</code> header. This header declares… a vocabulary of names. As was hinted in the <code>name</code> class declaration, to each <code>name</code> its sub-class… to each sub-class its <code>name</code>! The file goes a bit like this:</p><pre><code> 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; }</code></pre><p>The <code>element</code> 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?</p><h2>The Bends</h2><p>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.</p><p>For example, there is a good reason why the <code>name</code> 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!</p><p>Remember the <code>element</code> access functions? What would happen if they were overloaded like this:</p><pre><code> // Element retrieval. element &amp; operator [](const name &amp;); const element &amp; operator [](const name &amp;) const; // Overload!!! inline element&amp; operator [](const voc::rock_n&amp;) inline const element&amp; operator [](const voc::rock_n&amp;) const</code></pre><p>It means we can return the <code>element</code> without having to look it up! Shameless cheating! But how can the <code>element</code> be found if the <code>voc::rock</code> is accessed through the version taking a simple <code>name</code> and not a <code>voc::rock</code>? How can the <code>dict</code> 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 <code>element</code> class to record if it is a proxy. We also add a function to the <code>dict</code> class to record each proxy <code>element</code> and the direct-access <code>element</code> it refers to.</p><pre><code> struct dict { protected: std::map<name element=""> _elements; // Sub-classes call this during construction // to add the permanent proxy elements. void add_permanent_proxy(const name&amp; n, element &amp;); }; struct element { bool is_proxy() const; bool is_permanent() const; };</name></code></pre><p>The result is that we can access the elements of our choice at compile-time! You simply sub-class the <code>dict</code> 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 <code>dict</code> can be used, but if you know the true type of the <code>dict</code> and the true name you want to access, you get compile-time access thanks to function inlining and overloading.</p><h2>The Twist</h2><p>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 <b>value</b> contained in the element. Is that even possible? Why, yes, it is!</p><p>The sleight-of-hand we will be using is sub-classing the <code>element</code> class where the value resides. If we know in advance the type of value we want to keep under a <code>name</code>, 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 <code>name</code> is not unusual, it’s even typical! That’s how we design types, schema and databases, after all.</p><p>So here is a typical example of such sub-classing. (See the “fast-dict” branch on GitHub for all the variation provided.)</p><pre><code> struct eint64 : element { operator int64&amp;() { return _i; } // etc... };</code></pre><p>As we can see, it can inline the access to the true value contained in the <code>element</code>. Now our <code>dict</code> sub-class can return such an <code>eint64</code> in its overloaded <code>element</code>-access function, and offer full compile-time access to the direct value, like this:</p><pre><code> inline eint64&amp; operator [](const voc::rock_n&amp;) { return _rock; } inline const eint64&amp; operator [](const voc::rock_n&amp;) const { return _rock; }</code></pre><p>To support the <code>element</code> sub-classes, an additional function is added to <code>element</code> to let it know that the <code>value</code> type is now fixed:</p><pre><code> bool is_fixed() const { return _fixed == fixedtype::fixed; }</code></pre><h2>The Proof</h2><p>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 <code>dict</code>, 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 <b>raw struct</b>! See for yourself:</p><pre><code> struct rock_struct { int64 rock = 42; };</code></pre><p>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!</p><pre><code> 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 &lt;&lt; d1.rock;mov rbx,qword ptr [d1] mov rcx,qword ptr [std::wcout] mov rdx,rbx call qword ptr [operator&lt;&lt;] 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 &lt;&lt; d1.rock;mov rdx,qword ptr [d1] mov rcx,qword ptr [std::wcout] call qword ptr [operator&lt;&lt;] use_rock(d1);lea rcx,[d1] call dak::use_rock</code></pre><pre><code> 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 &lt;&lt; d1[voc::rock];lea rdx,[rsp+38h] mov rcx,qword ptr [std::wcout] call dak::operator&lt;&lt; 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 &lt;&lt; d1[voc::rock];lea rdx,[rsp+38h] mov rcx,qword ptr [std::wcout] call dak::operator&lt;&lt; use_rock(d1);lea rcx,[d1] call dak::use_rock</code></pre><h2>Conclusion</h2><p>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!</p><p>But I feel you are tense, confused and cross..</p><p>This is a parody of design, an abomination! Deriving from a <code>dict</code> class? Would you derive from a <code>std::vector</code>, a <code>std::map</code>, a <code>std::pair</code>? 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…</p><p>… 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 <code>dict</code> is not the real name of the class? What would happen if we renamed it … <code>object</code>?</p><p>Ah, the final key! Yes, now it makes sense to derive from <code>object</code>. Now it makes sense to add fixed permanent elements to an <code>object</code> 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++.</p><p>It’s also very useful. You no longer need to write and rewrite boiler-plate code for every <code>struct</code> and <code>class</code>. 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 <del><code>dict</code></del> <code>object</code> class. Every sub-class inherits the implementation of <code>object</code> and all data is always accessible via simple iteration over elements or name lookup.</p><p>Ain’t that something? So, did we birdie this one or not?</p></div>