I have a mixed relationship with variant…<\/p>\n
I just wrote a parser for S-expressions (that will be the basis of ASTs and intermediate types in my planned “write-a-compiler” article series). The parser itself is easy, but as always, I spent more time on the underlying data structures. <\/p>\n
<\/p>\n
What are S-expressions? S-expressions, also called sexps, are recursive, list based, data structures. Being recursive, they can represent hierarchical information. S-expressions are parenthesized prefix expressions, known for their use in LISP (and its sibling Scheme). Here’s a simple sexp:<\/p>\n
\r\n(* 2 (+ 3 4))\r\n<\/pre>\nThe sexp above corresponds to this infix expression:<\/p>\n
\r\n(2 * (3 + 4))\r\n<\/pre>\nS-expressions are simple and infinitely powerful beasts as evident in applications that use LISP as their scripting language. They can represent code and data. Some people even use S-expressions as a suitable (and terser!) replacement for XML. The in-memory data structures are very easy to use, transform and manipulate, traverse and compile or accumulate results from.<\/p>\n
The plan is to use S-expressions as our AST representation and embed a minimal LISP\/Scheme interpreter IN<\/strong> the compiler. This implies that along the way, we’ll be building an S-expression parser and a LISP\/Scheme interpreter. How cool is that? … We’re talking about scripting the compiler with an interpreter! \ud83d\ude42<\/p>\n
I needed a dynamic data type that can represent the S-expressions. I called it utree, short for universal-tree. I want it to be as simple as it can be and fast and tight in memory footprint. Boost variant was simply out of the question (I used it in one early prototypes). For one, it failed a basic requirement (tight memory footprint). The padding and the way it aligns the “what-type” integer member is quite wasteful. It uses a conservative alignment using the worst alignment of the types in the union. Thus if you have a type in there that aligns to 8 bytes, variant requires another 8 bytes just for the type discriminator! Try it out:<\/p>\n
\r\nstruct x { void* a; void* b; void* c; };\r\n\/***\/\r\nstd::cout << sizeof(x) << std::endl;\r\nstd::cout << sizeof(boost::variant<x, int, double>) << std::endl;\r\n<\/pre>\nI get: 12 and 24 respectively (32 bit system).<\/p>\n
I ended up with 40 bytes in my initial prototype (using STL containers and variant) and later squeezed that to 24 (minimum). I did away with variant in my latest version and got 16 bytes. In this case, I “stole” unused padding bits from the data to store the discriminator. \u00a0\u00a0With this 16 bytes, I have nil, bool, int, double, string and (double linked) list. The string itself steals memory when it can (i.e. it stores the string in the union when it can and only uses the heap when needed). The string steals as much as it can. So, on 32 bit systems, it can store in-situ as much as 14 bytes. That’s a lot for storing simple strings like symbols and identifiers. On 64 bit systems, you can store a lot more in-situ and minimize heap usage more.<\/p>\n
At this point, I feel like writing my own variant type that can do such things (intrusive variant?). Barring the use of Boost.Variant, I needed to write my own data structures (double linked list). I really wanted to use Boost.Intrusive which is quite efficient, but because I had to squeeze my own variant in there, I had to make use of unions which require PODs!<\/p>\n