{"id":1284,"date":"2015-10-14T23:17:47","date_gmt":"2015-10-15T06:17:47","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1284"},"modified":"2015-10-15T08:51:06","modified_gmt":"2015-10-15T15:51:06","slug":"compile-time-counters-revisited","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1284","title":{"rendered":"Compile-time counters, revisited"},"content":{"rendered":"

(Start at the beginning of the series<\/a> – and all the source can be found in my github repo<\/a>)<\/p>\n

Some time ago I read a blog post<\/a> showing how to make a compile-time counter: a constexpr<\/code> function that would return monotonically increasing integers. When I first read it I didn’t really take the time to understand it fully, but now that I was on a compile-time computation kick, I decided to grok it fully.<\/p>\n

Without getting too far into the nitty-gritty (go read the other blog post if you’re interested), the technique relies on using template instantiations to “bring-to-life” functions that affect future template instantiations. Thus we have a flag<\/code> that declares (but does not yet define) a friend function:<\/p>\n

\r\ntemplate \r\nstruct flag\r\n{\r\n  friend constexpr int adl_flag (flag);\r\n};\r\n<\/pre>\n
And then a recursive reader<\/code> function template that uses ADL and SFINAE to match against the (as-yet-undefined) friend function(s), bottoming out at zero:<\/p>\n
\r\ntemplate {})>\r\nconstexpr int reader(int, flag)\r\n{\r\n  return N;\r\n}\r\n\r\ntemplate \r\nconstexpr int reader(\r\n    float, flag, int R = reader(0, flag{}))\r\n{\r\n  return R;\r\n}\r\n\r\nconstexpr int reader(float, flag<0>)\r\n{\r\n  return 0;\r\n}\r\n<\/pre>\n
And finally, a writer<\/code> that, when instantiated with the result of calling reader<\/code>, instantiates the friend function, making the next call to reader<\/code> terminate at one level higher:<\/p>\n
\r\ntemplate \r\nstruct writer\r\n{\r\n  friend constexpr int adl_flag (flag)\r\n  {\r\n    return N;\r\n  }\r\n  static constexpr int value = N;\r\n};\r\n<\/pre>\n
This is a curiosity, right? A foible of C++, a fairy tale told by wizened programmers to fresh graduates to simultaneously impress and revolt them, no? Could anything useful be done with this? Well, C++ is full of such tales, and it’s a short hop from can’t-look-away-revolting to established feature – after all, template metaprogramming was discovered pretty much by accident…<\/p>\n
In fact, while at CppCon, I met up with Ansel and Barbara from CopperSpice<\/a>, who are using a very similar technique to do away with the Qt Metaobject Compiler.<\/p>\n
Max recursion depth, we meet again<\/strong><\/p>\n
My first thought was that this technique suffers at the hands of my old enemy, maximum recursion depth. In this case, maximum template instantiation depth, which despite a standard-recommended 1024, is frequently just 256 – lower than the recommended constexpr<\/code> recursion depth of 512. So let’s do something about that.<\/p>\n
Well, one quick-and-dirty way to do this is to compute the count in two halves: lower bits and upper bits, and then stick them together. When we reach the max on the lower bits, we’ll roll over one of the upper bits. So we have two flags representing the high and low, with the low flag also parameterized on the high bits:<\/p>\n
\r\ntemplate \r\nstruct flag1\r\n{\r\n  friend constexpr int adl_flag1(flag1);\r\n};\r\ntemplate \r\nstruct flag2\r\n{\r\n  friend constexpr int adl_flag2(flag2);\r\n};\r\n<\/pre>\n
And two readers: the low bits reader is in a struct to avoid partial specialization of a function, because it’s effectively parameterized on the high bits as well as the low bits.<\/p>\n
\r\ntemplate \r\nstruct r1\r\n{\r\n  template {})>\r\n  static constexpr int reader(int, flag1)\r\n  {\r\n    return L;\r\n  }\r\n  template \r\n  static constexpr int reader(\r\n      float, flag1, int R = reader(0, flag1{}))\r\n  {\r\n    return R;\r\n  }\r\n  static constexpr int reader(float, flag1)\r\n  {\r\n    return 0;\r\n  }\r\n};\r\n\r\ntemplate {})>\r\nconstexpr int reader(int, flag2)\r\n{\r\n  return H;\r\n}\r\ntemplate \r\nconstexpr int reader(\r\n    float, flag2, int R = reader(0, flag2{}))\r\n{\r\n  return R;\r\n}\r\nconstexpr int reader(float, flag2<0>)\r\n{\r\n  return 0;\r\n}\r\n<\/pre>\n
The low bits writer looks much the same as before, and the high bits writer is specialized on a bool<\/code> indicating whether or not to instantiate the friend function, which we only do when the low bits roll over:<\/p>\n
\r\ntemplate \r\nstruct writehi\r\n{\r\n  friend constexpr int adl_flag2(flag2)\r\n  {\r\n    return H;\r\n  }\r\n  static constexpr int value = H;\r\n};\r\n\r\ntemplate \r\nstruct writehi\r\n{\r\n  static constexpr int value = H;\r\n};\r\n<\/pre>\n
The writer can then write both the high and low bits accordingly:<\/p>\n
\r\ntemplate \r\nstruct writer\r\n{\r\n  static constexpr int hi_value =\r\n    writehi::value;\r\n  static constexpr int lo_value =\r\n    writelo::value;\r\n  static constexpr int value = (H << BIT_DEPTH) + L;\r\n};\r\n<\/pre>\n
Using this approach we can easily increase the maximum number that we can get out of our counter from 256 to 16k or so, which is enough for one translation unit, for me.<\/p>\n
Random acts of compiler abuse<\/strong><\/p>\n
Now, a counter is OK, as far as that goes, but something more useful might be nice... how about random numbers? But surely only a madman would try to implement a Mersenne Twister in C++11 constexpr<\/code>-land. (This despite the fact that I did SHA256 string hashing.) No, these days when I think of random numbers, I think of Melissa O'Neill and her excellent PCG32<\/a>. If you haven't seen her video<\/a>, go watch it. I'll wait here. PCG32 has some distinct advantages for constexpr<\/code> implementation:<\/p>\n