commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Aaron Smuts" <aaron.smu...@verizon.net>
Subject RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE: [simplestore] enhancements (was: [simplestore] inital check in)
Date Thu, 31 Jan 2002 14:04:00 GMT


> -----Original Message-----
> From: Paulo Gaspar [mailto:paulo.gaspar@krankikom.de]
> Sent: Thursday, January 31, 2002 6:14 AM
> To: Jakarta Commons Developers List; aaron.smuts3@verizon.net
> Subject: RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE:
> [simplestore] enhancements (was: [simplestore] inital check in)
> 
> That sample is a piece of crap.

Sure is. O(N) performance.

> 
> I use a custom made linked list and my Map entries point to the list
> nodes. This way you get really good performance since you have a
> direct reference to the node you want to remove.
> 

The LRUMemoryCache in JCS is like this.  The memory elements are wrapped
by a descriptor that keeps track of the next and previous.  The double
linked list performance is around O(1).

> In the Sun sample the "mrulist.remove(fname);" call has to iterate
> trough the LinkedList until it finds the right node since "fname"
> is not a reference to the node but a reference to a object being
> held by the node.

It is effectively just a Queue, which is not useful for this aspect of
cache management.

Aaron

> 
> 
> Have fun,
> Paulo Gaspar
> 
> > -----Original Message-----
> > From: Aaron Smuts [mailto:aaron.smuts3@verizon.net]
> > Sent: Thursday, January 31, 2002 6:24 AM
> > To: 'Jakarta Commons Developers List'
> > Subject: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE:
> > [simplestore] enhancements (was: [simplestore] inital check in)
> >
> >
> >
> > 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:
> >


--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message