commons-dev mailing list archives

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

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:

Mime
View raw message