Ideas to manage and clip very large trees (e.g. 100k+ nodes)

[nem0]

I made a simple tree view clipper for large trees, it can be found here https://gist.github.com/nem0/aa343f1c061db651569b5f68900ad63b

It has some downsides, mentioned in the gist.

• while static, performance is perfect and does not depend on number of root nodes
• dynamic (scrolling, collapsing, exapanding), performance is as bad as no clipping
• it only handles root nodes complexity, if there is a node with a lot of children, you are out of luck

[ocornut]

Another idea I recently stumbled upon is the following:

• If we consider the constraint that on any given tree level with "many nodes" (threshold up to app/user, e.g. may be 500) the user is only allowed to open one node at that specific level (aka sibling are automatically closed), then it becomes easier to implement a clipper by doing a little bit of bookkeeping. The constraint doesn't need to apply on level with a smaller number of nodes. And if you think about it it's a fairly reasonable and acceptable constraint since on a very large tree it is difficult to meaningfully open and view multiple siblings at e.g. root level. I'll try to toy with a proof of concept of this idea.

Some other thoughts:

• If your tree nodes have many decorations and extra calls, it is generally beneficial to handle coarse clipping e.g. IsRectVisible() before submitting the multiple-calls per node. I don't think this technique will get you nicely enough to "100k+ nodes" types of trees, but for smaller amount of nodes it is an easy way to reduce cost.

• Using OSX Finder style "one column per level, make new column visible and horizontally scroll then new levels are opened" is a way to completely bypass this problem. With this layout using a clipper becomes trivial. This is essentially a stricter variation of the first idea in my post.

[lyd405121]

Large Tree View Optimization

• Sometimes we will draw a tree to represent a scene
• Most of the time ImGui::TreeNodeEx is the best way to render
• But what if the scene is too large and the rendering performance drop!

Performance Disaster

• Here is the code for demonstration

    //A tree with 30000 leaf to draw
    int nLeafNum = 30000;
    ImGui::Begin("Large Tree");
    if (ImGui::TreeNodeEx("Large Tree"))
    {
        for (int i = 0; i < nLeafNum; i++)
        {
            //the algorithm for rendering 
            //when index  is a multiple of ten 
            //draw red as a key object
            auto strLeafName = std::to_string(i);
            bool bIsKey = i % 10 == 0;
            ImGui::PushID(0);ImGui::PushStyleColor(ImGuiCol_Text, 
            bIsKey?ImVec4(1.0f, 0.0f, 0.0f, 1.0f): ImVec4(0.5f, 0.5f, 0.5f, 0.8f));

            if (ImGui::TreeNodeEx(strLeafName.c_str(), ImGuiTreeNodeFlags_Leaf))
            {
                ImGui::TreePop();
            }
            ImGui::PopStyleColor(1);ImGui::PopID();
        }
        ImGui::TreePop();
    }
    ImGui::End();

• It look like :

• When the tree collapse, the fps drop down from 160 to 30
• So How to Solve this problem?

The magic of ImGui::Dummy

• The idea is to draw the element visible in current window
• ① We can locate the root node by ImGui::GetItemMax()
• ② We can measure size of every node by ImGui::GetItemSize()
• ③ The number we should draw is window size divide size of node
• But if we only draw part of the leaf node, the scroll bar will disappear
• That's not what we want
• So Here Comes the "ImGui::Dummy"
• This api draw an unvisible rect,seems useless
• But relly help in current situation for strench the scroll bar

The optimized code

 int nLeafNum = 30000;
 ImGui::Begin("Large Tree Optimaize");
 if (ImGui::TreeNodeEx("Large Tree"))
 {
     //query window and node info
     ImVec2  vLastItem = ImGui::GetItemRectMax();
     ImVec2  vItemSize = ImGui::GetItemRectSize();
     ImVec2  vWindowPos = ImGui::GetWindowPos();
     ImVec2  vWindowSize = ImGui::GetWindowSize();

    //measure the number of node to draw
     int nLeafStart = max(int((vWindowPos.y - vLastItem.y) / vItemSize.y), 0);
     int nLeafCanDraw = min(int(vWindowSize.y / vItemSize.y), (int)nLeafNum - nLeafStart);

     //blank rect for those node beyond window
     if (nLeafStart > 0 && nLeafCanDraw > 0)
     {
         ImGui::Dummy(ImVec2(10.0f, float(nLeafStart) * vItemSize.y));
     }

    //all the node we could see
     int nDrawLeaf = nLeafStart;
     while (nDrawLeaf < nLeafCanDraw+ nLeafStart && nDrawLeaf < nLeafNum)
     {
         auto strLeafName = std::to_string(nDrawLeaf);
         bool bIsKey = nDrawLeaf % 10 == 0;
         ImGui::PushID(0); ImGui::PushStyleColor(ImGuiCol_Text, bIsKey ? ImVec4(1.0f, 0.0f, 0.0f, 1.0f) : ImVec4(0.5f, 0.5f, 0.5f, 0.8f));
         if (ImGui::TreeNodeEx(strLeafName.c_str(), ImGuiTreeNodeFlags_Leaf))
         {
             ImGui::TreePop();
         }
         ImGui::PopStyleColor(1); ImGui::PopID();
         nDrawLeaf++;
     }

     //blank rect for those node exceed window bottom
     if (nDrawLeaf < nLeafNum)
     {
         ImGui::Dummy(ImVec2(10.0f, float(nLeafNum - nDrawLeaf) * vItemSize.y));
     }
     ImGui::TreePop();
 }
 ImGui::End();

• Here is the result
• The fps is stable 160fps as though the tree never collapse

[ocornut]

Reposting some of the contents you posted to other thread (now deleted):

• as I mentioned - I think you know but this is for others - your usage of std::to_string() contributes for more slowdown than the sum of all TreeNode() calls! In my rough measurement about ~45 ms was TreeNode() cost and 90 ms was std::to_string() cost. What would still be prohibitively too slow but technically three times fast. Also note that comparing FPS is very error-prone and misleading, you should always be comparing time per frame.
• as mentioned by Daniel and me: your method works for a single tree levels. Essentially you could be using ImGuiListClipper to do exactly what you are doing, and it would handle slightly more edge cases, such as some peculiarities of keyboard navigation. It will work ok for tree with many nodes and few levels.
• if you have nested nodes you would need to take account for the fact that some may be open, which would involve using TreeNodeGetOpen() and maybe using the ImGuiListClipper in the special mode where items_count = INT_MAX, aka "unknown until the end of iteration + call `SeekCursorForItem() after end of iteration".

I am currently working a little on this problem and may post further ideas later.

[ocornut]

As part of some research some for multi-select and demos I pushed some improvements with would facilitate some form of clipping.

(1) 8bab3ea, ImGuiListClipper can more explicitly be used with an indeterminate items count, passing items_count=INT_MAX. This enables starting to use the clipper before knowing the items count. At the end of stepping you'll need to call clipper.SeekCursorForItem(items_count) to adjust to items. This is useful if you want to use clipping by fast-forwarding through a non-trivial structure such as a tree.

(2) df38704: i have added a SetNextItemStorageID(ImGuiID storage_id). In various experiment related to tree nodes I realized it was advantageous or necessary to query the open/closed state. The problem is that ID is typically tied to the ID Stack which works with iterating the data but not as easily if you want to randomly get/set the idea as a different point in time. SetNextItemStorageID() is a way to circumvent this issue.

(3) Attached is an experiment to implement clipper by "fast seeking forward" through a tree:
imgui-a483c5d-(WIP) Demo Property Editor with seeking tree clipper (v1).patch
imgui-1e3637c-(WIP) Demo Property Editor with seeking tree clipper (v2).patch

This is a zero-caching method.
The general idea is:

// Use the clipper
// - with indeterminate count (items_count = INT_MAX, and we call SeekCursorForItem() at the end)
DrawCurrentIdx = 0;
DrawClipper.Begin(INT_MAX);

int root_n = 0;
while (DrawClipper.Step())
    while (DrawCurrentIdx < DrawClipper.DisplayEnd && root_n < root_node->Childs.Size)
        DrawTreeNode(root_node->Childs[root_n++]);
while (root_n < root_node->Childs.Size) // keep going to count
    DrawTreeNode(root_node->Childs[root_n++]);

    void DrawTreeNode(ExampleTreeNode* node)
    {
        // (..Filtering...)

        const bool is_visible = (DrawCurrentIdx >= DrawClipper.DisplayStart && DrawCurrentIdx < DrawClipper.DisplayEnd);
        DrawCurrentIdx++;

        if (is_visible)
        {
            ImGui::SetNextItemStorageID((ImGuiID)node->UID); // use node->UID as storage id
            //... various decorations
            bool node_open = ImGui::TreeNodeEx(node->Name, tree_flags);
            //... various decorations
            if (node_open)
            {
                for (ExampleTreeNode* child : node->Childs)
                    DrawTreeNode(child);
                ImGui::TreePop();
            }
        }
        else if (node->Childs.Size > 0)
        {
            // Clipped
            if (ImGui::GetStateStorage()->GetInt(node->UID) != 0) // are we open?
            {
                ImGui::TreePush(node->Name);
                for (ExampleTreeNode* child : node->Childs)
                    DrawTreeNode(child);
                ImGui::TreePop();
            }
        }
    }

The wins comes from the fact:

• When outside of view we only do a storage query (ImGui::GetStateStorage()->GetInt(node->UID)) instead of full on TreeNode() which has more overhead.
• We can generally skip any styling, extraneous decoration, layout/tables detailes

With this method, in the Property Editor tree with 18000 root items:

• MSVC X64 Debug : 26 ms down to 2.5 ms
• MSVC X86 Release : 2 ms down to 0.1 ms

Again this is a zero-caching method. It's always more efficient if you can linearize your tree by creating an index, but then you need to have an event to notify of tree changes to rebuild the index. It also happens that to implement any form of non-trivial search you will want to have this index anyhow, at which point you can implement something that's much faster.
This is why this is not committed in demo: I think it's nicer to bite the bullet and build the after-filter-index that a real/advanced application will use anyhow. I'll work on that.

(4) In ce3a8d7 I have pushed a demo to implement multi-select (with shift-selection, mouse drag selection) in a tree.
It's quite non trivial because of the same reason: lack of an index.
One interesting aspect of it is the helper function TreeGetNextNodeInVisibleOrder() with gets the next sibling or child or parent in linear order and accounting for open/close state. This also uses SetNextItemStorageID().
It also implement a feature where when closing a close, it automatically close and unselect its child nodes, and select parent node if any child node was previously selected.

---

TL;DR; both (3) and (4) will be superseded by the use of an index. Working on that soon.