why when we have a conditional branch we cannot just fetch and prepare instructions for both possible branches and then discard the incorrect one?
is this that much harder or there are other reasons that makes this not worth it
A modern TAGE branch predictor is correct well over 99% of the time. So those extra instructions for the other side of the branch are almost always discarded.
Worse, the frontend is fetching dozens of branches ahead of where the backend can actually confirm which direction to take. What are you going to do at the next branch, start decoding four possible branches? then 8, 16, 32 possible branches? Remember, most of the time you are going to throw it away.
If you actually have the hardware to fetch from multiple instruction streams in parallel (which Intel's Gracemont/Goldmont/Skymont and now AMDs Zen 5 do), the better strategy is to assume your branch predictor is actually correct 100% of the time. Follow one side of the branch, then the one after it.
Intel's Skymont actually decodes the next 3 branch targets in parallel because it has three decoders, each 3-wide. Intel actually introduce fake branches to break up large blocks of code, so that all three decoders are always active decoding different part of the upcoming instruction stream. The three uop streams are later merged, allowing Skymont to maintain an effect decode bandwidth of 9 instructions per cycle.
If you executed both sides of the branch, you are only slightly reducing the branch misspredit delay in the rare case the branch prediction was wrong. Instead, by executing one side the next two or three predictions, Intel and AMD can make multiple decoders do work in parallel. Intel are doing 9-wide with three simpler 3-wide decoders, and AMD can do 8-wide with two simpler 4-wide decoders.
Intel have actually implemented a 6-wide decoder for Golden Cove, but they must really be pushing the limits of propagation delays. So it's attractive to just use two or three smaller decoders in parallel.
> If branches can be used in this way, unconditional jumps (e.g. gotos) and function calls can probably be used for similar purposes.
It's a common misconception that the branch predictor only predicts conditional branches. They need to predict anything that causes control flow to diverge. So unconditional branches, calls, returns, and maybe even syscalls, all count as "branches" and get handled by the branch predictor.
(On most RISC instruction sets, these instruction are often labeled branch. Call is just "Branch And Link" which saves the return address in a register. To return, you just use the "Branch to Register" instruction)
This is necessary because the frontend is pipelined. It takes a minimum of four cycles to fetch the instruction data from instruction cache and decode it before the frontend can even know there is a call, return or unconditional branch instruction. If we are decoding four instruction per cycle, we are already 16 instructions past the branch before we even know it's there, and it's common to have a branch every 3-4 instructions.
Basically, the frontend is blind and can't see any branches.
Predicting the direction of conditional branches is almost a secondary task for modern branch predictors. It's much more important to predict where the branches are and their destination, so that instruction fetch stage can request the correct data from the instruction cache and keep the pipeline fed.
I think a lot of people don't have an intuition about how accurate branch prediction can be, but if you look at your own code, you'll quickly realize "well, yeah, control flow is almost always going to go this way and we just have this branch so we can handle the exceptional case" -- compilers can often deduce this pretty well themselves now, and cpus/jits/runtimes can develop some pretty impressive heuristics as well, and when all those fail you can often add explicit hints in your code that tell your compiler/etc what you expect if they can't guess.
How rare, though?
QuickSort has fundamentally unpredictable branches, and it’s a pretty widely used algorithm. Binary search, B-trees also come to mind.
It's also definitely going to depend on the cost of the hash function and comparison function - for something like strings, where those can be quite expensive, binary search probably has a better chance of applicability than for guid's say.
As far as I can tell, branch predictors have always been too good for it to be worth it. Moderns CPUs have instruction reorder buffers that are hundreds of instructions deep, so even if only 8 of those instructions are conditional jumps, there's 256 different paths your program could take. If your branch predictor predicts all 8 correctly >50% of the time (It does), doing 256x the work to cover your ass is not worth it.
It requires more silicon to hold more microarchitectural state and more execution units to fully exploit the technique, but superscalar CPUs already have those since they are essential to exploit instruction level parallelism in non-branchy code. The rest is "just" a lot of headaches to handle complicated stuff such as aliasing, interrupts, ... But hardware engineers are such wizards they can do these things too.
Turns out however that speculative execution opens up a possibility of abusing a cache timing side channel to extract information from data touched by branches of code that has been only speculatively executed but whose architectural side effects were not committed (i.e. not "really" executed).
Which includes code that had been explicitly not executed because of a conditional check (e.g. permissions, ...)
A familiar instance of such an attack is Spectre [1]
1: https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...
So basically it’s just nowhere near worth it. Much better to use those chip resources for another thread or core.
You could potentially do it only for predicted "unpredictable" branches. Now the tradeoff is wasted power and execution units for dead work and so far the tradeoff was just not worth it.
Some form of this has been experimented with. In the late '90 SPRC experimented with scouting threads and as mentioned else thread the Efficient Intel cores can fetch (but not execute) across branches.
- Double the execution units; very expensive for wide vector units
- Massive waste of energy as half the resources will always be wasted no matter what
- Bad scaling, i.e. four branches ahead would require 16x the resources
Doubling the execution units also isn't strictly needed - you can use the existing out-of-order core to send two sets of instructions through the same functional units. There will be more contention for the resources, possibly causing stalls, but you don't need to fully double everything.
Things similar to this idea are already done in processors - simultaneous multithreading, early branch resolution, conditional instructions, are all ideas that have similar implementation difficulties. So the reason this specific idea is not done is more in line with your last two points rather than the first two.
I say the SMT core would be reduced by one since, rather than being used as an SMT core, it would be used as the second branch prediction thing.
We actually do that. It's called a GPU. And it sucks for general code.