[kudu] branch master updated: [util] Fix comment of faststring

[ad...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

adar pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/kudu.git


The following commit(s) were added to refs/heads/master by this push:
     new a035869  [util] Fix comment of faststring
a035869 is described below

commit a035869886bb5de37cde7b2bf48bdd3def3123ff
Author: lingbin <li...@gmail.com>
AuthorDate: Thu Oct 31 22:11:26 2019 +0800

    [util] Fix comment of faststring
    
    1. Under any case, capacity() is greater than or equal to
       the data length. If the current length is shorter than
       kInitialCapacity, after call shrink_to_fit(),
       capacity() will go down to kInitialCapacity.
    2. The caller must be responsible for releasing the pointer
       release() returns.
    
    Now In `GrowByAtLeast()`, to_reserve (i.e. `len_ + count`)
    is usually larger than we really need. This commit also
    calculate an exact value when we try to expand the faststring.
    
    To be clearer, this commit rename `GrowByAtLeast()` to
    `GrowToAtLeast()`, and make the newcapacity as its argument.
    
    Note: If the capacity needs to grow, it still expand by
    at least 50% each time.
    
    Change-Id: Ie4bd4f31216fdf5cfbf70526f1358824fbda225a
    Reviewed-on: http://gerrit.cloudera.org:8080/14604
    Reviewed-by: Adar Dembo <ad...@cloudera.com>
    Tested-by: Adar Dembo <ad...@cloudera.com>
---
 src/kudu/util/faststring-test.cc | 63 +++++++++++++++++++++++++++++++++++++++-
 src/kudu/util/faststring.cc      |  9 +++---
 src/kudu/util/faststring.h       | 17 ++++++-----
 3 files changed, 76 insertions(+), 13 deletions(-)

diff --git a/src/kudu/util/faststring-test.cc b/src/kudu/util/faststring-test.cc
index 07c5697..79dd6b2 100644
--- a/src/kudu/util/faststring-test.cc
+++ b/src/kudu/util/faststring-test.cc
@@ -18,6 +18,7 @@
 #include <algorithm>
 #include <cstring>
 #include <memory>
+#include <string>
 
 #include <gtest/gtest.h>
 
@@ -26,6 +27,9 @@
 #include "kudu/util/random_util.h"
 #include "kudu/util/test_util.h"
 
+using std::string;
+using std::unique_ptr;
+
 namespace kudu {
 class FaststringTest : public KuduTest {};
 
@@ -48,7 +52,7 @@ TEST_F(FaststringTest, TestShrinkToFit_SmallerThanInitialCapacity) {
 TEST_F(FaststringTest, TestShrinkToFit_Random) {
   Random r(GetRandomSeed32());
   int kMaxSize = faststring::kInitialCapacity * 2;
-  std::unique_ptr<char[]> random_bytes(new char[kMaxSize]);
+  unique_ptr<char[]> random_bytes(new char[kMaxSize]);
   RandomString(random_bytes.get(), kMaxSize, &r);
 
   faststring s;
@@ -62,4 +66,61 @@ TEST_F(FaststringTest, TestShrinkToFit_Random) {
   }
 }
 
+TEST_F(FaststringTest, TestPushBack) {
+  faststring s;
+  for (int i = 0; i < faststring::kInitialCapacity * 2; ++i) {
+    s.push_back('a');
+    ASSERT_LE(s.size(), s.capacity());
+    ASSERT_EQ(i + 1, s.size());
+    if (i + 1 <= faststring::kInitialCapacity) {
+      ASSERT_EQ(s.capacity(), faststring::kInitialCapacity);
+    }
+  }
+}
+
+TEST_F(FaststringTest, TestAppend_Simple) {
+  faststring s;
+  ASSERT_EQ(s.capacity(), faststring::kInitialCapacity);
+  ASSERT_EQ(s.size(), 0);
+
+  // append empty string
+  s.append("");
+  ASSERT_EQ(s.capacity(), faststring::kInitialCapacity);
+  ASSERT_EQ(s.size(), 0);
+
+  // len_ < kInitialCapacity
+  s.append("hello");
+  ASSERT_EQ(s.capacity(), faststring::kInitialCapacity);
+  ASSERT_EQ(s.size(), 5);
+
+  // len_ > kInitialCapacity
+  string tmp(faststring::kInitialCapacity, 'a');
+  s.append(tmp);
+  ASSERT_GT(s.capacity(), faststring::kInitialCapacity);
+  ASSERT_EQ(s.size(), 5 + faststring::kInitialCapacity);
+}
+
+TEST_F(FaststringTest, TestAppend_ExponentiallyExpand) {
+  size_t initial_capacity = faststring::kInitialCapacity / 2;
+  string tmp1(initial_capacity, 'a');
+
+  {
+    // Less than 150% after expansion
+    faststring s;
+    string tmp2(faststring::kInitialCapacity - 1, 'a');
+    s.append(tmp1);
+    s.append(tmp2);
+    ASSERT_EQ(s.capacity(), faststring::kInitialCapacity * 3 / 2);
+  }
+
+  {
+    // More than 150% after expansion
+    faststring s;
+    string tmp2(faststring::kInitialCapacity + 1, 'a');
+    s.append(tmp1);
+    s.append(tmp2);
+    ASSERT_GT(s.capacity(), faststring::kInitialCapacity * 3 / 2);
+  }
+}
+
 } // namespace kudu
diff --git a/src/kudu/util/faststring.cc b/src/kudu/util/faststring.cc
index a1cd26b..33610d0 100644
--- a/src/kudu/util/faststring.cc
+++ b/src/kudu/util/faststring.cc
@@ -22,17 +22,16 @@
 
 namespace kudu {
 
-void faststring::GrowByAtLeast(size_t count) {
+void faststring::GrowToAtLeast(size_t newcapacity) {
   // Not enough space, need to reserve more.
   // Don't reserve exactly enough space for the new string -- that makes it
   // too easy to write perf bugs where you get O(n^2) append.
   // Instead, alwayhs expand by at least 50%.
 
-  size_t to_reserve = len_ + count;
-  if (len_ + count < len_ * 3 / 2) {
-    to_reserve = len_ *  3 / 2;
+  if (newcapacity < capacity_ * 3 / 2) {
+    newcapacity = capacity_ *  3 / 2;
   }
-  GrowArray(to_reserve);
+  GrowArray(newcapacity);
 }
 
 void faststring::GrowArray(size_t newcapacity) {
diff --git a/src/kudu/util/faststring.h b/src/kudu/util/faststring.h
index 992060b..3ada37c 100644
--- a/src/kudu/util/faststring.h
+++ b/src/kudu/util/faststring.h
@@ -86,7 +86,8 @@ class faststring {
 
   // Releases the underlying array; after this, the buffer is left empty.
   //
-  // NOTE: the data pointer returned by release() is not necessarily the pointer
+  // NOTE: the data pointer returned by release() always points to dynamically
+  // allocated memory and the caller must be responsible for releasing it.
   uint8_t *release() WARN_UNUSED_RESULT {
     uint8_t *ret = data_;
     if (ret == initial_data_) {
@@ -208,10 +209,10 @@ class faststring {
   // Reallocates the internal storage to fit only the current data.
   //
   // This may revert to using internal storage if the current length is shorter than
-  // kInitialCapacity. Note that, in that case, after this call, capacity() will return
-  // a capacity larger than the data length.
+  // kInitialCapacity. In that case, after this call, capacity() will go down to
+  // kInitialCapacity.
   //
-  // Any pointers within this instance are invalidated.
+  // Any pointers within this instance may be invalidated.
   void shrink_to_fit() {
     if (data_ == initial_data_ || capacity_ == len_) return;
     ShrinkToFitInternal();
@@ -235,12 +236,12 @@ class faststring {
 
     // Call the non-inline slow path - this reduces the number of instructions
     // on the hot path.
-    GrowByAtLeast(count);
+    GrowToAtLeast(len_ + count);
   }
 
-  // The slow path of MakeRoomFor. Grows the buffer by either
+  // The slow path of EnsureRoomForAppend. Grows the buffer by either
   // 'count' bytes, or 50%, whichever is more.
-  void GrowByAtLeast(size_t count);
+  void GrowToAtLeast(size_t newcapacity);
 
   // Grow the array to the given capacity, which must be more than
   // the current capacity.
@@ -251,6 +252,8 @@ class faststring {
   uint8_t* data_;
   uint8_t initial_data_[kInitialCapacity];
   size_t len_;
+  // NOTE: we will make a initial buffer as part of the object, so the smallest
+  // possible value of capacity_ is kInitialCapacity.
   size_t capacity_;
 };