[WIP][ADT] Utility for comparision of hashtables implementation.

[avl]

Summary

NOT FOR INTEGRATION. FOR INFORMATIONAL PURPOSES ONLY.

The utility allows to compare performance and memory requirements
for following hashtables: ConcurrentHashTable, Intel TBB concurrent_unordered_map, libcuckoo cuckoohash_map, std::unordered_map, llvm::DenseMap, llvm DenseMap, lldb ConstString, llvm StringMap, TrieRawHashMap.

To obtain Intel threading building block library visit https://github.com/oneapi-src/oneTBB.
Build library according to the instructions.
Add following into the llvm/tools/check-hashtable/CMakeLists.txt

include_directories( oneTBB/install/include )

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wl,oneTBB/install/lib/libtbb.so ")

To obtain libcuckoo library visit https://github.com/efficient/libcuckoo
Build library according to the instructions.
Add following into the llvm/tools/check-hashtable/CMakeLists.txt

include_directories( libcuckoo/install/include )

Depends On D132455, D142318, D133714, D133715

[avl]

rebased.

[avl]

rebased

[avl]

added HashMappedTrie to the set of hashtables to compare.

[avl]

rebased. added test set - dwarffile.

llvm/tools/check-hashtable/CMakeLists.txt

+set(LLVM_TARGET_DEFINITIONS Options.td)
+tablegen(LLVM Options.inc -gen-opt-parser-defs)
+add_public_tablegen_target(CheckHashtableTableGen)
+
+include_directories( /home/avl/oneTBB/include /home/avl/libcuckoo/install/include )
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wl,/home/avl/oneTBB/gnu_11.3_cxx11_64_release/libtbb.so ")
+
+set(LLVM_ENABLE_RTTI ON)
+set(LLVM_ENABLE_EH ON)
+
+set(LLVM_LINK_COMPONENTS
+  DebugInfoDWARF
+  Object
+  Option
+  Support
+  AllTargetsCodeGens
+  AllTargetsDescs
+  AllTargetsInfos
+  )
+
+add_llvm_tool(check-hashtable
+  check-hashtable.cpp
+  ConstString.cpp
+
+  DEPENDS
+  intrinsics_gen
+  ${tablegen_deps}
+  )

llvm/tools/check-hashtable/ConstString.h

+//===-- ConstString.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 LLDB_UTILITY_CONSTSTRING_H
+#define LLDB_UTILITY_CONSTSTRING_H
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/FormatVariadic.h"
+
+#include <cstddef>
+
+namespace llvm {
+class raw_ostream;
+}
+
+namespace check {
+
+/// \class ConstString ConstString.h "lldb/Utility/ConstString.h"
+/// A uniqued constant string class.
+///
+/// Provides an efficient way to store strings as uniqued strings. After the
+/// strings are uniqued, finding strings that are equal to one another is very
+/// fast as just the pointers need to be compared. It also allows for many
+/// common strings from many different sources to be shared to keep the memory
+/// footprint low.
+///
+/// No reference counting is done on strings that are added to the string
+/// pool, once strings are added they are in the string pool for the life of
+/// the program.
+class ConstString {
+public:
+  /// Default constructor
+  ///
+  /// Initializes the string to an empty string.
+  ConstString() = default;
+
+  explicit ConstString(const llvm::StringRef &s);
+
+  /// Construct with C String value
+  ///
+  /// Constructs this object with a C string by looking to see if the
+  /// C string already exists in the global string pool. If it doesn't
+  /// exist, it is added to the string pool.
+  ///
+  /// \param[in] cstr
+  ///     A NULL terminated C string to add to the string pool.
+  explicit ConstString(const char *cstr);
+
+  /// Construct with C String value with max length
+  ///
+  /// Constructs this object with a C string with a length. If \a max_cstr_len
+  /// is greater than the actual length of the string, the string length will
+  /// be truncated. This allows substrings to be created without the need to
+  /// NULL terminate the string as it is passed into this function.
+  ///
+  /// \param[in] cstr
+  ///     A pointer to the first character in the C string. The C
+  ///     string can be NULL terminated in a buffer that contains
+  ///     more characters than the length of the string, or the
+  ///     string can be part of another string and a new substring
+  ///     can be created.
+  ///
+  /// \param[in] max_cstr_len
+  ///     The max length of \a cstr. If the string length of \a cstr
+  ///     is less than \a max_cstr_len, then the string will be
+  ///     truncated. If the string length of \a cstr is greater than
+  ///     \a max_cstr_len, then only max_cstr_len bytes will be used
+  ///     from \a cstr.
+  explicit ConstString(const char *cstr, size_t max_cstr_len);
+
+  /// C string equality binary predicate function object for ConstString
+  /// objects.
+  struct StringIsEqual {
+    /// C equality test.
+    ///
+    /// Two C strings are equal when they are contained in ConstString objects
+    /// when their pointer values are equal to each other.
+    ///
+    /// \return
+    ///     Returns \b true if the C string in \a lhs is equal to
+    ///     the C string value in \a rhs, \b false otherwise.
+    bool operator()(const char *lhs, const char *rhs) const {
+      return lhs == rhs;
+    }
+  };
+
+  /// Convert to bool operator.
+  ///
+  /// This allows code to check a ConstString object to see if it contains a
+  /// valid string using code such as:
+  ///
+  /// \code
+  /// ConstString str(...);
+  /// if (str)
+  /// { ...
+  /// \endcode
+  ///
+  /// \return
+  ///     /b True this object contains a valid non-empty C string, \b
+  ///     false otherwise.
+  explicit operator bool() const { return !IsEmpty(); }
+
+  /// Equal to operator
+  ///
+  /// Returns true if this string is equal to the string in \a rhs. This
+  /// operation is very fast as it results in a pointer comparison since all
+  /// strings are in a uniqued in a global string pool.
+  ///
+  /// \param[in] rhs
+  ///     Another string object to compare this object to.
+  ///
+  /// \return
+  ///     true if this object is equal to \a rhs.
+  ///     false if this object is not equal to \a rhs.
+  bool operator==(ConstString rhs) const {
+    // We can do a pointer compare to compare these strings since they must
+    // come from the same pool in order to be equal.
+    return m_string == rhs.m_string;
+  }
+
+  /// Equal to operator against a non-ConstString value.
+  ///
+  /// Returns true if this string is equal to the string in \a rhs. This
+  /// overload is usually slower than comparing against a ConstString value.
+  /// However, if the rhs string not already a ConstString and it is impractical
+  /// to turn it into a non-temporary variable, then this overload is faster.
+  ///
+  /// \param[in] rhs
+  ///     Another string object to compare this object to.
+  ///
+  /// \return
+  ///     \b true if this object is equal to \a rhs.
+  ///     \b false if this object is not equal to \a rhs.
+  bool operator==(const char *rhs) const {
+    // ConstString differentiates between empty strings and nullptr strings, but
+    // StringRef doesn't. Therefore we have to do this check manually now.
+    if (m_string == nullptr && rhs != nullptr)
+      return false;
+    if (m_string != nullptr && rhs == nullptr)
+      return false;
+
+    return GetStringRef() == rhs;
+  }
+
+  /// Not equal to operator
+  ///
+  /// Returns true if this string is not equal to the string in \a rhs. This
+  /// operation is very fast as it results in a pointer comparison since all
+  /// strings are in a uniqued in a global string pool.
+  ///
+  /// \param[in] rhs
+  ///     Another string object to compare this object to.
+  ///
+  /// \return
+  ///     \b true if this object is not equal to \a rhs.
+  ///     \b false if this object is equal to \a rhs.
+  bool operator!=(ConstString rhs) const { return m_string != rhs.m_string; }
+
+  /// Not equal to operator against a non-ConstString value.
+  ///
+  /// Returns true if this string is not equal to the string in \a rhs. This
+  /// overload is usually slower than comparing against a ConstString value.
+  /// However, if the rhs string not already a ConstString and it is impractical
+  /// to turn it into a non-temporary variable, then this overload is faster.
+  ///
+  /// \param[in] rhs
+  ///     Another string object to compare this object to.
+  ///
+  /// \return \b true if this object is not equal to \a rhs, false otherwise.
+  bool operator!=(const char *rhs) const { return !(*this == rhs); }
+
+  bool operator<(ConstString rhs) const;
+
+  /// Get the string value as a C string.
+  ///
+  /// Get the value of the contained string as a NULL terminated C string
+  /// value.
+  ///
+  /// If \a value_if_empty is nullptr, then nullptr will be returned.
+  ///
+  /// \return Returns \a value_if_empty if the string is empty, otherwise
+  ///     the C string value contained in this object.
+  const char *AsCString(const char *value_if_empty = nullptr) const {
+    return (IsEmpty() ? value_if_empty : m_string);
+  }
+
+  /// Get the string value as a llvm::StringRef
+  ///
+  /// \return
+  ///     Returns a new llvm::StringRef object filled in with the
+  ///     needed data.
+  llvm::StringRef GetStringRef() const {
+    return llvm::StringRef(m_string, GetLength());
+  }
+
+  /// Get the string value as a C string.
+  ///
+  /// Get the value of the contained string as a NULL terminated C string
+  /// value. Similar to the ConstString::AsCString() function, yet this
+  /// function will always return nullptr if the string is not valid. So this
+  /// function is a direct accessor to the string pointer value.
+  ///
+  /// \return
+  ///     Returns nullptr the string is invalid, otherwise the C string
+  ///     value contained in this object.
+  const char *GetCString() const { return m_string; }
+
+  /// Get the length in bytes of string value.
+  ///
+  /// The string pool stores the length of the string, so we can avoid calling
+  /// strlen() on the pointer value with this function.
+  ///
+  /// \return
+  ///     Returns the number of bytes that this string occupies in
+  ///     memory, not including the NULL termination byte.
+  size_t GetLength() const;
+
+  /// Clear this object's state.
+  ///
+  /// Clear any contained string and reset the value to the empty string
+  /// value.
+  void Clear() { m_string = nullptr; }
+
+  /// Equal to operator
+  ///
+  /// Returns true if this string is equal to the string in \a rhs. If case
+  /// sensitive equality is tested, this operation is very fast as it results
+  /// in a pointer comparison since all strings are in a uniqued in a global
+  /// string pool.
+  ///
+  /// \param[in] lhs
+  ///     The Left Hand Side const ConstString object reference.
+  ///
+  /// \param[in] rhs
+  ///     The Right Hand Side const ConstString object reference.
+  ///
+  /// \param[in] case_sensitive
+  ///     Case sensitivity. If true, case sensitive equality
+  ///     will be tested, otherwise character case will be ignored
+  ///
+  /// \return \b true if this object is equal to \a rhs, \b false otherwise.
+  static bool Equals(ConstString lhs, ConstString rhs,
+                     const bool case_sensitive = true);
+
+  /// Compare two string objects.
+  ///
+  /// Compares the C string values contained in \a lhs and \a rhs and returns
+  /// an integer result.
+  ///
+  /// NOTE: only call this function when you want a true string
+  /// comparison. If you want string equality use the, use the == operator as
+  /// it is much more efficient. Also if you want string inequality, use the
+  /// != operator for the same reasons.
+  ///
+  /// \param[in] lhs
+  ///     The Left Hand Side const ConstString object reference.
+  ///
+  /// \param[in] rhs
+  ///     The Right Hand Side const ConstString object reference.
+  ///
+  /// \param[in] case_sensitive
+  ///     Case sensitivity of compare. If true, case sensitive compare
+  ///     will be performed, otherwise character case will be ignored
+  ///
+  /// \return -1 if lhs < rhs, 0 if lhs == rhs, 1 if lhs > rhs
+  static int Compare(ConstString lhs, ConstString rhs,
+                     const bool case_sensitive = true);
+
+  /// Test for empty string.
+  ///
+  /// \return
+  ///     \b true if the contained string is empty.
+  ///     \b false if the contained string is not empty.
+  bool IsEmpty() const { return m_string == nullptr || m_string[0] == '\0'; }
+
+  /// Test for null string.
+  ///
+  /// \return
+  ///     \b true if there is no string associated with this instance.
+  ///     \b false if there is a string associated with this instance.
+  bool IsNull() const { return m_string == nullptr; }
+
+  /// Set the C string value.
+  ///
+  /// Set the string value in the object by uniquing the \a cstr string value
+  /// in our global string pool.
+  ///
+  /// If the C string already exists in the global string pool, it finds the
+  /// current entry and returns the existing value. If it doesn't exist, it is
+  /// added to the string pool.
+  ///
+  /// \param[in] cstr
+  ///     A NULL terminated C string to add to the string pool.
+  void SetCString(const char *cstr);
+
+  void SetString(const llvm::StringRef &s);
+
+  /// Set the C string value and its mangled counterpart.
+  ///
+  /// Object files and debug symbols often use mangled string to represent the
+  /// linkage name for a symbol, function or global. The string pool can
+  /// efficiently store these values and their counterparts so when we run
+  /// into another instance of a mangled name, we can avoid calling the name
+  /// demangler over and over on the same strings and then trying to unique
+  /// them.
+  ///
+  /// \param[in] demangled
+  ///     The demangled string to correlate with the \a mangled name.
+  ///
+  /// \param[in] mangled
+  ///     The already uniqued mangled ConstString to correlate the
+  ///     soon to be uniqued version of \a demangled.
+  void SetStringWithMangledCounterpart(llvm::StringRef demangled,
+                                       ConstString mangled);
+
+  /// Retrieve the mangled or demangled counterpart for a mangled or demangled
+  /// ConstString.
+  ///
+  /// Object files and debug symbols often use mangled string to represent the
+  /// linkage name for a symbol, function or global. The string pool can
+  /// efficiently store these values and their counterparts so when we run
+  /// into another instance of a mangled name, we can avoid calling the name
+  /// demangler over and over on the same strings and then trying to unique
+  /// them.
+  ///
+  /// \param[in] counterpart
+  ///     A reference to a ConstString object that might get filled in
+  ///     with the demangled/mangled counterpart.
+  ///
+  /// \return
+  ///     /b True if \a counterpart was filled in with the counterpart
+  ///     /b false otherwise.
+  bool GetMangledCounterpart(ConstString &counterpart) const;
+
+  /// Set the C string value with length.
+  ///
+  /// Set the string value in the object by uniquing \a cstr_len bytes
+  /// starting at the \a cstr string value in our global string pool. If trim
+  /// is true, then \a cstr_len indicates a maximum length of the CString and
+  /// if the actual length of the string is less, then it will be trimmed.
+  ///
+  /// If the C string already exists in the global string pool, it finds the
+  /// current entry and returns the existing value. If it doesn't exist, it is
+  /// added to the string pool.
+  ///
+  /// \param[in] cstr
+  ///     A NULL terminated C string to add to the string pool.
+  ///
+  /// \param[in] cstr_len
+  ///     The maximum length of the C string.
+  void SetCStringWithLength(const char *cstr, size_t cstr_len);
+
+  /// Set the C string value with the minimum length between \a fixed_cstr_len
+  /// and the actual length of the C string. This can be used for data
+  /// structures that have a fixed length to store a C string where the string
+  /// might not be NULL terminated if the string takes the entire buffer.
+  void SetTrimmedCStringWithLength(const char *cstr, size_t fixed_cstr_len);
+
+  /// Get the memory cost of this object.
+  ///
+  /// Return the size in bytes that this object takes in memory. This returns
+  /// the size in bytes of this object, which does not include any the shared
+  /// string values it may refer to.
+  ///
+  /// \return
+  ///     The number of bytes that this object occupies in memory.
+  size_t MemorySize() const { return sizeof(ConstString); }
+
+  struct MemoryStats {
+    size_t GetBytesTotal() const { return bytes_total; }
+    size_t GetBytesUsed() const { return bytes_used; }
+    size_t GetBytesUnused() const { return bytes_total - bytes_used; }
+    size_t bytes_total = 0;
+    size_t bytes_used = 0;
+  };
+
+  static MemoryStats GetMemoryStats();
+
+protected:
+  template <typename T, typename Enable> friend struct ::llvm::DenseMapInfo;
+  /// Only used by DenseMapInfo.
+  static ConstString FromStringPoolPointer(const char *ptr) {
+    ConstString s;
+    s.m_string = ptr;
+    return s;
+  };
+
+  const char *m_string = nullptr;
+};
+
+} // namespace check
+
+namespace llvm {
+template <> struct format_provider<check::ConstString> {
+  static void format(const check::ConstString &CS, llvm::raw_ostream &OS,
+                     llvm::StringRef Options);
+};
+
+/// DenseMapInfo implementation.
+/// \{
+template <> struct DenseMapInfo<check::ConstString> {
+  static inline check::ConstString getEmptyKey() {
+    return check::ConstString::FromStringPoolPointer(
+        DenseMapInfo<const char *>::getEmptyKey());
+  }
+  static inline check::ConstString getTombstoneKey() {
+    return check::ConstString::FromStringPoolPointer(
+        DenseMapInfo<const char *>::getTombstoneKey());
+  }
+  static unsigned getHashValue(check::ConstString val) {
+    return DenseMapInfo<const char *>::getHashValue(val.m_string);
+  }
+  static bool isEqual(check::ConstString LHS, check::ConstString RHS) {
+    return LHS == RHS;
+  }
+};
+/// \}
+
+inline raw_ostream &operator<<(raw_ostream &os, check::ConstString s) {
+  os << s.GetStringRef();
+  return os;
+}
+} // namespace llvm
+
+#endif // LLDB_UTILITY_CONSTSTRING_H

llvm/tools/check-hashtable/ConstString.cpp

+//===-- ConstString.cpp ---------------------------------------------------===//
+//
+// 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 "ConstString.h"
+
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/DJB.h"
+#include "llvm/Support/FormatProviders.h"
+#include "llvm/Support/RWMutex.h"
+#include "llvm/Support/Threading.h"
+
+#include <array>
+#include <utility>
+
+#include <cinttypes>
+#include <cstdint>
+#include <cstring>
+
+using namespace check;
+
+class Pool {
+public:
+  /// The default BumpPtrAllocatorImpl slab size.
+  static const size_t AllocatorSlabSize = 4096;
+  static const size_t SizeThreshold = AllocatorSlabSize;
+  /// Every Pool has its own allocator which receives an equal share of
+  /// the ConstString allocations. This means that when allocating many
+  /// ConstStrings, every allocator sees only its small share of allocations and
+  /// assumes LLDB only allocated a small amount of memory so far. In reality
+  /// LLDB allocated a total memory that is N times as large as what the
+  /// allocator sees (where N is the number of string pools). This causes that
+  /// the BumpPtrAllocator continues a long time to allocate memory in small
+  /// chunks which only makes sense when allocating a small amount of memory
+  /// (which is true from the perspective of a single allocator). On some
+  /// systems doing all these small memory allocations causes LLDB to spend
+  /// a lot of time in malloc, so we need to force all these allocators to
+  /// behave like one allocator in terms of scaling their memory allocations
+  /// with increased demand. To do this we set the growth delay for each single
+  /// allocator to a rate so that our pool of allocators scales their memory
+  /// allocations similar to a single BumpPtrAllocatorImpl.
+  ///
+  /// Currently we have 256 string pools and the normal growth delay of the
+  /// BumpPtrAllocatorImpl is 128 (i.e., the memory allocation size increases
+  /// every 128 full chunks), so by changing the delay to 1 we get a
+  /// total growth delay in our allocator collection of 256/1 = 256. This is
+  /// still only half as fast as a normal allocator but we can't go any faster
+  /// without decreasing the number of string pools.
+  static const size_t AllocatorGrowthDelay = 1;
+  typedef llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, AllocatorSlabSize,
+                                     SizeThreshold, AllocatorGrowthDelay>
+      Allocator;
+  typedef const char *StringPoolValueType;
+  typedef llvm::StringMap<StringPoolValueType, Allocator> StringPool;
+  typedef llvm::StringMapEntry<StringPoolValueType> StringPoolEntryType;
+
+  static StringPoolEntryType &
+  GetStringMapEntryFromKeyData(const char *keyData) {
+    return StringPoolEntryType::GetStringMapEntryFromKeyData(keyData);
+  }
+
+  static size_t GetConstCStringLength(const char *ccstr) {
+    if (ccstr != nullptr) {
+      // Since the entry is read only, and we derive the entry entirely from
+      // the pointer, we don't need the lock.
+      const StringPoolEntryType &entry = GetStringMapEntryFromKeyData(ccstr);
+      return entry.getKey().size();
+    }
+    return 0;
+  }
+
+  StringPoolValueType GetMangledCounterpart(const char *ccstr) const {
+    if (ccstr != nullptr) {
+      const uint8_t h = hash(llvm::StringRef(ccstr));
+      llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
+      return GetStringMapEntryFromKeyData(ccstr).getValue();
+    }
+    return nullptr;
+  }
+
+  const char *GetConstCString(const char *cstr) {
+    if (cstr != nullptr)
+      return GetConstCStringWithLength(cstr, strlen(cstr));
+    return nullptr;
+  }
+
+  const char *GetConstCStringWithLength(const char *cstr, size_t cstr_len) {
+    if (cstr != nullptr)
+      return GetConstCStringWithStringRef(llvm::StringRef(cstr, cstr_len));
+    return nullptr;
+  }
+
+  const char *GetConstCStringWithStringRef(const llvm::StringRef &string_ref) {
+    if (string_ref.data()) {
+      const uint8_t h = hash(string_ref);
+
+      {
+        llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
+        auto it = m_string_pools[h].m_string_map.find(string_ref);
+        if (it != m_string_pools[h].m_string_map.end())
+          return it->getKeyData();
+      }
+
+      llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+      StringPoolEntryType &entry =
+          *m_string_pools[h]
+               .m_string_map.insert(std::make_pair(string_ref, nullptr))
+               .first;
+      return entry.getKeyData();
+    }
+    return nullptr;
+  }
+
+  const char *
+  GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled,
+                                          const char *mangled_ccstr) {
+    const char *demangled_ccstr = nullptr;
+
+    {
+      const uint8_t h = hash(demangled);
+      llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+
+      // Make or update string pool entry with the mangled counterpart
+      StringPool &map = m_string_pools[h].m_string_map;
+      StringPoolEntryType &entry = *map.try_emplace(demangled).first;
+
+      entry.second = mangled_ccstr;
+
+      // Extract the const version of the demangled_cstr
+      demangled_ccstr = entry.getKeyData();
+    }
+
+    {
+      // Now assign the demangled const string as the counterpart of the
+      // mangled const string...
+      const uint8_t h = hash(llvm::StringRef(mangled_ccstr));
+      llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+      GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);
+    }
+
+    // Return the constant demangled C string
+    return demangled_ccstr;
+  }
+
+  const char *GetConstTrimmedCStringWithLength(const char *cstr,
+                                               size_t cstr_len) {
+    if (cstr != nullptr) {
+      const size_t trimmed_len = strnlen(cstr, cstr_len);
+      return GetConstCStringWithLength(cstr, trimmed_len);
+    }
+    return nullptr;
+  }
+
+  ConstString::MemoryStats GetMemoryStats() const {
+    ConstString::MemoryStats stats;
+    for (const auto &pool : m_string_pools) {
+      llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
+      const Allocator &alloc = pool.m_string_map.getAllocator();
+      stats.bytes_total += alloc.getTotalMemory();
+      stats.bytes_used += alloc.getBytesAllocated();
+    }
+    return stats;
+  }
+
+protected:
+  uint8_t hash(const llvm::StringRef &s) const {
+    uint32_t h = llvm::djbHash(s);
+    return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
+  }
+
+  struct PoolEntry {
+    mutable llvm::sys::SmartRWMutex<false> m_mutex;
+    StringPool m_string_map;
+  };
+
+  std::array<PoolEntry, 256> m_string_pools;
+};
+
+// Frameworks and dylibs aren't supposed to have global C++ initializers so we
+// hide the string pool in a static function so that it will get initialized on
+// the first call to this static function.
+//
+// Note, for now we make the string pool a pointer to the pool, because we
+// can't guarantee that some objects won't get destroyed after the global
+// destructor chain is run, and trying to make sure no destructors touch
+// ConstStrings is difficult.  So we leak the pool instead.
+static Pool &StringPool() {
+  static llvm::once_flag g_pool_initialization_flag;
+  static Pool *g_string_pool = nullptr;
+
+  llvm::call_once(g_pool_initialization_flag,
+                  []() { g_string_pool = new Pool(); });
+
+  return *g_string_pool;
+}
+
+ConstString::ConstString(const char *cstr)
+    : m_string(StringPool().GetConstCString(cstr)) {}
+
+ConstString::ConstString(const char *cstr, size_t cstr_len)
+    : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}
+
+ConstString::ConstString(const llvm::StringRef &s)
+    : m_string(StringPool().GetConstCStringWithStringRef(s)) {}
+
+bool ConstString::operator<(ConstString rhs) const {
+  if (m_string == rhs.m_string)
+    return false;
+
+  llvm::StringRef lhs_string_ref(GetStringRef());
+  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
+
+  // If both have valid C strings, then return the comparison
+  if (lhs_string_ref.data() && rhs_string_ref.data())
+    return lhs_string_ref < rhs_string_ref;
+
+  // Else one of them was nullptr, so if LHS is nullptr then it is less than
+  return lhs_string_ref.data() == nullptr;
+}
+
+size_t ConstString::GetLength() const {
+  return Pool::GetConstCStringLength(m_string);
+}
+
+bool ConstString::Equals(ConstString lhs, ConstString rhs,
+                         const bool case_sensitive) {
+  if (lhs.m_string == rhs.m_string)
+    return true;
+
+  // Since the pointers weren't equal, and identical ConstStrings always have
+  // identical pointers, the result must be false for case sensitive equality
+  // test.
+  if (case_sensitive)
+    return false;
+
+  // perform case insensitive equality test
+  llvm::StringRef lhs_string_ref(lhs.GetStringRef());
+  llvm::StringRef rhs_string_ref(rhs.GetStringRef());
+  return lhs_string_ref.equals_insensitive(rhs_string_ref);
+}
+
+int ConstString::Compare(ConstString lhs, ConstString rhs,
+                         const bool case_sensitive) {
+  // If the iterators are the same, this is the same string
+  const char *lhs_cstr = lhs.m_string;
+  const char *rhs_cstr = rhs.m_string;
+  if (lhs_cstr == rhs_cstr)
+    return 0;
+  if (lhs_cstr && rhs_cstr) {
+    llvm::StringRef lhs_string_ref(lhs.GetStringRef());
+    llvm::StringRef rhs_string_ref(rhs.GetStringRef());
+
+    if (case_sensitive) {
+      return lhs_string_ref.compare(rhs_string_ref);
+    } else {
+      return lhs_string_ref.compare_insensitive(rhs_string_ref);
+    }
+  }
+
+  if (lhs_cstr)
+    return +1; // LHS isn't nullptr but RHS is
+  else
+    return -1; // LHS is nullptr but RHS isn't
+}
+
+void ConstString::SetCString(const char *cstr) {
+  m_string = StringPool().GetConstCString(cstr);
+}
+
+void ConstString::SetString(const llvm::StringRef &s) {
+  m_string = StringPool().GetConstCStringWithLength(s.data(), s.size());
+}
+
+void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
+                                                  ConstString mangled) {
+  m_string = StringPool().GetConstCStringAndSetMangledCounterPart(
+      demangled, mangled.m_string);
+}
+
+bool ConstString::GetMangledCounterpart(ConstString &counterpart) const {
+  counterpart.m_string = StringPool().GetMangledCounterpart(m_string);
+  return (bool)counterpart;
+}
+
+void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
+  m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
+}
+
+void ConstString::SetTrimmedCStringWithLength(const char *cstr,
+                                              size_t cstr_len) {
+  m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len);
+}
+
+ConstString::MemoryStats ConstString::GetMemoryStats() {
+  return StringPool().GetMemoryStats();
+}
+
+void llvm::format_provider<ConstString>::format(const ConstString &CS,
+                                                llvm::raw_ostream &OS,
+                                                llvm::StringRef Options) {
+  format_provider<StringRef>::format(CS.GetStringRef(), OS, Options);
+}

llvm/tools/check-hashtable/Options.td

+include "llvm/Option/OptParser.td"
+
+multiclass BB<string name, string help1, string help2> {
+  def NAME: Flag<["--"], name>, HelpText<help1>;
+  def no_ # NAME: Flag<["--"], "no-" # name>, HelpText<help2>;
+}
+
+defm only_reading : BB<"only-reading",
+  "measure only reading",
+  "Don`t measure only reading">;
+
+def threads: Separate<["--", "-"], "num-threads">,
+  MetaVarName<"<threads>">,
+  HelpText<"Number of available threads for multi-threaded execution. Defaults to the number of cores on the current machine">;
+
+def table_kind: Separate<["--", "-"], "table-kind">,
+  MetaVarName<"[resizeable,non-resizeable,itbb,unordered-map,dense-map,libcuckoo,hash-mapped-trie,string-map,lldb-conststring]">,
+  HelpText<"Kind of hashtable to test(default resizeable)">;
+
+def data_set: Separate<["--", "-"], "data-set">,
+  MetaVarName<"[sequential,random,random-short,single,dwarffile]">,
+  HelpText<"Type of data set(default sequential)">;
+
+def num_elements: Separate<["--", "-"], "num-elements">,
+  MetaVarName<"<elements>">,
+  HelpText<"Number of elements to be stored in the map. Defaults to the 100000000">;
+
+def initial_coeff: Separate<["--", "-"], "initial-coeff">,
+  MetaVarName<"<coeff>">,
+  HelpText<"The coefficient to calculate initial size of map: InitialSize = NumberOfElements * InitialCoeff. Defaults to the 1">;

llvm/tools/check-hashtable/check-hashtable.cpp

+#include "ConstString.h"
+#include "llvm/ADT/ConcurrentHashtable.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/DJB.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/LEB128.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/PerThreadBumpPtrAllocator.h"
+#include <array>
+#include <unordered_map>
+
+// Comment following define to suppress using intel Threading Blocks library.
+#define USE_ITBB
+
+// Comment following define to suppress using libcuckoo library.
+#define USE_LIBCUCKOO
+
+// Comment following define to suppress using llvm HashMappedTrie.
+#define USE_LLVM_HASHMAPPEDTRIE
+
+// Comment following define to suppress dwarffile dataset.
+//#define USE_DWARFFILE_DATASET
+
+#ifdef USE_ITBB
+#include "tbb/concurrent_unordered_map.h"
+#endif
+
+#ifdef USE_LIBCUCKOO
+#include "libcuckoo/cuckoohash_map.hh"
+#endif
+
+#ifdef USE_LLVM_HASHMAPPEDTRIE
+#include "llvm/ADT/TrieRawHashMap.h"
+#endif
+
+using namespace llvm;
+using namespace object;
+
+using std::chrono::duration_cast;
+using std::chrono::milliseconds;
+using std::chrono::seconds;
+using std::chrono::system_clock;
+
+enum HashTableKind {
+  // llvm::ConcurrentHashTable
+  LLVMConcurrentHashMap,
+
+  // Intel Threading Building Blocks: concurrent_unordered_map
+  ITBB,
+
+  // LibCuckoo
+  LibCuckoo,
+
+  // std::unordered_map
+  UnorderedMap,
+
+  // llvm::DenseMap
+  LLVMDenseMap,
+
+  // llvm::HashMappedTrie
+  LLVMHashMappedTrie,
+
+  // llvm::HashMappedTrie
+  LLVMLLDBConstString,
+
+  // llvm::HashMappedTrie
+  LLVMStringMap,
+};
+
+enum DataSet {
+  // All elements are sequential integer number from 0 till NumberOfElements.
+  Sequential,
+
+  // All elements are random integer number.
+  Random,
+
+  // All elements are random integer number in the range
+  // [0:NumberOfElements/100]
+  RandomShort,
+
+  // Whole data set is single 1.
+  Single,
+
+  // Input file with DWARF info.
+  DwarfFile
+};
+
+const char *getName(HashTableKind Kind) {
+  switch (Kind) {
+  case HashTableKind::LLVMConcurrentHashMap:
+    return "llvm-concurrent-hashmap";
+  case HashTableKind::ITBB:
+    return "itbb";
+  case HashTableKind::UnorderedMap:
+    return "unordered-map";
+  case HashTableKind::LLVMDenseMap:
+    return "llvm-dense-map";
+  case HashTableKind::LibCuckoo:
+    return "libcuckoo";
+  case HashTableKind::LLVMHashMappedTrie:
+    return "hash-mapped-trie";
+  case HashTableKind::LLVMLLDBConstString:
+    return "lldb-const-string";
+  case HashTableKind::LLVMStringMap:
+    return "llvm-string-map";
+  }
+}
+
+std::optional<HashTableKind> getKind(const char *Kind) {
+  if (StringRef(Kind) == "llvm-concurrent-hashmap")
+    return HashTableKind::LLVMConcurrentHashMap;
+  else if (StringRef(Kind) == "itbb")
+    return HashTableKind::ITBB;
+  else if (StringRef(Kind) == "unordered-map")
+    return HashTableKind::UnorderedMap;
+  else if (StringRef(Kind) == "llvm-dense-map")
+    return HashTableKind::LLVMDenseMap;
+  else if (StringRef(Kind) == "libcuckoo")
+    return HashTableKind::LibCuckoo;
+  else if (StringRef(Kind) == "hash-mapped-trie")
+    return HashTableKind::LLVMHashMappedTrie;
+  else if (StringRef(Kind) == "lldb-const-string")
+    return HashTableKind::LLVMLLDBConstString;
+  else if (StringRef(Kind) == "llvm-string-map")
+    return HashTableKind::LLVMStringMap;
+
+  return std::nullopt;
+}
+
+std::optional<DataSet> getDataSet(const char *DataSet) {
+  if (StringRef(DataSet) == "sequential")
+    return DataSet::Sequential;
+  else if (StringRef(DataSet) == "random")
+    return DataSet::Random;
+  else if (StringRef(DataSet) == "random-short")
+    return DataSet::RandomShort;
+  else if (StringRef(DataSet) == "single")
+    return DataSet::Single;
+  else if (StringRef(DataSet) == "dwarffile")
+    return DataSet::DwarfFile;
+
+  return std::nullopt;
+}
+
+// Variables keeping options values.
+
+DataSet SrcDataSet = Sequential;
+std::vector<HashTableKind> Tables;
+
+std::optional<uint64_t> OptInitSize;
+std::optional<uint64_t> OptNumElements;
+bool OptOnlyReading = false;
+std::optional<uint64_t> OptNumThreads = 0;
+bool EarlyExit = false;
+std::string FileName;
+std::vector<uint32_t> SrcData;
+
+std::optional<const char *> readStringOpt(int Idx, int Argc,
+                                          char const *Argv[]) {
+  if (Idx + 1 >= Argc)
+    return std::nullopt;
+
+  return Argv[Idx + 1];
+}
+
+std::optional<uint64_t> readIntOpt(int Idx, int Argc, char const *Argv[]) {
+  if (Idx + 1 >= Argc)
+    return std::nullopt;
+
+  return atoi(Argv[Idx + 1]);
+}
+
+void printHelpMessage() {
+  outs() << "\nOVERVIEW: check-hashtable is a tool comparing various "
+            "implementations of hashtables\n";
+  outs() << "\nUSAGE: check-hashtable [options]\n";
+  outs() << "\nOPTIONS:";
+  outs() << "\n  --data-set [sequential,random,random-short,single,dwarffile]";
+  outs() << "\n                          Type of data set(default sequential)";
+  outs() << "\n                          \"dwarffile\" data set has additional parameter:";
+  outs() << "\n                                --data-set dwarffile <filename>";
+  outs() << "\n  --initial-size <number> The initial size of map";
+  outs() << "\n  --num-elements <number>";
+  outs() << "\n                          Number of elements to be stored in "
+            "the map. Defaults to the 100000000";
+  outs() << "\n  --num-threads <threads> Number of available threads for "
+            "multi-threaded execution. Defaults to the number of cores on the "
+            "current machine";
+  outs() << "\n  --only-reading          measure only reading";
+  outs() << "\n  --table-kind "
+            "[llvm-concurrent-hashmap,itbb,unordered-map,llvm-dense-map,"
+            "libcuckoo,hash-mapped-trie,lldb-const-string,llvm-string-map]";
+  outs() << "\n                          Kind of hashtable to test(default "
+            "llvm-concurrent-hashmap)\n\n";
+}
+
+bool parseCommandLine(int Argc, char const *Argv[]) {
+  if (Argc == 1) {
+    printHelpMessage();
+    EarlyExit = true;
+    return true;
+  }
+
+  for (int Idx = 1; Idx < Argc; Idx++) {
+    assert(Argv[Idx] != nullptr);
+    if (StringRef(Argv[Idx]) == "--initial-size") {
+      if ((OptInitSize = readIntOpt(Idx, Argc, Argv))) {
+        Idx++;
+        continue;
+      }
+
+      outs() << "cann`t read --initial-size value\n";
+      return false;
+    } else if (StringRef(Argv[Idx]) == "--num-elements") {
+      if ((OptNumElements = readIntOpt(Idx, Argc, Argv))) {
+        Idx++;
+        continue;
+      }
+
+      outs() << "cann`t read --num-elements value\n";
+      return false;
+    } else if (StringRef(Argv[Idx]) == "--num-threads") {
+      if ((OptNumThreads = readIntOpt(Idx, Argc, Argv))) {
+        Idx++;
+        continue;
+      }
+
+      outs() << "cann`t read --num-threads value\n";
+      return false;
+    } else if (StringRef(Argv[Idx]) == "--data-set") {
+      if (std::optional<const char *> Value = readStringOpt(Idx, Argc, Argv)) {
+
+        if (std::optional<DataSet> Set = getDataSet(*Value)) {
+          SrcDataSet = *Set;
+
+          if (*Set == DwarfFile) {
+            // read file name.
+            if (Idx + 2 >= Argc)
+              return false;
+
+            FileName = Argv[Idx + 2];
+            Idx++;
+          }
+        } else {
+          outs() << "unknown data set value: " << StringRef(*Value) << "\n";
+          return false;
+        }
+
+        Idx++;
+        continue;
+      }
+
+      return false;
+    } else if (StringRef(Argv[Idx]) == "--table-kind") {
+      if (std::optional<const char *> Value = readStringOpt(Idx, Argc, Argv)) {
+        if (StringRef(*Value) == "all") {
+          Tables.push_back(HashTableKind::LLVMConcurrentHashMap);
+          Tables.push_back(HashTableKind::ITBB);
+          Tables.push_back(HashTableKind::UnorderedMap);
+          Tables.push_back(HashTableKind::LLVMDenseMap);
+          Tables.push_back(HashTableKind::LibCuckoo);
+          Tables.push_back(HashTableKind::LLVMHashMappedTrie);
+          Tables.push_back(HashTableKind::LLVMLLDBConstString);
+          Tables.push_back(HashTableKind::LLVMStringMap);
+        } else if (std::optional<HashTableKind> TableKind = getKind(*Value)) {
+          Tables.push_back(*TableKind);
+        } else {
+          outs() << "unknown table kind value: " << StringRef(*Value) << "\n";
+          return false;
+        }
+        Idx++;
+        continue;
+      }
+
+      return false;
+    } else if (StringRef(Argv[Idx]) == "--only-reading") {
+      OptOnlyReading = true;
+    } else if (StringRef(Argv[Idx]) == "--help") {
+      printHelpMessage();
+      EarlyExit = true;
+      return true;
+    } else {
+      outs() << "unknown option: " << StringRef(Argv[Idx]) << "\n";
+      return false;
+    }
+  }
+
+  return true;
+}
+
+class Meter {
+public:
+  Meter() = default;
+  virtual ~Meter() = default;
+
+  virtual uint64_t measureWritingToTheTable() = 0;
+
+#ifdef USE_DWARFFILE_DATASET
+  virtual Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() = 0;
+#endif
+
+protected:
+  void lookForStrings(DWARFContext &Context, const DWARFDie &InputDIE,
+                      function_ref<void(const char *)> StringHandler) {
+    DWARFUnit *Unit = InputDIE.getDwarfUnit();
+    DWARFDataExtractor Data = Unit->getDebugInfoExtractor();
+    uint64_t Offset = InputDIE.getOffset();
+
+    const auto *Abbrev = InputDIE.getAbbreviationDeclarationPtr();
+    Offset += getULEB128Size(Abbrev->getCode());
+
+    for (const auto &AttrSpec : Abbrev->attributes()) {
+      DWARFFormValue Val(AttrSpec.Form);
+      Val.extractValue(Data, &Offset, Unit->getFormParams(), &Context, Unit);
+
+      switch (AttrSpec.Form) {
+      case dwarf::DW_FORM_strp:
+      case dwarf::DW_FORM_string:
+      case dwarf::DW_FORM_strx:
+      case dwarf::DW_FORM_strx1:
+      case dwarf::DW_FORM_strx2:
+      case dwarf::DW_FORM_strx3:
+      case dwarf::DW_FORM_strx4: {
+        if (std::optional<const char *> String = dwarf::toString(Val)) {
+          StringHandler(*String);
+        }
+        break;
+      }
+
+      default:
+        break;
+      }
+    };
+
+    for (auto &Child : InputDIE.children()) {
+      lookForStrings(Context, Child, StringHandler);
+    }
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t>
+  measureReadingDWARFImpl(const std::string FileName,
+                          function_ref<void(const char *)> StringHandler) {
+    uint64_t Result = 0;
+
+    ErrorOr<std::unique_ptr<MemoryBuffer>> BuffOrErr =
+        MemoryBuffer::getFileOrSTDIN(FileName);
+    if (BuffOrErr.getError())
+      return createFileError(FileName, BuffOrErr.getError());
+
+    Expected<std::unique_ptr<Binary>> BinOrErr =
+        object::createBinary(**BuffOrErr);
+    if (!BinOrErr)
+      return createFileError(FileName, BinOrErr.takeError());
+
+    std::unique_ptr<DWARFContext> Context =
+        DWARFContext::create(*static_cast<ObjectFile *>((*BinOrErr).get()));
+    if (Context.get() != nullptr) {
+      SmallVector<DWARFUnit *> Units;
+      for (const std::unique_ptr<DWARFUnit> &CU : Context->compile_units()) {
+        CU->getUnitDIE(false);
+        Units.push_back(CU.get());
+      }
+
+      auto StartTime = system_clock::now();
+
+      parallelForEach(Units.begin(), Units.end(), [&](DWARFUnit *CU) {
+        lookForStrings(*Context, CU->getUnitDIE(), StringHandler);
+      });
+
+      auto EndTime = system_clock::now();
+      Result = duration_cast<milliseconds>(EndTime - StartTime).count();
+    }
+
+    return Result;
+  }
+#endif
+
+  void preFill(function_ref<void(const char *)> StringHandler) {
+    parallelFor(0, *OptNumElements, [&](size_t Idx) {
+      std::string String = itostr(SrcData[Idx]);
+      StringHandler(String.data());
+    });
+  }
+
+  uint64_t write(function_ref<void(const std::string &)> StringHandler) {
+    auto StartTime = system_clock::now();
+    parallelFor(0, *OptNumElements,
+                [&](size_t Idx) { StringHandler(itostr(SrcData[Idx])); });
+    auto EndTime = system_clock::now();
+    return duration_cast<milliseconds>(EndTime - StartTime).count();
+  }
+};
+
+using ExtraDataTy = int *;
+
+class StringWithData {
+public:
+  StringWithData() {}
+  StringRef getKey() const {
+    return StringRef(reinterpret_cast<const char *>(this) +
+                         sizeof(StringWithData),
+                     KeyLength);
+  }
+  StringRef key() const {
+    return StringRef(reinterpret_cast<const char *>(this) +
+                         sizeof(StringWithData),
+                     KeyLength);
+  }
+
+  static StringWithData *
+  create(const StringRef &Key, parallel::PerThreadBumpPtrAllocator &Allocator) {
+    char *CharPtr = (char *)Allocator.Allocate(
+        sizeof(StringWithData) + Key.size() + 1, alignof(StringWithData));
+    strcpy(CharPtr + sizeof(StringWithData), Key.data());
+    StringWithData *NewString = reinterpret_cast<StringWithData *>(CharPtr);
+    NewString->ExtraData = nullptr;
+    NewString->KeyLength = Key.size();
+    return NewString;
+  }
+
+protected:
+  ExtraDataTy ExtraData;
+  size_t KeyLength;
+};
+
+class ConcurrentHashTableInfo {
+public:
+  /// \returns Hash value for the specified \p Key.
+  static inline hash_code getHashValue(const StringRef &Key) {
+      return xxHash64(Key);
+  }
+
+  /// \returns true if both \p LHS and \p RHS are equal.
+  static inline bool isEqual(const StringRef &LHS, const StringRef &RHS) {
+    return LHS == RHS;
+  }
+
+  /// \returns key for the specified \p KeyData.
+  static inline StringRef getKey(const StringWithData &KeyData) {
+    return KeyData.getKey();
+  }
+
+  /// \returns newly created object of KeyDataTy type.
+  static inline StringWithData *
+  create(const StringRef &Key, parallel::PerThreadBumpPtrAllocator &Allocator) {
+    return StringWithData::create(Key, Allocator);
+  }
+};
+
+class LLVMConcurrentHashMapMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    uint64_t InitialSize = OptInitSize ? *OptInitSize : 100000;
+
+    // Create hashtable and reserve initial space.
+    parallel::PerThreadBumpPtrAllocator Allocator;
+    ConcurrentHashTableByPtr<StringRef, StringWithData,
+                             parallel::PerThreadBumpPtrAllocator,
+                             ConcurrentHashTableInfo>
+        HashTable(Allocator, InitialSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) { HashTable.insert(String); };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    HashTable.printStatistic(outs());
+
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    uint64_t InitialSize = OptInitSize ? *OptInitSize : 100000;
+
+    // Create hashtable and reserve initial space.
+    parallel::PerThreadBumpPtrAllocator Allocator;
+    ConcurrentHashTableByPtr<StringRef, StringWithData,
+                             parallel::PerThreadBumpPtrAllocator,
+                             ConcurrentHashTableInfo>
+        HashTable(Allocator, InitialSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) { HashTable.insert(String); };
+
+    Expected<uint64_t> Result =
+        measureReadingDWARFImpl(FileName, StringInserter);
+
+    HashTable.printStatistic(outs());
+
+    return Result;
+  }
+#endif
+};
+
+#ifdef USE_ITBB
+
+class ITBBMapMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+
+    // Create hashtable.
+    tbb::concurrent_unordered_map<std::string, ExtraDataTy> HashTable;
+
+    if (OptInitSize)
+      HashTable.reserve(*OptInitSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, ExtraDataTy()));
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    // Create hashtable.
+    tbb::concurrent_unordered_map<std::string, ExtraDataTy> HashTable;
+
+    if (OptInitSize)
+      HashTable.reserve(*OptInitSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, ExtraDataTy()));
+        };
+
+    return measureReadingDWARFImpl(FileName, StringInserter);
+  }
+#endif
+};
+
+#endif
+
+class UnorderedMapMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested;
+    parallel::strategy.ThreadsRequested = 1;
+
+    // Create hashtable.
+    std::unordered_map<std::string, ExtraDataTy> HashTable;
+
+    if (OptInitSize)
+      HashTable.reserve(*OptInitSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, ExtraDataTy()));
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    parallel::strategy.ThreadsRequested = OriginalThreadsRequested;
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    // Create hashtable.
+    std::unordered_map<std::string, ExtraDataTy> HashTable;
+
+    if (OptInitSize)
+      HashTable.reserve(*OptInitSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, ExtraDataTy()));
+        };
+    unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested;
+    parallel::strategy.ThreadsRequested = 1;
+
+    Expected<uint64_t> Result =
+        measureReadingDWARFImpl(FileName, StringInserter);
+    parallel::strategy.ThreadsRequested = OriginalThreadsRequested;
+    return Result;
+  }
+#endif
+};
+
+template <> struct DenseMapInfo<std::string> {
+  static inline std::string getEmptyKey() { return "\1"; }
+  static inline std::string getTombstoneKey() { return "\2"; }
+  static unsigned getHashValue(const std::string &Val) {
+    return std::hash<std::string>()(Val);
+  }
+
+  static bool isEqual(const std::string &LHS, const std::string &RHS) {
+    return LHS == RHS;
+  }
+};
+
+class LLVMDenseMapMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested;
+    parallel::strategy.ThreadsRequested = 1;
+
+    // Create hashtable.
+    DenseMap<std::string, ExtraDataTy> HashTable;
+
+    if (OptInitSize)
+      HashTable.reserve(*OptInitSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, ExtraDataTy()));
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    parallel::strategy.ThreadsRequested = OriginalThreadsRequested;
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    // Create hashtable.
+    DenseMap<std::string, ExtraDataTy> HashTable;
+
+    if (OptInitSize)
+      HashTable.reserve(*OptInitSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, ExtraDataTy()));
+        };
+
+    unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested;
+    parallel::strategy.ThreadsRequested = 1;
+
+    Expected<uint64_t> Result =
+        measureReadingDWARFImpl(FileName, StringInserter);
+    parallel::strategy.ThreadsRequested = OriginalThreadsRequested;
+    return Result;
+  }
+#endif
+};
+
+#ifdef USE_LLVM_HASHMAPPEDTRIE
+
+namespace {
+template <typename DataType, size_t HashSize> class SimpleTrieHashMapTest {
+public:
+  using NumType = DataType;
+  using HashType = std::array<uint8_t, HashSize>;
+  using TrieType = ThreadSafeTrieRawHashMap<DataType, sizeof(HashType)>;
+
+  TrieType &createTrie(size_t RootBits, size_t SubtrieBits) {
+    auto &Ret = Trie.emplace(RootBits, SubtrieBits);
+    return Ret;
+  }
+
+  void destroyTrie() { Trie.reset(); }
+
+  ~SimpleTrieHashMapTest() {
+    if (Trie)
+      Trie.reset();
+  }
+
+  // Use the number itself as hash to test the pathological case.
+  static HashType hash(const std::string &Str) { return djbHash(Str.c_str()); };
+
+private:
+  std::optional<TrieType> Trie;
+};
+} // namespace
+
+class LLVMHashMappedTrieMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    // Create hashtable.
+    // TODO: to have correct comparision it is neccessary to create
+    // hash table for key/data pair
+    SimpleTrieHashMapTest<std::string, sizeof(uint32_t)> HashTable;
+
+    SimpleTrieHashMapTest<std::string, sizeof(uint32_t)>::TrieType &Tree =
+        HashTable.createTrie(3, 3);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          uint32_t Hash = djbHash(String);
+          SimpleTrieHashMapTest<std::string,
+                                sizeof(uint32_t)>::TrieType::pointer Lookup =
+              Tree.find(Hash);
+
+          Tree.insert(Lookup,
+                      SimpleTrieHashMapTest<std::string, sizeof(uint32_t)>::
+                          TrieType::value_type(Hash, String));
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    // Create hashtable.
+    // TODO: to have correct comparision it is neccessary to create
+    // hash table for key/data pair
+    SimpleTrieHashMapTest<std::string, sizeof(uint32_t)> HashTable;
+
+    SimpleTrieHashMapTest<std::string, sizeof(uint32_t)>::TrieType &Tree =
+        HashTable.createTrie(3, 3);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          uint32_t Hash = djbHash(String);
+          SimpleTrieHashMapTest<std::string,
+                                sizeof(uint32_t)>::TrieType::pointer Lookup =
+              Tree.find(Hash);
+
+          Tree.insert(Lookup,
+                      SimpleTrieHashMapTest<std::string, sizeof(uint32_t)>::
+                          TrieType::value_type(Hash, String));
+        };
+
+    return measureReadingDWARFImpl(FileName, StringInserter);
+  }
+#endif
+};
+
+#endif
+
+template <typename T> class CuckooHash {
+public:
+  size_t operator()(T __val) const noexcept { return std::hash<T>()(__val); }
+};
+
+#ifdef USE_LIBCUCKOO
+
+class LibCuckooMapMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    uint64_t InitialSize = OptInitSize ? *OptInitSize : (1U << 16) * 4;
+
+    libcuckoo::cuckoohash_map<std::string, ExtraDataTy, CuckooHash<std::string>>
+        HashTable(InitialSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(String, ExtraDataTy());
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    uint64_t InitialSize = OptInitSize ? *OptInitSize : (1U << 16) * 4;
+
+    libcuckoo::cuckoohash_map<std::string, ExtraDataTy, CuckooHash<std::string>>
+        HashTable(InitialSize);
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(String, ExtraDataTy());
+        };
+
+    return measureReadingDWARFImpl(FileName, StringInserter);
+  }
+#endif
+};
+
+#endif
+
+class LLVMLLDBConstStringMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          check::ConstString(String.c_str(), String.size());
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          check::ConstString(String.c_str(), String.size());
+        };
+
+    return measureReadingDWARFImpl(FileName, StringInserter);
+  }
+#endif
+};
+
+class LLVMStringMapMeter : public Meter {
+public:
+  uint64_t measureWritingToTheTable() override {
+    unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested;
+    parallel::strategy.ThreadsRequested = 1;
+
+    static const size_t AllocatorSlabSize = 4096;
+    static const size_t SizeThreshold = AllocatorSlabSize;
+    typedef llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, AllocatorSlabSize,
+                                       SizeThreshold, 1>
+        Allocator;
+    typedef const char *StringPoolValueType;
+    typedef llvm::StringMap<StringPoolValueType, Allocator> StringPool;
+
+    StringPool HashTable;
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, nullptr));
+        };
+
+    if (OptOnlyReading)
+      preFill(StringInserter);
+
+    uint64_t Result = write(StringInserter);
+
+    parallel::strategy.ThreadsRequested = OriginalThreadsRequested;
+    return Result;
+  }
+
+#ifdef USE_DWARFFILE_DATASET
+  Expected<uint64_t> measureReadingDWARFAnPuttingStringsInTable() override {
+    static const size_t AllocatorSlabSize = 4096;
+    static const size_t SizeThreshold = AllocatorSlabSize;
+    typedef llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, AllocatorSlabSize,
+                                       SizeThreshold, 1>
+        Allocator;
+    typedef const char *StringPoolValueType;
+    typedef llvm::StringMap<StringPoolValueType, Allocator> StringPool;
+
+    StringPool HashTable;
+
+    std::function<void(const std::string &)> StringInserter =
+        [&](const std::string &String) {
+          HashTable.insert(std::make_pair(String, nullptr));
+        };
+
+    unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested;
+    parallel::strategy.ThreadsRequested = 1;
+
+    Expected<uint64_t> Result =
+        measureReadingDWARFImpl(FileName, StringInserter);
+    parallel::strategy.ThreadsRequested = OriginalThreadsRequested;
+    return Result;
+  }
+#endif
+};
+
+inline void error(Error Err) {
+  errs() << toString(std::move(Err));
+  std::exit(EXIT_FAILURE);
+}
+
+int main(int Argc, char const *Argv[]) {
+
+  InitLLVM X(Argc, Argv);
+
+  if (!parseCommandLine(Argc, Argv))
+    return EXIT_FAILURE;
+
+  if (EarlyExit)
+    return EXIT_SUCCESS;
+
+  if (!OptNumThreads || *OptNumThreads == 0)
+    parallel::strategy = optimal_concurrency();
+  else
+    parallel::strategy = hardware_concurrency(*OptNumThreads);
+
+  if (Tables.empty()) {
+    outs() << "kind of table is not specified\n";
+    return 0;
+  }
+
+  uint64_t Millisecs = 0;
+  double InitialCoeff = 1;
+  size_t Counter = 0;
+
+  if (!OptNumElements)
+    OptNumElements = 100000000;
+
+  SrcData.reserve(*OptNumElements);
+
+  // Build initial data set.
+  if (SrcDataSet == Sequential) {
+    for (uint64_t Idx = 0; Idx < *OptNumElements; Idx++)
+      SrcData.push_back(Idx);
+  } else if (SrcDataSet == Single) {
+    SrcData.push_back(1);
+  } else {
+    std::srand(std::time(nullptr));
+
+    if (SrcDataSet == Random) {
+      for (uint64_t Idx = 0; Idx < *OptNumElements; Idx++)
+        SrcData.push_back(std::rand());
+    } else {
+      uint64_t Divider = *OptNumElements / 100;
+      for (uint64_t Idx = 0; Idx < *OptNumElements; Idx++)
+        SrcData.push_back(std::rand() % Divider);
+    }
+  }
+
+  // Measure hashtable table filling.
+  for (HashTableKind TableKind : Tables) {
+    Millisecs = 0;
+    if (SrcDataSet == DataSet::DwarfFile) {
+#ifdef USE_DWARFFILE_DATASET
+      switch (TableKind) {
+      case HashTableKind::LLVMConcurrentHashMap: {
+        Expected<uint64_t> Time =
+            LLVMConcurrentHashMapMeter()
+                .measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+      } break;
+      case HashTableKind::ITBB: {
+#ifdef USE_ITBB
+        Expected<uint64_t> Time =
+            ITBBMapMeter().measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+#endif
+      } break;
+      case HashTableKind::UnorderedMap: {
+        Expected<uint64_t> Time =
+            UnorderedMapMeter().measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+      } break;
+      case HashTableKind::LLVMDenseMap: {
+        Expected<uint64_t> Time =
+            LLVMDenseMapMeter().measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+      } break;
+      case HashTableKind::LLVMHashMappedTrie: {
+#ifdef USE_LLVM_HASHMAPPEDTRIE
+        Expected<uint64_t> Time =
+            LLVMHashMappedTrieMeter()
+                .measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+#endif
+      } break;
+      case HashTableKind::LibCuckoo: {
+#ifdef USE_LIBCUCKOO
+        Expected<uint64_t> Time =
+            LibCuckooMapMeter().measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+#endif
+      } break;
+      case HashTableKind::LLVMLLDBConstString: {
+        Expected<uint64_t> Time =
+            LLVMLLDBConstStringMeter()
+                .measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+      } break;
+      case HashTableKind::LLVMStringMap: {
+        Expected<uint64_t> Time =
+            LLVMStringMapMeter().measureReadingDWARFAnPuttingStringsInTable();
+        if (!Time)
+          error(Time.takeError());
+
+        Millisecs = *Time;
+      } break;
+      }
+#else
+    outs() << " dataset \"dwarffile\" disabled\n";
+#endif
+    } else {
+      switch (TableKind) {
+      case HashTableKind::LLVMConcurrentHashMap: {
+        Millisecs = LLVMConcurrentHashMapMeter().measureWritingToTheTable();
+      } break;
+      case HashTableKind::ITBB: {
+#ifdef USE_ITBB
+        Millisecs = ITBBMapMeter().measureWritingToTheTable();
+#endif
+      } break;
+      case HashTableKind::UnorderedMap: {
+        Millisecs = UnorderedMapMeter().measureWritingToTheTable();
+      } break;
+      case HashTableKind::LLVMDenseMap: {
+        Millisecs = LLVMDenseMapMeter().measureWritingToTheTable();
+      } break;
+      case HashTableKind::LLVMHashMappedTrie: {
+#ifdef USE_LLVM_HASHMAPPEDTRIE
+        Millisecs = LLVMHashMappedTrieMeter().measureWritingToTheTable();
+#endif
+      } break;
+      case HashTableKind::LibCuckoo: {
+#ifdef USE_LIBCUCKOO
+        Millisecs = LibCuckooMapMeter().measureWritingToTheTable();
+#endif
+      } break;
+      case HashTableKind::LLVMLLDBConstString: {
+        Millisecs = LLVMLLDBConstStringMeter().measureWritingToTheTable();
+      } break;
+      case HashTableKind::LLVMStringMap: {
+        Millisecs = LLVMStringMapMeter().measureWritingToTheTable();
+      } break;
+      }
+    }
+
+    if (InitialCoeff >= 1) {
+      Counter++;
+      outs() << "\n-------------------------------------------\n"
+             << Counter << ". " << getName(TableKind) << ":";
+
+#ifndef USE_ITBB
+      if (TableKind == HashTableKind::ITBB) {
+        outs() << " Not supported\n";
+        continue;
+      }
+#endif
+
+#ifndef USE_LIBCUCKOO
+      if (TableKind == HashTableKind::LibCuckoo) {
+        outs() << " Not supported\n";
+        continue;
+      }
+#endif
+
+#ifndef USE_LLVM_HASHMAPPEDTRIE
+      if (TableKind == HashTableKind::LLVMHashMappedTrie) {
+        outs() << " Not supported\n";
+        continue;
+      }
+#endif
+
+      outs() << " Time(sec): " << (Millisecs / 1000) << "."
+             << (Millisecs % 1000) << "\n";
+    }
+  }
+
+  return EXIT_SUCCESS;
+}