You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@myfaces.apache.org by lu...@apache.org on 2012/03/03 16:53:12 UTC
svn commit: r1296648 - in /myfaces/core/trunk:
impl/src/main/java/org/apache/myfaces/lifecycle/
shared/src/main/java/org/apache/myfaces/shared/application/
shared/src/main/java/org/apache/myfaces/shared/resource/
shared/src/main/java/org/apache/myfaces...
Author: lu4242
Date: Sat Mar 3 15:53:12 2012
New Revision: 1296648
URL: http://svn.apache.org/viewvc?rev=1296648&view=rev
Log:
MYFACES-3484 [perf] Use solr ConcurrentLRUCache instead Collections.synchronizedMap
Added:
myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java (with props)
myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java (with props)
Modified:
myfaces/core/trunk/impl/src/main/java/org/apache/myfaces/lifecycle/DefaultRestoreViewSupport.java
myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/application/DefaultViewHandlerSupport.java
myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/resource/ResourceHandlerCache.java
Modified: myfaces/core/trunk/impl/src/main/java/org/apache/myfaces/lifecycle/DefaultRestoreViewSupport.java
URL: http://svn.apache.org/viewvc/myfaces/core/trunk/impl/src/main/java/org/apache/myfaces/lifecycle/DefaultRestoreViewSupport.java?rev=1296648&r1=1296647&r2=1296648&view=diff
==============================================================================
--- myfaces/core/trunk/impl/src/main/java/org/apache/myfaces/lifecycle/DefaultRestoreViewSupport.java (original)
+++ myfaces/core/trunk/impl/src/main/java/org/apache/myfaces/lifecycle/DefaultRestoreViewSupport.java Sat Mar 3 15:53:12 2012
@@ -19,9 +19,7 @@
package org.apache.myfaces.lifecycle;
import java.net.MalformedURLException;
-import java.util.Collections;
import java.util.EnumSet;
-import java.util.LinkedHashMap;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;
@@ -33,6 +31,7 @@ import javax.faces.application.ViewHandl
import javax.faces.component.UIComponent;
import javax.faces.component.visit.VisitCallback;
import javax.faces.component.visit.VisitContext;
+import javax.faces.component.visit.VisitContextFactory;
import javax.faces.component.visit.VisitHint;
import javax.faces.component.visit.VisitResult;
import javax.faces.context.ExternalContext;
@@ -45,6 +44,7 @@ import org.apache.myfaces.buildtools.mav
import org.apache.myfaces.shared.application.FacesServletMapping;
import org.apache.myfaces.shared.application.InvalidViewIdException;
import org.apache.myfaces.shared.util.Assert;
+import org.apache.myfaces.shared.util.ConcurrentLRUCache;
import org.apache.myfaces.shared.util.ExternalContextUtils;
/**
@@ -83,7 +83,7 @@ public class DefaultRestoreViewSupport i
private static final String SKIP_ITERATION_HINT = "javax.faces.visit.SKIP_ITERATION";
- private Map<String, Boolean> _checkedViewIdMap = null;
+ private volatile ConcurrentLRUCache<String, Boolean> _checkedViewIdMap = null;
private Boolean _checkedViewIdCacheEnabled = null;
private RenderKitFactory _renderKitFactory = null;
@@ -554,12 +554,12 @@ public class DefaultRestoreViewSupport i
}
}
- private Map<String, Boolean> getCheckedViewIDMap(FacesContext context)
+ private ConcurrentLRUCache<String, Boolean> getCheckedViewIDMap(FacesContext context)
{
if (_checkedViewIdMap == null)
{
- _checkedViewIdMap = Collections.synchronizedMap(
- new _CheckedViewIDMap<String, Boolean>(getViewIDCacheMaxSize(context)));
+ int maxSize = getViewIDCacheMaxSize(context);
+ _checkedViewIdMap = new ConcurrentLRUCache<String, Boolean>((maxSize * 4 + 3) / 3, maxSize);
}
return _checkedViewIdMap;
}
@@ -600,22 +600,4 @@ public class DefaultRestoreViewSupport i
: Integer.parseInt(configParam);
}
- private class _CheckedViewIDMap<K, V> extends LinkedHashMap<K, V>
- {
- private static final long serialVersionUID = 1L;
- private int maxCapacity;
-
- public _CheckedViewIDMap(int cacheSize)
- {
- // create map at max capacity and 1.1 load factor to avoid rehashing
- super(cacheSize + 1, 1.1f, true);
- maxCapacity = cacheSize;
- }
-
- @Override
- protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
- {
- return size() > maxCapacity;
- }
- }
}
Modified: myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/application/DefaultViewHandlerSupport.java
URL: http://svn.apache.org/viewvc/myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/application/DefaultViewHandlerSupport.java?rev=1296648&r1=1296647&r2=1296648&view=diff
==============================================================================
--- myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/application/DefaultViewHandlerSupport.java (original)
+++ myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/application/DefaultViewHandlerSupport.java Sat Mar 3 15:53:12 2012
@@ -19,8 +19,6 @@
package org.apache.myfaces.shared.application;
import java.net.MalformedURLException;
-import java.util.Collections;
-import java.util.LinkedHashMap;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;
@@ -33,6 +31,7 @@ import javax.faces.view.ViewDeclarationL
import org.apache.myfaces.buildtools.maven2.plugin.builder.annotation.JSFWebConfigParam;
import org.apache.myfaces.shared.renderkit.html.util.SharedStringBuilder;
+import org.apache.myfaces.shared.util.ConcurrentLRUCache;
import org.apache.myfaces.shared.util.ExternalContextUtils;
import org.apache.myfaces.shared.util.StringUtils;
import org.apache.myfaces.shared.util.WebConfigParamUtils;
@@ -78,7 +77,7 @@ public class DefaultViewHandlerSupport i
private static final String VIEW_HANDLER_SUPPORT_SB = "oam.viewhandler.SUPPORT_SB";
- private Map<String, Boolean> _checkedViewIdMap = null;
+ private volatile ConcurrentLRUCache<String, Boolean> _checkedViewIdMap = null;
private Boolean _checkedViewIdCacheEnabled = null;
public String calculateViewId(FacesContext context, String viewId)
@@ -569,12 +568,12 @@ public class DefaultViewHandlerSupport i
return false;
}
- private Map<String, Boolean> getCheckedViewIDMap(FacesContext context)
+ private ConcurrentLRUCache<String, Boolean> getCheckedViewIDMap(FacesContext context)
{
if (_checkedViewIdMap == null)
{
- _checkedViewIdMap = Collections.synchronizedMap(
- new _CheckedViewIDMap<String, Boolean>(getViewIDCacheMaxSize(context)));
+ int maxSize = getViewIDCacheMaxSize(context);
+ _checkedViewIdMap = new ConcurrentLRUCache<String, Boolean>((maxSize * 4 + 3) / 3, maxSize);
}
return _checkedViewIdMap;
}
@@ -612,23 +611,4 @@ public class DefaultViewHandlerSupport i
return WebConfigParamUtils.getIntegerInitParameter(externalContext,
CHECKED_VIEWID_CACHE_SIZE_ATTRIBUTE, CHECKED_VIEWID_CACHE_DEFAULT_SIZE);
}
-
- private class _CheckedViewIDMap<K, V> extends LinkedHashMap<K, V>
- {
- private static final long serialVersionUID = 1L;
- private int maxCapacity;
-
- public _CheckedViewIDMap(int cacheSize)
- {
- // create map at max capacity and 1.1 load factor to avoid rehashing
- super(cacheSize + 1, 1.1f, true);
- maxCapacity = cacheSize;
- }
-
- @Override
- protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
- {
- return size() > maxCapacity;
- }
- }
}
Modified: myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/resource/ResourceHandlerCache.java
URL: http://svn.apache.org/viewvc/myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/resource/ResourceHandlerCache.java?rev=1296648&r1=1296647&r2=1296648&view=diff
==============================================================================
--- myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/resource/ResourceHandlerCache.java (original)
+++ myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/resource/ResourceHandlerCache.java Sat Mar 3 15:53:12 2012
@@ -18,17 +18,16 @@
*/
package org.apache.myfaces.shared.resource;
-import org.apache.myfaces.buildtools.maven2.plugin.builder.annotation.JSFWebConfigParam;
-import org.apache.myfaces.shared.util.WebConfigParamUtils;
+import java.util.logging.Level;
+import java.util.logging.Logger;
import javax.faces.application.ProjectStage;
import javax.faces.context.ExternalContext;
import javax.faces.context.FacesContext;
-import java.util.Collections;
-import java.util.LinkedHashMap;
-import java.util.Map;
-import java.util.logging.Level;
-import java.util.logging.Logger;
+
+import org.apache.myfaces.buildtools.maven2.plugin.builder.annotation.JSFWebConfigParam;
+import org.apache.myfaces.shared.util.ConcurrentLRUCache;
+import org.apache.myfaces.shared.util.WebConfigParamUtils;
public class ResourceHandlerCache
{
@@ -36,7 +35,7 @@ public class ResourceHandlerCache
.getLogger(ResourceHandlerCache.class.getName());
private Boolean _resourceCacheEnabled = null;
- private Map<ResourceKey, ResourceValue> _resourceCacheMap = null;
+ private volatile ConcurrentLRUCache<ResourceKey, ResourceValue> _resourceCacheMap = null;
/**
* Controls the size of the cache used to check if a resource exists or not.
@@ -87,7 +86,7 @@ public class ResourceHandlerCache
}
ResourceKey key = new ResourceKey(resourceName, libraryName, contentType, localePrefix);
- return _resourceCacheMap.containsKey(key);
+ return _resourceCacheMap.get(key) != null;
}
public void putResource(String resourceName, String libraryName,
@@ -110,9 +109,9 @@ public class ResourceHandlerCache
{
log.log(Level.FINE, "Initializing resource cache map");
}
- _resourceCacheMap = Collections
- .synchronizedMap(new _ResourceMap<ResourceKey, ResourceValue>(
- getMaxSize()));
+ int maxSize = getMaxSize();
+ _resourceCacheMap = new ConcurrentLRUCache<ResourceKey, ResourceValue>(
+ (maxSize * 4 + 3) / 3, maxSize);
}
_resourceCacheMap.put(new ResourceKey(resourceName, libraryName,
@@ -247,22 +246,4 @@ public class ResourceHandlerCache
}
}
- private static class _ResourceMap<K, V> extends LinkedHashMap<K, V>
- {
- private static final long serialVersionUID = 1L;
- private int maxCapacity;
-
- public _ResourceMap(int cacheSize)
- {
- // create map at max capacity and 1.1 load factor to avoid rehashing
- super(cacheSize + 1, 1.1f, true);
- maxCapacity = cacheSize;
- }
-
- @Override
- protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
- {
- return size() > maxCapacity;
- }
- }
}
Added: myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java
URL: http://svn.apache.org/viewvc/myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java?rev=1296648&view=auto
==============================================================================
--- myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java (added)
+++ myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java Sat Mar 3 15:53:12 2012
@@ -0,0 +1,829 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.myfaces.shared.util;
+
+import java.lang.ref.WeakReference;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.TreeSet;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * A LRU cache implementation based upon ConcurrentHashMap and other techniques to reduce
+ * contention and synchronization overhead to utilize multiple CPU cores more effectively.
+ * <p/>
+ * Note that the implementation does not follow a true LRU (least-recently-used) eviction
+ * strategy. Instead it strives to remove least recently used items but when the initial
+ * cleanup does not remove enough items to reach the 'acceptableWaterMark' limit, it can
+ * remove more items forcefully regardless of access order.
+ *
+ *
+ * @since solr 1.4
+ * @see org.apache.solr.util.ConcurrentLRUCache
+ */
+public class ConcurrentLRUCache<K, V>
+{
+ //private static Logger log = Logger.getLogger(ConcurrentLRUCache.class
+ // .getName());
+
+ private final ConcurrentHashMap<Object, CacheEntry<K, V>> map;
+ private final int upperWaterMark;
+ private final int lowerWaterMark;
+ private final ReentrantLock markAndSweepLock = new ReentrantLock(true);
+ private boolean isCleaning = false; // not volatile... piggybacked on other volatile vars
+ private final boolean newThreadForCleanup;
+ private volatile boolean islive = true;
+ private final Stats stats = new Stats();
+ private final int acceptableWaterMark;
+ private long oldestEntry = 0; // not volatile, only accessed in the cleaning method
+ private final EvictionListener<K, V> evictionListener;
+ private CleanupThread cleanupThread;
+
+ public ConcurrentLRUCache(int upperWaterMark, final int lowerWaterMark,
+ int acceptableWatermark, int initialSize, boolean runCleanupThread,
+ boolean runNewThreadForCleanup,
+ EvictionListener<K, V> evictionListener)
+ {
+ if (upperWaterMark < 1)
+ {
+ throw new IllegalArgumentException("upperWaterMark must be > 0");
+ }
+ if (lowerWaterMark >= upperWaterMark)
+ {
+ throw new IllegalArgumentException(
+ "lowerWaterMark must be < upperWaterMark");
+ }
+ map = new ConcurrentHashMap<Object, CacheEntry<K, V>>(initialSize);
+ newThreadForCleanup = runNewThreadForCleanup;
+ this.upperWaterMark = upperWaterMark;
+ this.lowerWaterMark = lowerWaterMark;
+ this.acceptableWaterMark = acceptableWatermark;
+ this.evictionListener = evictionListener;
+ if (runCleanupThread)
+ {
+ cleanupThread = new CleanupThread(this);
+ cleanupThread.start();
+ }
+ }
+
+ public ConcurrentLRUCache(int size, int lowerWatermark)
+ {
+ this(size, lowerWatermark, (int) Math
+ .floor((lowerWatermark + size) / 2), (int) Math
+ .ceil(0.75 * size), false, false, null);
+ }
+
+ public void setAlive(boolean live)
+ {
+ islive = live;
+ }
+
+ public V get(K key)
+ {
+ CacheEntry<K, V> e = map.get(key);
+ if (e == null)
+ {
+ if (islive)
+ {
+ stats.missCounter.incrementAndGet();
+ }
+ return null;
+ }
+ if (islive)
+ {
+ e.lastAccessed = stats.accessCounter.incrementAndGet();
+ }
+ return e.value;
+ }
+
+ public V remove(K key)
+ {
+ CacheEntry<K, V> cacheEntry = map.remove(key);
+ if (cacheEntry != null)
+ {
+ stats.size.decrementAndGet();
+ return cacheEntry.value;
+ }
+ return null;
+ }
+
+ public V put(K key, V val)
+ {
+ if (val == null)
+ {
+ return null;
+ }
+ CacheEntry<K, V> e = new CacheEntry<K, V>(key, val,
+ stats.accessCounter.incrementAndGet());
+ CacheEntry<K, V> oldCacheEntry = map.put(key, e);
+ int currentSize;
+ if (oldCacheEntry == null)
+ {
+ currentSize = stats.size.incrementAndGet();
+ }
+ else
+ {
+ currentSize = stats.size.get();
+ }
+ if (islive)
+ {
+ stats.putCounter.incrementAndGet();
+ }
+ else
+ {
+ stats.nonLivePutCounter.incrementAndGet();
+ }
+
+ // Check if we need to clear out old entries from the cache.
+ // isCleaning variable is checked instead of markAndSweepLock.isLocked()
+ // for performance because every put invokation will check until
+ // the size is back to an acceptable level.
+ //
+ // There is a race between the check and the call to markAndSweep, but
+ // it's unimportant because markAndSweep actually aquires the lock or returns if it can't.
+ //
+ // Thread safety note: isCleaning read is piggybacked (comes after) other volatile reads
+ // in this method.
+ if (currentSize > upperWaterMark && !isCleaning)
+ {
+ if (newThreadForCleanup)
+ {
+ new Thread()
+ {
+ @Override
+ public void run()
+ {
+ markAndSweep();
+ }
+ }.start();
+ }
+ else if (cleanupThread != null)
+ {
+ cleanupThread.wakeThread();
+ }
+ else
+ {
+ markAndSweep();
+ }
+ }
+ return oldCacheEntry == null ? null : oldCacheEntry.value;
+ }
+
+ /**
+ * Removes items from the cache to bring the size down
+ * to an acceptable value ('acceptableWaterMark').
+ * <p/>
+ * It is done in two stages. In the first stage, least recently used items are evicted.
+ * If, after the first stage, the cache size is still greater than 'acceptableSize'
+ * config parameter, the second stage takes over.
+ * <p/>
+ * The second stage is more intensive and tries to bring down the cache size
+ * to the 'lowerWaterMark' config parameter.
+ */
+ private void markAndSweep()
+ {
+ // if we want to keep at least 1000 entries, then timestamps of
+ // current through current-1000 are guaranteed not to be the oldest (but that does
+ // not mean there are 1000 entries in that group... it's acutally anywhere between
+ // 1 and 1000).
+ // Also, if we want to remove 500 entries, then
+ // oldestEntry through oldestEntry+500 are guaranteed to be
+ // removed (however many there are there).
+
+ if (!markAndSweepLock.tryLock())
+ {
+ return;
+ }
+ try
+ {
+ long oldestEntry = this.oldestEntry;
+ isCleaning = true;
+ this.oldestEntry = oldestEntry; // volatile write to make isCleaning visible
+
+ long timeCurrent = stats.accessCounter.get();
+ int sz = stats.size.get();
+
+ int numRemoved = 0;
+ int numKept = 0;
+ long newestEntry = timeCurrent;
+ long newNewestEntry = -1;
+ long newOldestEntry = Long.MAX_VALUE;
+
+ int wantToKeep = lowerWaterMark;
+ int wantToRemove = sz - lowerWaterMark;
+
+ @SuppressWarnings("unchecked")
+ // generic array's are anoying
+ CacheEntry<K, V>[] eset = new CacheEntry[sz];
+ int eSize = 0;
+
+ // System.out.println("newestEntry="+newestEntry + " oldestEntry="+oldestEntry);
+ // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
+ // " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
+
+ for (CacheEntry<K, V> ce : map.values())
+ {
+ // set lastAccessedCopy to avoid more volatile reads
+ ce.lastAccessedCopy = ce.lastAccessed;
+ long thisEntry = ce.lastAccessedCopy;
+
+ // since the wantToKeep group is likely to be bigger than wantToRemove, check it first
+ if (thisEntry > newestEntry - wantToKeep)
+ {
+ // this entry is guaranteed not to be in the bottom
+ // group, so do nothing.
+ numKept++;
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+ }
+ else if (thisEntry < oldestEntry + wantToRemove)
+ { // entry in bottom group?
+ // this entry is guaranteed to be in the bottom group
+ // so immediately remove it from the map.
+ evictEntry(ce.key);
+ numRemoved++;
+ }
+ else
+ {
+ // This entry *could* be in the bottom group.
+ // Collect these entries to avoid another full pass... this is wasted
+ // effort if enough entries are normally removed in this first pass.
+ // An alternate impl could make a full second pass.
+ if (eSize < eset.length - 1)
+ {
+ eset[eSize++] = ce;
+ newNewestEntry = Math.max(thisEntry, newNewestEntry);
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+ }
+ }
+ }
+
+ // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
+ // " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
+ // TODO: allow this to be customized in the constructor?
+ int numPasses = 1; // maximum number of linear passes over the data
+
+ // if we didn't remove enough entries, then make more passes
+ // over the values we collected, with updated min and max values.
+ while (sz - numRemoved > acceptableWaterMark && --numPasses >= 0)
+ {
+
+ oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
+ : newOldestEntry;
+ newOldestEntry = Long.MAX_VALUE;
+ newestEntry = newNewestEntry;
+ newNewestEntry = -1;
+ wantToKeep = lowerWaterMark - numKept;
+ wantToRemove = sz - lowerWaterMark - numRemoved;
+
+ // iterate backward to make it easy to remove items.
+ for (int i = eSize - 1; i >= 0; i--)
+ {
+ CacheEntry<K, V> ce = eset[i];
+ long thisEntry = ce.lastAccessedCopy;
+
+ if (thisEntry > newestEntry - wantToKeep)
+ {
+ // this entry is guaranteed not to be in the bottom
+ // group, so do nothing but remove it from the eset.
+ numKept++;
+ // remove the entry by moving the last element to it's position
+ eset[i] = eset[eSize - 1];
+ eSize--;
+
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+
+ }
+ else if (thisEntry < oldestEntry + wantToRemove)
+ { // entry in bottom group?
+
+ // this entry is guaranteed to be in the bottom group
+ // so immediately remove it from the map.
+ evictEntry(ce.key);
+ numRemoved++;
+
+ // remove the entry by moving the last element to it's position
+ eset[i] = eset[eSize - 1];
+ eSize--;
+ }
+ else
+ {
+ // This entry *could* be in the bottom group, so keep it in the eset,
+ // and update the stats.
+ newNewestEntry = Math.max(thisEntry, newNewestEntry);
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+ }
+ }
+ // System.out.println("items removed:" + numRemoved + " numKept=" +
+ // numKept + " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
+ }
+
+ // if we still didn't remove enough entries, then make another pass while
+ // inserting into a priority queue
+ if (sz - numRemoved > acceptableWaterMark)
+ {
+
+ oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
+ : newOldestEntry;
+ newOldestEntry = Long.MAX_VALUE;
+ newestEntry = newNewestEntry;
+ newNewestEntry = -1;
+ wantToKeep = lowerWaterMark - numKept;
+ wantToRemove = sz - lowerWaterMark - numRemoved;
+
+ PQueue<K, V> queue = new PQueue<K, V>(wantToRemove);
+
+ for (int i = eSize - 1; i >= 0; i--)
+ {
+ CacheEntry<K, V> ce = eset[i];
+ long thisEntry = ce.lastAccessedCopy;
+
+ if (thisEntry > newestEntry - wantToKeep)
+ {
+ // this entry is guaranteed not to be in the bottom
+ // group, so do nothing but remove it from the eset.
+ numKept++;
+ // removal not necessary on last pass.
+ // eset[i] = eset[eSize-1];
+ // eSize--;
+
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+
+ }
+ else if (thisEntry < oldestEntry + wantToRemove)
+ { // entry in bottom group?
+ // this entry is guaranteed to be in the bottom group
+ // so immediately remove it.
+ evictEntry(ce.key);
+ numRemoved++;
+
+ // removal not necessary on last pass.
+ // eset[i] = eset[eSize-1];
+ // eSize--;
+ }
+ else
+ {
+ // This entry *could* be in the bottom group.
+ // add it to the priority queue
+
+ // everything in the priority queue will be removed, so keep track of
+ // the lowest value that ever comes back out of the queue.
+
+ // first reduce the size of the priority queue to account for
+ // the number of items we have already removed while executing
+ // this loop so far.
+ queue.myMaxSize = sz - lowerWaterMark - numRemoved;
+ while (queue.size() > queue.myMaxSize
+ && queue.size() > 0)
+ {
+ CacheEntry otherEntry = (CacheEntry) queue.pop();
+ newOldestEntry = Math
+ .min(otherEntry.lastAccessedCopy,
+ newOldestEntry);
+ }
+ if (queue.myMaxSize <= 0)
+ {
+ break;
+ }
+
+ Object o = queue.myInsertWithOverflow(ce);
+ if (o != null)
+ {
+ newOldestEntry = Math.min(
+ ((CacheEntry) o).lastAccessedCopy,
+ newOldestEntry);
+ }
+ }
+ }
+
+ // Now delete everything in the priority queue.
+ // avoid using pop() since order doesn't matter anymore
+ for (CacheEntry<K, V> ce : queue.getValues())
+ {
+ if (ce == null)
+ {
+ continue;
+ }
+ evictEntry(ce.key);
+ numRemoved++;
+ }
+
+ // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
+ // " initialQueueSize="+ wantToRemove + " finalQueueSize=" +
+ // queue.size() + " sz-numRemoved=" + (sz-numRemoved));
+ }
+
+ oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
+ : newOldestEntry;
+ this.oldestEntry = oldestEntry;
+ }
+ finally
+ {
+ isCleaning = false; // set before markAndSweep.unlock() for visibility
+ markAndSweepLock.unlock();
+ }
+ }
+
+ private static class PQueue<K, V> extends PriorityQueue<CacheEntry<K, V>>
+ {
+ int myMaxSize;
+ final Object[] heap;
+
+ PQueue(int maxSz)
+ {
+ super(maxSz);
+ heap = getHeapArray();
+ myMaxSize = maxSz;
+ }
+
+ @SuppressWarnings("unchecked")
+ Iterable<CacheEntry<K, V>> getValues()
+ {
+ return (Iterable) Collections.unmodifiableCollection(Arrays
+ .asList(heap));
+ }
+
+ @Override
+ protected boolean lessThan(CacheEntry a, CacheEntry b)
+ {
+ // reverse the parameter order so that the queue keeps the oldest items
+ return b.lastAccessedCopy < a.lastAccessedCopy;
+ }
+
+ // necessary because maxSize is private in base class
+ @SuppressWarnings("unchecked")
+ public CacheEntry<K, V> myInsertWithOverflow(CacheEntry<K, V> element)
+ {
+ if (size() < myMaxSize)
+ {
+ add(element);
+ return null;
+ }
+ else if (size() > 0
+ && !lessThan(element, (CacheEntry<K, V>) heap[1]))
+ {
+ CacheEntry<K, V> ret = (CacheEntry<K, V>) heap[1];
+ heap[1] = element;
+ updateTop();
+ return ret;
+ }
+ else
+ {
+ return element;
+ }
+ }
+ }
+
+ private void evictEntry(K key)
+ {
+ CacheEntry<K, V> o = map.remove(key);
+ if (o == null)
+ {
+ return;
+ }
+ stats.size.decrementAndGet();
+ stats.evictionCounter.incrementAndGet();
+ if (evictionListener != null)
+ {
+ evictionListener.evictedEntry(o.key, o.value);
+ }
+ }
+
+ /**
+ * Returns 'n' number of oldest accessed entries present in this cache.
+ *
+ * This uses a TreeSet to collect the 'n' oldest items ordered by ascending last access time
+ * and returns a LinkedHashMap containing 'n' or less than 'n' entries.
+ * @param n the number of oldest items needed
+ * @return a LinkedHashMap containing 'n' or less than 'n' entries
+ */
+ public Map<K, V> getOldestAccessedItems(int n)
+ {
+ Map<K, V> result = new LinkedHashMap<K, V>();
+ if (n <= 0)
+ {
+ return result;
+ }
+ TreeSet<CacheEntry<K, V>> tree = new TreeSet<CacheEntry<K, V>>();
+ markAndSweepLock.lock();
+ try
+ {
+ for (Map.Entry<Object, CacheEntry<K, V>> entry : map.entrySet())
+ {
+ CacheEntry<K, V> ce = entry.getValue();
+ ce.lastAccessedCopy = ce.lastAccessed;
+ if (tree.size() < n)
+ {
+ tree.add(ce);
+ }
+ else
+ {
+ if (ce.lastAccessedCopy < tree.first().lastAccessedCopy)
+ {
+ tree.remove(tree.first());
+ tree.add(ce);
+ }
+ }
+ }
+ }
+ finally
+ {
+ markAndSweepLock.unlock();
+ }
+ for (CacheEntry<K, V> e : tree)
+ {
+ result.put(e.key, e.value);
+ }
+ return result;
+ }
+
+ public Map<K, V> getLatestAccessedItems(int n)
+ {
+ Map<K, V> result = new LinkedHashMap<K, V>();
+ if (n <= 0)
+ {
+ return result;
+ }
+ TreeSet<CacheEntry<K, V>> tree = new TreeSet<CacheEntry<K, V>>();
+ // we need to grab the lock since we are changing lastAccessedCopy
+ markAndSweepLock.lock();
+ try
+ {
+ for (Map.Entry<Object, CacheEntry<K, V>> entry : map.entrySet())
+ {
+ CacheEntry<K, V> ce = entry.getValue();
+ ce.lastAccessedCopy = ce.lastAccessed;
+ if (tree.size() < n)
+ {
+ tree.add(ce);
+ }
+ else
+ {
+ if (ce.lastAccessedCopy > tree.last().lastAccessedCopy)
+ {
+ tree.remove(tree.last());
+ tree.add(ce);
+ }
+ }
+ }
+ }
+ finally
+ {
+ markAndSweepLock.unlock();
+ }
+ for (CacheEntry<K, V> e : tree)
+ {
+ result.put(e.key, e.value);
+ }
+ return result;
+ }
+
+ public int size()
+ {
+ return stats.size.get();
+ }
+
+ public void clear()
+ {
+ map.clear();
+ }
+
+ public Map<Object, CacheEntry<K, V>> getMap()
+ {
+ return map;
+ }
+
+ private static class CacheEntry<K, V> implements
+ Comparable<CacheEntry<K, V>>
+ {
+ K key;
+ V value;
+ volatile long lastAccessed = 0;
+ long lastAccessedCopy = 0;
+
+ public CacheEntry(K key, V value, long lastAccessed)
+ {
+ this.key = key;
+ this.value = value;
+ this.lastAccessed = lastAccessed;
+ }
+
+ public void setLastAccessed(long lastAccessed)
+ {
+ this.lastAccessed = lastAccessed;
+ }
+
+ public int compareTo(CacheEntry<K, V> that)
+ {
+ if (this.lastAccessedCopy == that.lastAccessedCopy)
+ {
+ return 0;
+ }
+ return this.lastAccessedCopy < that.lastAccessedCopy ? 1 : -1;
+ }
+
+ @Override
+ public int hashCode()
+ {
+ return value.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj)
+ {
+ return value.equals(obj);
+ }
+
+ @Override
+ public String toString()
+ {
+ return "key: " + key + " value: " + value + " lastAccessed:"
+ + lastAccessed;
+ }
+ }
+
+ private boolean isDestroyed = false;
+
+ public void destroy()
+ {
+ try
+ {
+ if (cleanupThread != null)
+ {
+ cleanupThread.stopThread();
+ }
+ }
+ finally
+ {
+ isDestroyed = true;
+ }
+ }
+
+ public Stats getStats()
+ {
+ return stats;
+ }
+
+ public static class Stats
+ {
+ private final AtomicLong accessCounter = new AtomicLong(0);
+ private final AtomicLong putCounter = new AtomicLong(0);
+ private final AtomicLong nonLivePutCounter = new AtomicLong(0);
+ private final AtomicLong missCounter = new AtomicLong();
+ private final AtomicInteger size = new AtomicInteger();
+ private AtomicLong evictionCounter = new AtomicLong();
+
+ public long getCumulativeLookups()
+ {
+ return (accessCounter.get() - putCounter.get() - nonLivePutCounter
+ .get()) + missCounter.get();
+ }
+
+ public long getCumulativeHits()
+ {
+ return accessCounter.get() - putCounter.get()
+ - nonLivePutCounter.get();
+ }
+
+ public long getCumulativePuts()
+ {
+ return putCounter.get();
+ }
+
+ public long getCumulativeEvictions()
+ {
+ return evictionCounter.get();
+ }
+
+ public int getCurrentSize()
+ {
+ return size.get();
+ }
+
+ public long getCumulativeNonLivePuts()
+ {
+ return nonLivePutCounter.get();
+ }
+
+ public long getCumulativeMisses()
+ {
+ return missCounter.get();
+ }
+
+ public void add(Stats other)
+ {
+ accessCounter.addAndGet(other.accessCounter.get());
+ putCounter.addAndGet(other.putCounter.get());
+ nonLivePutCounter.addAndGet(other.nonLivePutCounter.get());
+ missCounter.addAndGet(other.missCounter.get());
+ evictionCounter.addAndGet(other.evictionCounter.get());
+ size.set(Math.max(size.get(), other.size.get()));
+ }
+ }
+
+ public static interface EvictionListener<K, V>
+ {
+ public void evictedEntry(K key, V value);
+ }
+
+ private static class CleanupThread extends Thread
+ {
+ private WeakReference<ConcurrentLRUCache> cache;
+
+ private boolean stop = false;
+
+ public CleanupThread(ConcurrentLRUCache c)
+ {
+ cache = new WeakReference<ConcurrentLRUCache>(c);
+ }
+
+ @Override
+ public void run()
+ {
+ while (true)
+ {
+ synchronized (this)
+ {
+ if (stop)
+ {
+ break;
+ }
+ try
+ {
+ this.wait();
+ }
+ catch (InterruptedException e)
+ {
+ }
+ }
+ if (stop)
+ {
+ break;
+ }
+ ConcurrentLRUCache c = cache.get();
+ if (c == null)
+ {
+ break;
+ }
+ c.markAndSweep();
+ }
+ }
+
+ void wakeThread()
+ {
+ synchronized (this)
+ {
+ this.notify();
+ }
+ }
+
+ void stopThread()
+ {
+ synchronized (this)
+ {
+ stop = true;
+ this.notify();
+ }
+ }
+ }
+
+ @Override
+ protected void finalize() throws Throwable
+ {
+ try
+ {
+ if (!isDestroyed)
+ {
+ // This log message is useless, because it is not supposed to use
+ // thread cleanup strategy for this class.
+ //log.severe("ConcurrentLRUCache was not destroyed prior to finalize()," +
+ // " indicates a bug -- POSSIBLE RESOURCE LEAK!!!");
+ destroy();
+ }
+ }
+ finally
+ {
+ super.finalize();
+ }
+ }
+}
Propchange: myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java
URL: http://svn.apache.org/viewvc/myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java?rev=1296648&view=auto
==============================================================================
--- myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java (added)
+++ myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java Sat Mar 3 15:53:12 2012
@@ -0,0 +1,304 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.myfaces.shared.util;
+
+/** A PriorityQueue maintains a partial ordering of its elements such that the
+ * least element can always be found in constant time. Put()'s and pop()'s
+ * require log(size) time.
+ *
+ * <p><b>NOTE</b>: This class will pre-allocate a full array of
+ * length <code>maxSize+1</code> if instantiated via the
+ * {@link #PriorityQueue(int,boolean)} constructor with
+ * <code>prepopulate</code> set to <code>true</code>.
+ *
+ * @lucene.internal
+ * @see org.apache.lucene.util.PriorityQueue
+*/
+public abstract class PriorityQueue<T>
+{
+ private int size;
+ private final int maxSize;
+ private final T[] heap;
+
+ public PriorityQueue(int maxSize)
+ {
+ this(maxSize, true);
+ }
+
+ @SuppressWarnings("unchecked")
+ public PriorityQueue(int maxSize, boolean prepopulate)
+ {
+ size = 0;
+ int heapSize;
+ if (0 == maxSize)
+ {
+ // We allocate 1 extra to avoid if statement in top()
+ heapSize = 2;
+ }
+ else
+ {
+ if (maxSize == Integer.MAX_VALUE)
+ {
+ // Don't wrap heapSize to -1, in this case, which
+ // causes a confusing NegativeArraySizeException.
+ // Note that very likely this will simply then hit
+ // an OOME, but at least that's more indicative to
+ // caller that this values is too big. We don't +1
+ // in this case, but it's very unlikely in practice
+ // one will actually insert this many objects into
+ // the PQ:
+ heapSize = Integer.MAX_VALUE;
+ }
+ else
+ {
+ // NOTE: we add +1 because all access to heap is
+ // 1-based not 0-based. heap[0] is unused.
+ heapSize = maxSize + 1;
+ }
+ }
+ heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
+ this.maxSize = maxSize;
+
+ if (prepopulate)
+ {
+ // If sentinel objects are supported, populate the queue with them
+ T sentinel = getSentinelObject();
+ if (sentinel != null)
+ {
+ heap[1] = sentinel;
+ for (int i = 2; i < heap.length; i++)
+ {
+ heap[i] = getSentinelObject();
+ }
+ size = maxSize;
+ }
+ }
+ }
+
+ /** Determines the ordering of objects in this priority queue. Subclasses
+ * must define this one method.
+ * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter <tt>b</tt>.
+ */
+ protected abstract boolean lessThan(T a, T b);
+
+ /**
+ * This method can be overridden by extending classes to return a sentinel
+ * object which will be used by the {@link PriorityQueue#PriorityQueue(int,boolean)}
+ * constructor to fill the queue, so that the code which uses that queue can always
+ * assume it's full and only change the top without attempting to insert any new
+ * object.<br>
+ *
+ * Those sentinel values should always compare worse than any non-sentinel
+ * value (i.e., {@link #lessThan} should always favor the
+ * non-sentinel values).<br>
+ *
+ * By default, this method returns false, which means the queue will not be
+ * filled with sentinel values. Otherwise, the value returned will be used to
+ * pre-populate the queue. Adds sentinel values to the queue.<br>
+ *
+ * If this method is extended to return a non-null value, then the following
+ * usage pattern is recommended:
+ *
+ * <pre>
+ * // extends getSentinelObject() to return a non-null value.
+ * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
+ * // save the 'top' element, which is guaranteed to not be null.
+ * MyObject pqTop = pq.top();
+ * <...>
+ * // now in order to add a new element, which is 'better' than top (after
+ * // you've verified it is better), it is as simple as:
+ * pqTop.change().
+ * pqTop = pq.updateTop();
+ * </pre>
+ *
+ * <b>NOTE:</b> if this method returns a non-null value, it will be called by
+ * the {@link PriorityQueue#PriorityQueue(int,boolean)} constructor
+ * {@link #size()} times, relying on a new object to be returned and will not
+ * check if it's null again. Therefore you should ensure any call to this
+ * method creates a new instance and behaves consistently, e.g., it cannot
+ * return null if it previously returned non-null.
+ *
+ * @return the sentinel object to use to pre-populate the queue, or null if
+ * sentinel objects are not supported.
+ */
+ protected T getSentinelObject()
+ {
+ return null;
+ }
+
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time. If one tries to add
+ * more objects than maxSize from initialize an
+ * {@link ArrayIndexOutOfBoundsException} is thrown.
+ *
+ * @return the new 'top' element in the queue.
+ */
+ public final T add(T element)
+ {
+ size++;
+ heap[size] = element;
+ upHeap();
+ return heap[1];
+ }
+
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time.
+ * It returns the object (if any) that was
+ * dropped off the heap because it was full. This can be
+ * the given parameter (in case it is smaller than the
+ * full heap's minimum, and couldn't be added), or another
+ * object that was previously the smallest value in the
+ * heap and now has been replaced by a larger one, or null
+ * if the queue wasn't yet full with maxSize elements.
+ */
+ public T insertWithOverflow(T element)
+ {
+ if (size < maxSize)
+ {
+ add(element);
+ return null;
+ }
+ else if (size > 0 && !lessThan(element, heap[1]))
+ {
+ T ret = heap[1];
+ heap[1] = element;
+ updateTop();
+ return ret;
+ }
+ else
+ {
+ return element;
+ }
+ }
+
+ /** Returns the least element of the PriorityQueue in constant time. */
+ public final T top()
+ {
+ // We don't need to check size here: if maxSize is 0,
+ // then heap is length 2 array with both entries null.
+ // If size is 0 then heap[1] is already null.
+ return heap[1];
+ }
+
+ /** Removes and returns the least element of the PriorityQueue in log(size)
+ time. */
+ public final T pop()
+ {
+ if (size > 0)
+ {
+ T result = heap[1]; // save first value
+ heap[1] = heap[size]; // move last to first
+ heap[size] = null; // permit GC of objects
+ size--;
+ downHeap(); // adjust heap
+ return result;
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+ /**
+ * Should be called when the Object at top changes values. Still log(n) worst
+ * case, but it's at least twice as fast to
+ *
+ * <pre>
+ * pq.top().change();
+ * pq.updateTop();
+ * </pre>
+ *
+ * instead of
+ *
+ * <pre>
+ * o = pq.pop();
+ * o.change();
+ * pq.push(o);
+ * </pre>
+ *
+ * @return the new 'top' element.
+ */
+ public final T updateTop()
+ {
+ downHeap();
+ return heap[1];
+ }
+
+ /** Returns the number of elements currently stored in the PriorityQueue. */
+ public final int size()
+ {
+ return size;
+ }
+
+ /** Removes all entries from the PriorityQueue. */
+ public final void clear()
+ {
+ for (int i = 0; i <= size; i++)
+ {
+ heap[i] = null;
+ }
+ size = 0;
+ }
+
+ private final void upHeap()
+ {
+ int i = size;
+ T node = heap[i]; // save bottom node
+ int j = i >>> 1;
+ while (j > 0 && lessThan(node, heap[j]))
+ {
+ heap[i] = heap[j]; // shift parents down
+ i = j;
+ j = j >>> 1;
+ }
+ heap[i] = node; // install saved node
+ }
+
+ private final void downHeap()
+ {
+ int i = 1;
+ T node = heap[i]; // save top node
+ int j = i << 1; // find smaller child
+ int k = j + 1;
+ if (k <= size && lessThan(heap[k], heap[j]))
+ {
+ j = k;
+ }
+ while (j <= size && lessThan(heap[j], node))
+ {
+ heap[i] = heap[j]; // shift up child
+ i = j;
+ j = i << 1;
+ k = j + 1;
+ if (k <= size && lessThan(heap[k], heap[j]))
+ {
+ j = k;
+ }
+ }
+ heap[i] = node; // install saved node
+ }
+
+ /** This method returns the internal heap array as Object[].
+ * @lucene.internal
+ */
+ protected final Object[] getHeapArray()
+ {
+ return (Object[]) heap;
+ }
+}
Propchange: myfaces/core/trunk/shared/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java
------------------------------------------------------------------------------
svn:eol-style = native