3 ms·

I'm not sure if the methodology is sound. Let's say you want to measure if code is faster with branch or cmove, so you make a microbenchmark. In that case the

by fefe23 4y ago

I'm not sure if the methodology is sound. Let's say you want to measure if code is faster with branch or cmove, so you make a microbenchmark. In that case the branch predictor has little other branches to keep track of, so it definitely has enough resources to predict that branch well. In a real world program that function may only be called once in a while and the branch predictor may consider other branches more important. I wonder if cmove has advantages even if your microbenchmark tells you it doesn't. One side effect would probably be that it takes pressure off of the branch predictor, which we have no good way of measuring in microbenchmarks.

viraptor 4y ago
I think that still makes sense. If you use that branch rarely enough that another one takes its place in the predictor, then it's likely not important enough to matter in the grand scheme of things. Cmov -vs- branch will be most important in stream processing / tight loop. When it's "once in a while" then who cares?
- terrelln 4y ago
  It can still matter. You can have a common function that is inlined everywhere that takes a ton of CPU in aggregate, but each callsite is small. E.g Map::find().
eklitzke 4y ago
Your point about branch prediction working better in a microbenchmark than in real code is true in some scenarios. But it's also the case that if the code is called infrequently enough in the real program that it doesn't get good branch prediction it may not be worth optimizing, since that may mean it's not actually on a hot path. There are also plenty of examples of microbenchmarks you can write for this type of code that don't suffer from the problem of artificially high branch prediction. An example used in this article is a function called downHeap which is presumably used as part of heap sort. Searching and sorting are good examples of algorithms that often don't do well with branch prediction. As a simple example, if you're doing a binary search for a random element in a sorted vector you'll expect half the branches to go one way (left of the pivot for the iteration) and half the branches to go the other way (right of the pivot for the iteration) without a predictable pattern, even in a microbenchmark.

by fefe23 4y ago

viraptor 4y ago

I think that still makes sense. If you use that branch rarely enough that another one takes its place in the predictor, then it's likely not important enough to matter in the grand scheme of things. Cmov -vs- branch will be most important in stream processing / tight loop. When it's "once in a while" then who cares?

terrelln 4y ago
It can still matter. You can have a common function that is inlined everywhere that takes a ton of CPU in aggregate, but each callsite is small. E.g Map::find().

eklitzke 4y ago

Your point about branch prediction working better in a microbenchmark than in real code is true in some scenarios. But it's also the case that if the code is called infrequently enough in the real program that it doesn't get good branch prediction it may not be worth optimizing, since that may mean it's not actually on a hot path. There are also plenty of examples of microbenchmarks you can write for this type of code that don't suffer from the problem of artificially high branch prediction. An example used in this article is a function called downHeap which is presumably used as part of heap sort. Searching and sorting are good examples of algorithms that often don't do well with branch prediction. As a simple example, if you're doing a binary search for a random element in a sorted vector you'll expect half the branches to go one way (left of the pivot for the iteration) and half the branches to go the other way (right of the pivot for the iteration) without a predictable pattern, even in a microbenchmark.