Pickle::Write* micro-optimizations

base/pickle.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/pickle.h"
 
 #include <stdlib.h>
 
 #include <algorithm>  // for max()
 
@@ skipping 135 matching lines @@
     return false;
   *data = read_from;
   return true;
 }
 
 // Payload is uint32 aligned.
 
 Pickle::Pickle()
     : header_(NULL),
       header_size_(sizeof(Header)),
-      capacity_(0) {
+      capacity_(0),
+      write_offset_(0) {
   Resize(kPayloadUnit);
   header_->payload_size = 0;
 }
 
 Pickle::Pickle(int header_size)
     : header_(NULL),
       header_size_(AlignInt(header_size, sizeof(uint32))),
-      capacity_(0) {
+      capacity_(0),
+      write_offset_(0) {
   DCHECK_GE(static_cast<size_t>(header_size), sizeof(Header));
   DCHECK_LE(header_size, kPayloadUnit);
   Resize(kPayloadUnit);
   header_->payload_size = 0;
 }
 
 Pickle::Pickle(const char* data, int data_len)
     : header_(reinterpret_cast<Header*>(const_cast<char*>(data))),
       header_size_(0),
-      capacity_(kCapacityReadOnly) {
+      capacity_(kCapacityReadOnly),
+      write_offset_(0) {
   if (data_len >= static_cast<int>(sizeof(Header)))
     header_size_ = data_len - header_->payload_size;
 
   if (header_size_ > static_cast<unsigned int>(data_len))
     header_size_ = 0;
 
   if (header_size_ != AlignInt(header_size_, sizeof(uint32)))
     header_size_ = 0;
 
   // If there is anything wrong with the data, we're not going to use it.
   if (!header_size_)
     header_ = NULL;
 }
 
 Pickle::Pickle(const Pickle& other)
     : header_(NULL),
       header_size_(other.header_size_),
-      capacity_(0) {
-  size_t payload_size = header_size_ + other.header_->payload_size;
-  Resize(payload_size);
-  memcpy(header_, other.header_, payload_size);
+      capacity_(0),
+      write_offset_(other.write_offset_) {
+  Resize(other.header_->payload_size);
+  memcpy(header_, other.header_, header_size_ + other.header_->payload_size);
 }
 
 Pickle::~Pickle() {
   if (capacity_ != kCapacityReadOnly)
     free(header_);
 }
 
 Pickle& Pickle::operator=(const Pickle& other) {
   if (this == &other) {
     NOTREACHED();
     return *this;
   }
   if (capacity_ == kCapacityReadOnly) {
     header_ = NULL;
     capacity_ = 0;
   }
   if (header_size_ != other.header_size_) {
     free(header_);
     header_ = NULL;
     header_size_ = other.header_size_;
   }
-  Resize(other.header_size_ + other.header_->payload_size);
+  Resize(other.header_->payload_size);
   memcpy(header_, other.header_,
          other.header_size_ + other.header_->payload_size);
+  write_offset_ = other.write_offset_;
   return *this;
 }
 
 bool Pickle::WriteString(const std::string& value) {
   if (!WriteInt(static_cast<int>(value.size())))
     return false;
 
   return WriteBytes(value.data(), static_cast<int>(value.size()));
 }
 
@@ skipping 10 matching lines @@
     return false;
 
   return WriteBytes(value.data(),
                     static_cast<int>(value.size()) * sizeof(char16));
 }
 
 bool Pickle::WriteData(const char* data, int length) {
   return length >= 0 && WriteInt(length) && WriteBytes(data, length);
 }
 
-bool Pickle::WriteBytes(const void* data, int data_len) {
+inline void Pickle::WriteBytesCommon(const void* data, size_t length) {

[jar (doing other things), 2013/10/24 22:36:48]

Note that inline is a "hint" and is traditionally totally ignored by compilers,
since the compiler can usually figure this out better than the programmer.... so
they ignore it.

[piman, 2013/10/24 23:54:29]

Both clang and gcc failed to inline without it.
Without inlining, no specialization on the size is possible.

   DCHECK_NE(kCapacityReadOnly, capacity_) << "oops: pickle is readonly";
+#ifdef ARCH_CPU_64_BITS
+  DCHECK_LE(static_cast<size_t>(length), kuint32max);

[jar (doing other things), 2013/10/24 22:36:48]

nit: length is already of type size_t

Also... if you have concerns about overflow, wouldn't you want to be sure you
were:
DCHECK_LE(length, kuint32max - sizeof(uint32) + 1)
since you're about to potentially increase length a bit?

... or you could check that RSN:
DCHECK(data_len >= length);
and/or maybe:
DCHECK(static_cast<uint32>(data_len), static_cast<uint32>(length));

...which makes me wonder why these are DCHECKs.

Is there something in the code which assures we won't have such problems, and
these are really fallback developer protection?

[piman, 2013/10/24 23:54:29]

Yep, sorry, copy-and-paste from the previous version.
I don't particularly have concerns about overflow. We can add DCHECKs. This is
not meant to be called with untrusted data.
So, this is no change wrt previous code. As I mentioned, it's not meant to be
called with untrusted data, nor enough data that it would overflow (e.g.
messages would go over the limit of 256MB before we get to overflow).

I would severely push back against adding CHECKs, because that halves the
performance.

[piman, 2013/10/25 03:11:41]

Done.
I added some DCHECKs to ensure:
length <= data_len <= kuint32max (i.e. no overflow in AlignInt)
write_offset_ <= kuint32max - data_len <=> write_offset_ + data_len <=
kuint32max (i.e. no overflow in new_size computation).

+#endif
+  size_t data_len = AlignInt(length, sizeof(uint32));
+  size_t new_size = write_offset_ + data_len;

[jar (doing other things), 2013/10/24 22:36:48]

How are you assured that this is not an overflow?

Same question around line 287.

[piman, 2013/10/24 23:54:29]

The previous code (in BeginWrite) didn't check for overflow. I can add DCHECKs
if you want.

+  if (new_size > capacity_) {
+    Resize(std::max(capacity_ * 2, new_size));
+  }
 
-  char* dest = BeginWrite(data_len);
-  if (!dest)
-    return false;
+  char* write = mutable_payload() + write_offset_;
+  memcpy(write, data, length);
+  memset(write + length, 0, data_len - length);
+  header_->payload_size = write_offset_ + length;
+  write_offset_ = new_size;
+}
 
-  memcpy(dest, data, data_len);
-
-  EndWrite(dest, data_len);
+bool Pickle::WriteBytes(const void* data, int length) {
+  WriteBytesCommon(data, length);
   return true;
 }
 
-void Pickle::Reserve(size_t length) {
-  // write at a uint32-aligned offset from the beginning of the header
-  size_t offset = AlignInt(header_->payload_size, sizeof(uint32));
-
-  size_t new_size = offset + length;
-  size_t needed_size = header_size_ + new_size;
-  if (needed_size > capacity_)
-    Resize(capacity_ * 2 + needed_size);
+template <size_t length> void Pickle::WriteBytesStatic(const void* data) {
+  WriteBytesCommon(data, length);

[jar (doing other things), 2013/10/24 22:36:48]

For all the template magic... it appears that you changed calling with an
argument:
sizeof(foo)

to calling a template which handled the type
which forwarded to a template that specialized for the size
that called into the common code taking length.

I was *expecting* specialization to use type assignments such as moving across a
uint32 when size was 4..... and using this carefully only when you had proper
alignment... but that does not appear to be the case.

Can you clarify why this is an optimization, rather than just a lot of use of
templates?

Is the hope that your explicit statement in lines 281-283 will cause the
templates to be instantiated, and then all the code within them to be inlined?  

To be honest, I thought there was a good chance that a killer compiler could
already have done most of the inlining and propagation of calling constants that
you seem to be chasing.  Have you looked at compiled assembly code after full
optimization to see how the code already looked?

[piman, 2013/10/24 23:54:29]

It's possible to do, but then you need template instantiations for each of the
types, whereas you actually only need the size of the type in the resulting
code.
In this version, we only need one instantiation for each of the sizes, so we
have less bloat. WritePOD does the type->size translation, is fully inline and
so doesn't take any space.
I indicated some of the savings in an earlier version of the patch. Essentially,
if the size is known at compile-time, the compiler will:
1- elide the AlignInt logic and the memset it size is multiple of 4 (common
case)
2- inline the memcpy
Yes. I verified the code with objdump.
At the callsites for, say, WriteInt, it doesn't have the definition for
WriteBytes, so it won't inline it. Since it won't inline it, it will call the
generic version, passing the size as a run-time parameter. It has no way of
eliding/inlining what I mentioned above.
I tried calling WriteBytes from WriteBytesStatic, but gcc failed to inline. I
can't make WriteBytes itself inline because the callsites don't have the
definition. So the solution was to add an intermediate inline WriteBytesCommon,
that is only called where the definition is available. The compiler properly
inlines/specializes (I verified with objdump).
I drove this work by looking at the output code in parallel with the performance
measurements.

 }
 
-char* Pickle::BeginWrite(size_t length) {
-  // write at a uint32-aligned offset from the beginning of the header
-  size_t offset = AlignInt(header_->payload_size, sizeof(uint32));
+template void Pickle::WriteBytesStatic<2>(const void* data);
+template void Pickle::WriteBytesStatic<4>(const void* data);
+template void Pickle::WriteBytesStatic<8>(const void* data);
 
-  size_t new_size = offset + length;
-  size_t needed_size = header_size_ + new_size;
-  if (needed_size > capacity_)
-    Resize(std::max(capacity_ * 2, needed_size));
-
-#ifdef ARCH_CPU_64_BITS
-  DCHECK_LE(length, kuint32max);
-#endif
-
-  header_->payload_size = static_cast<uint32>(new_size);
-  return mutable_payload() + offset;
-}
-
-void Pickle::EndWrite(char* dest, int length) {
-  // Zero-pad to keep tools like valgrind from complaining about uninitialized
-  // memory.
-  if (length % sizeof(uint32))
-    memset(dest + length, 0, sizeof(uint32) - (length % sizeof(uint32)));
+void Pickle::Reserve(size_t length) {
+  size_t data_len = AlignInt(length, sizeof(uint32));
+  size_t new_size = write_offset_ + data_len;
+  if (new_size > capacity_)
+    Resize(capacity_ * 2 + new_size);
 }
 
 void Pickle::Resize(size_t new_capacity) {
   CHECK_NE(capacity_, kCapacityReadOnly);
 
   new_capacity = AlignInt(new_capacity, kPayloadUnit);
-  void* p = realloc(header_, new_capacity);
+  void* p = realloc(header_, header_size_ + new_capacity);
   header_ = reinterpret_cast<Header*>(p);
   capacity_ = new_capacity;
 }
 
 // static
 const char* Pickle::FindNext(size_t header_size,
                              const char* start,
                              const char* end) {
   DCHECK_EQ(header_size, AlignInt(header_size, sizeof(uint32)));
   DCHECK_LE(header_size, static_cast<size_t>(kPayloadUnit));
 
   if (static_cast<size_t>(end - start) < sizeof(Header))
     return NULL;
 
   const Header* hdr = reinterpret_cast<const Header*>(start);
   const char* payload_base = start + header_size;
   const char* payload_end = payload_base + hdr->payload_size;
   if (payload_end < payload_base)
     return NULL;
 
   return (payload_end > end) ? NULL : payload_end;
 }