Add GrMemoryPool as a helper to override operators new/delete

Review URL: http://codereview.appspot.com/6306090/



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

9 files changed, 652 insertions, 3 deletions

diff --git a/bench/GrMemoryPoolBench.cpp b/bench/GrMemoryPoolBench.cpp
new file mode 100644
index 0000000000..2fad7fcf4d
--- /dev/null
+++ b/bench/GrMemoryPoolBench.cpp
@@ -0,0 +1,164 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "GrMemoryPool.h"
+#include "SkBenchmark.h"
+#include "SkRandom.h"
+#include "SkTScopedPtr.h"
+#include "SkTDArray.h"
+
+// change this to 0 to compare GrMemoryPool to default new / delete
+#define OVERRIDE_NEW    1
+
+namespace {
+struct A {
+    int gStuff[10];
+#if OVERRIDE_NEW
+    void* operator new (size_t size) { return gPool.allocate(size); }
+    void operator delete (void* mem) { if (mem) { return gPool.release(mem); } }
+#endif
+    static GrMemoryPool gPool;
+};
+GrMemoryPool A::gPool(10 * (1 << 10), 10 * (1 << 10));
+}
+
+
+/**
+ * This benchmark creates and deletes objects in stack order
+ */
+class GrMemoryPoolBenchStack : public SkBenchmark {
+    enum {
+        N = SkBENCHLOOP(5 * (1 << 20)),
+    };
+public:
+    GrMemoryPoolBenchStack(void* param) : INHERITED(param) {
+    }
+protected:
+    virtual const char* onGetName() {
+        return "grmemorypool_stack";
+    }
+
+    virtual void onDraw(SkCanvas* canvas) {
+        SkRandom r;
+        enum {
+            kMaxObjects = 4 * (1 << 10),
+        };
+        A* objects[kMaxObjects];
+
+        // We delete if a random [-1, 1] fixed pt is < the thresh. Otherwise,
+        // we allocate. We start allocate-biased and ping-pong to delete-biased
+        SkFixed delThresh = -SK_FixedHalf;
+        enum {
+            kSwitchThreshPeriod = N / (2 * kMaxObjects),
+        };
+        int s = 0;
+
+        int count = 0;
+        for (int i = 0; i < N; i++, ++s) {
+            if (kSwitchThreshPeriod == s) {
+                delThresh = -delThresh;
+                s = 0;
+            }
+            SkFixed del = r.nextSFixed1();
+            if (count && 
+                (kMaxObjects == count || del < delThresh)) {
+                delete objects[count-1];
+                --count;
+            } else {
+                objects[count] = new A;
+                ++count;
+            }
+        }
+        for (int i = 0; i < count; ++i) {
+            delete objects[i];
+        }
+    }
+
+private:
+    typedef SkBenchmark INHERITED;
+};
+
+/**
+ * This benchmark creates objects and deletes them in random order
+ */
+class GrMemoryPoolBenchRandom : public SkBenchmark {
+    enum {
+        N = SkBENCHLOOP(5 * (1 << 20)),
+    };
+public:
+    GrMemoryPoolBenchRandom(void* param) : INHERITED(param) {
+    }
+protected:
+    virtual const char* onGetName() {
+        return "grmemorypool_random";
+    }
+
+    virtual void onDraw(SkCanvas* canvas) {
+        SkRandom r;
+        enum {
+            kMaxObjects = 4 * (1 << 10),
+        };
+        SkTScopedPtr<A> objects[kMaxObjects];
+
+        for (int i = 0; i < N; i++) {
+            uint32_t idx = r.nextRangeU(0, kMaxObjects-1);
+            if (NULL == objects[idx].get()) {
+                objects[idx].reset(new A);
+            } else {
+                objects[idx].reset(NULL);
+            }
+        }
+    }
+
+private:
+    typedef SkBenchmark INHERITED;
+};
+
+/**
+ * This benchmark creates objects and deletes them in queue order
+ */
+class GrMemoryPoolBenchQueue : public SkBenchmark {
+    enum {
+        N = SkBENCHLOOP((1 << 10)),
+        M = SkBENCHLOOP(4 * (1 << 10)),
+    };
+public:
+    GrMemoryPoolBenchQueue(void* param) : INHERITED(param) {
+    }
+protected:
+    virtual const char* onGetName() {
+        return "grmemorypool_queue";
+    }
+
+    virtual void onDraw(SkCanvas* canvas) {
+        SkRandom r;
+        A* objects[M];
+        for (int i = 0; i < N; i++) {
+            uint32_t count = r.nextRangeU(0, M-1);
+            for (uint32_t i = 0; i < count; i++) {
+                objects[i] = new A;
+            }
+            for (uint32_t i = 0; i < count; i++) {
+                delete objects[i];
+            }
+        }
+    }
+
+private:
+    typedef SkBenchmark INHERITED;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+static SkBenchmark* Fact1(void* p) { return new GrMemoryPoolBenchStack(p); }
+static SkBenchmark* Fact2(void* p) { return new GrMemoryPoolBenchRandom(p); }
+static SkBenchmark* Fact3(void* p) { return new GrMemoryPoolBenchQueue(p); }
+
+static BenchRegistry gReg01(Fact1);
+static BenchRegistry gReg02(Fact2);
+static BenchRegistry gReg03(Fact3);
+
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index fcefa7f321..9dd1e115dd 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -25,6 +25,7 @@
     '../bench/DecodeBench.cpp',
     '../bench/FontScalerBench.cpp',
     '../bench/GradientBench.cpp',
+    '../bench/GrMemoryPoolBench.cpp',
     '../bench/InterpBench.cpp',
     '../bench/MathBench.cpp',
     '../bench/MatrixBench.cpp',
diff --git a/gyp/gpu.gyp b/gyp/gpu.gyp
index f5d15ed1b0..ffe0e05f63 100644
--- a/gyp/gpu.gyp
+++ b/gyp/gpu.gyp
@@ -243,6 +243,8 @@
         '../src/gpu/GrInOrderDrawBuffer.h',
         '../src/gpu/GrMatrix.cpp',
         '../src/gpu/GrMemory.cpp',
+        '../src/gpu/GrMemoryPool.cpp',
+        '../src/gpu/GrMemoryPool.h',
         '../src/gpu/GrPath.h',
         '../src/gpu/GrPathRendererChain.cpp',
         '../src/gpu/GrPathRendererChain.h',
diff --git a/gyp/tests.gyp b/gyp/tests.gyp
index 646f4ae225..22aa3c43d6 100644
--- a/gyp/tests.gyp
+++ b/gyp/tests.gyp
@@ -44,6 +44,7 @@
         '../tests/GLInterfaceValidation.cpp',
         '../tests/GLProgramsTest.cpp',
         '../tests/GradientTest.cpp',
+        '../tests/GrMemoryPoolTest.cpp',
         '../tests/InfRectTest.cpp',
         '../tests/MathTest.cpp',
         '../tests/MatrixTest.cpp',
diff --git a/include/core/SkInstCnt.h b/include/core/SkInstCnt.h
index f3519a14dd..e5c44db11c 100644
--- a/include/core/SkInstCnt.h
+++ b/include/core/SkInstCnt.h
@@ -53,6 +53,10 @@
         static SkTArray<PFCheckInstCnt> gChildren;                          \
     } fInstanceCountHelper;                                                 \
                                                                             \
+    static int32_t GetInstanceCount() {                                     \
+        return SkInstanceCountHelper::gInstanceCount;                       \
+    }                                                                       \
+                                                                            \
     static void CheckInstanceCount() {                                      \
         if (0 != SkInstanceCountHelper::gInstanceCount) {                   \
             SkDebugf("Leaked %s objects: %d\n", #className,                 \
diff --git a/include/gpu/GrTypes.h b/include/gpu/GrTypes.h
index a5d85498fc..95527c1756 100644
--- a/include/gpu/GrTypes.h
+++ b/include/gpu/GrTypes.h
@@ -79,27 +79,33 @@ static inline int32_t GrIDivRoundUp(int x, int y) {
 static inline uint32_t GrUIDivRoundUp(uint32_t x, uint32_t y) {
     return (x + (y-1)) / y;
 }
-static inline size_t GrSizeDivRoundUp(size_t x, uint32_t y) {
+static inline size_t GrSizeDivRoundUp(size_t x, size_t y) {
     return (x + (y-1)) / y;
 }
 
+// compile time, evaluates Y multiple times
+#define GR_CT_DIV_ROUND_UP(X, Y) (((X) + ((Y)-1)) / (Y))
+
 /**
  *  align up
  */
 static inline uint32_t GrUIAlignUp(uint32_t x, uint32_t alignment) {
     return GrUIDivRoundUp(x, alignment) * alignment;
 }
-static inline uint32_t GrSizeAlignUp(size_t x, uint32_t alignment) {
+static inline size_t GrSizeAlignUp(size_t x, size_t alignment) {
     return GrSizeDivRoundUp(x, alignment) * alignment;
 }
 
+// compile time, evaluates A multiple times
+#define GR_CT_ALIGN_UP(X, A) (GR_CT_DIV_ROUND_UP((X),(A)) * (A))
+
 /**
  * amount of pad needed to align up
  */
 static inline uint32_t GrUIAlignUpPad(uint32_t x, uint32_t alignment) {
     return (alignment - x % alignment) % alignment;
 }
-static inline size_t GrSizeAlignUpPad(size_t x, uint32_t alignment) {
+static inline size_t GrSizeAlignUpPad(size_t x, size_t alignment) {
     return (alignment - x % alignment) % alignment;
 }
 
diff --git a/src/gpu/GrMemoryPool.cpp b/src/gpu/GrMemoryPool.cpp
new file mode 100644
index 0000000000..597f88cbb8
--- /dev/null
+++ b/src/gpu/GrMemoryPool.cpp
@@ -0,0 +1,153 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "GrMemoryPool.h"
+
+#if GR_DEBUG
+    #define VALIDATE this->validate()
+#else
+    #define VALIDATE
+#endif
+
+GrMemoryPool::GrMemoryPool(size_t preallocSize, size_t minAllocSize) {
+    GR_DEBUGCODE(fAllocationCnt = 0);
+
+    minAllocSize = GrMax<size_t>(minAllocSize, 1 << 10);
+    fMinAllocSize = GrSizeAlignUp(minAllocSize + kPerAllocPad, kAlignment),
+    fPreallocSize = GrSizeAlignUp(preallocSize + kPerAllocPad, kAlignment);
+    fPreallocSize = GrMax(fPreallocSize, fMinAllocSize);
+
+    fHead = CreateBlock(fPreallocSize);
+    fTail = fHead;
+    fHead->fNext = NULL;
+    fHead->fPrev = NULL;
+    VALIDATE;
+};
+
+GrMemoryPool::~GrMemoryPool() {
+    VALIDATE;
+    GrAssert(0 == fAllocationCnt);
+    GrAssert(fHead == fTail);
+    GrAssert(0 == fHead->fLiveCount);
+    DeleteBlock(fHead);
+};
+
+void* GrMemoryPool::allocate(size_t size) {
+    VALIDATE;
+    size = GrSizeAlignUp(size, kAlignment);
+    size += kPerAllocPad;
+    if (fTail->fFreeSize < size) {
+        int blockSize = size;
+        blockSize = GrMax<size_t>(blockSize, fMinAllocSize);
+        BlockHeader* block = CreateBlock(blockSize);
+
+        block->fPrev = fTail;
+        block->fNext = NULL;
+        GrAssert(NULL == fTail->fNext);
+        fTail->fNext = block;
+        fTail = block;
+    }
+    GrAssert(fTail->fFreeSize >= size);
+    intptr_t ptr = fTail->fCurrPtr;
+    // We stash a pointer to the block header, just before the allocated space,
+    // so that we can decrement the live count on delete in constant time.
+    *reinterpret_cast<BlockHeader**>(ptr) = fTail;
+    ptr += kPerAllocPad;
+    fTail->fCurrPtr += size;
+    fTail->fFreeSize -= size;
+    fTail->fLiveCount += 1;
+    GR_DEBUGCODE(++fAllocationCnt);
+    VALIDATE;
+    return reinterpret_cast<void*>(ptr);
+}
+
+void GrMemoryPool::release(void* p) {
+    VALIDATE;
+    intptr_t ptr = reinterpret_cast<intptr_t>(p) - kPerAllocPad;
+    BlockHeader* block = *reinterpret_cast<BlockHeader**>(ptr);
+    if (1 == block->fLiveCount) {
+        // the head block is special, it is reset rather than deleted
+        if (fHead == block) {
+            fHead->fCurrPtr = reinterpret_cast<intptr_t>(fHead) +
+                                kHeaderSize;
+            fHead->fLiveCount = 0;
+            fHead->fFreeSize = fPreallocSize;
+        } else {
+            BlockHeader* prev = block->fPrev;
+            BlockHeader* next = block->fNext;
+            GrAssert(prev);
+            prev->fNext = next;
+            if (next) {
+                next->fPrev = prev;
+            } else {
+                GrAssert(fTail == block);
+                fTail = prev;
+            }
+            DeleteBlock(block);
+        }
+    } else {
+        --block->fLiveCount;
+    }
+    GR_DEBUGCODE(--fAllocationCnt);
+    VALIDATE;
+}
+
+GrMemoryPool::BlockHeader* GrMemoryPool::CreateBlock(size_t size) {
+    BlockHeader* block =
+        reinterpret_cast<BlockHeader*>(GrMalloc(size + kHeaderSize));
+    // we assume malloc gives us aligned memory
+    GrAssert(!(reinterpret_cast<intptr_t>(block) % kAlignment));
+    block->fLiveCount = 0;
+    block->fFreeSize = size;
+    block->fCurrPtr = reinterpret_cast<intptr_t>(block) + kHeaderSize;
+    return block;
+}
+
+void GrMemoryPool::DeleteBlock(BlockHeader* block) {
+    GrFree(block);
+}
+
+void GrMemoryPool::validate() {
+    BlockHeader* block = fHead;
+    BlockHeader* prev = NULL;
+    GrAssert(block);
+    int allocCount = 0;
+    do {
+        allocCount += block->fLiveCount;
+        GrAssert(prev == block->fPrev);
+        if (NULL != prev) {
+            GrAssert(prev->fNext == block);
+        }
+
+        intptr_t b = reinterpret_cast<intptr_t>(block);
+        size_t ptrOffset = block->fCurrPtr - b;
+        size_t totalSize = ptrOffset + block->fFreeSize;
+        size_t userSize = totalSize - kHeaderSize;
+        intptr_t userStart = b + kHeaderSize;
+
+        GrAssert(!(b % kAlignment));
+        GrAssert(!(totalSize % kAlignment));
+        GrAssert(!(userSize % kAlignment));
+        GrAssert(!(block->fCurrPtr % kAlignment));
+        if (fHead != block) {
+            GrAssert(block->fLiveCount);
+            GrAssert(userSize >= fMinAllocSize);
+        } else {
+            GrAssert(userSize == fPreallocSize);
+        }
+        if (!block->fLiveCount) {
+            GrAssert(ptrOffset ==  kHeaderSize);
+            GrAssert(userStart == block->fCurrPtr);
+        } else {
+            GrAssert(block == *reinterpret_cast<BlockHeader**>(userStart));
+        }
+        prev = block;
+    } while ((block = block->fNext));
+    GrAssert(allocCount == fAllocationCnt);
+    GrAssert(prev == fTail);
+}
+
diff --git a/src/gpu/GrMemoryPool.h b/src/gpu/GrMemoryPool.h
new file mode 100644
index 0000000000..08c9ee2bbe
--- /dev/null
+++ b/src/gpu/GrMemoryPool.h
@@ -0,0 +1,79 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrMemoryPool_DEFINED
+#define GrMemoryPool_DEFINED
+
+#include "GrTypes.h"
+
+/**
+ * Allocates memory in blocks and parcels out space in the blocks for allocation
+ * requests. It is optimized for allocate / release speed over memory
+ * effeciency. The interface is designed to be used to implement operator new
+ * and delete overrides. All allocations are expected to be released before the
+ * pool's destructor is called. Allocations will be 8-byte aligned.
+ */
+class GrMemoryPool {
+public:
+    /**
+     * Prealloc size is the amount of space to make available at pool creation
+     * time and keep around until pool destruction. The min alloc size is the
+     * smallest allowed size of additional allocations.
+     */
+    GrMemoryPool(size_t preallocSize, size_t minAllocSize);
+
+    ~GrMemoryPool();
+
+    /**
+     * Allocates memory. The memory must be freed with release().
+     */
+    void* allocate(size_t size);
+
+    /**
+     * p must have been returned by allocate()
+     */
+    void release(void* p);
+
+    /**
+     * Returns true if there are no unreleased allocations.
+     */
+    bool isEmpty() const { return fTail == fHead && !fHead->fLiveCount; }
+
+private:
+    struct BlockHeader;
+
+    BlockHeader* CreateBlock(size_t size);
+
+    void DeleteBlock(BlockHeader* block);
+
+    void validate();
+
+    struct BlockHeader {
+        BlockHeader* fNext;      // doubly-linked list of blocks.
+        BlockHeader* fPrev;
+        int          fLiveCount; // number of outstanding allocations in the
+                                 // block.
+        intptr_t     fCurrPtr;   // ptr to the start of blocks free space.
+        size_t       fFreeSize;  // amount of free space left in the block.
+    };
+
+    enum {
+        // We assume this alignment is good enough for everybody.
+        kAlignment    = 8,
+        kHeaderSize   = GR_CT_ALIGN_UP(sizeof(BlockHeader), kAlignment),
+        kPerAllocPad  = GR_CT_ALIGN_UP(sizeof(BlockHeader*), kAlignment),
+    };
+    size_t                            fPreallocSize;
+    size_t                            fMinAllocSize;
+    BlockHeader*                      fHead;
+    BlockHeader*                      fTail;
+#if GR_DEBUG
+    int                               fAllocationCnt;
+#endif
+};
+
+#endif
diff --git a/tests/GrMemoryPoolTest.cpp b/tests/GrMemoryPoolTest.cpp
new file mode 100644
index 0000000000..f5527e9b35
--- /dev/null
+++ b/tests/GrMemoryPoolTest.cpp
@@ -0,0 +1,239 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Test.h"
+#include "GrMemoryPool.h"
+#include "SkRandom.h"
+#include "SkTDArray.h"
+#include "SkTScopedPtr.h"
+#include "SkInstCnt.h"
+
+namespace {
+// A is the top of an inheritance tree of classes that overload op new and
+// and delete to use a GrMemoryPool. The objects have values of different types
+// that can be set and checked.
+class A {
+public:
+    A() {};
+    virtual void setValues(int v) {
+        fChar = static_cast<char>(v);
+    }
+    virtual bool checkValues(int v) {
+        return fChar == static_cast<char>(v);
+    }
+    virtual ~A() {};
+
+    void* operator new(size_t size) {
+        if (!gPool.get()) {
+            return ::operator new(size);
+        } else {
+            return gPool->allocate(size);
+        }
+    }
+
+    void operator delete(void* p) {
+        if (!gPool.get()) {
+            ::operator delete(p);
+        } else {
+            return gPool->release(p);
+        }
+    }
+
+    SK_DECLARE_INST_COUNT_ROOT(A);
+
+    static A* Create(SkRandom* r);
+
+    static void SetAllocator(size_t preallocSize, size_t minAllocSize) {
+        SkASSERT(0 == GetInstanceCount());
+        GrMemoryPool* pool = new GrMemoryPool(preallocSize, minAllocSize);
+        gPool.reset(pool);
+    }
+
+    static void ResetAllocator() {
+        SkASSERT(0 == GetInstanceCount());
+        gPool.reset(NULL);
+    }
+
+private:
+    static SkTScopedPtr<GrMemoryPool> gPool;
+    char fChar;
+};
+SK_DEFINE_INST_COUNT(A);
+SkTScopedPtr<GrMemoryPool> A::gPool;
+
+class B : public A {
+public:
+    B() {};
+    virtual void setValues(int v) {
+        fDouble = static_cast<double>(v);
+        this->INHERITED::setValues(v);
+    }
+    virtual bool checkValues(int v) {
+        return fDouble == static_cast<double>(v) &&
+               this->INHERITED::checkValues(v);
+    }
+    virtual ~B() {};
+
+private:
+    double fDouble;
+
+    typedef A INHERITED;
+};
+
+class C : public A {
+public:
+    C() {};
+    virtual void setValues(int v) {
+        fInt64 = static_cast<int64_t>(v);
+        this->INHERITED::setValues(v);
+    }
+    virtual bool checkValues(int v) {
+        return fInt64 == static_cast<int64_t>(v) &&
+               this->INHERITED::checkValues(v);
+    }
+    virtual ~C() {};
+
+private:
+    int64_t fInt64;
+
+    typedef A INHERITED;
+};
+
+// D derives from C and owns a dynamically created B
+class D : public C {
+public:
+    D() {
+        fB = new B();
+    }
+    virtual void setValues(int v) {
+        fVoidStar = reinterpret_cast<void*>(v);
+        this->INHERITED::setValues(v);
+        fB->setValues(v);
+    }
+    virtual bool checkValues(int v) {
+        return fVoidStar == reinterpret_cast<void*>(v) &&
+               fB->checkValues(v) &&
+               this->INHERITED::checkValues(v);
+    }
+    virtual ~D() {
+        delete fB;
+    }
+private:
+    void*   fVoidStar;
+    B*      fB;
+
+    typedef C INHERITED;
+};
+
+class E : public A {
+public:
+    E() {}
+    virtual void setValues(int v) {
+        for (size_t i = 0; i < SK_ARRAY_COUNT(fIntArray); ++i) {
+            fIntArray[i] = v;
+        }
+        this->INHERITED::setValues(v);
+    }
+    virtual bool checkValues(int v) {
+        bool ok = true;
+        for (size_t i = 0; ok && i < SK_ARRAY_COUNT(fIntArray); ++i) {
+            if (fIntArray[i] != v) {
+                ok = false;
+            }
+        }
+        return ok && this->INHERITED::checkValues(v);
+    }
+    virtual ~E() {}
+private:
+    int   fIntArray[20];
+
+    typedef A INHERITED;
+};
+
+A* A::Create(SkRandom* r) {
+    switch (r->nextRangeU(0, 4)) {
+        case 0:
+            return new A;
+        case 1:
+            return new B;
+        case 2:
+            return new C;
+        case 3:
+            return new D;
+        case 4:
+            return new E;
+        default:
+            // suppress warning
+            return NULL;
+    }
+}
+}
+struct Rec {
+    A* fInstance;
+    int fValue;
+};
+
+static void test_memory_pool(skiatest::Reporter* reporter) {
+    // prealloc and min alloc sizes for the pool
+    static const size_t gSizes[][2] = {
+        {0, 0},
+        {10 * sizeof(A), 20 * sizeof(A)},
+        {100 * sizeof(A), 100 * sizeof(A)},
+        {500 * sizeof(A), 500 * sizeof(A)},
+        {10000 * sizeof(A), 0},
+        {1, 100 * sizeof(A)},
+    };
+    // different percentages of creation vs deletion
+    static const float gCreateFraction[] = {1.f, .95f, 0.75f, .5f};
+    // number of create/destroys per test
+    static const int kNumIters = 20000;
+    // check that all the values stored in A objects are correct after this
+    // number of iterations
+    static const int kCheckPeriod = 500;
+
+    SkRandom r;
+    for (size_t s = 0; s < SK_ARRAY_COUNT(gSizes); ++s) {
+        A::SetAllocator(gSizes[s][0], gSizes[s][1]);
+        for (size_t c = 0; c < SK_ARRAY_COUNT(gCreateFraction); ++c) {
+            SkTDArray<Rec> instanceRecs;
+            for (int i = 0; i < kNumIters; ++i) {
+                float createOrDestroy = r.nextUScalar1();
+                if (createOrDestroy < gCreateFraction[c] ||
+                    0 == instanceRecs.count()) {
+                    Rec* rec = instanceRecs.append();
+                    rec->fInstance = A::Create(&r);
+                    rec->fValue = static_cast<int>(r.nextU());
+                    rec->fInstance->setValues(rec->fValue);
+                } else {
+                    int d = r.nextRangeU(0, instanceRecs.count() - 1);
+                    Rec& rec = instanceRecs[d];
+                    REPORTER_ASSERT(reporter, rec.fInstance->checkValues(rec.fValue));
+                    delete rec.fInstance;
+                    instanceRecs.removeShuffle(d);
+                }
+                if (0 == i % kCheckPeriod) {
+                    for (int r = 0; r < instanceRecs.count(); ++r) {
+                        Rec& rec = instanceRecs[r];
+                        REPORTER_ASSERT(reporter, rec.fInstance->checkValues(rec.fValue));
+                    }
+                }
+            }
+            for (int i = 0; i < instanceRecs.count(); ++i) {
+                Rec& rec = instanceRecs[i];
+                REPORTER_ASSERT(reporter, rec.fInstance->checkValues(rec.fValue));
+                delete rec.fInstance;
+            }
+#ifdef SK_DEBUG
+            REPORTER_ASSERT(reporter, !A::GetInstanceCount());
+#endif
+        }
+    }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("GrMemoryPool", GrMemoryPoolClass, test_memory_pool)
+