myfaces-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jeanne Waldman <>
Subject Re: [Trinidad][api] Trinidad-2013 TreeModel is extremely inefficient when dealing with deep tree paths
Date Wed, 26 Jan 2011 17:51:54 GMT
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<body bgcolor="#ffffff" text="#000000">
Matthias Wessendorf wrote, On 1/19/2011 11:11 PM PT:
  <pre wrap="">+1

On Wed, Jan 19, 2011 at 10:24 PM, Blake Sullivan
<a class="moz-txt-link-rfc2396E" href="">&lt;;</a>
  <blockquote type="cite">
    <pre wrap="">The JIRA has the complete story, but the basic issue is that operations
create keys representing the ancestors of TreeModel keys can currently only
get those keys by essentially recursively calling
TreeModel.getContainerRowKey().&nbsp; For list-based keys, this creates deeply
nested subLists.&nbsp; When these keys are used as keys into a HashMap, the
resulting behavior is n^3.&nbsp; For example, adding each of the keys in a 374
element-deep path to a HashSet resulted in over 800 million calls to

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:

&nbsp; /**
&nbsp;&nbsp; * Returns the nth ancestor rowKey or &lt;code&gt;null&lt;/code&gt;
if no such
ancestor exists.
&nbsp;&nbsp; * This is more efficient than calling
&nbsp;&nbsp; * on each rowKey in turn.
&nbsp;&nbsp; * &lt;p&gt;
&nbsp;&nbsp; * If generationFromChild is 0, the childRowKey will be returned.
&nbsp;&nbsp; * &lt;p&gt;
&nbsp;&nbsp; * While for backwards compatibility, &lt;code&gt;getAncestorRowKey&lt;/code&gt;
implemented in terms
&nbsp;&nbsp; * of &lt;code&gt;getContainerRowKey&lt;/code&gt;, Path-based
subclasses should
&nbsp;&nbsp; * &lt;code&gt;getContainerRowKey&lt;/code&gt; in terms
&lt;code&gt;getAncestorRowKey&lt;/code&gt; to avoid
&nbsp;&nbsp; * creating deeply nested sublists of keys.
&nbsp;&nbsp; * @param childRowKey
&nbsp;&nbsp; * @param generationFromChild
&nbsp;&nbsp; * @return the nth ancestor rowKey or &lt;code&gt;null&lt;/code&gt;
if no such
ancestor exists
&nbsp;&nbsp; * @throws NullPointerException if childRowKey is &lt;code&gt;null&lt;/code&gt;
&nbsp;&nbsp; * @throws IllegalArgumentException if generationFromChild is less than
&nbsp;&nbsp; * @see #getContainerRowKey
&nbsp;&nbsp; */
&nbsp; public Object getAncestorRowKey(Object childRowKey, int

in TreeModel

&nbsp;&nbsp; * Returns a new immutable wrapper list based on an existing list
&nbsp;&nbsp; * &lt;p&gt;
&nbsp;&nbsp; * Once an immutable wrapper has been created on &lt;code&gt;l&lt;/code&gt;,
&nbsp;&nbsp; * &lt;code&gt;l&lt;/code&gt; nor the contents of List
&lt;code&gt;l&lt;/code&gt; may be changed.
&nbsp;&nbsp; * &lt;p&gt;
&nbsp;&nbsp; * In return for this restriction, the immutable List offers much faster
&nbsp;&nbsp; * implementations of operations such as &lt;code&gt;hashCode&lt;/code&gt;
&nbsp;&nbsp; * &lt;code&gt;subList&lt;/code&gt;.&nbsp; This makes
the instances returned for use as
keys into
&nbsp;&nbsp; * Sets or Maps, especially since the immutability restrictions are
&nbsp;&nbsp; * @param l The List to create an immutable wrapper on
&nbsp;&nbsp; * @return A new immutable list on &lt;code&gt;l&lt;/code&gt;
&nbsp;&nbsp; * @throws NullPointerException if &lt;code&gt;l&lt;/code&gt;
is null.
&nbsp;&nbsp; */
&nbsp; public static &lt;T&gt; List&lt;? extends T&gt; newImmutableList(List&lt;?
extends T&gt; l)

in org.apache.myfaces.trinidad.util.CollectionUtils

-- Blake Sullivan

  <pre wrap=""><!---->


View raw message