Created attachment 238328 [details] [review]
Mostly avoid an expensive multi-map iteration pattern

If you have a MultiMap with, say, 100 keys each with 1 value, and you
iterate over it like this (pseudocode):

    for key in keys():
        values = get(key)
        for value in values:
            do something(key, value)

then you have constructed one GObject for the result of keys(), and
100 GObjects for the results of get() (because it returns a read-only
view). If you iterate it like this:

    iter = map_iterator()
    while iter.next():
        do something(iter.key(), iter.value())

there's only one extraneous GObject, the iterator itself.

When there are thousands of contacts, as in add-contacts-stress-test,
this really starts to matter.

This patch doesn't fix every use of get_keys() - some of them do
non-trivial work per key as well as per value, making it awkward to
convert to map_iterator() - but it's a start. It cuts 'user' CPU time
for IndividualAggregator quiescence for an e-d-s Google account with
2049 contacts (reading from cache) by around 3%.

Review of attachment 238328 [details] [review]:

Perhaps it would be worthwhile adding this to HACKING under the ‘Coding style’ section? Something along the lines of “always explicitly use an iter when iterating over Maps and MultiMaps for efficiency reasons”.

Apart from that, this looks great! Please commit to master with the above change to HACKING. Thanks.

Comment on attachment 238328 [details] [review]
Mostly avoid an expensive multi-map iteration pattern

Pushed as 3ead5929, thanks.

Leaving this bug open, because there's more that could be done.

(In reply to comment #2)
> Perhaps it would be worthwhile adding this to HACKING under the ‘Coding style’
> section?

I gave this advice for multimaps. I don't think there's nearly as much performance advantage in avoiding get_keys() + get() for ordinary 1:1 maps (OK, get_keys() + iterating over them creates two GObjects rather than one, but that's still O(1) so it doesn't really show up in my profiling).

(In reply to comment #4)
> (In reply to comment #2)
> > Perhaps it would be worthwhile adding this to HACKING under the ‘Coding style’
> > section?
> 
> I gave this advice for multimaps. I don't think there's nearly as much
> performance advantage in avoiding get_keys() + get() for ordinary 1:1 maps (OK,
> get_keys() + iterating over them creates two GObjects rather than one, but
> that's still O(1) so it doesn't really show up in my profiling).

IIRC it’s (slightly) more efficient in CPU time for Maps since calling get() has to skip over empty and collided buckets multiple times; whereas the Iterator can keep state to avoid them after skipping them the first time.

-- GitLab Migration Automatic Message --

This bug has been migrated to GNOME's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/folks/issues/42.