1 /**
2 * Copyright 2003-2006 Greg Luck
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package net.sf.ehcache.store;
18
19 import net.sf.ehcache.Element;
20 import net.sf.ehcache.MemoryStoreTester;
21 import net.sf.ehcache.StopWatch;
22 import net.sf.ehcache.AbstractCacheTest;
23 import org.apache.commons.logging.Log;
24 import org.apache.commons.logging.LogFactory;
25
26 import java.io.IOException;
27 import java.util.Date;
28 import java.util.HashMap;
29 import java.util.Iterator;
30 import java.util.Map;
31 import java.util.Random;
32
33 /**
34 * Test class for LfuMemoryStore
35 * <p/>
36 * @author <a href="ssuravarapu@users.sourceforge.net">Surya Suravarapu</a>
37 * @version $Id: LfuMemoryStoreTest.java 28 2006-04-15 05:12:32Z gregluck $
38 */
39 public class LfuMemoryStoreTest extends MemoryStoreTester {
40
41 private static final Log LOG = LogFactory.getLog(LfuMemoryStoreTest.class.getName());
42
43 /**
44 * setup test
45 */
46 protected void setUp() throws Exception {
47 super.setUp();
48 createMemoryStore(MemoryStoreEvictionPolicy.LFU);
49 }
50
51
52 /**
53 * Tests the put by reading the config file
54 */
55 public void testPutFromConfig() throws Exception {
56 createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache1");
57 putTest();
58 }
59
60 /**
61 * Tests the put by reading the config file
62 */
63 public void testPutFromConfigZeroMemoryStore() throws Exception {
64 createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache2");
65 Element element = new Element("1", "value");
66 store.put(element);
67 assertNull(store.get("1"));
68 }
69
70 /**
71 * Tests the remove() method by using the parameters specified in the config file
72 */
73 public void testRemoveFromConfig() throws Exception {
74 createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache1");
75 removeTest();
76 }
77
78 /**
79 * Benchmark to test speed.
80 * This takes a little longer for LFU than the others.
81 * Takes about 7400ms
82 */
83 public void testBenchmarkPutGetSurya() throws Exception {
84 benchmarkPutGetSuryaTest(9000);
85 }
86
87 /**
88 * Tests the LFU policy
89 */
90 public void testLfuPolicy() throws Exception {
91 createMemoryStore(MemoryStoreEvictionPolicy.LFU, 4);
92 lfuPolicyTest();
93 }
94
95 /**
96 * Tests the LFU policy by using the parameters specified in the config file
97 */
98 public void testLfuPolicyFromConfig() throws Exception {
99 createMemoryStore(AbstractCacheTest.TEST_CONFIG_DIR + "ehcache-policy-test.xml", "sampleLFUCache1");
100 lfuPolicyTest();
101 }
102
103
104 private void lfuPolicyTest() throws IOException {
105
106 assertEquals(0, store.getSize());
107
108
109 Element element = new Element("key1", "value1");
110 store.put(element);
111 assertEquals(1, store.getSize());
112
113 element = new Element("key2", "value2");
114 store.put(element);
115 assertEquals(2, store.getSize());
116
117 element = new Element("key3", "value3");
118 store.put(element);
119 assertEquals(3, store.getSize());
120
121 element = new Element("key4", "value4");
122 store.put(element);
123 assertEquals(4, store.getSize());
124
125
126 store.get("key1");
127 store.get("key1");
128 store.get("key3");
129 store.get("key3");
130 store.get("key3");
131 store.get("key4");
132
133
134 element = new Element("key5", "value5");
135 store.put(element);
136
137 assertEquals(4, store.getSize());
138
139 assertNull(store.get("key2"));
140
141
142 store.get("key5");
143 store.get("key5");
144
145
146 element = new Element("key6", "value6");
147 store.put(element);
148 assertEquals(4, store.getSize());
149 assertNull(store.get("key4"));
150 }
151
152 /**
153 * Benchmark to test speed.
154 * new sampling LFU 417ms
155 */
156 public void testBenchmarkPutGetRemove() throws Exception {
157 super.testBenchmarkPutGetRemove();
158 }
159
160
161 /**
162 * Multi-thread read, put and removeAll test.
163 * This checks for memory leaks
164 * using the removeAll which was the known cause of memory leaks with LruMemoryStore in JCS
165 * new sampling LFU has no leaks
166 */
167 public void testMemoryLeak() throws Exception {
168 super.testMemoryLeak();
169 }
170
171 /**
172 * Benchmark to test speed.
173 * new sampling LFU 132ms
174 */
175 public void testBenchmarkPutGet() throws Exception {
176 super.testBenchmarkPutGet();
177 }
178
179 /**
180 * Tests how random the java.util.Map iteration is by measuring the differences in iterate order.
181 * <p/>
182 * If iterate was ordered in either insert or reverse insert order the mean difference would be 1.
183 * Using Random gives a mean difference of 343.
184 * The observed value is 175 but always 175 for a key set of 500 because it always iterates in the same order,
185 * just not an obvious order.
186 * <p/>
187 * Conclusion: Unable to use the iterator as a pseudorandom selector.
188 */
189 public void testRandomnessOfIterator() {
190 int mean = 0;
191 int absoluteDifferences = 0;
192 int lastReading = 0;
193 Map map = new HashMap();
194 for (int i = 1; i <= 500; i++) {
195 mean += i;
196 map.put("" + i, " ");
197 }
198 mean = mean / 500;
199 for (Iterator iterator = map.keySet().iterator(); iterator.hasNext();) {
200 String string = (String) iterator.next();
201 int thisReading = Integer.parseInt(string);
202 absoluteDifferences += Math.abs(lastReading - thisReading);
203 lastReading = thisReading;
204 }
205 LOG.info("Mean difference through iteration: " + absoluteDifferences / 500);
206
207
208 Random random = new Random();
209 while (map.size() != 0) {
210 int thisReading = random.nextInt(501);
211 Object o = map.remove("" + thisReading);
212 if (o == null) {
213 continue;
214 }
215 absoluteDifferences += Math.abs(lastReading - thisReading);
216 lastReading = thisReading;
217 }
218 LOG.info("Mean difference with random selection without replacement : " + absoluteDifferences / 500);
219 LOG.info("Mean of range 1 - 500 : " + mean);
220
221 }
222
223
224 /**
225 * Check nothing breaks and that we get the right number of samples
226 *
227 * @throws IOException
228 */
229 public void testSampling() throws IOException {
230 createMemoryStore(MemoryStoreEvictionPolicy.LFU, 1000);
231 Element[] elements = null;
232 for (int i = 0; i < 10; i++) {
233 store.put(new Element("" + i, new Date()));
234 elements = ((LfuMemoryStore) store).sampleElements(i + 1);
235 }
236
237 for (int i = 10; i < 2000; i++) {
238 store.put(new Element("" + i, new Date()));
239 elements = ((LfuMemoryStore) store).sampleElements(10);
240 assertEquals(10, elements.length);
241 }
242 }
243
244
245 /**
246 * Check we get reasonable results for 2000 entries where entry 0 is accessed once increasing to entry 1999 accessed
247 * 2000 times.
248 * <p/>
249 * 1 to 5000 population, with hit counts ranging from 1 to 500, not selecting lowest half. 5000 tests
250 * S Cost No
251 * 7 38 99.24% confidence
252 * 8 27 99.46% confidence
253 * 9 10
254 * 10 11300 4 99.92% confidence
255 * 12 2
256 * 20 11428 0 99.99% confidence
257 * <p/>
258 * 1 to 5000 population, with hit counts ranging from 1 to 500, not selecting lowest quarter. 5000 tests
259 * S No
260 * 10 291 94.18% confidence
261 * 20 15
262 * 30 11536 1 99.99% confidence
263 * <p/>
264 * For those with a statistical background the branch of stats which deals with this is hypothesis testing and
265 * the Student's T distribution. The higher your sample the greater confidence you can have in a hypothesis, in
266 * this case whether or not the "lowest" value lies in the bottom half or quarter of the distribution. Adding
267 * samples rapidly increases confidence but the return from extra sampling rapidly diminishes.
268 * <p/>
269 * Cost is not affected much by sample size. Profiling shows that it is the iteration that is causing most of the
270 * time. If we had access to the array backing Map, all would work very fast. Still, it is fast enough.
271 * <p/>
272 * A 99.99% confidence interval can be achieved that the "lowest" element is actually in the bottom quarter of the
273 * hit count distribution.
274 * @throws IOException
275 */
276 public void testLowest() throws IOException {
277 createMemoryStore(MemoryStoreEvictionPolicy.LFU, 5000);
278 Element element = null;
279 Element newElement = null;
280 for (int i = 0; i < 10; i++) {
281 newElement = new Element("" + i, new Date());
282 store.put(newElement);
283 int j;
284 for (j = 0; j <= i; j++) {
285 store.get("" + i);
286 }
287 if (i > 0) {
288 element = ((LfuMemoryStore) store).findRelativelyUnused(newElement);
289 assertTrue(!element.equals(newElement));
290 assertTrue(element.getHitCount() < 2);
291 }
292 }
293
294 int lowestQuarterNotIdentified = 0;
295
296 long findTime = 0;
297 StopWatch stopWatch = new StopWatch();
298 for (int i = 10; i < 5000; i++) {
299 store.put(new Element("" + i, new Date()));
300 int j;
301 int maximumHitCount = 0;
302 for (j = 0; j <= i; j += 10) {
303 store.get("" + i);
304 maximumHitCount++;
305 }
306
307 stopWatch.getElapsedTime();
308 element = ((LfuMemoryStore) store).findRelativelyUnused(newElement);
309 findTime += stopWatch.getElapsedTime();
310 long lowest = element.getHitCount();
311 long bottomQuarter = (Math.round(maximumHitCount / 4.0) + 1);
312 assertTrue(!element.equals(newElement));
313 if (lowest > bottomQuarter) {
314 lowestQuarterNotIdentified++;
315
316 }
317 }
318 LOG.info("Find time: " + findTime);
319 assertTrue(findTime < 1500);
320 LOG.info("Selections not in lowest quartile: " + lowestQuarterNotIdentified);
321 assertTrue(lowestQuarterNotIdentified < 3);
322
323 }
324
325 }