3 ms·

Running the C equivalent of your first example under cachegrind with --branch-sim=yes, it shows 10,000,000 conditional branches at the if (i % 2 == 0) line, wit

by caf 11y ago

Running the C equivalent of your first example under cachegrind with --branch-sim=yes, it shows 10,000,000 conditional branches at the if (i % 2 == 0) line, with 3 mispredicts.

nkurz 11y ago
Cachegrind simulates caching on a generic CPU, and thus does not tell you how the code will actually run on any particular modern CPU. In this case, the results agree, but I'm of the strong opinion that cachegrind's time has passed. Unless you want a 'theoretical' rather than real answer, you are almost always better off today using the CPUs built in performance counters. That said, I do appreciate that you are offering real numbers rather than guesswork like I am.
- caf 11y ago
  I think that basic branch-sims are still useful as a kind of lowest common denominator - if the simple-minded branch sim can predict it OK, it'll almost certainly go OK on a wide variety of real CPUs. Do you disagree? Benchmarking on a particular CPU does give you more precise results, but at the risk of them being less generally applicable.
  - nkurz 11y ago
    Sure, I think it's fair to say that if cachegrind finds the branching to be predictable, that any modern processor will do fine on it. But if cachegrind predicts poor performance, I wouldn't suggest changing your code unless you've discovered that the actual performance is poor on a real processor. Overall, I think cachegrind's branch prediction is nowadays less accurate than the rule of thumb that "if there is a pattern the CPU will find it". Since using performance counters is so simple and accurate (at least on x86/x64), I'm not sure that there is a benefit to using the slower, less-accurate older method of emulation. You response encouraged me to check whether the branch predictor in cachegrind had been updated since I last looked at it. It doesn't look like it. It's still pretty simple, about 20 lines of actual code: https://github.com/fredericgermain/valgrind/blob/master/cachegrind/cg_branchpred.c https://github.com/fredericgermain/valgrind/blob/master/cach... I greatly appreciated the honesty in one of the comments: "TODO: use predictor written by someone who understands this stuff." It is a valid question might whether the consistency from processor to processor is any better than cachegrind or a rule of thumb. My experience was that for Nehalem/Sandy Bridge/Haswell things were more same than different (and only got better), but I don't know about other lines.
seanmcdirmid 11y ago
Here is a more exhaustive test that throws in a random boolean array (bb) for a total mispredict scenario (always read, sometimes used) First, modulo oscillation: var b = true; for (var i = 0; i < x.Length; i += 1) { var cc = bb[i]; if (b) x[i] = 0; else x[i] = 1; b = !b; } Time: 36 milliseconds (averaged over 10 runs) Case 2, no branch: for (var i = 0; i < x.Length; i += 2) { var c = bb[i]; x[i] = 0; } for (var i = 1; i < x.Length; i += 2) { var c = bb[i]; x[i] = 1; } Time: 22 milliseconds Case 3, coherent branching: var kk = x.Length / 2; for (var i = 0; i < x.Length; i += 1) { var c = bb[i]; if (i < kk) x[i] = 0; else x[i] = 1; } Time: 31 milliseconds Case 4, totally random branching: for (var i = 0; i < x.Length; i += 1) if (bb[i]) x[i] = 0; else x[i] = 1; Time: 75 milliseconds (the slowness could come from bad branch prediction, or the fact that a load needs to complete before the condition can be verified!)
- caf 11y ago
  My point is just to reiterate that the 0,1,0,1,0,1,... pattern of i % 2 == 0 is actually exactly the kind of pattern that branch predictors excel at, which you seemed to be skeptical of.
  - seanmcdirmid 11y ago
    Right, I was wrong. I'm wondering what the use case is for that kind of silicon... interpreters?

by caf 11y ago

Running the C equivalent of your first example under cachegrind with --branch-sim=yes, it shows 10,000,000 conditional branches at the if (i % 2 == 0) line, with 3 mispredicts.

nkurz 11y ago

Cachegrind simulates caching on a generic CPU, and thus does not tell you how the code will actually run on any particular modern CPU. In this case, the results agree, but I'm of the strong opinion that cachegrind's time has passed. Unless you want a 'theoretical' rather than real answer, you are almost always better off today using the CPUs built in performance counters. That said, I do appreciate that you are offering real numbers rather than guesswork like I am.

caf 11y ago
I think that basic branch-sims are still useful as a kind of lowest common denominator - if the simple-minded branch sim can predict it OK, it'll almost certainly go OK on a wide variety of real CPUs. Do you disagree? Benchmarking on a particular CPU does give you more precise results, but at the risk of them being less generally applicable.
- nkurz 11y ago
  Sure, I think it's fair to say that if cachegrind finds the branching to be predictable, that any modern processor will do fine on it. But if cachegrind predicts poor performance, I wouldn't suggest changing your code unless you've discovered that the actual performance is poor on a real processor. Overall, I think cachegrind's branch prediction is nowadays less accurate than the rule of thumb that "if there is a pattern the CPU will find it". Since using performance counters is so simple and accurate (at least on x86/x64), I'm not sure that there is a benefit to using the slower, less-accurate older method of emulation. You response encouraged me to check whether the branch predictor in cachegrind had been updated since I last looked at it. It doesn't look like it. It's still pretty simple, about 20 lines of actual code: https://github.com/fredericgermain/valgrind/blob/master/cachegrind/cg_branchpred.c https://github.com/fredericgermain/valgrind/blob/master/cach... I greatly appreciated the honesty in one of the comments: "TODO: use predictor written by someone who understands this stuff." It is a valid question might whether the consistency from processor to processor is any better than cachegrind or a rule of thumb. My experience was that for Nehalem/Sandy Bridge/Haswell things were more same than different (and only got better), but I don't know about other lines.

seanmcdirmid 11y ago

Here is a more exhaustive test that throws in a random boolean array (bb) for a total mispredict scenario (always read, sometimes used) First, modulo oscillation: var b = true; for (var i = 0; i < x.Length; i += 1) { var cc = bb[i]; if (b) x[i] = 0; else x[i] = 1; b = !b; } Time: 36 milliseconds (averaged over 10 runs) Case 2, no branch: for (var i = 0; i < x.Length; i += 2) { var c = bb[i]; x[i] = 0; } for (var i = 1; i < x.Length; i += 2) { var c = bb[i]; x[i] = 1; } Time: 22 milliseconds Case 3, coherent branching: var kk = x.Length / 2; for (var i = 0; i < x.Length; i += 1) { var c = bb[i]; if (i < kk) x[i] = 0; else x[i] = 1; } Time: 31 milliseconds Case 4, totally random branching: for (var i = 0; i < x.Length; i += 1) if (bb[i]) x[i] = 0; else x[i] = 1; Time: 75 milliseconds (the slowness could come from bad branch prediction, or the fact that a load needs to complete before the condition can be verified!)

caf 11y ago
My point is just to reiterate that the 0,1,0,1,0,1,... pattern of i % 2 == 0 is actually exactly the kind of pattern that branch predictors excel at, which you seemed to be skeptical of.
- seanmcdirmid 11y ago
  Right, I was wrong. I'm wondering what the use case is for that kind of silicon... interpreters?