[demangler] Fix buffer growth

[urnathan]

Summary

The output buffer growth algorithm had a couple of issues:

a) An off-by-one error in the initial size check, which uses '>='. This error was safe, but could cause us to reallocate when there was no need.

b) An inconsistency between the initial size check (>=) and the post-doubling check (>). The latter was somewhat obscured by the swapped operands.

c) There would be many reallocs with an initially-small buffer. Add a little initialization hysteresis.

[ChuanqiXu]

libcxxabi/src/demangle/Utility.h

39

What's the meaning of the magic number 100? Generally we should make it configurable or at least we should give a name to it.

[urnathan]

Let's make 1024 the minimum and use a constvar so we don't write it twice.

[urnathan]

libcxxabi/src/demangle/Utility.h

39

It seems dramatically over-engineering to make this configurable. You just want a number high enough for many symbols in one go, and big enough that larger symbols don't keep reallocating. But not so big that one allocates a tremendously excessive amount. The demangler Nodes themselves are probably the largest component?

100 seemed a good enough value. It's better than the current [non-configurable] zero :) I notice the demangler's node allocator (BumpPointerAllocator) allocates [unconfigurable] 4096 byte blocks. So let's go with 1024 here, ok?

[urnathan]

libcxxabi/src/demangle/Utility.h

39

I've noticed the missing full stop on the comment.

[ChuanqiXu]

libcxxabi/src/demangle/Utility.h

40–42

It looks like that MinInitAlloc is a better name. I would like to move line 43~45 after line 38. Then we could simplify the code to:

size_t Need = N + CurrentPosition;
/// A comment here
constexpr size_t MinInitAlloc = 1024;
 if (!BufferCapacity)
      Need = max(Need, MinInitAlloc);
if (Need > BufferCapacity)
       BufferCapacity = max(Need, BufferCapacity * 2);

[urnathan]

libcxxabi/src/demangle/Utility.h

40–42

I put the MinInitAlloc checking inside the outer if, to avoid making the non-allocating path more complex. We only need to check the minium when we know we're going to allocate

[ChuanqiXu]

libcxxabi/src/demangle/Utility.h

40–42

Now it lost the check: if (!BufferCapacity). Is it intentional? Now it wouldn't allocate at the initialization only. So the name may be not appropriate.

[urnathan]

libcxxabi/src/demangle/Utility.h

40–42

that check is unnecessary, we'll only pick MinInitAlloc on the first allocation -- because later allocations will be for a greater amount.

[ChuanqiXu]

libcxxabi/src/demangle/Utility.h

40–42

Yeah, it is true. I didn't figure it out previously.

[thakis]

This breaks building on one of our bots: https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8822094137116818625/+/u/package_clang/stdout?format=raw

In file included from /opt/s/w/ir/cache/builder/src/third_party/llvm/llvm/unittests/Demangle/ItaniumDemangleTest.cpp:9:
 In file included from /opt/s/w/ir/cache/builder/src/third_party/llvm/llvm/include/llvm/Demangle/ItaniumDemangle.h:25:
 /opt/s/w/ir/cache/builder/src/third_party/llvm/llvm/include/llvm/Demangle/Utility.h:42:19: error: no member named 'max' in namespace 'std'; did you mean 'fmax'?
       Need = std::max(Need, MinInitAlloc);
              ~~~~~^~~
                   fmax

Looks like this now needs an include of <algorithm> for std::max(). That's a pretty heavy header though; maybe this should instead be rewritten to not use max, like on the lhs?

[urnathan]

In D119177#3326232, @thakis wrote:

This breaks building on one of our bots: https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8822094137116818625/+/u/package_clang/stdout?format=raw

Looks like this now needs an include of <algorithm> for std::max(). That's a pretty heavy header though; maybe this should instead be rewritten to not use max, like on the lhs?

stupid inconsistent header files :), yeah algorithm is rather large, I'll open-code it.

ETA: Ah, I see the copied header diverged from the original, lacking the <algorithm> include. See D119951 for fix.

libcxxabi/src/demangle/Utility.h

 
 // Stream that AST nodes write their string representation into after the AST
 // has been parsed.
 class OutputBuffer {
   char *Buffer = nullptr;
   size_t CurrentPosition = 0;
   size_t BufferCapacity = 0;
 
-  // Ensure there is at least n more positions in buffer.
+  // Ensure there are at least N more positions in the buffer.
   void grow(size_t N) {
-    if (N + CurrentPosition >= BufferCapacity) {
-      BufferCapacity *= 2;
-      if (BufferCapacity < N + CurrentPosition)
-        BufferCapacity = N + CurrentPosition;
+    size_t Need = N + CurrentPosition;
+    if (Need > BufferCapacity) {
+      // Avoid many reallocations during startup, with a bit of hysteresis.
+      constexpr size_t MinInitAlloc = 1024;
+      Need = std::max(Need, MinInitAlloc);
+      BufferCapacity = std::max(Need, BufferCapacity * 2);
       Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
       if (Buffer == nullptr)
         std::terminate();
     }
   }
 
   OutputBuffer &writeUnsigned(uint64_t N, bool isNeg = false) {
     std::array<char, 21> Temp;

llvm/include/llvm/Demangle/Utility.h

 
 // Stream that AST nodes write their string representation into after the AST
 // has been parsed.
 class OutputBuffer {
   char *Buffer = nullptr;
   size_t CurrentPosition = 0;
   size_t BufferCapacity = 0;
 
-  // Ensure there is at least n more positions in buffer.
+  // Ensure there are at least N more positions in the buffer.
   void grow(size_t N) {
-    if (N + CurrentPosition >= BufferCapacity) {
-      BufferCapacity *= 2;
-      if (BufferCapacity < N + CurrentPosition)
-        BufferCapacity = N + CurrentPosition;
+    size_t Need = N + CurrentPosition;
+    if (Need > BufferCapacity) {
+      // Avoid many reallocations during startup, with a bit of hysteresis.
+      constexpr size_t MinInitAlloc = 1024;
+      Need = std::max(Need, MinInitAlloc);
+      BufferCapacity = std::max(Need, BufferCapacity * 2);
       Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
       if (Buffer == nullptr)
         std::terminate();
     }
   }
 
   OutputBuffer &writeUnsigned(uint64_t N, bool isNeg = false) {
     std::array<char, 21> Temp;