[PDB] Hash types up front when merging types instead of using StringMap

[rnk]

Summary

First, StringMap uses llvm::HashString, which is only good for short
identifiers and really bad for large blobs of binary data like type
records. Moving to DenseMap<StringRef, TypeIndex> with some tricks for
memory allocation fixes that.

Unfortunately, that didn't buy very much performance. Profiling showed
that we spend a long time during DenseMap growth rehashing existing
entries. Also, in general, DenseMap is faster when the keys are small.
This change takes that to the logical conclusion by introducing a small
wrapper value type around a pointer to key data. The key data contains a
precomputed hash, the original record data (pointer and size), and the
type index, which is the "value" of our original map.

This reduces the time to produce llvm-as.exe and llvm-as.pdb from ~15s
on my machine to 3.5s, which is about a 4x improvement.

[zturner]

llvm/lib/DebugInfo/CodeView/TypeSerializer.cpp

22

hash_code?

23–24

ArrayRef<uint8_t> or StringRef?

25

TypeIndex?

53–54

I haven't looked at the implementation of DenseMap, but is this check necessary? I would imagine you could assert that the hashes are different, otherwise why would DenseMap be calling this function?

59–60

Is this an important consideration? Seems like it sacrifices readability

98–99

Why not xxHash64? hash_value appears to operate on one char at a time.

[rnk]

llvm/lib/DebugInfo/CodeView/TypeSerializer.cpp

23–24

This saves 4 bytes. We know type records are always shorter than 0xFF00 bytes, so it's safe to go all the way to uint16_t as the comment suggests.

25

Yeah, we can do that. I kind of like unsigned or uint32_t because it doesn't depend on llvm::support::ulittle32_t, which uses all this memcpy craziness.

53–54

DenseMap takes the low bits of the hash and uses them to index into its table, so there can be hash collisions. So, if the table has 256 entries and two records hash to 0x100 and 0x200, this comparison will save us from doing a full memcmp.

59–60

I really wanted HashedType and HashedTypePtr to be in anonymous namespaces, and this is what I had to do to accomplish that. They really aren't general purpose types that should float around in public headers.

98–99

@chandlerc said we'll probably have to delete xxHash64, so I didn't want to use it. hash_value actually hashes 64 bytes at a time if it can. I'm pretty confident we're hitting that overload, but I could do more to check. It also worried me.

[chandlerc]

Drive by comment...

llvm/trunk/lib/DebugInfo/CodeView/TypeSerializer.cpp

40 ↗

(On Diff #99956)

This isn't suitably aligned. You should use the DenseMapInfo for some pointer type instead.

llvm/include/llvm/DebugInfo/CodeView/TypeSerializer.h

 
 #include "llvm/DebugInfo/CodeView/TypeRecordMapping.h"
 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Error.h"
 
 namespace llvm {
 
 namespace codeview {
 
+class TypeHasher;
+
 class TypeSerializer : public TypeVisitorCallbacks {
   struct SubRecord {
     SubRecord(TypeLeafKind K, uint32_t S) : Kind(K), Size(S) {}
 
     TypeLeafKind Kind;
     uint32_t Size = 0;
   };
   struct RecordSegment {
     SmallVector<SubRecord, 16> SubRecords;
 
     uint32_t length() const {
       uint32_t L = sizeof(RecordPrefix);
       for (const auto &R : SubRecords) {
         L += R.Size;
       }
       return L;
     }
   };
 
   typedef SmallVector<MutableArrayRef<uint8_t>, 2> MutableRecordList;
-  typedef SmallVector<ArrayRef<uint8_t>, 2> RecordList;
 
   static constexpr uint8_t ContinuationLength = 8;
   BumpPtrAllocator &RecordStorage;
   RecordSegment CurrentSegment;
   MutableRecordList FieldListSegments;
 
-  TypeIndex LastTypeIndex;
   Optional<TypeLeafKind> TypeKind;
   Optional<TypeLeafKind> MemberKind;
   std::vector<uint8_t> RecordBuffer;
   MutableBinaryByteStream Stream;
   BinaryStreamWriter Writer;
   TypeRecordMapping Mapping;
 
-  RecordList SeenRecords;
-  StringMap<TypeIndex, BumpPtrAllocator&> HashedRecords;
+  /// Private type record hashing implementation details are handled here.
+  std::unique_ptr<TypeHasher> Hasher;
 
   bool isInFieldList() const;
-  TypeIndex calcNextTypeIndex() const;
-  TypeIndex incrementTypeIndex();
   MutableArrayRef<uint8_t> getCurrentSubRecordData();
   MutableArrayRef<uint8_t> getCurrentRecordData();
   Error writeRecordPrefix(TypeLeafKind Kind);
-  TypeIndex insertRecordBytesPrivate(ArrayRef<uint8_t> &Record);
 
   Expected<MutableArrayRef<uint8_t>>
   addPadding(MutableArrayRef<uint8_t> Record);
 
 public:
   explicit TypeSerializer(BumpPtrAllocator &Storage);
+  ~TypeSerializer();
 
   ArrayRef<ArrayRef<uint8_t>> records() const;
-  TypeIndex getLastTypeIndex() const;
   TypeIndex insertRecordBytes(ArrayRef<uint8_t> Record);
   Expected<TypeIndex> visitTypeEndGetIndex(CVType &Record);
 
   Error visitTypeBegin(CVType &Record) override;
   Error visitTypeEnd(CVType &Record) override;
   Error visitMemberBegin(CVMemberRecord &Record) override;
   Error visitMemberEnd(CVMemberRecord &Record) override;
 

llvm/lib/DebugInfo/CodeView/TypeSerializer.cpp

 //===- TypeSerialzier.cpp ---------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/CodeView/TypeSerializer.h"
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 
 #include <string.h>
 
 using namespace llvm;
 using namespace llvm::codeview;
 
-bool TypeSerializer::isInFieldList() const {
-  return TypeKind.hasValue() && *TypeKind == TypeLeafKind::LF_FIELDLIST;
+namespace {
+struct HashedType {
+  uint64_t Hash;
+  const uint8_t *Data;
+  unsigned Size; // FIXME: Go to uint16_t?
+  unsigned Index;
+};
+
+/// Wrapper around a poitner to a HashedType. Hash and equality operations are
+/// based on data in the pointee.
+struct HashedTypePtr {
+  HashedTypePtr() = default;
+  HashedTypePtr(HashedType *Ptr) : Ptr(Ptr) {}
+  HashedType *Ptr = nullptr;
+  bool operator==(const HashedTypePtr &O) { return Ptr == O.Ptr; }
+  bool operator!=(const HashedTypePtr &O) { return Ptr != O.Ptr; }
+};
+} // namespace
+
+template <> struct DenseMapInfo<HashedTypePtr> {
+  static inline HashedTypePtr getEmptyKey() { return HashedTypePtr(nullptr); }
+  static inline HashedTypePtr getTombstoneKey() {
+    return HashedTypePtr(reinterpret_cast<HashedType *>(1));
+  }
+  static unsigned getHashValue(HashedTypePtr Val) {
+    assert(Val.Ptr != getEmptyKey().Ptr && Val.Ptr != getTombstoneKey().Ptr);
+    return Val.Ptr->Hash;
+  }
+  static bool isEqual(HashedTypePtr LHSP, HashedTypePtr RHSP) {
+    HashedType *LHS = LHSP.Ptr;
+    HashedType *RHS = RHSP.Ptr;
+    if (RHS == getEmptyKey().Ptr || RHS == getTombstoneKey().Ptr)
+      return LHS == RHS;
+    if (LHS->Hash != RHS->Hash || LHS->Size != RHS->Size)
+      return false;
+    return ::memcmp(LHS->Data, RHS->Data, LHS->Size) == 0;
+  }
+};
+
+/// Private implementation so that we don't leak our DenseMap instantiations to
+/// users.
+class llvm::codeview::TypeHasher {
+private:
+  /// Storage for type record provided by the caller. Records will outlive the
+  /// hasher object, so they should be allocated here.
+  BumpPtrAllocator &RecordStorage;
+
+  /// Storage for hash keys. These only need to live as long as the hashing
+  /// operation.
+  BumpPtrAllocator KeyStorage;
+
+  /// Hash table. We really want a DenseMap<ArrayRef<uint8_t>, TypeIndex> here,
+  /// but DenseMap is inefficient when the keys are long (like type records)
+  /// because it recomputes the hash value of every key when it grows. This
+  /// value type stores the hash out of line in KeyStorage, so that table
+  /// entries are small and easy to rehash.
+  DenseSet<HashedTypePtr> HashedRecords;
+
+  SmallVector<ArrayRef<uint8_t>, 2> SeenRecords;
+
+  unsigned NextTypeIndex = TypeIndex::FirstNonSimpleIndex;
+
+public:
+  TypeHasher(BumpPtrAllocator &RecordStorage) : RecordStorage(RecordStorage) {}
+
+  ArrayRef<ArrayRef<uint8_t>> records() const { return SeenRecords; }
+
+  /// Takes the bytes of type record, inserts them into the hash table, saves
+  /// them, and returns a pointer to an identical stable type record along with
+  /// its type index in the destination stream.
+  TypeIndex getOrCreateRecord(ArrayRef<uint8_t> &Record);
+};
+
+TypeIndex TypeHasher::getOrCreateRecord(ArrayRef<uint8_t> &Record) {
+  assert(Record.size() < UINT32_MAX && "Record too big");
+  assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!");
+
+  // Compute the hash up front so we can store it in the key.
+  HashedType TempHashedType = {hash_value(Record), Record.data(),
+                               unsigned(Record.size()), NextTypeIndex};
+
+  auto Result = HashedRecords.insert(HashedTypePtr(&TempHashedType));
+  HashedType *&Hashed = Result.first->Ptr;
+
+  if (Result.second) {
+    // This was a new type record. We need stable storage for both the key and
+    // the record. The record should outlive the hashing operation.
+    Hashed = KeyStorage.Allocate<HashedType>();
+    *Hashed = TempHashedType;
+
+    uint8_t *Stable = RecordStorage.Allocate<uint8_t>(Record.size());
+    memcpy(Stable, Record.data(), Record.size());
+    Hashed->Data = Stable;
+    assert(Hashed->Size == Record.size());
+
+    // This was a new record, so increment our next type index.
+    ++NextTypeIndex;
   }
 
-TypeIndex TypeSerializer::calcNextTypeIndex() const {
-  if (LastTypeIndex.isNoneType())
-    return TypeIndex(TypeIndex::FirstNonSimpleIndex);
-  else
-    return TypeIndex(LastTypeIndex.getIndex() + 1);
+  // Update the caller's copy of Record to point a stable copy.
+  Record = ArrayRef<uint8_t>(Hashed->Data, Hashed->Size);
+
+  if (Result.second) {
+    // FIXME: Can we record these in a more efficient way?
+    SeenRecords.push_back(Record);
   }
 
-TypeIndex TypeSerializer::incrementTypeIndex() {
-  TypeIndex Previous = LastTypeIndex;
-  LastTypeIndex = calcNextTypeIndex();
-  return Previous;
+  return TypeIndex(Hashed->Index);
+}
+
+bool TypeSerializer::isInFieldList() const {
+  return TypeKind.hasValue() && *TypeKind == TypeLeafKind::LF_FIELDLIST;
 }
 
 MutableArrayRef<uint8_t> TypeSerializer::getCurrentSubRecordData() {
   assert(isInFieldList());
   return getCurrentRecordData().drop_front(CurrentSegment.length());
 }
 
 MutableArrayRef<uint8_t> TypeSerializer::getCurrentRecordData() {
   return MutableArrayRef<uint8_t>(RecordBuffer).take_front(Writer.getOffset());
 }
 
 Error TypeSerializer::writeRecordPrefix(TypeLeafKind Kind) {
   RecordPrefix Prefix;
   Prefix.RecordKind = Kind;
   Prefix.RecordLen = 0;
   if (auto EC = Writer.writeObject(Prefix))
     return EC;
   return Error::success();
 }
 
-TypeIndex
-TypeSerializer::insertRecordBytesPrivate(ArrayRef<uint8_t> &Record) {
-  assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!");
-
-  StringRef S(reinterpret_cast<const char *>(Record.data()), Record.size());
-
-  TypeIndex NextTypeIndex = calcNextTypeIndex();
-  auto Result = HashedRecords.try_emplace(S, NextTypeIndex);
-
-  StringRef NewData = Result.first->getKey();
-  Record = ArrayRef<uint8_t>(NewData.bytes_begin(), NewData.bytes_end());
-
-  if (Result.second) {
-    // If this triggered an insert into the map, store the bytes.
-    LastTypeIndex = NextTypeIndex;
-    SeenRecords.push_back(Record);
-  }
-
-  return Result.first->getValue();
-}
-
 Expected<MutableArrayRef<uint8_t>>
 TypeSerializer::addPadding(MutableArrayRef<uint8_t> Record) {
   uint32_t Align = Record.size() % 4;
   if (Align == 0)
     return Record;
 
   int PaddingBytes = 4 - Align;
   int N = PaddingBytes;
   while (PaddingBytes > 0) {
     uint8_t Pad = static_cast<uint8_t>(LF_PAD0 + PaddingBytes);
     if (auto EC = Writer.writeInteger(Pad))
       return std::move(EC);
     --PaddingBytes;
   }
   return MutableArrayRef<uint8_t>(Record.data(), Record.size() + N);
 }
 
 TypeSerializer::TypeSerializer(BumpPtrAllocator &Storage)
-    : RecordStorage(Storage), LastTypeIndex(),
-      RecordBuffer(MaxRecordLength * 2),
+    : RecordStorage(Storage), RecordBuffer(MaxRecordLength * 2),
       Stream(RecordBuffer, llvm::support::little), Writer(Stream),
-      Mapping(Writer), HashedRecords(Storage) {
+      Mapping(Writer), Hasher(make_unique<TypeHasher>(Storage)) {
   // RecordBuffer needs to be able to hold enough data so that if we are 1
   // byte short of MaxRecordLen, and then we try to write MaxRecordLen bytes,
   // we won't overflow.
 }
 
+TypeSerializer::~TypeSerializer() = default;
+
 ArrayRef<ArrayRef<uint8_t>> TypeSerializer::records() const {
-  return SeenRecords;
+  return Hasher->records();
 }
 
-TypeIndex TypeSerializer::getLastTypeIndex() const { return LastTypeIndex; }
-
 TypeIndex TypeSerializer::insertRecordBytes(ArrayRef<uint8_t> Record) {
   assert(!TypeKind.hasValue() && "Already in a type mapping!");
   assert(Writer.getOffset() == 0 && "Stream has data already!");
 
-  return insertRecordBytesPrivate(Record);
+  return Hasher->getOrCreateRecord(Record);
 }
 
 Error TypeSerializer::visitTypeBegin(CVType &Record) {
   assert(!TypeKind.hasValue() && "Already in a type mapping!");
   assert(Writer.getOffset() == 0 && "Stream has data already!");
 
   if (auto EC = writeRecordPrefix(Record.kind()))
     return EC;
Expected<TypeIndex> TypeSerializer::visitTypeEndGetIndex(CVType &Record) {
   ThisRecordData = *ExpectedData;
 
   RecordPrefix *Prefix =
       reinterpret_cast<RecordPrefix *>(ThisRecordData.data());
   Prefix->RecordLen = ThisRecordData.size() - sizeof(uint16_t);
 
   Record.Type = *TypeKind;
   Record.RecordData = ThisRecordData;
-  TypeIndex InsertedTypeIndex = insertRecordBytesPrivate(Record.RecordData);
+  TypeIndex InsertedTypeIndex = Hasher->getOrCreateRecord(Record.RecordData);
 
   // Write out each additional segment in reverse order, and update each
   // record's continuation index to point to the previous one.
   for (auto X : reverse(FieldListSegments)) {
     auto CIBytes = X.take_back(sizeof(uint32_t));
     support::ulittle32_t *CI =
         reinterpret_cast<support::ulittle32_t *>(CIBytes.data());
     assert(*CI == 0xB0C0B0C0 && "Invalid TypeIndex placeholder");
     *CI = InsertedTypeIndex.getIndex();
-    InsertedTypeIndex = insertRecordBytesPrivate(X);
+    InsertedTypeIndex = Hasher->getOrCreateRecord(X);
   }
 
   TypeKind.reset();
   Writer.setOffset(0);
   FieldListSegments.clear();
   CurrentSegment.SubRecords.clear();
 
   return InsertedTypeIndex;