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