Some back of the envelope math:

- there is a branch instruction every 10 instructions or so

- if you can't predict, assume you guess wrong half of the time

So every 20 instructions or so, you take the wrong branch. Sounds like it could be a significant overhead, from 10% - 50% depending on what the code inside the loop is doing.

For instance, if your code is doing only arithmetic operations, no load/store, such as computing factorial or other silly integer math, 20 instructions would probably take 20 cycles or less to execute, but the branch failure would cause a similar delay. So that's 50% overhead. In the other case, assume the 20 instructions are fairly slow (lots of memory accesses), then your branch penalty won't feel so bad.