Hi Antonio, thanks for reviewing and providing feedbacks! In the existing codebase I don't see any eviction policy, I wonder if that data structure purpose is not for storing large amount of data, but rather just a memory area where quickly looking-up already processed Class related data - I know that could imply OOME but I would see it in action, maybe Struts mates can confirm if they've ever had issues with OGNL's memory. TreeMap sounds reasonable, it's an RB Tree implementation and insert/retrieve operations have both O(log n) complexity[1], I'd suggest to start with it and see how things are going, then switch to LRU if needed. WDYT? Many thanks in advance! Simo
[1] http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf http://people.apache.org/~simonetripodi/ http://www.99soft.org/ On Mon, Jun 6, 2011 at 9:26 AM, Antonio Petrelli <antonio.petre...@gmail.com> wrote: > 2011/6/6 Simone Tripodi <simonetrip...@apache.org> > >> my today's topic is about internal cache, that can be IMHO improved in >> therms of performance; its implementation is a multi-value map alike, >> based on a fixed-size array, a function is applied to each key to >> calculate the array index, each array element is a Collection of >> element. >> Even if getting the list of element related to a general key 'k' has >> complexity of O(1), which is fine, insert/search operations are not >> the best because their complexity is O(m) where m is the size of list >> related to the key. >> > > Pretty naive, i suppose. > > >> Follow below my proposal: there's no need to reinvent the wheel, so >> the array implementation can be replaced with the already provided >> HashMap, where each map value is a simple implementation of balanced >> binary heap (AFAIK commons-collections already provides an >> implementation), that allows us reducing insert/search complexity to >> O(log m). >> > > Probably you are referring to TreeMap, HashMap uses a fixed array with > collisions lists. > The "problem" with TreeMap is that any inserted key must implement > Comparable, or a Comparator must be supported. > Since it is a "cache", wouldn't an LRUMap be more useful? > http://commons.apache.org/collections/api-release/org/apache/commons/collections/map/LRUMap.html > > WDYT? Is is a worth or trivial added value? I know that maybe cache >> dimension is relatively small, but linear search sounds too basic, >> isn't it? >> > > I think you can go on. Surely a Map should be used, the implementation of > that Map could be considered at a later stage. > > Antonio > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
