llvm/unittests/ADT/ConcurrentHashtableTest.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-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> ExtraData;
  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([&]() {
  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
  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
 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
 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
 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