News for hackers. Stuff that matters.
Re:Software optimization resources for C++, assembly, Window... by ncmncm on Saturday March 07, 2020 @01:07PM (#22512979)
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.

Re:Software optimization resources for C++, assembly, Window... by a1369209993 on Saturday March 07, 2020 @03:08PM (#22513700)
> [...] 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;
Re:Software optimization resources for C++, assembly, Window... by einpoklum on Saturday March 07, 2020 @04:08PM (#22514068)
GP mis-spoke, s/he meant "O(N) of what?" rather than "N of what?"
Re:Software optimization resources for C++, assembly, Window... by ncmncm on Saturday March 07, 2020 @04:08PM (#22514072)
Errr, right, N counts input, N^2 or whatever should count stalls. I should learn not to post from on the train.
Re:Software optimization resources for C++, assembly, Window... by jfkebwjsbx on Saturday March 07, 2020 @03:11PM (#22513710)
That transformation seems like should always be performed by the compiler unless something very close afterwards depends on the value of i.
Re:Software optimization resources for C++, assembly, Window... by ncmncm on Saturday March 07, 2020 @04:18PM (#22514154)
Branches 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.
Re:Software optimization resources for C++, assembly, Window... by jfkebwjsbx on Saturday March 07, 2020 @05:50PM (#22514809)
Yes, 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.

Re:Software optimization resources for C++, assembly, Window... by ncmncm on Saturday March 07, 2020 @09:40PM (#22515969)
All 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.

Re:Software optimization resources for C++, assembly, Window... by dgellow on Saturday March 07, 2020 @02:31PM (#22513480)
What tools exist to analyze use of pipelines and caches?
Re:Software optimization resources for C++, assembly, Window... by H8crilA on Saturday March 07, 2020 @02:42PM (#22513563)
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.

Re:Software optimization resources for C++, assembly, Window... by flqn on Saturday March 07, 2020 @02:47PM (#22513587)
Cachegrind on linux is part of valgrinds analysers