benchmarks/algorithms.bench.cpp

#include <algorithm>
#include <cstdint>
#include <map>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "CartesianBenchmarks.h"
#include "GenerateInput.h"
#include "benchmark/benchmark.h"
#include "test_macros.h"

namespace {

enum class ValueType { Uint32, Uint64, Pair, Tuple, String };
struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 5> {
  static constexpr const char* Names[] = {
      "uint32", "uint64", "pair<uint32, uint32>",
      "tuple<uint32, uint64, uint32>", "string"};
};

template <class V>
using Value = std::conditional_t<
    V() == ValueType::Uint32, uint32_t,
    std::conditional_t<
        V() == ValueType::Uint64, uint64_t,
        std::conditional_t<
            V() == ValueType::Pair, std::pair<uint32_t, uint32_t>,
            std::conditional_t<V() == ValueType::Tuple,
                               std::tuple<uint32_t, uint64_t, uint32_t>,
                               std::string> > > >;

enum class Order {
  Random,
  Ascending,
  Descending,
  SingleElement,
  PipeOrgan,
  Heap,
  QuickSortAdversary,
};
struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {
  static constexpr const char* Names[] = {"Random",     "Ascending",
                                          "Descending", "SingleElement",
                                          "PipeOrgan",  "Heap",
                                          "QuickSortAdversary"};
};

// fillAdversarialQuickSortInput fills the input vector with N int-like values.
// These values are arranged in such a way that they would invoke O(N^2)
// behavior on any quick sort implementation that satisifies certain conditions.
// Details are available in the following paper:
// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice &
// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344.
// https://dl.acm.org/doi/10.5555/311868.311871.
template <class T>
void fillAdversarialQuickSortInput(T& V, size_t N) {
  assert(N > 0);
  // If an element is equal to gas, it indicates that the value of the element
  // is still to be decided and may change over the course of time.
  const int gas = N - 1;
  V.resize(N);
  for (int i = 0; i < N; ++i) {
    V[i] = gas;
  }
  // Candidate for the pivot position.
  int candidate = 0;
  int nsolid = 0;
  // Populate all positions in the generated input to gas.
  std::vector<int> ascVals(V.size());
  // Fill up with ascending values from 0 to V.size()-1.  These will act as
  // indices into V.
  std::iota(ascVals.begin(), ascVals.end(), 0);
  std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) {
    if (V[x] == gas && V[y] == gas) {
      // We are comparing two inputs whose value is still to be decided.
      if (x == candidate) {
        V[x] = nsolid++;
      } else {
        V[y] = nsolid++;
      }
    }
    if (V[x] == gas) {
      candidate = x;
    } else if (V[y] == gas) {
      candidate = y;
    }
    return V[x] < V[y];
  });
}

template <typename T>
void fillValues(std::vector<T>& V, size_t N, Order O) {
  if (O == Order::SingleElement) {
    V.resize(N, 0);
  } else if (O == Order::QuickSortAdversary) {
    fillAdversarialQuickSortInput(V, N);
  } else {
    while (V.size() < N)
      V.push_back(V.size());
  }
}

template <typename T>
void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
  if (O == Order::SingleElement) {
    V.resize(N, std::make_pair(0, 0));
  } else {
    while (V.size() < N)
      // Half of array will have the same first element.
      if (V.size() % 2) {
        V.push_back(std::make_pair(V.size(), V.size()));
      } else {
        V.push_back(std::make_pair(0, V.size()));
      }
  }
}

template <typename T1, typename T2, typename T3>
void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
  if (O == Order::SingleElement) {
    V.resize(N, std::make_tuple(0, 0, 0));
  } else {
    while (V.size() < N)
      // One third of array will have the same first element.
      // One third of array will have the same first element and the same second element.
      switch (V.size() % 3) {
      case 0:
        V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
        break;
      case 1:
        V.push_back(std::make_tuple(0, V.size(), V.size()));
        break;
      case 2:
        V.push_back(std::make_tuple(0, 0, V.size()));
        break;
      }
  }
}

void fillValues(std::vector<std::string>& V, size_t N, Order O) {
  if (O == Order::SingleElement) {
    V.resize(N, getRandomString(64));
  } else {
    while (V.size() < N)
      V.push_back(getRandomString(64));
  }
}

template <class T>
void sortValues(T& V, Order O) {
  assert(std::is_sorted(V.begin(), V.end()));
  switch (O) {
  case Order::Random: {
    std::random_device R;
    std::mt19937 M(R());
    std::shuffle(V.begin(), V.end(), M);
    break;
  }
  case Order::Ascending:
    std::sort(V.begin(), V.end());
    break;
  case Order::Descending:
    std::sort(V.begin(), V.end(), std::greater<>());
    break;
  case Order::SingleElement:
    // Nothing to do
    break;
  case Order::PipeOrgan:
    std::sort(V.begin(), V.end());
    std::reverse(V.begin() + V.size() / 2, V.end());
    break;
  case Order::Heap:
    std::make_heap(V.begin(), V.end());
    break;
  case Order::QuickSortAdversary:
    // Nothing to do
    break;
  }
}

constexpr size_t TestSetElements =
#if !TEST_HAS_FEATURE(memory_sanitizer)
    1 << 18;
#else
    1 << 14;
#endif

template <class ValueType>
std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
                                                               Order O) {
  std::vector<std::vector<Value<ValueType> > > Ret;
  const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);
  Ret.resize(NumCopies);
  for (auto& V : Ret) {
    fillValues(V, N, O);
    sortValues(V, O);
  }
  return Ret;
}

template <class T, class U>
TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
                                    U& Orig) {
  state.PauseTiming();
  for (auto& Copy : Copies)
    Copy = Orig;
  state.ResumeTiming();
}

enum class BatchSize {
  CountElements,
  CountBatch,
};

template <class ValueType, class F>
void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
                   BatchSize Count, F Body) {
  auto Copies = makeOrderedValues<ValueType>(Quantity, O);
  auto Orig = Copies;

  const size_t Batch = Count == BatchSize::CountElements
                           ? Copies.size() * Quantity
                           : Copies.size();
  while (state.KeepRunningBatch(Batch)) {
    for (auto& Copy : Copies) {
      Body(Copy);
      benchmark::DoNotOptimize(Copy);
    }
    state.PauseTiming();
    Copies = Orig;
    state.ResumeTiming();
  }
}

template <class ValueType, class Order>
struct Sort {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(
        state, Quantity, Order(), BatchSize::CountElements,
        [](auto& Copy) { std::sort(Copy.begin(), Copy.end()); });
  }

  bool skip() const { return Order() == ::Order::Heap; }

  std::string name() const {
    return "BM_Sort" + ValueType::name() + Order::name() + "_" +
           std::to_string(Quantity);
  };
};

template <class ValueType, class Order>
struct StableSort {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(
        state, Quantity, Order(), BatchSize::CountElements,
        [](auto& Copy) { std::stable_sort(Copy.begin(), Copy.end()); });
  }

  bool skip() const { return Order() == ::Order::Heap; }

  std::string name() const {
    return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
           std::to_string(Quantity);
  };
};

template <class ValueType, class Order>
struct MakeHeap {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(
        state, Quantity, Order(), BatchSize::CountElements,
        [](auto& Copy) { std::make_heap(Copy.begin(), Copy.end()); });
  }

  std::string name() const {
    return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
           std::to_string(Quantity);
  };
};

template <class ValueType>
struct SortHeap {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(
        state, Quantity, Order::Heap, BatchSize::CountElements,
        [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
  }

  std::string name() const {
    return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
  };
};

template <class ValueType, class Order>
struct MakeThenSortHeap {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements,
                             [](auto& Copy) {
                               std::make_heap(Copy.begin(), Copy.end());
                               std::sort_heap(Copy.begin(), Copy.end());
                             });
  }

  std::string name() const {
    return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
           std::to_string(Quantity);
  };
};

template <class ValueType, class Order>
struct PushHeap {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(
        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
          for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
            std::push_heap(Copy.begin(), I + 1);
          }
        });
  }

  bool skip() const { return Order() == ::Order::Heap; }

  std::string name() const {
    return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
           std::to_string(Quantity);
  };
};

template <class ValueType>
struct PopHeap {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(
        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
          for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
            std::pop_heap(B, I);
          }
        });
  }

  std::string name() const {
    return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
  };
};

} // namespace

int main(int argc, char** argv) {
  benchmark::Initialize(&argc, argv);
  if (benchmark::ReportUnrecognizedArguments(argc, argv))
    return 1;

  const std::vector<size_t> Quantities = {1 << 0, 1 << 2,  1 << 4,  1 << 6,
                                          1 << 8, 1 << 10, 1 << 14,
    // Running each benchmark in parallel consumes too much memory with MSAN
    // and can lead to the test process being killed.
#if !TEST_HAS_FEATURE(memory_sanitizer)
                                          1 << 18
#endif
  };
  makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
  makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
      Quantities);
  makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
  makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
  makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
      Quantities);
  makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
  makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
  benchmark::RunSpecifiedBenchmarks();
}