Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Hans Boehm's binary trees benchmark in C++ using the default new+delete
#include <algorithm>
#include <iostream>
#include <chrono>
struct Node {
Node *l, *r;
Node() : l(0), r(0) {}
Node(Node* l2, Node* r2) : l(l2), r(r2) {}
~Node() { delete l; delete r; }
int check() const {
if (l)
return l->check() + 1 + r->check();
else return 1;
}
};
Node* make(int d) {
if (d == 0) return new Node();
return new Node(make(d - 1), make(d - 1));
}
int test(int max_depth) {
int min_depth = 4;
max_depth = std::max(min_depth + 2, max_depth);
int stretch_depth = max_depth+1;
{
Node *c = make(stretch_depth);
std::cout << "stretch tree of depth " << stretch_depth << "\t "
<< "check: " << c->check() << std::endl;
delete c;
}
Node *long_lived_tree = make(max_depth);
for (int d = min_depth; d <= max_depth; d += 2) {
int iterations = 1 << (max_depth - d + min_depth), c = 0;
for (int i = 1; i <= iterations; ++i) {
Node *a = make(d);
c += a->check();
delete a;
}
std::cout << iterations << "\t trees of depth " << d << "\t "
<< "check: " << c << std::endl;
}
std::cout << "long lived tree of depth " << max_depth << "\t "
<< "check: " << long_lived_tree->check() << "\n";
delete long_lived_tree;
return 0;
}
int main()
{
for (int max_depth = 12; max_depth < 17; max_depth++) {
auto start = std::chrono::system_clock::now();
test(max_depth);
auto end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds = end - start;
std::cout << elapsed_seconds.count() << std::endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.