Re: rethinking GtkTreeModelSort

[Havoc Pennington <hp redhat com>]

jrb redhat com writes: 
> The problem is that it's done at the model level, while it's really a
> view issue, and the benefits of Model/View are lost.  The main reason it
> is done this way is so that you can have multiple views of the same
> model, each sorted differently.  As an example, consider a
> filemanager.  We could have one model of the filesystem for everything.
> If we have a list view in each pane, we save memory by only resorting it
> versus having a new model for each.

Right, I wasn't thinking about this. That does seem to require
TreeModelSort, or equivalent. (i.e. a bunch of models which are
themselves views onto some more basic model. This could be done with
custom code, e.g. a custom filesystem model represented by
GtkTreeModels that do the sorting, but perhaps painful. And of course
you need TreeModelSort to handle the built-in ListStore and
TreeStore.)

> I'm a little confused, Havoc.  How's it inefficient.  Speed?  Space?  In
> terms of speed, it's pretty darn fast.

It's fairly fast in the persist case - which eliminates the most
efficient possible custom model, an array model. And the overhead in
the persist case isn't unreasonable, but neither is it invisible.

I wasn't considering multiple views though; yes that's a problem.

>  In terms of space it requires 32
> bytes per visible node (on IA32), though 8 of them could be cut down if
> we decide to remove some unused pointers from GtkTreeIter (probably a
> good idea.)  Not exactly trivial, but certainly a space-saver when
> considring multiple models (see below).

The version in CVS looks a lot bigger than that to me... GtkTreeIter
itself is 128 bytes, no?

>   Also, why is the ITERS_PERSIST
> flag cheesy?  It's a performance saver, but GtkTreeModelSort should work
> without it set (albeit less efficiently.)

Sufficiently less efficiently to be near-useless, right, otherwise we
wouldn't have added that flag. ;-)
 
I think the flag is bad because it changes semantics substantially
depending on what kind of model you have, when iterator semantics are
already confusing, and after confusing iterator semantics it makes it
hard for us to warn about misuse of iterators. So it's pretty
suboptimal from that standpoint, IMHO.

Misusing iterators is quite easy, at least it is with the text
widget. Once you start having signals and stuff, I've done it quite a
few times just implementing the text widget itself.
 
> I started working on a convenience function in gtktreemodelsort to do
> this kind of thing.  Something like:
> 
> static void
> gtk_tree_view_set_sort_column (GtkSortView       *sort_view,
>                                GtkTreeViewColumn *column,
>                                GtkTreeModelSort  *sort,
>                                GValueCompareFunc  func);
> 
> Etc...
> 

Perhaps adding a set_sort_column method to the model is a bit nicer;
even with TreeModelSort, the way we do sorting is to have one model
per view. TreeModelSort just makes it easy to have a bunch of models
that differ only in their sort, sharing a common model as the backend.
So sort column _is_ fundamentally a property of a single model. If it
wasn't, you would need to pass a "view" argument to all the model
methods, and get different order of iteration per-view. As it is, for
a single model, there is only one ordering.

In principle you could have a model that shared the sort column
between views, or you could have a bunch of custom GtkTreeModel that
acted as views onto some application-specific child model. i.e. a sort
model that chained to something other than another GtkTreeModel.



Ugh, confusing. 

Let's see: the summary is that the basic way you do sorting is to sort
the model. The way you do a different sort for two different views is
to create proxy models between the real data model and the views. The
proxy models are themselves views for the real data
model. TreeModelSort is a ready-made proxy model for the case where
the real data model derives from GtkTreeModel. You could write your
own custom proxy models for other kinds of real data model. These
could conceivably use special knowledge about the real data model to
be faster or use less memory.

Possible practical conclusions being:

 - TreeModelSort is not the only way to sort; ergo it doesn't have to
   be efficient for all possible models, it just should be convenient
   for the common cases. (e.g. I was thinking TreeModelSort eliminated
   the ability to use an array for custom models with sorting; that's
   not the case.)

 - we may as well have models support sorting directly via a
   set_sort_column method, so we can set things up automatically,
   because sort order is already a property of the model

   I guess "set things up automatically" just means that you can call:
     gtk_tree_view_column_set_sort (column, 5, compare_func_can_be_null);
   so that clicking that column sorts column 5 of the model. And 
   you could even default to something clever, maybe the 
   first column we're getting an attribute from.

This may have been obvious already, but I am just recently thinking
about the issues.

Another thought: it may well be useful to require explicit enabling of
persistent iterators, and get safe iterators otherwise. Something
like:
  if (gtk_tree_model_request_persistent_iterators (model))
    {
       /* can now use persistent iterators going forward */

    }

For the ListStore and TreeStore, basically this would turn off
checking of the iterator stamps, and put the model in "persistent
mode." In the non-sorted default case, you get safe iterators, but
when you add TreeModelSort it automatically goes into unsafe mode for
models that support it.


So we can maybe eliminate all the worries I had, namely we can allow
efficient custom sorting, and we can keep safe iterators for unsorted
tree/list store models. Also we should be able to set up
clicking-causes-sort automatically. What do you think?

Havoc