You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Simone Tripodi <si...@apache.org> on 2011/06/06 08:36:30 UTC
[ognl] internal cache performance improvement
Hi all OGNL folks,
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.
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).
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?
Looking forward to your feedbacks, have a nice day,
Simo
http://people.apache.org/~simonetripodi/
http://www.99soft.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Maurizio Cucchiara <mc...@apache.org>.
Forget about key collision, obviously there is no collisions fro a
non-hash functions.
On 7 June 2011 02:43, Maurizio Cucchiara <mc...@apache.org> wrote:
> Simone,
>
>> a look at put( Class<?> key, T value )[1] implementation of
>
> Aside that put method is public, IIUC the only class that calls "put"
> is only the OgnlRuntime one (and almost every time it invokes inside
> a sync block).
>
>> ClassCacheImpl: the whole block should be controlled by a concurrency
>> policy, not only the access to the data structure... WDYT?
>> The main reason of proposing a TreeMap instead of an LRU cache is
>> that, in the curent implementation, for each key there could be more
>> than one value, keeping the multiple values in a kind of inefficient
>> linked list, that makes inserts/searches inefficient with complexity
>> of O(n), with TreeMap we can decrease it to O(log n).
>
> I'm not sure understand what you mean, how do you think to handle the
> key collisions (not even TreeMap supports duplicate keys)?
> At least an HashMap implementation (et similia) can guarantee a lower
> complexity than TreeMap (unless the order is not important), or am I
> missing something?
>
> I supposed that the new map implementation will replace the _table
> array, please correct me if I'm wrong.
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Maurizio Cucchiara <mc...@apache.org>.
Simone,
> a look at put( Class<?> key, T value )[1] implementation of
Aside that put method is public, IIUC the only class that calls "put"
is only the OgnlRuntime one (and almost every time it invokes inside
a sync block).
> ClassCacheImpl: the whole block should be controlled by a concurrency
> policy, not only the access to the data structure... WDYT?
> The main reason of proposing a TreeMap instead of an LRU cache is
> that, in the curent implementation, for each key there could be more
> than one value, keeping the multiple values in a kind of inefficient
> linked list, that makes inserts/searches inefficient with complexity
> of O(n), with TreeMap we can decrease it to O(log n).
I'm not sure understand what you mean, how do you think to handle the
key collisions (not even TreeMap supports duplicate keys)?
At least an HashMap implementation (et similia) can guarantee a lower
complexity than TreeMap (unless the order is not important), or am I
missing something?
I supposed that the new map implementation will replace the _table
array, please correct me if I'm wrong.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Simone Tripodi <si...@apache.org>.
Salut Henri!!!
thanks a lot for your contribution!!! your suggestiona are indeed
really useful and having a look at the packages you pointed is a big
worth, thanks!!!
Anyway, everybody feels comfortable on working on the cache is
welcome, I'll fill an issue about it soit will be tracked, feel free
to assign to yourself and work on it!
Have a nice day, all the best!!!
Simo
http://people.apache.org/~simonetripodi/
http://www.99soft.org/
On Tue, Jun 7, 2011 at 10:43 AM, henrib <he...@apache.org> wrote:
> Hi Simo;
> You might want to take a look at jexl in the
> org.apache.commons.jexl2.internal.introspection and
> org.apache.commons.jexl2.internal packages for ideas, more specifically at
> IntrospectorBase.
>
> Jexl caching is roughly a hashmap keyed by classes whose values are
> (essentially) hashmap keyed on method signatures pointing to methods. Cache
> access is synchronized and the whole cache is soft-refed so it can be
> evicted on memory pressure (or class loader change).
> To further reduce contention, the jexl interpreter caches method references
> in AST nodes through a volatile member; after the first execution, the
> script/statement retries to call the cached method. It will only go back to
> the class cache if the call is unsuccessful.
>
> At a higher level but I'm not sure it is practical, the
> org.apache.commons.jexl2.introspection package could be (re)used; it
> abstracts the whole introspection parts caching included.
>
> Hope this can help,
> Cheers
> Henrib
>
> --
> View this message in context: http://apache-commons.680414.n4.nabble.com/ognl-internal-cache-performance-improvement-tp3576227p3578976.html
> Sent from the Commons - Dev mailing list archive at Nabble.com.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Simone Tripodi <si...@apache.org>.
Hi Mau,
fine having such tests and fine you added the shade in a profile so it
doesn't collide with the normal build process, but let's discuss about
different topics in separate threads ;)
Anyway, good job!
All the best,
Simo
http://people.apache.org/~simonetripodi/
http://www.99soft.org/
On Tue, Jun 7, 2011 at 6:30 PM, Maurizio Cucchiara
<mc...@apache.org> wrote:
> Hi, guys.
> I set-up the shade plugin inside the OGNL pom [1], which allows us to
> do some performance test on S2.
>
> WDYT?
>
> [1] https://issues.apache.org/jira/browse/OGNL-16
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Maurizio Cucchiara <mc...@apache.org>.
Hi, guys.
I set-up the shade plugin inside the OGNL pom [1], which allows us to
do some performance test on S2.
WDYT?
[1] https://issues.apache.org/jira/browse/OGNL-16
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by henrib <he...@apache.org>.
Hi Simo;
You might want to take a look at jexl in the
org.apache.commons.jexl2.internal.introspection and
org.apache.commons.jexl2.internal packages for ideas, more specifically at
IntrospectorBase.
Jexl caching is roughly a hashmap keyed by classes whose values are
(essentially) hashmap keyed on method signatures pointing to methods. Cache
access is synchronized and the whole cache is soft-refed so it can be
evicted on memory pressure (or class loader change).
To further reduce contention, the jexl interpreter caches method references
in AST nodes through a volatile member; after the first execution, the
script/statement retries to call the cached method. It will only go back to
the class cache if the call is unsuccessful.
At a higher level but I'm not sure it is practical, the
org.apache.commons.jexl2.introspection package could be (re)used; it
abstracts the whole introspection parts caching included.
Hope this can help,
Cheers
Henrib
--
View this message in context: http://apache-commons.680414.n4.nabble.com/ognl-internal-cache-performance-improvement-tp3576227p3578976.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Simone Tripodi <si...@apache.org>.
Great to see all that participation guys!!! And welcome to Jason between us!
Concurrency is indeed yet another key feature for internal store/cache
but IMHO a synchronized/concurrent data structure is not enough, take
a look at put( Class<?> key, T value )[1] implementation of
ClassCacheImpl: the whole block should be controlled by a concurrency
policy, not only the access to the data structure... WDYT?
The main reason of proposing a TreeMap instead of an LRU cache is
that, in the curent implementation, for each key there could be more
than one value, keeping the multiple values in a kind of inefficient
linked list, that makes inserts/searches inefficient with complexity
of O(n), with TreeMap we can decrease it to O(log n).
Anyway I'm open to suggestions the main focus is we have to improve
the cache performances, supporting concurrency :)
Thanks for your feedback, have a nice day!!!
Simo
[1] http://tinyurl.com/3qm9d7u
http://people.apache.org/~simonetripodi/
http://www.99soft.org/
On Mon, Jun 6, 2011 at 6:46 PM, Maurizio Cucchiara
<mc...@apache.org> wrote:
> Jason, you're right there is one OGNL context per request in struts,
> but at the time that the OGNL code was written, concurrency was taken
> into account, so at this point I think we don't have other choice
> (there could be other projects that rely on the OGNL thread-safety).
>
> On 6 June 2011 18:24, Jason Pyeron <jp...@pdinc.us> wrote:
>>> -----Original Message-----
>>> From: maurizio.cucchiara@gmail.com
>>> [mailto:maurizio.cucchiara@gmail.com] On Behalf Of Maurizio Cucchiara
>>> Sent: Monday, June 06, 2011 12:14
>>> To: Commons Developers List
>>> Subject: Re: [ognl] internal cache performance improvement
>>>
>>> Gary hit the nail on the head, considering that OGNL usually
>>> runs in a multi-thread environment like struts, concurrency is a must.
>>
>> While struts2 is multi-threaded access to a given value stack should be in a
>> single thread, unless explicitly threaded by custom code of the OP.
>>
>>> At first glance LRUMap would seem the appropriate choice (it
>>> was thought for this purpose), unfortunately LRUMap is not
>>> thread safe, surely we can wrap using
>>> Collections#synchronizedMap, but it will always a bottlenecks.
>>>
>>> On the other hand ConcurrentHashMap seems the appropriate
>>> choice (Currently the synchronized keyword has 18 match
>>> inside the OgnlRuntime class).
>>>
>>> We could eventually consider to allow the user to decide
>>> which implementation to choose.
>>>
>>> Since I have many complex struts application in production, I
>>> can do a little test.
>>>
>>>
>>>
>>> On 6 June 2011 16:55, Gary Gregory <ga...@gmail.com> wrote:
>>> > Does concurrency need to be taken into account for the
>>> cache? If so,
>>> > you need to consider how access to the cache will be
>>> synchronized. An
>>> > intrinsic lock? A ConcurrentHashMap? and so on.
>>> >
>>> > Gary
>>> >
>>> > On Mon, Jun 6, 2011 at 2:36 AM, Simone Tripodi
>>> <si...@apache.org>wrote:
>>> >
>>> >> Hi all OGNL folks,
>>> >> 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.
>>> >> 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).
>>> >> 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?
>>> >> Looking forward to your feedbacks, have a nice day, Simo
>>> >>
>>> >> http://people.apache.org/~simonetripodi/
>>> >> http://www.99soft.org/
>>> >>
>>> >>
>>> ---------------------------------------------------------------------
>>> >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> >> For additional commands, e-mail: dev-help@commons.apache.org
>>> >>
>>> >>
>>> >
>>> >
>>> > --
>>> > Thank you,
>>> > Gary
>>> >
>>> > http://garygregory.wordpress.com/
>>> > http://garygregory.com/
>>> > http://people.apache.org/~ggregory/
>>> > http://twitter.com/GaryGregory
>>> >
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>
>>
>>
>> --
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>> - -
>> - Jason Pyeron PD Inc. http://www.pdinc.us -
>> - Principal Consultant 10 West 24th Street #100 -
>> - +1 (443) 269-1555 x333 Baltimore, Maryland 21218 -
>> - -
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>> This message is copyright PD Inc, subject to license 20080407P00.
>>
>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Maurizio Cucchiara <mc...@apache.org>.
Jason, you're right there is one OGNL context per request in struts,
but at the time that the OGNL code was written, concurrency was taken
into account, so at this point I think we don't have other choice
(there could be other projects that rely on the OGNL thread-safety).
On 6 June 2011 18:24, Jason Pyeron <jp...@pdinc.us> wrote:
>> -----Original Message-----
>> From: maurizio.cucchiara@gmail.com
>> [mailto:maurizio.cucchiara@gmail.com] On Behalf Of Maurizio Cucchiara
>> Sent: Monday, June 06, 2011 12:14
>> To: Commons Developers List
>> Subject: Re: [ognl] internal cache performance improvement
>>
>> Gary hit the nail on the head, considering that OGNL usually
>> runs in a multi-thread environment like struts, concurrency is a must.
>
> While struts2 is multi-threaded access to a given value stack should be in a
> single thread, unless explicitly threaded by custom code of the OP.
>
>> At first glance LRUMap would seem the appropriate choice (it
>> was thought for this purpose), unfortunately LRUMap is not
>> thread safe, surely we can wrap using
>> Collections#synchronizedMap, but it will always a bottlenecks.
>>
>> On the other hand ConcurrentHashMap seems the appropriate
>> choice (Currently the synchronized keyword has 18 match
>> inside the OgnlRuntime class).
>>
>> We could eventually consider to allow the user to decide
>> which implementation to choose.
>>
>> Since I have many complex struts application in production, I
>> can do a little test.
>>
>>
>>
>> On 6 June 2011 16:55, Gary Gregory <ga...@gmail.com> wrote:
>> > Does concurrency need to be taken into account for the
>> cache? If so,
>> > you need to consider how access to the cache will be
>> synchronized. An
>> > intrinsic lock? A ConcurrentHashMap? and so on.
>> >
>> > Gary
>> >
>> > On Mon, Jun 6, 2011 at 2:36 AM, Simone Tripodi
>> <si...@apache.org>wrote:
>> >
>> >> Hi all OGNL folks,
>> >> 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.
>> >> 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).
>> >> 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?
>> >> Looking forward to your feedbacks, have a nice day, Simo
>> >>
>> >> http://people.apache.org/~simonetripodi/
>> >> http://www.99soft.org/
>> >>
>> >>
>> ---------------------------------------------------------------------
>> >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> >> For additional commands, e-mail: dev-help@commons.apache.org
>> >>
>> >>
>> >
>> >
>> > --
>> > Thank you,
>> > Gary
>> >
>> > http://garygregory.wordpress.com/
>> > http://garygregory.com/
>> > http://people.apache.org/~ggregory/
>> > http://twitter.com/GaryGregory
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>
>
>
> --
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> - -
> - Jason Pyeron PD Inc. http://www.pdinc.us -
> - Principal Consultant 10 West 24th Street #100 -
> - +1 (443) 269-1555 x333 Baltimore, Maryland 21218 -
> - -
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> This message is copyright PD Inc, subject to license 20080407P00.
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
RE: [ognl] internal cache performance improvement
Posted by Jason Pyeron <jp...@pdinc.us>.
> -----Original Message-----
> From: maurizio.cucchiara@gmail.com
> [mailto:maurizio.cucchiara@gmail.com] On Behalf Of Maurizio Cucchiara
> Sent: Monday, June 06, 2011 12:14
> To: Commons Developers List
> Subject: Re: [ognl] internal cache performance improvement
>
> Gary hit the nail on the head, considering that OGNL usually
> runs in a multi-thread environment like struts, concurrency is a must.
While struts2 is multi-threaded access to a given value stack should be in a
single thread, unless explicitly threaded by custom code of the OP.
> At first glance LRUMap would seem the appropriate choice (it
> was thought for this purpose), unfortunately LRUMap is not
> thread safe, surely we can wrap using
> Collections#synchronizedMap, but it will always a bottlenecks.
>
> On the other hand ConcurrentHashMap seems the appropriate
> choice (Currently the synchronized keyword has 18 match
> inside the OgnlRuntime class).
>
> We could eventually consider to allow the user to decide
> which implementation to choose.
>
> Since I have many complex struts application in production, I
> can do a little test.
>
>
>
> On 6 June 2011 16:55, Gary Gregory <ga...@gmail.com> wrote:
> > Does concurrency need to be taken into account for the
> cache? If so,
> > you need to consider how access to the cache will be
> synchronized. An
> > intrinsic lock? A ConcurrentHashMap? and so on.
> >
> > Gary
> >
> > On Mon, Jun 6, 2011 at 2:36 AM, Simone Tripodi
> <si...@apache.org>wrote:
> >
> >> Hi all OGNL folks,
> >> 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.
> >> 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).
> >> 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?
> >> Looking forward to your feedbacks, have a nice day, Simo
> >>
> >> http://people.apache.org/~simonetripodi/
> >> http://www.99soft.org/
> >>
> >>
> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> >> For additional commands, e-mail: dev-help@commons.apache.org
> >>
> >>
> >
> >
> > --
> > Thank you,
> > Gary
> >
> > http://garygregory.wordpress.com/
> > http://garygregory.com/
> > http://people.apache.org/~ggregory/
> > http://twitter.com/GaryGregory
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
--
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
- -
- Jason Pyeron PD Inc. http://www.pdinc.us -
- Principal Consultant 10 West 24th Street #100 -
- +1 (443) 269-1555 x333 Baltimore, Maryland 21218 -
- -
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
This message is copyright PD Inc, subject to license 20080407P00.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Maurizio Cucchiara <mc...@apache.org>.
Gary hit the nail on the head, considering that OGNL usually runs in a
multi-thread environment like struts, concurrency is a must.
At first glance LRUMap would seem the appropriate choice (it was
thought for this purpose), unfortunately LRUMap is not thread safe,
surely we can wrap using Collections#synchronizedMap, but it will
always a bottlenecks.
On the other hand ConcurrentHashMap seems the appropriate choice
(Currently the synchronized keyword has 18 match inside the
OgnlRuntime class).
We could eventually consider to allow the user to decide which
implementation to choose.
Since I have many complex struts application in production, I can do a
little test.
On 6 June 2011 16:55, Gary Gregory <ga...@gmail.com> wrote:
> Does concurrency need to be taken into account for the cache? If so, you
> need to consider how access to the cache will be synchronized. An intrinsic
> lock? A ConcurrentHashMap? and so on.
>
> Gary
>
> On Mon, Jun 6, 2011 at 2:36 AM, Simone Tripodi <si...@apache.org>wrote:
>
>> Hi all OGNL folks,
>> 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.
>> 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).
>> 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?
>> Looking forward to your feedbacks, have a nice day,
>> Simo
>>
>> http://people.apache.org/~simonetripodi/
>> http://www.99soft.org/
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> --
> Thank you,
> Gary
>
> http://garygregory.wordpress.com/
> http://garygregory.com/
> http://people.apache.org/~ggregory/
> http://twitter.com/GaryGregory
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [ognl] internal cache performance improvement
Posted by Gary Gregory <ga...@gmail.com>.
Does concurrency need to be taken into account for the cache? If so, you
need to consider how access to the cache will be synchronized. An intrinsic
lock? A ConcurrentHashMap? and so on.
Gary
On Mon, Jun 6, 2011 at 2:36 AM, Simone Tripodi <si...@apache.org>wrote:
> Hi all OGNL folks,
> 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.
> 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).
> 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?
> Looking forward to your feedbacks, have a nice day,
> Simo
>
> http://people.apache.org/~simonetripodi/
> http://www.99soft.org/
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
--
Thank you,
Gary
http://garygregory.wordpress.com/
http://garygregory.com/
http://people.apache.org/~ggregory/
http://twitter.com/GaryGregory
Re: [ognl] internal cache performance improvement
Posted by Antonio Petrelli <an...@gmail.com>.
2011/6/6 Simone Tripodi <si...@apache.org>
> 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!
>
+1, TreeMap is fine for now.
Antonio
Re: [ognl] internal cache performance improvement
Posted by Simone Tripodi <si...@apache.org>.
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
<an...@gmail.com> wrote:
> 2011/6/6 Simone Tripodi <si...@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
Re: [ognl] internal cache performance improvement
Posted by Antonio Petrelli <an...@gmail.com>.
2011/6/6 Simone Tripodi <si...@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