diff --git a/llvm/tools/check-hashtable/CMakeLists.txt b/llvm/tools/check-hashtable/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/tools/check-hashtable/CMakeLists.txt @@ -0,0 +1,29 @@ +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} + ) diff --git a/llvm/tools/check-hashtable/ConstString.h b/llvm/tools/check-hashtable/ConstString.h new file mode 100644 --- /dev/null +++ b/llvm/tools/check-hashtable/ConstString.h @@ -0,0 +1,431 @@ +//===-- 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 + +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 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 { + static void format(const check::ConstString &CS, llvm::raw_ostream &OS, + llvm::StringRef Options); +}; + +/// DenseMapInfo implementation. +/// \{ +template <> struct DenseMapInfo { + static inline check::ConstString getEmptyKey() { + return check::ConstString::FromStringPoolPointer( + DenseMapInfo::getEmptyKey()); + } + static inline check::ConstString getTombstoneKey() { + return check::ConstString::FromStringPoolPointer( + DenseMapInfo::getTombstoneKey()); + } + static unsigned getHashValue(check::ConstString val) { + return DenseMapInfo::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 diff --git a/llvm/tools/check-hashtable/ConstString.cpp b/llvm/tools/check-hashtable/ConstString.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/check-hashtable/ConstString.cpp @@ -0,0 +1,308 @@ +//===-- 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 +#include + +#include +#include +#include + +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 + Allocator; + typedef const char *StringPoolValueType; + typedef llvm::StringMap StringPool; + typedef llvm::StringMapEntry 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 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 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 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 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 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 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 m_mutex; + StringPool m_string_map; + }; + + std::array 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::format(const ConstString &CS, + llvm::raw_ostream &OS, + llvm::StringRef Options) { + format_provider::format(CS.GetStringRef(), OS, Options); +} diff --git a/llvm/tools/check-hashtable/Options.td b/llvm/tools/check-hashtable/Options.td new file mode 100644 --- /dev/null +++ b/llvm/tools/check-hashtable/Options.td @@ -0,0 +1,30 @@ +include "llvm/Option/OptParser.td" + +multiclass BB { + def NAME: Flag<["--"], name>, HelpText; + def no_ # NAME: Flag<["--"], "no-" # name>, HelpText; +} + +defm only_reading : BB<"only-reading", + "measure only reading", + "Don`t measure only reading">; + +def threads: Separate<["--", "-"], "num-threads">, + MetaVarName<"">, + 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<"">, + HelpText<"Number of elements to be stored in the map. Defaults to the 100000000">; + +def initial_coeff: Separate<["--", "-"], "initial-coeff">, + MetaVarName<"">, + HelpText<"The coefficient to calculate initial size of map: InitialSize = NumberOfElements * InitialCoeff. Defaults to the 1">; diff --git a/llvm/tools/check-hashtable/check-hashtable.cpp b/llvm/tools/check-hashtable/check-hashtable.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/check-hashtable/check-hashtable.cpp @@ -0,0 +1,1082 @@ +#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 +#include + +// 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 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 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 Tables; + +std::optional OptInitSize; +std::optional OptNumElements; +bool OptOnlyReading = false; +std::optional OptNumThreads = 0; +bool EarlyExit = false; +std::string FileName; +std::vector SrcData; + +std::optional readStringOpt(int Idx, int Argc, + char const *Argv[]) { + if (Idx + 1 >= Argc) + return std::nullopt; + + return Argv[Idx + 1]; +} + +std::optional 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 "; + outs() << "\n --initial-size The initial size of map"; + outs() << "\n --num-elements "; + outs() << "\n Number of elements to be stored in " + "the map. Defaults to the 100000000"; + outs() << "\n --num-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 Value = readStringOpt(Idx, Argc, Argv)) { + + if (std::optional 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 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 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 measureReadingDWARFAnPuttingStringsInTable() = 0; +#endif + +protected: + void lookForStrings(DWARFContext &Context, const DWARFDie &InputDIE, + function_ref 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 String = dwarf::toString(Val)) { + StringHandler(*String); + } + break; + } + + default: + break; + } + }; + + for (auto &Child : InputDIE.children()) { + lookForStrings(Context, Child, StringHandler); + } + } + +#ifdef USE_DWARFFILE_DATASET + Expected + measureReadingDWARFImpl(const std::string FileName, + function_ref StringHandler) { + uint64_t Result = 0; + + ErrorOr> BuffOrErr = + MemoryBuffer::getFileOrSTDIN(FileName); + if (BuffOrErr.getError()) + return createFileError(FileName, BuffOrErr.getError()); + + Expected> BinOrErr = + object::createBinary(**BuffOrErr); + if (!BinOrErr) + return createFileError(FileName, BinOrErr.takeError()); + + std::unique_ptr Context = + DWARFContext::create(*static_cast((*BinOrErr).get())); + if (Context.get() != nullptr) { + SmallVector Units; + for (const std::unique_ptr &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(EndTime - StartTime).count(); + } + + return Result; + } +#endif + + void preFill(function_ref StringHandler) { + parallelFor(0, *OptNumElements, [&](size_t Idx) { + std::string String = itostr(SrcData[Idx]); + StringHandler(String.data()); + }); + } + + uint64_t write(function_ref StringHandler) { + auto StartTime = system_clock::now(); + parallelFor(0, *OptNumElements, + [&](size_t Idx) { StringHandler(itostr(SrcData[Idx])); }); + auto EndTime = system_clock::now(); + return duration_cast(EndTime - StartTime).count(); + } +}; + +using ExtraDataTy = int *; + +class StringWithData { +public: + StringWithData() {} + StringRef getKey() const { + return StringRef(reinterpret_cast(this) + + sizeof(StringWithData), + KeyLength); + } + StringRef key() const { + return StringRef(reinterpret_cast(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(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 + HashTable(Allocator, InitialSize); + + std::function 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 measureReadingDWARFAnPuttingStringsInTable() override { + uint64_t InitialSize = OptInitSize ? *OptInitSize : 100000; + + // Create hashtable and reserve initial space. + parallel::PerThreadBumpPtrAllocator Allocator; + ConcurrentHashTableByPtr + HashTable(Allocator, InitialSize); + + std::function StringInserter = + [&](const std::string &String) { HashTable.insert(String); }; + + Expected 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 HashTable; + + if (OptInitSize) + HashTable.reserve(*OptInitSize); + + std::function 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 measureReadingDWARFAnPuttingStringsInTable() override { + // Create hashtable. + tbb::concurrent_unordered_map HashTable; + + if (OptInitSize) + HashTable.reserve(*OptInitSize); + + std::function 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 HashTable; + + if (OptInitSize) + HashTable.reserve(*OptInitSize); + + std::function 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 measureReadingDWARFAnPuttingStringsInTable() override { + // Create hashtable. + std::unordered_map HashTable; + + if (OptInitSize) + HashTable.reserve(*OptInitSize); + + std::function StringInserter = + [&](const std::string &String) { + HashTable.insert(std::make_pair(String, ExtraDataTy())); + }; + unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested; + parallel::strategy.ThreadsRequested = 1; + + Expected Result = + measureReadingDWARFImpl(FileName, StringInserter); + parallel::strategy.ThreadsRequested = OriginalThreadsRequested; + return Result; + } +#endif +}; + +template <> struct DenseMapInfo { + static inline std::string getEmptyKey() { return "\1"; } + static inline std::string getTombstoneKey() { return "\2"; } + static unsigned getHashValue(const std::string &Val) { + return std::hash()(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 HashTable; + + if (OptInitSize) + HashTable.reserve(*OptInitSize); + + std::function 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 measureReadingDWARFAnPuttingStringsInTable() override { + // Create hashtable. + DenseMap HashTable; + + if (OptInitSize) + HashTable.reserve(*OptInitSize); + + std::function StringInserter = + [&](const std::string &String) { + HashTable.insert(std::make_pair(String, ExtraDataTy())); + }; + + unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested; + parallel::strategy.ThreadsRequested = 1; + + Expected Result = + measureReadingDWARFImpl(FileName, StringInserter); + parallel::strategy.ThreadsRequested = OriginalThreadsRequested; + return Result; + } +#endif +}; + +#ifdef USE_LLVM_HASHMAPPEDTRIE + +namespace { +template class SimpleTrieHashMapTest { +public: + using NumType = DataType; + using HashType = std::array; + using TrieType = ThreadSafeTrieRawHashMap; + + 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 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 HashTable; + + SimpleTrieHashMapTest::TrieType &Tree = + HashTable.createTrie(3, 3); + + std::function StringInserter = + [&](const std::string &String) { + uint32_t Hash = djbHash(String); + SimpleTrieHashMapTest::TrieType::pointer Lookup = + Tree.find(Hash); + + Tree.insert(Lookup, + SimpleTrieHashMapTest:: + TrieType::value_type(Hash, String)); + }; + + if (OptOnlyReading) + preFill(StringInserter); + + uint64_t Result = write(StringInserter); + + return Result; + } + +#ifdef USE_DWARFFILE_DATASET + Expected measureReadingDWARFAnPuttingStringsInTable() override { + // Create hashtable. + // TODO: to have correct comparision it is neccessary to create + // hash table for key/data pair + SimpleTrieHashMapTest HashTable; + + SimpleTrieHashMapTest::TrieType &Tree = + HashTable.createTrie(3, 3); + + std::function StringInserter = + [&](const std::string &String) { + uint32_t Hash = djbHash(String); + SimpleTrieHashMapTest::TrieType::pointer Lookup = + Tree.find(Hash); + + Tree.insert(Lookup, + SimpleTrieHashMapTest:: + TrieType::value_type(Hash, String)); + }; + + return measureReadingDWARFImpl(FileName, StringInserter); + } +#endif +}; + +#endif + +template class CuckooHash { +public: + size_t operator()(T __val) const noexcept { return std::hash()(__val); } +}; + +#ifdef USE_LIBCUCKOO + +class LibCuckooMapMeter : public Meter { +public: + uint64_t measureWritingToTheTable() override { + uint64_t InitialSize = OptInitSize ? *OptInitSize : (1U << 16) * 4; + + libcuckoo::cuckoohash_map> + HashTable(InitialSize); + + std::function 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 measureReadingDWARFAnPuttingStringsInTable() override { + uint64_t InitialSize = OptInitSize ? *OptInitSize : (1U << 16) * 4; + + libcuckoo::cuckoohash_map> + HashTable(InitialSize); + + std::function 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 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 measureReadingDWARFAnPuttingStringsInTable() override { + std::function 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 + Allocator; + typedef const char *StringPoolValueType; + typedef llvm::StringMap StringPool; + + StringPool HashTable; + + std::function 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 measureReadingDWARFAnPuttingStringsInTable() override { + static const size_t AllocatorSlabSize = 4096; + static const size_t SizeThreshold = AllocatorSlabSize; + typedef llvm::BumpPtrAllocatorImpl + Allocator; + typedef const char *StringPoolValueType; + typedef llvm::StringMap StringPool; + + StringPool HashTable; + + std::function StringInserter = + [&](const std::string &String) { + HashTable.insert(std::make_pair(String, nullptr)); + }; + + unsigned OriginalThreadsRequested = parallel::strategy.ThreadsRequested; + parallel::strategy.ThreadsRequested = 1; + + Expected 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 Time = + LLVMConcurrentHashMapMeter() + .measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; + } break; + case HashTableKind::ITBB: { +#ifdef USE_ITBB + Expected Time = + ITBBMapMeter().measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; +#endif + } break; + case HashTableKind::UnorderedMap: { + Expected Time = + UnorderedMapMeter().measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; + } break; + case HashTableKind::LLVMDenseMap: { + Expected Time = + LLVMDenseMapMeter().measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; + } break; + case HashTableKind::LLVMHashMappedTrie: { +#ifdef USE_LLVM_HASHMAPPEDTRIE + Expected Time = + LLVMHashMappedTrieMeter() + .measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; +#endif + } break; + case HashTableKind::LibCuckoo: { +#ifdef USE_LIBCUCKOO + Expected Time = + LibCuckooMapMeter().measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; +#endif + } break; + case HashTableKind::LLVMLLDBConstString: { + Expected Time = + LLVMLLDBConstStringMeter() + .measureReadingDWARFAnPuttingStringsInTable(); + if (!Time) + error(Time.takeError()); + + Millisecs = *Time; + } break; + case HashTableKind::LLVMStringMap: { + Expected 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; +}