Closed Bug 1374338 Opened 7 years ago Closed 6 years ago

Text selection in TreeHerder is very slow

Categories

(Core :: Layout, defect, P3)

defect

Tracking

()

RESOLVED FIXED
mozilla59
Performance Impact medium
Tracking Status
firefox57 --- wontfix
firefox58 --- wontfix
firefox59 --- fixed

People

(Reporter: tcampbell, Assigned: agashlin)

References

(Blocks 1 open bug)

Details

(Keywords: perf)

Attachments

(1 file)

STR
1) Go to treeherder.mozilla.org
2) Click (+) to expand all jobs
3) Find busy part of page and mouse select job list

I see repeated 1s pauses.

Profile: http://bit.ly/2rIQ98H
mostly painting.
Though selection handling could be optimized too.
Component: DOM: Core & HTML → Layout
The bulk of the time is being spent in nsRange::IsNodeSelected()
Priority: -- → P3
This is called from nsIFrame::IsSelected(), and can slow down various kinds of reflow.  I have seen this come up in a fair number of different profiles and I think it should be fixed for QF.

Mats, are you interested in taking it by any chance?
Flags: needinfo?(mats)
Whiteboard: [qf]
Blocks: FastReflows
Whiteboard: [qf] → [qf:p1]
I just dropped a breakpoint into nsRange::IsNodeSelected and performed the STR, to see what was going on.  (I selected a significant portion of the job list for a single push, and then I enabled the breakpoint, and then the breakpoint was triggered when I hovered the selected region, I think).

When I hit this, ranges->Count() is 92, which seems quite large.  Even though the user (me) only intended to select one contiguous range, it looks like we're splitting up the selection into many many distinct sub-ranges (which you can see on the screen when you try to select a job list on treeherder -- it's all split up around the parenthesis for some reason).

So we end up creating, working with, and destroying a temporary 92-entry hash table ("ancestorSelections") for every single frame that we paint in that range, I think.
(In reply to Daniel Holbert [:dholbert] from comment #5)
> When I hit this, ranges->Count() is 92, which seems quite large.  Even
> though the user (me) only intended to select one contiguous range, it looks
> like we're splitting up the selection into many many distinct sub-ranges
> (which you can see on the screen when you try to select a job list on
> treeherder -- it's all split up around the parenthesis for some reason).

Yes, this is due to the way that table cell selection works.  We represent those selections as separate ranges, see <https://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/layout/generic/nsFrameSelection.cpp#2117> which calls nsFrameSelection::CreateAndAddRange() <https://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/layout/generic/nsFrameSelection.cpp#2856>.
Whiteboard: [qf:p1] → [qf:p2]
Assignee: nobody → agashlin
Status: NEW → ASSIGNED
I think part 1 of bug 1216001 is hurting us here, we go through every range in a selection in order to build up |sortedRanges|, but if that selection has a lot of irrelevant ranges this is going to outweigh the benefit of having |sortedRanges| on hand to binary search.

Is there a reason we need to search over only those ranges we encountered on ancestors? I think that if we just do a binary search across all the ranges in a selection anything we hit will be valid for considering the node selected. Once we're doing log(N) comparisons a little more N (everything in the selection vs. those listed in ancestors) isn't going to matter against what we save not building |ancestorSelectedRanges| and iterating straight over the whole selection. I may misunderstand the mechanics of selection vs range, though.

In any case, above (comment 8) is my patch which does just that, it seems to work well with getting the profile down for IsNodeSelected in Treeherder (I've been testing with Ctrl-A), the GitHub example in bug 1396667, and it is pretty much the same for the DXR page in bug 1216001 (no surprise as there was also caching added there). For Treeherder the IsNodeSelected samples went from 400ms to 20 ms. For GitHub, from 150ms to 50ms, 2/3 of that is just adding the selections to the hash table, we can possibly work around that with the assumption that there are very few selections.
Daniel, does it seem reasonable to just binary search through the whole selection rather than try to filter it first? It certainly seems to work but I'm not sure if I'm misunderstanding something about some esoteric uses of selections. Or if you can suggest someone else to needinfo?, please do, I see mats is already ni?d but that was a few months ago.
Flags: needinfo?(dholbert)
I don't really know how selections/ranges work, so I can't offer an offhand sanity-judgement without first doing a bunch of investigation myself.

Note that Mats was on vacation for a while (which is probably part of why his needinfo went quiet), but he recently returned [though he's probably recovering from backlog a bit].  I expect his opinion here would be more useful than mine, given his work on bug 1216001, which is strongly related as you noted.
Flags: needinfo?(dholbert)
One possible issue is that my patch doesn't care whether it finds a collapsed range, I don't know how important this is. If it isn't necessary then we can avoid all those calls to Collapsed() when deciding whether to take a range's selection, otherwise if collapsed ranges must never be considered overlapping we'll need to be more careful during the search for an overlapping range.
Jet -- if Mats is underwater, can you recommend someone else to weigh in here? We're pretty new to this.
Flags: needinfo?(bugs)
Keywords: perf
Blocks: 1112352
IIRC, excluding collapsed ranges is just an optimization, to avoid adding
them to the current data structures, doing ComparePoints() on them, and
possibly putting the node on a slower painting path if there's an overlap.

Maybe we can deal with them in your patch too? roughly like this:

if (result == 0) {
  if (!range->Collapsed())
    return true;
  if ("start of range at middle+1 < node end")
    result = 1;
  else if ("end of range at middle-1 > node start")
    result = -1;
  else
    return false;
}

Not sure if it's worth it though...
Other than that, your patch looks fine to me.
Flags: needinfo?(mats)
Comment on attachment 8906218 [details]
Bug 1374338 - Search all ranges to avoid filtering

I took mats' advice to handle collapsed selections within the binary search (though I reversed the sense of the conditions as it seemed more consistent). Sorry I have left this sitting for so long.

Try on Linux at least looks good: https://treeherder.mozilla.org/#/jobs?repo=try&revision=11aa08c29a3fc47ec60dfdb0b91f2778a10aceac

I'd ignore the 1-2 interdiff, it picks up a lot of intermediate changes.
Flags: needinfo?(bugs)
Attachment #8906218 - Flags: review?(mats)
Comment on attachment 8906218 [details]
Bug 1374338 - Search all ranges to avoid filtering

https://reviewboard.mozilla.org/r/177976/#review210300

::: dom/base/nsRange.cpp:218
(Diff revision 2)
>          ancestorSelections.PutEntry(selection);
> +        if (prevSelection != selection) {
> +          prevSelection = selection;
> +          ancestorSelections.PutEntry(selection);
> +        }

You forgot to remove the first PutEntry call.
r=mats with that.
Attachment #8906218 - Flags: review?(mats) → review+
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/b2db8b6d26d0
Search all ranges to avoid filtering r=mats
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/b2db8b6d26d0
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
Depends on: 1424839
Performance Impact: --- → P2
Whiteboard: [qf:p2]
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: