Frozen - An header-only, constexpr alternative to gperf for C++14 users

An open source, header-only library that provides fast, immutable, constexpr-compatible implementation of std::set, std::map, std::unordered_map and std::unordered_set to C++14 users. It can be used as an alternative to gperf.


I've always been frustrated, when initializing a const std::set<int> keys = {1, 2, 3}, to see that the structure is initialized at runtime. Gast, it's marked as const! Couldn't this be a simple binary search in a sorted, constant array of ints?

And what about this one: const std::unordered_set<int> keys = {4, 5, 6}? By the eyes of my Bonnie Mary, one could find a hash function without collision for these three little pigs and use it, instead of doing the whole stuff at runtime!

This should even make lookup faster, right?

Actually, there already exists solutions to the second problem, known as perfect minimal hashing. You may have heard of gperf. It does exactly what we want: take a list of values, find a collision-free hash function for these values and generate the appropriate C code. It slightly complicates the build but it gets the jobs done.

This article uses C++14-powered constexpr to solve both issues, initializing containers at compile time, resulting in 0-cost initialization and fast lookup. The whole stuff is bundled in the frozen library.

It's available under the Apache license 2.0 on github.

std::set<> and std::map<>

std::set<> and std::map<> are standard containers that only require their keys to be comparable. The lookup is required to be in \(\mathcal{O}(log(n))\) and the implementation is usually based on a red-black tree to keep a balanced tree. The lookup is done using a binary search.

For an immutable set, there's no need for a red-black tree, a plain sorted array is enough. The constexpr constructor is in charge of sorting the initializer list, storing it into the array and then, the lookup is implemented using a standard binary search.

From the user point of view, the structure declaration only requires an extra size template parameter:

#include <frozen/set.h>

constexpr frozen::set<int, 3> keys = {1, 2, 3};

int some_user(int key) {
    return keys.count(key);

Because keys is used in a non-constexpr context by some_user, it does not only live in the constexpr world. Let's have a look at the generated assembly to find out why:

0000000000000000 <_Z9some_useri>:
   0:    83 ff 02                 cmp    edi,0x2
   3:    7e 10                    jle    15 <_Z9some_useri+0x15>
   5:    b8 03 00 00 00           mov    eax,0x3
   a:    83 ff 03                 cmp    edi,0x3
   d:    74 0e                    je     1d <_Z9some_useri+0x1d>
   f:    31 c0                    xor    eax,eax
  11:    0f b6 c0                 movzx  eax,al
  14:    c3                       ret
  15:    0f 94 c0                 sete   al
  18:    0f b6 c0                 movzx  eax,al
  1b:    ff c0                    inc    eax
  1d:    39 f8                    cmp    eax,edi
  1f:    0f 9e c0                 setle  al
  22:    0f b6 c0                 movzx  eax,al
  25:    c3                       ret

The binary search is actually unrolled, and the keys are set as immediate operands. Brest!

When trying with a larger set of elements, the unrolling + inlining still works nicely and the body of the lookup ends in a very large function, without any function call.

Implementation detail

The binary search is implemented as a recursive function, specialized for the size of the current range. This takes advantage of the compile-time information on the set size, and ends up with a fully unrolled lookup. The text-book iterative algorithm uses a while loop which performs very badly in that case, while this version plays very well with the compiler, or at least with Clang 5. Note that fully unrolling the binary search may be a bad choice, especially if it happens to stress the instruction cache too much. Yet, it works flawlessly for small sets!

template <class T, class Compare> struct LowerBound {
  T const &value;
  Compare const &compare;
  constexpr LowerBound(T const &value, Compare const &compare)
      : value(value), compare(compare) {}

  template <class ForwardIt>
  inline constexpr ForwardIt doit(ForwardIt first,
                                  std::integral_constant<std::size_t, 0>) {
    return first;

  template <class ForwardIt, std::size_t N>
  inline constexpr ForwardIt doit(ForwardIt first,
                                  std::integral_constant<std::size_t, N>) {
    auto constexpr step = N / 2;
    auto it = first + step;
    if (compare(*it, value)) {
      auto constexpr next_count = N - (step + 1);
      return doit(it + 1, std::integral_constant<std::size_t, next_count>{});
    } else {
      auto constexpr next_count = step;
      return doit(first, std::integral_constant<std::size_t, next_count>{});

std::unordered_set<> and std::unordered_map<>

The main feature of frozen is a static version of std::unordered_set<> and std::unordered_map<>. Finding a collision-free hashing function for a given set of keys is a well-studied problem, known as perfect (eventually minimal) hashing problem. I did not invent anything here, just read this great blogpost that provides a simple algorithm in Python, converted into a constexpr version and voilĂ . For the lazy ones, the whole idea is to use a first regular hashing function and fill the buckets. For those with collisions, order by number of collisions, we iteratively try another hashing function parametrized by a seed. Once we find a seed parameter that makes all keys fall into an empty slot, we move to the next bucket and so on until only collision-free entries are left, then we put them into the empty slots. This uses an auxiliary table to hold the extra seeds and collision-free displacements.

Using this algorithm, it's possible to declare a frozen unordered set like this:

#include <frozen/unordered_set.h>

constexpr frozen::unordered_set<int, 3> keys = {1,2,4};

int some_user(int key) {
    return keys.count(key);

with the guarantee that the frozen::unordered_set<int, 3>::count(int) call is collision-free.

The assembly dump of the some_user function tells us more about the implementation:

0000000000000000 <_Z9some_useri>:
   0:    89 f8                    mov    eax,edi
   2:    83 e0 03                 and    eax,0x3
   5:    48 8b 04 c5 00 00 00     mov    rax,QWORD PTR [rax*8+0x0]
   c:    00
   d:    48 85 c0                 test   rax,rax
  10:    78 45                    js     57 <_Z9some_useri+0x57>
  12:    48 63 cf                 movsxd rcx,edi
  15:    48 31 c8                 xor    rax,rcx
  18:    48 89 c1                 mov    rcx,rax
  1b:    48 f7 d1                 not    rcx
  1e:    48 c1 e0 15              shl    rax,0x15
  22:    48 01 c8                 add    rax,rcx
  25:    48 89 c1                 mov    rcx,rax
  28:    48 c1 e9 18              shr    rcx,0x18
  2c:    48 31 c1                 xor    rcx,rax
  2f:    48 69 c1 09 01 00 00     imul   rax,rcx,0x109
  36:    48 89 c1                 mov    rcx,rax
  39:    48 c1 e9 0e              shr    rcx,0xe
  3d:    31 c1                    xor    ecx,eax
  3f:    6b c1 15                 imul   eax,ecx,0x15
  42:    89 c1                    mov    ecx,eax
  44:    c1 e9 1c                 shr    ecx,0x1c
  47:    31 c1                    xor    ecx,eax
  49:    89 c8                    mov    eax,ecx
  4b:    c1 e0 1f                 shl    eax,0x1f
  4e:    29 c8                    sub    eax,ecx
  50:    f7 d8                    neg    eax
  52:    83 e0 03                 and    eax,0x3
  55:    eb 03                    jmp    5a <_Z9some_useri+0x5a>
  57:    48 f7 d0                 not    rax
  5a:    48 8b 0c c5 00 00 00     mov    rcx,QWORD PTR [rax*8+0x0]
  61:    00
  62:    31 c0                    xor    eax,eax
  64:    39 3c 8d 00 00 00 00     cmp    DWORD PTR [rcx*4+0x0],edi
  6b:    0f 94 c0                 sete   al
  6e:    c3                       ret

The first and performs the first (simplistic) hashing. Then it performs a lookup in the auxiliary table and based on the result, it either computes the auxiliary hash (based on the extra seed from the auxiliary table), or directly picks the index. Either way, it performs the comparison between the argument and the candidate and returns the result.

The string Case

A typical candidate for use with frozen are... strings. And because std::string cannot be used in a constexpr environment and std::string_view is only available in C++17 (with a constexpr constructor!), frozen provides a frozen::string class that acts as a view on existing data. The operator""_s can be used to easily convert C-style strings to this class.

Bonus: Usage in Constant Context

That's anecdotal, but the following is possible with frozen:

constexpr frozen::unordered_set<int, 4> UnluckyNumbers = {
    4, // from china
    9, // from japan
    17, // from Italy
    13, // Triskaidekaphobia

constexpr int value = ...;
static_assert(!UnluckyNumbers.count(value), "you're program is ill-blessed in some geographical location!");

Comparison to gperf

The gperf tool proposes an ahead-of-time compiler that generates perfect, minimal hash.

Consider this list of words, listed in the gperf input file format:


Running gperf > titan.c produces a C file that contains a const char * in_word_set(const char *str, unsigned int len) function to perform the check.

The equivalent C++ code based on frozen is the following, using frozen::string:

#include <frozen/unordered_set.h>
#include <frozen/string.h>

using namespace frozen::string_literals;

constexpr frozen::unordered_set<frozen::string> Titans = {
    "Coeus"_s, "Crius"_s, "Cronus"_s, "Hyperion"_s,
    "Iapetus"_s, "Mnemosyne"_s, "Oceanus"_s, "Phoebe"_s,
    "Rhea"_s, "Tethys"_s, "Theia"_s, "Themis"_s,
    "Asteria"_s, "Astraeus"_s, "Atlas"_s, "Aura"_s,
    "Clymene"_s, "Dione"_s, "Helios"_s, "Selene"_s,
    "Eos"_s, "Epimetheus"_s, "Eurybia"_s, "Eurynome"_s,
    "Lelantos"_s, "Leto"_s, "Menoetius"_s, "Metis"_s,
    "Ophion"_s, "Pallas"_s, "Perses"_s, "Prometheus"_s,

The benchmarking program is the following:

#include <iostream>
#include <string>
#include <unordered_set>
#include <chrono>

int main() {
    const std::unordered_set<std::string> Titans = {
        "Coeus", "Crius", "Cronus", "Hyperion",
        "Iapetus", "Mnemosyne", "Oceanus", "Phoebe",
        "Rhea", "Tethys", "Theia", "Themis",
        "Asteria", "Astraeus", "Atlas", "Aura",
        "Clymene", "Dione", "Helios", "Selene",
        "Eos", "Epimetheus", "Eurybia", "Eurynome",
        "Lelantos", "Leto", "Menoetius", "Metis",
        "Ophion", "Pallas", "Perses", "Prometheus",

  std::string line;
  unsigned count = 0;

  std::chrono::duration<double, std::milli> duration{0};

  while(std::cin) {
    std::getline(std::cin, line);
    auto start = std::chrono::steady_clock::now();
      count += 1;
    auto stop = std::chrono::steady_clock::now();
    duration += stop - start;
  std::cout << "duration: " << duration.count() << " ms" << std::endl;
  std::cout << count << std::endl;

  return 0;

Yes, it's probably I/O bound, but as we only measure the hashing time, it still gives a hint on the hashing time when the key is not in the set.

And here is the result, using /usr/share/dict/british-english-large as input (fun fact: 13 titans are present in this dictionary):

Engine Timing (ms)
std 57
gperf 5
frozen 9

So frozen is within the reach of gperf, and both are way faster than the standard solution.

That's still frustrating. Fortunately, we could change the hashing function (djb2 and FNV-1a) generator used by frozen to improve this situation. The default is:

template <> struct elsa<string> {
  constexpr std::size_t operator()(string value) const {
    std::size_t d = 5381;
    for (std::size_t i = 0; i < value.size; ++i)
      d = (d * 33) +[i];
    return d;
  constexpr std::size_t operator()(string value, std::size_t seed) const {
    std::size_t d = seed;
    for (std::size_t i = 0; i < value.size; ++i)
      d = (d * 0x01000193) ^[i];
    return d;

But using the much simpler:

struct olaf {
  constexpr std::size_t operator()(frozen::string value) const {
    return value.size;
  constexpr std::size_t operator()(frozen::string value, std::size_t seed) const {
    std::size_t d = seed;
    std::size_t bound = std::min(value.size, (std::size_t)2);
    for (std::size_t i = 0; i < bound; ++i)
      d = (d * 0x01000193) ^[i];
    return d;

constexpr frozen::unordered_set<frozen::string, 33, olaf> Titans = {...};

We get the same timings as gperf \o/. This generator is less robust though, so not suitable as a default.


Programming with constexpr in the post C++14 world is great. It makes it possible to achieve the same job as code generator while only relying on a standard C++ compiler. And in the case of perfect hashing, it gives very interesting result! One note though: on my laptop, using frozen with GCC is currently a pain, because the compiler hangs for no apparent good reason; Let's report this!


First, thanks to Steve Hanov for his great blog.

Then thanks to Romain and Adrien for their feedback, and all the Quarkslab proof readers, especially w1gz!