Re: [ognl] internal cache performance improvement
Forget about key collision, obviously there is no collisions fro a non-hash functions. On 7 June 2011 02:43, Maurizio Cucchiara mcucchi...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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 mcucchi...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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 hen...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
[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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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
Re: [ognl] internal cache performance improvement
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
Re: [ognl] internal cache performance improvement
2011/6/6 Simone Tripodi simonetrip...@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
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 simonetrip...@apache.orgwrote: 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@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
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 garydgreg...@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 simonetrip...@apache.orgwrote: 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
RE: [ognl] internal cache performance improvement
-Original Message- From: maurizio.cucchi...@gmail.com [mailto:maurizio.cucchi...@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 garydgreg...@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 simonetrip...@apache.orgwrote: 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org -- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- - - - Jason Pyeron PD Inc. http://www.pdinc.us - - Principal Consultant 10 West 24th Street #100- - +1 (443) 269-1555 x333Baltimore, Maryland 21218 - - - -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- This message is copyright PD Inc, subject to license 20080407P00. - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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 jpye...@pdinc.us wrote: -Original Message- From: maurizio.cucchi...@gmail.com [mailto:maurizio.cucchi...@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 garydgreg...@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 simonetrip...@apache.orgwrote: 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [ognl] internal cache performance improvement
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
