Golfing with Dict
Code golf is usually all about the briefness of the code. This code golf will be a bit different: it will be about code size, speed and efficiency.
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++ Class | Purpose | API |
---|---|---|
element |
The dictionary item. Contains a value of any type. For example: an integer, a double, some text, or another dictionary. | Setting values, reading the value, resetting the element, comparing elements, etc. |
name |
A label-like type used to access elements in the dictionary. | Constructing new names, comparing names. |
dict |
The dictionary, indexed by name, holding elements. | Construction, copying, merging, adding, removing and accessing its elements, over its elements. |
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?