[NFC] Optimize FoldingSet usage where it matters

[yurai007]

Summary

While building huge code bases it's not uncommon to see perf reports with following FoldingSet items:

1.56%     0.47%  clang  clang-14  [.] llvm::FoldingSetBase::FindNodeOrInsertPos
0.30%     0.01%  clang  clang-14  [.] llvm::ContextualFoldingSet<clang::FunctionProtoType, clang::ASTContext&>::NodeEquals
0.25%     0.02%  clang  clang-14  [.] llvm::FoldingSetBase::InsertNode
0.23%     0.12%  clang  clang-14  [.] llvm::FoldingSetBase::GrowBucketCount
0.22%     0.21%  clang  clang-14  [.] llvm::FoldingSetNodeID::AddPointer
0.47%     0.06%  clang  clang-14  [.] llvm::FoldingSetBase::InsertNode

or

1.12%     0.75%  clang++       libLLVM-13.so        [.] llvm::FoldingSetBase::GrowBucketCount
0.49%     0.48%  clang++       libLLVM-13.so        [.] llvm::FoldingSetNodeID::AddPointer
0.41%     0.09%  clang++       libLLVM-13.so        [.] llvm::FoldingSetNodeID::operator==

etc.

Among many FoldingSet users most notable seem to be ASTContext and CodeGenTypes.
The reasons that we spend not-so-tiny amount of time in FoldingSet calls from there, are following:

1. Default FoldingSet capacity for 2^6 items very often is not enough. For PointerTypes/ElaboratedTypes/ParenTypes it's not unlikely to observe growing it to 256 or 512 items. FunctionProtoTypes can easily exceed 1k items capacity growing up to 4k or even 8k size.

2. FoldingSetBase::GrowBucketCount cost itself is not very bad (pure reallocations are rather cheap thanks to BumpPtrAllocator) What matters is high collision rate when lot of items end up in same bucket slowing down FoldingSetBase::FindNodeOrInsertPos and trashing CPU cache (as items with same hash are organized in intrusive linked list which need to be traversed).

3. Lack of AddInteger/AddPointer and computeHash inlining slows down NodeEquals/Profile/:operator== calls. Inlining makes FunctionProtoTypes/PointerTypes/ElaboratedTypes/ParenTypes Profile functions faster but since NodeEquals is still called indirectly through function pointer from FindNodeOrInsertPos there is room for further inlining improvements.

After addressing above issues I built Linux (with default config) on isolated CPU cores in silent x86-64 Linux environment.
Compile time statistics diff produced by perf before and after change are following:
instructions -0.4%, cycles -0.9%
size-text change of output Clang binary is below +0.1%.

Similarly like in: https://reviews.llvm.org/D118169 for code bases containing smaller translation units
it's expected to get less significant speedup with this patch.

[serge-sans-paille]

clang/include/clang/AST/ASTContext.h

214

It's probably good to give that value a meaningful ( and constexpr) variable name as it's used at several point.

clang/lib/AST/ASTContext.cpp

976–977

same here, that's a lot of magic values :-)

clang/lib/CodeGen/CodeGenTypes.h

79

And here

llvm/include/llvm/ADT/FoldingSet.h

328–354

Concerning that inlined part, I expect LTO to close the gap instead of moving everything to headers. Do we have a policy on that topic?

[yurai007]

llvm/include/llvm/ADT/FoldingSet.h

328–354

I'm not aware of any LLVM Coding Guidlines policy, probably most related is just general rule: https://llvm.org/docs/CodingStandards.html#include-as-little-as-possible I agree LTO is great when enabled. I just tried to move only small part which matters.
Could you please elaborate what are you concerning about?

The only potential risks which come to my mind right now are:

• increased binary size, however I noticed Clang binary grows only below +0.1% which is acceptable I think.
• moving to header part of implementation which is often changed, however AddPointer/AddInteger/ComputeHash were touched last time in 2012.
• compile time impact on Clang build time. I confess I didn't compare Clang build times before and after change, but if you like I can.
• reduced I-cache hit rate. This is something also I didn't check under perf but I can if you like (not sure how important it is given that we get drops of other metrics).

[xbolva00]

llvm/include/llvm/ADT/FoldingSet.h

328–354

Is LLVM / Clang in distro releases even built with LTO / LTO + PGO?

[serge-sans-paille]

llvm/include/llvm/ADT/FoldingSet.h

328–354

In fedora, LLVM is compiled with LTO. But I agree that's not an assumption we should make, and thus moving some functions to the header looks ok.

[yurai007]

llvm/include/llvm/ADT/FoldingSet.h

328–354

Yep, recently there is growing interest in using LTO among distros. I heard about at least Fedora, Ubuntu, Red Hat, Debian and Arch interested in enabling it by default. Except Fedora not sure how it looks like with Clang package, though.

[nikic]

It might make sense to split this into individual changes, so it's clearer what impact each of them has.

I tested just moving the AddXYZ methods into the header, which had a large positive impact: https://llvm-compile-time-tracker.com/compare.php?from=784e01abca65722df8969b56d2d240cf9ced9c85&to=179ee195b8ce9f483827f843fc063388aed7f0d1&stat=instructions

Moving hashing into the header has smaller impact: https://llvm-compile-time-tracker.com/compare.php?from=179ee195b8ce9f483827f843fc063388aed7f0d1&to=5735a8981d5cf00281490989d02d7771b95cda51&stat=instructions

[yurai007]

In D118385#3281620, @nikic wrote:

It might make sense to split this into individual changes, so it's clearer what impact each of them has.

I tested just moving the AddXYZ methods into the header, which had a large positive impact: https://llvm-compile-time-tracker.com/compare.php?from=784e01abca65722df8969b56d2d240cf9ced9c85&to=179ee195b8ce9f483827f843fc063388aed7f0d1&stat=instructions

Moving hashing into the header has smaller impact: https://llvm-compile-time-tracker.com/compare.php?from=179ee195b8ce9f483827f843fc063388aed7f0d1&to=5735a8981d5cf00281490989d02d7771b95cda51&stat=instructions

Thanks for extra measurements. Yes, splitting it make sense. I will do it.

clang/include/clang/AST/ASTContext.h

 /// Holds long-lived AST nodes (such as types and decls) that can be
 /// referred to throughout the semantic analysis of a file.
 class ASTContext : public RefCountedBase<ASTContext> {
   friend class NestedNameSpecifier;
 
   mutable SmallVector<Type *, 0> Types;
   mutable llvm::FoldingSet<ExtQuals> ExtQualNodes;
   mutable llvm::FoldingSet<ComplexType> ComplexTypes;
-  mutable llvm::FoldingSet<PointerType> PointerTypes;
+  mutable llvm::FoldingSet<PointerType> PointerTypes{GeneralTypesLog2InitSize};
   mutable llvm::FoldingSet<AdjustedType> AdjustedTypes;
   mutable llvm::FoldingSet<BlockPointerType> BlockPointerTypes;
   mutable llvm::FoldingSet<LValueReferenceType> LValueReferenceTypes;
   mutable llvm::FoldingSet<RValueReferenceType> RValueReferenceTypes;
   mutable llvm::FoldingSet<MemberPointerType> MemberPointerTypes;
   mutable llvm::ContextualFoldingSet<ConstantArrayType, ASTContext &>
       ConstantArrayTypes;
   mutable llvm::FoldingSet<IncompleteArrayType> IncompleteArrayTypes;
class ASTContext : public RefCountedBase<ASTContext> {
   mutable llvm::FoldingSet<TemplateTypeParmType> TemplateTypeParmTypes;
   mutable llvm::FoldingSet<ObjCTypeParamType> ObjCTypeParamTypes;
   mutable llvm::FoldingSet<SubstTemplateTypeParmType>
     SubstTemplateTypeParmTypes;
   mutable llvm::FoldingSet<SubstTemplateTypeParmPackType>
     SubstTemplateTypeParmPackTypes;
   mutable llvm::ContextualFoldingSet<TemplateSpecializationType, ASTContext&>
     TemplateSpecializationTypes;
-  mutable llvm::FoldingSet<ParenType> ParenTypes;
+  mutable llvm::FoldingSet<ParenType> ParenTypes{GeneralTypesLog2InitSize};
   mutable llvm::FoldingSet<UsingType> UsingTypes;
-  mutable llvm::FoldingSet<ElaboratedType> ElaboratedTypes;
+  mutable llvm::FoldingSet<ElaboratedType> ElaboratedTypes{
+      GeneralTypesLog2InitSize};
   mutable llvm::FoldingSet<DependentNameType> DependentNameTypes;
   mutable llvm::ContextualFoldingSet<DependentTemplateSpecializationType,
                                      ASTContext&>
     DependentTemplateSpecializationTypes;
   llvm::FoldingSet<PackExpansionType> PackExpansionTypes;
   mutable llvm::FoldingSet<ObjCObjectTypeImpl> ObjCObjectTypes;
   mutable llvm::FoldingSet<ObjCObjectPointerType> ObjCObjectPointerTypes;
   mutable llvm::FoldingSet<DependentUnaryTransformType>
class ASTContext : public RefCountedBase<ASTContext> {
   struct PerModuleInitializers {
     llvm::SmallVector<Decl*, 4> Initializers;
     llvm::SmallVector<uint32_t, 4> LazyInitializers;
 
     void resolve(ASTContext &Ctx);
   };
   llvm::DenseMap<Module*, PerModuleInitializers*> ModuleInitializers;
 
+  static constexpr unsigned ConstantArrayTypesLog2InitSize = 8;
+  static constexpr unsigned GeneralTypesLog2InitSize = 9;
+  static constexpr unsigned FunctionProtoTypesLog2InitSize = 12;
+
   ASTContext &this_() { return *this; }
 
 public:
   /// A type synonym for the TemplateOrInstantiation mapping.
   using TemplateOrSpecializationInfo =
       llvm::PointerUnion<VarTemplateDecl *, MemberSpecializationInfo *>;
 
 private:

clang/lib/AST/ASTContext.cpp

case LangOptions::ASMM_Off:
     return false;
   }
   llvm_unreachable("getAddressSpaceMapMangling() doesn't cover anything.");
 }
 
 ASTContext::ASTContext(LangOptions &LOpts, SourceManager &SM,
                        IdentifierTable &idents, SelectorTable &sels,
                        Builtin::Context &builtins, TranslationUnitKind TUKind)
-    : ConstantArrayTypes(this_()), FunctionProtoTypes(this_()),
+    : ConstantArrayTypes(this_(), ConstantArrayTypesLog2InitSize),
+      FunctionProtoTypes(this_(), FunctionProtoTypesLog2InitSize),
       TemplateSpecializationTypes(this_()),
       DependentTemplateSpecializationTypes(this_()), AutoTypes(this_()),
       SubstTemplateTemplateParmPacks(this_()),
       CanonTemplateTemplateParms(this_()), SourceMgr(SM), LangOpts(LOpts),
       NoSanitizeL(new NoSanitizeList(LangOpts.NoSanitizeFiles, SM)),
       XRayFilter(new XRayFunctionFilter(LangOpts.XRayAlwaysInstrumentFiles,
                                         LangOpts.XRayNeverInstrumentFiles,
                                         LangOpts.XRayAttrListFiles, SM)),

clang/lib/CodeGen/CodeGenTypes.h

class CodeGenTypes {
 
   /// Maps clang struct type with corresponding record layout info.
   llvm::DenseMap<const Type*, std::unique_ptr<CGRecordLayout>> CGRecordLayouts;
 
   /// Contains the LLVM IR type for any converted RecordDecl.
   llvm::DenseMap<const Type*, llvm::StructType *> RecordDeclTypes;
 
   /// Hold memoized CGFunctionInfo results.
-  llvm::FoldingSet<CGFunctionInfo> FunctionInfos;
+  llvm::FoldingSet<CGFunctionInfo> FunctionInfos{FunctionInfosLog2InitSize};
 
   /// This set keeps track of records that we're currently converting
   /// to an IR type.  For example, when converting:
   /// struct A { struct B { int x; } } when processing 'x', the 'A' and 'B'
   /// types will be in this set.
   llvm::SmallPtrSet<const Type*, 4> RecordsBeingLaidOut;
 
   llvm::SmallPtrSet<const CGFunctionInfo*, 4> FunctionsBeingProcessed;
 
   /// True if we didn't layout a function due to a being inside
   /// a recursive struct conversion, set this to true.
   bool SkippedLayout;
 
   SmallVector<const RecordDecl *, 8> DeferredRecords;
 
   /// This map keeps cache of llvm::Types and maps clang::Type to
   /// corresponding llvm::Type.
   llvm::DenseMap<const Type *, llvm::Type *> TypeCache;
 
   llvm::SmallSet<const Type *, 8> RecordsWithOpaqueMemberPointers;
 
+  static constexpr unsigned FunctionInfosLog2InitSize = 9;
   /// Helper for ConvertType.
   llvm::Type *ConvertFunctionTypeInternal(QualType FT);
 
 public:
   CodeGenTypes(CodeGenModule &cgm);
   ~CodeGenTypes();
 
   const llvm::DataLayout &getDataLayout() const {

llvm/include/llvm/ADT/FoldingSet.h

 // in a graph.  This code was originally created by Chris Lattner for use with
 // SelectionDAGCSEMap, but was isolated to provide use across the llvm code set.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_FOLDINGSET_H
 #define LLVM_ADT_FOLDINGSET_H
 
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
class FoldingSetNodeIDRef {
   size_t Size = 0;
 
 public:
   FoldingSetNodeIDRef() = default;
   FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
 
   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
   /// used to lookup the node in the FoldingSetBase.
-  unsigned ComputeHash() const;
+  unsigned ComputeHash() const {
+    return static_cast<unsigned>(hash_combine_range(Data, Data + Size));
+  }
 
   bool operator==(FoldingSetNodeIDRef) const;
 
   bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
 
   /// Used to compare the "ordering" of two nodes as defined by the
   /// profiled bits and their ordering defined by memcmp().
   bool operator<(FoldingSetNodeIDRef) const;

 
 public:
   FoldingSetNodeID() = default;
 
   FoldingSetNodeID(FoldingSetNodeIDRef Ref)
     : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {}
 
   /// Add* - Add various data types to Bit data.
-  void AddPointer(const void *Ptr);
-  void AddInteger(signed I);
-  void AddInteger(unsigned I);
-  void AddInteger(long I);
-  void AddInteger(unsigned long I);
-  void AddInteger(long long I);
-  void AddInteger(unsigned long long I);
+  void AddPointer(const void *Ptr) {
+    // Note: this adds pointers to the hash using sizes and endianness that
+    // depend on the host. It doesn't matter, however, because hashing on
+    // pointer values is inherently unstable. Nothing should depend on the
+    // ordering of nodes in the folding set.
+    static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
+                  "unexpected pointer size");
+    AddInteger(reinterpret_cast<uintptr_t>(Ptr));
+  }
+  void AddInteger(signed I) { Bits.push_back(I); }
+  void AddInteger(unsigned I) { Bits.push_back(I); }
+  void AddInteger(long I) { AddInteger((unsigned long)I); }
+  void AddInteger(unsigned long I) {
+    if (sizeof(long) == sizeof(int))
+      AddInteger(unsigned(I));
+    else if (sizeof(long) == sizeof(long long)) {
+      AddInteger((unsigned long long)I);
+    } else {
+      llvm_unreachable("unexpected sizeof(long)");
+    }
+  }
+  void AddInteger(long long I) { AddInteger((unsigned long long)I); }
+  void AddInteger(unsigned long long I) {
+    AddInteger(unsigned(I));
+    AddInteger(unsigned(I >> 32));
+  }
+
   void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
   void AddString(StringRef String);
   void AddNodeID(const FoldingSetNodeID &ID);
 
   template <typename T>
   inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
 
   /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
   /// object to be used to compute a new profile.
   inline void clear() { Bits.clear(); }
 
   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
   /// to lookup the node in the FoldingSetBase.
-  unsigned ComputeHash() const;
+  unsigned ComputeHash() const {
+    return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
+  }
 
   /// operator== - Used to compare two nodes to each other.
   bool operator==(const FoldingSetNodeID &RHS) const;
   bool operator==(const FoldingSetNodeIDRef RHS) const;
 
   bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
   bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
 

llvm/lib/Support/FoldingSet.cpp

 //===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a hash set that can be used to remove duplication of
 // nodes in a graph.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/FoldingSet.h"
-#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MathExtras.h"
 #include <cassert>
 #include <cstring>
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 // FoldingSetNodeIDRef Implementation
 
-/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
-/// used to lookup the node in the FoldingSetBase.
-unsigned FoldingSetNodeIDRef::ComputeHash() const {
-  return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
-}
-
 bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
   if (Size != RHS.Size) return false;
   return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
 }
 
 /// Used to compare the "ordering" of two nodes as defined by the
 /// profiled bits and their ordering defined by memcmp().
 bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
   if (Size != RHS.Size)
     return Size < RHS.Size;
   return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;
 }
 
 //===----------------------------------------------------------------------===//
 // FoldingSetNodeID Implementation
 
 /// Add* - Add various data types to Bit data.
 ///
-void FoldingSetNodeID::AddPointer(const void *Ptr) {
-  // Note: this adds pointers to the hash using sizes and endianness that
-  // depend on the host. It doesn't matter, however, because hashing on
-  // pointer values is inherently unstable. Nothing should depend on the
-  // ordering of nodes in the folding set.
-  static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
-                "unexpected pointer size");
-  AddInteger(reinterpret_cast<uintptr_t>(Ptr));
-}
-void FoldingSetNodeID::AddInteger(signed I) {
-  Bits.push_back(I);
-}
-void FoldingSetNodeID::AddInteger(unsigned I) {
-  Bits.push_back(I);
-}
-void FoldingSetNodeID::AddInteger(long I) {
-  AddInteger((unsigned long)I);
-}
-void FoldingSetNodeID::AddInteger(unsigned long I) {
-  if (sizeof(long) == sizeof(int))
-    AddInteger(unsigned(I));
-  else if (sizeof(long) == sizeof(long long)) {
-    AddInteger((unsigned long long)I);
-  } else {
-    llvm_unreachable("unexpected sizeof(long)");
-  }
-}
-void FoldingSetNodeID::AddInteger(long long I) {
-  AddInteger((unsigned long long)I);
-}
-void FoldingSetNodeID::AddInteger(unsigned long long I) {
-  AddInteger(unsigned(I));
-  AddInteger(unsigned(I >> 32));
-}
-
 void FoldingSetNodeID::AddString(StringRef String) {
   unsigned Size =  String.size();
 
   unsigned NumInserts = 1 + divideCeil(Size, 4);
   Bits.reserve(Bits.size() + NumInserts);
 
   Bits.push_back(Size);
   if (!Size) return;
void FoldingSetNodeID::AddString(StringRef String) {
   Bits.push_back(V);
 }
 
 // AddNodeID - Adds the Bit data of another ID to *this.
 void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
   Bits.append(ID.Bits.begin(), ID.Bits.end());
 }
 
-/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to
-/// lookup the node in the FoldingSetBase.
-unsigned FoldingSetNodeID::ComputeHash() const {
-  return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
-}
-
 /// operator== - Used to compare two nodes to each other.
 ///
 bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
   return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
 }
 
 /// operator== - Used to compare two nodes to each other.
 ///