commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [ognl] internal cache performance improvement
Date Mon, 06 Jun 2011 13:55:51 GMT
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.petrelli@gmail.com> wrote:
> 2011/6/6 Simone Tripodi <simonetripodi@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message