3 ms·

From my experience the greatest optimization gains can be achieved by introducing more domain knowledge into the code. Heuristics that cut the number of executi

From my experience the greatest optimization gains can be achieved by introducing more domain knowledge into the code. Heuristics that cut the number of executions of some expensive function, shortcuts that introduce good enough approximations, pre-computing and memoizing certain values that are actually constant in the processed data. Things like that. And in programs that had never been optimized it's usually very easy to fire up the profiler and find some obviously terrible things. Like reinitializing in a tight loop some expensive object that can easily be a singleton (or at least a thread local object). I've once spent a month on a decent piece of code and brought down the CPU cost by literally 100x (nobody had optimized the code before). Also, always, first create a reliable framework for measuring progress (cpu instruction retired counters in Intel CPUs are very good and don't need a lot of execution repetitions to bring the p-values low), and only then start optimizing. Low-level, hardcore optimization rarely pays out (not never, but rarely).

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 ago
  What tools exist to analyze use of pipelines and caches?
  - H8crilA 7y ago
    https://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 ago
    Cachegrind 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;
  - einpoklum 7y ago
    GP mis-spoke, s/he meant "O(N) of what?" rather than "N of what?"
  - ncmncm 7y ago
    Errr, right, N counts input, N^2 or whatever should count stalls. I should learn not to post from on the train.
- jfkebwjsbx 7y ago
  That transformation seems like should always be performed by the compiler unless something very close afterwards depends on the value of i.
BubRoss 7y ago
Domain knowledge is great and I think 30 years ago this was much more true. These days I think most software has so many mind melting inefficiencies that there is an avalanche of fat waiting to be shaken loose. Even without nonsense O(n^2) accidentally lurking or huge amounts of time going to granular operations depending on something external that has a large latency, there are still usually gratuitous memory allocations and of course pointer chasing. Taking out allocations from inner loops can easily be a 7x speedup. Taking out pointer chasing, linked lists, virtual pointers etc. and just looping through an array of structs can be another 25x for the areas that use them. From there it's off to SIMD and multi-threading but I don't expect that from most software. Interestingly, none of these rely on programming directly in assembly.
- H8crilA 7y ago
  It is a good point that software has a lot of fat these days, therefore optimization is an easier task (because it's done much more rarely). Windows 98, for however many bugs it had, was so much more responsive.
kitsuac 7y ago
Low level optimization (assembly) is mostly only useful with algorithms which have instruction level parallelism. Modern compilers are incredibly good at optimizing serial algorithms. Making use of compile time branch reduction can be massive. For example template parameters which are evaluated at compile time skipping lots of work at runtime.

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 ago
What tools exist to analyze use of pipelines and caches?
- H8crilA 7y ago
  https://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 ago
  Cachegrind 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;
- einpoklum 7y ago
  GP mis-spoke, s/he meant "O(N) of what?" rather than "N of what?"
- ncmncm 7y ago
  Errr, right, N counts input, N^2 or whatever should count stalls. I should learn not to post from on the train.
jfkebwjsbx 7y ago
That transformation seems like should always be performed by the compiler unless something very close afterwards depends on the value of i.

BubRoss 7y ago

Domain knowledge is great and I think 30 years ago this was much more true. These days I think most software has so many mind melting inefficiencies that there is an avalanche of fat waiting to be shaken loose. Even without nonsense O(n^2) accidentally lurking or huge amounts of time going to granular operations depending on something external that has a large latency, there are still usually gratuitous memory allocations and of course pointer chasing. Taking out allocations from inner loops can easily be a 7x speedup. Taking out pointer chasing, linked lists, virtual pointers etc. and just looping through an array of structs can be another 25x for the areas that use them. From there it's off to SIMD and multi-threading but I don't expect that from most software. Interestingly, none of these rely on programming directly in assembly.

H8crilA 7y ago
It is a good point that software has a lot of fat these days, therefore optimization is an easier task (because it's done much more rarely). Windows 98, for however many bugs it had, was so much more responsive.

kitsuac 7y ago

Low level optimization (assembly) is mostly only useful with algorithms which have instruction level parallelism. Modern compilers are incredibly good at optimizing serial algorithms. Making use of compile time branch reduction can be massive. For example template parameters which are evaluated at compile time skipping lots of work at runtime.