> -----Original Message-----
> From: Daniel Rall [mailto:[EMAIL PROTECTED]]
> Sent: Thursday, January 31, 2002 11:41 AM
> To: Turbine Developers List
> Subject: Re: cvs commit: jakarta-turbine-
> stratum/src/java/org/apache/stratum/jcs/engine/memory/mru
> MRUMemoryCache.java
>
> Was there something wrong with either of the two other versions of LRU
> in the Commons (LRUMap in Collections or BufferCache in Util), or does
> MRU differ significantly from LRU?
>
> Dan
Sorry, I didn't post here. I thought I was in another conversation.
I was testing the SimpleStore in commons and the general technique before
the commit you responded to. I'll include my message below since it is
relevant:
"
I found this example of a MRUCache on the sun site and tried making a memory
cache plugin with the technique.
http://developer.java.sun.com/developer/onlineTraining/Programming/JDCBo
ok/perf4.html
The performance of the LinkedList remove function makes it unusable. They
should deprecate it.
I'm going to check the code into JCS as an example. I got around the remove
problem for initial puts, since you can avoid a remove, but any updates will
kill you. Since every get in this system requires an update of the linked
list, it makes the technique unscalable.
The simplestore MRUMap class is pretty much the same as this example, except
it takes the remove hit for just about every operation, even an initial put.
I've included some results and the main method I used to test the MRUMap
below. Just watch the performance degrade.
G:\dev\bin\classes>java MRUMap 1000 2
took 111 ms. to put 1000
took 170 ms. to get 1000
took 160 ms. to put 1000
took 150 ms. to get 1000
G:\dev\bin\classes>java MRUMap 2000 2
took 290 ms. to put 2000
took 891 ms. to get 2000
took 691 ms. to put 2000
took 711 ms. to get 2000
G:\dev\bin\classes>java MRUMap 3000 2
took 1272 ms. to put 3000
took 3365 ms. to get 3000
took 3165 ms. to put 3000
took 3645 ms. to get 3000
G:\dev\bin\classes>java MRUMap 5000 2
took 6389 ms. to put 5000
took 16665 ms. to get 5000
took 16764 ms. to put 5000
took 16885 ms. to get 5000
G:\dev\bin\classes>java MRUMap 9000 2
took 26779 ms. to put 9000
took 56403 ms. to get 9000
took 51044 ms. to put 9000
took 54429 ms. to get 9000
(Oh, I depackaged the MRUMap to make it easier to work with. I attached
it.)
The test method for MRUMap:
////////////////////////////////////////////////////////////////////////
//
public static void main( String[] args ) {
int size = 1000;
if ( args.length > 0 ) {
try {
size = Integer.parseInt(args[0]);
} catch ( NumberFormatException e ) {
System.out.println( "arg 1 (size) should be a number" );
}
}
int cycles = 2;
if ( args.length > 1 ) {
try {
cycles = Integer.parseInt(args[1]);
} catch ( NumberFormatException e ) {
System.out.println( "arg 2 (cycles) should be a number" );
}
}
MRUMap map = new MRUMap( size );
boolean show = false;
if ( args.length > 2 ) {
try {
show = Boolean.valueOf(args[2]).booleanValue();;
} catch ( Exception e ) {
System.out.println( "arg 3 (show) should be true or false"
);
}
}
for ( int i = 0; i < cycles; i++ ) {
long startP = System.currentTimeMillis();
for ( int j = 0; j <= size; j++ ) {
map.put( "key" + j, "value" + j );
}
long endP = System.currentTimeMillis();
long deltaP = endP - startP;
System.out.println( "took " + deltaP + " ms. to put " + size );
long startG = System.currentTimeMillis();
for ( int j = 0; j <= size; j++ ) {
String val = (String)map.get( "key" + j );
if ( show ) {
System.out.println( val );
}
}
long endG = System.currentTimeMillis();
long deltaG = endG - startG;
System.out.println( "took " + deltaG + " ms. to get " + size );
}
} // end main
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\\\
The bad method in java.util.LinkedList
/////////////////////////////////////////////////////
/**
* Removes the first occurrence of the specified element in this list.
If
* the list does not contain the element, it is unchanged. More
formally,
* removes the element with the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
* element exists).
*
* @param o element to be removed from this list, if present.
* @return <tt>true</tt> if the list contained the specified element.
*/
public boolean remove(Object o) {
if (o==null) {
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
/////////////////////////////////////////
The LRUMemoryCache in JCS gets inside the linked list and doesn't suffer
from these problems. On average, with 9000 items the cache JCS is over 1000
time faster than the MRUMap.
Here are some times from the JCS tester using only the memory cache. These
tests went through the cache hub with all the added operations.
putm 9000
---put 9000 in 220 millis ---
enter command:
putm 9000
---put 9000 in 180 millis ---
enter command:
putm 9000
---put 9000 in 220 millis ---
enter command:
putm 9000
---put 9000 in 221 millis ---
enter command:
getm 9000 false
---got 9000 in 40 millis ---
enter command:
getm 9000 false
---got 9000 in 60 millis ---
enter command:
getm 9000 false
---got 9000 in 50 millis ---
enter command:
getm 9000 false
---got 9000 in 50 millis ---
[The configuration
################## JCS CACHE REGIONS AVAILABLE ################### # Regions
preconfirgured for caching jcs.region.testCache1=DC
jcs.region.testCache1.cacheattributes=org.apache.stratum.jcs.engine.Comp
ositeCacheAttributes jcs.region.testCache1.cacheattributes.MaxObjects=20000
jcs.region.testCache1.cacheattributes.MemoryCacheName=org.apache.stratum
.jcs.engine.memory.lru.LRUMemoryCache
]
enter command:
putm 20000
---put 20000 in 761 millis ---
enter command:
getm 20000 false
---got 20000 in 301 millis ---
enter command:
putm 20000
---put 20000 in 781 millis ---
enter command:
getm 20000 false
---got 20000 in 220 millis ---
enter command:
Another configuration (max mem at 1000, all gets shuffling, no getting of
first element, hence all the gets at 2000 are from disk and memory elements
are being replaced)
[configuration
# Regions preconfirgured for caching
jcs.region.testCache1=DC
jcs.region.testCache1.cacheattributes=org.apache.stratum.jcs.engine.Comp
ositeCacheAttributes jcs.region.testCache1.cacheattributes.MaxObjects=1000
jcs.region.testCache1.cacheattributes.MemoryCacheName=org.apache.stratum
.jcs.engine.memory.lru.LRUMemoryCache
]
enter command:
putm 2000
---put 2000 in 621 millis ---
enter command:
getm 2000 false
---got 2000 in 1653 millis ---
enter command:
getm 2000 false
---got 2000 in 1102 millis ---
enter command:
getm 2000 false
---got 2000 in 1172 millis ---
enter command:
getm 2000 false
---got 2000 in 1241 millis ---
enter command:
getm 2000 false
---got 2000 in 1132 millis ---
enter command:
putm 2000
---put 2000 in 170 millis ---
enter command:
putm 2000
---put 2000 in 151 millis ---
enter command:
putm 2000
---put 2000 in 100 millis ---
enter command:
putm 2000
---put 2000 in 40 millis ---
enter command:
getm 2000 false
---got 2000 in 1202 millis ---
enter command:
getm 2000 false
---got 2000 in 1141 millis ---
enter command:
getm 2000 false
---got 2000 in 1242 millis ---
enter command:
"
