Part 4 of "You Didn't Learn C++ in College"
I'm four weeks into CMU's 15-445 Database Systems project on B+Trees. My code compiles on the previous commit. I changed one line. The compiler responds with nine identical errors. Same bug, reported nine times, each with a different template instantiation.
Nine opportunities to learn about templates.
The project that broke me
CMU 15-445 has you build a database storage engine from scratch. Project 1 is a buffer pool manager. Project 2 is a B+Tree index that sits on top of it. The B+Tree stores key-value pairs where both the key type and value type are template parameters. Your tree needs to work with 4-byte keys, 8-byte keys, 16-byte keys, 64-byte composite keys. All without writing separate implementations for each.
The tree class has three template parameters: KeyType, ValueType, and KeyComparator. Every method you write needs to handle any combination. And your B+Tree pages live in the buffer pool as raw memory that you cast into typed nodes. One wrong type and you're debugging memory corruption. No one wants to do that.
I can't post the implementation (course policy), but the template structure is public. Three type parameters, dozens of methods, all generic over key and value types.
What college taught me about templates
My undergraduate C++ course covered templates in maybe two lectures. "Here's vector<int>, here's vector<string>, templates let you reuse code." That's pretty much it, two weeks condensed into two sentences.
I thought templates were syntax sugar. Write one function, use it with different types. The textbooks show template<typename T> T max(T a, T b) and I assumed the compiler did something clever at runtime to figure out the types.
I was completely wrong.
Templates generate code at compile time
When you write BPlusTree<GenericKey<8>, RID, GenericComparator<8>>, the compiler doesn't create a generic class that handles all types. It generates a completely new class. Specific to those exact types. With its own machine code.
Two instantiations with different key sizes are two entirely separate classes. The 8-byte version has no idea the 16-byte version exists. They don't share code. They don't share vtables. The compiler literally generates distinct implementations and compiles them independently. C++ templates have no runtime component. By the time your program runs, the templates are gone. They are replaced by concrete, specialized code for each type combination you actually used.
One bug, nine errors
Here's an actual error I caused. I passed a page_id_t (an int) where the function expected an RID:
error: reference to type 'const bustub::RID' could not bind to
an lvalue of type 'bustub::page_id_t' (aka 'int')
leaf->SetValueAt(insert_index, cause_error);
^~~~~~~~~~~
Clear enough. But the compiler didn't report one error. It reported nine:
note: in instantiation of member function
'bustub::BPlusTree<bustub::GenericKey<4>, bustub::RID,
bustub::GenericComparator<4>, 0>::InsertWithCrabbing' requested here
template class BPlusTree<GenericKey<4>, RID, GenericComparator<4>>;
^
Then the same error for GenericKey<8>. Then GenericKey<16>. Then GenericKey<32>. Then GenericKey<64>. Plus variants with different fourth template parameters.
The bottom of the B+Tree implementation file has explicit template instantiations. Lines that tell the compiler: generate complete code for each of these type combinations right here, in this translation unit. The codebase does this so linking works correctly. Template code normally lives in headers, but explicit instantiation lets you put implementations in .cpp files.
My one type error existed in a method called InsertWithCrabbing. The compiler instantiated that method nine times, once per explicit instantiation. Each instantiation hit the same bug. Nine identical errors, each with its own "in instantiation of" note showing which type combination triggered it.
The error itself was on line 311. The instantiation requests were on lines 1383-1395. A thousand lines apart in the output, connected by template machinery. Once I understood that each "note: in instantiation of" was just the compiler saying "I tried to generate code for this type combination and hit your bug," the error dump became readable.
Why databases use templates
After staring at enough error messages, the design made sense. Databases need type-specific code without paying for runtime polymorphism.
Consider the alternative with virtual functions. Every operation requires a virtual function call through a vtable. The compiler can't inline across the indirection. You end up casting void* everywhere, losing type safety. And if you want to optimize key comparisons for different key sizes, you need runtime branches.
Templates eliminate all of this. The compiler sees the exact types at compile time. For BPlusTree<GenericKey<8>, RID, GenericComparator<8>>, it generates code that operates directly on 8-byte keys. No indirection. No vtables. The optimizer can inline the comparator, see through all the abstractions, and generate tight machine code.
This is what C++ people mean by "zero-overhead abstraction." You write generic code, the compiler generates specialized code. The abstraction costs nothing at runtime because it doesn't exist at runtime.
Compile-time specialization
The template power in BusTub is straightforward: the compiler generates specialized code for each key size, and all the size calculations happen at compile time.
The comparator shows how non-type template parameters work:
template <size_t KeySize>
class GenericComparator {
public:
inline auto operator()(const GenericKey<KeySize> &lhs,
const GenericKey<KeySize> &rhs) const -> int {
for (uint32_t i = 0; i < key_schema_->GetColumnCount(); i++) {
Value lhs_value = lhs.ToValue(key_schema_, i);
Value rhs_value = rhs.ToValue(key_schema_, i);
if (lhs_value.CompareLessThan(rhs_value) == CmpBool::CmpTrue) {
return -1;
}
if (lhs_value.CompareGreaterThan(rhs_value) == CmpBool::CmpTrue) {
return 1;
}
}
return 0;
}
private:
Schema *key_schema_;
};
KeySize isn't a type, it's a compile-time constant. GenericComparator<8> only compares GenericKey<8> values. Try to compare a GenericKey<16> and you get a type error at compile time, not a runtime bug. The template parameter acts as a compile-time constraint that prevents mismatched key sizes from ever reaching production.
This is why the codebase has those explicit instantiations. The database knows it will index columns of certain sizes. Rather than let templates instantiate lazily and potentially bloat binary size with unused combinations, explicit instantiation says: generate exactly these versions, nothing else.
What C++20 fixed (and what you'll still encounter)
The 15-445 codebase uses C++17. Modern C++ has concepts, which make template constraints explicit and readable:
template <typename T>
requires std::integral<T>
T square(T x) { return x * x; }
And the error messages become human-readable:
error: cannot call square with type 'GenericKey<8>'
note: constraints not satisfied: std::integral<GenericKey<8>> evaluated to false
One line telling you exactly what went wrong.
Rust learned from this
Rust calls template instantiation "monomorphization" and builds constraints into the language from day one.
fn compare<T: Ord>(a: &T, b: &T) -> Ordering {
a.cmp(b)
}
The T: Ord is a trait bound. If you try to call this with a type that doesn't implement Ord, the error tells you exactly that. No instantiation chain. No nine repeated errors.
Rust also catches constraint violations where you define the generic function, not where you call it. C++ templates don't check that KeyType has the methods you need until instantiation. Rust checks the trait bounds immediately. This is what happens when language designers learn from 30 years of C++ template errors.
What I actually learned
The B+Tree project took me a month. I'm currently on a break from it because implementing concurrent access with latching broke my brain. But debugging template errors taught me something I never got from college.
Templates are a code generation system. When you write a template, you're writing instructions for the compiler to follow when it generates real code. Each instantiation creates a new, specialized version. The error messages are repetitive because the compiler hits your bug once per instantiation. Understanding this changes how you debug.
The B+Tree uses templates because database indexes need to work with arbitrary key types while generating optimal code for each one. Virtual functions would add overhead on every comparison, every key copy, every node traversal. Templates let you write the generic algorithm once and get specialized assembly for each key type. The compile-time pain is the price for runtime performance.
Next: Part 5 covers move semantics
Top comments (0)