You said replacing _remove() with a map put?? Would you have intermediate empty nodes? So, if you have /a/b/c/d, what would the Map look like? Just an entry for /a/b/c/d? or entry for /, entry for /a,...etc and finally entry in the map with /a/b/c/d? Speed of removals and additions would certainly depend on this. Without intermediate nodes, they would be O(1), but how would you handle parental locks? You could have had two maps, one only with populated nodes so that you can get O(1) for additions, removals and lookups, and another map with current locking information where all nodes would be present, both intermediate and populated nodes? Galder Zamarreño Sr. Software Maintenance Engineer JBoss, a division of Red Hat -----Original Message----- From: jbosscache-dev-bounces(a)lists.jboss.org [mailto:jbosscache-dev-bounces@lists.jboss.org] On Behalf Of Manik Surtani Sent: 02 February 2007 18:18 To: jbosscache-dev(a)lists.jboss.org Subject: [jbosscache-dev] Optimising node storage in memory Guys, Playing around with looking at how efficient (or not) it is to store nodes as children of other nodes. While this makes logical sense, on an implementation level walking the tree sucks - O(n) where n is the depth of the tree. This works great for small trees, but as depth increases, so does the lookup time. Since all locking happens on the interceptor level (based on a logical Fqn) isn't the tree structure effectively maintained here? What if Node objects weren't directly linked, but maintained in a simple HashMap, keyed on Fqn? Instant constant-time lookups, regardless of tree depth. Sure, it will mean tuning the HashMap for the mem footprint/speed tradeoff, maybe even a custom Map impl tuned for this purpose. And in the initial part the fix should be easy - just replace CacheImpl.peek() with a map lookup, and _remove() and _put() with a map put. Will think about this some more, and post later, but for now I wrote a quick test class that looped through node creation, lookup and deletion through arbitrary depths and these are what the numbers look like. Starting test, with 10000 nodes evenly spread out across the tree. All times in millis. Testing with depth 10 Node Creation 7924 Node Retrieval 1141 Node Deletion 889 Testing with depth 20 Node Creation 16372 Node Retrieval 2072 Node Deletion 1524 Testing with depth 30 Node Creation 31440 Node Retrieval 3010 Node Deletion 2303 Testing with depth 40 Node Creation 52238 Node Retrieval 4172 Node Deletion 3184 Testing with depth 50 Node Creation 80781 Node Retrieval 35788 Node Deletion 34107 Arbitrary depths may not be very useful with current use cases but thinking of scaling to larger and larger grids and dealing with ever larger data volumes, this may be a crucial optimisation. Thoughts and comments? Cheers, Manik FYI, the script to run is tests/scripts/loopFlatteningTest.sh in HEAD. Usage: loopFlatteningTest.sh <space-separated list of depths to test>, e.g., loopFlatteningTest.sh 10 20 30 40 50 -- Manik Surtani Lead, JBoss Cache JBoss, a division of Red Hat Email: manik(a)jboss.org Telephone: +44 7786 702 706 MSN: manik(a)surtani.org Yahoo/AIM/Skype: maniksurtani _______________________________________________ jbosscache-dev mailing list jbosscache-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/jbosscache-dev