benchmarks game - binary trees

binary_trees.cc

#include <inttypes.h>
#include <condition_variable>
#include <deque>
#include <iostream>
#include <memory>
#include <mutex>
#include <thread>
#include <variant>
#include <vector>

template <typename T>
class BlockingQueue {
 public:
  BlockingQueue() = default;
  ~BlockingQueue() = default;

  BlockingQueue(const BlockingQueue&) = delete;
  BlockingQueue(BlockingQueue&&) = delete;

  BlockingQueue& operator=(const BlockingQueue&) = delete;
  BlockingQueue& operator=(BlockingQueue&&) = delete;

  template <typename Arg>
  void PushBack(Arg&& data) {
    std::lock_guard<std::mutex> locker(mutex_);
    queue_.push_back(std::forward<Arg>(data));
    condition_.notify_all();
  }

  template <typename... Args>
  void EmplaceBack(Args&&... args) {
    std::lock_guard<std::mutex> locker(mutex_);
    queue_.emplace_back(std::forward<Args>(args)...);
    condition_.notify_all();
  }

  template <typename Arg>
  void PushFront(Arg&& data) {
    std::lock_guard<std::mutex> locker(mutex_);
    queue_.push_front(std::forward<Arg>(data));
    condition_.notify_all();
  }

  template <typename... Args>
  void EmplaceFront(Args&&... args) {
    std::lock_guard<std::mutex> locker(mutex_);
    queue_.emplace_front(std::forward<Args>(args)...);
    condition_.notify_all();
  }

  auto Take() {
    std::unique_lock<std::mutex> locker(mutex_);
    condition_.wait(locker, [this] { return not queue_.empty(); });
    auto data = std::move(queue_.front());
    queue_.pop_front();
    return data;
  }

  auto TryTake() {
    std::unique_lock<std::mutex> locker(mutex_);
    if (queue_.empty()) {
      return T{};
    }
    auto data = std::move(queue_.front());
    queue_.pop_front();
    return data;
  }

  void Wait(size_t n) {
    std::unique_lock<std::mutex> locker(mutex_);
    condition_.wait(locker, [this, n] { return queue_.size() >= n; });
  }

  void Clear() {
    std::lock_guard<std::mutex> locker(mutex_);
    queue_.clear();
  }

  void Shrink() {
    std::lock_guard<std::mutex> locker(mutex_);
    queue_.shrink_to_fit();
  }

  auto Size() const {
    return queue_.size();
  }

  auto Empty() const {
    return queue_.empty();
  }

 private:
  std::mutex mutex_;
  std::condition_variable condition_;
  std::deque<T> queue_;
};

template <class T, size_t chunk_size>
class ObjectPool {
  struct Chunk {
    T objects[chunk_size];
  };

  std::vector<std::unique_ptr<Chunk>> pool_;
  size_t index_ = chunk_size;

 public:
  T* Get() {
    if (index_ >= chunk_size) {
      pool_.emplace_back(std::make_unique<Chunk>());
      index_ = 0;
    }
    auto& back = pool_.back();
    auto object = back->objects + index_;
    ++index_;
    return object;
  }
};

struct Tree {
  Tree* left = nullptr;
  Tree* right = nullptr;
};

using TreePool = ObjectPool<Tree, 4096 / sizeof(Tree)>;

Tree* BottomUpTree(uint32_t depth, TreePool& pool) {
  auto tree = pool.Get();
  if (depth > 0u) {
    tree->right = BottomUpTree(depth - 1, pool);
    tree->left = BottomUpTree(depth - 1, pool);
  }
  return tree;
}

uint32_t ItemCheck(Tree* tree) {
  if (tree->left && tree->right) {
    return 1u + ItemCheck(tree->right) + ItemCheck(tree->left);
  }
  return 1u;
}

std::string Inner(uint32_t depth, uint32_t iterations) {
  auto chk = 0u;
  for (auto i = 0u; i < iterations; ++i) {
    TreePool pool;
    auto tree = BottomUpTree(depth, pool);
    chk += ItemCheck(tree);
  }
  char buf[64] = {0};
  auto n = snprintf(buf, sizeof(buf), "%d\t trees of depth %d\t check: %d", iterations, depth, chk);
  return std::string(buf, n);
}

enum class MailType {
  None,
  Stop,
  Stopped,
  ProcessInner,
  ProcessStretch,
  ProcessLongLived,
  ProcessResult,
};

struct Result {
  uint32_t id;
  std::string text;
  Result(uint32_t id, std::string&& text)
      : id(id), text(std::move(text)) {
  }
};

struct Mail {
  MailType type = MailType::None;
  std::variant<uint32_t, Result> data;
  Mail(MailType type)
      : type(type) {
  }
  Mail(MailType type, uint32_t data)
      : type(type), data(data) {
  }
  Mail(MailType type, Result&& data)
      : type(type), data(std::move(data)) {
  }
};

int main(int argc, char* argv[]) {
  using Mailbox = BlockingQueue<Mail>;

  const uint32_t n = argc > 1 ? std::stoul(argv[1]) : 6u;
  const auto ncpu = std::thread::hardware_concurrency();

  auto min_depth = 4u;
  auto max_depth = n;
  if (min_depth + 2 > n) {
    max_depth = min_depth + 2;
  }

  Mailbox worker_mailbox;
  Mailbox master_mailbox;

  // start processors
  for (uint32_t i = 0; i < ncpu; ++i) {
    std::thread([&]() {
      while (true) {
        auto mail = worker_mailbox.Take();
        switch (mail.type) {
          case MailType::Stop: {
            master_mailbox.EmplaceBack(MailType::Stopped);
            return;
          }
          case MailType::ProcessInner: {
            auto depth = std::get<uint32_t>(mail.data) * 2;
            auto iterations = 1lu << (max_depth - depth + min_depth);
            auto&& text = Inner(depth, iterations);
            master_mailbox.EmplaceBack(MailType::ProcessResult, Result(depth, std::move(text)));
            break;
          }
          case MailType::ProcessStretch:
          case MailType::ProcessLongLived: {
            auto depth = std::get<uint32_t>(mail.data);
            TreePool pool;
            auto tree = BottomUpTree(depth, pool);
            auto check = ItemCheck(tree);
            uint32_t id;
            std::string prefix;
            if (mail.type == MailType::ProcessStretch) {
              id = 0;
              prefix = "stretch";
            } else {
              id = std::numeric_limits<uint32_t>::max();
              prefix = "long lived";
            };
            char buf[64] = {0};
            auto n = snprintf(buf, sizeof(buf), " tree of depth %d\t check: %d", depth, check);
            auto&& text = prefix + std::string(buf, n);
            master_mailbox.EmplaceBack(MailType::ProcessResult, Result(id, std::move(text)));
            break;
          }
          default: {
            break;
          }
        }
      }
    })
        .detach();
  }

  // dispatch jobs
  worker_mailbox.EmplaceBack(MailType::ProcessStretch, max_depth + 1);
  for (uint32_t half_depth = min_depth / 2; half_depth < max_depth / 2 + 1; ++half_depth) {
    worker_mailbox.EmplaceBack(MailType::ProcessInner, half_depth);
  }
  worker_mailbox.EmplaceBack(MailType::ProcessLongLived, max_depth);
  for (uint32_t i = 0; i < ncpu; ++i) {
    worker_mailbox.EmplaceBack(MailType::Stop);
  }

  // gather results
  std::vector<Result> results;
  for (int expected = ncpu; expected > 0;) {
    auto mail = master_mailbox.Take();
    switch (mail.type) {
      case MailType::Stopped: {
        --expected;
        break;
      }
      case MailType::ProcessResult: {
        auto&& result = std::get<Result>(mail.data);
        results.push_back(std::move(result));
        break;
      }
      default: {
        break;
      }
    }
  }

  // show results
  std::sort(results.begin(), results.end(), [](const auto& a, const auto& b) {
    return a.id < b.id;
  });
  for (const auto& item : results) {
    std::cout << item.text << std::endl;
  }
  return 0;
}