-rw-r--r-- 1600 sortbench-20240116/bench-djbsort.c raw
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "int32_sort.h"

long long ticks(void)
{
  unsigned long long result;
  asm volatile(".byte 15;.byte 49;shlq $32,%%rdx;orq %%rdx,%%rax"
    : "=a"(result) :: "%rdx");
  return result;
}

#define N 131072
#define TIMINGS 127

int32_t r[N] __attribute__((aligned(4096)));
int32_t x[(TIMINGS+1)*N] __attribute__((aligned(4096)));
int32_t y[N] __attribute__((aligned(4096)));

long long t[TIMINGS+1] __attribute__((aligned(4096)));

int main()
{
  for (long long n = 1;n <= N;n += 1+(n/16)) {
    for (long long i = 0;i < n;++i)
      r[i] = random();
    for (long long j = 0;j <= TIMINGS;++j)
      for (long long i = 0;i < n;++i)
        x[j*n+i] = r[i];
    for (long long j = 0;j <= TIMINGS;++j)
      t[j] = ticks();

    for (long long j = 0;j <= TIMINGS;++j) {
      t[j] = ticks();
      int32_sort(x+j*n,n);
    }

    for (long long i = 0;i < n;++i)
      y[i] = r[i];
    for (long long i = 0;i < n;++i)
      for (long long j = 0;j < i;++j)
        if (y[i] < y[j]) {
          int32_t z = y[i];
          y[i] = y[j];
          y[j] = z;
        }
    for (long long j = 0;j <= TIMINGS;++j)
      for (long long i = 0;i < n;++i)
        assert(y[i] == x[j*n+i]);

    for (long long i = 0;i < TIMINGS;++i)
      t[i] = t[i+1]-t[i];
    for (long long i = 0;i < TIMINGS;++i)
      for (long long j = 0;j < i;++j)
        if (t[i] < t[j]) {
          long long z = t[i];
          t[i] = t[j];
          t[j] = z;
        }

    printf("%lld %lld %lld %lld\n",n,t[TIMINGS/4],t[TIMINGS/2],t[(3*TIMINGS)/4]);
  }
  return 0;
}