[Support] FoldingSetNodeID::AddString(): reserve memory

[lebedev.ri]

Summary

It is traditionally potentially very inefficient to not preallocate the memory,
but rely on reallocation every time you push something into vector.

For example, looking at unity build of RawSpeed
(-O3 -g0 -emit-llvm -Xclang -disable-llvm-optzns),
the memory story is as follows:

total runtime: 11.34s.
calls to allocation functions: 2694053 (237612/s)
temporary memory allocations: 645188 (56904/s)
peak heap memory consumption: 231.36MB
peak RSS (including heaptrack overhead): 397.39MB

Looking at details, FoldingSetNodeID::AddString() is noteworthy, frequently called and is allocation-heavy.

But it is quite obvious how many times we will push into Bits - we will push String.size() itself,
and then we will push once per every 4 bytes of String (padding last block).

And if we preallocate, we get:

total runtime: 11.20s.
calls to allocation functions: 2594704 (231669/s)
temporary memory allocations: 560004 (50000/s)
peak heap memory consumption: 231.36MB
peak RSS (including heaptrack overhead): 398.06MB

Which is a measurable win:

total runtime: -0.14s.                             #  -1.23 %
calls to allocation functions: -99349 (719920/s)   #  -3.69 %
temporary memory allocations: -85184 (617275/s)    # -13.2 % (!)
peak heap memory consumption: 0B
peak RSS (including heaptrack overhead): 0B
total memory leaked: 0B

[bkramer]

llvm/lib/Support/FoldingSet.cpp

90

We have divideCeil in MathExtras.

[lebedev.ri]

Use divideCeil().

llvm/lib/Support/FoldingSet.cpp

90

Ah, that is how it's called here. Thanks.

[bkramer]

lg

llvm/lib/Support/FoldingSet.cpp

 }
 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;
 
   unsigned Units = Size / 4;
   unsigned Pos = 0;
   const unsigned *Base = (const unsigned*) String.data();
 
   // If the string is aligned do a bulk transfer.