commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Paulo Gaspar" <paulo.gas...@krankikom.de>
Subject RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE: [simplestore] enhancements (was: [simplestore] inital check in)
Date Thu, 31 Jan 2002 11:14:29 GMT
That sample is a piece of crap.

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.

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.


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