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

/* The Computer Language Benchmarks Game
 * https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
 *
 * contributed by Danial Klimkin (C++)
 * contributed by the Rust Project Developers (Rust)
 * contributed by TeXitoi (Rust)
 * contributed by Cristi Cobzarenco (Rust)
 * contributed by Matt Brubeck (Rust) 
 * contributed by Dmytro Ovdiienko
 *
 */

#include <atomic>
#include <numeric>
#include <algorithm>
#include <functional>
#include <iostream>
#include <memory_resource>
#include <thread>

using MemoryPool = std::pmr::monotonic_buffer_resource;

struct Node
{
    Node *l, *r;

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

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 run_parallel(unsigned depth, int iterations, unsigned int workers = std::thread::hardware_concurrency())
{
    std::vector<std::thread> threads;
    threads.reserve(workers);

    std::atomic_int counter = iterations;
    std::atomic_int output = 0;

    for(unsigned i = 0; i < workers; ++i) {
        threads.push_back(std::thread([&counter, depth, &output] {
            std::pmr::unsynchronized_pool_resource upperPool;
            MemoryPool pool {&upperPool};
            int checksum = 0;

            while(--counter >= 0) {
                Node* a     = make(depth, pool);
                checksum    += a->check();
                pool.release();
            }

            output += checksum;
        }));
    }
    
    for(unsigned i = 0; i < workers; ++i) {
        threads[i].join();
    }

    return output;
}

constexpr auto MIN_DEPTH     = 4;

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);

    for (int d = MIN_DEPTH; d <= max_depth; d += 2)
    {
        const int iterations = 1 << (max_depth - d + MIN_DEPTH);
        auto const c = run_parallel(d, iterations);

        std::cout << iterations << "\t trees of depth " << d << "\t check: " << c << "\n";
    }

    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-4ubuntu3


 Thu, 07 Mar 2024 01:22:16 GMT

MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=ivybridge  -std=gnu++17 binarytrees.gpp-5.c++ -o binarytrees.gpp-5.c++.o &&  \
        /usr/bin/g++ binarytrees.gpp-5.c++.o -o binarytrees.gpp-5.gpp_run -lpthread 
rm binarytrees.gpp-5.c++

3.70s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.gpp-5.gpp_run 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303