Make ConstString creation and access lockfree

[scott.smith]

Summary

Utilize atomics to update linked lists without requiring locks. Reduces the number of calls to compute the hash by not having to compute it once to determine the bucket and then again inside a separate hashtable implementation. Use xxhash for better performance, especially with longer strings. Eliminates calls to hash when just updating the value by being able to use atomics instead of locks.

[scott.smith]

Note, I don't expect you guys to want this as is, since the # of buckets can't grow, and thus for very large applications this will behave O(n) instead of O(1). Before I bother to convert this to 1M skip lists (instead of 1M singly linked lists), is this something you're at all interested in? It brings execution time of my test down from ~4.5s to ~3.5s (lldb -b -o 'b main' -o 'run' my_test_program).

[clayborg]

Do you have performance numbers here? I am all for it if it improves performance. If this is faster than llvm::StringMap why not just fix it there? Seems like everyone could benefit if you fix it in LLVM?

[clayborg]

Sorry missed your first note about perf. This has to be able to handle any number of strings efficiently and growing buckets is probably needed. How many buckets are you starting with here? The design probably shouldn't take up gobs of memory if it just has a few strings as well.

Do we really need to use a homegrown hash table here? Can we not leverage std::unordered_map or some other hash table in LLVM here?

[scott.smith]

In D32832#745361, @clayborg wrote:

Do you have performance numbers here? I am all for it if it improves performance. If this is faster than llvm::StringMap why not just fix it there? Seems like everyone could benefit if you fix it in LLVM?

A proper lockfree hashtable that allows deletions is complicated and slow for simple cases, IME.

ConstString is a special case, because

1. It's big
2. It's insert-only
3. It's highly concurrent

I think a proper lock free SkipList would be a better fit for LLVM though, and this code could then build upon it, which would solve it's existing scalability issue.

Truth is this isn't a huge deal (ignoring the HashString->xxHash change and assuming tcmalloc, it's saving 1+ seconds, out of 4.5-5ish). It might lead itself to a custom allocator, though, which may make linking with tcmalloc unnecessary (something like BumpPtrAllocator, but threadsafe, or maybe just thread local). Again, a trick you can get away with since this is insert-only.

So to break it down:

1. the HashString->xxHash change could be made separately if there was a version of StringMap that took the hash as a parameter, rather than running the hash function itself. That would reduce the # of calls from 2 to 1, and would allow the use of a function that is better suited to lldb (I ran into resistance changing llvm::HashString since clang depends on it, and I couldn't prove it wouldn't hurt.
2. 64-bit hashes for fewer collisions - StringMap uses 32-bit hashes, which makes sense for smaller hash tables. This may or may not matter much.
3. no lock for reading or updating value - GetMangledCounterpart, SetMangledCounterparts, and half of GetConstCStringAndSetMangledCountrpart no longer compute a hash, and don't need a lock. You can actually do this with StringMap by using a struct as the value side that has std::atomic in it
4. much finer granularity - I tried increasing the # of buckets in the old ConstString but could never improve performance (though that was without tcmalloc, maybe it'd work now)
5. lockfree insertion

and possibly in the future:

6. BumpPtrAllocator for struct Entry - maybe eliminate the need for tcmalloc (well, assuming the demangler used an arena allocator, something else I gave up rather than trying to convince libcxxabi to change, then having to port that back to llvm).

I haven't measured how much each of these changes matter. This change is small enough and in a file that changes infrequently, so we can keep this as a private patch if we have to.

[labath]

I have feeling you gave up on the llvm change too quickly. My interpretation of that thread was that there was general support for the hash function switch, and people only wanted some confirmation it will not regress.

However, I do believe that this can be made faster than any solution based on a generic string map (but I don't like hardcoding bucket numbers either). For a change of this depth, I also think it would be fair to ask for some ConstString unit tests, so we have something we can run thread sanitizer on, instead of tracking down obscure debugger failures.

source/Utility/ConstString.cpp

58

s/StringPoolEntryType/Pool::Entry/ instead of the typedef?

source/Utility/ConstString.cpp

 
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/iterator.h"            // for iterator_facade_base
 #include "llvm/Support/Allocator.h"       // for BumpPtrAllocator
 #include "llvm/Support/FormatProviders.h" // for format_provider
 #include "llvm/Support/RWMutex.h"
 #include "llvm/Support/Threading.h"
+#include "llvm/Support/xxhash.h"
 
 #include <algorithm> // for min
 #include <array>
 #include <utility> // for make_pair, pair
 
 #include <inttypes.h> // for PRIu64
 #include <stdint.h>   // for uint8_t, uint32_t, uint64_t
 #include <string.h>   // for size_t, strlen
 
 using namespace lldb_private;
 
 class Pool {
 public:
-  typedef const char *StringPoolValueType;
-  typedef llvm::StringMap<StringPoolValueType, llvm::BumpPtrAllocator>
-      StringPool;
-  typedef llvm::StringMapEntry<StringPoolValueType> StringPoolEntryType;
+  struct Entry {
+    uint64_t hash;
+    size_t key_len;
+    std::atomic<const char *> value;
+    std::atomic<Entry *> next;
+    // string follows
+    void setValue(const char * val) {
+      value.store(val, std::memory_order_release);
+    }
+    const char * cstr() const {
+      return reinterpret_cast<const char *>(this + 1);
+    }
+    llvm::StringRef str() const {
+      return llvm::StringRef(cstr(), key_len);
+    }
+  };
+
+  Pool() {
+    for (auto & a : m_string_pools)
+      a.store(nullptr, std::memory_order_release);
+  }
+
+  typedef std::atomic<Entry *> StringPool;
+  typedef Entry StringPoolEntryType;
 
   static StringPoolEntryType &
   GetStringMapEntryFromKeyData(const char *keyData) {
-    return StringPoolEntryType::GetStringMapEntryFromKeyData(keyData);
+    StringPoolEntryType * p = reinterpret_cast<StringPoolEntryType *>(const_cast<char *>(keyData));
+    return *(p - 1);
   }
 
   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 entry.key_len;
     }
     return 0;
   }
 
-  StringPoolValueType GetMangledCounterpart(const char *ccstr) const {
+  const char * 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 GetStringMapEntryFromKeyData(ccstr).value;
     }
     return nullptr;
   }
 
   bool SetMangledCounterparts(const char *key_ccstr, const char *value_ccstr) {
     if (key_ccstr != nullptr && value_ccstr != nullptr) {
-      {
-        const uint8_t h = hash(llvm::StringRef(key_ccstr));
-        llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
-        GetStringMapEntryFromKeyData(key_ccstr).setValue(value_ccstr);
-      }
-      {
-        const uint8_t h = hash(llvm::StringRef(value_ccstr));
-        llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
-        GetStringMapEntryFromKeyData(value_ccstr).setValue(key_ccstr);
-      }
       return true;
     }
     return false;
   }
 
   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();
+      const uint64_t h = hash(string_ref);
+      while (true) {
+        auto * b = &bucket(h);
+        Entry * bref;
+        while ((bref = b->load())) {
+          if (bref->hash > h)
+            break;
+          if (bref->hash == h) {
+            // Hash collision, do a secondary sort on string
+            llvm::StringRef bstringref = bref->str();
+            if (string_ref == bstringref)
+              return bref->cstr();
+            if (bstringref > string_ref)
+              break;
+          }
+          b = &bref->next;
+        }
+        Entry * new_entry = reinterpret_cast<Entry *>(
+          malloc(sizeof(Entry) + string_ref.size() + 1));
+        new_entry->hash = h;
+        new_entry->key_len = string_ref.size();
+        new_entry->value.store(nullptr, std::memory_order_relaxed);
+        new_entry->next.store(bref, std::memory_order_relaxed);
+        char * dest = const_cast<char *>(new_entry->cstr());
+        memcpy(dest, string_ref.data(), string_ref.size());
+        dest[string_ref.size()] = 0;
+        if (b->compare_exchange_strong(bref, new_entry)) {
+          return dest;
+        }
+        free(new_entry);
       }
-
-      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(const char *demangled_cstr,
                                           const char *mangled_ccstr) {
     if (demangled_cstr != nullptr) {
-      const char *demangled_ccstr = nullptr;
-
-      {
-        llvm::StringRef string_ref(demangled_cstr);
-        const uint8_t h = hash(string_ref);
-        llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
+      const char *demangled_ccstr = GetConstCStringWithStringRef(demangled_cstr);
 
-        // Make string pool entry with the mangled counterpart already set
-        StringPoolEntryType &entry =
-            *m_string_pools[h]
-                 .m_string_map.insert(std::make_pair(string_ref, mangled_ccstr))
-                 .first;
-
-        // 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;
     }
     return nullptr;
   }
 
   const char *GetConstTrimmedCStringWithLength(const char *cstr,
                                                size_t cstr_len) {
     if (cstr != nullptr) {
       const size_t trimmed_len = std::min<size_t>(strlen(cstr), cstr_len);
       return GetConstCStringWithLength(cstr, trimmed_len);
     }
     return nullptr;
   }
 
   //------------------------------------------------------------------
   // Return the size in bytes that this object and any items in its
   // collection of uniqued strings + data count values takes in
   // memory.
   //------------------------------------------------------------------
   size_t MemorySize() const {
     size_t mem_size = sizeof(Pool);
+    /*
     for (const auto &pool : m_string_pools) {
       llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
       for (const auto &entry : pool.m_string_map)
         mem_size += sizeof(StringPoolEntryType) + entry.getKey().size();
     }
+    */
     return mem_size;
   }
 
 protected:
-  uint8_t hash(const llvm::StringRef &s) const {
-    uint32_t h = llvm::HashString(s);
-    return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
+  static const unsigned hash_bits = 20;
+  uint64_t hash(const llvm::StringRef &s) const {
+    return llvm::xxHash64(s);
   }
 
-  struct PoolEntry {
-    mutable llvm::sys::SmartRWMutex<false> m_mutex;
-    StringPool m_string_map;
-  };
+  std::atomic<Entry *> & bucket(uint64_t hash) {
+    return m_string_pools[hash >> (64 - hash_bits)];
+  }
 
-  std::array<PoolEntry, 256> m_string_pools;
+  std::atomic<Entry *> m_string_pools[1 << hash_bits];
 };
 
 //----------------------------------------------------------------------
 // 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.
 //