A Thing I Learned: constexpr & consteval
A Thing I Learned is intended to be an ongoing series where I teach myself to write narrowly about some small thing that I have recently discovered that may also be of interest to others. In this first post in the series, I’m going to talk about a couple of new specifiers that have been added to modern C++, constexpr and consteval and how I recently had a revelation that their compile time capabilities were beyond what I originally understood.
While I never write C++ professionally these days, I do have fond memories of previous professional projects where C++ was the primary language and I harbor just enough nostalgia to try to keep up with some of the newer features added to the language. Recently, I decided to see if I had kept up with the new features enough to write a sudoku solver. This is something I often write when I’m attempting to learn a new language. Since I’m already familiar with my own solution, I can focus on learning the appropriate way to write it in the given language. Like many sudoku solvers in existence, mine derives from Peter Norvig’s famous post Solving Every Sudoku Puzzle. As Norvig explains, we can solve sudoku puzzles efficiently by using constraint propagation and then doing a backtracking search on what remains. If you are interested in those details, you really should read the original. I’m only going to talk about a very specific part of the solution and those are the constraints that are implicit in the sudoku puzzles. As Norvig describes it, every square has exactly 3 units and 20 peers. As an example, if square 0 is known to have the value of 1, then none of its other peers can have that value. The list of peers for each square is the data we need to do the constraint propagation. The peers are higlighted in yellow for each square in the puzzle below.
Typically when I write this sudoku solver, I build the list of peers as a static array computed once during runtime. The code for that in C++ might look something like this.
size_t quad_of(size_t ix) {
return (ix % 9) / 3 + 3 * (ix / 27);
}
size_t col_of(size_t ix) {
return ix % 9;
}
size_t row_of(size_t ix) {
return ix / 9;
}
auto get_peers() {
std::vector<size_t> peers;
peers.reserve(81 * 20);
for (auto i = 0; i < 81; i++) {
auto row = row_of(i);
auto col = col_of(i);
auto quad = quad_of(i);
for (auto j = 0; j < 81; j++) {
if (i == j) {
continue;
}
if (row == row_of(j) || col == col_of(j) || quad == quad_of(j)) {
peers.push_back(j);
}
}
}
return peers;
};
// ...
bool Puzzle::assign(int ix, int value) {
static auto peers = get_peers();
// ...
}
Each time I implement this, I’m tempted to generate the peers in advance and embed it in the code as an array literal. That’s nice in that it ensures the data is embedded in a read-only segment of the executable but to do that I would end up writing a small script to generate that array literal and then I’m left wondering if I should keep the code generation script or delete it. Also the source ends up cluttered with an unseemly 1,620 element array literal. Is it possible, I wondered, to build this array during compile time using something like constexpr? Turns out the answer is yes and it’s all pretty straightforward. First, though, let me give you a simple description of what I mean by constexpr and consteval.
What is a constexpr and a consteval?
Despite what Google Bard might tell you, constexpr was introduced in C++11, not C++17, and has been steadily improved since. When you add the constexpr specifier to a function or a value the compiler ensures that that function or value can be evaluated at compile time.
The consteval is a related specifier, introduced in C++20, that directs the compiler to ensure that the value or function is evaluated at compile time. As you might expect, a function that is specified with consteval can call one that is specified with constexpr, but not the other way around, which would be a compile time error.
So in theory, if we can create a consteval function that builds the table of peers we can evaluate that function entirely at compile time. Since it’s constexpr function, we know that any calls to it must be evaluated at compile time.
Computing the peer table at compile time
First, we know that our consteval get_peers function is going to need to call all constexpr functions, so there is the trivial matter of adding the constexpr specifier to row_of, col_of and quad_of. That’s no problem since the expressions in each of those functions are pretty trivial to do at compile time.
constexpr size_t quad_of(size_t ix) {
return (ix % 9) / 3 + 3 * (ix / 27);
}
constexpr size_t col_of(size_t ix) {
return ix % 9;
}
constexpr size_t row_of(size_t ix) {
return ix / 9;
}
There is one wrinkle, though, with our current get_peers function. std::vector uses dynamic memory allocations, which cannot be done at compile time. Apparently there are ways to use std::vector in a very limited manner inside of a constexpr function. Doesn’t matter, though, we don’t need the dynamic nature of a std::vector as we know the exact size of the table we’re building. We can easily switch to std::array with a statically declared size.
consteval auto get_peers() {
std::array<size_t, 81 * 20> peers = {};
auto iter = peers.begin();
for (auto i = 0; i < 81; i++) {
auto row = row_of(i);
auto col = col_of(i);
auto quad = quad_of(i);
for (auto j = 0; j < 81; j++) {
if (i == j) {
continue;
}
if (row == row_of(j) || col == col_of(j) || quad == quad_of(j)) {
*iter = j;
iter++;
}
}
}
return peers;
}
In the function where we need the table of peers, now we can just make a local static.
bool Puzzle::assign(int ix, int value) {
static constexpr auto peers = get_peers();
// ...
}
Does it work?
According to the C++20 specification, we should feel confident at this point that the table of 1,620 should have been generated at compile time and should be embedded somewhere in our executable. Computers, though, are liars. Just a few minutes ago, Google Bard told me that both constexpr and consteval were introduced as part of C++17. I’d rather verify this myself. If this table really is being computed at compile time, I’d expect to find the full contents of the table in one of the read only sections of the executable. I’m doing this on a Mac M1 so my hunch is that my table is going to be in the __const section (within the __TEXT segment) of the Mach-O object. Let’s see.
$ objdump -sj __const puzzle.o
puzzle.o: file format mach-o arm64
Contents of section __TEXT,__const:
0fb0 01000000 00000000 02000000 00000000 ................
0fc0 03000000 00000000 04000000 00000000 ................
0fd0 05000000 00000000 06000000 00000000 ................
0fe0 07000000 00000000 08000000 00000000 ................
0ff0 09000000 00000000 0a000000 00000000 ................
1000 0b000000 00000000 12000000 00000000 ................
1010 13000000 00000000 14000000 00000000 ................
1020 1b000000 00000000 24000000 00000000 ........$.......
1030 2d000000 00000000 36000000 00000000 -.......6.......
1040 3f000000 00000000 48000000 00000000 ?.......H.......
1050 00000000 00000000 02000000 00000000 ................
1060 03000000 00000000 04000000 00000000 ................
1070 05000000 00000000 06000000 00000000 ................
1080 07000000 00000000 08000000 00000000 ................
1090 09000000 00000000 0a000000 00000000 ................
10a0 0b000000 00000000 12000000 00000000 ................
10b0 13000000 00000000 14000000 00000000 ................
...
I guess it did work, after all. That’s clearly the table of peers, albeit in 64 bit little endian values. Should you, for some strange reason, have an interest in the sudoku solver that prompted this exploration, you can find it in my github. And if you are interested in a pretty solid intro to modern C++, I enjoyed Scott Meyer’s Effective Modern C++.