network_sort.cpp

#include <cassert>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstdint>

// https://gcc.gnu.org/onlinedocs/gcc-8.2.0/gcc/Machine-Constraints.html#Machine-Constraints
inline uint64_t rdtsc()
{
  uint32_t tickl, tickh;
  __asm__ __volatile__("rdtsc":"=a"(tickl),"=d"(tickh));
  return (static_cast<uint64_t>(tickh) << 32) | tickl;
}

void network_sort_swap(int32_t *v, int a, int b)
{
  auto va = v[a];
  auto vb = v[b];
  v[a] = va < vb ? va : vb;
  v[b] = va < vb ? vb : va;
}

#define SWAP(a, b) network_sort_swap(v, a, b)

void network_sort_8n(int32_t *v)
{
  SWAP(0, 1); SWAP(2, 3); SWAP(4, 5); SWAP(6, 7);
  SWAP(0, 2); SWAP(1, 3); SWAP(4, 6); SWAP(5, 7);
  SWAP(1, 2); SWAP(5, 6); SWAP(0, 4); SWAP(3, 7);
  SWAP(1, 5); SWAP(2, 6);
  SWAP(1, 4); SWAP(3, 6);
  SWAP(2, 4); SWAP(3, 5);
  SWAP(3, 4);
}

// xorshift: https://ja.wikipedia.org/wiki/Xorshift
uint32_t rnd(void)
{
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 15);
}

void benchmark()
{
  constexpr const int N = 80 * 1000 * 1000;

  // 領域vを確保し乱数で埋める
  auto v = static_cast<int32_t*>(calloc(sizeof(int32_t), N));
  for (int i = 0; i < N; i++) {
    v[i] = rnd();
  }
  auto t0 = rdtsc();
  for (int n = 0; n < N; n += 8) {
    // ここのコメントアウトで実装を切り替える
    network_sort_8n(v + n);
    //std::sort(v + n, v + n + 8);
  }
  auto t1 = rdtsc();
  printf("%lld [Mcycles]\n", (t1 - t0)/1000/1000);

  // valiadtion
  for (int n = 0; n < N; n += 8) {
    auto value = v[n];
    for (int i = 0; i < 8; i++) {
      assert(value <= v[n + i]);
      value = v[n + i];
    }
  }
  puts("Validation OK");
}

int main() {
  benchmark();
}