Menu
▾
▴
#231 smarter updating of ttk::treeview display
I propose some combination of visible set determination, a better search structure, and throttled GUI updates be implemented for a reasonable balance between keeping the GUI responsive and inserting a large data set into a ttk::treeview widget (and perhaps other data display widgets).
The cost of updating the display for a ttk::treeview appears to be proportional to the number of non-detached items. This is a problem if you want to load a large data set (hundreds of thousands or millions of items) and start seeing things right away. Maybe the treeview is not designed for this purpose, but I didn't find the multicolumn widget that is. So far I have found the following options, all at least somewhat unsatisfactory:
1. Don't update. This gets everything inserted in the minimum amount of time, but locking up the GUI for several seconds is not really acceptable.
2. Update after every insertion. This keeps the GUI responsive but it takes orders of magnitude too long to insert all the items, even for a very moderate number of items (tens of thousands).
3. Update only after some time elapsed or number of insertions, or some adaptive scheme involving both. A huge improvement over (2) but still way too slow for large data sets. Also, I don't think "post redisplay" is something I should have to implement myself.
4. Insert everything as a child of a detached item and make them the children of {} only at the very end. The GUI remains responsive and the insertions complete in a reasonable amount of time as long as you implement (3), but nothing is displayed until all the items are inserted.
5. Insert and update normally until the visible area is full and then switch to (4). But what if the user changes the viewport before everything is inserted?
If we could maintain the visible set of items and insert items and compute their geometry without actually realizing them, then updates could basically take constant time as long as the viewport remains constant. If we maintained better search structures, then inserting at arbitrary locations and viewport changes could be handled nicely as well. That would also address the (undocumented?) quadratic running time of inserting all items at the end. And if GUI updates were throttled in general then I maybe would simply be able to use plain old update instead of workaround (3)?
The ttk::treeview widget already defers redisplay until idle time (like all Tk widgets); the cost of populating the tree is unrelated to refresh time.
The pathological quadratic runtime behavior has also been fixed in Tk 8.5.9 (and in 8.6 if and when that is released). Populating the tree in depth-first or breadth-first order using [$tv insert .. end] now takes (near-) linear time.
If you are unable to upgrade to 8.5.9, a workaround is to create all children in reverse order -- [$tv insert $parent 0 ...] is constant-time -- then reverse the order when finished:
$tv children $parent [lreverse [$tv children $parent]]
You're right about the quadratic insertion being fixed in 8.5.9; I hadn't tested that part of my comment with 8.5.9. That wasn't really my main complaint, since the workaround was pretty obvious (though annoying) once I figured out the cause of the quadratic behavior.
About the idle redisplay thing though, perhaps I haven't made myself clear. The easiest way to understand what I'm talking about is to make a treeview and try inserting a few million items, text 1..10000000 for example, and time it. It will take a few seconds, during which the GUI will not respond. Now try to figure out a way of keeping the GUI responsive while the items are inserted. I added a progressbar with autoincrement to see visually how responsive I was keeping the GUI. I couldn't figure any way to keep the GUI responsive without drastically increasing the time to the last insertion without the use of methods (3) and (4), which still didn't resolve the issue of scrolling or resizing.
I agree that the cost of insertion alone is not dependent on the size of the tree. Indeed, if you simply insert everything without ever calling update, then the insertion time is unrelated to the display time. That was what I described in option (1) of my initial comment. However, if you are inserting literally millions of items (and possibly doing other things), it will take several seconds to complete, even if you never call update. If you don't call update, you never get idle time, and the GUI doesn't respond. So I call update once in a while, but the number of times I need to redraw increases with how long it takes to populate and periodically redraw the tree, and the cost of each redraw increases with the size of the tree. So even though the cost of insertion itself is unrelated to the size of the tree, the cost of keeping the GUI updated while inserting grows very rapidly with the size of the tree. That was my main complaint, and it has *not* been addressed by 8.5.9.
So I think my original main points are in fact still valid. The main point is that you should be able to easily keep the GUI responsive during long insertion tasks without causing the total time to completion to be drastically longer. And what I proposed as parts of the solution are:
1. The GUI should not be unconditionally redrawn after every idle time. That is far too often under most circumstances and drives the cost of update far higher than it needs to be. That is what I meant by "throttling" GUI updates. I think this is an issue with Tk in general, not just the treeview widget, except that it exacerbated by...
2. The cost of drawing something should depend on what is visible, not the total size of the underlying model. If I can only only see 10 rows, then I should only have to pay for drawing 10 rows each idle cycle. It shouldn't matter on the Tcl programmer's side whether there are 10 items or 10 million. That is what I meant by "visible set determination" and "better search structures".