[TreeView] Performance of TreeView with huge lists

[Thorsten Wilmer <thorsten wilmer udo edu>]

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?


What is the preferred solution?

Thanks for your comments!

Have nice Day,
  Thorsten