0xDEADBEEF

testRandomsort.d

import core.bitop;
import std.algorithm;
import std.bitmanip;
import std.conv;
import std.datetime.stopwatch;
import std.file : readText;
import std.format.read : formattedRead;
import std.random;
import std.range;
import std.stdio;
import std.string;

struct S { uint key; }

void histgramSort(T)(const(T)[] src, T[] dest, uint[] counts) {
  auto bits = bsr(src.length - 1) + 1 - 4; // 4 = log2(blockSize = 16)
  auto shift = (uint.sizeof * 8) - bits;

  auto sw = StopWatch(AutoStart.yes);
  counts = counts[0 .. 1 << bits];
  counts[] = 0;

  foreach (x; src) {
    counts[x.key >> shift]++;
  }

  foreach (i; 1 .. counts.length) {
    counts[i] += counts[i-1];
  }

  foreach (x; src) {
    dest[--counts[x.key >> shift]] = x;
  }

  auto reorgTime = sw.peek.total!"nsecs" / 1e6;
  sw.reset();

  foreach (i, c; counts) {
    auto slice = dest[counts[i] .. (i < counts.length-1) ? counts[i+1] : $];
    sort!"a.key < b.key"(slice);
  }

  auto sortTime = sw.peek.total!"nsecs" / 1e6;

  writef("%8.2f + %8.2f = %8.2f ms ", reorgTime, sortTime, reorgTime+sortTime);
}

void main(string[] args) {
  size_t n = args[1].to!uint;

  auto arr = new S[n];
  auto tmp = new S[n];
  auto counts = new uint[n/4];

  writef("%3dM x %dB: ", n / 1000000, S.sizeof);
  Xorshift(1337).take(arr.length).map!(x => S(x)).copy(arr);
  histgramSort(arr, tmp, counts);

  auto sw = StopWatch(AutoStart.yes);
  sort!"a.key < b.key"(arr);
  writef("# %8.2f ms", sw.peek.total!"nsecs" / 1e6);
  assert(arr == tmp);


  auto hugePagesKb = readText("/proc/self/smaps")
    .lineSplitter
    .filter!(line => line.canFind("AnonHugePages"))
    .map!((line) {
        uint val;
        formattedRead!("AnonHugePages: %d")(line, val);
        return val;
    }).sum;

  writeln("# huge pages = ", hugePagesKb, " kB");
}