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