Optimizing GtkListBox for many rows

[Timm Bäder <mail baedert org>]

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:

  - Of course, the scrollbar jumps around.  If seen people say that
    nowadays, scrollbars should be seen as a rough indicator so maybe
    this is a non-issue but in extreme cases it seems pretty awkward
    to me.
  - Scrolling by dragging the scrollbar is completely broken if you have
    uneven row heights.  Android solves (read avoids) this by scrolling
    row-by-row in those cases. I think Alex said something about this at
    the GTK+ BoF at Guadec.
  - We estimate the list size by just looking at the height of the
    current widgets.  This means that the estimated height changes
    almost every time we remove/add a new row (given that rows have
    uneven height).  I explicitly decided agains saving the height of
    every row we ever allocated and using that as a better estimate,
    because it makes the estimation much more complex (think about the
    row height depending on the data in the model...) and I don't want
    people to notoriously scroll through all the listboxes once to fix
    the scrolling.
  - We currently just pool the used widgets, i.e. we never free any of
    them.  I'm not sure how other existing implementations solve this or
    if it's just not a problem at all.
  - IIRC Benjamin told me once that just faking widgets to A11y isn't
    really possible ATM.
  - I'm not sure if there's gtk+-internal API for this, but we'd
    basically need to tell the css machinery that a widget is at
    position i, without i being the actual current position in the
    widget hierarchy (so :nth-child works as expected).
  - Of course, this is currently completely independent from GtkListBox
    so we'd need to integrate it there.


For reference, the Android implementation can be found at [1] and
features nice methods like findViewByPredicateInHeadersOrFooters, but
also lots of informative comments. I'm not sure how many of those 4KLOC
Java we really need (and how many that would be in C...), but Android's
ListView does much more than the current GtkListBox, like headers that
stick to the top of the list when scrolled. On the other hand, I'm
certain that e.g. Christian wants exactly that so if such a feature
would completely change the entire implementation, we should maybe care
about it from the very start.


The current performance is OK I think.  The repo includes a tweet-row.ui
that I just copied from corebird and removed a few things, but it's
still around 330 lines of XML and that works as far as I can see.


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.


[1] https://github.com/android/platform_frameworks_base/blob/master/core/java/android/widget/ListView.java