0

performance of Tree

asked 2012-09-19 06:50:24 +0800

avidD gravatar image avidD
166 2

Hello,
we are using many trees in our application, some of which have several thousand nodes. In such trees we have serious performance problems because the tree traverses the whole model although only the top node is expanded by default. The desired behavior would be that the tree traverses
* all expanded nodes as their children must be displayed of course
* the children of the "leafs" with respect to expansion state, so expanding a collapsed node with children can at once show the children
* the tree should just ask these non-visible nodes so it can offer an icon for expanding them when they become visible
For example:

+A
| + B
| | + C
| | + D
| |
| + E
|
+F

Assume only the root is expanded, i.e., A and F are visible.
* for performance the tree should already create B and E because the user may expand A
* to be able to properly render B the tree must ask the model whether B is a leaf (no more is needed here)
* C is only built when B becomes visible (btw. I think this should happen asynchronously)

Is this somehow supported by ZK trees or has someone experience doing this?

Thanks beforehand,
David

delete flag offensive retag edit

7 Replies

Sort by ยป oldest newest

answered 2012-09-19 07:35:09 +0800

dliu gravatar image dliu
15

I have a similar problem and I found the solution(more or less):

In org.zkoss.zul.AbstractTreeModel, it is recommended to override "public int[] getPath(E child)".

If you have the path info of your node, you can override the method using the path info instead of blindly doing default deep-first search . In my case, I do get a performance boost after doing so.

Hope it helps.

link publish delete flag offensive edit

answered 2012-09-19 07:48:10 +0800

avidD gravatar image avidD
166 2

Hi dliu,
thanks for the prompt response. However, I think overriding getPath is important for handling of tree changing events, right? In my code getPath(..) is not called at all when building the tree. The problem I have is that while building the tree for the first time the ZK tree traverses all nodes as long as they (correctly) say they are not leafs. But actually, only, say, 10 of 10000 nodes are visible. So there is no point in traversing the whole tree here. Therefore, I believe to optimize this I have to return "wrong" values for isLeaf if the node is not visible in the GUI.

link publish delete flag offensive edit

answered 2012-09-19 08:30:02 +0800

dliu gravatar image dliu
15

Hi avidD,

You are right. I get the problem when tree changes. For your case, you want to optimize for the "visible" nodes and skip those "invisible" nodes' isLeaf() call. Do I understand correctly?

I don't have much idea on this but I think the feature is good to have.

link publish delete flag offensive edit

answered 2012-09-19 15:24:29 +0800

avidD gravatar image avidD
166 2

Hi dlio,
the solution was actually to fool ZK that the tree is smaller than it actually is. I now maintain a set of actually visible nodes and on each OPEN event I mark the node's children as visible, get each child's children from the database, and if it actually has children (is not a leaf) then I fire an INTERVAL_ADDED so ZK can draw the little triangle for expanding it. If a node is not visible, then I tell ZK it were a leaf no matter whether it realy is one. Works like a charm.

Cheers,
David

link publish delete flag offensive edit

answered 2012-09-19 21:23:14 +0800

mgvv gravatar image mgvv
127 2

Hi avidD,

Your solution sounds cool.
Could you provide sample code about your solution?

Thanks,

Miguel Goncalves

link publish delete flag offensive edit

answered 2012-09-20 08:17:26 +0800

avidD gravatar image avidD
166 2

Hi Miguel,
this is my solution

public class SmartNodeTreeModel extends AbstractTreeModel<Node> implements TreeDataListener {
  private final Set<Node> visible = new HashSet<Node>();

  /**
   * Create a new tree model with the given list of resources as the root.
   * @param root the root of the model
   */
  public SmartNodeTreeModel(Node root) {
    super(root);
    this.addTreeDataListener(this);
    visible.add(root);                  // actually, the root is never visible but for correctness we add it
    visible.addAll(root.getChildren()); // these are the only nodes visible when first opening the tree
  }
  
  /**
   * @param node the parent tree node
   * @param index the position of the child, starting at 0
   * @return the child of the given input node at the given position
   */
  @Override
  public Node getChild(Node node, int index) {
    // calling this method if the node is not visible is a bug
    assert( visible.contains(node) );
    return node.getChildren().get(index);
  }

  /**
   * @param node the parent node the number of children of which is requested
   * @return the number of children of the given input node
   */
  @Override
  public int getChildCount(Node node) {
    if ( node == null ) {
      return 0;
    }
    // calling this method if the node is not visible is a bug
    assert( visible.contains(node) );    
    return node.getChildren().size();
  }
    
  @Override
  public boolean isLeaf(Node node) {    
    // pretend the node to be a leaf if it is not  visible, this prunes the iteration when building Treeitems
    return !visible.contains(node) || getChildCount(node) == 0;
  }

  @Override
  public void onChange(TreeDataEvent event) {
    if ( event.getType() != TreeDataEvent.OPEN_CHANGED ) { return; }
    // get the domain object represented by the node
    Node node = getChild(event.getPath()); 
    // fetch its children from the database (children is a lazy property)
    for ( Node child : node.getChildren() ) {
      // if the child is not yet visible somewhere 
      if ( !visible.contains(child) ) {
        // now it is visible
        visible.add(child);
        // if the node has children (these are fetched from the database lazily)
        if ( child.getChildren().size() > 0 ) {
          // for each occurrence (recall, we have a DAG)
          Set<Treeitem> occurrences = ExplorerUtils.getTreeitems(child); // a mapping from domain object to several Treeitems
          for ( Treeitem occurrence : occurrences ) {
            // tell ZK to add the little triangel for expanding it
            // ( this is not actually a change in the data but ZK thought 'child' to be a leaf up to now )
            fireEvent(
                TreeDataEvent.INTERVAL_ADDED, 
                ExplorerUtils.getPath(occurrence), // our getPath method 
                0,
                child.getChildren().size() - 1);
          }
        }
      }
    }
  }    
  ...
}

Cheers,
David

link publish delete flag offensive edit

answered 2012-09-21 08:21:27 +0800

avidD gravatar image avidD
166 2

Hello,
I have now tried optimizing the responsiveness more by fetching the children of the node ( the whole conditional after visible.add(child) ) asynchronously in a worker thread. In this case I get an exception telling that I must fire events only in event listeners. I assume this is a general restriction that cannot be solved? What I am planning to do is to proactively _push_ events to the client. Has anyone made any experiences with such a thing?

Greetings,
David

link publish delete flag offensive edit
Your reply
Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

[hide preview]

Question tools

Follow

RSS

Stats

Asked: 2012-09-19 06:50:24 +0800

Seen: 171 times

Last updated: Sep 21 '12

Support Options
  • Email Support
  • Training
  • Consulting
  • Outsourcing
Learn More