Hint for branch prediction in assertions

Question

I have a custom ASSERT(...) macro which I use in a C++ application.

#include <stdlib.h>
#include <iostream>

/// ASSERT(expr) checks if expr is true.  If not, error details are logged
/// and the process is exited with a non-zero code.
#ifdef INCLUDE_ASSERTIONS
#define ASSERT(expr)                                                      \
    if (!(expr)) {                                                        \
        char buf[4096];                                                   \
        snprintf (buf, 4096, "Assertion failed in \"%s\", line %d\n%s\n", \
                 __FILE__, __LINE__, #expr);                              \
        std::cerr << buf;                                                 \
        ::abort();                                                        \
    }                                                                     \
    else // This 'else' exists to catch the user's following semicolon
#else
#define ASSERT(expr)
#endif

Recently I was reading some Linux kernel module code and came across the existence of likely(...) and unlikely(...) macros. These provide a hint to the CPU that a given branch is more likely, and that the pipeline should optimise for that path.

Assertions are, by definition, expected to evaluate to true (i.e. likely).

Can I provide a similar hint in my ASSERT macro? What's the underlying mechanism here?

Obviously I will measure for any difference in performance, but in theory should it make any difference?

I only run my code on Linux, but would be interested to know if there's a cross platform way of doing this too. I'm also using gcc, but would like to support clang as well.

Dichromic

Anything wrong with assert from <cassert>? – Emmuela

Unless you're going to be putting ASSERTs inside performance-critical loops then it really isn't going to make any difference. Also branch prediction is pretty good for consistent branches such as this these days, so even in a performance-critical loop it shouldn't make much difference on a modern CPU. – Heal

@Mat, the rationale was primarily to allow including asserts in Release and RelWithDebInfo builds. It's controlled via INCLUDE_ASSERTIONS which is independent of the build type. – Dichromic

Unless your assertions are on a hot path I doubt you'll notice any difference, and even then I doubt the difference will be significant. Also, what is your question exactly? Can I provide a similar hint in my ASSERT macro? Yes, you can of course use likely and unlikely if you so wish. – Actinia

Side note: you don't need that else. Empty statements are perfectly acceptable in C, and don't change the meaning of the code at all. if (foo) {}; is no different from if (foo) {}. – Hispid

@BlacklightShining: Without else, the macro could gobble up a following else: if (x) ASSERT(y) else z(); -- with the current version, this gives an error (good!) but if you omit the else in the macro definition, the else z() will attach inside the expansion of the ASSERT macro (bad!). Of course, this is why we use do { ... } while(0) in macros. – Bathsheeb

Optimizing your ASSERT is a low hanging fruit. Makes sense to get it right and move on. – Charlinecharlock

"else // This 'else' exists to catch the user's following semicolon" - the usual way to do that is to wrap the body of the macro in a do { /* ... macro body here ... */ } while (false) block. – Downdraft

Answer 1

The performance gain is not likely to be significant, but this is how those linux kernel macros are defined:

#define likely(x)      __builtin_expect(!!(x), 1)
#define unlikely(x)    __builtin_expect(!!(x), 0)

So, you could modify your condition like this (assuming that expr is expected to be true and therefore !(expr) is expected to be false):

if (__builtin_expect(!(expr), 0)) {

Or you could define the same macros as the kernel and use them for better readability.

This is gcc builtin, so not portable of course.

This suggests that clang also supports the builtin. Othrwise, you can use the above macros and conditionally define them like #define likely(x) (x) on compilers that don't support the builtin.

In your case, the prediction is going to be good (either that or you're aborting), so there shouldn't be a risk of pessimisation, but if you do consider using the builtin more widely, here's a word of advice from gcc documentation:

In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform.

Blather

gcc also have -fprofile-generate flag to instrument program with branch profiling, then run program to generate profiling data, and re-compile with -fprofile-use. It will automatically set expect-like predictions. – Chrysarobin

@keltar, good point. I added a quote from the documentation which also suggests profile feedback. – Blather

likely is rather pointless, because when the brain/assert hits it looses many many many cycles – Unimposing

Answer 2

For many CPUs, likely and unlikely (or anything else for that matter) don't provide a branch hint to the CPU (only to the compiler, which may use it to optimize differently, similar to profile guided optimization) for the simple reason that there is no way to do it.

For example, branch hints are defined for x86 since P4. Before that they had no effect, but it's even worse, they have no effect on anything between P4 and Redwood Cove. So they're useless on many processors (but waste space and bandwidth), and as far as I know GCC does not emit them. These prefixes did nothing for a long time, but Intel is reportedly bringing them back in Redwood Cove,

Starting with the Redwood Cove microarchitecture, if the predictor has no stored information about a branch, the branch has the Intel® SSE2 branch taken hint (i.e., instruction prefix 3EH)
...
The microarchitecture is obliged to decode the Intel® SSE2 branch not-taken hint (i.e., instruction prefix 2EH), but otherwise ignores it.

• There’s no need to hint that a branch is not-taken since, by default, it’s predicted not-taken if the predictor doesn’t have stored information about it.

(from: Intel® 64 and IA-32 Architectures Optimization Reference Manual: Volume 1)

ARM doesn't (yet?) have branch hints either. PPC, IA64 and SPARC do have hinted branches, I don't know whether GCC uses likely and unlikely for them though, but at least it could.

Ferdelance

+1 for pointing out that instruction bandwidth is important, even when we live in a world full of cpu's with fancy multiple dispatching stuff from 16 bytes lines...i guess few know that :) – Unimposing

I'm almost sure expect is more like hint to compiler to rearrange instructions to [possibly] reduce conditional jumps; it could have performance gains even without actual designated hinting instructions. But effect may be reduced by CPU's own hardware branch prediction. – Chrysarobin

This isn't entirely correct. When the branch predictor has no collected statistics, it still must do some prediction. And the default prediction made (at least on Intels) is that backward jumps are taken (loops) and forward jumps aren't taken (if's). By reordering the code compilers implicitly provide those hints. – Rooks

@ybungalobill not necessarily, Core2 just uses whatever junk happens to be in the predictor whether it actually relates to the branch or not. So the hint doesn't work then. But it doesn't even count anyway. Relying on a default is specifically the absence of a hint. – Ferdelance

@harold: Don't know about Core2. But I cannot make sense of your last sentence. Nobody defined a 'hint' to necessarily be an opcode prefix. Nobody said that likely/unlikely must emit such prefixes. Code layout that takes advantage of the documented assumptions made by the processor is just as a valid hint as anything else. The likely/unlikely as well as PGO cause the compiler to reorder code to match those assumptions. In the end your likely/unlikely end up being implicit hints to the processors supporting this protocol. – Rooks

@ybungalobill not necessarily a prefix, obviously. An implicit hint is an oxymoron. Not telling the CPU anything is not a hint, it's nothing. Literally nothing. It's as much of a hint as stacking small things atop big things is a hint to physics to not make the pile fall over. Not a hint - just using existing behaviour. – Ferdelance

Answer 3

There is no need for any additional annotation. The compiler already knows about abort being called very rarely (at most once per program execution), and so the compiler will consider the branch containing abort as the unlikely branch anyway. You can verify this by looking at the declaration of abort. In glibc it is declared as

extern void abort (void) __THROW __attribute__ ((__noreturn__));

and in Visual Studio 2013:

_CRTIMP __declspec(noreturn) void __cdecl abort(void);

Gametophyte

Do you have a reference for this claim regarding the compiler's knowledge of abort? – Wivina

@CodyGray I added some references. – Gametophyte

noreturn means that it does not return by the regular means. Such function can still be called multiple times and even frequently but return by other means, like longjmp. – Rooks