You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Aaron Smuts <AS...@therealm.com> on 2002/01/31 17:20:14 UTC
RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE: [si
mplestore] enhancements (was: [simplestore] inital check in)
> -----Original Message-----
> From: Juozas Baliuka [mailto:baliuka@mwm.lt]
> Sent: Thursday, January 31, 2002 12:23 PM
> To: Jakarta Commons Developers List
> Subject: RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE:
> [simplestore] enhancements (was: [simplestore] inital check in)
>
> <skip>
> >You should try to build it as a memory plugin for JCS. It might require
> >some element attribute additions (what type of reference) if they are
> >useful.
> >
> >The cache hub manages expiration at request time, this could be moved to
> >a background thread. Cleanup of unused items could result in spooling.
>
> Sorry, I can't use any "background cleanup" it has no meaning for memory
> cache.
Sure it does.
> This thread can remove objects from cache, but not from memory, if
> application has strong reference on object.
Yes. It can remove it from the cache.
> "expiration at request time" has no meaning if application has strong
> reference on object.
>
It can be removed from the cache.
> example situation :
> ...............................................
> User u = cache.get(id);
> if( u == null ){
> u = User.create( id );
> cache.put(id,u);
> session.setAttribute("user",u);// I have strong reference here
> team.add(u);
> }
> ..............................................
>
> request.setAttribute("player",u);
>
> ...............................................
>
> Requests, operations , but I don't remove "user" from session
> ..............................................
>
> assertTrue("try to increase sessin time out", session.isValid() );
> // my session is valid at this time.
> // cache must not remove my "user" if GC not decided to do this.
>
> assertEquals("cache doe's not work or bug in GC ",
> session.getAttribute("user"), cache.get(id));
>
> Cache must release unused references, if memory is "low" and must never
> remove object from cache if it used by application.
>
Why? Is it a cached store? It can be removed from the store.
I'm not sure what you are trying to do or why.
Good luck.
> if this test fails I don't need this kind of cache, it can be very fast,
> but not useful.
>
>
>
>
>
>
> >JCS has a memory index of disk items. The performance is better than a
> >B tree, but it takes some memory (around 1.5 Mb for 500,000 items, not
> >much if you ask me.) There are also B tree disk plugins. . . . .
> >
> >
> > >
> > > 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/JDCB
> >o
> > > >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.Com
> >p
> > > >ositeCacheAttributes
> > > >jcs.region.testCache1.cacheattributes.MaxObjects=20000
> > >
> > >jcs.region.testCache1.cacheattributes.MemoryCacheName=org.apache.stratu
> >m
> > > >.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.Com
> >p
> > > >ositeCacheAttributes
> > > >jcs.region.testCache1.cacheattributes.MaxObjects=1000
> > >
> > >jcs.region.testCache1.cacheattributes.MemoryCacheName=org.apache.stratu
> >m
> > > >.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>
> >
> >
> >--
> >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>