Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 39197 invoked from network); 31 Jan 2002 10:58:07 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 31 Jan 2002 10:58:07 -0000 Received: (qmail 3564 invoked by uid 97); 31 Jan 2002 10:58:18 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 3548 invoked by uid 97); 31 Jan 2002 10:58:18 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 3537 invoked from network); 31 Jan 2002 10:58:17 -0000 Reply-To: From: "Paulo Gaspar" To: "Jakarta Commons Developers List" , Subject: RE: Serious problem with MRUMap -- JCS LRU and MRUMap -- RE: [simplestore] enhancements (was: [simplestore] inital check in) Date: Thu, 31 Jan 2002 12:14:29 +0100 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 In-reply-to: <000001c1aa17$7af21620$0100a8c0@realpulse.com> Importance: Normal X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N 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 i such that > * (o==null ? get(i)==null : o.equals(get(i))) (if such an > * element exists). > * > * @param o element to be removed from this list, if present. > * @return true 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: For additional commands, e-mail: