[demangler] Improve buffer hysteresis

[urnathan]

Summary

In fixing the std:max problem with the earlier patch, I noticed we could do better here by adjusting how the allocator hysteresis is used.

Except in the initialization case, if we needed more than double the buffer, the original code would allocate exactly the amount needed, and thus consequently the next request would also realloc. Just add the hysteresis to what we need everytime we know we're going to allocate. As the first request is probably a few bytes, avoid allocating just over 1K by dialing the hysteresis back a bit.

[ChuanqiXu]

I found it is possible to add a test for this in llvm/unittest/Demangle/. The unittest uses google test and we could test the number of reallocation in a certain input. I think it is always better to add a test when we make a non-NFC change.

[urnathan]

Added unit test

[ChuanqiXu]

Oh, the test looks not straight forward. I am confused at the first sight. And I figure it out after thinking for a while. I could understand it since I have the revision background. I guess other people reading the test might be confused. I have two suggestion:

1. Add a debug counter wrapped by #ifndef NDEBUG and a corresponding test wrapped by #ifndef NDEBUG. This is friendly for reader to read.
2. Or at least create another test with new name Reallocation and a corresponding comment.

[urnathan]

In D119972#3331375, @ChuanqiXu wrote:

Oh, the test looks not straight forward. I am confused at the first sight. And I figure it out after thinking for a while. I could understand it since I have the revision background. I guess other people reading the test might be confused. I have two suggestion:

1. Add a debug counter wrapped by #ifndef NDEBUG and a corresponding test wrapped by #ifndef NDEBUG. This is friendly for reader to read.
2. Or at least create another test with new name Reallocation and a corresponding comment.

I think you're making this far too complicated.

[ChuanqiXu]

In D119972#3331718, @urnathan wrote:

In D119972#3331375, @ChuanqiXu wrote:

Oh, the test looks not straight forward. I am confused at the first sight. And I figure it out after thinking for a while. I could understand it since I have the revision background. I guess other people reading the test might be confused. I have two suggestion:

1. Add a debug counter wrapped by #ifndef NDEBUG and a corresponding test wrapped by #ifndef NDEBUG. This is friendly for reader to read.
2. Or at least create another test with new name Reallocation and a corresponding comment.

I think you're making this far too complicated.

I don't think so. I think the reader who reads the test would be confused really. And it wouldn't be complicated. All we need to do is to add a new TEST and a more detailed comment. I think it wouldn't take too many lines.

[serge-sans-paille]

It would be great to backup this kind of fine-tuning with some benchmarks, otherwise we're just making the code more complex without data :-/

[urnathan]

separate unit test

[urnathan]

In D119972#3342871, @serge-sans-paille wrote:

It would be great to backup this kind of fine-tuning with some benchmarks, otherwise we're just making the code more complex without data :-/

We're actually making it simpler. Replacing a conditional assignment with an unconditional add.

[ChuanqiXu]

Benchmarking is always good. But the cost may be too high sometimes.

llvm/unittests/Demangle/OutputBufferTest.cpp

95

Thanks. I feel better if there is a comment.

libcxxabi/src/demangle/Utility.h

class OutputBuffer {
   char *Buffer = nullptr;
   size_t CurrentPosition = 0;
   size_t BufferCapacity = 0;
 
   // Ensure there are at least N more positions in the buffer.
   void grow(size_t N) {
     size_t Need = N + CurrentPosition;
     if (Need > BufferCapacity) {
-      // Avoid many reallocations during startup, with a bit of hysteresis.
-      constexpr size_t MinInitAlloc = 1024;
-      if (Need < MinInitAlloc)
-        Need = MinInitAlloc;
+      // Reduce the number of reallocations, with a bit of hysteresis. The
+      // number here is chosen so the first allocation will more-than-likely not
+      // allocate more than 1K.
+      Need += 1024 - 32;
       BufferCapacity *= 2;
       if (BufferCapacity < Need)
         BufferCapacity = Need;
       Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
       if (Buffer == nullptr)
         std::terminate();
     }
   }

llvm/include/llvm/Demangle/Utility.h

class OutputBuffer {
   char *Buffer = nullptr;
   size_t CurrentPosition = 0;
   size_t BufferCapacity = 0;
 
   // Ensure there are at least N more positions in the buffer.
   void grow(size_t N) {
     size_t Need = N + CurrentPosition;
     if (Need > BufferCapacity) {
-      // Avoid many reallocations during startup, with a bit of hysteresis.
-      constexpr size_t MinInitAlloc = 1024;
-      if (Need < MinInitAlloc)
-        Need = MinInitAlloc;
+      // Reduce the number of reallocations, with a bit of hysteresis. The
+      // number here is chosen so the first allocation will more-than-likely not
+      // allocate more than 1K.
+      Need += 1024 - 32;
       BufferCapacity *= 2;
       if (BufferCapacity < Need)
         BufferCapacity = Need;
       Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
       if (Buffer == nullptr)
         std::terminate();
     }
   }

llvm/unittests/Demangle/OutputBufferTest.cpp

TEST(OutputBufferTest, Format) {
   EXPECT_EQ("-90", printToString(-90));
   EXPECT_EQ("109", printToString(109));
   EXPECT_EQ("400", printToString(400));
 
   EXPECT_EQ("a", printToString('a'));
   EXPECT_EQ("?", printToString('?'));
 
   EXPECT_EQ("abc", printToString("abc"));
+
+  // Something that's larger than the initial default allocation.
+  char Massive[2000];
+  std::memset(Massive, 'a', sizeof(Massive));
+  Massive[sizeof(Massive) - 1] = 0;
+  EXPECT_EQ(Massive, printToString(Massive));
 }
 
 TEST(OutputBufferTest, Insert) {
   OutputBuffer OB;
 
   OB.insert(0, "", 0);
   EXPECT_EQ("", toString(OB));
 
TEST(OutputBufferTest, Prepend) {
   EXPECT_EQ("defnabc", toString(OB));
 
   OB.setCurrentPosition(3);
 
   OB.prepend("abc");
   EXPECT_EQ("abcdef", toString(OB));
 
   std::free(OB.getBuffer());
 }