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 749583 - GSequence performance improvements
GSequence performance improvements
Status: RESOLVED FIXED
Product: glib
Classification: Platform
Component: general
unspecified
Other Linux
: Normal normal
: ---
Assigned To: gtkdev
gtkdev
Depends on:
Blocks:
 
 
Reported: 2015-05-19 14:05 UTC by Garrett Regier
Modified: 2018-01-11 12:56 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
gsequence: Kill check_iter_access() (5.09 KB, patch)
2015-05-19 14:07 UTC, Garrett Regier
none Details | Review
gsequence: Add seq_is_end() (2.23 KB, patch)
2015-05-19 14:08 UTC, Garrett Regier
none Details | Review
gsequence: Improve is_end() (1.18 KB, patch)
2015-05-19 14:08 UTC, Garrett Regier
committed Details | Review
gsequence: Kill check_iter_access() (4.94 KB, patch)
2016-05-09 09:09 UTC, Christian Hergert
committed Details | Review
gsequence: Add seq_is_end() (2.19 KB, patch)
2016-05-09 09:33 UTC, Christian Hergert
committed Details | Review

Description Garrett Regier 2015-05-19 14:05:28 UTC
There are a number of checks being done that could be improved from a performance perspective.
Comment 1 Garrett Regier 2015-05-19 14:07:23 UTC
Created attachment 303597 [details] [review]
gsequence: Kill check_iter_access()

Generally the GSequence has already been determined by the caller. This saves quite a few calls to get_sequence().
Comment 2 Garrett Regier 2015-05-19 14:08:05 UTC
Created attachment 303598 [details] [review]
gsequence: Add seq_is_end()

This avoids calling is_end() when the GSequence is already determined, thus avoids having to walk the tree.
Comment 3 Garrett Regier 2015-05-19 14:08:24 UTC
Created attachment 303599 [details] [review]
gsequence: Improve is_end()

Instead of finding the GSequence, just walk up the tree and determine if the iter is the end node.
Comment 4 Garrett Regier 2015-05-19 14:14:22 UTC
Performance improvement varies quite a bit depending on the GSequence being used, but just opening gedit results in a few thousand fewer calls to get_sequence().

Performance change after all three patches:
tests/sequence -seed=825541568
before: 15.62
after:  13.80
Comment 5 Sri Ramkrishna 2015-08-31 23:35:04 UTC
This seems like a good thing if it improves performance.  Any reason why we don't accept it?
Comment 6 Matthias Clasen 2015-09-01 15:19:22 UTC
I'll have a look.
Comment 7 Matthias Clasen 2015-09-01 23:02:55 UTC
Review of attachment 303597 [details] [review]:

::: glib/gsequence.c
@@ +561,3 @@
+
+  check_seq_access (seq_begin);
+  check_seq_access (seq_end);

I would suggest to just drop these calls here, since g_sequence_move_range is just repeating them first thing.

@@ +753,3 @@
   info.cmp_data = cmp_data;
+  info.end_node = seq->end_node;
+  check_seq_access (seq);

Just drop the call here - g_sequence_sort_changed_iter does it again
Comment 8 Matthias Clasen 2015-09-01 23:05:35 UTC
Review of attachment 303598 [details] [review]:

seems ok
Comment 9 Matthias Clasen 2015-09-01 23:07:49 UTC
Review of attachment 303599 [details] [review]:

Not entirely obvious why one should be faster than the other here.
Comment 10 Matthias Clasen 2015-09-01 23:08:54 UTC
In general, I would suggest as a strategy to remove check_access and is_end checks and similar preconditions from g_sequence api if it just calls out to g_sequence...iter api that has the same checks and preconditions.
Comment 11 Matthias Clasen 2015-12-16 12:43:33 UTC
Sadly, the acn patch doesn't apply cleanly without the other. Will you redo them as suggested ?
Comment 12 Christian Hergert 2016-05-09 09:01:31 UTC
(In reply to Matthias Clasen from comment #9)
> Review of attachment 303599 [details] [review] [review]:
> 
> Not entirely obvious why one should be faster than the other here.

This has the potential to be a lot faster for two reasons.

 1) You avoid walking to the root unless you are actually the end node.
 2) You avoid a call to node_get_last() in get_sequence() which is really
    expensive since it walks to the root and then to the right.

Instead this just checks for right as it walks up the tree.

Definitely a +1 from me.
Comment 13 Christian Hergert 2016-05-09 09:09:51 UTC
Created attachment 327497 [details] [review]
gsequence: Kill check_iter_access()

Adjust for review suggestions
Comment 14 Christian Hergert 2016-05-09 09:27:39 UTC
Also, I took a look at updating the ACN patch, but it really should continue to use the check_iter_access() removal from the updated patch above.

I think these are all ready to be committed as a set, but obviously mclasen or others will need to ACK.
Comment 15 Christian Hergert 2016-05-09 09:33:27 UTC
Created attachment 327499 [details] [review]
gsequence: Add seq_is_end()

Update the patch to apply cleanly with other updated patches
Comment 16 Christian Hergert 2016-05-09 09:34:50 UTC
Comment on attachment 303599 [details] [review]
gsequence: Improve is_end()

Resetting status as now there is an update on why this is faster in bug comments.
Comment 17 Allison Karlitskaya (desrt) 2016-05-09 12:50:33 UTC
Review of attachment 303599 [details] [review]:

Looks fine, and I agree with the logic.  Thanks.
Comment 18 Christian Hergert 2016-06-04 00:52:04 UTC
Mind doing another review pass on the other updated patches?

Although, it can wait until the hackfest if everyone is time constrained.
Comment 19 Philip Withnall 2018-01-11 12:42:51 UTC
Review of attachment 327499 [details] [review]:

Looks good to me.
Comment 20 Philip Withnall 2018-01-11 12:42:57 UTC
Review of attachment 327497 [details] [review]:

::: glib/gsequence.c
@@ +562,3 @@
+  seq_begin = get_sequence (begin);
+  seq_end = get_sequence (end);
+  g_return_if_fail (seq_begin == seq_end);

The check_seq_access() calls are dropped here.

@@ +753,3 @@
   info.cmp_func = cmp_func;
   info.cmp_data = cmp_data;
+  info.end_node = seq->end_node;

The check_seq_access() call is dropped here.
Comment 21 Philip Withnall 2018-01-11 12:44:32 UTC
(In reply to Philip Withnall from comment #20)
> Review of attachment 327497 [details] [review] [review]:
> 
> ::: glib/gsequence.c
> @@ +562,3 @@
> +  seq_begin = get_sequence (begin);
> +  seq_end = get_sequence (end);
> +  g_return_if_fail (seq_begin == seq_end);
> 
> The check_seq_access() calls are dropped here.
> 
> @@ +753,3 @@
>    info.cmp_func = cmp_func;
>    info.cmp_data = cmp_data;
> +  info.end_node = seq->end_node;
> 
> The check_seq_access() call is dropped here.

Ah, these were requested in comment #7. In which case, there should be a comment mentioning that in each location. I’ll update and merge the patch.
Comment 22 Philip Withnall 2018-01-11 12:56:22 UTC
Updated to include comments, and pushed to master.

Attachment 327497 [details] pushed as ee8f7be - gsequence: Kill check_iter_access()
Attachment 327499 [details] pushed as 6aa19a2 - gsequence: Add seq_is_end()