001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright
003: * notice. All rights reserved.
004: */
005: package com.tc.object.cache;
006:
007: import com.tc.logging.TCLogger;
008: import com.tc.logging.TCLogging;
009: import com.tc.text.PrettyPrinter;
010:
011: import gnu.trove.TLinkedList;
012: import gnu.trove.TObjectLongHashMap;
013:
014: import java.util.ArrayList;
015: import java.util.Arrays;
016: import java.util.Collection;
017: import java.util.Collections;
018: import java.util.HashSet;
019: import java.util.Iterator;
020: import java.util.Map;
021: import java.util.TreeMap;
022: import java.util.Map.Entry;
023:
024: /**
025: * This Cache policy tries to evict objects from cache using the access count. The Least Frequenctly used objects are
026: * chucked out.
027: */
028: public class LFUEvictionPolicy implements EvictionPolicy {
029:
030: private static final TCLogger logger = TCLogging
031: .getLogger(LFUEvictionPolicy.class);
032:
033: private static final LFUConfig DEFAULT_CONFIG = new LFUConfig() {
034:
035: public float getAgingFactor() {
036: // DISABLED
037: return 1;
038: }
039:
040: public int getRecentlyAccessedIgnorePercentage() {
041: return 20;
042: }
043:
044: public boolean isDebugEnabled() {
045: return false;
046: }
047:
048: };
049:
050: private final int capacity;
051: private final int evictionSize;
052: private final TLinkedList cache = new TLinkedList();
053: private final LFUConfig config;
054:
055: private TObjectLongHashMap smap = new TObjectLongHashMap();
056:
057: public LFUEvictionPolicy(int capacity) {
058: this (capacity, capacity / 10, DEFAULT_CONFIG);
059: }
060:
061: public LFUEvictionPolicy(int capacity, LFUConfig config) {
062: this (capacity, capacity / 10, config);
063: }
064:
065: public LFUEvictionPolicy(int capacity, int evictionSize) {
066: this (capacity, evictionSize, DEFAULT_CONFIG);
067: }
068:
069: public LFUEvictionPolicy(int capacity, int evictionSize,
070: LFUConfig config) {
071: if (logger.isDebugEnabled()) {
072: logger.debug("new " + getClass().getName() + "(" + capacity
073: + ")");
074: }
075: this .capacity = capacity;
076: this .evictionSize = (evictionSize <= 0 ? 1 : evictionSize);
077: this .config = config;
078: }
079:
080: public synchronized boolean add(Cacheable obj) {
081: cache.addLast(obj);
082: if (config.isDebugEnabled())
083: smap.put(obj.getObjectID(), System.currentTimeMillis());
084: return isCacheFull();
085: }
086:
087: private boolean isCacheFull() {
088: return (capacity > 0 && cache.size() > capacity);
089: }
090:
091: public int getCacheCapacity() {
092: return capacity;
093: }
094:
095: public synchronized void markReferenced(Cacheable obj) {
096: obj.markAccessed();
097: moveToTail(obj);
098: }
099:
100: private void moveToTail(Cacheable obj) {
101: if (contains(obj)) {
102: cache.remove(obj);
103: cache.addLast(obj);
104: }
105: }
106:
107: public Collection getRemovalCandidates(int maxCount) {
108: Collection candidates = getRemovalCandidatesInternal(maxCount);
109: if (config.isDebugEnabled()) {
110: reportTime("Cache", cache.subList(0, cache.size()));
111: reportTime("Eviction candidates", candidates);
112: }
113: return candidates;
114: }
115:
116: private void reportTime(String name, Collection cacheables) {
117: long now = System.currentTimeMillis();
118: long times[] = new long[cacheables.size()];
119: int j = 0;
120: long avg = 0;
121: synchronized (this ) {
122: for (Iterator i = cacheables.iterator(); i.hasNext();) {
123: Cacheable c = (Cacheable) i.next();
124: long diff = now - smap.get(c.getObjectID());
125: times[j++] = diff;
126: avg += diff;
127: }
128: }
129: avg = avg / times.length;
130: // Stupid but whatever
131: Arrays.sort(times);
132: StringBuffer sb = new StringBuffer(name);
133: sb.append(" : size = ").append(cacheables.size()).append(
134: " Avg = ").append(avg);
135: sb.append(" Min = ").append(times[0]);
136: sb.append(" Max = ").append(times[times.length - 1]);
137: sb.append("\n\n");
138: int n10 = times.length / 10;
139: for (int i = 1; i < 10; i++) {
140: sb.append("\t").append(i * 10).append(" % = ").append(
141: times[n10 * i]).append("\n");
142: }
143: sb.append("\n\n");
144: logger.info(sb.toString());
145: }
146:
147: private Collection getRemovalCandidatesInternal(int maxCount) {
148:
149: long start = System.currentTimeMillis();
150: Collection rv = new HashSet();
151: int count = 0;
152: ArrayList accessCounts;
153: Cacheable stop, c;
154: synchronized (this ) {
155: if (capacity > 0) {
156: if (!isCacheFull()) {
157: return Collections.EMPTY_LIST;
158: }
159: if (maxCount <= 0 || maxCount > evictionSize) {
160: maxCount = evictionSize;
161: }
162: } else if (maxCount <= 0) {
163: // disallow negetative maxCount when capacity is negative
164: throw new AssertionError(
165: "Please specify maxcount > 0 as capacity is set to : "
166: + capacity + " Max Count = " + maxCount);
167: }
168:
169: count = Math.min(cache.size(), maxCount);
170: accessCounts = new ArrayList(cache.size());
171:
172: c = (Cacheable) cache.getFirst();
173: stop = getStopPoint();
174: int agingFactor = (int) config.getAgingFactor();
175: // Step 1: Remove elements which were never accessed and at the same time collect stats
176: while (cache.size() - rv.size() > capacity && count > 0
177: && c != null && c != stop) {
178: Cacheable next = (Cacheable) c.getNext();
179: int accessed = c.accessCount(agingFactor);
180: if (accessed == 0) {
181: if (c.canEvict()) {
182: rv.add(c);
183: cache.remove(c);
184: cache.addLast(c);
185: count--;
186: }
187: } else {
188: // incrementAccessCountFor(accessCountSummary, accessed);
189: accessCounts.add(new Integer(accessed));
190:
191: }
192: c = next;
193: }
194: while (c != null && c != stop) {
195: c.accessCount(agingFactor);
196: c = (Cacheable) c.getNext();
197: }
198: if (cache.size() - rv.size() <= capacity || count <= 0) {
199: // we already got what is needed
200: log_time_taken(start);
201: return rv;
202: }
203: }
204:
205: // Step 2: Do the sorting ... This can be optimized since we dont need it to be sorted.
206: Map accessCountSummary = new TreeMap(); // This is sorted map
207: for (Iterator i = accessCounts.iterator(); i.hasNext();) {
208: Integer ac = (Integer) i.next();
209: incrementAccessCountFor(accessCountSummary, ac);
210: }
211:
212: // release memory when done
213: accessCounts = null;
214:
215: // Step 3: Use the summary that was built earlier to decide the accessCountCutOff
216: int accessCountCutOff = 0;
217: int remaining = count;
218: for (Iterator i = accessCountSummary.entrySet().iterator(); i
219: .hasNext();) {
220: Entry e = (Entry) i.next();
221: accessCountCutOff = ((Integer) e.getKey()).intValue();
222: int occurance = ((Integer) e.getValue()).intValue();
223: remaining -= occurance;
224: if (remaining <= 0) {
225: break;
226: }
227: }
228:
229: // release memory when done
230: accessCountSummary = null;
231:
232: // Step 4 : Use the calculated accessCountCutOff to get the rigth candidates under the lock. Since we release teh
233: // lock,
234: // we have to be fault tolerant
235: synchronized (this ) {
236: c = (Cacheable) cache.getFirst();
237: while (cache.size() - rv.size() > capacity && count > 0
238: && c != null && c != stop) {
239: Cacheable next = (Cacheable) c.getNext();
240: int accessed = c.accessCount(1);
241: if (accessed <= accessCountCutOff) {
242: if (c.canEvict()) {
243: rv.add(c);
244: cache.remove(c);
245: cache.addLast(c);
246: count--;
247: }
248: }
249: c = next;
250: }
251: log_time_taken(start);
252: return rv;
253: }
254: }
255:
256: private Cacheable getStopPoint() {
257: // The last LRU_IN_MEMORY_PERCENTAGE of element are not processed to be fair with new objects/recently accessed
258: // objects
259: Cacheable stop = (Cacheable) cache.getLast();
260: int ignore = (int) (cache.size()
261: * config.getRecentlyAccessedIgnorePercentage() / 100.0); // force floating point
262: // arithemetic
263: while (ignore-- > 0) {
264: stop = (Cacheable) stop.getPrevious();
265: }
266: return stop;
267: }
268:
269: private void log_time_taken(long start) {
270: long taken = System.currentTimeMillis() - start;
271: if (taken > 1000) {
272: logger.info("Time taken to compute removal candidates : "
273: + taken + " ms");
274: }
275: }
276:
277: private void incrementAccessCountFor(Map accessCountSummary,
278: Integer key) {
279: Integer count = (Integer) accessCountSummary.get(key);
280: if (count == null) {
281: accessCountSummary.put(key, new Integer(1));
282: } else {
283: accessCountSummary.put(key, new Integer(
284: count.intValue() + 1));
285: }
286: }
287:
288: private boolean contains(Cacheable obj) {
289: // XXX: This is here to get around bogus implementation of TLinkedList.contains(Object)
290: return obj != null
291: && (obj.getNext() != null || obj.getPrevious() != null);
292: }
293:
294: public synchronized void remove(Cacheable obj) {
295: if (contains(obj)) {
296: cache.remove(obj);
297: if (config.isDebugEnabled())
298: smap.remove(obj.getObjectID());
299: }
300: }
301:
302: public PrettyPrinter prettyPrint(PrettyPrinter out) {
303: PrettyPrinter rv = out;
304: out.println(getClass().getName());
305: out = out.duplicateAndIndent();
306: out.indent().println("max size: " + capacity).indent().print(
307: "cache: ").visit(cache).println();
308: return rv;
309: }
310:
311: }
|