commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Juozas Baliuka <bali...@mwm.lt>
Subject Re: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE: [simplestore] enhancements (was: [simplestore] inital check in)
Date Thu, 31 Jan 2002 08:37:30 GMT
Hi,
Yes this problem exits at this time, cache  operations are approximately 
liner then we use lists for MRU stuf .
I am going to use SoftMemoryStore without "Swap" in current project , but 
there are more projects and more specific problems. My problems are :
1)I can't lose object from cache if application has strong reference on it.
2)Memory is limited and need to remove object from cache if it is unused 
and "old".
I believe it is possible to implement and have cache performance equivalent 
to map performance.
  it seams SoftMemoryStore memory store solves my problem, but it is not 
well tested and I don't recommend
to use it in production at this time. I will use it on my own risk.

I believe everything can be optimized, and thank you for help.

At 12:23 AM 1/31/2002 -0500, you wrote:

>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>



--
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