1811115 - Stop iterating all tabs each time that one is removed

Status: RESOLVED FIXED

(Firefox :: Tabbed Browser, enhancement)

Description

[Oriol Brufau [:Oriol]]

Let's say you have a window with 1000 tabs, you right-click one and choose "Close Multiple Tabs > Close Other Tabs".

Then _beginRemoveTab will be called for each one of the 999 tabs, and it contains this code:

      // Remove this tab as the owner of any other tabs, since it's going away.
      for (let tab of this.tabs) {
        if ("owner" in tab && tab.owner == aTab) {
          // |tab| is a child of the tab we're removing, make it an orphan
          tab.owner = null;
        }
      }

• The 1st removed tab will iterate 1000 tabs
• The 2nd removed tab will iterate 999 tabs
• ...
• The 999th removed tab will iterate 2 tabs

In total, that's 500499 tab iterations, it's quadratic.

It seems to me that tabs could track the other tabs that they own, then only these could be iterated.

Comment 1

[:Gijs (out for now; he/him)]

(In reply to Oriol Brufau [:Oriol] from comment #0)

It seems to me that tabs could track the other tabs that they own, then only these could be iterated.

This sounds like it'd have a caching problem (ie when do we clear things from the other owned tabs list). The other solution I see is separating out the "clear owner tab" bit into a helper that takes a set of tabs about to be removed, and then iterates the list only once, which would produce linear + set lookup time behaviour, which is probably O(N log N) or similar, which is probably sufficient.

Do you have a performance profile showing what the practical impact of this is when you close 999 tabs or something? Half a million iterations sounds bad but I do wonder if it's the worst thing happening in this situation.

Comment 2

[:Gijs (out for now; he/him)]

We could probably also optimize the code so that if we're removing all but 1 tab we just don't bother doing this except by clearing it on the 1 remaining tab.

Or, much simpler, we could start using weak references for tab.owner, and then we might not need to do this at all! At least, I'm assuming the only reason we do this is to avoid hanging on to tabs that are being removed.

Comment 3

[Oriol Brufau [:Oriol]]

(In reply to :Gijs (he/him) from comment #1)

This sounds like it'd have a caching problem (ie when do we clear things from the other owned tabs list).

Not sure if I understand, it would be a matter of turning owner into an accessor property, so when setting it, the tab would be removed from the old owner's list of owned tabs, and be added into the new owner's list of owned tabs.

Do you have a performance profile showing what the practical impact of this is when you close 999 tabs or something? Half a million iterations sounds bad but I do wonder if it's the worst thing happening in this situation.

I think it wasn't the worst part, but it had some impact. I had a draft patch but my partition got some errors and doesn't mount, it's on my backlog to recover the files into a new drive. Then I will be able to test and provide some perf info.

(In reply to :Gijs (he/him) from comment #2)

we could start using weak references for tab.owner, and then we might not need to do this at all! At least, I'm assuming the only reason we do this is to avoid hanging on to tabs that are being removed.

Sounds a good idea. But probably turning owner into a getter that checks if the referenced tab has been removed, to avoid nondeterministic behavior and match the expectations of the current consumers.

Comment 4

[Niklas Baumgardner [:niklas]]

Attachment: Bug 1811115 - Make tab owner a weak reference. r=dao,mhowell

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/b44f42bf0f7b
Make tab owner a weak reference. r=dao,mhowell

Comment 6

[Norisz Fay [:noriszfay]]

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