|
1
5 package com.tc.object.cache;
6
7 import com.tc.logging.TCLogger;
8 import com.tc.logging.TCLogging;
9 import com.tc.text.PrettyPrinter;
10
11 import gnu.trove.TLinkedList;
12 import gnu.trove.TObjectLongHashMap;
13
14 import java.util.ArrayList  ;
15 import java.util.Arrays ;
16 import java.util.Collection ;
17 import java.util.Collections ;
18 import java.util.HashSet ;
19 import java.util.Iterator ;
20 import java.util.Map ;
21 import java.util.TreeMap ;
22 import java.util.Map.Entry;
23
24
28 public class LFUEvictionPolicy implements EvictionPolicy {
29
30 private static final TCLogger logger = TCLogging.getLogger(LFUEvictionPolicy.class);
31
32 private static final LFUConfig DEFAULT_CONFIG = new LFUConfig() {
33
34 public float getAgingFactor() {
35 return 1;
37 }
38
39 public int getRecentlyAccessedIgnorePercentage() {
40 return 20;
41 }
42
43 public boolean isDebugEnabled() {
44 return false;
45 }
46
47 };
48
49 private final int capacity;
50 private final int evictionSize;
51 private final TLinkedList cache = new TLinkedList();
52 private final LFUConfig config;
53
54 private TObjectLongHashMap smap = new TObjectLongHashMap();
55
56 public LFUEvictionPolicy(int capacity) {
57 this(capacity, capacity / 10, DEFAULT_CONFIG);
58 }
59
60 public LFUEvictionPolicy(int capacity, LFUConfig config) {
61 this(capacity, capacity / 10, config);
62 }
63
64 public LFUEvictionPolicy(int capacity, int evictionSize) {
65 this(capacity, evictionSize, DEFAULT_CONFIG);
66 }
67
68 public LFUEvictionPolicy(int capacity, int evictionSize, LFUConfig config) {
69 if (logger.isDebugEnabled()) {
70 logger.debug("new " + getClass().getName() + "(" + capacity + ")");
71 }
72 this.capacity = capacity;
73 this.evictionSize = (evictionSize <= 0 ? 1 : evictionSize);
74 this.config = config;
75 }
76
77 public synchronized boolean add(Cacheable obj) {
78 cache.addLast(obj);
79 if (config.isDebugEnabled()) smap.put(obj.getObjectID(), System.currentTimeMillis());
80 return isCacheFull();
81 }
82
83 private boolean isCacheFull() {
84 return (capacity > 0 && cache.size() > capacity);
85 }
86
87 public int getCacheCapacity() {
88 return capacity;
89 }
90
91 public synchronized void markReferenced(Cacheable obj) {
92 obj.markAccessed();
93 moveToTail(obj);
94 }
95
96 private void moveToTail(Cacheable obj) {
97 if (contains(obj)) {
98 cache.remove(obj);
99 cache.addLast(obj);
100 }
101 }
102
103 public Collection getRemovalCandidates(int maxCount) {
104 Collection candidates = getRemovalCandidatesInternal(maxCount);
105 if (config.isDebugEnabled()) {
106 reportTime("Cache", cache.subList(0, cache.size()));
107 reportTime("Eviction candidates", candidates);
108 }
109 return candidates;
110 }
111
112 private void reportTime(String name, Collection cacheables) {
113 long now = System.currentTimeMillis();
114 long times[] = new long[cacheables.size()];
115 int j = 0;
116 long avg = 0;
117 synchronized (this) {
118 for (Iterator i = cacheables.iterator(); i.hasNext();) {
119 Cacheable c = (Cacheable) i.next();
120 long diff = now - smap.get(c.getObjectID());
121 times[j++] = diff;
122 avg += diff;
123 }
124 }
125 avg = avg / times.length;
126 Arrays.sort(times);
128 StringBuffer sb = new StringBuffer (name);
129 sb.append(" : size = ").append(cacheables.size()).append(" Avg = ").append(avg);
130 sb.append(" Min = ").append(times[0]);
131 sb.append(" Max = ").append(times[times.length - 1]);
132 sb.append("\n\n");
133 int n10 = times.length / 10;
134 for (int i = 1; i < 10; i++) {
135 sb.append("\t").append(i * 10).append(" % = ").append(times[n10 * i]).append("\n");
136 }
137 sb.append("\n\n");
138 logger.info(sb.toString());
139 }
140
141 private Collection getRemovalCandidatesInternal(int maxCount) {
142
143 long start = System.currentTimeMillis();
144 Collection rv = new HashSet ();
145 int count = 0;
146 ArrayList accessCounts;
147 Cacheable stop, c;
148 synchronized (this) {
149 if (capacity > 0) {
150 if (!isCacheFull()) { return Collections.EMPTY_LIST; }
151 if (maxCount <= 0 || maxCount > evictionSize) {
152 maxCount = evictionSize;
153 }
154 } else if (maxCount <= 0) {
155 throw new AssertionError ("Please specify maxcount > 0 as capacity is set to : " + capacity + " Max Count = "
157 + maxCount);
158 }
159
160 count = Math.min(cache.size(), maxCount);
161 accessCounts = new ArrayList (cache.size());
162
163 c = (Cacheable) cache.getFirst();
164 stop = getStopPoint();
165 int agingFactor = (int) config.getAgingFactor();
166 while (cache.size() - rv.size() > capacity && count > 0 && c != null && c != stop) {
168 Cacheable next = (Cacheable) c.getNext();
169 int accessed = c.accessCount(agingFactor);
170 if (accessed == 0) {
171 if (c.canEvict()) {
172 rv.add(c);
173 cache.remove(c);
174 cache.addLast(c);
175 count--;
176 }
177 } else {
178 accessCounts.add(new Integer (accessed));
180
181 }
182 c = next;
183 }
184 while (c != null && c != stop) {
185 c.accessCount(agingFactor);
186 c = (Cacheable) c.getNext();
187 }
188 if (cache.size() - rv.size() <= capacity || count <= 0) {
189 log_time_taken(start);
191 return rv;
192 }
193 }
194
195 Map accessCountSummary = new TreeMap (); for (Iterator i = accessCounts.iterator(); i.hasNext();) {
198 Integer ac = (Integer ) i.next();
199 incrementAccessCountFor(accessCountSummary, ac);
200 }
201
202 accessCounts = null;
204
205 int accessCountCutOff = 0;
207 int remaining = count;
208 for (Iterator i = accessCountSummary.entrySet().iterator(); i.hasNext();) {
209 Entry e = (Entry) i.next();
210 accessCountCutOff = ((Integer ) e.getKey()).intValue();
211 int occurance = ((Integer ) e.getValue()).intValue();
212 remaining -= occurance;
213 if (remaining <= 0) {
214 break;
215 }
216 }
217
218 accessCountSummary = null;
220
221 synchronized (this) {
225 c = (Cacheable) cache.getFirst();
226 while (cache.size() - rv.size() > capacity && count > 0 && c != null && c != stop) {
227 Cacheable next = (Cacheable) c.getNext();
228 int accessed = c.accessCount(1);
229 if (accessed <= accessCountCutOff) {
230 if (c.canEvict()) {
231 rv.add(c);
232 cache.remove(c);
233 cache.addLast(c);
234 count--;
235 }
236 }
237 c = next;
238 }
239 log_time_taken(start);
240 return rv;
241 }
242 }
243
244 private Cacheable getStopPoint() {
245 Cacheable stop = (Cacheable) cache.getLast();
248 int ignore = (int) (cache.size() * config.getRecentlyAccessedIgnorePercentage() / 100.0); while (ignore-- > 0) {
251 stop = (Cacheable) stop.getPrevious();
252 }
253 return stop;
254 }
255
256 private void log_time_taken(long start) {
257 long taken = System.currentTimeMillis() - start;
258 if (taken > 1000) {
259 logger.info("Time taken to compute removal candidates : " + taken + " ms");
260 }
261 }
262
263 private void incrementAccessCountFor(Map accessCountSummary, Integer key) {
264 Integer count = (Integer ) accessCountSummary.get(key);
265 if (count == null) {
266 accessCountSummary.put(key, new Integer (1));
267 } else {
268 accessCountSummary.put(key, new Integer (count.intValue() + 1));
269 }
270 }
271
272 private boolean contains(Cacheable obj) {
273 return obj != null && (obj.getNext() != null || obj.getPrevious() != null);
275 }
276
277 public synchronized void remove(Cacheable obj) {
278 if (contains(obj)) {
279 cache.remove(obj);
280 if (config.isDebugEnabled()) smap.remove(obj.getObjectID());
281 }
282 }
283
284 public PrettyPrinter prettyPrint(PrettyPrinter out) {
285 PrettyPrinter rv = out;
286 out.println(getClass().getName());
287 out = out.duplicateAndIndent();
288 out.indent().println("max size: " + capacity).indent().print("cache: ").visit(cache).println();
289 return rv;
290 }
291
292 }
293 |
Popular Tags |
Java API By Example, From Geeks To Geeks.