binary-trees C++ g++ #4 program

/* The Computer Language Benchmarks Game
 * https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
 *
 * contributed by Danial Klimkin
 *
 */

#include <functional>
#include <iostream>
#include <memory_resource>
#include <mutex>
#include <queue>
#include <thread>

using MemoryPool = std::pmr::monotonic_buffer_resource;
using Lambda = std::function<void(void)>;

template<typename T>
class LockingQueue final {
public:
  LockingQueue() = default;

  void emplace(T item) {
    {
      std::scoped_lock lock(mutex);
      queue.emplace(std::move(item));
    }
    signal.notify_one();
  }

  void waitAndPop(T *out) {
    std::unique_lock lock(mutex);
    while (queue.empty()) {
      signal.wait(lock);
    }
    *out = queue.front();
    queue.pop();
  }

private:
  std::mutex mutex;
  std::condition_variable signal;
  std::queue<T> queue;
};

class ThreadPool final {
public:
  explicit ThreadPool(
      const unsigned int workers = std::thread::hardware_concurrency()) {
    threads_.reserve(workers);
    for (size_t i = 0; i < workers; ++i)
      threads_.emplace_back(std::thread([this]() {
        Lambda job;
        while (true) {
          queue_.waitAndPop(&job);
          if (job) {
            job();
          } else {
            enqueue_task(nullptr);
            break;
          }
        }
      }));
  }

  ~ThreadPool() noexcept {
    enqueue_task(nullptr);
    for (std::thread &thread : threads_) {
      thread.join();
    }
  }

  void enqueue_task(Lambda f) {
    queue_.emplace(std::move(f));
  }

private:
  std::vector<std::thread> threads_;
  LockingQueue<Lambda> queue_;
};

struct Node {
  Node *l, *r;

  int check() const {
    if (l)
      return l->check() + 1 + r->check();
    else
      return 1;
  }
};

namespace {
  constexpr size_t LINE_SIZE = 64;
  constexpr size_t SIZEOF_NODE = sizeof(Node);
  constexpr auto MIN_DEPTH = 4;
}

Node *make(const int d, MemoryPool &store) {
  Node *root = static_cast<Node *>(store.allocate(SIZEOF_NODE));
  if (d > 0) {
    root->l = make(d - 1, store);
    root->r = make(d - 1, store);
  } else {
    root->l = root->r = nullptr;
  }
  return root;
}

int main(int argc, char *argv[]) {
  const int max_depth =
      std::max(MIN_DEPTH + 2, (argc == 2 ? atoi(argv[1]) : 10));
  const int stretch_depth = max_depth + 1;

  // Alloc then dealloc stretchdepth tree.
  {
    MemoryPool store;

    Node *c = make(stretch_depth, store);
    std::cout << "stretch tree of depth " << stretch_depth << "\t "
              << "check: " << c->check() << std::endl;
  }

  MemoryPool long_lived_store;
  Node *long_lived_tree = make(max_depth, long_lived_store);

  // Buffer to store output of each thread.
  std::vector<char> buf(
      static_cast<size_t>(LINE_SIZE * (max_depth + 1) * sizeof(char)), 0);

  {
    ThreadPool pool;
    for (int d = MIN_DEPTH; d <= max_depth; d += 2) {
      const int iterations = 1 << (max_depth - d + MIN_DEPTH);
      pool.enqueue_task([iterations, d, &buf]() {
        int c = 0;

        // Create a memory pool for this thread to use.
        MemoryPool store;

        for (int i = 1; i <= iterations; ++i) {
          Node *a = make(d, store);
          c += a->check();
          store.release();
        }

        // each thread write to separate location
        sprintf(buf.data() + LINE_SIZE * d,
                "%d\t trees of depth %d\t check: %d\n",
                iterations, d, c);
      });
    }
  }

  // print all results
  for (int d = MIN_DEPTH; d <= max_depth; d += 2) {
    printf("%s", buf.data() + (d * LINE_SIZE));
  }

  std::cout << "long lived tree of depth " << max_depth << "\t "
            << "check: " << (long_lived_tree->check()) << "\n";

  return 0;
}
    

NOTES:
64-bit Ubuntu quad core
Ubuntu 13.2.0-23ubuntu4


 Tue, 04 Jun 2024 01:59:30 GMT

MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=ivybridge  -std=gnu++17 binarytrees.gpp-4.c++ -o binarytrees.gpp-4.c++.o &&  \
        /usr/bin/g++ binarytrees.gpp-4.c++.o -o binarytrees.gpp-4.gpp_run -lpthread 
binarytrees.gpp-4.c++:42:8: error: ‘condition_variable’ in namespace ‘std’ does not name a type
   42 |   std::condition_variable signal;
      |        ^~~~~~~~~~~~~~~~~~
binarytrees.gpp-4.c++:14:1: note: ‘std::condition_variable’ is defined in header ‘<condition_variable>’; did you forget to ‘#include <condition_variable>’?
   13 | #include <thread>
  +++ |+#include <condition_variable>
   14 | 
binarytrees.gpp-4.c++: In member function ‘void LockingQueue<T>::emplace(T)’:
binarytrees.gpp-4.c++:28:5: error: ‘signal’ was not declared in this scope; did you mean ‘signed’?
   28 |     signal.notify_one();
      |     ^~~~~~
      |     signed
binarytrees.gpp-4.c++: In member function ‘void LockingQueue<T>::waitAndPop(T*)’:
binarytrees.gpp-4.c++:34:7: error: ‘signal’ was not declared in this scope; did you mean ‘signed’?
   34 |       signal.wait(lock);
      |       ^~~~~~
      |       signed
make: [/home/dunham/all-benchmarksgame/2000-benchmarksgame/nanobench/makefiles/u64q.programs.Makefile:54: binarytrees.gpp-4.gpp_run] Error 1 (ignored)
rm binarytrees.gpp-4.c++

3.30s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.gpp-4.gpp_run 7

MAKE ERROR