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