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: |
24 | String() {} |
25 | const std::string &getKey() const { return Data; } |
26 | |
27 | template <typename AllocatorTy> |
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: |
35 | String(const std::string &Num) { Data += Num; } |
36 | |
37 | std::string Data; |
38 | std::array<char, 0x20> ; |
39 | }; |
40 | |
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(f: [&]() { |
53 | size_t AllocatedBytesAtStart = Allocator.getBytesAllocated(); |
54 | std::pair<String *, bool> res1 = HashTable.insert(NewValue: "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(NewValue: "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(NewValue: "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(NewValue: "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(OS&: StatisticStream); |
90 | |
91 | EXPECT_TRUE(StatisticString.find("Overall number of entries = 3\n" ) != |
92 | std::string::npos); |
93 | }); |
94 | } |
95 | |
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(f: [&]() { |
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(Fmt: "{0}" , Vals&: I); |
115 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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(OS&: 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(Fmt: "{0}" , Vals&: I); |
137 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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 | |
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(f: [&]() { |
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(Fmt: "{0} {1}" , Vals&: I, Vals: I + 100); |
173 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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(OS&: 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(Fmt: "{0} {1}" , Vals&: I, Vals: I + 100); |
195 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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 | |
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(Begin: 0, End: NumElements, Fn: [&](size_t I) { |
221 | BumpPtrAllocator &ThreadLocalAllocator = |
222 | Allocator.getThreadLocalAllocator(); |
223 | size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated(); |
224 | std::string StringForElement = formatv(Fmt: "{0}" , Vals&: I); |
225 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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(OS&: 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(Begin: 0, End: NumElements, Fn: [&](size_t I) { |
243 | BumpPtrAllocator &ThreadLocalAllocator = |
244 | Allocator.getThreadLocalAllocator(); |
245 | size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated(); |
246 | std::string StringForElement = formatv(Fmt: "{0}" , Vals&: I); |
247 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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 | |
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(Begin: 0, End: NumElements, Fn: [&](size_t I) { |
272 | BumpPtrAllocator &ThreadLocalAllocator = |
273 | Allocator.getThreadLocalAllocator(); |
274 | size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated(); |
275 | std::string StringForElement = formatv(Fmt: "{0}" , Vals&: I); |
276 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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(OS&: 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(Begin: 0, End: NumElements, Fn: [&](size_t I) { |
294 | BumpPtrAllocator &ThreadLocalAllocator = |
295 | Allocator.getThreadLocalAllocator(); |
296 | size_t AllocatedBytesAtStart = ThreadLocalAllocator.getBytesAllocated(); |
297 | std::string StringForElement = formatv(Fmt: "{0}" , Vals&: I); |
298 | std::pair<String *, bool> Entry = HashTable.insert(NewValue: 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 | |