Benchmark BinaryHeap

main.d

void main()
{
  import mybinaryheap : MyBinaryHeap;
  import std.container.binaryheap : BinaryHeap;
  import std.container.rbtree : RedBlackTree;
  import std.datetime.stopwatch : benchmark;
  import std.stdio : writeln;
  import std.random : Random, unpredictableSeed, uniform;

  auto rnd = Random(unpredictableSeed);
  const size_t n = 10 ^^ 1;
  auto a0 = new int[](n), b = new int[](n);
  foreach (i; 0 .. n)
  {
    a0[i] = uniform!"[]"(-10 ^^ 9, 10 ^^ 9, rnd);
    b[i] = uniform!"[]"(-10 ^^ 9, 10 ^^ 9, rnd);
  }
  auto a1 = a0.dup, a2 = a0.dup;
  
  void f0()
  {
    auto h = new BinaryHeap!(int[])(a0, a0.length);
    foreach (_; 0 .. n / 2)
      h.removeFront;
    foreach (x; b)
      h.insert(x);
    foreach (_; 0 .. n / 2)
      h.removeFront;
  }

  void f1()
  {
    auto h = new RedBlackTree!(int, "a>b", true)(a1);
    foreach (_; 0 .. n / 2)
      h.removeFront;
    foreach (x; b)
      h.insert(x);
    foreach (_; 0 .. n / 2)
      h.removeFront;
  }

  void f2()
  {
    auto h = new MyBinaryHeap!(int, "a>b")(a2);
    foreach (_; 0 .. n / 2)
      h.removeFront;
    foreach (x; b)
      h.insert(x);
    foreach (_; 0 .. n / 2)
      h.removeFront;
  }

  auto results = benchmark!(f0, f1, f2)(100);
  writeln("std.container.binaryheap : ", results[0]);
  writeln("std.container.rbtree     : ", results[1]);
  writeln("myBinaryHeap             : ", results[2]);
}

/*
  dmd -O -release -inline main.d
  ./main
  
  std.container.binaryheap : 1 sec, 552 ms, 492 μs, and 7 hnsecs
  std.container.rbtree     : 7 secs, 480 ms, 554 μs, and 9 hnsecs
  myBinaryHeap             : 2 secs, 265 ms, 37 μs, and 5 hnsecs
*/