Re: [TreeView] Performance of TreeView with huge lists

["Mikkel Kamstrup Erlandsen" <mikkel kamstrup gmail com>]

On 10/02/2008, Thorsten Wilmer <thorsten wilmer udo edu> wrote:
> Hello,
>
> thank you for gtk+ and especially gtkmm.
>
> I want to Display  a really _huge_ List with TreeView. My result is,
> that my application consumes a even more huge amount of memory -- more
> than Virtual Memory is available. The responsiveness is also not as
> expected. I have only a few lines to be displayed, I expect that the
> TreeView does not iterate over the complete tree before showing
> anything, even though the Data are not accessed. It just takes several
> seconds to iterate over 1000000 elements and I don't want to wait for
> 100000000 elements.  I want a fixed_height display and my Model is
> marked as a list. By the way 100000000 elements are only a few Megabytes
> and my Harddisks stores Gigabytes...
>
> I tracked the problem down and found that gtk_tree_view_build_tree
> effectively copies the complete structure of my List. This is a very bad
> idea. My model is able to load the needed data on demand from disk, but
> it is not possible to store the complete list in memory. As only a small
> amount of the data are visible at any given time, the view should only
> load the data to be displayed. And the view shall never use the
> iteratores to iterate over the complete list, if not requested by the
> user. I expect that the user will never see the complete list, though.
>
> Then I thought, why not optimize TreeView? If its known that the Model
> is a list and each element shall have a fixed_height, then it is known
> at any time, what Data are to be displayed. It is possible to map the
> display coordinates to the appropriate item in the model.
>
> The next problem ist, what is to be done with the several masks and
> attributes which are stored in the rb_tree. For my application it is
> sufficient to have a single selection, but it might also be feasible to
> store a selection as a list of selections and deselections done by the
> user. And trying to compact the List after each add, so that if I select
> everything, it just states: selected [0-n] unselected [].
>
> Quite a similar optimization might exist, to represent the collapsed and
> expanded states of the tree. Then you do not need to copy the complete
> structure of the Tree into the private tree and node fields. You can
> calculate the ranges, how to access a complete list in the tree.
>
> I have several questions:
>  - How has this problem been solved by others. Is there an existing
> Gtk-Solution to my Problem?
>  - Is there anybody other than me trying to solve this kind of problem?
>  - What do you suggest:
>  -- write a new simple specialized Widget to ViewHugeLists, which uses
> the TreeViewList or another model (Easy, might not be accepted to be
> integrated into gtk, because TreeView also displays lists)
>  -- change each TreeView function, which uses ->priv->tree or
> ->priv->node if it is a fixed_height list, dynamically recalculate
> everything needed and leave the ->priv->tree ->priv->node as they are
> now. (Hard, might not be accepted to be integrated into gtk, because
> duplicated code and limited to Lists of fixed height)
>  -- rewrite the complete TreeView to get completely rid of tree and node
> and recalculate only the needed information from the compacted current
> state of the tree and the model? (Master, might take a long hard time to
> implement, might become accepted if it works, the external interface is
> not changed and passes the TreeView test). This also works only for Rows
> of fixed_height because to calculate the Maximum rubber position you
> need to know the Height of the complete tree, an if the height of the
> rows differ it is not possible to precalculate the height.
>
> Another problem is, how to evolve the nice existing TreeView into a
> TreeView which takes full advantage of the fixed_height ?
>
> Is it feasible, to Modify each function, to first test if the Flag for
> HugeTree is set, then call the fixed_height counter part or otherwise
> leave the function as it is? The HugeTree optimization can only be
> activated, if it is fixed_height. The fixed_height counter part can
> test,  if the function is already capable to cope with the needed
> functionality. If a not supported function is needed, the optimization
> has to be disabled and the tree has to reinitialize itself or do
> nothing. As the gtk-user has to activate the HugeTree optimization and
> can test if everything needed is already working as expected.
>
> Or is it better to write a HugeTreeView from scratch, using the TreeView
> public interface, which first only handles Lists but can be extended to
> handle HugeTrees later?


I think I would try and tackle this from a different angle. Implement
a custom tree model instead. Don't change the tree view.

Basically create a sliding window model that uses proxy objects for
everything not in the view.

If the rows have fixed height the scrollbars should work as expected.

Does this make sense? I believe I read something similar in a TnyMail
blog entry by Philip van Hoof a good while ago...

Cheers,
Mikkel