[LLVMdev] SmallString + raw_svector_ostream combination should be more efficient

Yaron Keren yaron.keren at gmail.com
Sat May 2 11:31:54 PDT 2015


Following a hint from Duncan in http://llvm.org/pr23395, here is a revised
patch. Rather then introduce the raw_char_ostream adapter, this version
improves raw_svector_ostream.

raw_svector_ostream is now a very lightweight adapter, running without a
buffer and fowarding almost anything to the SmallString. This solves both
the performance issue and the information duplication issue. The
SmallString is always up-to-date and can be used at any time. flush() does
nothing and is not required. resync() was kept in this patch as a no-op and
will be removed with its users in a follow-up patch. I'll also try to
remove the superfluous flush calls() along the way.



2015-05-02 7:41 GMT+03:00 Yaron Keren <yaron.keren at gmail.com>:

> +update diff
>
>
> 2015-05-02 7:38 GMT+03:00 Yaron Keren <yaron.keren at gmail.com>:
>
>> I outlined (is that the right
>> word?) raw_char_ostream::grow, raw_char_ostream::write (both) into
>> raw_ostream.cpp with less than 10% difference in performance.
>>
>> Profiling reveals that the real culprit is the code line
>>
>>  OS.reserve(OS.size() + 64);
>>
>> called from raw_svector_ostream::write_impl called from
>> raw_svector_ostream::~raw_svector_ostream.
>> The issue is already documented:
>>
>> raw_svector_ostream::~raw_svector_ostream() {
>>   // FIXME: Prevent resizing during this flush().
>>   flush();
>> }
>>
>> And a solution is provided in raw_svector_ostream::init():
>>
>>   // Set up the initial external buffer. We make sure that the buffer has
>> at
>>   // least 128 bytes free; raw_ostream itself only requires 64, but we
>> want to
>>   // make sure that we don't grow the buffer unnecessarily on destruction
>> (when
>>   // the data is flushed). See the FIXME below.
>>   OS.reserve(OS.size() + 128);
>>
>> This solution may be worse than the problem. In total:
>>
>> * If the SmallString was less than 128 bytes init() will always(!) heap
>> allocate.
>> * If it's more or equal to 128 bytes but upon destruction less than 64
>> bytes are left unused it will heap allocate for no reason.
>>
>> A careful programmer who did size the SmallString to match its use +
>> small reserve will find either of these heap allocations surprising,
>> negating the SmallString advantage and then paying memcpy cost.
>>
>> I filed http://llvm.org/pr23395 about this. To temporarly avoid this
>> issue, in addition to the outline methods change I commented the OS.reserve
>> line in flush(). (This change of course requires further review.)
>>
>> With reserve being out of the way, the gap now is smaller but still
>> significant: raw_char_ostream is about 20% faster than
>> raw_svector_ostream in Release=optimized configuration.
>>
>>
>> 2015-05-02 4:39 GMT+03:00 Sean Silva <chisophugis at gmail.com>:
>>
>>>
>>> Could you dig into why:
>>> +  raw_ostream &write(unsigned char C) override {
>>> +    grow(1);
>>> +    *OutBufCur++ = C;
>>> +    return *this;
>>> +  }
>>>
>>> Is 3 times as fast as raw_svector_ostream? I don't see a good reason why
>>> that should be any faster than:
>>>
>>>   raw_ostream &operator<<(char C) {
>>>     if (OutBufCur >= OutBufEnd)
>>>       return write(C);
>>>     *OutBufCur++ = C;
>>>     return *this;
>>>   }
>>>
>>>
>>> You might just be seeing the difference between having write inlined vs.
>>> non-inlined, in which case your patch might be a complicated way to pull
>>> the likely cases of some raw_ostream methods into the header.
>>>
>>>
>>> -- Sean Silva
>>>
>>
>> On Thu, Apr 30, 2015 at 8:02 PM, Yaron Keren <yaron.keren at gmail.com>
>> wrote:
>>
>>> Yes, we should do without virtual flush. The problem
>>> was raw_char_ostream should not be flushed - it's always current - so I
>>> overloaded flush to a no-op. A cleaner solution is attached, adding
>>> a DirectBuffer mode to the raw_ostream.
>>>
>>> Also added a simple performance comparison project
>>> between raw_char_ostream and raw_svector_ostream. On Window 7 x64
>>> machine, raw_char_ostream was three times faster than raw_svector_ostream
>>> when the provided buffer size is large enough and two times as fast with
>>> one dynamic allocation resize.
>>>
>>>
>>> 2015-04-30 22:48 GMT+03:00 Rafael EspĂ­ndola <rafael.espindola at gmail.com>
>>> :
>>>
>>>> I don't think we should make flush virtual. Why do you need to do it?
>>>> Can't you set up the base class to write to use the tail of the memory
>>>> region as the buffer?
>>>>
>>>>
>>>>
>>>> On 24 April 2015 at 06:46, Yaron Keren <yaron.keren at gmail.com> wrote:
>>>> > Hi,
>>>> >
>>>> > Is this what you're thinking about?
>>>> > The code is not tested yet, I'd like to know if the overall direction
>>>> and
>>>> > design are correct.
>>>> >
>>>> > Yaron
>>>> >
>>>> >
>>>> > 2015-04-21 0:10 GMT+03:00 Yaron Keren <yaron.keren at gmail.com>:
>>>> >>
>>>> >> Sean, thanks for reminding this, Alp did commit a class derived from
>>>> >> raw_svector_ostream conatining an internal SmallString he called
>>>> >> small_string_ostream. The commit was reverted after a day due to a
>>>> >> disagreement about the commit approval and apparently abandoned.
>>>> >>
>>>> >>
>>>> >>
>>>> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140623/223393.html
>>>> >>
>>>> >>
>>>> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140623/223557.html
>>>> >>
>>>> >>
>>>> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140630/223986.html
>>>> >>
>>>> >> The class Alp comitted did solve the possible mismatch between the
>>>> >> SmallString and the stream by making the SmallString private to the
>>>> class.
>>>> >> This however did not treat the root problem, the duplication of the
>>>> >> information about the buffer between SmallString and the stream.
>>>> >>
>>>> >> I can make performance measurements but even if the performance
>>>> difference
>>>> >> is neglible (and looking at all the code paths and conditionals of
>>>> >> non-inlined functions at raw_ostream.cpp that's hard to believe), the
>>>> >> current SmallString-raw_svector_ostream is simply wrong.
>>>> >>
>>>> >> Personally, after the previous "Alp" discussion I found and fixed
>>>> several
>>>> >> such issues in my out-of-tree code only to make new similar new error
>>>> >> earlier this year, which I caught only months after, when Rafael
>>>> committed
>>>> >> the pwrite which reminded me the issue. Due ot the information
>>>> duplication
>>>> >> Rafael commit also had a bug and Mehdi reports similar experience.
>>>> Back then
>>>> >> Alp reported similar problems he found in LLVM code which were
>>>> hopefully
>>>> >> fixed otherwise.
>>>> >>
>>>> >> In addition to the information duplication, the design is quite
>>>> confusing
>>>> >> to use
>>>> >>
>>>> >> - Should one use the stream.str() function or the SmallString itself?
>>>> >> - flush or str?
>>>> >> - How do you properly clear the combination for reuse (that was my
>>>> >> mistake, I forgot to resync after OS.clear())?
>>>> >>
>>>> >> It's safe to say this design pattern is very easy to get wrong one
>>>> way or
>>>> >> another, we got burned by it multiple times and it should be
>>>> replaced.
>>>> >>
>>>> >> Alp suggested a derived class containing its own SmallString. That's
>>>> a
>>>> >> simple and effective approach to avoid the bugs mentioned but does
>>>> not fix
>>>> >> the memory or runtime issues. Small as they may be, why have them at
>>>> a
>>>> >> fundemental data structure?
>>>> >>
>>>> >> I was thinking about going further avoiding all duplication with a
>>>> >> templated class derived with its own internal buffer storage.
>>>> >>
>>>> >> Rafael suggested a more modular approach, a derived adpater class
>>>> adapter
>>>> >> to a *simple* buffer (or nullptr for fully-dynamic operation) which
>>>> also
>>>> >> won't duplicate any information the buffer is dumb and has no state.
>>>> >>
>>>> >> That solution sounds simple, efficient and safe to use. The
>>>> implementation
>>>> >> would be actually simpler then raw_svector_ostream since all the
>>>> >> coordination logic is not required anymore.
>>>> >>
>>>> >>
>>>> >> 2015-04-20 22:17 GMT+03:00 Sean Silva <chisophugis at gmail.com>:
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>> On Sun, Apr 19, 2015 at 7:40 AM, Yaron Keren <yaron.keren at gmail.com
>>>> >
>>>> >>> wrote:
>>>> >>>>
>>>> >>>> A very common code pattern in LLVM is
>>>> >>>>
>>>> >>>>  SmallString<128> S;
>>>> >>>>  raw_svector_ostream OS(S);
>>>> >>>>  OS<< ...
>>>> >>>>  Use OS.str()
>>>> >>>>
>>>> >>>> While raw_svector_ostream is smart to share the text buffer
>>>> itself, it's
>>>> >>>> inefficient keeping two sets of pointers to the same buffer:
>>>> >>>>
>>>> >>>>  In SmallString: void *BeginX, *EndX, *CapacityX
>>>> >>>>  In raw_ostream: char *OutBufStart, *OutBufEnd, *OutBufCur
>>>> >>>>
>>>> >>>> Moreover, at runtime the two sets of pointers need to be
>>>> coordinated
>>>> >>>> between the SmallString and raw_svector_ostream using
>>>> >>>> raw_svector_ostream::init, raw_svector_ostream::pwrite,
>>>> >>>> raw_svector_ostream::resync and raw_svector_ostream::write_impl.
>>>> >>>> All these functions have non-inlined implementations in
>>>> raw_ostream.cpp.
>>>> >>>>
>>>> >>>> Finally, this may cause subtle bugs if S is modified without
>>>> calling
>>>> >>>> OS::resync(). This is too easy to do by mistake.
>>>> >>>>
>>>> >>>> In this frequent case usage the client does not really care about S
>>>> >>>> being a SmallString with its many useful string helper function.
>>>> It's just
>>>> >>>> boilerplate code for raw_svector_ostream. But it does cost three
>>>> extra
>>>> >>>> pointers, some runtime performance and possible bugs.
>>>> >>>
>>>> >>>
>>>> >>> I agree the bugs are real (Alp proposed something a while back
>>>> regarding
>>>> >>> this?), but you will need to provide measurements to justify the
>>>> cost in
>>>> >>> runtime performance. One technique I have used in the past to
>>>> measure these
>>>> >>> sorts of things I call "stuffing": take the operation that you want
>>>> to
>>>> >>> measure, then essentially change the logic so that you pay the cost
>>>> 2 times,
>>>> >>> 3 times, etc. You can then look at the trend in performance as N
>>>> varies and
>>>> >>> extrapolate back to the case where N = 0 (i.e. you don't pay the
>>>> cost).
>>>> >>>
>>>> >>> For example, in one situation where I used this method it was to
>>>> measure
>>>> >>> the cost of stat'ing files (sys::fs::status) across a holistic
>>>> build, using
>>>> >>> only "time" on the command line (it was on Windows and I didn't
>>>> have any
>>>> >>> tools like DTrace available that can directly measure this). In
>>>> order to do
>>>> >>> this, I changed sys::fs::status to call stat N times instead of 1,
>>>> and
>>>> >>> measured with N=1 N=2 N=3 etc. The result was that the difference
>>>> between
>>>> >>> the N and N+1 versions was about 1-2% across N=1..10 (or whatever I
>>>> >>> measured). In order to negate caching and other confounding
>>>> effects, it is
>>>> >>> important to try different distributions of stats; e.g. the extra
>>>> stats are
>>>> >>> on the same file as the "real" stat vs. the extra stats are on
>>>> nonexistent
>>>> >>> files in the same directory as the "real" file vs. parent
>>>> directories of the
>>>> >>> "real" file; if these match up fairly well (they did), then you
>>>> have some
>>>> >>> indication that the "stuffing" is measuring what you want to
>>>> measure.
>>>> >>>
>>>> >>> So e.g. if you think the cost of 3 extra pointers is significant,
>>>> then
>>>> >>> "stuff" the struct with 3, 6, 9, ... extra pointers and measure the
>>>> >>> difference in performance (e.g. measure the time building a real
>>>> project).
>>>> >>>
>>>> >>> -- Sean Silva
>>>> >>>
>>>> >>>>
>>>> >>>>
>>>> >>>> To solve all three issues, would it make sense to have
>>>> >>>> raw_ostream-derived container with a its own SmallString like
>>>> templated-size
>>>> >>>> built-in buffer?
>>>> >>>>
>>>> >>>
>>>> >
>>>>
>>>
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150502/f543d9cb/attachment.html>
-------------- next part --------------
Index: include/llvm/Support/raw_ostream.h
===================================================================
--- include/llvm/Support/raw_ostream.h	(revision 236389)
+++ include/llvm/Support/raw_ostream.h	(working copy)
@@ -208,8 +208,8 @@
   /// satisfy std::isprint into an escape sequence.
   raw_ostream &write_escaped(StringRef Str, bool UseHexEscapes = false);
 
-  raw_ostream &write(unsigned char C);
-  raw_ostream &write(const char *Ptr, size_t Size);
+  virtual raw_ostream &write(unsigned char C);
+  virtual raw_ostream &write(const char *Ptr, size_t Size);
 
   // Formatted output, see the format() function in Support/Format.h.
   raw_ostream &operator<<(const format_object_base &Fmt);
@@ -483,40 +483,42 @@
 
 /// A raw_ostream that writes to an SmallVector or SmallString.  This is a
 /// simple adaptor class. This class does not encounter output errors.
+/// raw_svector_ostream operates without a buffer, delegating all memory
+/// management to the SmallString. Thus the SmallString is always up-to-date,
+/// may be used directly and there is no need to call flush().
 class raw_svector_ostream : public raw_pwrite_stream {
   SmallVectorImpl<char> &OS;
 
   /// See raw_ostream::write_impl.
-  void write_impl(const char *Ptr, size_t Size) override;
+  void write_impl(const char *Ptr, size_t Size) override{};
+  void pwrite_impl(const char *Ptr, size_t Size, uint64_t Offset) override {
+    memcpy(OS.data() + Offset, Ptr, Size);
+  }
 
-  void pwrite_impl(const char *Ptr, size_t Size, uint64_t Offset) override;
-
   /// Return the current position within the stream, not counting the bytes
   /// currently in the buffer.
-  uint64_t current_pos() const override;
+  uint64_t current_pos() const override { return OS.size(); }
 
-protected:
-  // Like the regular constructor, but doesn't call init.
-  explicit raw_svector_ostream(SmallVectorImpl<char> &O, unsigned);
-  void init();
-
 public:
   /// Construct a new raw_svector_ostream.
   ///
-  /// \param O The vector to write to; this should generally have at least 128
-  /// bytes free to avoid any extraneous memory overhead.
-  explicit raw_svector_ostream(SmallVectorImpl<char> &O);
-  ~raw_svector_ostream() override;
+  explicit raw_svector_ostream(SmallVectorImpl<char> &O) : OS(O) {}
+  ~raw_svector_ostream() override {}
 
+  raw_ostream &write(unsigned char C) override {
+    OS.push_back(C);
+    return *this;
+  }
+  raw_ostream &write(const char *Ptr, size_t Size) override {
+    OS.append(Ptr, Ptr + Size);
+    return *this;
+  }
 
-  /// This is called when the SmallVector we're appending to is changed outside
-  /// of the raw_svector_ostream's control.  It is only safe to do this if the
-  /// raw_svector_ostream has previously been flushed.
-  void resync();
+  // FIXME: remove resync() and users.
+  void resync() {}
 
-  /// Flushes the stream contents to the target vector and return a StringRef
-  /// for the vector contents.
-  StringRef str();
+  /// Return a StringRef for the vector contents.
+  StringRef str() { return StringRef(OS.data(), OS.size()); }
 };
 
 /// A raw_ostream that discards all output.
@@ -539,9 +541,7 @@
   SmallVector<char, 0> Buffer;
 
 public:
-  buffer_ostream(raw_ostream &OS) : raw_svector_ostream(Buffer, 0), OS(OS) {
-    init();
-  }
+  buffer_ostream(raw_ostream &OS) : raw_svector_ostream(Buffer), OS(OS) {}
   ~buffer_ostream() { OS << str(); }
 };
 
Index: lib/Support/raw_ostream.cpp
===================================================================
--- lib/Support/raw_ostream.cpp	(revision 236389)
+++ lib/Support/raw_ostream.cpp	(working copy)
@@ -752,78 +752,6 @@
 }
 
 //===----------------------------------------------------------------------===//
-//  raw_svector_ostream
-//===----------------------------------------------------------------------===//
-
-// The raw_svector_ostream implementation uses the SmallVector itself as the
-// buffer for the raw_ostream. We guarantee that the raw_ostream buffer is
-// always pointing past the end of the vector, but within the vector
-// capacity. This allows raw_ostream to write directly into the correct place,
-// and we only need to set the vector size when the data is flushed.
-
-raw_svector_ostream::raw_svector_ostream(SmallVectorImpl<char> &O, unsigned)
-    : OS(O) {}
-
-raw_svector_ostream::raw_svector_ostream(SmallVectorImpl<char> &O) : OS(O) {
-  init();
-}
-
-void raw_svector_ostream::init() {
-  // Set up the initial external buffer. We make sure that the buffer has at
-  // least 128 bytes free; raw_ostream itself only requires 64, but we want to
-  // make sure that we don't grow the buffer unnecessarily on destruction (when
-  // the data is flushed). See the FIXME below.
-  OS.reserve(OS.size() + 128);
-  SetBuffer(OS.end(), OS.capacity() - OS.size());
-}
-
-raw_svector_ostream::~raw_svector_ostream() {
-  // FIXME: Prevent resizing during this flush().
-  flush();
-}
-
-void raw_svector_ostream::pwrite_impl(const char *Ptr, size_t Size,
-                                      uint64_t Offset) {
-  flush();
-  memcpy(OS.begin() + Offset, Ptr, Size);
-}
-
-/// resync - This is called when the SmallVector we're appending to is changed
-/// outside of the raw_svector_ostream's control.  It is only safe to do this
-/// if the raw_svector_ostream has previously been flushed.
-void raw_svector_ostream::resync() {
-  assert(GetNumBytesInBuffer() == 0 && "Didn't flush before mutating vector");
-
-  if (OS.capacity() - OS.size() < 64)
-    OS.reserve(OS.capacity() * 2);
-  SetBuffer(OS.end(), OS.capacity() - OS.size());
-}
-
-void raw_svector_ostream::write_impl(const char *Ptr, size_t Size) {
-  if (Ptr == OS.end()) {
-    // Grow the buffer to include the scratch area without copying.
-    size_t NewSize = OS.size() + Size;
-    assert(NewSize <= OS.capacity() && "Invalid write_impl() call!");
-    OS.set_size(NewSize);
-  } else {
-    assert(!GetNumBytesInBuffer());
-    OS.append(Ptr, Ptr + Size);
-  }
-
-  OS.reserve(OS.size() + 64);
-  SetBuffer(OS.end(), OS.capacity() - OS.size());
-}
-
-uint64_t raw_svector_ostream::current_pos() const {
-   return OS.size();
-}
-
-StringRef raw_svector_ostream::str() {
-  flush();
-  return StringRef(OS.begin(), OS.size());
-}
-
-//===----------------------------------------------------------------------===//
 //  raw_null_ostream
 //===----------------------------------------------------------------------===//
 


More information about the llvm-dev mailing list