gtk-rs/gtk

Performance problems with TreeStore, set_value()

BenjaminRi opened this issue · 7 comments

BenjaminRi commented

Problem description:

Iterating through an entire TreeStore and setting all its elements to an new value shows unexpected performance problems that seem to grow quadratically with the number of elements in the TreeStore.

For example, setting 15000 elements containing u64 values takes gtk-rs about 270 milliseconds on my machine. The same program implemented in C takes 1 millisecond to set these values. Theoretically, the Rust wrappers should have nearly the same performance as the C code.

For the case in Rust, I plotted the situation:

  • x-axis: Number of elements
  • y-axis (blue): Number of milliseconds to set them all
  • y-axis (red): quadratic curve with constant factor fitted to blue line

plot

Problem reproduction:

https://github.com/BenjaminRi/gtk_treemodel_perf_rust
Build & start with cargo run --release
https://github.com/BenjaminRi/gtk_treemodel_perf_c
Build with ./compile.sh, start with ./treemodel_perf

I tried to write the above programs such that they do the exact same thing in terms of gtk calls.

The programs print out the number of elements, a comma, and then the number of milliseconds it took to set all the elements.

Notes:

The problem is exacerbated when uncommenting the line that creates a TreeModelSort on top of the TreeStore. In that case, the Rust performance is even worse in comparison to the C performance.

I did not make sure that the gtk libs I linked for C and the ones I linked for my Rust project were identical. So it could technically be a regression or already fixed bug in the gtk libs.

It seems like the --release build in Rust does a little bit worse (just a few percent), so that's an interesting tidbit.

BenjaminRi commented

Note: Performance disparity between C and Rust versions has now been verified with identical linked gtk library versions. This effectively rules out a bug in the gtk C libraries and points to the Rust wrappers.

sdroege commented

As discussed on IRC, the problem is a measurement problem. time() returns seconds, so the C version always reported 1 or 0 here. Both versions behave the same and are equally too slow, so a GTK problem here.

sdroege commented

@GuillaumeGomez Can you close this?

BenjaminRi commented

Thanks for the help, and sorry for that blunder.

sdroege commented

No worries, it's an interesting problem :)

BenjaminRi commented

@sdroege
Just to tie up loose ends: I ended up making an issue on the Gtk GitLab ( https://gitlab.gnome.org/GNOME/gtk/-/issues/2693 ) and the result of the analysis was that:

  • Yes, it is a bug in GTK.
  • Unfortunately, it's not just an implementation bug, it's an API design bug.
  • It is impossible to maintain the API invariants without this slow O(n^2) time.
  • This bug cannot / will not be fixed.
  • GTK4 will move tree and list based widgets to GListModel which does not have these invariants, so the situation should be better there.
  • I guess in the meantime, GTK3 users need to work around this issue by keeping TreeViews small or using custom models.
sdroege commented

Thanks for the update! Going with your own model seems like the solution for now then