1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include <vespa/vespalib/testkit/testapp.h>
#include <vespa/vespalib/util/rusage.h>
#include <vespa/vespalib/util/optimized.h>
#include <vespa/vespalib/util/allocinarray.h>
#include <vespa/vespalib/util/array.hpp>
#include <vespa/log/log.h>
LOG_SETUP("allocinarray_benchmark");
using namespace vespalib;
class Test : public TestApp
{
public:
private:
void benchmarkTree(size_t count);
void benchmarkTreeInArray(size_t count);
int Main() override;
};
template <typename T>
class TreeNode
{
public:
typedef TreeNode * P;
TreeNode(const T & p) :_left(NULL), _right(NULL), _payLoad(p) { }
~TreeNode() {
if (_left) {
delete _left;
}
if (_right) {
delete _right;
}
}
P left() { return _left; }
P right() { return _right; }
void left(P l) { _left = l; }
void right(P l) { _right = l; }
private:
P _left;
P _right;
T _payLoad;
};
template <typename T>
class RefTreeNode
{
public:
typedef uint32_t P;
RefTreeNode(const T & p) :_left(-1), _right(-1), _payLoad(p) { }
P left() { return _left; }
P right() { return _right; }
void left(P l) { _left = l; }
void right(P l) { _right = l; }
private:
P _left;
P _right;
T _payLoad;
};
typedef TreeNode<long> N;
typedef RefTreeNode<long> R;
typedef AllocInArray<R, vespalib::Array<R> > Store;
void populate(Store & store, uint32_t parent, size_t depth)
{
if (depth > 0) {
store[parent].left(store.alloc(R(0)));
populate(store, store[parent].left(), depth-1);
store[parent].right(store.alloc(R(1)));
populate(store, store[parent].right(), depth-1);
}
}
void populate(N * parent, size_t depth)
{
if (depth > 0) {
parent->left(new N(0));
populate(parent->left(), depth-1);
parent->right(new N(1));
populate(parent->right(), depth-1);
}
}
void Test::benchmarkTree(size_t count)
{
N root(0);
size_t depth = Optimized::msbIdx(count);
populate(&root, depth);
}
void Test::benchmarkTreeInArray(size_t count)
{
Store store;
store.alloc(R(0));
size_t depth = Optimized::msbIdx(count);
populate(store, 0, depth);
}
int
Test::Main()
{
std::string type("direct");
size_t count = 1000000;
if (_argc > 1) {
type = _argv[1];
}
if (_argc > 2) {
count = strtol(_argv[2], NULL, 0);
}
TEST_INIT("allocinarray_benchmark");
fastos::TimeStamp start(fastos::ClockSystem::now());
if (type == "direct") {
benchmarkTree(count);
} else {
benchmarkTreeInArray(count);
}
LOG(info, "rusage = {\n%s\n}", vespalib::RUsage::createSelf(start).toString().c_str());
ASSERT_EQUAL(0, kill(0, SIGPROF));
TEST_DONE();
}
TEST_APPHOOK(Test);
|
