[jira] Commented: (TRINIDAD-2013) TreeModel is extremely inefficient when dealing with deep tree paths

["Matthias Weßendorf (JIRA)" <de...@myfaces.apache.org>]

    [ 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.