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().

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.

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.

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

This seems like a good thing if it improves performance.  Any reason why we don't accept it?

I'll have a look.

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

Review of attachment 303598 [details] [review]:

seems ok

Review of attachment 303599 [details] [review]:

Not entirely obvious why one should be faster than the other here.

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.

Sadly, the acn patch doesn't apply cleanly without the other. Will you redo them as suggested ?

(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.

Created attachment 327497 [details] [review]
gsequence: Kill check_iter_access()

Adjust for review suggestions

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.

Created attachment 327499 [details] [review]
gsequence: Add seq_is_end()

Update the patch to apply cleanly with other updated patches

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.

Review of attachment 303599 [details] [review]:

Looks fine, and I agree with the logic.  Thanks.

Mind doing another review pass on the other updated patches?

Although, it can wait until the hackfest if everyone is time constrained.

Review of attachment 327499 [details] [review]:

Looks good to me.

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.

(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.

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()