Skip to content

Before the Program Runs

Edit source

Switching on a string, classifying a character, and coloring a terminal, all resolved at compile time.

Part 27 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries I carved out of Xapiand. This opens the compile-time chapter with three tiny ones: hashes, char-classify, and term-color.

The fastest code is the code that never runs, and the closest thing to that in C++ is code the compiler runs for you, before main ever starts. constexpr turned that from a party trick into a tool: a value computed at compile time costs nothing at runtime, and a mistake in it becomes a compile error instead of a bug. Three of the smallest familiars live entirely in that world, and each one takes a cost you would normally pay every time the program runs and pays it once, at the build.

C++ lets you switch on an integer and, pointedly, not on a string. The idiomatic workarounds are an if/else if ladder of == comparisons, which is O(cases) and ugly, or building a std::map at startup, which allocates and is O(log n). hashes offers the third way: a header of constexpr hash functions, FNV-1a, djb2, a constexpr xxHash-64, integer mixers, jump-consistent hashing, plus _fnv1a and _xx user-defined literals. Because the hash of a string literal is a compile-time constant, you can hash the input once and switch on it, with case labels like "commit"_fnv1a that the compiler folds to integers:

switch (fnv1ah32::hash(verb)) {
case "commit"_fnv1a: return do_commit();
case "search"_fnv1a: return do_search();
// ...
}

That is a switch over strings with no allocation and no string compares, the case labels checked at compile time. Hash values are sparse, so the compiler builds a binary search rather than a jump table; the next post makes them dense. It is the trick that turns a request verb or a token into a branch without a map or a ladder, and it is exactly how a search engine dispatches its dozens of operation names.

Underneath a lot of parsing sits the humble question “is this byte a digit? a letter? whitespace?”, and the standard answer, <cctype>’s isdigit and friends, carries baggage most parsers do not want: it is locale-dependent, so the answer can change under you, and it is a function call, not a constant. char-classify replaces it with one 256-entry table of packed flags and a set of constexpr masked lookups, is_digit, is_alpha, is_space, is_hexdigit, tolower, toupper, and a byte-to-hex char_repr, with nothing behind them but the standard library. Every classification is a compile-time-capable array read, locale-free and deterministic, so a lexer built on it is faster, portable, and cannot be quietly changed by a setlocale somewhere else in the process.

term-color has the cleverest trick of the three. A named color like RED or STEEL_BLUE expands, at compile time, into an ANSI escape sequence, but the problem is that terminals disagree about which escapes they understand: some do 16 colors, some 256, some 24-bit truecolor. So term-color emits three escapes back to back, worst first: the 16-color code, then the 256-color code, then the truecolor code. A terminal applies each escape it recognizes in turn and ends on the last one it supports, so the richest tier it can render wins, and a single compile-time constant is portable across every terminal without any runtime detection. When you do need one guaranteed tier, to honor a --color mode, the NO_COLOR convention, or a plain log file that should get no escapes at all, collapse() and apply() resolve the stacked string down at runtime. The default is a constant that just works; the runtime path is there for when “just works” is not precise enough.

These three are one corner of a larger idea, and the chapter they open is the rest of it: the Familiars that mainly live at build time, each moving a cost you would otherwise pay at runtime onto the compiler. Sorted by the job they do:

  • Hashing. hashes: constexpr FNV-1a, djb2, a constexpr xxHash-64, integer mixers, jump-consistent hashing, and the _fnv1a and _xx literals. The string switch above stands on it.
  • Perfect hashing. constexpr-phf: a minimal perfect hash over a fixed set of integer keys, built while the program compiles, so a known set of keys becomes a dense, collision-free, branch-free index into a table. The next post is all about it.
  • Character classification. char-classify: the locale-free constexpr byte tables above, is_digit and its siblings with nothing behind them but a masked array read.
  • Enum reflection. enum-reflection, with utype: turn an enum value back into the name you wrote it with, and the name back into the value, both resolved at compile time. Its post closes the chapter.
  • Terminal color. term-color: the worst-first stacked ANSI constant above, portable across terminals with no runtime detection.

Different jobs, one habit: the answer is a constant the compiler already worked out.

Reach for these when a cost you keep paying at runtime, a string dispatch, a character check, a color code, could be a constant the compiler folds instead. Skip them where the input is genuinely dynamic and no compile-time form exists. They are small, but they are the honest shape of the idea the rest of this chapter runs on: do it once, at the build.

The next familiar is the machinery under that string switch, made exact: a hash table for a fixed set of keys, built entirely at compile time, that is guaranteed to never collide.