Function Pointers and Branch Prediction
Author
Hey guys,
I've been researching the impact function pointers have on branch prediction, but can't seam to find too much concrete information. My question is: If I have a function pointer, pointing across a DLL boundary, which never changes after it is set, how will this affect dynamic branch prediction? By my understanding, once the branch history is established, the CPU should be able to successfully predict the branch always, and if the pointer were to change, there would be at most 2 branch miss predictions, and then the history would be corrected. However, is that correct? And does the fact that the pointer points across to DLL code matter?
I've been using 'Structured Computer Organization" as a reference on this, But if you know any good books or articles on writing highly efficient C++ as well as coping with things like branching and caching, a recommendation would be much appreciated.
A depends on the CPU. To each their own for how they handle branches and instruction cache.
Besides a function pointer incurs not only a instruction stall posibility, but a data stall. It has to read the pointer in from memory (rather read in the structure holding the pointer, then read the pointer). And unless you can assure the compiler (through some intrinsic) that the pointer is not aliased and will not change, then it will read it in fresh every time. Meaning there is still a lot of overhead.
On an x86 you are likely to have good prediction of the branch (more sophisticated caching of what particular branch instruction corresponds to what to predict). On other processors (read consoles/embeded) there are often a lot of sacrifices made. For instance, the PS3 cell SPU has no branch predictor, only "branch assume true" and "branch assume false" instructions that have to be manually chosen by the programmer or compiler. Other consoles tend to have very bad icache performance (read it doesn't predict where the dynamic branch goes to).
Now, that doesn't mean avoid entierly virtual functions and function pointers. But it should read as, don't use function pointers in tight loops of code, or any place where a regular function could be used.
Random google provides more info
Besides a function pointer incurs not only a instruction stall posibility, but a data stall. It has to read the pointer in from memory (rather read in the structure holding the pointer, then read the pointer). And unless you can assure the compiler (through some intrinsic) that the pointer is not aliased and will not change, then it will read it in fresh every time. Meaning there is still a lot of overhead.
On an x86 you are likely to have good prediction of the branch (more sophisticated caching of what particular branch instruction corresponds to what to predict). On other processors (read consoles/embeded) there are often a lot of sacrifices made. For instance, the PS3 cell SPU has no branch predictor, only "branch assume true" and "branch assume false" instructions that have to be manually chosen by the programmer or compiler. Other consoles tend to have very bad icache performance (read it doesn't predict where the dynamic branch goes to).
Now, that doesn't mean avoid entierly virtual functions and function pointers. But it should read as, don't use function pointers in tight loops of code, or any place where a regular function could be used.
Random google provides more info
If you're extremely concerned about the call performance, you could dynamically replace the operand of the CALL instruction with the address at runtime (assuming you put a compatible instruction placeholder in that location). Finding the instruction address would be difficult in standard C/C++ code though. Inline assembly might make it easier but I haven't personally tried it.
Different processors and operating systems would also have other things you'd need to do. For example in Windows on x86/x64 you would need to call VirtualProtect to give yourself write access to the code. On x64, you'd need to be aware of RIP-relative addressing.
It works, but this isn't a common approach. I would only use this if it's your last possible choice.
[Edited by - Nypyren on June 24, 2009 2:40:42 AM]
Different processors and operating systems would also have other things you'd need to do. For example in Windows on x86/x64 you would need to call VirtualProtect to give yourself write access to the code. On x64, you'd need to be aware of RIP-relative addressing.
It works, but this isn't a common approach. I would only use this if it's your last possible choice.
[Edited by - Nypyren on June 24, 2009 2:40:42 AM]
Function pointer branches aren't predicted like normal branches because they're (usually) not conditional; the only thing that needs to be resolved is the target.
For that CPUs use branch target prediction to store the target of some number of indirect branches in a branch target buffer. This type of prediction doesn't suffer from aliasing, the BTB is direct mapped. Unless you have a lot of function pointers or C++ virtual calls a few indirect branches should stay in the BTB, but it depends on the size of the BTB, if it's cleared on context switches, etc.
For that CPUs use branch target prediction to store the target of some number of indirect branches in a branch target buffer. This type of prediction doesn't suffer from aliasing, the BTB is direct mapped. Unless you have a lot of function pointers or C++ virtual calls a few indirect branches should stay in the BTB, but it depends on the size of the BTB, if it's cleared on context switches, etc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement