3 ms·
My experience differs. Domain-specific optimizations do often yield order-of-magnitude improvements, but once those opportunities have been exploited, there is
by ncmncm 7y ago
My experience differs.
Domain-specific optimizations do often yield order-of-magnitude improvements, but once those opportunities have been exploited, there is very often another factor of two or ten remaining.
For example, a three-line change to quicksort, not changing the algorithm at all, more than doubles its speed.
The key insight not taught is that the familiar order notation -- O(N), O(N^2) -- does not dictate what N must count. Traditionally, it counts comparisons, swaps, or other algorithmic events. Nowadays, these operations are practically free, and what matters are cache misses and pipeline stalls.
Because each miss is so devastating, it is essential to keep plenty of work in the pipeline. Interfaces should provide batched operations, because often it takes no more time to, say, produce four hashes than one.
Measurement is necessary, but since it is so hard to know whether a thing is fast, reading out the hardware performance counters is essential. How many pipeline stalls, how many cache misses, how many branch mispredictions?
Transforming "if (c) ++i;" to "i += c;" can make a huge difference, in an inner loop, when c is unpredictable. Similarly, "if (c) a -= b;" may become "a -= (-c & b);". Compilers usually will not make these transformations because they guess that c is predictable. When it isn't, you get a pipeline stall every other iteration, with 10-15 cycles down the drain each time, enough for ~40-60 useful instructions.
- dgellow 7y agoWhat tools exist to analyze use of pipelines and caches?
- H8crilA 7y agohttps://en.m.wikipedia.org/wiki/Perf_(Linux) https://en.m.wikipedia.org/wiki/Perf_(Linux) It is all powered by hardware support in CPUs. Intel CPUs have 3 programmable counters, you can set them to trace events, like instructions retired or Ln cache misses.
- flqn 7y agoCachegrind on linux is part of valgrinds analysers
- a1369209993 7y ago> [...] what N must count. Traditionally, it counts comparisons, swaps, or other algorithmic events. Er, N is counting the input elements (eg number of nodes in a graph, array length, etc), O() is what counts algorithmic or microarchitectural events. > Similarly, "if (c) a -= b;" may become "a -= (-c & b);". Reminds me of speeding up a ECC loop by almost two orders of magnitude with (basically): - if(i&(1<<k)) p ^= parity(x[i])<<k; + p32[k] ^= x[i] & -(ii&1); ii>>=1;
- jfkebwjsbx 7y agoThat transformation seems like should always be performed by the compiler unless something very close afterwards depends on the value of i.
- ncmncm 7y agoBranches break dependency chains. So, correctly predicted branches enable more instruction-scheduling parallelism, essentially running multiple loop iterations in parallel. So, reasoning about this is very uncertain. You have to measure both ways and see.
- jfkebwjsbx 7y agoYes, that is why I say it should not be done if something is very close that depends on i. But in many algorithms and in a lot of user loops you don't need data from previous iterations; or if you do, they may be far enough eg. if you are running something complex in each iteration. So you have to be in the case where you are implementing a 1) non-trivial loop that is 2) small enough and in which 3) branches can be predicted. It indeed happens, but I bet most code is not like that. (I have no clue though). We also have to remember that every added branch may be destroying performance for some other branch out there (and this is way harder to know unless you measure your particular program). That is why I feel removing the branch is almost always a good idea unless proven otherwise; rather than the other way around.
- ncmncm 7y agoAll very true. The partition used in quicksort has a textbook example of a result--the possibly swapped elements--not used in the next iteration. (The conditional increment is used immediately, though.) But replacing the innards of partition's loop with bool c = *left <= pivot T v[2] = { std::move(*left), std::move(*right) }; *right = std::move(v[1-c]), *left = std::move(v[c]); left += c; almost doubles the speed. Persuade the compiler to substitute cmov instructions, and you get more than double. Gcc cannot be persuaded, under any circumstances, to put more than one cmov in a basic block. Clang can be persuaded, with a bit of subterfuge: *right = (v[0] & -c) | (v[1] & c-1); *left = (v[1] & -c) | (v[0] & c-1); or (less fun) with ?: expressions. Probably the optimizers should recognize the array index trick, which is formally correct for all types. Pressure on the cache of predicted branches is hard to quantify. They don't tell us how many branch prediction slots we get. But you definitely can blow that cache. We don't know what all dodgy gimcracks are in modern CPU cores. I do know that loops with FILE getc/putc and streambuf sgetc/sputc are faster than they have any business being. If you can get your loops to look enough like those, they will be improbably faster.