From 6b9ece8710604adec2805b903d977264f90087c6 Mon Sep 17 00:00:00 2001 From: Bobby Georgescu Date: Tue, 21 May 2013 12:08:06 -0700 Subject: Add comments to bitmap pools Change-Id: Ie841316629ef0737dcdd5002b3278cf0bca3a768 --- src/com/android/photos/data/GalleryBitmapPool.java | 37 ++++++++++- .../android/photos/data/SparseArrayBitmapPool.java | 74 ++++++++++++++++++++-- 2 files changed, 105 insertions(+), 6 deletions(-) (limited to 'src/com/android/photos/data') diff --git a/src/com/android/photos/data/GalleryBitmapPool.java b/src/com/android/photos/data/GalleryBitmapPool.java index a5a17ede2..7eb9794c5 100644 --- a/src/com/android/photos/data/GalleryBitmapPool.java +++ b/src/com/android/photos/data/GalleryBitmapPool.java @@ -23,9 +23,25 @@ import android.util.Pools.SimplePool; import com.android.photos.data.SparseArrayBitmapPool.Node; +/** + * Pool allowing the efficient reuse of bitmaps in order to avoid long + * garbage collection pauses. + */ public class GalleryBitmapPool { private static final int CAPACITY_BYTES = 20971520; + + // We found that Gallery uses bitmaps that are either square (for example, + // tiles of large images or square thumbnails), match one of the common + // photo aspect ratios (4x3, 3x2, or 16x9), or, less commonly, are of some + // other aspect ratio. Taking advantage of this information, we use 3 + // SparseArrayBitmapPool instances to back the GalleryBitmapPool, which affords + // O(1) lookups for square bitmaps, and average-case - but *not* asymptotically - + // O(1) lookups for common photo aspect ratios and other miscellaneous aspect + // ratios. Beware of the pathological case where there are many bitmaps added + // to the pool with different non-square aspect ratios but the same width, as + // performance will degrade and the average case lookup will approach + // O(# of different aspect ratios). private static final int POOL_INDEX_NONE = -1; private static final int POOL_INDEX_SQUARE = 0; private static final int POOL_INDEX_PHOTO = 1; @@ -84,11 +100,20 @@ public class GalleryBitmapPool { return POOL_INDEX_MISC; } + /** + * @return Capacity of the pool in bytes. + */ public synchronized int getCapacity() { return mCapacityBytes; } - public synchronized int getSize() { + /** + * @return Approximate total size in bytes of the bitmaps stored in the pool. + */ + public int getSize() { + // Note that this only returns an approximate size, since multiple threads + // might be getting and putting Bitmaps from the pool and we lock at the + // sub-pool level to avoid unnecessary blocking. int total = 0; for (SparseArrayBitmapPool p : mPools) { total += p.getSize(); @@ -96,6 +121,9 @@ public class GalleryBitmapPool { return total; } + /** + * @return Bitmap from the pool with the desired height/width or null if none available. + */ public Bitmap get(int width, int height) { SparseArrayBitmapPool pool = getPoolForDimensions(width, height); if (pool == null) { @@ -105,6 +133,10 @@ public class GalleryBitmapPool { } } + /** + * Adds the given bitmap to the pool. + * @return Whether the bitmap was added to the pool. + */ public boolean put(Bitmap b) { if (b == null || b.getConfig() != Bitmap.Config.ARGB_8888) { return false; @@ -118,6 +150,9 @@ public class GalleryBitmapPool { } } + /** + * Empty the pool, recycling all the bitmaps currently in it. + */ public void clear() { for (SparseArrayBitmapPool p : mPools) { p.clear(); diff --git a/src/com/android/photos/data/SparseArrayBitmapPool.java b/src/com/android/photos/data/SparseArrayBitmapPool.java index 1ef9e9f48..95e10267b 100644 --- a/src/com/android/photos/data/SparseArrayBitmapPool.java +++ b/src/com/android/photos/data/SparseArrayBitmapPool.java @@ -20,10 +20,15 @@ import android.graphics.Bitmap; import android.util.SparseArray; import android.util.Pools.Pool; +import android.util.Pools.SimplePool; +/** + * Bitmap pool backed by a sparse array indexing linked lists of bitmaps + * sharing the same width. Performance will degrade if using this to store + * many bitmaps with the same width but many different heights. + */ public class SparseArrayBitmapPool { - private static final int BITMAPS_TO_KEEP_AFTER_UNNEEDED_HINT = 4; private int mCapacityBytes; private SparseArray mStore = new SparseArray(); private int mSizeBytes = 0; @@ -34,53 +39,80 @@ public class SparseArrayBitmapPool { protected static class Node { Bitmap bitmap; + + // Each node is part of two doubly linked lists: + // - A pool-level list (accessed by mPoolNodesHead and mPoolNodesTail) + // that is used for FIFO eviction of nodes when the pool gets full. + // - A bucket-level list for each index of the sparse array, so that + // each index can store more than one item. Node prevInBucket; Node nextInBucket; Node nextInPool; Node prevInPool; } + /** + * @param capacityBytes Maximum capacity of the pool in bytes. + * @param nodePool Shared pool to use for recycling linked list nodes, or null. + */ public SparseArrayBitmapPool(int capacityBytes, Pool nodePool) { mCapacityBytes = capacityBytes; - mNodePool = nodePool; + if (nodePool == null) { + mNodePool = new SimplePool(32); + } else { + mNodePool = nodePool; + } } + /** + * Set the maximum capacity of the pool, and if necessary trim it down to size. + */ public synchronized void setCapacity(int capacityBytes) { mCapacityBytes = capacityBytes; + + // No-op unless current size exceeds the new capacity. freeUpCapacity(0); } private void freeUpCapacity(int bytesNeeded) { int targetSize = mCapacityBytes - bytesNeeded; + // Repeatedly remove the oldest node until we have freed up at least bytesNeeded. while (mPoolNodesTail != null && mSizeBytes > targetSize) { unlinkAndRecycleNode(mPoolNodesTail, true); } } private void unlinkAndRecycleNode(Node n, boolean recycleBitmap) { - // Remove the node from its spot in its bucket + // Unlink the node from its sparse array bucket list. if (n.prevInBucket != null) { + // This wasn't the head, update the previous node. n.prevInBucket.nextInBucket = n.nextInBucket; } else { + // This was the head of the bucket, replace it with the next node. mStore.put(n.bitmap.getWidth(), n.nextInBucket); } if (n.nextInBucket != null) { + // This wasn't the tail, update the next node. n.nextInBucket.prevInBucket = n.prevInBucket; } - // Remove the node from its spot in the list of pool nodes + // Unlink the node from the pool-wide list. if (n.prevInPool != null) { + // This wasn't the head, update the previous node. n.prevInPool.nextInPool = n.nextInPool; } else { + // This was the head of the pool-wide list, update the head pointer. mPoolNodesHead = n.nextInPool; } if (n.nextInPool != null) { + // This wasn't the tail, update the next node. n.nextInPool.prevInPool = n.prevInPool; } else { + // This was the tail, update the tail pointer. mPoolNodesTail = n.prevInPool; } - // Recycle the node + // Recycle the node. n.nextInBucket = null; n.nextInPool = null; n.prevInBucket = null; @@ -91,16 +123,29 @@ public class SparseArrayBitmapPool { mNodePool.release(n); } + /** + * @return Capacity of the pool in bytes. + */ public synchronized int getCapacity() { return mCapacityBytes; } + /** + * @return Total size in bytes of the bitmaps stored in the pool. + */ public synchronized int getSize() { return mSizeBytes; } + /** + * @return Bitmap from the pool with the desired height/width or null if none available. + */ public synchronized Bitmap get(int width, int height) { Node cur = mStore.get(width); + + // Traverse the list corresponding to the width bucket in the + // sparse array, and unlink and return the first bitmap that + // also has the correct height. while (cur != null) { if (cur.bitmap.getHeight() == height) { Bitmap b = cur.bitmap; @@ -112,28 +157,43 @@ public class SparseArrayBitmapPool { return null; } + /** + * Adds the given bitmap to the pool. + * @return Whether the bitmap was added to the pool. + */ public synchronized boolean put(Bitmap b) { if (b == null) { return false; } + + // Ensure there is enough room to contain the new bitmap. int bytes = b.getByteCount(); freeUpCapacity(bytes); + Node newNode = mNodePool.acquire(); if (newNode == null) { newNode = new Node(); } newNode.bitmap = b; + + // We append to the head, and freeUpCapacity clears from the tail, + // resulting in FIFO eviction. newNode.prevInBucket = null; newNode.prevInPool = null; newNode.nextInPool = mPoolNodesHead; mPoolNodesHead = newNode; + + // Insert the node into its appropriate bucket based on width. int key = b.getWidth(); newNode.nextInBucket = mStore.get(key); if (newNode.nextInBucket != null) { + // The bucket already had nodes, update the old head. newNode.nextInBucket.prevInBucket = newNode; } mStore.put(key, newNode); + if (newNode.nextInPool == null) { + // This is the only node in the list, update the tail pointer. mPoolNodesTail = newNode; } else { newNode.nextInPool.prevInPool = newNode; @@ -142,7 +202,11 @@ public class SparseArrayBitmapPool { return true; } + /** + * Empty the pool, recycling all the bitmaps currently in it. + */ public synchronized void clear() { + // Clearing is equivalent to ensuring all the capacity is available. freeUpCapacity(mCapacityBytes); } } -- cgit v1.2.3