After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 80868 - Look into optimizing row validation
Look into optimizing row validation
Status: RESOLVED FIXED
Product: gtk+
Classification: Platform
Component: Widget: GtkTreeView
2.0.x
Other other
: Normal normal
: ---
Assigned To: gtktreeview-bugs
gtktreeview-bugs
: 71968 94710 99134 (view as bug list)
Depends on:
Blocks: 123538
 
 
Reported: 2002-05-05 18:16 UTC by Kristian Rietveld
Modified: 2011-02-04 16:12 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
proof of concept patch to speed up validate_rows() against 2.2.2 (1.68 KB, patch)
2003-09-06 22:03 UTC, Michael Vogt
none Details | Review
second part of proof of concept patch for speeding up validate_rows() (333 bytes, patch)
2003-09-06 22:07 UTC, Michael Vogt
none Details | Review
Fixed height patch. (6.43 KB, patch)
2003-09-11 21:37 UTC, Kristian Rietveld
none Details | Review
Patch shortcircuiting _build_tree. (4.27 KB, patch)
2003-09-11 21:37 UTC, Kristian Rietveld
none Details | Review
second attempt. (12.75 KB, patch)
2003-12-17 17:23 UTC, Kristian Rietveld
none Details | Review

Description Kristian Rietveld 2002-05-05 18:16:11 UTC
SSIA.
Comment 1 Kristian Rietveld 2002-12-19 02:44:34 UTC
Moving remaining bugs to 2.2.1.
Comment 2 Kristian Rietveld 2003-01-22 20:09:34 UTC
The current plan is to add a property which disables validation. It
will use fixed heights, and fixed columns. I don't see much more rooms
for performance improvements than this though, I need to learn to use
a profiler soon.

I have some concept patches on my harddrive. Once I make a stable
once, I will put it out for testing.
Comment 3 Kristian Rietveld 2003-01-22 20:15:25 UTC
Adding property means punting to 2.3.x
Comment 4 Kristian Rietveld 2003-01-22 20:17:37 UTC
*** Bug 99134 has been marked as a duplicate of this bug. ***
Comment 5 Kristian Rietveld 2003-01-22 20:18:03 UTC
*** Bug 71968 has been marked as a duplicate of this bug. ***
Comment 6 Kristian Rietveld 2003-01-22 20:18:37 UTC
*** Bug 94710 has been marked as a duplicate of this bug. ***
Comment 7 Charles Kerr 2003-05-07 21:01:30 UTC
Is there any progress being made on speeding up GtkTreeView?

I don't have much free time to implement the fixed heights/columns,
but if I can help you to do it, or help with testing/debugging,
I can swing that.

Fifteen months after reporting #71968 I'm still unable to migrate
Pan to TreeView because it's literally 22x slower than GtkCTree.
How on Earth does this a puntable unassigned normal/normal? :)

From the timing comparison programs included with #71968:

% pkg-config --modversion gtk+-2.0 
2.2.1
% ./time-clist 
** Message: clist inserted 30000 rows in 1.3 seconds (23351 rows/sec)
% ./time-treeview2 
** Message: gtk_list_store appended 30000 items in 4.7 secs (6403
rows/sec)
** Message: 29.2 seconds until idle

Comment 8 Kristian Rietveld 2003-05-22 21:31:19 UTC
I did some work on a fixed height patch. I think it got lost somewhere
after my machine went bad. Need to find it and attach it here. It
didn't help all that much though, I think there are more issues. The
latest pango HEAD might help (which has improved performance IIRC).

Don't count on me too much, I just don't have any profiling skills.
Comment 9 Pawel Salek 2003-07-29 12:00:59 UTC
Is there any progress on this one? Is there anything out that could be
tested/benchmarked?
Comment 10 Morten Welinder 2003-07-29 13:30:32 UTC
No profiling skills are needed.  Just create a test list with a million
entries in it and have the data provider log every request.

The goal should be to only call the data provider for visible cells.
Comment 11 Michael Vogt 2003-09-02 14:32:02 UTC
I'm also very interessted in speeding up the GtkTreeView. I use it in
synaptic (a gtk frontend for apt). And it take much too long to
display all 13.000 debian packages. I use
gtk_tree_view_column_set_fixed_width()  and
gtk_cell_renderer_text_set_fixed_height_from_font() to minimize the
amount of computation. But it still takes ~9sec to display the 13.000
packages (6 columns). 

I build gtk with profiling support and linked synaptic against this
version. I can provide the profiling output if someone is interessted.
It looks like the bottleneck is do_validate_rows(). 

Why does it go throught all the rows and columns? As far as I
understand the code (I admit that I do not understand it very well)
this is done to calc the size of each cell? If we use fixed sizes,
this shouldn't be needed? 
Comment 12 Kristian Rietveld 2003-09-02 18:16:16 UTC
We know that do_validate_rows is the bottleneck. Currently it goes
through all rows/columns because it has to measure them. This is
indeed not needed if we use fixed sizes, hence the fixed height patch
I was talking about earlier in this bug.

I have a concept patch on my hard drive. I will try to rewrite it
against HEAD ASAP (shouldn't take long, if I get time).

The fixed height patch will definitely make 2.4.
Comment 13 Michael Vogt 2003-09-02 20:59:01 UTC
that are really great news. I like the GtkTreeView, the only think
that bugs me is that it's not fast enough. So, once there is something
to test (even a preliminarily patch), please let me know. Maybe you
can even post the concept patch here, so that I can try to help you
with it (also I'm not familiar with the gtktreeview code).
Comment 14 Soren Sandmann Pedersen 2003-09-02 21:56:17 UTC
Michael, could you try upgrading to glib, pango and gtk+ HEAD and tell
me how long it takes with those?

The TreeView should be a good bit faster in HEAD.
Comment 15 Soren Sandmann Pedersen 2003-09-02 22:07:28 UTC
FYI, these are the numbers I get with cvs HEAD on the benchmarks from
#71968:

    CList:

    ** Message: clist inserted 30000 rows in 1.0 seconds (29781 rows/sec)

    TreeView:

    ** Message: added 30000 rows in 3.4 seconds (8813 rows/sec)

So the TreeView is currently 3.4 times slower than CList. Not terribly
bad, I'd say (but there's room for improvement of course).
Comment 16 Kristian Rietveld 2003-09-02 22:21:20 UTC
That's good news Soeren! There probably is some more room for
improvement (in gobject IIRC, we talked about that on IRC a few months
back, but I forgot all details ...).

Michael, I can't post the concept patch, since it's old (I think I
wrote it in December of last year), doesn't apply anymore and it's
broken. I will probably rewrite it somewhere this week, which is
something I should be able to do in one afternoon/evening.

Writing that patch is basically on top of my todo list now.
Comment 17 Soren Sandmann Pedersen 2003-09-02 22:23:45 UTC
blah, ignore those numbers, because 

 a) a lot of the time in both cases is spent
    in code that only runs once (cache building and such). The
    benchmark needs to run with more data to say anything useful.
 b) I had a compilation running.
 c) I had some extra patches applied

The point still stands though: HEAD is substantially faster than
stable, and actually I don't see any huge performance problems with it.
Comment 18 Soren Sandmann Pedersen 2003-09-02 22:28:05 UTC
Kristian, well I believe I said then that I don't think a
programmer-settable "fixed-height" property makes sense, because it is
basically a hack that requires more knowledge about the data tahn I
think should be necessary. 

I'd tend to agree with Morten that the TreeView should be able to just
assume that everything is fixed height, and only ask the data provider
when the tree view is "proven wrong".
Comment 19 Kristian Rietveld 2003-09-02 22:58:53 UTC
I agree that it is a hack, I am also really afraid that people will
misuse it.

Your second comment is interesting. I have some thoughts right now on
how to implement it (I will think about it more on the train tomorrow
;), I will give that a try first this week. If that doesn't help
enough, I will fallback on my fixed-height plan.
Comment 20 Michael Vogt 2003-09-03 00:15:43 UTC
Ok, thanks for the hints. I build synaptic against GLib/Pango/Gtk+
HEAD and measured the time spend in do_validate_rows via clock()
(sorry for this simple method but I was to lazy to build a profiling
version again). Please note that I measured how long it takes to build
the complete tree (until idle), not the time until something is
visible for the first time. My results for a list with ~13.000
packages and 6 columns (1 pixmap, 5 text):

GTK+ - HEAD:
start - end do_validate_rows: 6140000 = 6.1sec

GTK+ - 2.2.2
start - end do_validate_rows: 8590000 = 8.5sec

(times measured/approximated ;) in clock_t on a 1200Mhz Pentium3)

While this is certainly a improvement, I really hope that there is
room for more :)

[Disclaimer: I'm not 100% sure if this figures are ok for HEAD,
because something is wrong with my pango HEAD installation, I get: "**
(synaptic:17820): WARNING **: No builtin or dynamically loaded modules
were found. Pango will not work correctly." on startup.]
Comment 21 Charles Kerr 2003-09-03 03:55:36 UTC
Soren or Michael: could you run CVS HEAD against the two benchmarks
I attached to issue #71968?

(1) http://bugzilla.gnome.org/showattachment.cgi?attach_id=6815
    times how long it takes to populate & render a 30,000-item clist

(2) http://bugzilla.gnome.org/showattachment.cgi?attach_id=6816
    time-treeview.c: times how long it takes to populate & render a
    30,000-item treeview

cheers
Comment 22 Pawel Salek 2003-09-03 04:57:29 UTC
I think it should be emphasized that benchmarking GtkTreeStore is one
thing and the other thing is to have ability to "only call the data
provider for visible cells" - as Morten wrote. Otherwise, GtkTreeView
will remain hardly useful for browsing eg. databases and similar data
structures which have large cost associated with fetching the data. 
Comment 23 Michael Vogt 2003-09-03 08:00:09 UTC
I have to say that I agree with Pavel here. 

I did a benchmark nevertheless :) Here are my results (same as above
my pango HEAD gives me a warning about:  No builtin or dynamically
loaded modules found).

HEAD
** Message: clist inserted 30000 rows in 0.2 seconds (143375 rows/sec)
** Message: added 30000 rows in 2.2 seconds (13369 rows/sec)

GTK+ - 2.2.2
** Message: clist inserted 30000 rows in 0.2 seconds (133822 rows/sec)
** Message: added 30000 rows in 2.8 seconds (10555 rows/sec)

[Machine is a Pentium3 1200Mhz, gcc 3.3.1]
Comment 24 Michael Vogt 2003-09-03 08:05:18 UTC
A small addition: from the 2.2 sec it took in HEAD to display the
list, 2,03 secs are spend in do_validate_rows() (according to my
"clock()" profile). 
Comment 25 Charles Kerr 2003-09-03 15:38:55 UTC
> Message: clist inserted 30000 rows in 0.2 seconds (143375 rows/sec)
> Message: added 30000 rows in 2.2 seconds (13369 rows/sec)

So the treeview is over an order of magnitude slower than gtkclist.

jrb marked #71968 (which was closed as a dup of this bug) as a high
priority, major severity back in Feb 2002.
Comment 26 Michael Vogt 2003-09-06 22:03:29 UTC
Created attachment 19790 [details] [review]
proof of concept patch to speed up validate_rows() against 2.2.2
Comment 27 Michael Vogt 2003-09-06 22:06:43 UTC
I had a look into validate_rows() today and hacked around a bit. I
added two new private variables use_uniform_row_height and
uniform_row_height. If uniform_row_height is set (currently
hardcoded), the row height is only calculated once in validate_rows()
and then used for all other rows in the treeview. This way, the
treeview is much faster. I attach a proof of concept patch against
gtk+ 2.2.2 (the patch is pretty trivial). 
Comment 28 Michael Vogt 2003-09-06 22:07:36 UTC
Created attachment 19791 [details] [review]
second part of proof of concept patch for speeding up validate_rows()
Comment 29 Kristian Rietveld 2003-09-07 11:57:06 UTC
Yes, we know that, and that is what we need to get TreeView to do most
of the time. The only problem is deciding when exactly we use which
method.

I wrote some ideas on paper during class last week, which I am trying
to get jrb to look at (he has some comments on those). The plan is here:

http://www.math.leidenuniv.nl/~kris/validation-plan

As soon as jrb and I settle on those details, I can start implementing
it. Then it won't be long before there is a patch ;) I really want to
write this patch and get it in soon now.
Comment 30 Kristian Rietveld 2003-09-11 21:36:40 UTC
After talking with owen on IRC, we decided to go with the property.
Owen basically had two comments:

* He doesn't like a scrollbar which starts changing automagically when
scrolling.
* In order to use this, the programmer should set *all* columns to
FIXED and set the fixed_height_mode property to TRUE. Else it will not
work.

I will attach two patches:
1) The patch adding a fixed_height_mode property.
2) A patch (inspired by jrb) to shortcircuit touching the childs in
gtk_tree_view_build_tree if the model specifies that it doesn't and
won't contain children.
Comment 31 Kristian Rietveld 2003-09-11 21:37:14 UTC
Created attachment 19877 [details] [review]
Fixed height patch.
Comment 32 Kristian Rietveld 2003-09-11 21:37:57 UTC
Created attachment 19878 [details] [review]
Patch shortcircuiting _build_tree.
Comment 33 Michael Vogt 2003-09-11 23:37:08 UTC
thanks for the patch. the speed is _much_ better. in fact no slowdown
is noteable at all with 12.000 entrys with my P3-1200. the row height
is wrong in my test, but it's wrong regardless if I enable
fixed_height or not, so it's probably my fault (installing two pango
versions seems a bit tricky).

This will be part of gtk 2.4? released in november? can't wait for it :)
It's really great that this issue is fixed now! thanks a lot!
Comment 34 Soren Sandmann Pedersen 2003-09-12 16:49:49 UTC
> * He doesn't like a scrollbar which starts changing
>    automagically when scrolling.

Neither do I, but this would _only_ happen when the TreeView was
"proven wrong", so in the 99% case where the tree view actually is
fixed height, the scrollbar would not change automagically. And in
the case of a big list (which is what we are concerned about here), 
the scrollbar thumb would be at its minimum width anyway, so unlikely
to actually change.

The only advantage to having the property that I see is that in the
case where the rows are unequal height AND the programmer knows that
this may be the case AND the treeview is _not_ big enough to make the
scrollbar thumb the minimum size AND the programmer is conscientious
to not turn on the property anyway, in that case scrollbar thumbs
won't change size during scroll (but the tree view will be slow).

The disadvantage is that it requires the programmer to manually
specify information that he in many cases *does not have*. If 
the data comes from an external source, then the programmer often
can't be sure that it will actually be fixed height without 
manually doing a validation ...

I predict programmers will invariably turn the property on anyway,
and things will be broken when the rows are actually unequal height.

The TreeView could compensate by actually doing a validation when
it discovers a row with a different height, but then you'd get
changing scrollbars ...
 
> * In order to use this, the programmer should set *all* columns to
> FIXED and set the fixed_height_mode property to TRUE. Else it will
> not work.

This would be necessary for both approaches, but the no-property
approach would result in one less thing that could fail.

(Why doesn't the tree view use the RB tree to keep track of the
maximum width btw? It should not be necessary to pass over all
the data for each and every change to some row.)
Comment 35 Owen Taylor 2003-09-12 17:04:46 UTC
Soeren - you seem to be neglecting that most tree views 
are small enough for the current approaches to work well.
I think sacrificing correctness (and the scrollbar that
changes size as you scroll is *not* correct) for those
tree views would be a bad mistake.

And also, since you have to set all columns to FIXED means
that people have to read the "My TreeView is slow" FAQ
anyways, so adding something else there isn't a big
deal.

(The reason that autosize is as slow at is is because
a per-column width attribute in the RBTree would be a
huge memory sink. But even if you took that hit, you'd
still have to measure every string in the tree.)
Comment 36 manu 2003-09-12 18:27:17 UTC
I'm one of the developpers of Balsa, and for us we can afford to have
automagically changing scrollbars if the tree can be drawn rapidly for
thousands of lines (~10 columns by row). And I guess pan will also use
that feature (last time I checked they were still using clist or
ctree, and I think it is certainly for perormance reason).
So I would vote for this : fixed height tree could be turned on by the
programmer and he could also ask the treeview to adapt its height when
a visible line is greater than the fixed value.
Comment 37 Michael Vogt 2003-09-18 09:34:57 UTC
I checked out the latest gtk cvs today and I noticed that the
"fixed_height_mode" patch is not in (yet). What prevents it from going
in? 
Comment 38 Kristian Rietveld 2003-09-18 19:35:42 UTC
I am waiting on Jonathan to review/approve the patches.
Comment 39 Michael Vogt 2003-09-24 13:36:20 UTC
I really don't want to get on your nerves, but according to
http://www.gtk.org/plan/2.4/ there is the api/abi freeze planed for 1
October 2003. I'm sligthly worried, that if the patch does not make it
before, it will be missing in gtk 2.4. 	
Comment 40 Morten Welinder 2003-10-03 18:14:53 UTC
As bug 123538 shows, it only takes 100 lines of text to make things
horribly slow.  Long lines, admittedly, but that is what real life
is going to throw at treeview/pango.

If the powers that be intend to let this one slip, would they please
speak up!

Then, at least, we could make informed decision as to whether a forked
and severely bastadized treeview should be coded up for gnumeric.
Comment 41 Pawel Salek 2003-10-03 18:48:16 UTC
gnumeric wouldn't be the only program with the forked gtktreeview if
this patch does not make it. True, one can work around this in certain
conditions with help of some gtk_tree_view_get_visible_rect() 
gtk_tree_view_get_cell_area() calls but that's not effective, and it
breaks the MVC model.
Comment 42 Owen Taylor 2003-10-03 19:03:37 UTC
Michael / Pawel / etc. The sign of something not making the 
API freeze is someone changing the milestone to be "2.6 API freeze".
Has that happened? Then you don't need to clutter up the bug
report.
Comment 43 Michael Vogt 2003-11-05 01:02:22 UTC
Sorry for making noise again. But it just wanted to ask if there is a
way I can help getting the fixed-height patch in (now that 2.3.0 is
released without the patch)? IMHO it's save to apply as it's not
enabled by default and only applications that explicit set the
property will get the new code. 
Comment 44 Kristian Rietveld 2003-11-16 15:20:05 UTC
I am going to pester jrb to get my patches reviewed this week.
Comment 45 Jonathan Blandford 2003-12-01 23:01:21 UTC
Some comments on "Patch shortcircuiting _build_tree" first:

 * You need to do a g_return_val_if_fail(model->priv->child_model) in
both GtkTreeModelFilter and GtkTreeModelSort, as we can't change our
flags after the child model has been added.  Thus get_flag shouldn't
be called before the child is set.
 * It looks like we don't set the _IS_LIST flag in the case where the
model doesn't explicitly set the flag, but it is one anyway.
Comment 46 Jonathan Blandford 2003-12-01 23:33:35 UTC
Some comments on the first reading of the fixed-height patch:

 * If there's the invariant that columns have to be FIXED for
   fixed_height to be set, then we need to also check for it when we add
   new columns or when columns change their SIZING.

 * I think we should store the height of the fixed height (and clear it
   in style_set).  Your current strategy of always using
   tree_view->priv->tree->root as the height is cute, but won't provide
   a consistent behavior.  People will use this with non-fixed-height
   trees despite the warning, and tree_view->priv->tree->root will
   change as nodes get added/removed.  Additionally, if we keep the
   height, we can actually do insert_remove synchronously.
Comment 47 Michael Vogt 2003-12-08 11:55:59 UTC
Jonathan: are your comments about fixed-height patch a show-stopper
for the inclusion of the in gtk 2.3.1? 
Kristian: are you working on the issues pointed out by Jonathan
already or do you want me to give it a try? (though I don't have a lot
of experience with the internals of the widget).
Comment 48 Kristian Rietveld 2003-12-08 21:31:09 UTC
I will fix my patch and commit it on Saturday.
Comment 49 Kristian Rietveld 2003-12-14 15:23:58 UTC
(build tree patch went in yesterday, fixed height will follow later
(needs more changes and a new review)).
Comment 50 Kristian Rietveld 2003-12-17 17:23:16 UTC
Created attachment 22513 [details] [review]
second attempt.
Comment 51 Kristian Rietveld 2003-12-17 20:30:41 UTC
Second attempt committed with some slight changes.

Case closed.

(hooray)
Comment 52 Morten Welinder 2003-12-19 21:16:36 UTC
This isn't actually quite as powerful as I would have liked.  It
currently requires

  gtk_tree_view_column_get_sizing (column) == GTK_TREE_VIEW_COLUMN_FIXED

which, if I understand things right, means that I must come up with a
proper width in pixels for the column (since I have more than one
column).

What does width have to do with fixed-height?
Comment 53 Kristian Rietveld 2003-12-19 23:31:52 UTC
Yes, you are going to have to come up with a good width for your
column. Fixed height mode basically avoids the validation phase; in
the validation phase the width was also measured to come up with a
good column size for autosize columns. Since fixed height mode avoids
validation this is no longer possible.

I might change the requirement to be "the column should not be of type
AUTOSIZE", instead of "the column should be of type FIXED". But I will
talk with jrb about that first. But that's not going to help you much.

Anyway, you get to come up with a column size. This complete fixed
height thing is not the most beautiful hack of the world. As I said in
my mail on gtk-devel-list/d-d-l, only use it when it is REALLY needed.

Closing again as FIXED.