Bug 188144 - REGRESSION (r230817): Terrible performance when selecting text on Stash code review
Summary: REGRESSION (r230817): Terrible performance when selecting text on Stash code ...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: UI Events (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Wenson Hsieh
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2018-07-29 00:51 PDT by Wenson Hsieh
Modified: 2018-07-30 19:24 PDT (History)
13 users (show)

See Also:


Attachments
Patch (5.50 KB, patch)
2018-07-29 01:20 PDT, Wenson Hsieh
no flags Details | Formatted Diff | Diff
Patch (5.47 KB, patch)
2018-07-29 02:12 PDT, Wenson Hsieh
darin: review+
Details | Formatted Diff | Diff
Archive of layout-test-results from ews206 for win-future (13.02 MB, application/zip)
2018-07-29 15:52 PDT, Build Bot
no flags Details
Archive of layout-test-results from ews205 for win-future (12.97 MB, application/zip)
2018-07-29 18:51 PDT, Build Bot
no flags Details
Address review feedback. (7.44 KB, patch)
2018-07-30 12:50 PDT, Wenson Hsieh
no flags Details | Formatted Diff | Diff
Address review feedback (v2) (5.45 KB, patch)
2018-07-30 13:17 PDT, Wenson Hsieh
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Wenson Hsieh 2018-07-29 00:51:28 PDT
<rdar://problem/42642489>
Comment 1 Wenson Hsieh 2018-07-29 01:20:43 PDT
Created attachment 346018 [details]
Patch
Comment 2 Wenson Hsieh 2018-07-29 02:12:36 PDT
Created attachment 346024 [details]
Patch
Comment 3 Simon Fraser (smfr) 2018-07-29 09:01:30 PDT
Comment on attachment 346024 [details]
Patch

Is there a danger here that the event replacement in a queue of mixed mouseMoved and mouseForceChanged will cause an earlier event to effectively get the coordinates of a later event, meaning that with rapid mouse movement, you'll make the event coordinates appear to jump around erratically?
Comment 4 Wenson Hsieh 2018-07-29 11:14:00 PDT
So this mechanism works by finding an event in the queue that can be replaced by the incoming event, removing that enqueued event, and then appending the incoming event to the end of the queue.

The effect this should have is skipping over some events that otherwise would have been processed, rather than shuffling around the order of events, so I don’t think there’s a risk of sending mouse event coordinates to the page out of order.
Comment 5 Alexey Proskuryakov 2018-07-29 11:30:17 PDT
Is there a way to check how this will affect drawing when using a touchpad? The check for queue being non-empty seems like it could result in coalescing too much.
Comment 6 Wenson Hsieh 2018-07-29 14:15:51 PDT
(In reply to Alexey Proskuryakov from comment #5)
> Is there a way to check how this will affect drawing when using a touchpad?

Are there touchpads for drawing that support force click? Or do you mean drawing using a trackpad that supports force click? I couldn't test the former (since I don't have any touch pads, and couldn't find any that support force clicking after a quick Amazon search). For the latter, I surveyed a few online sketching tools (https://sketch.io, https://www.autodraw.com, http://kleki.com, https://drawisland.com), and they all seem to be working as expected...

> The check for queue being non-empty seems like it could result in coalescing
> too much.

Hm...I'm not quite sure I understand what you mean. Is the comment referring to the following condition?

    while (queue.size() > 1) {
        …
    }

Note that because of the break statement, we'll only ever replace a single mouse event in the queue with the incoming event. This means mouse event coalescing should work exactly as it does currently on trunk.
Comment 7 Build Bot 2018-07-29 15:52:00 PDT Comment hidden (obsolete)
Comment 8 Build Bot 2018-07-29 15:52:12 PDT Comment hidden (obsolete)
Comment 9 Alexey Proskuryakov 2018-07-29 17:06:18 PDT
I don't know the difference between a touchpad and a trackpad. And yes, the question applies to the trunk behavior too, which is only a few months old as I understand it.
Comment 10 Wenson Hsieh 2018-07-29 17:45:20 PDT
(In reply to Alexey Proskuryakov from comment #9)
> I don't know the difference between a touchpad and a trackpad.

By touchpad, I assumed you meant something like this: https://www.amazon.com/Wacom-Bamboo-Pen-and-Touch/dp/B002OOWC3S (as opposed to a trackpad, which comes built-in with MacBook Pro).

> And yes, the question applies to the trunk behavior too, which is only a few months old as I understand it.

From <https://trac.webkit.org/r231511>:

> When mousemove events come in faster than they can be processed, we should coalesce
> pending mousemoves that have not yet been sent to WebProcess. This has the effect of
> processing the most recent mousemove location, which is the old behavior that regressed.

Brian or Simon might be more familiar with the history here, but it seems that coalescing mousemove events that had not yet been dispatched to the web process was the preexisting behavior before macOS Mojave (refer to https://trac.webkit.org/export/230816/webkit/trunk/Source/WebKit/UIProcess/WebPageProxy.cpp and search for m_nextMouseMoveEvent). r230817 had regressed this, causing laggy mouse move behaviors, and r231511 later fixed this by restoring mouse move coalescing, but only in the case where the mouse is not down, or a force-click trackpad is not being used.

And so the patch here restores the old (pre-Mojave) behavior in this one remaining case where the user is dragging with the mouse down using a force-click enabled trackpad.
Comment 11 Build Bot 2018-07-29 18:50:48 PDT Comment hidden (obsolete)
Comment 12 Build Bot 2018-07-29 18:51:00 PDT Comment hidden (obsolete)
Comment 13 Simon Fraser (smfr) 2018-07-30 09:20:39 PDT
(In reply to Wenson Hsieh from comment #4)
> So this mechanism works by finding an event in the queue that can be
> replaced by the incoming event, removing that enqueued event, and then
> appending the incoming event to the end of the queue.
> 
> The effect this should have is skipping over some events that otherwise
> would have been processed, rather than shuffling around the order of events,
> so I don’t think there’s a risk of sending mouse event coordinates to the
> page out of order.

Say you receive:

move at 5,5
forceChange at 10,10

then you receive a move at 20,20

won't the queue then contain:
move at 20,20
forceChange at 10,10

thus flipping the coordinates?
Comment 14 Wenson Hsieh 2018-07-30 09:23:12 PDT
(In reply to Simon Fraser (smfr) from comment #13)
> (In reply to Wenson Hsieh from comment #4)
> > So this mechanism works by finding an event in the queue that can be
> > replaced by the incoming event, removing that enqueued event, and then
> > appending the incoming event to the end of the queue.
> > 
> > The effect this should have is skipping over some events that otherwise
> > would have been processed, rather than shuffling around the order of events,
> > so I don’t think there’s a risk of sending mouse event coordinates to the
> > page out of order.
> 
> Say you receive:
> 
> move at 5,5
> forceChange at 10,10
> 
> then you receive a move at 20,20
> 
> won't the queue then contain:
> move at 20,20
> forceChange at 10,10
> 
> thus flipping the coordinates?

No.

As I explained in the ChangeLog as well as the above comment, this mechanism works by finding an event in the queue that can be replaced by the incoming event, removing that enqueued event, and then appending the incoming event to the end of the queue.

So this:

  move at 5,5
  forceChange at 10,10

would become:

  forceChange at 10,10
  move at 20,20

...thereby skipping "move at 5,5".
Comment 15 Darin Adler 2018-07-30 09:30:08 PDT
Comment on attachment 346024 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=346024&action=review

> Source/WebKit/UIProcess/WebPageProxy.cpp:1953
> +    Vector<NativeWebMouseEvent, 1> eventsAfterReplacedEvent;

The algorithm here is unnecessarily inefficient. We can find the event to replace by iterating the Deque without modifying the Deque. Then we can replace it in place. There is no need to remove all the events after it and then re-append them. This could be the function:

    auto it = queue.rbegin();
    auto end = queue.rend();
    // Must not merge with the first event in the deque, since it is already being dispatched.
    if (it != end)
        --end;
    for (; it != end; ++it) {
        auto type = it->type();
        if (type == incomingEvent.type()) {
            LOG(MouseHandling, "UIProcess: replacing mouse event %s (queue size %zu)", webMouseEventTypeString(type), queue.size());
            *it = incomingEvent;
            return;
        }
        if (type != WebEvent::MouseMove && type != WebEvent::MouseForceChanged)
            break;
    }
    LOG(MouseHandling, "UIProcess: enqueueing mouse event %s (queue size %zu)", webMouseEventTypeString(incomingEvent.type()), queue.size());
    queue.append(incomingEvent);

I left the logging in, although I think it makes the code a little confusing.

> Source/WebKit/UIProcess/WebPageProxy.cpp:1966
> +        auto lastEvent = queue.takeLast();
> +        if (lastEvent.type() == incomingEvent.type()) {
> +            performedReplacement = true;
> +            break;
> +        }
> +
> +        eventsAfterReplacedEvent.append(WTFMove(lastEvent));

Two thoughts:

1) Could use lastEventType here instead of lastEvent.type().
2) Could write this a different way that I find clearer:

        if (lastEventType == incomingEvent.type()) {
            queue.removeLast();
            performedReplacement = true;
            break;
        }

        eventsAfterReplacedEvent.append(queue.takeLast());

There’s no real reason to structure the code so that the takeLast is shared.

But I like the rewritten version above even more -- replacing in place seems better.
Comment 16 Darin Adler 2018-07-30 09:32:02 PDT
Comment on attachment 346024 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=346024&action=review

>> Source/WebKit/UIProcess/WebPageProxy.cpp:1953
>> +    Vector<NativeWebMouseEvent, 1> eventsAfterReplacedEvent;
> 
> The algorithm here is unnecessarily inefficient. We can find the event to replace by iterating the Deque without modifying the Deque. Then we can replace it in place. There is no need to remove all the events after it and then re-append them. This could be the function:
> 
>     auto it = queue.rbegin();
>     auto end = queue.rend();
>     // Must not merge with the first event in the deque, since it is already being dispatched.
>     if (it != end)
>         --end;
>     for (; it != end; ++it) {
>         auto type = it->type();
>         if (type == incomingEvent.type()) {
>             LOG(MouseHandling, "UIProcess: replacing mouse event %s (queue size %zu)", webMouseEventTypeString(type), queue.size());
>             *it = incomingEvent;
>             return;
>         }
>         if (type != WebEvent::MouseMove && type != WebEvent::MouseForceChanged)
>             break;
>     }
>     LOG(MouseHandling, "UIProcess: enqueueing mouse event %s (queue size %zu)", webMouseEventTypeString(incomingEvent.type()), queue.size());
>     queue.append(incomingEvent);
> 
> I left the logging in, although I think it makes the code a little confusing.

Oh, I guess I should have read the discussion between you and Simon. You want to move the new event past the others.
Comment 17 Darin Adler 2018-07-30 09:35:42 PDT
Comment on attachment 346024 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=346024&action=review

>>> Source/WebKit/UIProcess/WebPageProxy.cpp:1953
>>> +    Vector<NativeWebMouseEvent, 1> eventsAfterReplacedEvent;
>> 
>> The algorithm here is unnecessarily inefficient. We can find the event to replace by iterating the Deque without modifying the Deque. Then we can replace it in place. There is no need to remove all the events after it and then re-append them. This could be the function:
>> 
>>     auto it = queue.rbegin();
>>     auto end = queue.rend();
>>     // Must not merge with the first event in the deque, since it is already being dispatched.
>>     if (it != end)
>>         --end;
>>     for (; it != end; ++it) {
>>         auto type = it->type();
>>         if (type == incomingEvent.type()) {
>>             LOG(MouseHandling, "UIProcess: replacing mouse event %s (queue size %zu)", webMouseEventTypeString(type), queue.size());
>>             *it = incomingEvent;
>>             return;
>>         }
>>         if (type != WebEvent::MouseMove && type != WebEvent::MouseForceChanged)
>>             break;
>>     }
>>     LOG(MouseHandling, "UIProcess: enqueueing mouse event %s (queue size %zu)", webMouseEventTypeString(incomingEvent.type()), queue.size());
>>     queue.append(incomingEvent);
>> 
>> I left the logging in, although I think it makes the code a little confusing.
> 
> Oh, I guess I should have read the discussion between you and Simon. You want to move the new event past the others.

Here’s a version that preserves that behavior, but does not use a vector:

    auto it = queue.rbegin();
    auto end = queue.rend();
    // Must not merge with the first event in the deque, since it is already being dispatched.
    if (it != end)
        --end;
    bool removedEvent = false;
    for (; it != end; ++it) {
        auto type = it->type();
        if (type == incomingEvent.type()) {
            queue.remove(it);
            break;
        }
        if (type != WebEvent::MouseMove && type != WebEvent::MouseForceChanged)
            break;
    }
    LOG(MouseHandling, "UIProcess: %s mouse event %s (queue size %zu)", removedEvent ? "replacing" : "enqueueing", webMouseEventTypeString(incomingEvent.type()), queue.size());
    queue.append(incomingEvent);

While it’s true that Deque::remove is not as efficient as Deque::removeLast, it is more efficient than moving all the elements out into a vector and then re-appending them.
Comment 18 Wenson Hsieh 2018-07-30 09:40:38 PDT
(In reply to Darin Adler from comment #17)
> Comment on attachment 346024 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=346024&action=review
> 
> >>> Source/WebKit/UIProcess/WebPageProxy.cpp:1953
> >>> +    Vector<NativeWebMouseEvent, 1> eventsAfterReplacedEvent;
> >> 
> >> The algorithm here is unnecessarily inefficient. We can find the event to replace by iterating the Deque without modifying the Deque. Then we can replace it in place. There is no need to remove all the events after it and then re-append them. This could be the function:
> >> 
> >>     auto it = queue.rbegin();
> >>     auto end = queue.rend();
> >>     // Must not merge with the first event in the deque, since it is already being dispatched.
> >>     if (it != end)
> >>         --end;
> >>     for (; it != end; ++it) {
> >>         auto type = it->type();
> >>         if (type == incomingEvent.type()) {
> >>             LOG(MouseHandling, "UIProcess: replacing mouse event %s (queue size %zu)", webMouseEventTypeString(type), queue.size());
> >>             *it = incomingEvent;
> >>             return;
> >>         }
> >>         if (type != WebEvent::MouseMove && type != WebEvent::MouseForceChanged)
> >>             break;
> >>     }
> >>     LOG(MouseHandling, "UIProcess: enqueueing mouse event %s (queue size %zu)", webMouseEventTypeString(incomingEvent.type()), queue.size());
> >>     queue.append(incomingEvent);
> >> 
> >> I left the logging in, although I think it makes the code a little confusing.
> > 
> > Oh, I guess I should have read the discussion between you and Simon. You want to move the new event past the others.
> 
> Here’s a version that preserves that behavior, but does not use a vector:
> 
>     auto it = queue.rbegin();
>     auto end = queue.rend();
>     // Must not merge with the first event in the deque, since it is already
> being dispatched.
>     if (it != end)
>         --end;
>     bool removedEvent = false;
>     for (; it != end; ++it) {
>         auto type = it->type();
>         if (type == incomingEvent.type()) {
>             queue.remove(it);
>             break;
>         }
>         if (type != WebEvent::MouseMove && type !=
> WebEvent::MouseForceChanged)
>             break;
>     }
>     LOG(MouseHandling, "UIProcess: %s mouse event %s (queue size %zu)",
> removedEvent ? "replacing" : "enqueueing",
> webMouseEventTypeString(incomingEvent.type()), queue.size());
>     queue.append(incomingEvent);
> 
> While it’s true that Deque::remove is not as efficient as Deque::removeLast,
> it is more efficient than moving all the elements out into a vector and then
> re-appending them.

Good point! I'll change this to `remove()` instead of using a separate Vector<NativeWebMouseEvent>.
Comment 19 Darin Adler 2018-07-30 09:40:42 PDT
I think it would be even clearer to move the entire "remove old event" into a separate function that just returns a boolean:

    static bool removeOldRedundantEvent(Deque<NativeWebMouseEvent>& queue, WebEvent::Type incomingEventType)
    {
        if (incomingEventType != WebEvent::MouseMove && incomingEventType != WebEvent::MouseForceChanged)
            return false;

        auto it = queue.rbegin();
        auto end = queue.rend();

        // Must not remove the first event in the deque, since it is already being dispatched.
        if (it != end)
            --end;

        for (; it != end; ++it) {
            auto type = it->type();
            if (type == incomingEventType) {
                queue.remove(it);
                return true;
            }
            if (type != WebEvent::MouseMove && type != WebEvent::MouseForceChanged)
                break;
        }
        return false;
    }

    bool removedEvent = removeOldRedundantEvent(queue, incomingEvent.type());
    LOG(MouseHandling, "UIProcess: %s mouse event %s (queue size %zu)", removedEvent ? "replacing" : "enqueueing", webMouseEventTypeString(incomingEvent.type()), queue.size());
    queue.append(incomingEvent);
Comment 20 Wenson Hsieh 2018-07-30 10:27:30 PDT
(In reply to Darin Adler from comment #19)
> I think it would be even clearer to move the entire "remove old event" into
> a separate function that just returns a boolean:
> 
>     static bool removeOldRedundantEvent(Deque<NativeWebMouseEvent>& queue,
> WebEvent::Type incomingEventType)
>     {
>         if (incomingEventType != WebEvent::MouseMove && incomingEventType !=
> WebEvent::MouseForceChanged)
>             return false;
> 
>         auto it = queue.rbegin();
>         auto end = queue.rend();
> 
>         // Must not remove the first event in the deque, since it is already
> being dispatched.
>         if (it != end)
>             --end;
> 
>         for (; it != end; ++it) {
>             auto type = it->type();
>             if (type == incomingEventType) {
>                 queue.remove(it);

Note: currently, WTF's Deque just has remove(iterator&), not remove(reverse_iterator&).

>                 return true;
>             }
>             if (type != WebEvent::MouseMove && type !=
> WebEvent::MouseForceChanged)
>                 break;
>         }
>         return false;
>     }
> 
>     bool removedEvent = removeOldRedundantEvent(queue, incomingEvent.type());
>     LOG(MouseHandling, "UIProcess: %s mouse event %s (queue size %zu)",
> removedEvent ? "replacing" : "enqueueing",
> webMouseEventTypeString(incomingEvent.type()), queue.size());
>     queue.append(incomingEvent);
Comment 21 Wenson Hsieh 2018-07-30 12:50:16 PDT
Created attachment 346088 [details]
Address review feedback.
Comment 22 Wenson Hsieh 2018-07-30 13:17:06 PDT
Created attachment 346091 [details]
Address review feedback (v2)
Comment 23 WebKit Commit Bot 2018-07-30 14:47:37 PDT
Comment on attachment 346091 [details]
Address review feedback (v2)

Clearing flags on attachment: 346091

Committed r234384: <https://trac.webkit.org/changeset/234384>
Comment 24 Darin Adler 2018-07-30 19:12:26 PDT
Later, someone should add Deque::remove(reverse_iterator&) and clean this up.
Comment 25 Darin Adler 2018-07-30 19:24:49 PDT
(In reply to Darin Adler from comment #24)
> Later, someone should add Deque::remove(reverse_iterator&) and clean this up.

Maybe not. std::deque works exactly the same way, so perhaps we should just leave it like this.