Firefox does not scale to 2500 tabs: function ssi_getTabForBrowser() has Ω(n) performance while it should have O(1) performance

RESOLVED FIXED in Firefox 36

Status

()

RESOLVED FIXED
4 years ago
4 years ago

People

(Reporter: baldauf--2015--bugzilla.mozilla.org, Assigned: rlustin, Mentored)

Tracking

({perf})

30 Branch
Firefox 36
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [lang=js][good second bug])

Attachments

(2 attachments)

(Reporter)

Description

4 years ago
How to reproduce:

Restore a session with 8700 tabs, where in one window, there are 2500 tabs. The "tree style tab" extension is active.

Expected result:

Restoring such an amount of tabs should take maybe 1 minute.

Actual result:

Restoring such an amount of tabs actually takes about 30 minutes.

Analysis:

One culprit for the performance degradation seems to be the implementation of ssi_getTabForBrowser() (see https://hg.mozilla.org/releases/mozilla-release/annotate/f29ab60028d4/browser/components/sessionstore/src/SessionStore.jsm#l2968 ). That function is called in many different places, one being ssi_receiveMessage() which happens each time a tab is opened or closed. This effectively means that restoring tabs has Ω(n^2) performance, which in turn means that starting firefox has Ω(n^2) performance. If n=2500, that means a lot of CPU time and user's lifetime spent unneccessarily.
Ouch, I thought we had rewritten this method a long time ago. Thanks for noticing this.

This is a pretty simple bug that can be fixed with 5 to 10 lines of code plus documentation.

We need to create a WeakMap `_tabForBrowser`. In method `onTabAdd`, we should add the binding from `aTab.linkedBrowser` to `aTab` in `_tabForBrowser`. In method `getTabFromBrowser`, we should fetch the tab from `_tabForBrowser`.
Mentor: dteller
Keywords: perf
Whiteboard: [lang=js][good second bug]
tabbrowser._getTabForBrowser() is implemented the same. I think we should fix this and expose it rather than only fixing sessionstore.
Once bug 1039500 has landed, we can simply get rid of `_getTabForBrowser` in SessionStore.jsm and replace it with `window.gBrowser.getTabForBrowser`.
Comment hidden (off-topic)
Comment hidden (off-topic)
Created attachment 8511525 [details] [diff] [review]
Firefox does not scale to 2500 tabs: :  function ssi_getTabForBrowser() has Ω(n) performance while it should have O(1) performance
Attachment #8511525 - Flags: review?(dteller)
Hi David, I've submitted a patch for this bug. Can you review it please?
Thanks!
Flags: needinfo?(dteller)
Comment on attachment 8511525 [details] [diff] [review]
Firefox does not scale to 2500 tabs: :  function ssi_getTabForBrowser() has Ω(n) performance while it should have O(1) performance

Review of attachment 8511525 [details] [diff] [review]:
-----------------------------------------------------------------

In case Tim can get to it sooner.
Attachment #8511525 - Flags: review?(ttaubert)
Comment on attachment 8511525 [details] [diff] [review]
Firefox does not scale to 2500 tabs: :  function ssi_getTabForBrowser() has Ω(n) performance while it should have O(1) performance

Review of attachment 8511525 [details] [diff] [review]:
-----------------------------------------------------------------

This looks great, thanks a lot Raphaël!
Attachment #8511525 - Flags: review?(ttaubert)
Attachment #8511525 - Flags: review?(dteller)
Attachment #8511525 - Flags: review+
Can you push it to Try please?
Flags: needinfo?(ttaubert)
(In reply to Raphaël Lustin [:rlustin] [:rlubitel] [:lubitel] from comment #10)
> Can you push it to Try please?

Ran all sessionstore tests locally and they all pass. This is a very self-contained change that we don't need to push to try I think. But certainly good thinking!

Want to prepare it for checkin-needed? :)
Flags: needinfo?(ttaubert)
Assignee: nobody → raphael
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Flags: needinfo?(dteller)
Created attachment 8511969 [details] [diff] [review]
Firefox does not scale to 2500 tabs...

Preparing patch for checkin: update commit message with r=ttaubert
Keywords: checkin-needed
Thanks Raphael!

https://hg.mozilla.org/integration/fx-team/rev/eac86090909c
Keywords: checkin-needed
Whiteboard: [lang=js][good second bug] → [lang=js][good second bug][fixed in fx-team]
https://hg.mozilla.org/mozilla-central/rev/eac86090909c
Status: ASSIGNED → RESOLVED
Last Resolved: 4 years ago
Resolution: --- → FIXED
Whiteboard: [lang=js][good second bug][fixed in fx-team] → [lang=js][good second bug]
Target Milestone: --- → Firefox 36
You need to log in before you can comment on or make changes to this bug.