Closed Bug 398965 Opened 14 years ago Closed 13 years ago

tab bar smooth-scrolling performance problems

Categories

(Toolkit :: XUL Widgets, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla1.9beta2

People

(Reporter: Gavin, Assigned: dao)

References

Details

(Keywords: perf)

Attachments

(8 files, 12 obsolete files)

32.66 KB, text/plain
Details
1.96 KB, text/plain
Details
1.69 KB, patch
Gavin
: review+
sayrer
: approval1.9+
Details | Diff | Splinter Review
6.56 KB, patch
Gavin
: review+
sayrer
: approval1.9+
Details | Diff | Splinter Review
506 bytes, text/html
Details
1.17 KB, text/plain
Details
1.69 KB, text/plain
Details
1.88 KB, patch
enndeakin
: review+
mconnor
: approval1.9+
Details | Diff | Splinter Review
bz, reed, and sayrer teamed up to find a performance problem with the tabbar smooth-scrolling code. Here's a log of bz's summary of the problem:
Flags: blocking1.9?
Attached file dtrace profile
(In reply to comment #0)
> bz, reed, and sayrer teamed up to find a performance problem with the tabbar
> smooth-scrolling code. Here's a log of bz's summary of the problem:

Bugzilla ate the rest of my comment. Trying again:

Attached file bz's IRC summary
Bugzilla won't let me paste this as a comment, because it hates me.
I will try to implement bz's suggestions.
"1)  Eliminate the linear search in favor of binary search or a cache + local linear search"

if only document.elementFromPoint would work for anonymous elements ...
Attached patch Patch for binary search (obsolete) — Splinter Review
This patch will (if I did everything correctly) convert scrollByIndex to a binary search. Can anyone test to see if this improves perf at all? I would also like your feedback on this, Dao.
I would like to go elementFromPoint path without looping, but right now it doesn't work for anonymous content, so ...
Comment on attachment 283978 [details] [diff] [review]
Patch for binary search

>+          var start = 0;
>+          var end = elements.length;

elements.length - 1
Comment on attachment 283978 [details] [diff] [review]
Patch for binary search

You have exactly the same code in the if branches, except for |edge += scrollBox.width;|.
Attached patch Patch 2 (obsolete) — Splinter Review
You're right. I was meant to have different conditions in each loop.
Attachment #283978 - Attachment is obsolete: true
> if only document.elementFromPoint would work for anonymous elements ...

That does a _lot_ more work than you need here.  In particular, it would not only do a linear search on the tabs, but a walk along the whole tree too, building up a full display list for the window, etc, etc.  Now it would all be in C++, so might be faster.... or might not.  The thing is, you have a lot more information than elementFromPoint is allowed to assume, so you can optimize a good bit over what it could do.
bz, did you do any profiling with the patch applied? Does it improve perf at all?
Attached patch Patch 3 (obsolete) — Splinter Review
Dao, it does need to be end = elements.length; instead of elements.length - 1, otherwise if the last element is the one partly offscreen and we're scrolling to the right, it'll go into an infinite loop.
Attachment #283980 - Attachment is obsolete: true
Attached patch binary search (obsolete) — Splinter Review
> Dao, it does need to be end = elements.length; instead of elements.length - 1,
> otherwise if the last element is the one partly offscreen and we're scrolling
> to the right, it'll go into an infinite loop.

this indicates that your algorithm isn't quite right
Attachment #284052 - Attachment is obsolete: true
Attachment #284079 - Flags: review?(gavin.sharp)
this one is tricky:

"Don't call _updateScrollButtonsDisabledState for intermediate steps of a smoothscroll; just update it when you finish  smoothscrolling"

We currently don't know if the scrolling has finished, the timer keeps on firing until you release the mouse button. Adding a check for the remaining scroll distance wouldn't be different from calling _updateScrollButtonsDisabledState.
> bz, did you do any profiling with the patch applied?

I haven't, nor have I without it applied.  reed and sayrer did all the profiling; I just helped analyze.

It looks like the steps to reproduce didn't make the bug.  They are:

1)  Open lots of tabs.
2)  Hover the mouse pointer over the tab bar.
3)  Scroll the mouse wheel.

I don't have a mousewheel, so I couldn't really profile this anyway.
> the timer keeps on firing 

Hmm.  I'd thought that eventually _stopSmoothScroll would fire, looking at the check in processFrame, etc.

> wouldn't be different from calling
_updateScrollButtonsDisabledState.

Except for not firing events or setting attributes. I wish we had data for how the time breakdown under _updateScrollButtonsDisabledState looks.
Ah, just read that patch.  Yeah, that might more or less cover it.
(In reply to comment #18)
> > the timer keeps on firing 
> 
> Hmm.  I'd thought that eventually _stopSmoothScroll would fire, looking at the
> check in processFrame, etc.

If you use one of the autorepeat buttons to scroll, _startScroll sets up a different timer and scrollByIndex (thereby ensureElementIsVisible -> processFrame -> _stopSmoothScroll) is only called as you release the button (bug 393006).
Would it make sense to give the button a disabled look while the user has it activated, though?
I think it makes sense, based on my daily use of the buttons.
fixed some nits in _distanceScroll
Attachment #284079 - Attachment is obsolete: true
Attachment #284096 - Flags: review?(gavin.sharp)
Attachment #284079 - Flags: review?(gavin.sharp)
I assume there isn't enough locality to make the O(1) cache feasible, by the way, or that the constant is too big, which is why we're doing binary search?
I'm not sure what exactly you want to cache. boxObject.x for each element? Keeping that up to date sounds a bit painful, as elements can be resized, moved etc. The scroll width would work as a checksum to invalidate the cache for the tab bar (we could even assume the same width for all tabs), but it would cause problems with a customized tab bar or other random scroll boxes.
> I'm not sure what exactly you want to cache.

The point of this code is to locate the index of the tab that is at the left-hand edge of the visible part of the tabbar right now, right?

Depending on how much that can change, it might make sense to cache the last index found.  For example, if in the common case it either doesn't change at all or only changes by 1, you could check the tab at the last-found index, then if it's not the right tab check the next or previous one (depending on which direction you need to go from it), then fall back on binary search on the relevant part of the list.

Of course none of that is relevant if there isn't in fact locality of reference here; that's for someone who knows how this code is used to decide.
One mouse wheel scroll action usually spans 3 tabs (but the number comes from the OS and can vary) and continuous button-scrolling (ending with a scrollByIndex) can span any number of tabs. As if this wasn't enough, there are other ways to scroll that don't use scrollByIndex (e.g. Ctrl+1 / Ctrl+9), meaning that the next time scrollByIndex is used, the "last index found" will be worthless.
OK.  Sounds like binary search might be the simplest thing to do, then.
Attached patch binary search v3 (obsolete) — Splinter Review
RTL fixed
Attachment #284096 - Attachment is obsolete: true
Attachment #284448 - Flags: review?(gavin.sharp)
Attachment #284096 - Flags: review?(gavin.sharp)
Attachment #284081 - Flags: review?(gavin.sharp) → review+
Assignee: nobody → dao
What do you think of using Array.prototype.slice.call(elements, 0).reverse() instead of the LTR conditionals in _elementFromPoint? Simpler code at the cost of possibly reduced performance in the RTL case, but I'm not sure how much of a perf hit it would really be.

I'm not sure I understand the changes to scrollByPixels and _startScroll... are they unrelated RTL fixes?
(In reply to comment #30)
> What do you think of using Array.prototype.slice.call(elements, 0).reverse()
> instead of the LTR conditionals in _elementFromPoint?

sounds good to me

> I'm not sure I understand the changes to scrollByPixels and _startScroll... are
> they unrelated RTL fixes?

No, they are directly related to RTL. Previously, scrollByPixels and scrollByIndex inverted their arguments for RTL scrollboxes, which I think is fundamentally wrong. That became clear when I used the scroll wheel, which passes a positive or negative value to scrollByIndex, depending on the *physical* scroll direction. Because of this, wheel scrolling is currently only functional at LTR. To make everything consistent, the public methods now take physical arguments and the index inversion is moved to _startScroll, which is called as you click on the scrollbuttons (their physical direction is flipped at RTL).
Attached patch binary search v3.1 (obsolete) — Splinter Review
Attachment #284448 - Attachment is obsolete: true
Attachment #284528 - Flags: review?(gavin.sharp)
Attachment #284448 - Flags: review?(gavin.sharp)
Attachment #284081 - Flags: approval1.9?
> Simpler code at the cost of possibly reduced performance in the RTL case

Can we get a number here?  I suspect it's small, as you say, but it would be good to quantify it instead of just blithely saying "who cares about those Arabic and Hebrew speakers".  ;)

Comment on attachment 284096 [details] [diff] [review]
binary search v2 (checked in)

Gavin said he wants to put RTL issues off to a separate bug.
Attachment #284096 - Attachment is patch: false
Attachment #284096 - Flags: review?(gavin.sharp)
Attachment #284528 - Attachment is obsolete: true
Attachment #284528 - Flags: review?(gavin.sharp)
Attachment #284096 - Attachment is obsolete: false
Attachment #284096 - Attachment is patch: true
Version: unspecified → Trunk
Blocks: 399657
Attachment #284096 - Flags: review?(gavin.sharp) → review+
Attachment #284096 - Flags: approval1.9?
Attachment #284081 - Flags: approval1.9? → approval1.9+
Attachment #284096 - Flags: approval1.9? → approval1.9+
attachment 284081 [details] [diff] [review]:
Checking in toolkit/content/widgets/scrollbox.xml;
/cvsroot/mozilla/toolkit/content/widgets/scrollbox.xml,v  <--  scrollbox.xml
new revision: 1.28; previous revision: 1.27
done

attachment 284096 [details] [diff] [review]
Checking in toolkit/content/widgets/scrollbox.xml;
/cvsroot/mozilla/toolkit/content/widgets/scrollbox.xml,v  <--  scrollbox.xml
new revision: 1.29; previous revision: 1.28
done
Status: NEW → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9 M9
This is still waaaaaaay too slow. I have 234 tabs open from repeatedly selecting "Open All in Tabs" from the "Latest Headlines" live bookmark, and my CPU goes to a steady 35% when I attempt to scroll the tabs using my mouse scroll wheel and holding it down. After holding down the scroll wheel for two minutes or so, it took another three/four minutes to clear out and drop back down to zero CPU. My scroll wheel allows me to hold it down for a direction, so it constantly sends scroll notifications to the browser.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
However, I would like to note that with 234 tabs open, Minefield was only eating 267.5MB of RAM, which is a huge improvement over Firefox 2.
I suppose we could suppress some mouse scroll ticks so they don't happen too fast? I'll see what I can come up with.
This is what I had in mind. Does this improve things at all, reed?
Attachment #284804 - Flags: review?(gavin.sharp)
(In reply to comment #39)
> This is what I had in mind. Does this improve things at all, reed?

While I now can see the tabs actually scrolling somewhat instead of just freezing completely, it's seems really jerky. It'll scroll for a second, stop, scroll some more, stop, etc. Kinda reminds me of the videos in science that I used to see such that the blood flows for a bit, stops, flows some more, stops, etc. (all due to the heart pumping the blood). However, this is definitely a step in the right direction, though!
Thats because the scrollbox will ignore mouse ticks for a very, very short time in order to stop the freezing. This was bz's idea no.3.

Reed, you can adjust the ignore time by changing the magic '400' in the patch, thats the number of milliseconds to ignore mouse ticks after the last one. I would very much appreciate it if you could find a value that felt less jerky, but still prevented freezing.
(In reply to comment #39)
> Created an attachment (id=284804) [details]
> Ignore mouse ticks for a fraction of a second
> 
> This is what I had in mind. Does this improve things at all, reed?

We could disable mouse wheel scrolling completely to not disturb the CPU at all ;)

Seriously, I think that's the wrong approach. Mouse wheel scrolling should be as fast as the user wants it to be.

(In reply to comment #36)
> My scroll wheel allows me to hold it down for a direction, so
> it constantly sends scroll notifications to the browser.

That's quite different from to the normal "roll the wheel -> scroll X lines" case, which imho must remain fully responsive. I think Michaels patch could be used as a workaround here, but with a *much* lower timeout.
Attachment #284804 - Attachment is obsolete: true
Attachment #284804 - Flags: review?(gavin.sharp)
This reduces it to 150ms which seems very reasonable to me. I created a testcase which would measure how many "ticks" an average scrolling could get in 1 second, and my average was 16 (1 every 62.5 ms). Even with this patch the scrolling didn't feel "obstructed".
Attachment #284822 - Flags: review?(gavin.sharp)
Attachment #284081 - Attachment description: dispatch UpdatedScrollButtonsDisabledState only if there are updates → dispatch UpdatedScrollButtonsDisabledState only if there are updates (checked in)
Attachment #284096 - Attachment description: binary search v2 → binary search v2 (checked in)
Reed, do you have an idea how often the scroll notifications are sent with your mouse?
Reed, can you give this a try? The numbers are guesses.
Comment on attachment 284822 [details] [diff] [review]
Ignore mouse ticks for even less time

150 is still too high. With my normal mouse wheel I actually reach the 50 ms border from my latest patch.

The point is not that 150 with smooth scrolling would /feel/ sluggish, but in fact it *would be* slower. Accelerating the wheel should accelerate the scrolling.
Attachment #284822 - Attachment is obsolete: true
Attachment #284822 - Flags: review?(gavin.sharp)
It's worth reprofiling with this patch in to see what the remaining bottlenecks are.
Reed, please use this to measure your average DOMMouseScroll interval length.
Attachment #284831 - Attachment is obsolete: true
Attachment #285153 - Flags: review?(gavin.sharp)
Actually if smooth scrolling is disabled for <50, there's no reason to not apply the <10 rule to all horizontal scrollboxes.
Secondly I think Michael was right to stop the event propagation in all cases.
Attachment #285153 - Attachment is obsolete: true
Attachment #285165 - Flags: review?(gavin.sharp)
Attachment #285153 - Flags: review?(gavin.sharp)
Attached file scrolling down results
Results from attachment 284920 [details] while scrolling down. Note that the page went completely crazy at the end and started giving completely ridiculous numbers even though I didn't do anything differently.
Attached file scrolling up results
Results from attachment 284920 [details] while scrolling up.
Thanks Reed. Not sure what happened at the end, but the first dozen numbers should be good enough.
Moved a line, last version was flawed under certain circumstances.
Attachment #285165 - Attachment is obsolete: true
Attachment #285682 - Flags: review?(gavin.sharp)
Attachment #285165 - Flags: review?(gavin.sharp)
Flags: wanted1.9+
Flags: blocking1.9?
Flags: blocking1.9-
Target Milestone: mozilla1.9 M9 → mozilla1.9 M10
Attachment #289297 - Flags: review?(enndeakin)
Attachment #289297 - Flags: review?(enndeakin) → review+
Attachment #289297 - Flags: approval1.9?
dao: did you want to land both patches?
(In reply to comment #56)
> dao: did you want to land both patches?

"both patches"? Only one of the ones not checked-in has review...
(In reply to comment #57)
> (In reply to comment #56)
> > dao: did you want to land both patches?
> 
> "both patches"? Only one of the ones not checked-in has review...
> 

Right - and so why are we approving/landing only one of them?
(In reply to comment #58)
> Right - and so why are we approving/landing only one of them?

Because they are completely separate issues. One fixes a bug (avoid closure) while the other tries to make smooth scrolling better for people with mice that send a high number of mouse events (ignore event ...).
Attachment #289297 - Flags: approval1.9? → approval1.9+
attachment 289297 [details] [diff] [review]:

Checking in toolkit/content/widgets/scrollbox.xml;
/cvsroot/mozilla/toolkit/content/widgets/scrollbox.xml,v  <--  scrollbox.xml
new revision: 1.31; previous revision: 1.30
done
Keywords: checkin-needed
Attachment #289297 - Attachment description: avoid closure → avoid closure (checked in)
Status: REOPENED → ASSIGNED
Comment on attachment 285682 [details] [diff] [review]
ignore event for t < 10, disable smooth scrolling for t < 50 (v3)

Reed, I don't know how bad or annoying this issue is, using a mouse like yours. If you think this should make Firefox 3, I guess it would help if you could test the patch.
Comment on attachment 285682 [details] [diff] [review]
ignore event for t < 10, disable smooth scrolling for t < 50 (v3)

This patch has been sitting around for long enough. We're obviously going to finish 1.9 without it, and seemingly the issue isn't serious enough anyway. If somebody still thinks we should do something about short scroll event intervals, a new bug should be filed specifically about it.
Attachment #285682 - Attachment is obsolete: true
Attachment #285682 - Flags: review?(gavin.sharp)
Status: ASSIGNED → RESOLVED
Closed: 14 years ago13 years ago
Resolution: --- → FIXED
Depends on: 430925
Duplicate of this bug: 407976
You need to log in before you can comment on or make changes to this bug.