[
https://issues.apache.org/jira/browse/TRINIDAD-2013?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12986932#action_12986932
]
Matthias Weßendorf commented on TRINIDAD-2013:
----------------------------------------------
+1 on this fix
> TreeModel is extremely inefficient when dealing with deep tree paths
> --------------------------------------------------------------------
>
> Key: TRINIDAD-2013
> URL: https://issues.apache.org/jira/browse/TRINIDAD-2013
> Project: MyFaces Trinidad
> Issue Type: Improvement
> Affects Versions: 1.2.12-core, 2.0.0-alpha-2
> Reporter: Blake Sullivan
> Assignee: Blake Sullivan
> Priority: Minor
> Original Estimate: 48h
> Remaining Estimate: 48h
>
> Given the tree path to a node in a TreeModel, there is no mechanism for
> retrieving efficient tree path implementations for each of the ancestor
> nodes. This is because the only way of retrieving an ancestor node is to
> call TreeModel.getContainerRowKey(Object path) to retrieve each ancestor key
> and then pass the returned key in to retrieve its ancestor, etc.
> For efficiency, List-based keys (which are essentially all of the keys),
> return a subList(), trimming off the end element. As the initial lists get
> longer, the nest subLists become deeper as well. Even worse is when one
> these keys is used as a key into a Set or Map since the defined
> implementation of hashCode on a List is to hash each of the elements. As a
> result, the following test code called next() on the ListIterator 800 million
> times when passed a 374 element path:
> private static boolean _testN3Sublist(List<?> testList)
> {
> Set<?> expanded = new HashSet();
>
> List<?> currKey = testList;
>
> do
> {
> boolean parentExpanded = expanded.contains(currKey);
> parentExpanded = expanded.contains(currKey);
>
> if (!parentExpanded)
> {
> int newSize = currKey.size() - 1;
>
> if (newSize == 0)
> return false;
>
> currKey = currKey.subList(0, newSize);
> }
> else
> {
> break;
> }
> } while (true);
>
> return true;
> }
> There are four parts to the solution:
> 1) Add
> /**
> * 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)
> {
> if (generationFromChild < 0)
> throw new IllegalArgumentException();
>
> while (generationFromChild >= 0)
> {
> childRowKey = getContainerRowKey(childRowKey);
>
> generationFromChild--;
>
> if (childRowKey == null)
> break;
> }
>
> return childRowKey;
> }
> 2) Change List-based TreeModel subclasses to override
> public Object getAncestorRowKey(Object childRowKey, int generationFromChild)
> With an implementation providing exactly the needed subList
> 3) Change code that iterates up the keys to pass in the generation of the
> List that they want. This avoids any nesting of subLists
> 4) In many cases, the resulting Lists are immutable, so add the following api
> to allow TreeModel implementations to speed up the hashCode calculation as
> well:
> /**
> * 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)
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
