OSDev.org

Brendan wrote:Your example is so trivial that it's entirely idiotic and pointless

Brendan wrote:

Code: Select all

void foo(void) {
    int c;
    int x = 0;

    while( (c = getc()) != EOF) {
        switch(c) {
        case 'a':
            x /= 3;
            break;
        case '4':
            x += 4;
            break;
        case 'q':
            exit(0);
        default:
            x++;
            break;
        }
        if(x%7 == 0) {
            printf("Bork!\n");
        }
    }
}

Questions:

• How often will the "if(x%6 == 0)" branch be predicted correctly by a traditional "ahead of time" compiler?
• How often will the "if(x%6 == 0)" branch be predicted correctly by a modern CPU's branch predictors?
• How often will the "if(x%6 == 0)" branch be predicted correctly by a modern "just in time" compiler?
• For a "just in time" compiler, would the overhead of attempting to correctly predict the "if(x%6 == 0)" branch cost far more than a misprediction would have?
• What about the "switch/case" branches?

Rusky wrote:Only the CPU knows exactly which addresses are being loaded at a given moment.

Rusky wrote:There's absolutely no reason to make this an all-or-nothing contest- the best outcome is often when the CPU and compiler cooperate

You know what? Show us the code a compiler would output if it did branch prediction itself. Give us an example that's better than the CPU doing it.

(...)
for (int i = 0; i < 50; i++)
{
    (do stuff)
}
(...)

(...)
CLR r1
.loop:
CMP r1, 50-1
MOV r2, .endloop
(add n-2 parallel ops here)
MOVNBE r2, .loop
(add n-1 parallel ops here)

(do parts of stuff)

DJMP r2 ; fetching starts now
(do last few instructions of stuff to fill delay slot)
INC r1
.endloop: 
; jump will have taken effect here.
(...)

Rusky wrote:What other algorithm are you possibly going to use for detecting aliasing stores?

Combuster wrote:

You know what? Show us the code a compiler would output if it did branch prediction itself. Give us an example that's better than the CPU doing it.

Code: Select all

(...)
for (int i = 0; i < 50; i++)
{
    (do stuff)
}
(...)

Code: Select all

(...)
CLR r1
.loop:
CMP r1, 50-1
MOV r2, .endloop
(add n-2 parallel ops here)
MOVNBE r2, .loop
(add n-1 parallel ops here)

(do parts of stuff)

DJMP r2 ; fetching starts now
(do last few instructions of stuff to fill delay slot)
INC r1
.endloop: 
; jump will have taken effect here.
(...)

Owen wrote:BETTER. Trivial loop exit conditions are uninteresting and, well, trivial. Intel have been correctly predicting them for 15 years.

In fact your code is worse, because it wastes two registers and two instructions per cycle.

Now that we've got enough background, let's take a look at Intel's own description of the loop detector:

The Loop Detector analyzes branches to see if they have loop behavior. Loop behavior is defined as moving in one direction (taken or not-taken) a fixed number of times interspersed with a single movement in the opposite direction. When such a branch is detected, a set of counters are allocated in the predictor such that the behavior of the program can be predicted completely accurately for larger iteration counts than typically captured by global or local history predictors.

Combuster wrote:Because zero mispredictions are better than occasional mispredictions?

Combuster wrote:Bottom line: there's no such thing as the CPU being superior to the compiler.