3 ms·

Completely random from 1-32 -> first order branch predictor determines that the branch is usually taken, and generally predicts it as such. There is likely a se

by brigade 11y ago

Completely random from 1-32 -> first order branch predictor determines that the branch is usually taken, and generally predicts it as such. There is likely a second level predictor that notices that after 16 taken branches it becomes more likely to not be taken, so on average it'll predict loops of length 16. The most relevant buffers are (sizes for Haswell): - 192 µop reorder buffer (ROB) - 42 entry store buffer - 72 entry load buffer So assuming an average length of 16, the processor should issue far enough ahead to keep ~3 outstanding strings being loaded from memory simultaneously (3*16 byte stores = 48, larger than the store buffer.) Then when a branch mispredicts occur, the recovery is quick since the needed cachelines are likely already in L1 (unless the string is longer than average and crosses another cacheline.) If you wanted to speed this up, you could prefetch several (~19) strings ahead in the list. (300 / 16 byte stores at 1 store per cycle = 18.75)

nkurz 11y ago
Thanks! Would this mean that if the strings were a constant length longer than 42 (or possibly longer than the longest predictable loop, which Agner says is "32 or a little more"), that the 42 entry store buffer would be the limiting factor and the next outer load would only be issued after the string begins to be copied? Or is there some limit on the number of outstanding speculative branches kicks in first? Also, can you point to any further documentation on the behavior of the second level predictor? Most things I've seen suggest that it matches only exact patterns, and thus can only predict patterns that happen at least twice in a row. I haven't been able to find anything about averaging.
- brigade 11y ago
  Hm, I assume that if it were longer strings such that the branch is always predicted taken, that yeah it wouldn't speculate to the next string until the mispredict is found, which won't happen until the data gets into registers. If, on the other hand, you had Pascal-style strings with a known length up front instead of null-terminated strings, then the mispredict could be resolved independently of loading every byte of the string, and it could have outstanding loads for two strings simultaneously. But only for strings that span more than one cacheline. The only limit for speculation is the OoOE buffers. I abbreviated it, but the inner loop is a minimum of 5 µops, so you actually end up hitting the ROB limit at 39 iterations before the store buffer is full. Though some architectures could reduce it to 4 with a compare+branch instruction. (x86 fuses this sequence to one µop but I'm not sure if it reduces the ROB entries) If you don't hit the ROB limit, then even after you hit the store buffer limit, the load buffer can take some loads. So assuming 4 µops, 42 stores and 48 loads would be actively buffered while their cache misses are resolved. There's no public documentation on what modern CPUs actually do for branch prediction; that's why I said "likely" - I'm not claiming that any specific CPU does precisely what I described. Just that it's likely to be better than "predict the branch as always taken." The more general "hash pc history as input to branch prediction" is a better way to look at it. How it's hashed and used is a trade secret. Actually, thinking about it again, for truly random data the only prediction improvement over "always taken" is predicting the 32nd consecutive inner branch as not taken. Predicting not taken before that increases the mispredict rate...

by brigade 11y ago

nkurz 11y ago

Thanks! Would this mean that if the strings were a constant length longer than 42 (or possibly longer than the longest predictable loop, which Agner says is "32 or a little more"), that the 42 entry store buffer would be the limiting factor and the next outer load would only be issued after the string begins to be copied? Or is there some limit on the number of outstanding speculative branches kicks in first? Also, can you point to any further documentation on the behavior of the second level predictor? Most things I've seen suggest that it matches only exact patterns, and thus can only predict patterns that happen at least twice in a row. I haven't been able to find anything about averaging.

brigade 11y ago
Hm, I assume that if it were longer strings such that the branch is always predicted taken, that yeah it wouldn't speculate to the next string until the mispredict is found, which won't happen until the data gets into registers. If, on the other hand, you had Pascal-style strings with a known length up front instead of null-terminated strings, then the mispredict could be resolved independently of loading every byte of the string, and it could have outstanding loads for two strings simultaneously. But only for strings that span more than one cacheline. The only limit for speculation is the OoOE buffers. I abbreviated it, but the inner loop is a minimum of 5 µops, so you actually end up hitting the ROB limit at 39 iterations before the store buffer is full. Though some architectures could reduce it to 4 with a compare+branch instruction. (x86 fuses this sequence to one µop but I'm not sure if it reduces the ROB entries) If you don't hit the ROB limit, then even after you hit the store buffer limit, the load buffer can take some loads. So assuming 4 µops, 42 stores and 48 loads would be actively buffered while their cache misses are resolved. There's no public documentation on what modern CPUs actually do for branch prediction; that's why I said "likely" - I'm not claiming that any specific CPU does precisely what I described. Just that it's likely to be better than "predict the branch as always taken." The more general "hash pc history as input to branch prediction" is a better way to look at it. How it's hashed and used is a trade secret. Actually, thinking about it again, for truly random data the only prediction improvement over "always taken" is predicting the 32nd consecutive inner branch as not taken. Predicting not taken before that increases the mispredict rate...