REGRESSION (r230817): Terrible performance when selecting text on Stash code review

• Component: UI Events
• Status: RESOLVED FIXED

[Wenson Hsieh]

<rdar://problem/42642489>

[Wenson Hsieh]

Created attachment 346018 [details]
Patch

[Wenson Hsieh]

Created attachment 346024 [details]
Patch

[Simon Fraser (smfr)]

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?

[Wenson Hsieh]

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.

[Alexey Proskuryakov]

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.

[Wenson Hsieh]

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

[EWS Watchlist]

Comment on attachment 346024 [details]
Patch

Attachment 346024 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/8694244

New failing tests:
http/tests/security/canvas-remote-read-remote-video-blocked-no-crossorigin.html

[EWS Watchlist]

Created attachment 346045 [details]
Archive of layout-test-results from ews206 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews206  Port: win-future  Platform: CYGWIN_NT-6.1-2.9.0-0.318-5-3-x86_64-64bit

[Alexey Proskuryakov]

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.

[Wenson Hsieh]

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

[EWS Watchlist]

Comment on attachment 346024 [details]
Patch

Attachment 346024 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/8695055

New failing tests:
imported/blink/transitions/unprefixed-transform.html

[EWS Watchlist]

Created attachment 346047 [details]
Archive of layout-test-results from ews205 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews205  Port: win-future  Platform: CYGWIN_NT-6.1-2.9.0-0.318-5-3-x86_64-64bit

[Simon Fraser (smfr)]

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

[Wenson Hsieh]

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

[Darin Adler]

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.

[Darin Adler]

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.

[Darin Adler]

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.

[Wenson Hsieh]

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

[Darin Adler]

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

[Wenson Hsieh]

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

[Wenson Hsieh]

Created attachment 346088 [details]
Address review feedback.

[Wenson Hsieh]

Created attachment 346091 [details]
Address review feedback (v2)

[WebKit Commit Bot]

Comment on attachment 346091 [details]
Address review feedback (v2)

Clearing flags on attachment: 346091

Committed r234384: <https://trac.webkit.org/changeset/234384>

[Darin Adler]

Later, someone should add Deque::remove(reverse_iterator&) and clean this up.

[Darin Adler]

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