Convert SkWriter32 to use an SkTDArray for its internal storage.

This reduces the allocation overhead of a null picture (create, beginRecording(), endRecording) from about 18K to about 1.9K.  (There's still lots more to prune.)

SkPictureFlat can exploit the fact that Writer32 is contiguous simplify its memory management.  The Writer32 itself becomes the scratch buffer.

Remove lots and lots of arbitrary magic numbers that were size guesses and minimum allocation sizes.  Keep your eyes open for the big obvious DUH why we save 16K per picture!  (Spoiler alert.  It's because that first save we issue in beginRecording() forces the old SkWriter32 to allocate 16K.)

Tests passing, DM passing.

bench --match writer: ~20% faster
null bench_record: ~30% faster
bench_record on buildbot .skps: ~3-6% slower, ranging 25% faster to 20% slower
bench_pictures on buildbot .skps: ~1-2% faster, ranging 13% faster to 28% slower

BUG=skia:1850
R=reed@google.com

Author: mtklein@google.com

Review URL: https://codereview.chromium.org/137433003

git-svn-id: http://skia.googlecode.com/svn/trunk@13073 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 109 insertions, 136 deletions

diff --git a/include/core/SkWriter32.h b/include/core/SkWriter32.h
index 9fb1f7b85b..61d4a95f7e 100644
--- a/include/core/SkWriter32.h
+++ b/include/core/SkWriter32.h
@@ -10,74 +10,96 @@
 #ifndef SkWriter32_DEFINED
 #define SkWriter32_DEFINED
 
-#include "SkTypes.h"
-
-#include "SkScalar.h"
+#include "SkMatrix.h"
 #include "SkPath.h"
 #include "SkPoint.h"
-#include "SkRect.h"
 #include "SkRRect.h"
-#include "SkMatrix.h"
+#include "SkRect.h"
 #include "SkRegion.h"
-
-class SkStream;
-class SkWStream;
+#include "SkScalar.h"
+#include "SkStream.h"
+#include "SkTDArray.h"
+#include "SkTypes.h"
 
 class SkWriter32 : SkNoncopyable {
-    struct BlockHeader;
 public:
     /**
      *  The caller can specify an initial block of storage, which the caller manages.
-     *  SkWriter32 will not attempt to free this in its destructor. It is up to the
-     *  implementation to decide if, and how much, of the storage to utilize, and it
-     *  is possible that it may be ignored entirely.
+     *
+     *  SkWriter32 will try to back reserve and write calls with this external storage until the
+     *  first time an allocation doesn't fit.  From then it will use dynamically allocated storage.
+     *  This used to be optional behavior, but pipe now relies on it.
      */
-    SkWriter32(size_t minSize, void* initialStorage, size_t storageSize);
-
-    SkWriter32(size_t minSize)
-        : fHead(NULL)
-        , fTail(NULL)
-        , fMinSize(minSize)
-        , fSize(0)
-        , fWrittenBeforeLastBlock(0)
-        {}
-
-    ~SkWriter32();
+    SkWriter32(void* external = NULL, size_t externalBytes = 0) {
+        this->reset(external, externalBytes);
+    }
 
     // return the current offset (will always be a multiple of 4)
-    size_t bytesWritten() const { return fSize; }
+    size_t bytesWritten() const { return fCount * 4; }
 
     SK_ATTR_DEPRECATED("use bytesWritten")
     size_t size() const { return this->bytesWritten(); }
 
-    // Returns true if we've written only into the storage passed into constructor or reset.
-    // (You may be able to use this to avoid a call to flatten.)
-    bool wroteOnlyToStorage() const {
-        return fHead == &fExternalBlock && this->bytesWritten() <= fExternalBlock.fSizeOfBlock;
+    void reset(void* external = NULL, size_t externalBytes = 0) {
+        SkASSERT(SkIsAlign4((uintptr_t)external));
+        SkASSERT(SkIsAlign4(externalBytes));
+        fExternal = (uint32_t*)external;
+        fExternalLimit = externalBytes/4;
+        fCount = 0;
+        fInternal.rewind();
     }
 
-    void reset();
-    void reset(void* storage, size_t size);
+    // If all data written is contiguous, then this returns a pointer to it, otherwise NULL.
+    // This will work if we've only written to the externally supplied block of storage, or if we've
+    // only written to our internal dynamic storage, but will fail if we have written into both.
+    const uint32_t* contiguousArray() const {
+        if (this->externalCount()  == 0) {
+            return fInternal.begin();
+        } else if (fInternal.isEmpty()) {
+            return fExternal;
+        }
+        return NULL;
+    }
 
     // size MUST be multiple of 4
     uint32_t* reserve(size_t size) {
         SkASSERT(SkAlign4(size) == size);
+        const int count = size/4;
+
+        uint32_t* p;
+        // Once we start writing to fInternal, we never write to fExternal again.
+        // This simplifies tracking what data is where.
+        if (fInternal.isEmpty() && this->externalCount() + count <= fExternalLimit) {
+            p = fExternal + fCount;
+        } else {
+            p = fInternal.append(count);
+        }
+
+        fCount += count;
+        return p;
+    }
 
-        Block* block = fTail;
-        if (NULL == block || block->available() < size) {
-            block = this->doReserve(size);
+    // return the address of the 4byte int at the specified offset (which must
+    // be a multiple of 4. This does not allocate any new space, so the returned
+    // address is only valid for 1 int.
+    uint32_t* peek32(size_t offset) {
+        SkASSERT(SkAlign4(offset) == offset);
+        const int count = offset/4;
+        SkASSERT(count < fCount);
+
+        if (count < this->externalCount()) {
+            return fExternal + count;
         }
-        fSize += size;
-        return block->alloc(size);
+        return &fInternal[count - this->externalCount()];
     }
 
     bool writeBool(bool value) {
-        this->writeInt(value);
+        this->write32(value);
         return value;
     }
 
     void writeInt(int32_t value) {
-        *(int32_t*)this->reserve(sizeof(value)) = value;
+        this->write32(value);
     }
 
     void write8(int32_t value) {
@@ -92,15 +114,8 @@ public:
         *(int32_t*)this->reserve(sizeof(value)) = value;
     }
 
-    void writePtr(void* ptr) {
-        // Since we "know" that we're always 4-byte aligned, we can tell the
-        // compiler that here, by assigning to an int32 ptr.
-        int32_t* addr = (int32_t*)this->reserve(sizeof(void*));
-        if (4 == sizeof(void*)) {
-            *(void**)addr = ptr;
-        } else {
-            memcpy(addr, &ptr, sizeof(void*));
-        }
+    void writePtr(void* value) {
+        *(void**)this->reserve(sizeof(value)) = value;
     }
 
     void writeScalar(SkScalar value) {
@@ -152,9 +167,8 @@ public:
      */
     void write(const void* values, size_t size) {
         SkASSERT(SkAlign4(size) == size);
-        // if we could query how much is avail in the current block, we might
-        // copy that much, and then alloc the rest. That would reduce the waste
-        // in the current block
+        // TODO: If we're going to spill from fExternal to fInternal, we might want to fill
+        // fExternal as much as possible before writing to fInternal.
         memcpy(this->reserve(size), values, size);
     }
 
@@ -162,12 +176,25 @@ public:
      *  Reserve size bytes. Does not need to be 4 byte aligned. The remaining space (if any) will be
      *  filled in with zeroes.
      */
-    uint32_t* reservePad(size_t size);
+    uint32_t* reservePad(size_t size) {
+        uint32_t* p = this->reserve(SkAlign4(size));
+        uint8_t* tail = (uint8_t*)p + size;
+        switch (SkAlign4(size) - size) {
+            default: SkDEBUGFAIL("SkAlign4(x) - x should always be 0, 1, 2, or 3.");
+            case 3: *tail++ = 0x00;  // fallthrough is intentional
+            case 2: *tail++ = 0x00;  // fallthrough is intentional
+            case 1: *tail++ = 0x00;
+            case 0: ;/*nothing to do*/
+        }
+        return p;
+    }
 
     /**
      *  Write size bytes from src, and pad to 4 byte alignment with zeroes.
      */
-    void writePad(const void* src, size_t size);
+    void writePad(const void* src, size_t size) {
+        memcpy(this->reservePad(size), src, size);
+    }
 
     /**
      *  Writes a string to the writer, which can be retrieved with
@@ -186,103 +213,49 @@ public:
      */
     static size_t WriteStringSize(const char* str, size_t len = (size_t)-1);
 
-    // return the address of the 4byte int at the specified offset (which must
-    // be a multiple of 4. This does not allocate any new space, so the returned
-    // address is only valid for 1 int.
-    uint32_t* peek32(size_t offset);
-
     /**
      *  Move the cursor back to offset bytes from the beginning.
      *  This has the same restrictions as peek32: offset must be <= size() and
      *  offset must be a multiple of 4.
      */
-    void rewindToOffset(size_t offset);
+    void rewindToOffset(size_t offset) {
+        SkASSERT(SkAlign4(offset) == offset);
+        const int count = offset/4;
+        if (count < this->externalCount()) {
+            fInternal.setCount(0);
+        } else {
+            fInternal.setCount(count - this->externalCount());
+        }
+        fCount = count;
+    }
 
     // copy into a single buffer (allocated by caller). Must be at least size()
-    void flatten(void* dst) const;
+    void flatten(void* dst) const {
+        const size_t externalBytes = this->externalCount()*4;
+        memcpy(dst, fExternal, externalBytes);
+        dst = (uint8_t*)dst + externalBytes;
+        memcpy(dst, fInternal.begin(), fInternal.bytes());
+    }
+
+    bool writeToStream(SkWStream* stream) const {
+        return stream->write(fExternal, this->externalCount()*4)
+            && stream->write(fInternal.begin(), fInternal.bytes());
+    }
 
     // read from the stream, and write up to length bytes. Return the actual
     // number of bytes written.
-    size_t readFromStream(SkStream*, size_t length);
-
-    bool writeToStream(SkWStream*);
-
-private:
-    struct Block {
-        Block*  fNext;
-        char*   fBasePtr;
-        size_t  fSizeOfBlock;      // total space allocated (after this)
-        size_t  fAllocatedSoFar;    // space used so far
-
-        size_t  available() const { return fSizeOfBlock - fAllocatedSoFar; }
-        char*   base() { return fBasePtr; }
-        const char* base() const { return fBasePtr; }
-
-        uint32_t* alloc(size_t size) {
-            SkASSERT(SkAlign4(size) == size);
-            SkASSERT(this->available() >= size);
-            void* ptr = this->base() + fAllocatedSoFar;
-            fAllocatedSoFar += size;
-            SkASSERT(fAllocatedSoFar <= fSizeOfBlock);
-            return (uint32_t*)ptr;
-        }
-
-        uint32_t* peek32(size_t offset) {
-            SkASSERT(offset <= fAllocatedSoFar + 4);
-            void* ptr = this->base() + offset;
-            return (uint32_t*)ptr;
-        }
-
-        void rewind() {
-            fNext = NULL;
-            fAllocatedSoFar = 0;
-            // keep fSizeOfBlock as is
-        }
-
-        static Block* Create(size_t size) {
-            SkASSERT(SkIsAlign4(size));
-            Block* block = (Block*)sk_malloc_throw(sizeof(Block) + size);
-            block->fNext = NULL;
-            block->fBasePtr = (char*)(block + 1);
-            block->fSizeOfBlock = size;
-            block->fAllocatedSoFar = 0;
-            return block;
-        }
-
-        Block* initFromStorage(void* storage, size_t size) {
-            SkASSERT(SkIsAlign4((intptr_t)storage));
-            SkASSERT(SkIsAlign4(size));
-            Block* block = this;
-            block->fNext = NULL;
-            block->fBasePtr = (char*)storage;
-            block->fSizeOfBlock = size;
-            block->fAllocatedSoFar = 0;
-            return block;
-        }
-    };
-
-    enum {
-        MIN_BLOCKSIZE = sizeof(SkWriter32::Block) + sizeof(intptr_t)
-    };
-
-    Block       fExternalBlock;
-    Block*      fHead;
-    Block*      fTail;
-    size_t      fMinSize;
-    size_t      fSize;
-    // sum of bytes written in all blocks *before* fTail
-    size_t      fWrittenBeforeLastBlock;
-
-    bool isHeadExternallyAllocated() const {
-        return fHead == &fExternalBlock;
+    size_t readFromStream(SkStream* stream, size_t length) {
+        return stream->read(this->reservePad(length), length);
     }
 
-    Block* newBlock(size_t bytes);
-
-    // only call from reserve()
-    Block* doReserve(size_t bytes);
+private:
+    // Number of uint32_t written into fExternal.  <= fExternalLimit.
+    int externalCount() const { return fCount - fInternal.count(); }
 
-    SkDEBUGCODE(void validate() const;)
+    int fCount;                     // Total number of uint32_t written.
+    int fExternalLimit;             // Number of uint32_t we can write to fExternal.
+    uint32_t* fExternal;            // Unmanaged memory block.
+    SkTDArray<uint32_t> fInternal;  // Managed memory block.
 };
 
 /**
@@ -293,7 +266,7 @@ private:
  */
 template <size_t SIZE> class SkSWriter32 : public SkWriter32 {
 public:
-    SkSWriter32(size_t minSize) : SkWriter32(minSize, fData.fStorage, SIZE) {}
+    SkSWriter32() : SkWriter32(fData.fStorage, SIZE) {}
 
 private:
     union {