commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Antonio Petrelli <antonio.petre...@gmail.com>
Subject Re: [ognl] internal cache performance improvement
Date Mon, 06 Jun 2011 07:26:59 GMT
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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message