Add UserInputTracker, which keeps track of recent user input events.

chrome/browser/page_load_metrics/user_input_tracker.cc

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/page_load_metrics/user_input_tracker.h"
+
+#include <algorithm>
+
+#include "third_party/WebKit/public/platform/WebInputEvent.h"
+
+namespace page_load_metrics {
+
+namespace {
+
+// Blink's UserGestureIndicator allows events to be associated with gestures
+// that are up to 1 second old, based on guidance in the HTML spec:
+// https://html.spec.whatwg.org/multipage/interaction.html#triggered-by-user-activation.
+const int kMaxEventAgeSeconds = 1;
+
+// Allow for up to 2x the oldest time. This allows consumers to continue to
+// find events for timestamps up to 1 second in the past.
+const int kOldestAllowedEventAgeSeconds = kMaxEventAgeSeconds * 2;
+
+// In order to limit to at most kMaxEntries, we rate limit the recorded events,
+// allowing one per rate limit period.
+const int kRateLimitClampMillis =
+    (kOldestAllowedEventAgeSeconds * 1000) / UserInputTracker::kMaxEntries;
+
+bool IsInterestingInputEvent(const blink::WebInputEvent& event) {
+  // Ignore synthesized auto repeat events.
+  if (event.modifiers & blink::WebInputEvent::IsAutoRepeat)
+    return false;
+
+  switch (event.type) {
+    case blink::WebInputEvent::MouseDown:
+    case blink::WebInputEvent::MouseUp:
+    case blink::WebInputEvent::RawKeyDown:
+    case blink::WebInputEvent::KeyDown:
+    case blink::WebInputEvent::Char:
+    case blink::WebInputEvent::TouchStart:
+    case blink::WebInputEvent::TouchEnd:
+      return true;
+    default:
+      return false;
+  }
+}
+
+base::TimeTicks GetTimeTicksFromSeconds(double seconds) {
+  // WebInputEvent::timeStampSeconds is a double representing number of

[Charlie Harrison, 2016/12/05 19:17:46]

optional: This looks like its only used once, I'd personally prefer inlining in
GetEventTime, but up to you.

[Bryan McQuade, 2016/12/06 01:52:24]

You're right, there's no benefit to factoring this out for reuse purposes, given
it's only used one time. This was motivated by a desire to abstract away the
strange implementation (base::TimeTicks() plus a time delta, in order to get a
timedelta in monotonic time base). This ideally allows readers of the code to
just skip right over 'GetTimeTicksFromSeconds' at the call site, since it's
obvious from the name what that should do, making it easier to focus on the
implementation details of the call site. This was motivated in part by your
earlier comment asking to add a comment where it was used previously - felt it
better to abstract the strange code away in a helper along with a comment to
explain.

+  // monotonic seconds in TimeTicks time base. There's no convenience API for
+  // initializing a TimeTicks from such a value. The canonical way to perform
+  // this initialization is to create a TimeTicks with value 0 and add a
+  // TimeDelta to it.
+  return base::TimeTicks() + base::TimeDelta::FromSecondsD(seconds);
+}
+
+}  // namespace
+
+UserInputTracker::UserInputTracker() {
+  event_times_.reserve(kMaxEntries);
+}
+
+UserInputTracker::~UserInputTracker() {}
+
+const size_t UserInputTracker::kMaxEntries = 100;

[Charlie Harrison, 2016/12/05 19:17:46]

Why 100 and not a nice round number like 128 or 64? Is it to ensure an integer
ClampMillis?

[Bryan McQuade, 2016/12/06 01:52:24]

Ha, is 64 or 128 rounder than 100? I guess it depends on your base. :)

I've not heard this suggestion before but I'm open to it. Is there a benefit to
using a base16-based value like 64 or 128? Does it lead to better memory
alignment? I can make the change - just want to understand the motivation.

You point out the benefit to using 100 - it makes the clamp interval a round
number that's easier for humans to reason about. I think that's reason to stick
with a base10 value but I'm open to switching if there's a reason base16 will
have a significant improvement on browser performance.

[Charlie Harrison, 2016/12/06 18:43:09]

It isn't a huge deal.  Aligning to a multiple of 64 bytes (a typical cache line
size) makes some sense, as you won't be pulling unnecessary data into your cache
when reading from the end of your buffer. TimeTicks is 8 bytes so that's 8
TimeTicks per cache line.

Probably 100 is fine though, especially because you get the integer clamp :)

+
+// static
+base::TimeTicks UserInputTracker::GetEventTime(
+    const blink::WebInputEvent& event) {
+  return GetTimeTicksFromSeconds(event.timeStampSeconds);
+}
+
+// static
+base::TimeTicks UserInputTracker::RoundToRateLimitedOffset(
+    base::TimeTicks time) {
+  base::TimeDelta time_as_delta = time - base::TimeTicks();
+  base::TimeDelta rate_limit_remainder =
+      time_as_delta % base::TimeDelta::FromMilliseconds(kRateLimitClampMillis);
+  return time - rate_limit_remainder;
+}
+
+void UserInputTracker::OnInputEvent(const blink::WebInputEvent& event) {
+  RemoveOldInputEvents();
+
+  if (!IsInterestingInputEvent(event))
+    return;
+
+  // TODO(bmcquade): ideally we'd limit tracking to events generated by a user
+  // action, as opposed to those generated from JavaScript. The JS API isTrusted
+  // can be used to distinguish these cases. isTrusted isn't yet a property of
+  // WebInputEvent. We should consider adding it.
+
+  base::TimeTicks time = RoundToRateLimitedOffset(GetEventTime(event));

[Charlie Harrison, 2016/12/05 19:17:46]

Optional: Instead of rounding we could instead just check if the given event is
> ClampMillis from the most recent event. It gives us less precision but it is
simpler and doesn't require the complicated rounding code.

[Bryan McQuade, 2016/12/06 01:52:24]

That's an interesting idea. It adds some additional complexity in that we need
to call upper_bound then decrement the iterator if we're not at beginning in
order to get the first event before or equal to, then see if it's within the
clamp threshold (can't just look at events_.end() since the new time may not go
at the end). I think it's complexity either way.

[Charlie Harrison, 2016/12/06 18:43:09]

Yeah I'm not sure, after going through the rest of the patch I'm in favor of how
you did it.

+  if (time <= std::max(most_recent_consumed_time_, GetOldestAllowedEventTime()))

[Charlie Harrison, 2016/12/05 19:17:46]

GetOldestAllowedEventTime calls the monotonic clock, which isn't cheap. Since we
already call TimeTicks::Now() in RemoveOldInputEvents I'd like to find a way to
only call it once in this function, maybe by expanding RemoveOldInputEvents?

[Bryan McQuade, 2016/12/06 01:52:24]

I'm mixed on this. I think the simplest way to do this would be to pass 'now'
into GetOldestAllowedEventTime(). That brings a slight perf benefit, but it's
weird to have to pass the current time into this method. Are we sure it's worth
the added code complexity? We expect this method to be called relatively
infrequently, on the order of the frequency with which a user might click a
mouse button, click a key on the keyboard, or tap the screen of the device.
Perhaps once every few hundred milliseconds during an active period.

I've gone ahead & made the change but I'm not sure this is the right perf/code
simplicity tradeoff. I don't know how long the call to clock_gettime takes,
however. Do you have a sense for the cost of an inocation of clock_gettime with
the monotonic clock? Are we talking nanos here? Assuming a few tens of nanos,
we're looking at about 20/100000000 = 0.00002% CPU cycle savings assuming 1
event per 100ms. My sense is that's probably not enough to justify an
optimization.

[Charlie Harrison, 2016/12/06 18:43:09]

Your call. I agree It is a bit awkward to thread the TimeTicks, and I would be
fine reverting it to calling Now() twice. One thing you could do is have
GetOldestAllowedEventTime to instead return a TimeDelta, and rename it something
like GetOldEventThreshold or something.

[Charlie Harrison, 2016/12/06 22:04:55]

What do you think about this idea?

[Bryan McQuade, 2016/12/06 22:15:21]

That is better. I've changed it.

+    return;
+
+  if (time > base::TimeTicks::Now()) {
+    DCHECK(!base::TimeTicks::IsHighResolution());
+    return;
+  }
+
+  // lower_bound finds the first element >= |time|.
+  auto it = std::lower_bound(event_times_.begin(), event_times_.end(), time);
+  if (it != event_times_.end() && *it == time) {
+    // Don't insert duplicate values.
+    return;
+  }
+
+  event_times_.insert(it, time);

[Charlie Harrison, 2016/12/05 19:17:46]

I am curious what the insertion pattern looks like in practice. Are we usually
inserting at the ~end?

[Bryan McQuade, 2016/12/06 01:52:24]

Yes, it should be usually at the end, but no guarantee.

[Charlie Harrison, 2016/12/06 18:43:09]

Acknowledged.

+  DCHECK(event_times_.size() <= kMaxEntries);
+  DCHECK(std::is_sorted(event_times_.begin(), event_times_.end()));
+}
+
+bool UserInputTracker::FindAndConsumeInputEventsBefore(base::TimeTicks time) {
+  base::TimeTicks recent_input_event_time =
+      FindMostRecentUserInputEventBefore(time);
+
+  if (recent_input_event_time.is_null())
+    return false;
+
+  RemoveInputEventsUpTo(time);
+  return true;
+}
+
+base::TimeTicks UserInputTracker::FindMostRecentUserInputEventBefore(
+    base::TimeTicks time) {
+  RemoveOldInputEvents();
+
+  if (event_times_.empty())
+    return base::TimeTicks();
+
+  // lower_bound finds the first element >= |time|.
+  auto it = std::lower_bound(event_times_.begin(), event_times_.end(), time);
+
+  // If all times are after the requested time, then we don't have a time to
+  // return.
+  if (it == event_times_.begin())
+    return base::TimeTicks();
+
+  // |it| points to the first event >= the specified time, so decrement once to
+  // find the greatest event before the specified time.
+  --it;
+  base::TimeTicks candidate = *it;
+  DCHECK(candidate < time);
+
+  // If the most recent event is too old, then don't return it.
+  if (candidate < time - base::TimeDelta::FromSeconds(kMaxEventAgeSeconds))
+    return base::TimeTicks();
+
+  return candidate;
+}
+
+void UserInputTracker::RemoveOldInputEvents() {
+  RemoveInputEventsUpTo(GetOldestAllowedEventTime());
+}
+
+void UserInputTracker::RemoveInputEventsUpTo(base::TimeTicks cutoff) {

[Charlie Harrison, 2016/12/05 19:17:46]

This looks like it removes input events up to *and including* cutoff. Optional
if you want to clarify the name.

[Bryan McQuade, 2016/12/06 01:52:24]

Ah, interesting, I'd though of 'UpTo' as being inclusive, but I can see that's
not guaranteed. I renamed it.

+  cutoff =
+      std::max(RoundToRateLimitedOffset(cutoff), GetOldestAllowedEventTime());
+  most_recent_consumed_time_ = std::max(most_recent_consumed_time_, cutoff);
+  event_times_.erase(
+      event_times_.begin(),
+      std::upper_bound(event_times_.begin(), event_times_.end(), cutoff));
+}
+
+// static
+base::TimeTicks UserInputTracker::GetOldestAllowedEventTime() {
+  return base::TimeTicks::Now() -
+         base::TimeDelta::FromSeconds(kOldestAllowedEventAgeSeconds);
+}
+
+}  // namespace page_load_metrics