Menu
I have a loop that is running over and over again. The logic inside that loop is dependent on the mode that the program is in. To improve performance I was thinking that an array of function pointers can be initialized, functionPtr[], so that would just call functionPtrmode that runs the right logic. The loop will stay in the same mode for many cycles (the number is unknown upfront but many thousands). The program runs on an intel x64 machine only and needs no portability.
I was hoping that the CPU would utilize branch prediction but since my branch isn't conditional (on the assembly level) but the location of the branch does depend on a variable, (functionPtr+mode). Will the CPU attempt to calculate functionPtr+mode and start pulling those instructions in while in the pipeline?
836
Branch prediction breaks instructions down into predicates, similar to predicate logic. A CPU using branch prediction only executes statements if a predicate is true. One example is using conditional logic. Since unnecessary code is not executed, the processor can work much more efficiently.
The branch predictor operates in the Fetch stage of the pipeline so that it can determine which instruction to execute on the next cycle. When it predicts that the branch should be taken, the processor fetches the next instruction from the branch destination stored in the branch target buffer.
This is done in a special part of the processor called the branch predictor unit (BPU). The branch predictor attempts to figure out a destination of a branching instruction very early and with very little context. This magic happens before the "decoder" pipeline stage and the predictor has very limited data available.
The branch prediction is based on the previous iterations on the same instruction. If the branches follow a regular pattern, the prediction are successful. The best cases are those in which a branch instruction has always the same effect; in such cases, the prediction is almost always correct.
From The microarchitecture of Intel, AMD and VIA CPUs An optimization guide for assembly programmers and compiler makers
http://www.agner.org/optimize/microarchitecture.pdf
section 3.7 (for Sandy Bridge, other processors are in other sections) Pattern recognition for indirect jumps and calls Indirect jumps and indirect calls (but not returns) are predicted using the same two-level predictor as branch instructions.
A pointer to a function is an indirect call.
152
Yes, reasonably recent processors can do (at least something like) branch prediction for indirect jumps.
From the Pentium (Intel's first to do branch prediction) through the first Pentium IV's, all that was used for indirect branches was the Branch Target Buffer (BTB). This meant that they "predicted" such branches correctly when (and only when) the target was exactly identical to the previous target--which sounds like it's adequate for your case.
Starting with the Pentium M/Prescott (the last Pentium IV) Intel improved branch prediction for indirect jumps to use a two-level adaptive predictor. If I'm understanding your question correctly (i.e., your loop will execute with the same target for many consecutive iterations, and those are what you care about) even just the BTB would be sufficient for your purposes. The two level predictor would become more useful if (for example) you were branching on the least significant bit of consecutive numbers, so you had a predictable pattern of jumping to one target in one iteration, and the other in the next iteration. With a pattern like this, the BTB alone would always predict the branch incorrectly, but the two-level predictor in a current processor would predict correctly (after the first couple of iterations, so the pattern could be detected).
28
Branch Prediction is for actual branches where we do not know until evaluation of branch, which tells which of the instruction is to be executed next. But since in your code next instruction is known depending on mode we are in, there is no need of any prediction neither will their be any wait in pipeline.
Given that there is enough time between mode change and instruction options, pipeline will successfully fetch the right instruction every time without any extra effort.
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
