Latest topics > Look back on the history of Tree Style Tab until the performance improvement at version 4.0

Look back on the history of Tree Style Tab until the performance improvement at version 4.0 - Mar 26, 2024

（日本語版はこちら）

I recently released version 4.0 of Tree Style Tab (TST) add-on, which provides vertical and indented tab bar UI for Firefox. The significant change in this version is the performance improvement in responsiveness and CPU/RAM usage, particularly in cases with a very large number of tabs. Here is reference data regarding resource usage related to TST, measured using about:memory in my development environment (Windows 11, Firefox 122.0.1, 536 tabs), immediately after Firefox started and restored the last session, and after TST was fully initialized:

	TST 3.9.22	TST 4.0	Reduced RAM usage between TST 3.9.22 and TST 4.0
Main process	10.87MB	6.62MB	39.1% reduced
Extensions process	143.92MB	83.35MB	42.1% reduced

I feel that the responsiveness has greatly improved when opening tabs and collapsing/expanding the tree. You may feel this effect even more if you have thousands of tabs or if Firefox's processes live for an extended period.

There are some compatibility issues with customization by user style sheets and/or helper addons. I have already researched and updated known helper addons, but there may still be some broken behaviors.

Most of improvements in this version are based on a development project sponsored by the Waterfox. Thank you very much, Alex!

Abstract about what I did to improve performance

In short: the key change was switching the UI to virtual scrolling.

In previous versions (up until version 3.x), TST retained DOM nodes for HTML elements corresponding to all existing tabs, including collapsed tabs and those out of the viewport. TST 4.0 now holds DOM nodes only for tabs within/near the viewport (up to three pages: the visible range and the preceding/following pages for smooth scrolling). DOM nodes for tabs under collapsed trees and far from the viewport are no longer held.

You'll observe tab elements being dynamically spawned and despawning as you scroll, through the DOM inspector.

Until TST 3.x, there were performance bottlenecks due to the large number of DOM nodes:

• Favicons's data: URL (Base64 encoded data of icon images) for each tab consumed RAM even when they weren't visible.
• The cache used to speed up initialization of the sidebar UI stored the entire HTML content of the sidebar, leading to bloating with many tabs, increased RAM usage, longer GPU time for serialization to JSON, and more disk I/O - resulting in significant performance degression.
• The time to match DOM nodes with CSS selectors and redraw them appeared to increase proportionally with the number of DOM nodes.
• Overall, resources were wasted on tabs that were rarely visible.

On the other hand, with TST 4.0 and later, these bottlenecks have been alleviated due to the recuved number of DOM nodes,

I researched other addons similar to TST and found that none of themhave implemented virtual scrolling. This doesn't necessarily mean TST is innovative - it may indicate that TST's basic architecture wasn't optimal and required such a workaround for improved performance, while other implementations didn't need such a workaround.

As some know, virtual scrolling isn't a next-generation technology but is popular today. I had been thinking of introducing it for many years because it definitely improves TST's performance. So, why didn't I do it sooner? There were two reasons: historically, TST's internal design wasn't conducive to such an architecture, and I had a significant misunderstanding about the architecture itself.

The evolution of TST's design towards virtual scrolling-friendly architecture

The fundamental principle: separation of data model and UI

One of the primary scenarios where virtual scrolling is employed is when rendering tables with very large datasets. For example, the website jspreadsheets lists various JavaScript libraries for rendering tables with large datasets, some of which prominently feature keywords like "virtual scroll" and "virtual DOM" in their descriptions. I also used one of them Tabulator to implement an addressbook addon for Thunderbird 3 years ago. Thunderbird 's thread pane is also implemented with virtual scrolling on recent versions.

The common situation of these examples is: there is large number of uniformed data at first, and later a table (spreadsheet) is prepared as a view for the data. Virtual scrolling isn't just limited to spreadsheet applications like MS Excel; even Firefox utilizes it. Firefox has its own C++-based implementation known as the "XUL tree", which has been in use for over 20 years, particularly in areas such as bookmarks, history, and sidebar UI. Thunderbird used XUL tree until the thread pane has re-written with pure JS.

In the most high-performance implementations of virtual scrolling, such as the XUL tree, a fixed number of cells are prepared, and the rendered data within them is dynamically changed based on the scroll position.

This type of implementation does not enable scrolling by pixels, making it easily identifiable as a virtual scroll.

WebExtensions API-based add-ons are expected to offer a virtual scrolling UI effortlessly. This is because you can obtain information about individual tabs as instance objects of tabs.Tab through APIs like tabs.query(). They are just data model, and you addon author can implement any UI without limitation. Virtual scrolling is already available for bookmarks, history, and more others, thus we surely can do it for tabs (and TST 4.0 indeedly does it.)

But why I didn't it on TST 3.x and older? It is because old versions of TST (until 3.x, including 0.x) are based on the design of Firefox's native tabs unifying data model and UI. Let's delve into how native tabs are implemented in Firefox to understand the context.

Firefox's UI is (was) unified with data model

Firefox's UI is built on XUL.HTML, CSS and JS. All UI widgets, such as the address bar, toolbar buttons, tabs, and more, existed as DOM nodes of HTML or XUL elements on the DOM tree.

The most important thing is: data model and UI widget are unified on Firefox's UI layer, in other words a XUL element behaves both as data model and UI widget.

I think it is because the Mozilla Browser (aka SeaMonkey, the predecessor of Firefox) was aimed not only to be a browser but a Web technology based application development platform also, like the Electron today. Applications might be developed so easily if we can use rich UI widgets with just writing XUL elements. For example, you can implement a color picker, a date picker with calendar, or more something, just with an HTML input element. Firefox's UI was built on some basic XUL elements: "switchable tabs" (<tab>), "auto-scrollable boxes" (<arrowscrollbox>), and so on, and implemented tabbed browser like behaviors by some tricks: creating and adding a <tab> element under the <tabs> in the <tabbrowser> for a request to open a tab, and adding a <browser> (an enhanced version of <iframe>) under the <tabpanels>,

Moreover, some special behavior of widgets was implemented by CSS tricks like:

• When a tab is added to the <tabs> (the tab bar), applying overflow:hidden and make overflowed tabs accessible with scrolling.
• Pinned tabs are detached from the regular rendering flow by position:fixed, and positioned at leftmost of the tab bar.
  • Multiple pinned tabs are placed in different position with margin-left of them.
  • To prevent pinned tabs cover over regular tabs, move regular tabs to the right with padding-left.

A customization method userChrome.css strongly depends on this background: behaviors are flexible, not fixed. "XUL add-ons", like old versions TST (0.x), loaded their own custom JS files into the namespace of Firefox's UI itself and it was allowed to replace internal functions or methods of DOM nodes, overriding style definitions, and more. So "tree of tabs" feature on TST 0.x was also implemented with:

• Switch the contents orientation of the parent element of <tab>s by changing its orient attribute from horizontal to vertical, like changing CSS flex-direction from row to column today.
• Store parent-child relationship of tabs as attributes or custom properties of <tab>s.
• Indicate depth of trees with margin-left of <tab>s.
• Find tabs based on the tree structure via querySelector() (CSS selector) or DOM3 XPath APIs (XPath expressions) matching to specific <tab>s.

The user-friendliness of developing local apps or customizing apps for web developers has been one of Firefox's major features since its inception. But there is a demerit: data model and UI widget is unified thus it is hard to do something beyond the general behavior of a widget. I mentioned that pinned tabs were implemented with some CSS tricks as above. This implies that <tab>s must be placed under a scrollable container <tabs>, meaning we cannot detach pinned tabs, which we don't want to scroll, from it and attach them to another parent element. It seems that the CSS tricks method was chosen to implement the desired behavior regardless, bypassing the limitation.

Such a design is not friendly to some kind architecture like virtual scrolling. We cannot remove <tab>s from the DOM tree easily because they are expected to be there as data models, and the requirement conflicts with the concept: adding and removing UI widgets dynamically according to the scroll position.

Developing APIs to access <tab>s as data models and preventing loopholes like querySelector() may allow us to implement virtual scrolling on such a design, but <tab>s detached from DOM tree are too rich to be used just as data models, and their features (event bubbling, querying DOM elements, and others) cannot be used well.

I believe I couldn't introduce virtual scrolling to TST because the UI codes of older versions of TST, up until 3.x, inherited such a design and limitations from Firefox, whether intentionally or unintentionally.

(By the way, the design based on unified UI widgets and data models is progressively being phased out in recent versions of Firefox. Some widgets implemented with XUL elements have been replaced with pure JavaScript objects. For example, while <tab>s still exist as XUL elements, the <tabbrowser> element no longer exists in the DOM tree. Instead, there is just a JS object gBrowser with an interface compatible to <tabbrowser> today.)

Progressive redesigning through TST 2.0 to TST 3.x

TST 0.x was a XUL add-on so it inherited limitations of such a design of Firefox's UI directly, but WebExtensions add-on is free from such limitations. Tab objects which are tabs.Tab got via WebExtensions APIs are not UI widgets of Firefox itself, but just snapshots of <tab>s' states. We add-on author can build any architecture UI as we like, based on the tabs.Tab data models. I think TST's migration to WebExtensions add-on was the best timing to introduce virtual scrolling if I did.

Actually, I didn't do that because I wasn't aware of other designs at the time (2017). I mentioned in the article about TST 2.0 that we needed to create a new WebExtensions-based add-on to provide a similar experience to users, but I actually didn't redesign it totally. I wrote details at the article about TST 3.0 (Japanese): TST 2.0 was built on WebExtensions API to listen events around Firefox tabs and specify new tab state, but other parts are very similar to the legacy version TST 0.x, simulated UI widgets unified with data models with regular HTML <ul class="tabs"> and <li class="tab-item"> instead of XUL <tabs> and <tab>. Therefore, querySelector() and DOM3 XPath were used to find tabs based on the tree structure, while pinned tabs were implemented using position:fixed CSS tricks.

At the major update on TST 3.0 at 2019 I redesigned TST from an autonomous-decentralized model to a managed model, and I separated tabs.Tab objects as data models from HTML elements as UI widgets, to operate tab data as pure JS objects as possible.

However, the structure of the DOM tree remained unchanged, resulting in a UI based on the legacy design: flat tab elements and CSS tricks.

This cautious approach stemmed from my deep involvement in XUL-add-on-centric designs, which was my primary development experience for over 18 years. I was hesitant to risk disrupting the handling of data models and the DOM tree structure through a complete restructuring. While TST 3.x had essentially separated the data model, some crucial information, such as tab dimensions, still relied on DOM nodes, preventing them from being detached from the DOM tree. This resulted in an incomplete setup.

Risk and cost about reconstruction based on a framework

As described above, TST 3.0 had basically separated data model so the UI was already implementable based on any existing frameworks like React, instead of custom HTML. Such well-known frameworks may provide better performance from their built-in or plugin virtual scrolling feature, virtual DOM, and more other optimization.

However, I didn't pursue this option because I was unfamiliar with major JS frameworks, and I was apprehensive about the challenges of integrating a framework into an existing implementation. Major frameworks are aimed to be used as a guideline to implement application from the starting point expected by the designer of the framework. So the ideal scenario for adopting a framework is as follows:

• Choice a framework before starting all other development.
• Build data models with a structure expected by the framework.
• Build the UI based on features provided by the framework.

On my experiences, it may become a hard way if there are preconditions far from the expectation of the framework. Yes, the case of TST is quite different from the scenario described above:

• It was developed without any thought to introduce something framework later.
• The data model was designed at TST 3.0 without thought about any framework, so there looked to be no existing framework acceptable such a data directly.
• The goal of the UI development is implementing a UI matching to behaviors of Firefox's native tabs as possible, even if it is far from behaviors provided by the built-in UIs of the framework.

Rebuilding all existing TST 3.x implementations from scratch using a framework would have been the optimal approach. However, I lacked the motivation for such a daunting task, having already completed two major overhauls at TST 2.0 and 3.0.

And more, originally the TST project was started as an add-on using by myself. I felt down about struggling to the serious performance problem with thousand tabs I have never experienced (I ordinarily use about 500 or less tabs.)

We were on the verge of introducing virtual scrolling, but I halted the process for 5 years.

Introducing virtual scrolling (at last)

Development sponsored by the Waterfox project

The catalyst for my action was a contact from Alex Kontos, the organizer of the Waterfox project, about cooperation to introduce vertical tabs to Waterfox.

Initially, he contacted me as an individual developer. But I had concerns: I had not experienced any international development contract yet, and I thought I had very limited time to develop software on my private time (because I draw a cartoon style technical articles bimestrially.) Thus I asked to both Alex and my boss at the employer company to allow me to develop that on my working time. Finally, they approved to treat it as a contract between our companies, and I was assigned as the main developer for the project.

While planning, I had an idea to develop Waterfox's vertical tabs as a sidebar based on the existing add-on Tree Style Tab (TST), I had a concern about the performance problem with a very large number of tabs because Waterfox targets power users, and they may have tons of tabs. I thought that virtual scrolling UI is required for such situations, and if I successfully implemented that it may be backported to the public TST project - and the plan was accepted.

This article talks only about improvements of TST itself, so details about the collaboration is told at another article at a blog article of the employer company. Anyway, I feel fortunate that such a proposal was accepted by both parties.

Resolved misunderstanding

I initially thought I had to restructure the vertical tabs UI based on an existing framework, but I rethough that I don't need to do that and I just need to modify the existing UI a little, after I read the article Build your Own Virtual Scroll which was found when I searched to study about how virtual scrolling is implemented.

The reason why I thought I have to restructure all based on a framework is: I thought we needed to "reuse" HTML elements during virtual scrolling.

My initial exposure to virtual scrolling was during a project to develop a Web app with infinite scrolling based on a JS framework "Sencha Touch". The article explaining about infinite virtual scrolling that I read said that HTML elements are reused like steps of an escalator: when it goes away from the viewport it is moved to the other side and reappears with different content, so it looked important that high cost operations creating HTML elements is reduced.

It seemed too complex to implement from scratch, so I felt a pre-existing framework was required.

However the article recently I read did not talk about such a reusing of HTML elements and it just said to create/remove HTML elements according to the scroll position.

So I finally understood that reusing HTML elements is not necessary for "virtual scrolling".

Yes, you may think I was too stupid and lacking in study. I panicked due to various reasons: I was too busy from drawing monthly articles with manga style (it takes much time than text articles!), there were many things I hope to do, and there was a misunderstanding at the past development experience (I told above). I'm so glad to get an opportunity to research without such a panic, it was the most thankful for me on this project.

Implementing

We don't need to reuse HTML elements, so we only need to make a few more modifications to introduce virtual scrolling, because I already finished separation data models from UI widgets:

• Clearify conditions about a tab is renderable or not. For example, completely collapsed tabs won't be rendered but tabs collapsing with animation should be rendered.
• Generate the HTML element for a tab when it comes into view in the viewport, rather than when it is initially created (tabs.onCreated).
• Remove the HTML element for a tab when it goes out of view in the viewport, rather than when it is notified as removed (tabs.onRemoved).
• Skip operations to apply states to tab elements if the tab is not currently visible.
• Pinned tabs are detached from the container for regular tabs and inserted under a special container for pinned tabs, to simplify various operations. We don't need to leave them under the regular container because relation of tabs are already operated based on JS data models not HTML element UI widgets.

Most modifications were finished within 2 days and virtual scrolling were successfully landed.

　

TST's virtual scrolling implementation uses the algorithm of "diff" which was introduced at TST 3.0 to synchronize the order of tabs from data models to UI widgets.

A simple implementation of virtual scrolling creates and removes HTML elements according to the scroll position, but TST has one more factor: collapsing and expanding of tabs. Not only tabs on edges but middle tabs may need to be created/removed, so we need to find such tabs with fewer calculations.

o accelerate rendering operations, TST implements the following strategies:

1. Observe changes of tabs' states (collapsed, expanded, pinned, unpinned and more others) and prepare a list of renderable tabs from the states.
2. Observe scroll position, and detect the first tab and the last tab in the renderable range from "new scroll position", "height of a tab" and "the size of the viewport". And finally extract list of tabs finally need to be rendered: tabs extracted from the from the first tab and the last tab.
3. Compare the list of ids of last rendered tabs and ids of tabs we are going to render, with the algorithm of the "diff".
4. Create and remove HTML elements based on the result calculated at the previous step.
5. Store ids of finally rendered tabs, for the next rendering.

I understood that reducing DOM operations based on calculations is a feature of a virtual DOM architecture. But as I already told, it looked very hard for me to introduce any framework to existing implementation of TST without troubles, so instead I've introduced optimized updating with diff individually.

　

After these changes the time to build UI widgets has been quite reduced even if there are thousand tabs. We don't need to cache pre-built HTML for acceleration anymore, and the cache mechanism of the sidebar contents has been obsolete and deleted completely.

Optimizations unexpectedly become possible

The largest bottleneck has been gone by introduced virtual scrolling, and it has exposed many other minor issues and inefficiencies:

• Numerous smaller bottlenecks, previously obscured by the main initialization bottleneck, became apparent. Thus, I've significantly optimized TST, addressing not only the sidebar panel but also the background page, based on performance profiles collected by the Browser Toolbox.
• I realized some helper addons made TST quite slow. This was caused by excessive overhead in exposing tab data to helper addons based on their permissions, stemming from an emphasis on maintaining high code readability. So I had to rewrite the code to make it faster, albeit less maintainable.
• Animation effects became smoother after optimizations, revealing underlying issues that were behind the slow animation: conflicting operations from multiple modules to a shared object. Finally, the codes have been rewritten, and conflicts have been resolved.

Before introducing virtual scrolling, I gave up to investigate small bottlenecks because the design with full DOM tree was basically slow and I thought small optimizations would be a pebble tossed into a churning sea. "The faster is the winner": it is one of truths on software development. On my case, slower architecture hid bottlenecks and faster one exposed them, so we really needed fastness for more optimizations.

Sticking of tabs

This feature is not related to virtual scrolling directly, but I've implemented the "sticking tabs to tab bar edges" feature to improve user experience in cases where there are a large number of tabs, allowing quick access to tabs even when they are scrolled out of view.

Some time ago I developed a helper addon TST Active Tab on Scroll Bar because I frequently lose the position of the active tab when there are large number tabs. However, at the time, the underlying motivation behind this was not entirely clear to me. And I've realized my implicit motivations:

• When I want to copy title and URL of the active tab (by another addon), I have to open the context menu on the active tab, but it is hard because the active tab is sometimes scrolled out and lost.
• When I want to close the active tab, I cannot do that with the keyboard shortcut because my left hand is full by some reasons, but the active tab is scrolled out so I cannot click its closebox.

In short: I'll never be stressed if the active tab was always in the viewport.

Of course, we can already keep a tab always in the viewport as a pinned tab, but there is a restriction: pinned tabs can't be a member of a tree. I needed a new solution for cases when I want to keep a tab in the viewport but retain its tree relationship.

At first I remembered the position:sticky feature of CSS, but it didn't work as I expected. I have to set contain:paint instead of overflow:hidden to the container element to use position:sticky, but sadly it hides some elements and that broke TST's features.

So finally, I've implemented the "sticky tab" behavior. When a tab is out of the visible area, it is detached from the general container and attached to one of the separated containers placed at the top and bottom of the tab bar. The process is reversed when the tab is scrolled into the visible area. At first only the active tab was automatically sticked to tab bar edges, but I realized it is useful if multiple tabs are sticked so I added a new context menu command "Stick Tab to Tab Bar Edges" for more cases, like the "Pin Tab" command. (After that I've realized there are more useful auto-sticking cases, so I've released a new helper addon for that.

And one more note: detaching of a stuck tab from the container of regular tabs simply shifts following tabs, causing incorrect scroll position. To avoid this shifting, TST now inserts a spacer element to the container instead of sticked-detached tab element, so we have no need to recalculate scroll position. Such a mixing of different children types under the tabs container was impossible before complete separation of the data model and UI widgets, this is a sub benefit of introduced virtual scrolling.

　

It is one of TST project policies: concentrating to providing basic tree management features and simulating Firefox's native tab features. In other words, providing extra useful features is out of purposes, so such a TST original feature is supposed not to be a built-in, but actually here it is. I've decided to implement the feature by TST side because designing of an API (for helper addons) to allow providing the feature looks very hard or impossible for me - this is also one of TST project policies.

Progressive improvements is the only one possible way for me

As described above, TST 4.0 has been improved so much.

I let slip the opportunity to restructure TST with clean architecture and high performance, at the migration from XUL add-on to WebExtensions add-on at the version 2.0. Version 3.0 moved closer to the design it should have been, and version 4.0 nearly reached that goal.

Sadly, the current implementation of TST is not clean and is still difficult to maintain, and unfriendly for developers other than myself, due to such historical reasons. I believe version 5.0 might have been possible if it had been redesigned to be cleaner, or if it had become functional without requiring a permanent background page.

　

It is definitely true that I should study more about software designing before creating TST 2.0, but I couldn't do that. I would been gave up all from over-capacity, if I tried both migration from XUL to WebExtensions and redesigning with the best architecture together.

It's a common scenario: someone in a situation where they have to develop what's urgently needed rather than what should be, not someone who has skills to develop enough, often resulting in software that works adequately but lacks proper design. Anyway it is the fact that here is a usable product - TST is still alive for 17 years doing whatever. I'll continue developing TST as long as Firefox remains active.