source code
/* The Computer Language Benchmarks Game
* https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
*
* contributed by Jon Harrop
* modified by Alex Mizrahi
* modified by Andreas Schäfer
* very minor omp tweak by The Anh Tran
* *reset*
*/
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
#include <boost/pool/object_pool.hpp>
const size_t LINE_SIZE = 64;
struct Node
{
Node *l, *r;
Node() : l(0), r(0)
{}
Node(Node *l2, Node *r2) : l(l2), r(r2)
{}
int check() const
{
if (l)
return l->check() + 1 + r->check();
else return 1;
}
};
typedef boost::object_pool<Node> NodePool;
Node *make(int d, NodePool &store)
{
if (d > 0)
return store.construct( make(d-1, store),
make(d-1, store) );
return store.construct();
}
int GetThreadCount()
{
cpu_set_t cs;
CPU_ZERO(&cs);
sched_getaffinity(0, sizeof(cs), &cs);
int count = 0;
for (int i = 0; i < 8; i++)
{
if (CPU_ISSET(i, &cs))
count++;
}
return count;
}
int main(int argc, char *argv[])
{
int min_depth = 4;
int max_depth = std::max(min_depth+2,
(argc == 2 ? atoi(argv[1]) : 10));
int stretch_depth = max_depth+1;
// Alloc then dealloc stretchdepth tree
{
NodePool store;
Node *c = make(stretch_depth, store);
std::cout << "stretch tree of depth " << stretch_depth << "\t "
<< "check: " << c->check() << std::endl;
}
NodePool long_lived_store;
Node *long_lived_tree = make(max_depth, long_lived_store);
// buffer to store output of each thread
char *outputstr = (char*)malloc(LINE_SIZE * (max_depth +1) * sizeof(char));
#pragma omp parallel for default(shared) num_threads(GetThreadCount()) schedule(dynamic, 1)
for (int d = min_depth; d <= max_depth; d += 2)
{
int iterations = 1 << (max_depth - d + min_depth);
int c = 0;
for (int i = 1; i <= iterations; ++i)
{
NodePool store;
Node *a = make(d, store);
c += a->check();
}
// each thread write to separate location
sprintf(outputstr + 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", outputstr + (d * LINE_SIZE) );
free(outputstr);
std::cout << "long lived tree of depth " << max_depth << "\t "
<< "check: " << (long_lived_tree->check()) << "\n";
return 0;
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
g++ (Ubuntu 14.2.0-4ubuntu2) 14.2.0
Tue, 22 Oct 2024 19:53:53 GMT
MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=ivybridge -fopenmp binarytrees.gpp-6.c++ -o binarytrees.gpp-6.c++.o && \
/usr/bin/g++ binarytrees.gpp-6.c++.o -o binarytrees.gpp-6.gpp_run -fopenmp
rm binarytrees.gpp-6.c++
4.95s to complete and log all make actions
COMMAND LINE:
./binarytrees.gpp-6.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