Improved performance in GtkTreeModelSort and GtkTreeModelFilter

GtkTreeModelSort and GtkTreeModelFilter basically proxy the shape of their child model, including modifications. Internally, the models proxy incoming requests from their observers to requests on the child model. A mapping is needed from nodes exposed by the sort and filter models to nodes in their child models. Since the models can “perform” modifications, the mapping must be able to deal with these modifications.

The mapping is internally implemented as a tree of nodes that are visible in the observer (i.e. the observer took references on these nodes). Each level is an array of nodes. When we hand out an iterator to the observer, the user data of the iterator is set to a pointer to the node in the array. When the iterator is used, we can very quickly access the node in the internal data structure. Using data in this node (for example index into the level in the child model) we can construct an iterator relative to the child model to forward the operation. Sometimes we can even cache these iterators. A node can have a “children” pointer set to point at a child level.

Using arrays works well — we have been using GArray for a long time — unless the internal data structure is subject to frequent changes. This either happens due to a lot of activity in the child model, or due to filtering activity. When adding and removing nodes in the GArray, memory has to be moved. When the array is large and this happens often, this becomes very costly.

Xavier Claessens noticed this and wrote a patch to replace the use of GArray with GSequence. This significantly sped up operation of the filter model in certain cases. We have committed this change as part of the “treemodel-fix” branch last year, but only after we got a lot more of the sort and filter model under unit test. This way, we could ensure that no regressions were introduced when migrating from GArray to GSequence.

One Response to “Improved performance in GtkTreeModelSort and GtkTreeModelFilter”

  1. I would have implemented GtkTreeModelFilter using GtkRBTree.
    Side note: You could implement a hypothetical GtkTreeModelFlatten that way, too.