This special Guru of the Week series focuses on contracts. We covered basic assertions in GotW #97… but not all asserted conditions are created equal.
Given some assertion facility that can be used like this:
MyAssert( condition ); // expresses that ‘condition’ must be true
1. Give one example each of an asserted condition whose run-time evaluation is:
a) super cheap
Without resorting to constexpr expressions, it’s hard to find one cheaper than the one we saw in GotW #97 Example 3, which we can simplify down to this:
// Example 1(a): A dirt cheap assertion (from GotW #97 Example 3)
int min = /* some computation */;
int max = /* some other computation */;
MyAssert( min <= max );
This is always going to be dirt cheap. Not only is the integer comparison operation cheap, but min and max are already being accessed by this function and so they’re already “hot” in registers or cache.
b) arbitrarily expensive
“A condition that’s expensive? That sounds pretty easy,” you might say, and you’re right!
One commonly cited example is is_sorted. Just to emphasize how expensive it can be both in absolute terms and also relative to the program’s normal execution, let’s put it inside a well-known function… this is a precondition, but we’ll write it as an assertion in the function body for now which doesn’t affect this question: [1]
// Example 1(b): An arbitrarily expensive assertion
template <typename Iter, typename T>
bool binary_search( Iter begin, Iter end, const T& value ) {
MyAssert( is_sorted(begin, end) );
// ...
}
Checking that all the container’s elements are in ascending order requires visiting them all, and that O(N) linear complexity is arbitrarily expensive when the container’s size N can be arbitrarily large.
The icing on the cake: In this example, just evaluating the assertion requires doing more work than the entire function it appears in, which is only O(log N) complexity!
On a humorous note, O(N) remains O(N) no matter how hard we try to make it efficient:
MyAssert( std::is_sorted( std::execution::par, begin(s), end(s) ) );
// still O(N) arbitrarily expensive, but good try!
2. What does the answer to Question 1 imply for assertion checking? Explain.
We want a way to enable checking for some assertions but not others in the same code, because we may not always be able to afford expensive checks. That’s true whether we’re enabling checking at test time (e.g., on the developer’s machine) or at run time (e.g., in production).
Some conditions are so expensive that we may never check them without a good reason, even in testing. Example 1(b)’s is_sorted is a great example: You probably won’t ever enable it in production, and likely not by default in testing, except by explicitly turning it on during a bug hunt after enabling checking for cheaper assertions wasn’t enough or pointed at this data structure for deeper investigation. [2]
Other conditions are so cheap we’ll probably always check them absent a good reason not to, even in production. Example 1(a)’s min <= max is at this other end of the scale: It’s so dirt cheap to check that it’s unlikely we’ll ever have a performance reason to disable it. [2]
So it makes perfect sense that if Examples 1(a) and 1(b) appear in the same source file, the developer will want to enable checking for 1(b)’s assertion only by some kind of manual override to explicitly request it, and enable checking for 1(a)’s assertion all the time.
3. Give an example of an asserted condition that is in general impossible to evaluate, and so cannot be checked.
One common example is is_reachable for pointers or other iterators, to say that if we increment an iterator enough times we can make it equal to (refer to the same object as) a second iterator:
// Example 3: Very reasonable, but generally not checkable
auto first_iterator = /*...*/;
auto last_iterator = /*...*/;
MyAssert( is_reachable(first_iterator, last_iterator) );
std::find( first_iterator, last_iterator, value );
In general, there’s no way to write is_reachable. You could try to increment first_iterator repeatedly until it becomes equal to last_iterator, but when the latter is not reachable that might never happen and even just trying would often be undefined behavior.
You might be tempted to test is_reachable using std::distance:
MyAssert( std::distance(first_iterator, last_iterator) >= 0 );
… but that would be horribly wrong. Can you see why?
Take a moment to think about it before continuing…
…
…
… okay. The answer is that std::distance itself requires that last_iterator is reachable from first_iterator, otherwise it’s undefined behavior. So this maybe-tempting-looking alternative actually assumes what we want to prove, and so it’s not useful for this purpose. (GotW #100 will consider in detail the general question of preconditions of contract subexpressions, which covers examples like this one.)
Can these kinds of conditions still be useful?
Yes. In practice, these kinds of conditions spell out “this is a formal comment.” Static analyzers and other tools may be able to test such a condition in a subset of cases; for example, at some call sites an analyzer may be able to infer statically that two iterators point into different containers and so one isn’t reachable from the other. Alternatively, the tools might support special pseudofunction names that they recognize when you use them in assertion expressions to give information to the tool. So the conditions can still be useful, even if they can’t generally be checked the normal way, by just evaluating them and inspecting the result.
4. How do these questions help answer:
a) what “levels” of asserted conditions we should be able to express?
There’s a wide spectrum of “expensiveness” of assertion conditions, ranging from cheap to arbitrarily high to even impossible. In the post-C++20 contracts proposal at [3], this is partly captured by the proposed basic levels of default, audit, and axiom, roughly intended to represent “cheap,” “expensive,” and “impossible” respectively.
Because we need to check these with different frequencies (or not at all), we need a way to enable and disable checking for subsets of assertions independently, even when they’re in the same piece of code.
GUIDELINE: Distinguish between (at least) “cheap,” “expensive,” and “impossible” to evaluate assertions. If you develop your own assertion system for in-house use, support enabling/disabling at least these kinds of assertions independently. [1] I say “at least” because what’s “expensive” is subjective and will vary from program to program, from team to team… and even within a program from your code to your third-party library’s code that you’re calling. Having just two preset “cheap” and “expensive” levels is minimal, but useful.
b) why the assertions we can “practically” write are a subset of all the ones we might “ideally” like to write?
It can be useful to distinguish between all ideal assertions, meaning everything that has to be true at various points in the program for it to run correctly, and the practical assertions, meaning the subset of those that can be reasonably expressed as a C++ expression and checked. In GotW #97 question 3, part of the solution says that “if an assertion fails” then…
… there is a program bug, possibly in the assertion itself. The first place to look for the bug is in this same function, because if prior contracts were well tested then likely this function created the first unexpected state.
If we could write all ideal assertions, and exercise all control flow and data flow during testing, then a failed assertion would definitely mean a bug in the same function where it was written. Because we realistically can’t write and exercise them all, though, we could be observing a secondary effect from a bug that happened earlier. Still, this function is the first place to start looking for the bug.
Notes
[1] Upcoming GotWs will cover preconditions and violation handling. For handlers, we’ll cover additional distinctions such as categories of violations (e.g., to distinguish safety-related checks vs. other checks).
[2] As always, any checks left on in production would often install a different handler, such as a log-and-continue handler rather than a terminating handler; see GotW #97 Question 4, and note [1].
[3] G. Dos Reis, J. D. Garcia, J. Lakos, A. Meredith, N. Myers, and B. Stroustrup. “P0542: Support for contract based programming in C++” (WG21 paper, June 2018).
Acknowledgments
Thank you to the following for their feedback on this material: Joshua Berne, Guy Davidson, J. Daniel Garcia, Gábor Horváth, Maciej J., Andrzej Krzemieński.
Sutter’s Mill 
@Anton:
> I think these tools will never arise and the reason to support my believes is if they could they would already do this.
Actually the tools I describe exist already. Some static analysis tools already do recognize C assert() calls and diagnose violations they can statically prove (or suspect). Some diagnose cases of undefined behavior they can prove statically, such as null pointer dereference. Some offer custom pseudofunctions like those I mentioned that let the programmer ask to apply custom rules recognized by the tool. Here’s a list of 25 analyzers for C and C++ on Wikipedia: https://en.wikipedia.org/wiki/List_of_tools_for_static_code_analysis#C,_C++
> why would you try to write such an axiom contract in the first place if you can leverage the type system?
This is an excellent question we’ll touch on soon. In the upcoming GotW #101, “Preconditions, Part 2,” a major focus will be the overlap where a precondition could be expressed in the type system (incl. static type and dynamic invariant) and as a code contract, and why to generally prefer the former but also don’t overdo it. As Bjarne Stroustrup commented regarding precondition assertions in particular, ‘types used for argument checking only can be useful but we have seen them seriously overused — like all other useful features and techniques.’
@Maciej:
> assert with constexpr would be the cheapest as it can be optimized out
Good point, I was focusing on run-time evaluation but I should mention that for completeness… added the phrase to the front of 1(a) and added you to Acknowledgments. Thanks.
> if (n==8) unreachable();
Note this is a current technique to spell an “assumption,” to inject a fact into the optimizer, which is different (and ~1000x rarer) than assertions, and so…
> In release build the compiler would produce no-code, however, impact of the presence of statement could lead to powerful optimizations.
… here be dragons. If our assertions were commonly emitted as assumptions in release builds, that would be very dangerous (the other direction makes sense though, to assert our assumptions in debug). For the detailed answer, please see my paper P2064: https://wg21.link/p2064 . You’re in good company in making this suggestion, though; the reason I spent weeks writing that paper was because this idea kept surfacing in the committee’s contracts discussions, and I think now we (the committee) understand that post-C++20 contracts need to make assertions and assumptions clearly distinct things.
@Adrian, good point about amortizing post-test-time checking costs by spreading them out and doing only a few in a given execution.
There are checks that are not arbitrarily expensive, but still expensive enough that you wouldn’t check them in production. For example, checking to see if a container is sorted may be too expensive for production, but if you know the container size has an upper bound, it’s not technically arbitrarily expensive.
I know of one experiment that’s finding real bugs in a production service by stochastically sampling assertion-like checks at run time. It almost always skips the expensive check but occasionally, at randomly selected times, it does the expensive check. If there’s a lurking bug, you’ll miss it most of the time, but in a high volume system, you can occasionally catch one. (This depends on make the test/don’t-test decision extremely cheap.)
Furthermore, you can tune how frequently the expensive check is done to ensure that your overall metrics still hit their goals. Even better, the system can tune itself based on performance goals.
I was highly skeptical of the experiment when I learned about it, thinking that the odds of a rare bug being caught by a rare check were too small to be useful to be worth the cost of the test/don’t-test decision. But the results have made me a believer.
I think there might be another angle dividing assertions.
a0) assert with constexpr would be the cheapest as it can be optimized out
It would make sense to have a generic assert that handles such situations during compilation. I mean a templated method instantiation or invocation of a function with constant expressions passed as a parameter.
a1) assert with a pure expression transparent to compiler
What I mean by `expression transparent to compiler` is an expression, whose code is entirely visible to compiler in current compilation unit. And by pure I mean no side-effects nor access to global variables.
This class of assertions can be utilized by compilers to optimize production code.
e.g. let’s see how `assert(n==8)` could look be expanded in debug and release build:
1. debug (expr1):
if (n==8)
throw logic_error(…);
2. release (expr2):
if (n==8)
unreachable();
In release build the compiler would produce no-code, however, impact of the presence of statement could lead to powerful optimizations.
I’ve been using this mechanism quite extensively (low latency applications). There are some issues there. One is that C++ language does not specify (nor compilers implement) a mechanism to identify whether the expression expr2 gets in fact eliminated. And mistake can be costly (lot of redundant code on critical path).
a2) assert with expressions that contain side effects
If there was a way for compiler to flag this cases… noting that this is a non-trivial matter as some side effects might be benign.
a3) assert with expressions not transparent to compiler
Basically, expressions that compiler is unable to eliminate (comparing to expr2) among others due to reference to extern symbols.
Compiler could reason correctness of the assertions with perhaps help of `pure` or `const` keyword attributed to functions invoked in the expression.
These are some ideas.
Regards,
Maciej
Can these kinds(axiom) of conditions still be useful?
Yes. In practice, these kinds of conditions spell out “this is a formal comment.”
And after there is a passage about imaginary tools. I think these tools will never arise and the reason to support my believes is if they could they would already do this. Look, there is already a widely used macro assert and similar almost standards for different frameworks which can be easily detected and parsed. Tools already can do these imaginary checks (and some does but only very limited number of default kinds in terms of contract assert level) but none that I know even try to do these(axiom/audit) checks, so not having contracts is NOT a real obstacle to make these tools.
On the other hand, why would you try to write such an axiom contract in the first place if you can leverage the type system?
struct UnsafeTag{};
template
class Ordered
{
public:
Ordered(R&& orderedRange, UnsafeTag) noexcept
[[expected audit: is_sorted(orderedRange)]]
: _range(std::move(range))
{
}
operator const R&() const noexcept { return _range; }
R move() noexcept { return std::move(_range); }
private:
R _range;
}
template
Ordered sort(R range)
{
…
return Ordered{ std::move(range), UnsafeTag{} };
}
template
bool binary_search(const Ordered& range)
{
…
}
The same idea for reachable, you can use std::span instead of unrelated to each other iters or you can define a more generic range like std::span to cover other containers that simply don’t provide any unsafe operations – those that can produce pair of unreachable iters as a result. Then express std lib functions in terms of these safe abstractions rather than via unrelated pairs of iters.
Ideally, every expectation and ensure should be replaced on such abstractions, however, today there are lots of places where simple expect/ensure is more productive rather than creating such abstraction.
I personally believe that axiom level is a completely ridiculous thing. Instead of giving people a pseudo tool that does nothing but gives a false promise related to imaginary tools and can’t be used other than misuse. I am sure some devs will not fully understand that axiom never checks or set it by a mistake/typo and will rely on such contracts. Another way of misusing axiom is expressing a contradictory condition. It might be very unobvious that a condition may be always false or true regardless of anything. Will the compiler generates a warning about this like it does for unreachable code in case of if constexpr (true) { … return; } ? What if the compiler can’t figure out that condition is contradictory which part of the contradictory expression should I believe?
It would be more productive to provide language tools/std libs that helps leverage type system for such(audit/axiom) use cases. We already have a working way to express axiom contracts – comments and/or doxygen, why do we need yet another way of expressing this?
I assume that the compiler should process a contract condition as any other source code to be wellformed even though it is an axiom. However, I didn’t find the part of the proposal related to this so I may be wrong and compiler may completely ignore the contract condition if it is an axiom level. Compilation of condition is the only difference between an axiom contract and a comment. Does it really matter? Above I have provided misuse case with a contradictory condition and the fact that compiler won’t generate a warning for all such misuses will make people sure that such contradictory contract is fine because it was checked/validated by compiler but makes no sense. With comments, they at least won’t blame the compiler if they specify such a contradictory contract.