DO NOT REPLY New: Poor performance in large trees under the SITE tab

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577


           Summary: Poor performance in large trees under
the SITE tab
           Product: Lenya
           Version: Trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Site Management
        AssignedTo: devlenya.apache.org
        ReportedBy: rfrovarpapache.org


There is extremely poor performance under the SITE tab for
large subtrees. The
problem is even worse if the tree is tall instead of wide.
From the best I can
tell (and remember from algorithms) the runtime is O(n^2)
for 6 usecase tests
on that page. And actually each usecase has 2 O(n^2), O(n),
O(n log n). 

What I have found is getPath from
o.a.l.c.s.tree2.TreeNodeImpl runs the
following number of times for the Index node on the site tab
for the following
configurations:

Default: 96
Default + Child: 184
Default + Child + Nephew: 194
Default + Nephew + Child + Grand Child: 500

While investigating this, I have found several areas which
could use
optimization and will document them in this bug.


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #1 from Richard Frovarp <rfrovarpapache.org>  2008-03-11 12:34:54 PST ---
Cache getPath results in r636074. Reduces the number of
calls to 359 from 500.
All of my testing has not been able to generate a problem
using this caching. 


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #2 from Richard Frovarp <rfrovarpapache.org>  2008-03-11 12:40:39 PST ---
In r636076 I made it so that both if checks aren't ran in
the Comparator.
Probably won't help a whole bunch with performance. However,
it is confusing
for the code to run both checks.


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #3 from Richard Frovarp <rfrovarpapache.org>  2008-03-11 12:59:28 PST ---
Provided functionality to retrieve an unordered iterator to
NodeSet in r636082.
This should help out usecases who were previously asking for
all children in
ascending order in getNodesToLock, which has a cost of
O(n^2).


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #4 from Richard Frovarp <rfrovarpapache.org>  2008-03-11 13:34:19 PST ---
Changed getDocuments in NodeSet to now use the unsorted
iterator r636095. API
made no guarantee about order of returned elements and
sorting doesn't appear
to help the function any. 


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #5 from Richard Frovarp <rfrovarpapache.org>  2008-03-11 13:36:14 PST ---
ChangeNodeID called NodeSet.ascending directly. This is the
last usecase from
the sitetab where I have seen the sort being called
unecessarily. r636099


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #6 from Andreas Hartmann <andreasapache.org>  2008-03-19 15:51:51 PST ---
IMO this is a good usecase for AJAX. The JavaScript could
request only the set
of immediately visible children when opening a node.


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org

https://issues.apache.org/bugzilla/show_bug.cgi?id=44577






--- Comment #7 from Richard Frovarp <rfrovarpapache.org>  2008-03-20 10:31:27 PST ---
Well, the problem was for the currently selected node. So I
don't know that
AJAX would help in that regard. However, not testing if the
usecases are
possible for every click in the sitetree would be good. You
did create that
menubar module, which should fix that problem when used.


-- 
Configure bugmail: https://issues.apache.org/bugzilla/userprefs.cgi?tab=e
mail
------- You are receiving this mail because: -------
You are the assignee for the bug.

------------------------------------------------------------
---------
To unsubscribe, e-mail: dev-unsubscribelenya.apache.org
For additional commands, e-mail: dev-helplenya.apache.org