UnrefedPooledCache.java revision a07e0af0f1997ce3d40df6a8a9f44cb0b2e4c07f
189daad6bae798779e57f252e9da4fe4e62337124Tim Murray/* 289daad6bae798779e57f252e9da4fe4e62337124Tim Murray * Copyright (C) 2013 The Android Open Source Project 389daad6bae798779e57f252e9da4fe4e62337124Tim Murray * 489daad6bae798779e57f252e9da4fe4e62337124Tim Murray * Licensed under the Apache License, Version 2.0 (the "License"); 589daad6bae798779e57f252e9da4fe4e62337124Tim Murray * you may not use this file except in compliance with the License. 689daad6bae798779e57f252e9da4fe4e62337124Tim Murray * You may obtain a copy of the License at 789daad6bae798779e57f252e9da4fe4e62337124Tim Murray * 889daad6bae798779e57f252e9da4fe4e62337124Tim Murray * http://www.apache.org/licenses/LICENSE-2.0 989daad6bae798779e57f252e9da4fe4e62337124Tim Murray * 1089daad6bae798779e57f252e9da4fe4e62337124Tim Murray * Unless required by applicable law or agreed to in writing, software 1189daad6bae798779e57f252e9da4fe4e62337124Tim Murray * distributed under the License is distributed on an "AS IS" BASIS, 1289daad6bae798779e57f252e9da4fe4e62337124Tim Murray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1389daad6bae798779e57f252e9da4fe4e62337124Tim Murray * See the License for the specific language governing permissions and 1489daad6bae798779e57f252e9da4fe4e62337124Tim Murray * limitations under the License. 1589daad6bae798779e57f252e9da4fe4e62337124Tim Murray */ 1689daad6bae798779e57f252e9da4fe4e62337124Tim Murray 1789daad6bae798779e57f252e9da4fe4e62337124Tim Murraypackage com.android.bitmap; 1889daad6bae798779e57f252e9da4fe4e62337124Tim Murray 1989daad6bae798779e57f252e9da4fe4e62337124Tim Murrayimport android.util.Log; 2089daad6bae798779e57f252e9da4fe4e62337124Tim Murrayimport android.util.LruCache; 2189daad6bae798779e57f252e9da4fe4e62337124Tim Murray 2289daad6bae798779e57f252e9da4fe4e62337124Tim Murrayimport com.android.bitmap.util.Trace; 2389daad6bae798779e57f252e9da4fe4e62337124Tim Murray 2489daad6bae798779e57f252e9da4fe4e62337124Tim Murrayimport java.util.LinkedHashMap; 2589daad6bae798779e57f252e9da4fe4e62337124Tim Murrayimport java.util.Map; 2689daad6bae798779e57f252e9da4fe4e62337124Tim Murrayimport java.util.concurrent.LinkedBlockingQueue; 2789daad6bae798779e57f252e9da4fe4e62337124Tim Murray 2889daad6bae798779e57f252e9da4fe4e62337124Tim Murray/** 2989daad6bae798779e57f252e9da4fe4e62337124Tim Murray * An alternative implementation of a pool+cache. This implementation only counts 3089daad6bae798779e57f252e9da4fe4e62337124Tim Murray * unreferenced objects in its size calculation. Internally, it never evicts from 3189daad6bae798779e57f252e9da4fe4e62337124Tim Murray * its cache, and instead {@link #poll()} is allowed to return unreferenced cache 3289daad6bae798779e57f252e9da4fe4e62337124Tim Murray * entries. 3389daad6bae798779e57f252e9da4fe4e62337124Tim Murray * <p> 3489daad6bae798779e57f252e9da4fe4e62337124Tim Murray * You would only use this kind of cache if your objects are interchangeable and 3589daad6bae798779e57f252e9da4fe4e62337124Tim Murray * have significant allocation cost, and if your memory footprint is somewhat 3689daad6bae798779e57f252e9da4fe4e62337124Tim Murray * flexible. 3789daad6bae798779e57f252e9da4fe4e62337124Tim Murray * <p> 3889daad6bae798779e57f252e9da4fe4e62337124Tim Murray * Because this class only counts unreferenced objects toward targetSize, 3989daad6bae798779e57f252e9da4fe4e62337124Tim Murray * it will have a total memory footprint of: 4089daad6bae798779e57f252e9da4fe4e62337124Tim Murray * <code>(targetSize) + (# of threads concurrently writing to cache) + 4189daad6bae798779e57f252e9da4fe4e62337124Tim Murray * (total size of still-referenced entries)</code> 4289daad6bae798779e57f252e9da4fe4e62337124Tim Murray * 4389daad6bae798779e57f252e9da4fe4e62337124Tim Murray */ 4489daad6bae798779e57f252e9da4fe4e62337124Tim Murraypublic class UnrefedPooledCache<K, V extends Poolable> implements PooledCache<K, V> { 4589daad6bae798779e57f252e9da4fe4e62337124Tim Murray 4689daad6bae798779e57f252e9da4fe4e62337124Tim Murray private final LinkedHashMap<K, V> mCache; 4789daad6bae798779e57f252e9da4fe4e62337124Tim Murray private final LinkedBlockingQueue<V> mPool; 4889daad6bae798779e57f252e9da4fe4e62337124Tim Murray private final int mTargetSize; 4989daad6bae798779e57f252e9da4fe4e62337124Tim Murray private final LruCache<K, V> mNonPooledCache; 5089daad6bae798779e57f252e9da4fe4e62337124Tim Murray 5189daad6bae798779e57f252e9da4fe4e62337124Tim Murray private static final boolean DEBUG = DecodeTask.DEBUG; 5289daad6bae798779e57f252e9da4fe4e62337124Tim Murray private static final String TAG = UnrefedPooledCache.class.getSimpleName(); 5389daad6bae798779e57f252e9da4fe4e62337124Tim Murray 5489daad6bae798779e57f252e9da4fe4e62337124Tim Murray /** 5589daad6bae798779e57f252e9da4fe4e62337124Tim Murray * @param targetSize not exactly a max size in practice 5689daad6bae798779e57f252e9da4fe4e62337124Tim Murray * @param nonPooledFraction the fractional portion in the range [0.0,1.0] of targetSize to 5789daad6bae798779e57f252e9da4fe4e62337124Tim Murray * dedicate to non-poolable entries 5889daad6bae798779e57f252e9da4fe4e62337124Tim Murray */ 5989daad6bae798779e57f252e9da4fe4e62337124Tim Murray public UnrefedPooledCache(int targetSize, float nonPooledFraction) { 6089daad6bae798779e57f252e9da4fe4e62337124Tim Murray mCache = new LinkedHashMap<K, V>(0, 0.75f, true); 6189daad6bae798779e57f252e9da4fe4e62337124Tim Murray mPool = new LinkedBlockingQueue<V>(); 6289daad6bae798779e57f252e9da4fe4e62337124Tim Murray final int nonPooledSize = Math.round(targetSize * nonPooledFraction); 6389daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (nonPooledSize > 0) { 6489daad6bae798779e57f252e9da4fe4e62337124Tim Murray mNonPooledCache = new NonPooledCache(nonPooledSize); 6589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } else { 6689daad6bae798779e57f252e9da4fe4e62337124Tim Murray mNonPooledCache = null; 6789daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 6889daad6bae798779e57f252e9da4fe4e62337124Tim Murray mTargetSize = targetSize - nonPooledSize; 6989daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 7089daad6bae798779e57f252e9da4fe4e62337124Tim Murray 7189daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 7289daad6bae798779e57f252e9da4fe4e62337124Tim Murray public V get(K key, boolean incrementRefCount) { 7389daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.beginSection("cache get"); 7489daad6bae798779e57f252e9da4fe4e62337124Tim Murray synchronized (mCache) { 7589daad6bae798779e57f252e9da4fe4e62337124Tim Murray V result = mCache.get(key); 7689daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (result == null && mNonPooledCache != null) { 7789daad6bae798779e57f252e9da4fe4e62337124Tim Murray result = mNonPooledCache.get(key); 7889daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 7989daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (incrementRefCount && result != null) { 8089daad6bae798779e57f252e9da4fe4e62337124Tim Murray result.acquireReference(); 8189daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 8289daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.endSection(); 8389daad6bae798779e57f252e9da4fe4e62337124Tim Murray return result; 8489daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 8589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 8689daad6bae798779e57f252e9da4fe4e62337124Tim Murray 8789daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 8889daad6bae798779e57f252e9da4fe4e62337124Tim Murray public V put(K key, V value) { 8989daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.beginSection("cache put"); 9089daad6bae798779e57f252e9da4fe4e62337124Tim Murray // Null values not supported. 9189daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (value == null) { 9289daad6bae798779e57f252e9da4fe4e62337124Tim Murray return null; 9389daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 9489daad6bae798779e57f252e9da4fe4e62337124Tim Murray synchronized (mCache) { 9589daad6bae798779e57f252e9da4fe4e62337124Tim Murray final V prev; 9689daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (value.isEligibleForPooling()) { 9789daad6bae798779e57f252e9da4fe4e62337124Tim Murray prev = mCache.put(key, value); 9889daad6bae798779e57f252e9da4fe4e62337124Tim Murray } else if (mNonPooledCache != null) { 9989daad6bae798779e57f252e9da4fe4e62337124Tim Murray prev = mNonPooledCache.put(key, value); 10089daad6bae798779e57f252e9da4fe4e62337124Tim Murray } else { 10189daad6bae798779e57f252e9da4fe4e62337124Tim Murray prev = null; 10289daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 10389daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.endSection(); 10489daad6bae798779e57f252e9da4fe4e62337124Tim Murray return prev; 10589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 10689daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 10789daad6bae798779e57f252e9da4fe4e62337124Tim Murray 10889daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 10989daad6bae798779e57f252e9da4fe4e62337124Tim Murray public void offer(V value) { 11089daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.beginSection("pool offer"); 11189daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (value.getRefCount() != 0 || !value.isEligibleForPooling()) { 11289daad6bae798779e57f252e9da4fe4e62337124Tim Murray throw new IllegalArgumentException("unexpected offer of an invalid object: " + value); 11389daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 11489daad6bae798779e57f252e9da4fe4e62337124Tim Murray mPool.offer(value); 11589daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.endSection(); 11689daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 11789daad6bae798779e57f252e9da4fe4e62337124Tim Murray 11889daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 11989daad6bae798779e57f252e9da4fe4e62337124Tim Murray public V poll() { 12089daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.beginSection("pool poll"); 12189daad6bae798779e57f252e9da4fe4e62337124Tim Murray final V pooled = mPool.poll(); 12289daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (pooled != null) { 12389daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.endSection(); 12489daad6bae798779e57f252e9da4fe4e62337124Tim Murray return pooled; 12589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 12689daad6bae798779e57f252e9da4fe4e62337124Tim Murray 12789daad6bae798779e57f252e9da4fe4e62337124Tim Murray synchronized (mCache) { 12889daad6bae798779e57f252e9da4fe4e62337124Tim Murray int unrefSize = 0; 12989daad6bae798779e57f252e9da4fe4e62337124Tim Murray Map.Entry<K, V> eldestUnref = null; 13089daad6bae798779e57f252e9da4fe4e62337124Tim Murray for (Map.Entry<K, V> entry : mCache.entrySet()) { 13189daad6bae798779e57f252e9da4fe4e62337124Tim Murray final V value = entry.getValue(); 13289daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (value.getRefCount() > 0 || !value.isEligibleForPooling()) { 13389daad6bae798779e57f252e9da4fe4e62337124Tim Murray continue; 13489daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 13589daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (eldestUnref == null) { 13689daad6bae798779e57f252e9da4fe4e62337124Tim Murray eldestUnref = entry; 13789daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 13889daad6bae798779e57f252e9da4fe4e62337124Tim Murray unrefSize += sizeOf(value); 13989daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (unrefSize > mTargetSize) { 14089daad6bae798779e57f252e9da4fe4e62337124Tim Murray break; 14189daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 14289daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 14389daad6bae798779e57f252e9da4fe4e62337124Tim Murray // only return a scavenged cache entry if the cache has enough 14489daad6bae798779e57f252e9da4fe4e62337124Tim Murray // eligible (unreferenced) items 14589daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (unrefSize <= mTargetSize) { 14689daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (DEBUG) { 14789daad6bae798779e57f252e9da4fe4e62337124Tim Murray Log.e(TAG, "POOL SCAVENGE FAILED, cache not fully warm yet. szDelta=" 14889daad6bae798779e57f252e9da4fe4e62337124Tim Murray + (mTargetSize-unrefSize)); 14989daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 15089daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.endSection(); 15189daad6bae798779e57f252e9da4fe4e62337124Tim Murray return null; 15289daad6bae798779e57f252e9da4fe4e62337124Tim Murray } else { 15389daad6bae798779e57f252e9da4fe4e62337124Tim Murray mCache.remove(eldestUnref.getKey()); 15489daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (DEBUG) { 15589daad6bae798779e57f252e9da4fe4e62337124Tim Murray Log.e(TAG, "POOL SCAVENGE SUCCESS, oldKey=" + eldestUnref.getKey()); 15689daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 15789daad6bae798779e57f252e9da4fe4e62337124Tim Murray Trace.endSection(); 15889daad6bae798779e57f252e9da4fe4e62337124Tim Murray return eldestUnref.getValue(); 15989daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 16089daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 16189daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 16289daad6bae798779e57f252e9da4fe4e62337124Tim Murray 16389daad6bae798779e57f252e9da4fe4e62337124Tim Murray protected int sizeOf(V value) { 16489daad6bae798779e57f252e9da4fe4e62337124Tim Murray return 1; 16589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 16689daad6bae798779e57f252e9da4fe4e62337124Tim Murray 16789daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 16889daad6bae798779e57f252e9da4fe4e62337124Tim Murray public String toDebugString() { 16989daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (DEBUG) { 17089daad6bae798779e57f252e9da4fe4e62337124Tim Murray final StringBuilder sb = new StringBuilder("["); 17189daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(super.toString()); 17289daad6bae798779e57f252e9da4fe4e62337124Tim Murray int size = 0; 17389daad6bae798779e57f252e9da4fe4e62337124Tim Murray synchronized (mCache) { 17489daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(" poolCount="); 17589daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(mPool.size()); 17689daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(" cacheSize="); 17789daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(mCache.size()); 17889daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (mNonPooledCache != null) { 17989daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(" nonPooledCacheSize="); 18089daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(mNonPooledCache.size()); 18189daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 18289daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n---------------------"); 18389daad6bae798779e57f252e9da4fe4e62337124Tim Murray for (V val : mPool) { 18489daad6bae798779e57f252e9da4fe4e62337124Tim Murray size += sizeOf(val); 18589daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n\tpool item: "); 18689daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(val); 18789daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 18889daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n---------------------"); 18989daad6bae798779e57f252e9da4fe4e62337124Tim Murray for (Map.Entry<K, V> item : mCache.entrySet()) { 19089daad6bae798779e57f252e9da4fe4e62337124Tim Murray final V val = item.getValue(); 19189daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n\tcache key="); 19289daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(item.getKey()); 19389daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(" val="); 19489daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(val); 19589daad6bae798779e57f252e9da4fe4e62337124Tim Murray size += sizeOf(val); 19689daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 19789daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n---------------------"); 19889daad6bae798779e57f252e9da4fe4e62337124Tim Murray if (mNonPooledCache != null) { 19989daad6bae798779e57f252e9da4fe4e62337124Tim Murray for (Map.Entry<K, V> item : mNonPooledCache.snapshot().entrySet()) { 20089daad6bae798779e57f252e9da4fe4e62337124Tim Murray final V val = item.getValue(); 20189daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n\tnon-pooled cache key="); 20289daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(item.getKey()); 20389daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(" val="); 20489daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append(val); 20589daad6bae798779e57f252e9da4fe4e62337124Tim Murray size += sizeOf(val); 20689daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 20789daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\n---------------------"); 20889daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 20989daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("\nTOTAL SIZE=" + size); 21089daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 21189daad6bae798779e57f252e9da4fe4e62337124Tim Murray sb.append("]"); 21289daad6bae798779e57f252e9da4fe4e62337124Tim Murray return sb.toString(); 21389daad6bae798779e57f252e9da4fe4e62337124Tim Murray } else { 21489daad6bae798779e57f252e9da4fe4e62337124Tim Murray return null; 21589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 21689daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 21789daad6bae798779e57f252e9da4fe4e62337124Tim Murray 21889daad6bae798779e57f252e9da4fe4e62337124Tim Murray private class NonPooledCache extends LruCache<K, V> { 21989daad6bae798779e57f252e9da4fe4e62337124Tim Murray 22089daad6bae798779e57f252e9da4fe4e62337124Tim Murray public NonPooledCache(int maxSize) { 22189daad6bae798779e57f252e9da4fe4e62337124Tim Murray super(maxSize); 22289daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 22389daad6bae798779e57f252e9da4fe4e62337124Tim Murray 22489daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 22589daad6bae798779e57f252e9da4fe4e62337124Tim Murray protected int sizeOf(K key, V value) { 22689daad6bae798779e57f252e9da4fe4e62337124Tim Murray return UnrefedPooledCache.this.sizeOf(value); 22789daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 22889daad6bae798779e57f252e9da4fe4e62337124Tim Murray 22989daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 23089daad6bae798779e57f252e9da4fe4e62337124Tim Murray 23189daad6bae798779e57f252e9da4fe4e62337124Tim Murray @Override 23289daad6bae798779e57f252e9da4fe4e62337124Tim Murray public void clear() { 23389daad6bae798779e57f252e9da4fe4e62337124Tim Murray mCache.clear(); 23489daad6bae798779e57f252e9da4fe4e62337124Tim Murray mPool.clear(); 23589daad6bae798779e57f252e9da4fe4e62337124Tim Murray } 23689daad6bae798779e57f252e9da4fe4e62337124Tim Murray} 23789daad6bae798779e57f252e9da4fe4e62337124Tim Murray