I came across a post on branch prediction (Why is it faster to process a sorted array than an unsorted array?) and it got me thinking about my own Monte Carlo simulations. For the sake of specificity, let's say we are working in C and writing for CPUs. (Does that matter?) Suppose you have a loop that goes something like this:
while ( condition ) {
// dE will be stochastic...
dE = MonteCarloMove();
// ...and d is a random number between 0 and 1
d = RandomRealNumber(0,1);
w = exp(-dE);
if ( dE < 0 || d < w ) {
AcceptMonteCarloMove();
}
else {
RejectMonteCarloMove();
}
}
It seems to me that branch prediction at the if..else
statement is completely useless, since it is random which way we go. In a properly designed Monte Carlo simulation, you'll have roughly as many accepts as rejections. So here are my questions:
- Is there any technique one could use to avoid the branching slowdown in a random process like this?
- If so, is it likely to provide any significant speed-up, considering that
MonteCarloMove()
probably involves some expensive numerical calculations?
Update: In case this general question is unanswerable, or the answer is generally no, suppose we can make some assumptions about the functions inside the if
statement:
AcceptMonteCarloMove()
is a function that updates the current state of the simulation. All it likely needs to do is- Copy values from one variable to another;
- Perform simple arithmetic (addition/subtraction).
RejectMonteCarloMove()
needs to reset the current state and possibly some bookkeeping variables. Likely it only needs to- Copy values from one variable to another.