You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@myfaces.apache.org by Blake Sullivan <bl...@oracle.com> on 2011/01/19 22:24:36 UTC
[Trinidad][api] Trinidad-2013 TreeModel is extremely inefficient
when dealing with deep tree paths
The JIRA <https://issues.apache.org/jira/browse/TRINIDAD-2013> has the
complete story, but the basic issue is that operations that create keys
representing the ancestors of TreeModel keys can currently only get
those keys by essentially recursively calling
TreeModel.getContainerRowKey(). For list-based keys, this creates
deeply nested subLists. When these keys are used as keys into a
HashMap, the resulting behavior is n^3. For example, adding each of the
keys in a 374 element-deep path to a HashSet resulted in over 800
million calls to ListIterator.next().
The two api parts to the solution are to add another method to TreeModel
that subclasses can override for greater efficiency:
And also allow immutable lists to cache their hash codes with:
/**
* Returns the nth ancestor rowKey or <code>null</code> if no such
ancestor exists.
* This is more efficient than calling
<code>getContainerRowKey(Object)</code>
* on each rowKey in turn.
* <p>
* If generationFromChild is 0, the childRowKey will be returned.
* <p>
* While for backwards compatibility, <code>getAncestorRowKey</code>
is implemented in terms
* of <code>getContainerRowKey</code>, Path-based subclasses should
implement
* <code>getContainerRowKey</code> in terms of
<code>getAncestorRowKey</code> to avoid
* creating deeply nested sublists of keys.
* @param childRowKey
* @param generationFromChild
* @return the nth ancestor rowKey or <code>null</code> if no such
ancestor exists
* @throws NullPointerException if childRowKey is <code>null</code>
* @throws IllegalArgumentException if generationFromChild is less than 0
* @see #getContainerRowKey
*/
public Object getAncestorRowKey(Object childRowKey, int
generationFromChild)
in TreeModel
/**
* Returns a new immutable wrapper list based on an existing list
<code>l</code>.
* <p>
* Once an immutable wrapper has been created on <code>l</code>, neither
* <code>l</code> nor the contents of List <code>l</code> may be changed.
* <p>
* In return for this restriction, the immutable List offers much faster
* implementations of operations such as <code>hashCode</code> and
* <code>subList</code>. This makes the instances returned for use
as keys into
* Sets or Maps, especially since the immutability restrictions are
identical.
* @param l The List to create an immutable wrapper on
* @return A new immutable list on <code>l</code>
* @throws NullPointerException if <code>l</code> is null.
*/
public static <T> List<? extends T> newImmutableList(List<? extends T> l)
in org.apache.myfaces.trinidad.util.CollectionUtils
-- Blake Sullivan
Re: [Trinidad][api] Trinidad-2013 TreeModel is extremely inefficient
when dealing with deep tree paths
Posted by Matthias Wessendorf <ma...@apache.org>.
+1
On Wed, Jan 19, 2011 at 10:24 PM, Blake Sullivan
<bl...@oracle.com> wrote:
> The JIRA has the complete story, but the basic issue is that operations that
> create keys representing the ancestors of TreeModel keys can currently only
> get those keys by essentially recursively calling
> TreeModel.getContainerRowKey(). For list-based keys, this creates deeply
> nested subLists. When these keys are used as keys into a HashMap, the
> resulting behavior is n^3. For example, adding each of the keys in a 374
> element-deep path to a HashSet resulted in over 800 million calls to
> ListIterator.next().
>
> The two api parts to the solution are to add another method to TreeModel
> that subclasses can override for greater efficiency:
>
> And also allow immutable lists to cache their hash codes with:
>
> /**
> * Returns the nth ancestor rowKey or <code>null</code> if no such
> ancestor exists.
> * This is more efficient than calling
> <code>getContainerRowKey(Object)</code>
> * on each rowKey in turn.
> * <p>
> * If generationFromChild is 0, the childRowKey will be returned.
> * <p>
> * While for backwards compatibility, <code>getAncestorRowKey</code> is
> implemented in terms
> * of <code>getContainerRowKey</code>, Path-based subclasses should
> implement
> * <code>getContainerRowKey</code> in terms of
> <code>getAncestorRowKey</code> to avoid
> * creating deeply nested sublists of keys.
> * @param childRowKey
> * @param generationFromChild
> * @return the nth ancestor rowKey or <code>null</code> if no such
> ancestor exists
> * @throws NullPointerException if childRowKey is <code>null</code>
> * @throws IllegalArgumentException if generationFromChild is less than 0
> * @see #getContainerRowKey
> */
> public Object getAncestorRowKey(Object childRowKey, int
> generationFromChild)
>
> in TreeModel
>
>
> /**
> * Returns a new immutable wrapper list based on an existing list
> <code>l</code>.
> * <p>
> * Once an immutable wrapper has been created on <code>l</code>, neither
> * <code>l</code> nor the contents of List <code>l</code> may be changed.
> * <p>
> * In return for this restriction, the immutable List offers much faster
> * implementations of operations such as <code>hashCode</code> and
> * <code>subList</code>. This makes the instances returned for use as
> keys into
> * Sets or Maps, especially since the immutability restrictions are
> identical.
> * @param l The List to create an immutable wrapper on
> * @return A new immutable list on <code>l</code>
> * @throws NullPointerException if <code>l</code> is null.
> */
> public static <T> List<? extends T> newImmutableList(List<? extends T> l)
>
> in org.apache.myfaces.trinidad.util.CollectionUtils
>
> -- Blake Sullivan
>
>
--
Matthias Wessendorf
blog: http://matthiaswessendorf.wordpress.com/
sessions: http://www.slideshare.net/mwessendorf
twitter: http://twitter.com/mwessendorf