Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Could someone describes the keyword "unlikely" and "likely" in a bit more details? It seem to be a very niche thing to add to the language. Is it expected that those hints will have an impact important enough regarding what the optimizer can do?


likely and unlikely exist in different forms as compiler extensions for a while. There is code where they indeed help compilers to produce slightly better code for the hot path. Good use typically involves lots of measurement as developers are often wrong about the impact and about what the real flow is.

What kind of things can the compiler improve? For instance it can arrange the code in a way that the instructions of the hot path are directly behind each other, whereas the unlikely case jumps further away. Or it can arrange code a bit to help the branch predictor.


gcc and clang (at least, I don't know about msvc) have had these for a while. Basically, the instructions for whichever branch is declared most likely to be taken will be placed immediately after the comparison instruction(s), which is generally more cache-friendly.

It seems conceivable that it might also affect the compiler's inlining choices in each branch (i.e. don't bother to inline as aggressively in the less likely branch, to reduce code size), though I don't know for sure.


Intel and AMD don't hasn't any hinting instructions. Mostly it will affect inlining and well move unlikely code away so the likely path in straight.

But is can already figure that out often especially if it sees exceptions.

Better is to just use the profile guided optimization in the compiler.


A common way to extend a language is to standardize what people are doing in practice. It seems niche, but you have to remember what C++'s niche is. Linux kernel etc use hints like this extensively


I thought the Linux kernel was C and not C++. Has Linus changed his opinion of C++ in all these years?


Features needed/useful for kernel development often get implemented as extensions to gcc and other compilers and then later standardized.


In some niches it is important.

Say you are writing a high speed trading program. At some point you get to the "if(wouldMakeMoneyOnTrade())...". However for every time this passes and you trade there are 1000 where it fails and you don't. However time is critical because your competitors are using similar algorithms and so you need to beat them - thus you put in a likely and ensure that the CPU jumps to the trade code the fastest possible. Your competitors that use Java pay a CPU branch prediction penalty here because the hotspot optimizer has noticed that the if almost always fails and optimized for the false case. Thus you can make money by beating your competitor to the trade. (Note, this doesn't mean you can't use Java for your code, but if you do you need to manage that risk somehow)


If you don't use FPGAs, you probably lost that game anyway.


A stop-the-world GC for HFT doesn't sound like it would work all the well…


Many HFT firms use C# or Java. Quite a few matching engines are written in those languages as well.

The trick is to remember that garbage collection is not some sort of werewolf that wakes up and decides to mess with your stuff whenever it feels like it; it (can) happen only at certain, documented points. So you have to write your code in such a way that it does not do memory allocations in the critical path (which you would not be doing in C++ anyway, for a similar reason; malloc/free is expensive).

Generally if you're doing HFT your critical path is not going to being doing much anyway. A few reads, comparisons, maybe some trivial arithmetic and that should be it.


For what is worth, at least in London, all the HFT firms I have worked with or interviewed for use C++. As I'm a C++ programmer there is bias of course, so my sample is probably not representative. Still I suspect that those that use anything other than C++ are a small minority.



Interesting. From the comment in abseil's implementation:

// Compilers can use the information that a certain branch is not likely to be

// taken (for instance, a CHECK failure) to optimize for the common case in

// the absence of better information (ie. compiling gcc with `-fprofile-arcs`).

//

// Recommendation: Modern CPUs dynamically predict branch execution paths,

// typically with accuracy greater than 97%. As a result, annotating every

// branch in a codebase is likely counterproductive; however, annotating

// specific branches that are both hot and consistently mispredicted is likely

// to yield performance improvements.


Without actually looking at the docs, I would guess these map directly to cpu intrisics that can be used to guide the cpu branch prediction algorithms.


Which cpu instructions guide branch prediction algorithms? Which cpus?


At some point pentium4 had static branch prediction hints, but they are obsolete and no longer relevant.

Today __buitin_expect are mostly used to mark hot/cold branches. The compiler will normally optimize hot code for speed and cold code for size also will attempt to put cold code in separate cachelines and even pages. And other similar code layout optimizations.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: