I’m a huge believer in formal methods - theorem provers and model checkers are invaluable for mission critical application and services. Unfortunately, Coq, TLA+ or Idris are still far from mainstream, so I rarely have a chance to use them in practice.
At the same time, C++ is constantly evolving and improving. And even though it’s far from Idris, it’s powerful enough to perform at least simple checks. For example, in Haskell, head returns the first element of the list. It’s expected to be non-empty, but this is not enforced at compile time, so something like head [] would fail only at runtime. Similarly, it makes no sense to call tail on the empty list, but again, it’s not something compiler would help you with.
Chances are, that at some point you’ve used or created Stack or similar data types that have methods like pop that have checks for emptiness which fail at runtime. So what does it have to do with performance and why are we talking about this? Well, it’s because these runtime checks add runtime overhead even though they are unlikely to fail in case data structure is used properly, so we are essentially paying for something we rarely need. Because of this, some developers use debug only assertions, which removes this overhead in production builds, but is fundamentally unsafe and not something I’d be comfortable doing.
Let’s take a look at a super simplified version of List type
So what’s so special about it? Not much, but note that it tracks its size at compile time using template parameter N. It’s used to remove head and tail member functions in case N is 0, so that usages
wouldn’t compile
but valid usages like
works like a charm.
Disclaimer: this List implementation is horrible - I intentionally ignore most best practices to reduce the size to the minimum, so that we can focus on the aspects relevant to this article.