Re: Optimizing GtkListBox for many rows

[Sam Thursfield <ssssam gmail com>]

hi Timm

On Mon, Aug 31, 2015 at 10:49 AM, Timm Bäder <mail baedert org> wrote:
> Hi,
>
> if you've ever worked with a GtkListBox that has many rows, you probably
> know about the performance problems.  These are mostly not even related
> to drawing or scrolling.  The biggest problem is just allocating all of
> those rows (bonus points if every row uses a composite template, so you
> have to parse XML and create all those widgets/objects, set the
> properties, etc.) and size allocation.
>
> And I guess basically everyone knows how mobile UIs solve (or avoid)
> thsi problem: they just estimate the list height, and only keep as many
> rows around as they need to cover the current viewport.  This way
> obviously needs a backing model implementation (which we have now with
> GListModel) and a function that just takes an item and assigns the data
> to the corresponsing widgets etc.
>
> Earlier this year I've started to play around with such a
> widget-recycling listbox implementation here:
> https://github.com/baedert/listbox-test (don't judge my commit
> messages).  It's currrently written in Vala (so I can write stuff
> faster).  The repo includes a few demos which work more or less, you
> just have to (un)comment the corresponding lines int the Makefile.  The
> ideal case, i.e. "all rows are visible and all rows have the same
> height" seems to work already.
>
> I've talked to at least 4 people about this and I know a few others have
> worked on an implementation, too, so I think it's better to just
> collect all the knowledge we have instead of smoeone writing it on
> their own.  The current implementation faces a few problems, mainly
> regarding scrolling:

...

> I hope I didn't forget anything and I'm curious what you alll think and
> what solutions you have for all those problems, cheers.


I started prototyping something similar a while back, but with kind of
a different angle.

GListModel has a 'g_list_model_get_n_items()' function. I am
interested in the case where the data model doesn't actually know how
many items it has, but might be able to estimate. This is useful when
you have a database query across a big data set, with a whole lot of
joins and stuff too so that even doing COUNT() of the number of rows
might take longer than 10 seconds.

I came up with a PagedDataModel interface with 5 methods:
first_page(), next_page(), prev_page(), last_page(),
estimate_row_count() and get_page_for_position(). Each page would hold
a certain number of rows in memory. The get_page_for_position()
function allows jumping through the model with the scroll bar: you
pass it a float between 0 and 1, and it returns you the page of data
*around* that position.

Row numbers are relative to the page. There are no absolute row
numbers at all. Pages have a 'normal' size (100 rows, for example) but
the model can return a smaller page, to ensure that each row is only
ever in one page.

To take the example of an SQL database, you could implement a
PagedDataModel interface by using OFFSET and LIMIT, and by using COUNT
on a simplified version of the query to estimate the number of rows
quickly.

It's a bit crazy and I never got far enough with it to prove that it
wasn't *too* crazy, or that it provided any speed/memory benefits in
real use cases.  It's also a fairly niche usecase, I don't think it's
necessarily something Gtk+ itself needs to support. But perhaps it's
good to have in mind.

Prototype code is here:
<https://github.com/ssssam/charango/blob/research/research/view.py#L203>,
it's pretty bananas. I had a go at hacking GtkTreeView to display this
kind of model via a GtkTreeModel 'adaptor', too, but the code I linked
to doesn't work because it emits signals like row-changed and
row-added from *within* calls like gtk_tree_model_iter_next(), which
breaks everything.

I hope this is interesting, anyway
Sam