1 //===- ConcurrentHashtableTest.cpp ----------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/ADT/ConcurrentHashtable.h"
10 #include "llvm/Support/Debug.h"
11 #include "llvm/Support/FormatVariadic.h"
12 #include "llvm/Support/Parallel.h"
13 #include "llvm/Support/PerThreadBumpPtrAllocator.h"
14 #include "gtest/gtest.h"
15 #include <limits>
16 #include <random>
17 #include <vector>
18 using namespace llvm;
19 using namespace parallel;
20
21 namespace {
22 class String {
23 public:
String()24 String() {}
getKey() const25 const std::string &getKey() const { return Data; }
26
27 template <typename AllocatorTy>
create(const std::string & Num,AllocatorTy & Allocator)28 static String *create(const std::string &Num, AllocatorTy &Allocator) {
29 String *Result = Allocator.template Allocate<String>();
30 new (Result) String(Num);
31 return Result;
32 }
33
34 protected:
String(const std::string & Num)35 String(const std::string &Num) { Data += Num; }
36
37 std::string Data;
38 std::array<char, 0x20> ExtraData;
39 };
40
TEST(ConcurrentHashTableTest,AddStringEntries)41 TEST(ConcurrentHashTableTest, AddStringEntries) {
42 PerThreadBumpPtrAllocator Allocator;
43 ConcurrentHashTableByPtr<std::string, String, PerThreadBumpPtrAllocator,
44 ConcurrentHashTableInfoByPtr<
45 std::string, String, PerThreadBumpPtrAllocator>>
46 HashTable(Allocator, 10);
47
48 // PerThreadBumpPtrAllocator should be accessed from threads created by
49 // ThreadPoolExecutor. Use TaskGroup to run on ThreadPoolExecutor threads.
50 parallel::TaskGroup tg;
51
52 tg.spawn([&]() {
53 size_t AllocatedBytesAtStart = Allocator.getBytesAllocated();
54 std::pair<String *, bool> res1 = HashTable.insert("1");
55 // Check entry is inserted.
56 EXPECT_TRUE(res1.first->getKey() == "1");
57 EXPECT_TRUE(res1.second);
58
59 std::pair<String *, bool> res2 = HashTable.insert("2");
60 // Check old entry is still valid.
61 EXPECT_TRUE(res1.first->getKey() == "1");
62 // Check new entry is inserted.
63 EXPECT_TRUE(res2.first->getKey() == "2");
64 EXPECT_TRUE(res2.second);
65 // Check new and old entries use different memory.
66 EXPECT_TRUE(res1.first != res2.first);
67
68 std::pair<String *, bool> res3 = HashTable.insert("3");
69 // Check one more entry is inserted.
70 EXPECT_TRUE(res3.first->getKey() == "3");
71 EXPECT_TRUE(res3.second);
72
73 std::pair<String *, bool> res4 = HashTable.insert("1");
74 // Check duplicated entry is inserted.
75 EXPECT_TRUE(res4.first->getKey() == "1");
76 EXPECT_FALSE(res4.second);
77 // Check duplicated entry uses the same memory.
78 EXPECT_TRUE(res1.first == res4.first);
79
80 // Check first entry is still valid.
81 EXPECT_TRUE(res1.first->getKey() == "1");
82
83 // Check data was allocated by allocator.
84 EXPECT_TRUE(Allocator.getBytesAllocated() > AllocatedBytesAtStart);
85
86 // Check statistic.
87 std::string StatisticString;
88 raw_string_ostream StatisticStream(StatisticString);
89 HashTable.printStatistic(StatisticStream);
90
91 EXPECT_TRUE(StatisticString.find("Overall number of entries = 3\n") !=
92 std::string::npos);
93 });
94 }
95
TEST(ConcurrentHashTableTest,AddStringMultiplueEntries)96 TEST(ConcurrentHashTableTest, AddStringMultiplueEntries) {
97 PerThreadBumpPtrAllocator Allocator;
98 const size_t NumElements = 10000;
99 ConcurrentHashTableByPtr<std::string, String, PerThreadBumpPtrAllocator,
100 ConcurrentHashTableInfoByPtr<
101 std::string, String, PerThreadBumpPtrAllocator>>
102 HashTable(Allocator);
103
104 // PerThreadBumpPtrAllocator should be accessed from threads created by
105 // ThreadPoolExecutor. Use TaskGroup to run on ThreadPoolExecutor threads.
106 parallel::TaskGroup tg;
107
108 tg.spawn([&]() {
109 // Check insertion.
110 for (size_t I = 0; I < NumElements; I++) {
111 BumpPtrAllocator &ThreadLocalAllocator =
112 Allocator.getThreadLocalAllocator();
113 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
114 std::string StringForElement = formatv("{0}", I);
115 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
116 EXPECT_TRUE(Entry.second);
117 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
118 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() >
119 AllocatedBytesAtStart);
120 }
121
122 std::string StatisticString;
123 raw_string_ostream StatisticStream(StatisticString);
124 HashTable.printStatistic(StatisticStream);
125
126 // Verifying that the table contains exactly the number of elements we
127 // inserted.
128 EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000\n") !=
129 std::string::npos);
130
131 // Check insertion of duplicates.
132 for (size_t I = 0; I < NumElements; I++) {
133 BumpPtrAllocator &ThreadLocalAllocator =
134 Allocator.getThreadLocalAllocator();
135 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
136 std::string StringForElement = formatv("{0}", I);
137 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
138 EXPECT_FALSE(Entry.second);
139 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
140 // Check no additional bytes were allocated for duplicate.
141 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() ==
142 AllocatedBytesAtStart);
143 }
144
145 // Check statistic.
146 // Verifying that the table contains exactly the number of elements we
147 // inserted.
148 EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000\n") !=
149 std::string::npos);
150 });
151 }
152
TEST(ConcurrentHashTableTest,AddStringMultiplueEntriesWithResize)153 TEST(ConcurrentHashTableTest, AddStringMultiplueEntriesWithResize) {
154 PerThreadBumpPtrAllocator Allocator;
155 // Number of elements exceeds original size, thus hashtable should be resized.
156 const size_t NumElements = 20000;
157 ConcurrentHashTableByPtr<std::string, String, PerThreadBumpPtrAllocator,
158 ConcurrentHashTableInfoByPtr<
159 std::string, String, PerThreadBumpPtrAllocator>>
160 HashTable(Allocator, 100);
161
162 // PerThreadBumpPtrAllocator should be accessed from threads created by
163 // ThreadPoolExecutor. Use TaskGroup to run on ThreadPoolExecutor threads.
164 parallel::TaskGroup tg;
165
166 tg.spawn([&]() {
167 // Check insertion.
168 for (size_t I = 0; I < NumElements; I++) {
169 BumpPtrAllocator &ThreadLocalAllocator =
170 Allocator.getThreadLocalAllocator();
171 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
172 std::string StringForElement = formatv("{0} {1}", I, I + 100);
173 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
174 EXPECT_TRUE(Entry.second);
175 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
176 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() >
177 AllocatedBytesAtStart);
178 }
179
180 std::string StatisticString;
181 raw_string_ostream StatisticStream(StatisticString);
182 HashTable.printStatistic(StatisticStream);
183
184 // Verifying that the table contains exactly the number of elements we
185 // inserted.
186 EXPECT_TRUE(StatisticString.find("Overall number of entries = 20000\n") !=
187 std::string::npos);
188
189 // Check insertion of duplicates.
190 for (size_t I = 0; I < NumElements; I++) {
191 BumpPtrAllocator &ThreadLocalAllocator =
192 Allocator.getThreadLocalAllocator();
193 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
194 std::string StringForElement = formatv("{0} {1}", I, I + 100);
195 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
196 EXPECT_FALSE(Entry.second);
197 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
198 // Check no additional bytes were allocated for duplicate.
199 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() ==
200 AllocatedBytesAtStart);
201 }
202
203 // Check statistic.
204 // Verifying that the table contains exactly the number of elements we
205 // inserted.
206 EXPECT_TRUE(StatisticString.find("Overall number of entries = 20000\n") !=
207 std::string::npos);
208 });
209 }
210
TEST(ConcurrentHashTableTest,AddStringEntriesParallel)211 TEST(ConcurrentHashTableTest, AddStringEntriesParallel) {
212 PerThreadBumpPtrAllocator Allocator;
213 const size_t NumElements = 10000;
214 ConcurrentHashTableByPtr<std::string, String, PerThreadBumpPtrAllocator,
215 ConcurrentHashTableInfoByPtr<
216 std::string, String, PerThreadBumpPtrAllocator>>
217 HashTable(Allocator);
218
219 // Check parallel insertion.
220 parallelFor(0, NumElements, [&](size_t I) {
221 BumpPtrAllocator &ThreadLocalAllocator =
222 Allocator.getThreadLocalAllocator();
223 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
224 std::string StringForElement = formatv("{0}", I);
225 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
226 EXPECT_TRUE(Entry.second);
227 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
228 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() >
229 AllocatedBytesAtStart);
230 });
231
232 std::string StatisticString;
233 raw_string_ostream StatisticStream(StatisticString);
234 HashTable.printStatistic(StatisticStream);
235
236 // Verifying that the table contains exactly the number of elements we
237 // inserted.
238 EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000\n") !=
239 std::string::npos);
240
241 // Check parallel insertion of duplicates.
242 parallelFor(0, NumElements, [&](size_t I) {
243 BumpPtrAllocator &ThreadLocalAllocator =
244 Allocator.getThreadLocalAllocator();
245 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
246 std::string StringForElement = formatv("{0}", I);
247 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
248 EXPECT_FALSE(Entry.second);
249 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
250 // Check no additional bytes were allocated for duplicate.
251 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() ==
252 AllocatedBytesAtStart);
253 });
254
255 // Check statistic.
256 // Verifying that the table contains exactly the number of elements we
257 // inserted.
258 EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000\n") !=
259 std::string::npos);
260 }
261
TEST(ConcurrentHashTableTest,AddStringEntriesParallelWithResize)262 TEST(ConcurrentHashTableTest, AddStringEntriesParallelWithResize) {
263 PerThreadBumpPtrAllocator Allocator;
264 const size_t NumElements = 20000;
265 ConcurrentHashTableByPtr<std::string, String, PerThreadBumpPtrAllocator,
266 ConcurrentHashTableInfoByPtr<
267 std::string, String, PerThreadBumpPtrAllocator>>
268 HashTable(Allocator, 100);
269
270 // Check parallel insertion.
271 parallelFor(0, NumElements, [&](size_t I) {
272 BumpPtrAllocator &ThreadLocalAllocator =
273 Allocator.getThreadLocalAllocator();
274 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
275 std::string StringForElement = formatv("{0}", I);
276 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
277 EXPECT_TRUE(Entry.second);
278 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
279 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() >
280 AllocatedBytesAtStart);
281 });
282
283 std::string StatisticString;
284 raw_string_ostream StatisticStream(StatisticString);
285 HashTable.printStatistic(StatisticStream);
286
287 // Verifying that the table contains exactly the number of elements we
288 // inserted.
289 EXPECT_TRUE(StatisticString.find("Overall number of entries = 20000\n") !=
290 std::string::npos);
291
292 // Check parallel insertion of duplicates.
293 parallelFor(0, NumElements, [&](size_t I) {
294 BumpPtrAllocator &ThreadLocalAllocator =
295 Allocator.getThreadLocalAllocator();
296 size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated();
297 std::string StringForElement = formatv("{0}", I);
298 std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
299 EXPECT_FALSE(Entry.second);
300 EXPECT_TRUE(Entry.first->getKey() == StringForElement);
301 // Check no additional bytes were allocated for duplicate.
302 EXPECT_TRUE(ThreadLocalAllocator.getBytesAllocated() ==
303 AllocatedBytesAtStart);
304 });
305
306 // Check statistic.
307 // Verifying that the table contains exactly the number of elements we
308 // inserted.
309 EXPECT_TRUE(StatisticString.find("Overall number of entries = 20000\n") !=
310 std::string::npos);
311 }
312
313 } // namespace
314