protected void shouldResize() {
if (cacheRequests > getSize()) {
currentHitRatio = cacheHits / cacheRequests;
if (currentHitRatio > desiredHitRatio) {
resize();
}
}
}It is possible I am missing something here. However, there is never any check made to see if the cache is actually full before resizing. Consider this case:
1. The desired hit ratio is 0.9
2. The cache is empty, and a request is made (cacheRequests = 1, cacheHits = 0)
3. Now the requested item is added to the cache.
4. The cached item is now requested 10 times (cacheRequests = 11, cacheHits = 10)
5. The current hit ratio is now 0.909, so the cache is emptied.
Beyond this problem, there is also the fact that it is possible to get the cache fuller than the maxSize because it is never checked. Please let me know what you think. Thanks
Duncan
/* * $Header: /home/cvs/jakarta-slide/src/share/org/apache/slide/util/AbstractObjectCache.java,v 1.7 2002/04/25 21:12:26 jericho Exp $ * $Revision: 1.7 $ * $Date: 2002/04/25 21:12:26 $ * * ==================================================================== * * The Apache Software License, Version 1.1 * * Copyright (c) 1999-2002 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, if * any, must include the following acknowlegement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowlegement may appear in the software itself, * if and wherever such third-party acknowlegements normally appear. * * 4. The names "The Jakarta Project", "Slide", and "Apache Software * Foundation" must not be used to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written * permission of the Apache Group. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * * [Additional notices, if required by prior licensing conditions] * */
package org.apache.slide.util; /** * Object cache abstract implementation. * * @author <a href="mailto:[EMAIL PROTECTED]">Remy Maucherat</a> * @version $Revision: 1.7 $ $Date: 2002/04/25 21:12:26 $ */ public abstract class AbstractObjectCache implements ObjectCache { // -------------------------------------------------------------- Constants /** * Default cache size. */ protected static final int DEFAULT_SIZE = 1000; /** * The amount the cache should grow by if required. */ protected static final int DEFAULT_GROW_BY = 100; /** * Default desired hit ratio. */ protected static final double DEFAULT_HIT_RATIO = 0.8; // ----------------------------------------------------------- Constructors /** * Constructor. * <p> * Warning (blinking) : That constructor is to be used really carefully * as the cache maximum size is not limited. */ public AbstractObjectCache() { this(DEFAULT_SIZE, Integer.MAX_VALUE, DEFAULT_HIT_RATIO); } /** * Constructor. * * @param initialSize Initial size of the cache * @param maxSize Maximum size of the cache * @param desiredHitRatio Desired cache hit ratio */ public AbstractObjectCache(int initialSize, int maxSize, double desiredHitRatio) { this.currentMax = initialSize; this.initialSize = initialSize; this.maxSize = maxSize; this.desiredHitRatio = desiredHitRatio; } // ----------------------------------------------------- Instance Variables /** * The current size of the cache. */ protected int currentMax; /** * Initial cache size. */ protected int initialSize; /** * Desired hit ratio. */ protected double desiredHitRatio; /** * Maximum cache size. */ protected int maxSize; // Cache statistics /** * Number of cache requests. */ protected double cacheRequests; /** * Number of cache hits. */ protected double cacheHits; /** * Current cache hit ratio. Equals to cacheHits / cacheRequests, if, and * only if cacheRequests >= cache.size(). Otherwise, it's value is not * used. If the cache hit ratio, is inferior to the desired hit ratio, * the cache grows (unless its maximum size is already reached). */ protected double currentHitRatio; // ---------------------------------------------------- ObjectCache methods /** * Get the object associated with the key. * * @param key Object's key * @return Object null if there is no object associated with that key in * the cache, or the object value otherwise */ public abstract Object get(Object key); /** * Add an object to the cache, or overwrite its value. * * @param key Object's key * @param value Object's value */ public abstract void put(Object key, Object value); /** * Remove object associated with the given key. Doesn't do anything if the * key wasn't associated with any object. * * @param key Object's key */ public abstract void remove(Object key); /** * Clear object cache. */ public abstract void clear(); // ------------------------------------------------------ Protected Methods /** * Removes some elements from the cache. The selection of the objects to * remove, along with the number are left to the implementation. */ protected abstract void removeSomeObjects(int nCount); /** * Get cache size. * * @return int Current cache size */ protected abstract int getSize(); /** * Resize cache. */ protected abstract void resize(); /** * Make sure we are not overfilling the cache. */ protected void checkSize() { if (getSize() > currentMax) { removeSomeObjects(getSize() - currentMax); } } /** * Is the cache size too small ? */ protected void shouldResize() { if (getSize() >= currentMax) { currentHitRatio = cacheHits / cacheRequests; if (currentHitRatio < desiredHitRatio) { currentMax = Math.min(currentMax + DEFAULT_GROW_BY, maxSize); resize(); } } } }
/* * $Header: /home/cvs/jakarta-slide/src/share/org/apache/slide/util/HashMapObjectCache.java,v 1.8 2002/04/25 21:12:26 jericho Exp $ * $Revision: 1.8 $ * $Date: 2002/04/25 21:12:26 $ * * ==================================================================== * * The Apache Software License, Version 1.1 * * Copyright (c) 1999-2002 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, if * any, must include the following acknowlegement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowlegement may appear in the software itself, * if and wherever such third-party acknowlegements normally appear. * * 4. The names "The Jakarta Project", "Slide", and "Apache Software * Foundation" must not be used to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written * permission of the Apache Group. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * * [Additional notices, if required by prior licensing conditions] * */ package org.apache.slide.util; /** * Object cache implementation using Keith Visco's HashMap structure. * * @author <a href="mailto:[EMAIL PROTECTED]">Remy Maucherat</a> * @version $Revision: 1.8 $ $Date: 2002/04/25 21:12:26 $ */ public class HashMapObjectCache extends AbstractObjectCache { // ----------------------------------------------------------- Constructors /** * Constructor. * <p> * Warning (blinking) : That constructor is to be used really carefully * as the cache maximum size is not limited. */ public HashMapObjectCache() { super(); this.cache = new HashMap(this.initialSize); } /** * Constructor. * * @param initialSize Initial size of the cache * @param maxSize Maximum size of the cache * @param desiredHitRatio Desired cache hit ratio */ public HashMapObjectCache(int initialSize, int maxSize, double desiredHitRatio) { super(initialSize, maxSize, desiredHitRatio); this.cache = new HashMap(this.initialSize / 3); } // ----------------------------------------------------- Instance Variables /** * Cache structure. */ protected HashMap cache; // ---------------------------------------------------- ObjectCache methods /** * Get the object associated with the key. * * @param key Object's key * @return Object null if there is no object associated with that key in * the cache, or the object value otherwise */ public Object get(Object key) { synchronized (cache) { Object result = cache.get(key); this.cacheRequests += 1; if (result != null) { this.cacheHits += 1; } else { shouldResize(); } return result; } } /** * Add an object to the cache, or overwrite its value. * * @param key Object's key * @param value Object's value */ public void put(Object key, Object value) { synchronized (cache) { cache.put(key, value); checkSize(); } } /** * Remove object associated with the given key. Doesn't do anything if the * key wasn't associated with any object. * * @param key Object's key */ public void remove(Object key) { synchronized (cache) { cache.remove(key); } } /** * Clear object cache. */ public void clear() { synchronized (cache) { cache.clear(); } } // ------------------------------------------------------ Protected Methods /** * Removes some elements from the cache. The selection of the objects to * remove, along with the number are left to the implementation. */ protected void removeSomeObjects(int nCount) { Iterator it = cache.keys(); Object keys[] = new Object[nCount]; int nRemove = 0; //basically we grab a few elements in the cache at random and remove them. for (;nRemove < nCount && it.hasNext(); ++nRemove) { keys[nRemove] = it.next(); } for (int n = 0; n < nRemove; ++n) { cache.remove(keys[n]); } } /** * Get cache size. * * @return int Current cache size */ protected int getSize() { return cache.size(); } /** * Resize cache. */ protected void resize() { } }
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
