News for hackers. Stuff that matters.
Re:Wc2: Investigates optimizing 'wc', the Unix word count pr... by teo_zero on Friday June 21, 2024 @02:04AM (#40746652)
That's an over-generalization.

Only branches that capture exceptional events, e.g. error checks, show 99% hit rate.

Branches that are part of an algorithm are driven by the data you feed to them. For example in a classical binary search, the prediction is right only 50% of the time.

Re:Wc2: Investigates optimizing 'wc', the Unix word count pr... by ncruces on Friday June 21, 2024 @05:45AM (#40747873)
And any loop that iterates more than 100 times.
Re:Wc2: Investigates optimizing 'wc', the Unix word count pr... by kazinator on Friday June 21, 2024 @09:18AM (#40749307)
But there's an overall loop which branches backward to the same spot, regardless whether the iteration went left or right. At least that's predictable.

If we have an instruction that will conditionally load one of two pointers from memory, the left or right traversal can be made branch-free.

The only reason we need to switch between two code paths in the binary tree descent is that we have two different pieces of code for loading the left or right pointer to the different offsets used in the load instruction.

If we use a two element array for left and right, the indices [0] and [1] select between them. We make the comparison condition calculate a 0 or 1 result and use it as an index.