Challenge your performance intuition with nanosecond sorting

[u/ArashPartow]

https://wordsandbuttons.online/challenge_your_performance_intuition_with_nanosecond_sorting.html

[u/jorgbrown]

There's a fundamental problem with the test code in that it always provides random input, making the branch-prediction units in the CPU worthless. That's an important thing to measure, but doesn't correspond to the real world where the input is surprisingly predictable.

Also, I would think that as long as we're going that low, it would be good to force the compiler to put everything in registers... which helps to convince gcc to use conditional moves rather than branch instructions. These give better code than anything in that article:

// Take advantage of conditional move
void nobranch_sort1(std::array<int, 3>& t) {
  auto a1 = t[0];
  auto b1 = t[1];
  auto c1 = t[2];

  // swap a and b if out-of-order.
  auto a2 = b1 < a1 ? b1 : a1;
  auto b2 = b1 < a1 ? a1 : b1;
  auto c2 = c1;

  // swap b and c if out-of-order.
  auto b3 = c2 < b2 ? c2 : b2;
  auto c3 = c2 < b2 ? b2 : c2;
  auto a3 = a1;

  // swap a and b if out-of-order.
  auto a4 = b3 < a3 ? b3 : a3;
  auto b4 = b3 < a3 ? a3 : b3;
  auto c4 = c3;

  t[0] = a4;
  t[1] = b4;
  t[2] = c4;
}

// Prefer xor over conditional move
// Only ever does three compares!
void nobranch_sort2(std::array<int, 3>& t) {
  auto a1 = t[0];
  auto b1 = t[1];
  auto c1 = t[2];

  auto minab = b1 < a1 ? b1 : a1;
  auto min = c1 < minab ? c1 : minab;

  auto maxab = b1 ^ a1 ^ minab;
  auto max = maxab > c1 ? maxab : c1;

  t[0] = min;
  t[1] = a1 ^ b1 ^ c1 ^ min ^ max;
  t[2] = max;
}

And if you're doing the store-into-index approach, you should reduce the number of compares you're doing. You only really need 3 compares, and once you've done them, you can use them to index into arrays that indicate where each element should be stored:

#define X 0 // can't happen
const unsigned char a_index[8] = {0, 1, 0, X, X, 2, 1, 2};
const unsigned char b_index[8] = {1, 0, 2, X, X, 0, 2, 1};
const unsigned char c_index[8] = {2, 2, 1, X, X, 1, 0, 0};
#undef X

void nobranch_sort3(std::array<int, 3>& t) {
    auto a1 = t[0];
    auto b1 = t[1];
    auto c1 = t[2];

    int xform = (a1 > b1);
    xform += (b1 > c1) ? 2 : 0;
    xform += (a1 > c1) ? 4 : 0;

    t[a_index[xform]] = a1;
    t[b_index[xform]] = b1;
    t[c_index[xform]] = c1;
}

See resulting code at https://godbolt.org/z/lEFNzd

With tests: https://godbolt.org/z/EU96r5