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

Status: RESOLVED FIXED

(Firefox :: Session Restore, defect)

Description

[Xuân Baldauf]

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.

Comment 1

[David Teller [:Yoric] - still alive but not very active]

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

Comment 2

[Tim Taubert [:ttaubert] (inactive)]

tabbrowser._getTabForBrowser() is implemented the same. I think we should fix this and expose it rather than only fixing sessionstore.

Comment 3

[David Teller [:Yoric] - still alive but not very active]

Once bug 1039500 has landed, we can simply get rid of `_getTabForBrowser` in SessionStore.jsm and replace it with `window.gBrowser.getTabForBrowser`.

Comment 4

[TheRave]

addtab() give DEPRECATION WARNING: _getTabForBrowser` is now deprecated, please use `getTabForBrowser
You may find more details about this deprecation at: https://developer.mozilla.org/docs/Mozilla/Tech/XUL/Method/getTabForBrowser

Comment 5

[TheRave]

^^ in wrong tab posted. Please ignore this.

Comment 6

[Raphaël Lustin [:rlustin] [:rlubitel] [:lubitel]]

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

Comment 7

[Raphaël Lustin [:rlustin] [:rlubitel] [:lubitel]]

Hi David, I've submitted a patch for this bug. Can you review it please?
Thanks!

Comment 8

[Jared Wein [:jaws] (please needinfo? me)]

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.

Comment 9

[Tim Taubert [:ttaubert] (inactive)]

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!

Comment 10

[Raphaël Lustin [:rlustin] [:rlubitel] [:lubitel]]

Can you push it to Try please?

Comment 11

[Tim Taubert [:ttaubert] (inactive)]

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

Comment 12

[Raphaël Lustin [:rlustin] [:rlubitel] [:lubitel]]

Attachment: Firefox does not scale to 2500 tabs...

Preparing patch for checkin: update commit message with r=ttaubert

Comment 13

[Jared Wein [:jaws] (please needinfo? me)]

Thanks Raphael!

https://hg.mozilla.org/integration/fx-team/rev/eac86090909c

Comment 14

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/eac86090909c