Reduce integer divides in GrAllocator

R=egdaniel@google.com

Author: bsalomon@google.com

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

1 files changed, 151 insertions, 64 deletions

diff --git a/src/gpu/GrAllocator.h b/src/gpu/GrAllocator.h
index a2ad408e07..50d9a6cdad 100644
--- a/src/gpu/GrAllocator.h
+++ b/src/gpu/GrAllocator.h
@@ -15,9 +15,7 @@
 
 class GrAllocator : SkNoncopyable {
 public:
-    ~GrAllocator() {
-        reset();
-    }
+    ~GrAllocator() { this->reset(); }
 
     /**
      * Create an allocator
@@ -28,31 +26,21 @@ public:
      *                          Must be at least itemSize*itemsPerBlock sized.
      *                          Caller is responsible for freeing this memory.
      */
-    GrAllocator(size_t itemSize, int itemsPerBlock, void* initialBlock) :
-            fItemSize(itemSize),
-            fItemsPerBlock(itemsPerBlock),
-            fOwnFirstBlock(NULL == initialBlock),
-            fCount(0) {
+    GrAllocator(size_t itemSize, int itemsPerBlock, void* initialBlock)
+        : fItemSize(itemSize)
+        , fItemsPerBlock(itemsPerBlock)
+        , fOwnFirstBlock(NULL == initialBlock)
+        , fCount(0)
+        , fInsertionIndexInBlock(0) {
         SkASSERT(itemsPerBlock > 0);
         fBlockSize = fItemSize * fItemsPerBlock;
-        fBlocks.push_back() = initialBlock;
-        SkDEBUGCODE(if (!fOwnFirstBlock) {*((char*)initialBlock+fBlockSize-1)='a';} );
-    }
-
-    /*
-     * Set first block of memory to write into.  Must be called before any other methods.
-     * This requires that you have passed NULL in the constructor.
-     *
-     * @param   initialBlock    optional memory to use for the first block.
-     *                          Must be at least itemSize*itemsPerBlock sized.
-     *                          Caller is responsible for freeing this memory.
-     */
-    void setInitialBlock(void* initialBlock) {
-        SkASSERT(0 == fCount);
-        SkASSERT(1 == fBlocks.count());
-        SkASSERT(NULL == fBlocks.back());
-        fOwnFirstBlock = false;
-        fBlocks.back() = initialBlock;
+        if (fOwnFirstBlock) {
+            // This force us to allocate a new block on push_back().
+            fInsertionIndexInBlock = fItemsPerBlock;
+        } else {
+            fBlocks.push_back() = initialBlock;
+            fInsertionIndexInBlock = 0;
+        }
     }
 
     /**
@@ -61,68 +49,113 @@ public:
      * @return pointer to the added item.
      */
     void* push_back() {
-        int indexInBlock = fCount % fItemsPerBlock;
         // we always have at least one block
-        if (0 == indexInBlock) {
-            if (0 != fCount) {
-                fBlocks.push_back() = sk_malloc_throw(fBlockSize);
-            } else if (fOwnFirstBlock) {
-                fBlocks[0] = sk_malloc_throw(fBlockSize);
-            }
+        if (fItemsPerBlock == fInsertionIndexInBlock) {
+            fBlocks.push_back() = sk_malloc_throw(fBlockSize);
+            fInsertionIndexInBlock = 0;
         }
-        void* ret = (char*)fBlocks[fCount/fItemsPerBlock] +
-                    fItemSize * indexInBlock;
+        void* ret = (char*)fBlocks.back() + fItemSize * fInsertionIndexInBlock;
         ++fCount;
+        ++fInsertionIndexInBlock;
         return ret;
     }
 
     /**
-     * removes all added items
+     * Removes all added items.
      */
     void reset() {
-        int blockCount = SkTMax((unsigned)1,
-                               GrUIDivRoundUp(fCount, fItemsPerBlock));
-        for (int i = 1; i < blockCount; ++i) {
+        int firstBlockToFree = fOwnFirstBlock ? 0 : 1;
+        for (int i = firstBlockToFree; i < fBlocks.count(); ++i) {
             sk_free(fBlocks[i]);
         }
         if (fOwnFirstBlock) {
-            sk_free(fBlocks[0]);
-            fBlocks[0] = NULL;
+            fBlocks.reset();
+            // This force us to allocate a new block on push_back().
+            fInsertionIndexInBlock = fItemsPerBlock;
+        } else {
+            fBlocks.pop_back_n(fBlocks.count() - 1);
+            fInsertionIndexInBlock = 0;
         }
-        fBlocks.pop_back_n(blockCount-1);
         fCount = 0;
     }
 
     /**
-     * count of items
+     * Returns the item count.
      */
     int count() const {
         return fCount;
     }
 
     /**
-     * is the count 0
+     * Is the count 0?
      */
-    bool empty() const { return fCount == 0; }
+    bool empty() const { return 0 == fCount; }
 
     /**
-     * access last item, only call if count() != 0
+     * Access last item, only call if count() != 0
      */
     void* back() {
         SkASSERT(fCount);
-        return (*this)[fCount-1];
+        SkASSERT(fInsertionIndexInBlock > 0);
+        return (char*)(fBlocks.back()) + (fInsertionIndexInBlock - 1) * fItemSize;
     }
 
     /**
-     * access last item, only call if count() != 0
+     * Access last item, only call if count() != 0
      */
     const void* back() const {
         SkASSERT(fCount);
-        return (*this)[fCount-1];
+        SkASSERT(fInsertionIndexInBlock > 0);
+        return (const char*)(fBlocks.back()) + (fInsertionIndexInBlock - 1) * fItemSize;
     }
 
+
+    /**
+     * Iterates through the allocator. This is faster than using operator[] when walking linearly
+     * through the allocator.
+     */
+    class Iter {
+    public:
+        /**
+         * Initializes the iterator. next() must be called before get().
+         */
+        Iter(const GrAllocator* allocator)
+            : fAllocator(allocator)
+            , fBlockIndex(-1)
+            , fIndexInBlock(allocator->fItemsPerBlock - 1)
+            , fItemIndex(-1) {}
+
+        /**
+         * Advances the iterator. Iteration is finished when next() returns false.
+         */
+        bool next() {
+            ++fIndexInBlock;
+            ++fItemIndex;
+            if (fIndexInBlock == fAllocator->fItemsPerBlock) {
+                ++fBlockIndex;
+                fIndexInBlock = 0;
+            }
+            return fItemIndex < fAllocator->fCount;
+        }
+
+        /**
+         * Gets the current iterator value. Call next() at least once before calling. Don't call
+         * after next() returns false.
+         */
+        const void* get() const {
+            SkASSERT(fItemIndex >= 0 && fItemIndex < fAllocator->fCount);
+            return (char*) fAllocator->fBlocks[fBlockIndex] + fIndexInBlock * fAllocator->fItemSize;
+        }
+
+    private:
+        const GrAllocator* fAllocator;
+        int                fBlockIndex;
+        int                fIndexInBlock;
+        int                fItemIndex;
+    };
+
     /**
-     * access item by index.
+     * Access item by index.
      */
     void* operator[] (int i) {
         SkASSERT(i >= 0 && i < fCount);
@@ -131,7 +164,7 @@ public:
     }
 
     /**
-     * access item by index.
+     * Access item by index.
      */
     const void* operator[] (int i) const {
         SkASSERT(i >= 0 && i < fCount);
@@ -139,15 +172,37 @@ public:
                fItemSize * (i % fItemsPerBlock);
     }
 
+protected:
+    /**
+     * Set first block of memory to write into.  Must be called before any other methods.
+     * This requires that you have passed NULL in the constructor.
+     *
+     * @param   initialBlock    optional memory to use for the first block.
+     *                          Must be at least itemSize*itemsPerBlock sized.
+     *                          Caller is responsible for freeing this memory.
+     */
+    void setInitialBlock(void* initialBlock) {
+        SkASSERT(0 == fCount);
+        SkASSERT(0 == fBlocks.count());
+        SkASSERT(fItemsPerBlock == fInsertionIndexInBlock);
+        fOwnFirstBlock = false;
+        fBlocks.push_back() = initialBlock;
+        fInsertionIndexInBlock = 0;
+    }
+
+    // For access to above function.
+    template <typename T> friend class GrTAllocator;
+
 private:
     static const int NUM_INIT_BLOCK_PTRS = 8;
 
-    SkSTArray<NUM_INIT_BLOCK_PTRS, void*>   fBlocks;
-    size_t                                  fBlockSize;
-    size_t                                  fItemSize;
-    int                                     fItemsPerBlock;
-    bool                                    fOwnFirstBlock;
-    int                                     fCount;
+    SkSTArray<NUM_INIT_BLOCK_PTRS, void*, true>   fBlocks;
+    size_t                                        fBlockSize;
+    size_t                                        fItemSize;
+    int                                           fItemsPerBlock;
+    bool                                          fOwnFirstBlock;
+    int                                           fCount;
+    int                                           fInsertionIndexInBlock;
 
     typedef SkNoncopyable INHERITED;
 };
@@ -185,7 +240,7 @@ public:
     }
 
     /**
-     * removes all added items
+     * Removes all added items.
      */
     void reset() {
         int c = fAllocator.count();
@@ -196,40 +251,72 @@ public:
     }
 
     /**
-     * count of items
+     * Returns the item count.
      */
     int count() const {
         return fAllocator.count();
     }
 
     /**
-     * is the count 0
+     * Is the count 0?
      */
     bool empty() const { return fAllocator.empty(); }
 
     /**
-     * access last item, only call if count() != 0
+     * Access last item, only call if count() != 0
      */
     T& back() {
         return *(T*)fAllocator.back();
     }
 
     /**
-     * access last item, only call if count() != 0
+     * Access last item, only call if count() != 0
      */
     const T& back() const {
         return *(const T*)fAllocator.back();
     }
 
     /**
-     * access item by index.
+     * Iterates through the allocator. This is faster than using operator[] when walking linearly
+     * through the allocator.
+     */
+    class Iter {
+    public:
+        /**
+         * Initializes the iterator. next() must be called before get() or ops * and ->.
+         */
+        Iter(const GrTAllocator* allocator) : fImpl(&allocator->fAllocator) {}
+
+        /**
+         * Advances the iterator. Iteration is finished when next() returns false.
+         */
+        bool next() { return fImpl.next(); }
+
+        /**
+         * Gets the current iterator value. Call next() at least once before calling. Don't call
+         * after next() returns false.
+         */
+        const T* get() const { return (const T*) fImpl.get(); }
+
+        /**
+         * Convenience operators. Same rules for calling apply as get().
+         */
+        const T& operator*() const { return *this->get(); }
+        const T* operator->() const { return this->get(); }
+
+    private:
+        GrAllocator::Iter fImpl;
+    };
+
+    /**
+     * Access item by index.
      */
     T& operator[] (int i) {
         return *(T*)(fAllocator[i]);
     }
 
     /**
-     * access item by index.
+     * Access item by index.
      */
     const T& operator[] (int i) const {
         return *(const T*)(fAllocator[i]);