Let's benchmark malloc
[WebKit-https.git] / PerformanceTests / MallocBench / MallocBench / tree.cpp
1 /*
2  * Copyright (C) 2014 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "tree.h"
27 #include <limits>
28 #include <stdlib.h>
29 #include <strings.h>
30
31 #include "mbmalloc.h"
32
33 namespace {
34
35 struct Node {
36     void* operator new(size_t size)
37     {
38         return mbmalloc(size);
39     }
40
41     void operator delete(void* p, size_t size)
42     {
43         mbfree(p, size);
44     }
45
46     Node(Node* left, Node* right, size_t payloadSize, size_t id)
47         : m_refCount(1)
48         , m_left(left)
49         , m_right(right)
50         , m_payload(static_cast<char*>(mbmalloc(payloadSize)))
51         , m_payloadSize(payloadSize)
52         , m_id(id)
53     {
54         if (m_left)
55             m_left->ref();
56         if (m_right)
57             m_right->ref();
58         bzero(m_payload, payloadSize);
59     }
60
61     ~Node()
62     {
63         if (m_left)
64             m_left->deref();
65         if (m_right)
66             m_right->deref();
67         mbfree(m_payload, m_payloadSize);
68     }
69
70     void ref()
71     {
72         ++m_refCount;
73     }
74
75     void deref()
76     {
77         if (m_refCount == 1)
78             delete this;
79         else
80             --m_refCount;
81     }
82     
83     size_t id() { return m_id; }
84     Node* left() { return m_left; }
85     Node* right() { return m_right; }
86
87     void setLeft(Node* left)
88     {
89         left->ref();
90         if (m_left)
91             m_left->deref();
92         
93         m_left = left;
94     }
95
96     void setRight(Node* right)
97     {
98         right->ref();
99         if (m_right)
100             m_right->deref();
101         
102         m_right = right;
103     }
104
105     unsigned m_refCount;
106     Node* m_left;
107     Node* m_right;
108     char* m_payload;
109     size_t m_payloadSize;
110     size_t m_id;
111 };
112
113 void verify(Node* node, Node* left, Node* right)
114 {
115     if (left && left->id() >= node->id())
116         abort();
117
118     if (right && right->id() <= node->id())
119         abort();
120 }
121
122 Node* createTree(size_t depth, size_t& counter)
123 {
124     if (!depth)
125         return 0;
126
127     Node* left = createTree(depth - 1, counter);
128     size_t id = counter++;
129     Node* right = createTree(depth - 1, counter);
130
131     Node* result = new Node(left, right, ((depth * 8) & (64 - 1)) | 1, id);
132
133     verify(result, left, right);
134
135     if (left)
136         left->deref();
137     if (right)
138         right->deref();
139     return result;
140 }
141
142 Node* createTree(size_t depth)
143 {
144     size_t counter = 0;
145     return createTree(depth, counter);
146 }
147
148 void churnTree(Node* node, size_t stride, size_t& counter)
149 {
150     if (!node)
151         return;
152     
153     churnTree(node->left(), stride, counter);
154
155     if (node->left() && !(counter % stride)) {
156         Node* left = new Node(node->left()->left(), node->left()->right(), (counter & (64 - 1)) | 1, node->left()->id());
157         Node* right = new Node(node->right()->left(), node->right()->right(), (counter & (64 - 1)) | 1, node->right()->id());
158         node->setLeft(left);
159         node->setRight(right);
160         left->deref();
161         right->deref();
162     }
163     ++counter;
164
165     churnTree(node->right(), stride, counter);
166
167     verify(node, node->left(), node->right());
168 }
169
170 void churnTree(Node* tree, size_t stride)
171 {
172     size_t counter;
173     churnTree(tree, stride, counter);
174 }
175
176 } // namespace
177
178 void benchmark_tree_allocate(bool isParallel)
179 {
180     size_t times = 24;
181     size_t depth = 16;
182     if (isParallel) {
183         times *= 4;
184         depth = 13;
185     }
186
187     for (size_t time = 0; time < times; ++time) {
188         Node* tree = createTree(depth);
189         tree->deref();
190     }
191 }
192
193 void benchmark_tree_traverse(bool isParallel)
194 {
195     size_t times = 256;
196     size_t depth = 15;
197     if (isParallel) {
198         times = 512;
199         depth = 13;
200     }
201
202     Node* tree = createTree(depth);
203     for (size_t time = 0; time < times; ++time)
204         churnTree(tree, std::numeric_limits<size_t>::max()); // Reuse this to iterate and validate.
205     tree->deref();
206 }
207
208 void benchmark_tree_churn(bool isParallel)
209 {
210     size_t times = 160;
211     size_t depth = 15;
212     if (isParallel) {
213         times *= 4;
214         depth = 12;
215     }
216
217     Node* tree = createTree(depth);
218     for (size_t time = 0; time < times; ++time)
219         churnTree(tree, 8);
220     tree->deref();
221 }