Array designators.

Or one more reason to use arrays.

A few days ago I’ve noticed one of the functions responsible for reporting runtime stats in production profiles. Its functionality is very simple - delegate logging based on enum value. Even though there are only a few enum values and its configuration is fairly trivial, author decided to use one of folly’s hash table implementations. To minimize external dependencies, I’m going to use std::unordered_map in the article instead of folly::F14FastMap

There are certainly many alternative ways to approach this, including switches, macros etc., to minimize code disruption and not sacrifice any flexibility I’ve decided to give a good old std::array instead a try

Array designators make initialization syntax even nicer than with maps, although I’ve used enum instead of enum struct in the article to avoid the need for static casts from enum to size_t.

Using optionals makes handling missing mappings easy and intuitive and compiler makes sure that array size is always at least large enough to accommodate the enum with highest value. The only extra requirement is handling new enums - when adding new enums it’s important to either add it to the array, using std::nullopt if it has no associated value or add a if (enum_value >= arr.size()) return std::nullopt in API for querying this array.

Ok, so far it looks like it’s possible to use an array, but why would we want to do this? Well, performance, of course. Hash table lookups have O(1) time complexity only in wonderland, but even every decent algorithms course or book would mention that it’s not really constant and it highly depends on the implementation. For example, in the absolute worst case of using chaining for collision handling, all values can end up in the linked list, resulting in O(N) complexity, but usually good implementation of open addressing is pretty close to constant. Still, even assuming O(1) time, theory claims that 100000000 * O(1) is still O(1) but nobody would be happy with this in practice.

Enough of words.

Let’s take a look at the benchmark results

5.6 times! In my case, this function is hot enough to show up in global profiling dashboard, so this makes a huge difference.