Mill Computing, Inc. Forums The Mill Architecture Grab bag of questions Reply To: Grab bag of questions

Post count: 23

The cause of the exit transfer doesn’t matter for prediction, with the exception of returns. Most ebbs (hyperblocks) have several conditional ways to exit, one of which is taken; the predictor says where the taken one will go, in which cycle, and the kind of transfer (call/return/branch). The prediction itself doesn’t care whether it was something dynamic.

I’m not sure we understand each other here.

Say you have a loop iterating over a list of dynamic objects (say, widgets):

for (i in 0…this.child_widgets.size()) {

Given the same EBB (the loop body), each entry might have a different exit. So for each loop iteration, the predictor would be given the same EBB address, and need to predict a different exit address (the paint call of the given vtable).

I guess history prediction, agree prediction, etc would help. If your widget list is [Button, Label, Checkbox, Button, Label, CheckBox, Button, ...], the predictor can probably guess “If you got into this EBB by returning from Button::paint then the exit is probably Label::paint” from history. I’m not sure how much that helps? If you have a lot of method calls on heterogeneous object lists, and/or if you have lists that change regularly, wouldn’t that saturate the predictor? On the other hand, modern predictors are pretty big (around 4096 entries according to a cloudflare article I found).

Anyway, my point was, given the example code above, the compiler has enough information to predict every call to the paint method hundreds of cycles in advance of it happening. Say each paint call takes about 100 cycles on average, and the compiler knows that. The compiler could insert prefetch calls to tell the CPU “prefetch the vtable entry for child_widgets[i + 3]” and mask the DRAM load latency. Then “predict that next time this EBB is entered, its exit will be child_widgets[i + 1].paint()” and avoid the mispredict even if the history has not caught up yet.

Of course, I don’t know how useful any of this would be in practice. From what I know of the subject, likely-style hints aren’t used by the compiler because branch predictors actually outperform compiler hints, to the point that the hints are a hindrance more than anything else. But I don’t know how much this is accidental vs fundamental to the prediction problem.