Avoid iterating over all handles in MessagePumpMojo on every iteration to calculate deadlines.

Avoid iterating over all handles in MessagePumpMojo on every iteration to calculate deadlines.

Instead of iterating over every handle, only iterate over those that have
a deadline set (and hence can expire). This requires tracking which
handles have deadlines.

A better solution would be to use a priority queue to track the closest
deadline. However, it turns out that no-one currently uses deadlines here, so
the size of |deadline_handles_| will always be 0.

BUG=556865
Committed: https://crrev.com/e8de0bc0f5403012fa125c1dc94e82744a270eb7
Cr-Commit-Position: refs/heads/master@{#361291}

[Anand Mistry (off Chromium), 2015-11-17 06:21:14]

amistry@chromium.org changed reviewers:
+ sky@chromium.org

[Anand Mistry (off Chromium), 2015-11-17 06:21:14]

This change eliminates two O(handles) loops on every message loop iteration; in
MessagePumpMojo::GetDeadlineForWait(), and the deadline expiry logic.

I've run HandleWatcherPerftest to benchmark this change and most of the tests
show no significant change. However, two tests shows a significant improvement,
and one has a small regression. The improved tests are (over 10 runs, warm page
cache, iteration/sec, bigger is better):
=========StartAllThenStop_1000Handles/DefaultMessageLoop=======
Before:
Min: 6502.09
Max: 6726.76
Mean: 6637.136
Median: 6664.795
StdDev: 71.8073914301
After:
Min: 8837.51
Max: 9159.93
Mean: 9059.511
Median: 9077.595
StdDev: 102.743955486
=========StartAndSignal_1000Waiting/MojoMessageLoop=======
Before:
Min: 5486.46
Max: 5584.78
Mean: 5558.285
Median: 5572.57
StdDev: 30.3145777638
After:
Min: 9654.28
Max: 10395.0
Mean: 10205.208
Median: 10260.0
StdDev: 203.67068659

Some of the others do show an improvement, but not enough to mention.

The regressed test is:
=========StartAndSignal_1000Waiting/DefaultMessageLoop=======
Before:
Min: 5564.37
Max: 5762.59
Mean: 5674.896
Median: 5691.62
StdDev: 58.7718664328
After:
Min: 5241.12
Max: 5395.17
Mean: 5348.061
Median: 5350.715
StdDev: 40.630070502

The latter improved test represents the case of Mojo apps which run on a Mojo
message loop (mandoline?). The equivalent test for Chrome's usage seems to
regress slightly. I can't explain the regression. The test consumes ~10% fewer
cycles, ~30% fewer branches, and ~50% fewer branch misses, so maybe timing?
Regardless, I think this change is a net win.

[sky, 2015-11-17 18:35:11]

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
File mojo/message_pump/message_pump_mojo.cc (right):

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.cc:230: for (auto h : expired_handles) {
auto& . And naming what is a pair 'h' is rather confusing and misleading. Use
pair.

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.cc:260: handlers_.erase(handle);
Replace these two lines with RemoveHandler.

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
File mojo/message_pump/message_pump_mojo.h (right):

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.h:124: std::set<Handle> deadline_handles_;
If we're really worried about efficiency, why don't we sort this based on
TimeTicks? That way GetDeadlineForWait() need only consult the first element.

[Anand Mistry (off Chromium), 2015-11-17 23:54:40]

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
File mojo/message_pump/message_pump_mojo.cc (right):

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.cc:230: for (auto h : expired_handles) {
On 2015/11/17 18:35:11, sky wrote:
> auto& . And naming what is a pair 'h' is rather confusing and misleading. Use
> pair.

Done.

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.cc:260: handlers_.erase(handle);
On 2015/11/17 18:35:11, sky wrote:
> Replace these two lines with RemoveHandler.

Done.

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
File mojo/message_pump/message_pump_mojo.h (right):

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.h:124: std::set<Handle> deadline_handles_;
On 2015/11/17 18:35:11, sky wrote:
> If we're really worried about efficiency, why don't we sort this based on
> TimeTicks? That way GetDeadlineForWait() need only consult the first element.

Sorting by TimeTicks would make removing by handle require a linear scan over
this. I can't think of an existing structure that would have efficient sorting
by time _and_ efficient insert/removal by handle. I could certainly write one,
but that's more than I wanted to do in this change.

And besides, I scoured codesearch looking for uses of this, and it turns out,
no-one ever sets a deadline. So right now, in 100% of cases, this set will be
empty.

[sky, 2015-11-17 23:58:42]

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
File mojo/message_pump/message_pump_mojo.h (right):

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.h:124: std::set<Handle> deadline_handles_;
On 2015/11/17 23:54:39, Anand Mistry wrote:
> On 2015/11/17 18:35:11, sky wrote:
> > If we're really worried about efficiency, why don't we sort this based on
> > TimeTicks? That way GetDeadlineForWait() need only consult the first
element.
> 
> Sorting by TimeTicks would make removing by handle require a linear scan over
> this. I can't think of an existing structure that would have efficient sorting
> by time _and_ efficient insert/removal by handle. I could certainly write one,
> but that's more than I wanted to do in this change.
> 
> And besides, I scoured codesearch looking for uses of this, and it turns out,
> no-one ever sets a deadline. So right now, in 100% of cases, this set will be
> empty.

If no one specifies a deadline, then wouldn't a boolean be simpler? A boolean is
more costly to keep in sync if we do specify deadlines, but as you said, we
don't specify a deadline.

[Anand Mistry (off Chromium), 2015-11-18 00:10:12]

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
File mojo/message_pump/message_pump_mojo.h (right):

https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
mojo/message_pump/message_pump_mojo.h:124: std::set<Handle> deadline_handles_;
On 2015/11/17 23:58:42, sky wrote:
> On 2015/11/17 23:54:39, Anand Mistry wrote:
> > On 2015/11/17 18:35:11, sky wrote:
> > > If we're really worried about efficiency, why don't we sort this based on
> > > TimeTicks? That way GetDeadlineForWait() need only consult the first
> element.
> > 
> > Sorting by TimeTicks would make removing by handle require a linear scan
over
> > this. I can't think of an existing structure that would have efficient
sorting
> > by time _and_ efficient insert/removal by handle. I could certainly write
one,
> > but that's more than I wanted to do in this change.
> > 
> > And besides, I scoured codesearch looking for uses of this, and it turns
out,
> > no-one ever sets a deadline. So right now, in 100% of cases, this set will
be
> > empty.
> 
> If no one specifies a deadline, then wouldn't a boolean be simpler? A boolean
is
> more costly to keep in sync if we do specify deadlines, but as you said, we
> don't specify a deadline.

It would, but then if one user does come along and sets a deadline, the
behaviour regresses significantly. My goal is to be better, but not perfect, and
not regress too much if usage changes.

[sky, 2015-11-18 00:47:00]

Wouldn't a set<Handler*> with a comparator that orders based on
deadline solve this?

  -Scott

On Tue, Nov 17, 2015 at 4:10 PM,  <amistry@chromium.org> wrote:
>
>
https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
> File mojo/message_pump/message_pump_mojo.h (right):
>
>
https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
> mojo/message_pump/message_pump_mojo.h:124: std::set<Handle>
> deadline_handles_;
> On 2015/11/17 23:58:42, sky wrote:
>>
>> On 2015/11/17 23:54:39, Anand Mistry wrote:
>> > On 2015/11/17 18:35:11, sky wrote:
>> > > If we're really worried about efficiency, why don't we sort this
>
> based on
>>
>> > > TimeTicks? That way GetDeadlineForWait() need only consult the
>
> first
>>
>> element.
>> >
>> > Sorting by TimeTicks would make removing by handle require a linear
>
> scan over
>>
>> > this. I can't think of an existing structure that would have
>
> efficient sorting
>>
>> > by time _and_ efficient insert/removal by handle. I could certainly
>
> write one,
>>
>> > but that's more than I wanted to do in this change.
>> >
>> > And besides, I scoured codesearch looking for uses of this, and it
>
> turns out,
>>
>> > no-one ever sets a deadline. So right now, in 100% of cases, this
>
> set will be
>>
>> > empty.
>
>
>> If no one specifies a deadline, then wouldn't a boolean be simpler? A
>
> boolean is
>>
>> more costly to keep in sync if we do specify deadlines, but as you
>
> said, we
>>
>> don't specify a deadline.
>
>
> It would, but then if one user does come along and sets a deadline, the
> behaviour regresses significantly. My goal is to be better, but not
> perfect, and not regress too much if usage changes.
>
> https://codereview.chromium.org/1448233002/

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[Anand Mistry (off Chromium), 2015-11-18 00:59:12]

On 18 November 2015 at 11:46, Scott Violet <sky@chromium.org> wrote:

> Wouldn't a set<Handler*> with a comparator that orders based on
> deadline solve this?
>

But then you couldn't do a lookup by Handler* since lookups are inherently
linked to ordering in std::set and std::map. I think I want a bi-map, but I
don't think there's currently one in the code base.


>
>   -Scott
>
> On Tue, Nov 17, 2015 at 4:10 PM,  <amistry@chromium.org> wrote:
> >
> >
>
https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
> > File mojo/message_pump/message_pump_mojo.h (right):
> >
> >
>
https://codereview.chromium.org/1448233002/diff/1/mojo/message_pump/message_p...
> > mojo/message_pump/message_pump_mojo.h:124: std::set<Handle>
> > deadline_handles_;
> > On 2015/11/17 23:58:42, sky wrote:
> >>
> >> On 2015/11/17 23:54:39, Anand Mistry wrote:
> >> > On 2015/11/17 18:35:11, sky wrote:
> >> > > If we're really worried about efficiency, why don't we sort this
> >
> > based on
> >>
> >> > > TimeTicks? That way GetDeadlineForWait() need only consult the
> >
> > first
> >>
> >> element.
> >> >
> >> > Sorting by TimeTicks would make removing by handle require a linear
> >
> > scan over
> >>
> >> > this. I can't think of an existing structure that would have
> >
> > efficient sorting
> >>
> >> > by time _and_ efficient insert/removal by handle. I could certainly
> >
> > write one,
> >>
> >> > but that's more than I wanted to do in this change.
> >> >
> >> > And besides, I scoured codesearch looking for uses of this, and it
> >
> > turns out,
> >>
> >> > no-one ever sets a deadline. So right now, in 100% of cases, this
> >
> > set will be
> >>
> >> > empty.
> >
> >
> >> If no one specifies a deadline, then wouldn't a boolean be simpler? A
> >
> > boolean is
> >>
> >> more costly to keep in sync if we do specify deadlines, but as you
> >
> > said, we
> >>
> >> don't specify a deadline.
> >
> >
> > It would, but then if one user does come along and sets a deadline, the
> > behaviour regresses significantly. My goal is to be better, but not
> > perfect, and not regress too much if usage changes.
> >
> > https://codereview.chromium.org/1448233002/
>

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[Anand Mistry (off Chromium), 2015-11-23 23:07:55]

Ping!

[sky, 2015-11-24 00:18:27]

I thought you were investigating separate structures. LGTM

[Anand Mistry (off Chromium), 2015-11-24 00:28:35]

On 2015/11/24 00:18:27, sky wrote:
> I thought you were investigating separate structures. LGTM

Oh, sorry. Yeah, I looked into it. It's complicated. A bimap is what I want, but
the naive ways of doing it won't work for this situation (because there's a
1-to-many mapping in the deadline->handler direction). I'm going to look into it
as a follow-up, but it's not so important at this point because deadlines just
aren't used.

[Anand Mistry (off Chromium), 2015-11-24 00:29:31]

The CQ bit was checked by amistry@chromium.org

[commit-bot: I haz the power, 2015-11-24 00:30:43]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1448233002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1448233002/20001

[commit-bot: I haz the power, 2015-11-24 03:38:36]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-11-24 03:38:37]

Try jobs failed on following builders:
  linux_chromium_chromeos_rel_ng on tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[Anand Mistry (off Chromium), 2015-11-24 08:11:09]

The CQ bit was checked by amistry@chromium.org

[commit-bot: I haz the power, 2015-11-24 08:12:10]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1448233002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1448233002/20001

[commit-bot: I haz the power, 2015-11-24 08:42:56]

Committed patchset #2 (id:20001)

[commit-bot: I haz the power, 2015-11-24 08:44:05]

Patchset 2 (id:??) landed as
https://crrev.com/e8de0bc0f5403012fa125c1dc94e82744a270eb7
Cr-Commit-Position: refs/heads/master@{#361291}