[ADT] add FixedConcurrentHashTable class.

[avl]

Summary

This review is extracted from D96035.

It adds a hash table that could be filled asynchronously.
A possible use case for that kind of hashtable is keeping strings
(with possible additional data) and comparing them by
pointers comparisons. f.e. it might be used instead of
NonRelocatableStringpool which cannot be used in parallel.

The implementation of the hashmap is copied(with modifications)
from lld/COFF/DebugTypes.cpp.

[rnk]

@MaskRay, can you review this? I think you have been thinking the most about how to parallelize linkers, and what fundamental data structures are most important.

[MaskRay]

In D125979#3528140, @rnk wrote:

@MaskRay, can you review this? I think you have been thinking the most about how to parallelize linkers, and what fundamental data structures are most important.

Will try to do my best. I'll also need to spend some time on reading D96035...

[MaskRay]

LockFreeDataPool

The name is not descriptive. It misses the important words about "hash map". ConcurrentHashMap may be a better name.

The slab system appears to be the modification to lld/COFF/DebugTypes.cpp.
It provides limited growing capability when the capacity is hit.
There is a hard limit of 6 slabs, and report_fatal_error may eventually be called. Then why is reportWarning needed?
I think we should either implement a proper growing mechanism or just crash.

Does your application have a reasonable way estimating the capacity? Does it help to use HyperLogLog?
(There is a poor way to not implement a growing version: If we want to prevent a crash in a pathological case where the estimated capacity is insufficient and causes the concurrent hash map to crash, we can use something like lld::safeLldMain (llvm::CrashRecoveryContext).)

llvm/include/llvm/ADT/LockFreeDataPool.h

26 ↗

(On Diff #430692)

I think mentioning the origin in the summary is sufficient, no need to keep it in the comment.

58 ↗

(On Diff #430692)

Why so large?

159 ↗

(On Diff #430692)

relaxed load

229 ↗

(On Diff #430692)

MaxBucketLength needs an explanation.

236 ↗

(On Diff #430692)

Is this useful? See my main comment.

[MaskRay]

llvm/include/llvm/ADT/LockFreeDataPool.h

113 ↗

(On Diff #430692)

relaxed load on NextSlab and save it into a local variable.

[dblaikie]

(any chance we can avoid duplicating this, and instead refactor the lld one into LLVM and have lld use that one instead of using its own local copy?)

[avl]

The name is not descriptive. It misses the important words about "hash map". ConcurrentHashMap may be a better name.

The data structure which I need is a concurrent data pool of unique objects.
That pool should keep objects and matching objects should have the same entry.

The hash map is an implementation detail. The pool uses hash map to control the data entries. There might be used another(other than hash map) structure controlling pool entries.

Probably, it is possible to separate this LockFreeDataPool into two classes data pool and hash map.

The slab system appears to be the modification to lld/COFF/DebugTypes.cpp.
It provides limited growing capability when the capacity is hit.
There is a hard limit of 6 slabs, and report_fatal_error may eventually be called. Then why is reportWarning needed?
I think we should either implement a proper growing mechanism or just crash.

The best use case for that hash map is when it is allocated once and no growings are necessary. But, there are use cases when it is hard to estimate initial size. In such cases, without resizing, application will crash or need to waste memory(to allocate a huge amount of memory covering exceptional cases).

Slab system in this patch allows to resize hash map by the price of slower search(that is the source of restriction by the number of resizes). This allows to allocate smaller hash map initially and reallocate it for the exceptionally large cases. The purpose of the warning is to inform user that an exceptional case is hit.

Does your application have a reasonable way estimating the capacity?

I use an coefficient for incoming DWARF to calculate the size of hash map. In most cases it is quite accurate. But there are some exceptional cases when estimation is not accurate and then possibility to do resize helps.

Does it help to use HyperLogLog?

Let me examine this, please.

(There is a poor way to not implement a growing version: If we want to prevent a crash in a pathological case where the estimated capacity is insufficient and causes the concurrent hash map to crash, we can use something like lld::safeLldMain (llvm::CrashRecoveryContext).)

I will check it, thanks. Do you think it would be better than possibility to resize?

llvm/include/llvm/ADT/LockFreeDataPool.h

58 ↗

(On Diff #430692)

to avoid re-sizings for small sizes. It does not look to be too big value, but will do working with small sizes more smooth.

113 ↗

(On Diff #430692)

something like this ?:

Slab *Slab = CurSlab->NextSlab.load(std::memory_order_relaxed);

if (Slab == nullptr) {
      const std::lock_guard<std::mutex> lock(SlabsMutex);

      if (Slab  == nullptr)   <<<<<<<<<<<
        CurSlab->NextSlab = allocateNextSlab(Allocator);
    }
}

It looks like we could not save NextSlab into the local variable because CurSlab->NextSlab can change the value when we arrive at pointed line..

[avl]

In D125979#3529745, @dblaikie wrote:

(any chance we can avoid duplicating this, and instead refactor the lld one into LLVM and have lld use that one instead of using its own local copy?)

I thought about that. But the implementation from lld looks too specific for general implementation.
It uses knowledge about stored data:

1. It keeps data together with hash inside hash table. This is OK for 32-bit integer but it would not be OK for larger type.

2. It compares data to select which version should be stored. We need a way to do it or avoid it without introducing more checks.

if (!oldCell.isEmpty() >>>&& oldCell < newCell<<<)
  return idx;

I do not have effective way on how to put that behaviour in general implementation at the moment.
Probably, that might be done by inheritance and redefinition in child implementations.

[dblaikie]

In D125979#3532163, @avl wrote:

In D125979#3529745, @dblaikie wrote:

(any chance we can avoid duplicating this, and instead refactor the lld one into LLVM and have lld use that one instead of using its own local copy?)

I thought about that. But the implementation from lld looks too specific for general implementation.
It uses knowledge about stored data:

1. It keeps data together with hash inside hash table. This is OK for 32-bit integer but it would not be OK for larger type.

Other LLVM data structures make different choices based on the size of the content (eg: the default size of SmallVector varies depending on the size of the elements) - using traits or other template techniques seems suitable.

2. It compares data to select which version should be stored. We need a way to do it or avoid it without introducing more checks.

if (!oldCell.isEmpty() >>>&& oldCell < newCell<<<)
  return idx;

Yeah, some sort of trait could be used to implement that (but maybe there are other broader abstractions) - like maybe that functionality should stay out in lld, even if the data structure's moved into LLVM - lld could "insert, check that the thing was already present, then do the comparison/decide whether to overwrite" - doesn't sound like it'd be a performance issue.

[avl]

Ok, thanks. Will change review to use a general implementation in lld and DWARFLinker.

[avl]

addressed comments:

1. renamed LockFreeDataPool -> ConcurrentHashTable.
2. implemented support for both lld and DWARFLinker implementations.

[dblaikie]

llvm/include/llvm/ADT/ConcurrentHashTable.h

83

(similarly below/for the other ctor here)

117–118

It's pretty weird to have warnings coming out of data structures. @MaskRay would it be reasonable to remove these/replace them with some other tool if we're promoting this to a more general purpose data structure rather than something more special-case in lld?

315–316

This should probably be provided via specialization, rather than as a separately named type?

I guess it has different requirements for the type, by the looks of it? That's curious/maybe enough to warrant a separate name, I guess, though I'm not 100% sure.

324

generally operator== should be implemented as a non-member (so that implicit conversions are equally applied to the left and right hand operands) - maybe this whole specification area should be written less in terms of specific declarations that should be provided, and more in terms of code snippets that should be valid/have certain semantics? (that's how the C++ standard documents requirements on things like value types, iterator types, etc)

llvm/unittests/ADT/ConcurrentHashTableTest.cpp

44–46

[avl]

llvm/include/llvm/ADT/ConcurrentHashTable.h

117–118

Probably, instead of warning we can introduce method:

bool IsInGoodState () const {
  return CurSlabNum <= MaxNumberOfSlabs && !hasFullSlab;
}

the consumer could call this method somewhere and inform the user:

if (!HashTable.IsInGoodState()) {
    outs() << "Hash table is in suboptimal state";
}

?

315–316

They have different interface:

std::pair<KeyDataTy, bool> insert(KeyDataTy NewData)

and

std::pair<KeyDataTy *, bool> insert(AllocatorTy &Allocator, KeyTy Key)

Implementing this through the specialization looks to be more complex and it seems does not have benefits comparing to the variant with separately named types?

[dblaikie]

llvm/include/llvm/ADT/ConcurrentHashTable.h

117–118

Maybe? I'd be curious to hear from @MaskRay here, since I guess he wrote the original/had the original motivation for the warning.

315–316

Fair enough. I wonder if it'd be acceptable to have the hash table take the allocator as a ctor parameter (& then keep the same API otherwise) and store it, or if there are too many of these that the extra pointer member would be too costly.

Though coming back to the original comment - why is external allocation usage/recommendation related to the size of the keys/size of a pointer?

[avl]

llvm/include/llvm/ADT/ConcurrentHashTable.h

117–118

that is me, who introduced the warning. Original lld implementation does not have it.

My motivation is that it should be known somehow that hashtable is not in good state and it is necessary to revise initial size.

315–316

Fair enough. I wonder if it'd be acceptable to have the hash table take the allocator as a ctor parameter (& then keep the same API otherwise) and store it, or if there are too many of these that the extra pointer member would be too costly.

The reason is necessity to synchronize allocator.

The allocator may be passed as the ctor parameter if it would be able to work in multy-thread mode. This implementation assumes that allocator is not able to work in multi-thread mode. To properly working it requires that the same allocator is used from the same thread. In that case no need to synchronize allocator.

1. std::pair<KeyDataTy*, bool> insert(KeyTy Key)

The insert method might be called from different threads. if It would call to allocator stored in the constructor then we need to use mutex or to use special multi-thread implementation for the allocator.

2. std::pair<KeyDataTy *, bool> insert(AllocatorTy &Allocator, KeyTy Key)

This solution assumes that the same thread uses the same allocator. It allows not to synchronize allocators.

Though coming back to the original comment - why is external allocation usage/recommendation related to the size of the keys/size of a pointer?

entry size for the solution with external allocation could not be less than pointer(since each entry is a pointer to the externally allocated data).

entry size for the solution with allocating inside hash table can be less and then the table may have smaller size. It also does not need special allocator, since data are kept inside hash table.

We could not always keep data inside hash table: If data size is greater then pointer then each entry(even null) would occupy bigger size. That would result in a bigger hash table. It would also result in copying extra data, since data entries are passed by value in that case.

So if entry size is less than pointer then it would require less size and no additional allocator required when ConcurrentHashTable is used. If entry size is greater than pointer then less space is used(no need to allocate full data for null entries) and data copying is faster when ConcurrentHashTableExtAlloc is used.

[MaskRay]

llvm/include/llvm/ADT/ConcurrentHashTable.h

117–118

The root issue is that the patch does not implement proper grow/resize, so setting a capacity and having oversize warnings here look like hacks. For many general-purpose usages it's difficult to estimate the size beforehand, or without heavily refactoring the usage pattern. So I wish that we implement a proper resizable hashtable with amortized O(1) time complexity, not the current version which will be slow if the actual size is much more larger than the reserved capacity.

[avl]

llvm/include/llvm/ADT/ConcurrentHashTable.h

117–118

This is correct. This implementation is not a good choice for the case when it is difficult to estimate the size beforehand.

But this might be a good choice for the cases when such estimation is possible. F.e. lld/COFF already uses
this implementation even without the resizing feature. I used it for DWARF files. All clang/llvm binaries are processed
without warning(and far from the resizing limits). That means that estimations are quite accurate. Still, resizing feature might be helpful for exceptional cases.

The implementation from this patch has several advantages: it is fast and lightweight, it does not require extra memory for buckets, does not require locking table or buckets for most cases, and does not require any additional memory management for the most cases.

For the task when it is not possible to estimate the size beforehand - there should be used another implementation.

[avl]

addressed comments: removed warningHandler(added IsInSuboptimalState instead),
changed specification comments.

[avl]

removed resizing(as I am going to submit another resizeable solution),
refactored to have a single "insert" method.

[avl]

the patch with resizeable hashtable D132455

[avl]

Performance results for this patch https://reviews.llvm.org/file/data/a36xmbx43mp35xx5rznf/PHID-FILE-lncmoijytnb3gn4gjrii/Performance.pdf (Collected by utility from : D132548)

[avl]

closed in favor of D132455

llvm/include/llvm/ADT/ConcurrentHashTable.h

+//===- ConcurrentHashTable.h ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_CONCURRENTHASHTABLE_H
+#define LLVM_ADT_CONCURRENTHASHTABLE_H
+
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/NativeFormatting.h"
+#include "llvm/Support/WithColor.h"
+#include <atomic>
+#include <mutex>
+
+namespace llvm {
+
+/// ConcurrentHashTable - is a partially resizeable lock-free hashtable.
+///
+/// A concurrent hash table for global type hashing. It is based on this paper:
+/// Concurrent Hash Tables: Fast and General(?)!
+/// https://dl.acm.org/doi/10.1145/3309206
+///
+/// This hash table is meant to be used in two phases:
+/// 1. concurrent insertions
+/// 2. concurrent reads
+/// It does not support lookup, deletion, or rehashing. It uses linear probing.
+///
+/// The paper describes storing a key-value pair in two machine words.
+/// ConcurrentHashTable: keeps a KeyDataTy(which is a key-value pair).
+/// ConcurrentHashTableExtAlloc: keeps a pointer to the KeyDataTy class
+/// (which is a key-value pair), whose data are allocated and kept by the
+/// external allocator.
+
+template <class MapEntryTy> class ConcurrentHashTableBase {
+public:
+  /// Initialize the table with the given size.
+  void init(size_t InitialSize) {
+    TableSize = NextPowerOf2(InitialSize);
+    TableSize = std::max(TableSize, (size_t)4096);
+    HashMask = TableSize - 1;
+    CurSlabNum = 0;
+    FirstSlab = allocateNextSlab();
+  }
+
+  /// Print information about current state of hash table structures.
+  void printStatistic(raw_ostream &OS) {
+    OS << "\nConcurrentHashTable:\n";
+    OS << "\nNumber of slabs: " << CurSlabNum;
+    OS << "\nNumber of elements per slab: " << TableSize;
+    OS << "\nFull size of hash table: "
+       << CurSlabNum * TableSize * sizeof(MapEntryTy) << " bytes \n";
+
+    size_t OverallNumberOfUsedEntries = 0;
+    for (Slab *CurSlab = FirstSlab; CurSlab != nullptr;
+         CurSlab = CurSlab->NextSlab) {
+      std::pair<size_t, size_t> Statistic = getNumberOfEntriesForSlab(CurSlab);
+      OS << "\n Slab depth: " << CurSlab->SlabDepth;
+      OS << "\n Slab fullness: ";
+      llvm::write_double(OS, ((float)Statistic.first / (float)TableSize),
+                         FloatStyle::Percent);
+      OS << "\n Slab longest bucket: " << Statistic.second;
+      OS << "\n";
+
+      OverallNumberOfUsedEntries += Statistic.first;
+    }
+
+    OS << "\nOverall number of used elements: " << OverallNumberOfUsedEntries;
+    OS << "\nOverall fullness of hash table: ";
+    llvm::write_double(
+        OS,
+        ((float)OverallNumberOfUsedEntries / ((float)CurSlabNum * TableSize)),
+        FloatStyle::Percent);
+  }
+
+protected:
+  ConcurrentHashTableBase(
+      std::function<void(const char *message)> WarningHandler = nullptr)
+      : WarningHandler(WarningHandler) {}
+
+  struct Slab {
+    std::atomic<MapEntryTy> *Table = nullptr;
+    std::atomic<Slab *> NextSlab = nullptr;
+    size_t SlabDepth = 0;
+  };
+
+  // \returns next available slab, allocate a new one if necessary.
+  Slab *getNextSlab(Slab *CurSlab) {
+    if (CurSlab->NextSlab.load(std::memory_order_relaxed) == nullptr) {
+      const std::lock_guard<std::mutex> lock(SlabsMutex);
+
+      if (CurSlab->NextSlab.load(std::memory_order_relaxed) == nullptr)
+        CurSlab->NextSlab = allocateNextSlab();
+    }
+
+    return CurSlab->NextSlab;
+  }
+
+  // Allocate new slab.
+  Slab *allocateNextSlab() {
+    Slab *NewSlab = Allocator.template Allocate<Slab>();
+
+    NewSlab->Table =
+        Allocator.template Allocate<std::atomic<MapEntryTy>>(TableSize);
+    memset(NewSlab->Table, 0, TableSize * sizeof(MapEntryTy));
+    NewSlab->NextSlab = nullptr;
+
+    NewSlab->SlabDepth = CurSlabNum++;
+
+    if (CurSlabNum > (MaxNumberOfSlabs + 2))
+      report_fatal_error("Hash table is full.");
+    else if (CurSlabNum > MaxNumberOfSlabs)
+      reportWarning("Too many slabs. Consider increasing initial size or "
+                    "changing hash function.");
+
+    return NewSlab;
+  }
+
+  // \returns number of used elements inside slab and the length of the longest
+  // bucket inside slab.
+  std::pair<size_t, size_t> getNumberOfEntriesForSlab(Slab *CurSlab) {
+    size_t NumberOfElements = 0;
+    size_t MaxBucketLength = 0;
+    size_t CurBucketLength = 0;
+    bool prevEntryIsNull = true;
+    for (size_t CurIdx = 0; CurIdx < TableSize; CurIdx++) {
+      if (!isNull(CurSlab->Table[CurIdx].load(std::memory_order_relaxed))) {
+        NumberOfElements++;
+
+        if (prevEntryIsNull)
+          CurBucketLength = 0;
+        else
+          CurBucketLength++;
+        prevEntryIsNull = false;
+      } else {
+        if (!prevEntryIsNull)
+          MaxBucketLength = std::max(MaxBucketLength, CurBucketLength);
+        prevEntryIsNull = true;
+      }
+    }
+
+    return std::make_pair(NumberOfElements, MaxBucketLength);
+  }
+
+  // Call warning handler.
+  void reportWarning(const char *message) {
+    if (WarningIsReported)
+      return;
+
+    if (!WarningHandler)
+      return;
+
+    WarningIsReported = true;
+    WarningHandler(message);
+  }
+
+  template <typename T>
+  typename std::enable_if_t<std::is_pointer<T>::value, bool> isNull(T Data) {
+    return Data == nullptr;
+  }
+
+  template <typename T>
+  typename std::enable_if_t<!std::is_pointer<T>::value, bool> isNull(T Data) {
+    return Data.isNull();
+  }
+
+  // This allocator is used to allocate space for the hash table entries.
+  BumpPtrAllocator Allocator;
+
+  // Size of single slab.
+  size_t TableSize = 0;
+
+  // Mask, used to convert hash_code into the hash table index.
+  size_t HashMask = 0;
+
+  // Max length of the continuous sequence of non-null entries.
+  // If length of bucket exceeds MaxBucketLength then new slab would be
+  // allocated.
+  const size_t MaxBucketLength = 100;
+
+  // If number of slabs exceeds (MaxNumberOfSlabs + 2) the fatal error will be
+  // raised.
+  const size_t MaxNumberOfSlabs = 3;
+
+  // Guard for slabs.
+  std::mutex SlabsMutex;
+
+  // Pointer to the first slab.
+  Slab *FirstSlab = nullptr;
+
+  // Number of allocated slabs.
+  size_t CurSlabNum = 0;
+
+  // Handler to report warnings.
+  std::function<void(const char *message)> WarningHandler;
+  bool WarningIsReported = false;
+};
+
+/// ConcurrentHashTable:
+///
+/// It is recommended to use ConcurrentHashTable if sizeof(KeyDataTy) <=
+/// sizeof(pointer).
+///
+/// There should be implemented:
+///
+/// hash_code hash_value(KeyTy Key);
+/// bool KeyTy::operator==(const KeyTy &Other) const;
+/// KeyTy KeyDataTy::key() const;
+/// bool KeyDataTy::isNull() const; /* Check that all data bits are zero */
+///
+/// If hash entries should be ordered then following should also be implemented:
+///
+/// bool KeyDataTy::lessThen(const KeyDataTy&) const;
+///
+/// KeyDataTy should match with requirements of atomic types(size and
+/// alignment).
+
+template <class KeyTy, class KeyDataTy>
+class ConcurrentHashTable : public ConcurrentHashTableBase<KeyDataTy> {
+public:
+  ConcurrentHashTable(
+      std::function<void(const char *message)> WarningHandler = nullptr)
+      : ConcurrentHashTableBase<KeyDataTy>(WarningHandler) {}
+
+  /// Insert new entry \p Data or return already existing entry.
+  ///
+  /// \returns entry and "true" if an entry is just inserted or
+  /// "false" if an entry already exists.
+  std::pair<KeyDataTy, bool> insert(KeyDataTy NewData) {
+    assert((!this->isNull(NewData)) && "Null entry is inserted.");
+    assert(this->TableSize > 0 && "hashtable is not initialised");
+    return insert(this->FirstSlab, hash_value(NewData.key()) & this->HashMask,
+                  NewData);
+  }
+
+protected:
+  template <typename T>
+  using haslessThen =
+      decltype(std::declval<T &>().lessThen(std::declval<T &>()));
+
+  template <typename T>
+  typename std::enable_if_t<is_detected<haslessThen, T>::value, bool>
+  needToOverwriteEntry(T NewData, T Candidate) {
+    return NewData.lessThen(Candidate);
+  }
+
+  template <typename T>
+  constexpr typename std::enable_if_t<!is_detected<haslessThen, T>::value, bool>
+  needToOverwriteEntry(T, T) {
+    return false;
+  }
+
+  // Insert \p NewData into the specified \p CurSlab. Start probing from
+  // the \p StartIdx. Allocate new slab if specified slab \p CurSlab is full.
+  std::pair<KeyDataTy, bool>
+  insert(typename ConcurrentHashTableBase<KeyDataTy>::Slab *CurSlab,
+         uint32_t StartIdx, KeyDataTy NewData) {
+    // Do a linear probe starting at startIdx.
+    uint32_t Idx = StartIdx;
+    uint32_t CurBucketSize = 0;
+
+    while (true) {
+      // Run a compare and swap loop. There are three cases:
+      // - cell is empty: CAS into place and return
+      // - cell has matching key, return cell`s data
+      // - cell has non-matching key: hash collision, probe next cell
+      KeyDataTy Candidate = CurSlab->Table[Idx].load(std::memory_order_relaxed);
+      if (ConcurrentHashTableBase<KeyDataTy>::isNull(Candidate)) {
+        if (CurBucketSize >= this->MaxBucketLength)
+          // insert data into the new slab.
+          return insert(
+              ConcurrentHashTableBase<KeyDataTy>::getNextSlab(CurSlab),
+              StartIdx, NewData);
+
+        if (CurSlab->Table[Idx].compare_exchange_weak(Candidate, NewData))
+          return std::make_pair(NewData, true);
+        continue;
+      }
+
+      if (Candidate.key() == NewData.key()) {
+        // Check order and overwrite entry if necessary.
+        if (needToOverwriteEntry(NewData, Candidate)) {
+          if (CurSlab->Table[Idx].compare_exchange_weak(Candidate, NewData))
+            return std::make_pair(NewData, true);
+
+          continue;
+        }
+
+        return std::make_pair(Candidate, false);
+      }
+
+      ++CurBucketSize;
+      // Advance the probe. Wrap around to the beginning if we run off the end.
+      ++Idx;
+
+      Idx = Idx == this->TableSize ? 0 : Idx;
+      if (Idx == StartIdx) {
+        ConcurrentHashTableBase<KeyDataTy>::reportWarning(
+            "Slab is 100% full. Consider increasing initial size.");
+
+        return insert(ConcurrentHashTableBase<KeyDataTy>::getNextSlab(CurSlab),
+                      StartIdx, NewData);
+      }
+    }
+    llvm_unreachable("left infloop");
+  }
+};
+
+/// ConcurrentHashTableExtAlloc:
+///
+/// It is recommended to use ConcurrentHashTableExtAlloc if sizeof(KeyDataTy) >
+/// sizeof(pointer).
+///
+/// Insertions into the internal hash table are lock-free, and
+/// allocations are done using an external non-mt-safe data pool.
+///
+/// There should be implemented:
+///
+/// hash_code hash_value(KeyTy Key);
+/// bool KeyTy::operator==(const KeyTy &Other) const;
+/// KeyTy KeyDataTy::key() const;
+/// static KeyDataTy* KeyDataTy::create (KeyTy Key, AllocatorTy* Allocator);
+
+template <class KeyTy, class KeyDataTy, class AllocatorTy = BumpPtrAllocator>
+class ConcurrentHashTableExtAlloc
+    : public ConcurrentHashTableBase<KeyDataTy *> {
+public:
+  ConcurrentHashTableExtAlloc(
+      std::function<void(const char *message)> WarningHandler = nullptr)
+      : ConcurrentHashTableBase<KeyDataTy *>(WarningHandler) {}
+
+  /// Insert new entry allocated by \p Allocator for specified \p Key or
+  /// return already existing entry which key matched with specified \p Key.
+  ///
+  /// \returns entry and "true" if an entry is just inserted or
+  /// "false" if an entry already exists.
+  std::pair<KeyDataTy *, bool> insert(AllocatorTy &Allocator, KeyTy Key) {
+    assert(this->TableSize > 0 && "hashtable is not initialised");
+    return insert(Allocator, this->FirstSlab, hash_value(Key) & this->HashMask,
+                  Key, nullptr);
+  }
+
+protected:
+  // Insert \p NewData into the specified \p CurSlab. Start probing from
+  // the \p StartIdx. Allocate new slab if specified slab \p CurSlab is full.
+  std::pair<KeyDataTy *, bool>
+  insert(AllocatorTy &Allocator,
+         typename ConcurrentHashTableBase<KeyDataTy *>::Slab *CurSlab,
+         uint32_t StartIdx, KeyTy Key, KeyDataTy *NewData) {
+    // Do a linear probe starting at startIdx.
+    uint32_t Idx = StartIdx;
+    uint32_t CurBucketSize = 0;
+
+    while (true) {
+      // Run a compare and swap loop. There are three cases:
+      // - cell is empty: CAS into place and return
+      // - cell has matching key, return cell`s data
+      // - cell has non-matching key: hash collision, probe next cell
+      KeyDataTy *Candidate =
+          CurSlab->Table[Idx].load(std::memory_order_relaxed);
+      if (ConcurrentHashTableBase<KeyDataTy *>::isNull(Candidate)) {
+        if (CurBucketSize >= this->MaxBucketLength)
+          // insert data into the new slab.
+          return insert(
+              Allocator,
+              ConcurrentHashTableBase<KeyDataTy *>::getNextSlab(CurSlab),
+              StartIdx, Key, NewData);
+
+        if (ConcurrentHashTableBase<KeyDataTy *>::isNull(NewData))
+          NewData = KeyDataTy::create(Key, Allocator);
+
+        if (CurSlab->Table[Idx].compare_exchange_weak(Candidate, NewData))
+          return std::make_pair(NewData, true);
+        continue;
+      }
+
+      if (Candidate->key() == Key)
+        return std::make_pair(Candidate, false);
+
+      ++CurBucketSize;
+      // Advance the probe. Wrap around to the beginning if we run off the end.
+      ++Idx;
+
+      Idx = Idx == this->TableSize ? 0 : Idx;
+      if (Idx == StartIdx) {
+        ConcurrentHashTableBase<KeyDataTy *>::reportWarning(
+            "Slab is 100% full. Consider increasing initial size.");
+
+        return insert(
+            Allocator,
+            ConcurrentHashTableBase<KeyDataTy *>::getNextSlab(CurSlab),
+            StartIdx, Key, NewData);
+      }
+    }
+    llvm_unreachable("left infloop");
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_CONCURRENTHASHTABLE_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   APSIntTest.cpp
   ArrayRefTest.cpp
   BitFieldsTest.cpp
   BitmaskEnumTest.cpp
   BitVectorTest.cpp
   BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
   CoalescingBitVectorTest.cpp
+  ConcurrentHashTableTest.cpp
   CombinationGeneratorTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   DirectedGraphTest.cpp
   EnumeratedArrayTest.cpp

llvm/unittests/ADT/ConcurrentHashTableTest.cpp

+//===- ConcurrentHashTableTest.cpp - ConcurrentHashTable unit tests -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/ConcurrentHashTable.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/Parallel.h"
+#include "gtest/gtest.h"
+#include <limits>
+#include <vector>
+using namespace llvm;
+
+namespace {
+
+class Int {
+public:
+  Int(uint32_t Data) : Data(Data | 0x80000000) {}
+
+  uint32_t key() { return Data & 0x7FFFFFFF; }
+
+  bool isNull() const { return Data == 0; }
+
+  bool operator==(const Int &Other) const { return Data == Other.Data; }
+
+protected:
+  uint32_t Data;
+};
+
+class OrderedInt {
+public:
+  OrderedInt(uint32_t Data, uint32_t Order)
+      : Data(Data | 0x80000000), Order(Order) {}
+
+  uint32_t key() { return Data & 0x7FFFFFFF; }
+  uint32_t order() { return Order; }
+
+  bool isNull() const { return Data == 0 && Order == 0; }
+
+  bool operator==(const OrderedInt &Other) const {
+    return Data == Other.Data && Order == Other.Order;
+  }
+
+  bool lessThen(const OrderedInt &Other) const { return Order < Other.Order; }
+
+protected:
+  uint32_t Data;
+  uint32_t Order;
+};
+
+class String {
+public:
+  static String *create(StringRef Key, BumpPtrAllocator &Allocator) {
+    return new (Allocator) String(Key);
+  }
+
+  StringRef key() { return Data; }
+
+protected:
+  String(StringRef Data) : Data(Data) {}
+  std::string Data;
+};
+
+TEST(ConcurrentHashTableTest, AddIntEntries) {
+  ConcurrentHashTable<uint32_t, Int> HashTable;
+
+  HashTable.init(10);
+
+  std::pair<Int, bool> res1 = HashTable.insert(Int(1));
+  // Check entry is inserted.
+  EXPECT_TRUE(res1.first.key() == 1);
+  EXPECT_TRUE(res1.second);
+
+  std::pair<Int, bool> res2 = HashTable.insert(Int(2));
+  // Check old entry is still valid.
+  EXPECT_TRUE(res1.first.key() == 1);
+  // Check new entry is inserted.
+  EXPECT_TRUE(res2.first.key() == 2);
+  EXPECT_TRUE(res2.second);
+  // Check new and old entries are not the equal.
+  EXPECT_FALSE(res1.first == res2.first);
+
+  std::pair<Int, bool> res3 = HashTable.insert(Int(3));
+  // Check one more entry is inserted.
+  EXPECT_TRUE(res3.first.key() == 3);
+  EXPECT_TRUE(res3.second);
+
+  std::pair<Int, bool> res4 = HashTable.insert(Int(1));
+  // Check duplicated entry is inserted.
+  EXPECT_TRUE(res4.first.key() == 1);
+  EXPECT_FALSE(res4.second);
+  // Check duplicated entry matches with the first one.
+  EXPECT_TRUE(res1.first == res4.first);
+
+  // Check first entry is still valid.
+  EXPECT_TRUE(res1.first.key() == 1);
+
+  // Check statistic.
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  EXPECT_TRUE(StatisticString.find("ConcurrentHashTable:") !=
+              std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Number of slabs: 1") != std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Slab depth: 0") != std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Slab fullness: 0.07%") !=
+              std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Overall number of used elements: 3") !=
+              std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Overall fullness of hash table: 0.07%") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddOrderedIntEntries) {
+  ConcurrentHashTable<uint32_t, OrderedInt> HashTable;
+
+  HashTable.init(10);
+
+  std::pair<OrderedInt, bool> res = HashTable.insert(OrderedInt(1, 2));
+  // Check entry is inserted.
+  EXPECT_TRUE(res.first.key() == 1);
+  EXPECT_TRUE(res.first.order() == 2);
+  EXPECT_TRUE(res.second);
+
+  res = HashTable.insert(OrderedInt(1, 3));
+  // Check entry is unchanged.
+  EXPECT_TRUE(res.first.key() == 1);
+  EXPECT_TRUE(res.first.order() == 2);
+  EXPECT_FALSE(res.second);
+
+  res = HashTable.insert(OrderedInt(1, 2));
+  // Check entry is unchanged.
+  EXPECT_TRUE(res.first.key() == 1);
+  EXPECT_TRUE(res.first.order() == 2);
+  EXPECT_FALSE(res.second);
+
+  res = HashTable.insert(OrderedInt(1, 1));
+  // Check entry is overwritten.
+  EXPECT_TRUE(res.first.key() == 1);
+  EXPECT_TRUE(res.first.order() == 1);
+  EXPECT_TRUE(res.second);
+}
+
+TEST(ConcurrentHashTableTest, AddIntEntriesParallel) {
+  ConcurrentHashTable<uint32_t, Int> HashTable;
+
+  HashTable.init(5000);
+
+  // Number of elements exceeds original size, thus hashtable
+  // should be resized.
+  const size_t NumElements = 10000;
+
+  // Check parallel insertion.
+  parallelForEachN(0, NumElements, [&](size_t I) {
+    std::pair<Int, bool> Entry = HashTable.insert(Int(I));
+    EXPECT_TRUE(Entry.second);
+    EXPECT_TRUE(Entry.first.key() == I);
+  });
+
+  // Check parallel insertion of duplicates.
+  parallelForEachN(0, NumElements, [&](size_t I) {
+    std::pair<Int, bool> Entry = HashTable.insert(Int(I));
+    EXPECT_FALSE(Entry.second);
+    EXPECT_TRUE(Entry.first.key() == I);
+  });
+
+  // Check statistic.
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  EXPECT_TRUE(StatisticString.find("Number of slabs: 2") != std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Overall number of used elements: 10000") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddStringEntries) {
+  BumpPtrAllocator Allocator;
+  ConcurrentHashTableExtAlloc<StringRef, String, BumpPtrAllocator> HashTable;
+
+  HashTable.init(10);
+
+  std::pair<String *, bool> res1 = HashTable.insert(Allocator, "1");
+  // Check entry is inserted.
+  EXPECT_TRUE(res1.first->key() == "1");
+  EXPECT_TRUE(res1.second);
+
+  std::pair<String *, bool> res2 = HashTable.insert(Allocator, "2");
+  // Check old entry is still valid.
+  EXPECT_TRUE(res1.first->key() == "1");
+  // Check new entry is inserted.
+  EXPECT_TRUE(res2.first->key() == "2");
+  EXPECT_TRUE(res2.second);
+  // Check new and old entries use different memory.
+  EXPECT_TRUE(res1.first != res2.first);
+
+  std::pair<String *, bool> res3 = HashTable.insert(Allocator, "3");
+  // Check one more entry is inserted.
+  EXPECT_TRUE(res3.first->key() == "3");
+  EXPECT_TRUE(res3.second);
+
+  std::pair<String *, bool> res4 = HashTable.insert(Allocator, "1");
+  // Check duplicated entry is inserted.
+  EXPECT_TRUE(res4.first->key() == "1");
+  EXPECT_FALSE(res4.second);
+  // Check duplicated entry matches with the first one.
+  EXPECT_TRUE(res1.first == res4.first);
+
+  // Check first entry is still valid.
+  EXPECT_TRUE(res1.first->key() == "1");
+
+  // Check data was allocated by allocator.
+  EXPECT_TRUE(Allocator.getBytesAllocated() > 0);
+
+  // Check statistic.
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  EXPECT_TRUE(StatisticString.find("ConcurrentHashTable:") !=
+              std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Number of slabs: 1") != std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Slab depth: 0") != std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Slab fullness: 0.07%") !=
+              std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Overall number of used elements: 3") !=
+              std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Overall fullness of hash table: 0.07%") !=
+              std::string::npos);
+}
+
+TEST(ConcurrentHashTableTest, AddStringEntriesParallel) {
+  ConcurrentHashTableExtAlloc<StringRef, String, BumpPtrAllocator> HashTable;
+
+  HashTable.init(5000);
+
+  // Number of elements exceeds original size, thus hashtable
+  // should be resized.
+  const size_t NumElements = 10000;
+  BumpPtrAllocator Allocators[NumElements];
+
+  // Check parallel insertion.
+  parallelForEachN(0, NumElements, [&](size_t I) {
+    std::string StringForElement = formatv("{0}", I);
+    std::pair<String *, bool> Entry =
+        HashTable.insert(Allocators[I], StringForElement);
+    EXPECT_TRUE(Entry.second);
+    EXPECT_TRUE(Entry.first->key() == StringForElement);
+    EXPECT_TRUE(Allocators[I].getBytesAllocated() > 0);
+  });
+
+  // Check parallel insertion of duplicates.
+  parallelForEachN(0, NumElements, [&](size_t I) {
+    size_t BytesAllocated = Allocators[I].getBytesAllocated();
+    std::string StringForElement = formatv("{0}", I);
+    std::pair<String *, bool> Entry =
+        HashTable.insert(Allocators[I], StringForElement);
+    EXPECT_FALSE(Entry.second);
+    EXPECT_TRUE(Entry.first->key() == StringForElement);
+    // Check no additional bytes were allocated for duplicate.
+    EXPECT_TRUE(Allocators[I].getBytesAllocated() == BytesAllocated);
+  });
+
+  // Check statistic.
+  std::string StatisticString;
+  raw_string_ostream StatisticStream(StatisticString);
+  HashTable.printStatistic(StatisticStream);
+
+  EXPECT_TRUE(StatisticString.find("Number of slabs: 2") != std::string::npos);
+  EXPECT_TRUE(StatisticString.find("Overall number of used elements: 10000") !=
+              std::string::npos);
+}
+
+} // end anonymous namespace