commit edf2a795b7208ea25881ce7eacd1828cdf3364fa
parent 5fc2acb0ab6437f129fe7687573e742cf76e69ee
Author: Jonathan Kew <jkew@mozilla.com>
Date: Thu, 30 Oct 2025 16:21:18 +0000
Bug 1997044 - Use a hashtable to collect frames in DepthOrderedFrameList, and sort the list lazily when needed. r=layout-reviewers,emilio,firefox-style-system-reviewers
For the example here, this reduces the jank when deleting the JS source
from 3.6 seconds to 650ms in my local build, because we are no longer
shifting all the entries of a large array each time we delete a frame
from the list.
Differential Revision: https://phabricator.services.mozilla.com/D270541
Diffstat:
4 files changed, 94 insertions(+), 54 deletions(-)
diff --git a/layout/base/DepthOrderedFrameList.cpp b/layout/base/DepthOrderedFrameList.cpp
@@ -12,30 +12,40 @@
namespace mozilla {
void DepthOrderedFrameList::Add(nsIFrame* aFrame) {
- // Is this root already scheduled for reflow?
- FrameAndDepth entry{aFrame, aFrame->GetDepthInFrameTree()};
- auto index = mList.IndexOfFirstElementGt(
- entry, FrameAndDepth::CompareByReverseDepth{});
- if (MOZ_UNLIKELY(index > 0 && mList[index - 1].mFrame == aFrame)) {
- // FIXME: This could possibly be changed to a uniqueness assertion, with
- // some work in ResizeReflowIgnoreOverride (and maybe others?)
- MOZ_ASSERT(mList[index - 1].mDepth == entry.mDepth);
- return;
- }
- mList.InsertElementAt(index, std::move(entry));
-}
+ MOZ_ASSERT(aFrame);
-void DepthOrderedFrameList::Remove(nsIFrame* aFrame) {
- mList.RemoveElement(aFrame);
+ if (auto p = mFrames.lookupForAdd(aFrame)) {
+ // We don't expect the depth of a frame in the list to change.
+ MOZ_ASSERT(p->value() == aFrame->GetDepthInFrameTree());
+ } else {
+ if (!mFrames.add(p, aFrame, aFrame->GetDepthInFrameTree())) {
+ NS_WARNING("failed to add frame to DepthOrderedFrameList");
+ }
+ if (mFrames.count() == 1) {
+ // We just added the first frame, so can directly set up mSortedFrames.
+ // (Lists that only contain a single frame are common.)
+ MOZ_ASSERT(mSortedFrames.IsEmpty());
+ mSortedFrames.AppendElement(FrameAndDepth{aFrame, p->value()});
+ } else {
+ // Clear mSortedFrames, so that we'll rebuild it when needed.
+ mSortedFrames.ClearAndRetainStorage();
+ }
+ }
}
nsIFrame* DepthOrderedFrameList::PopShallowestRoot() {
+ MOZ_ASSERT(!mFrames.empty(), "no frames in list!");
+
+ EnsureSortedList();
+
// List is sorted in order of decreasing depth, so there are no shallower
// frames than the last one.
- const FrameAndDepth& lastFAD = mList.PopLastElement();
+ const FrameAndDepth& lastFAD = mSortedFrames.PopLastElement();
nsIFrame* frame = lastFAD.mFrame;
// We don't expect frame to change depths.
MOZ_ASSERT(frame->GetDepthInFrameTree() == lastFAD.mDepth);
+ // Keep the hashtable in sync with the sorted list.
+ mFrames.remove(frame);
return frame;
}
@@ -46,7 +56,8 @@ bool DepthOrderedFrameList::FrameIsAncestorOfAnyElement(
// Look for a path from any element to aFrame, following GetParent(). This
// check mirrors what FrameNeedsReflow() would have done if the reflow root
// didn't get in the way.
- for (nsIFrame* f : mList) {
+ for (auto iter = mFrames.iter(); !iter.done(); iter.next()) {
+ nsIFrame* f = iter.get().key();
do {
if (f == aFrame) {
return true;
@@ -58,4 +69,15 @@ bool DepthOrderedFrameList::FrameIsAncestorOfAnyElement(
return false;
}
+void DepthOrderedFrameList::BuildSortedList() const {
+ MOZ_ASSERT(mSortedFrames.IsEmpty());
+
+ mSortedFrames.SetCapacity(mFrames.count());
+ for (auto iter = mFrames.iter(); !iter.done(); iter.next()) {
+ mSortedFrames.AppendElement(
+ FrameAndDepth{iter.get().key(), iter.get().value()});
+ }
+ mSortedFrames.Sort();
+}
+
} // namespace mozilla
diff --git a/layout/base/DepthOrderedFrameList.h b/layout/base/DepthOrderedFrameList.h
@@ -7,6 +7,7 @@
#ifndef mozilla_DepthOrderedFrameList_h
#define mozilla_DepthOrderedFrameList_h
+#include "mozilla/HashTable.h"
#include "mozilla/ReverseIterator.h"
#include "nsTArray.h"
@@ -16,57 +17,70 @@ namespace mozilla {
class DepthOrderedFrameList {
public:
- // Add a dirty root.
+ // Add a frame to the set being tracked.
void Add(nsIFrame* aFrame);
+
// Remove this frame if present.
- void Remove(nsIFrame* aFrame);
- // Remove and return one of the shallowest dirty roots from the list.
- // (If two roots are at the same depth, order is indeterminate.)
+ void Remove(nsIFrame* aFrame) {
+ mFrames.remove(aFrame);
+ mSortedFrames.ClearAndRetainStorage();
+ }
+
+ // Remove and return one of the shallowest frames from the list.
+ // (If two frames are at the same depth, order is indeterminate.)
nsIFrame* PopShallowestRoot();
- // Remove all dirty roots.
- void Clear() { mList.Clear(); }
+
+ // Remove all frames.
+ void Clear() {
+ mFrames.clear();
+ mSortedFrames.Clear();
+ }
+
// Is this frame one of the elements in the list?
- bool Contains(nsIFrame* aFrame) const { return mList.Contains(aFrame); }
+ bool Contains(nsIFrame* aFrame) const { return mFrames.has(aFrame); }
+
// Are there no elements?
- bool IsEmpty() const { return mList.IsEmpty(); }
+ bool IsEmpty() const { return mFrames.empty(); }
// Is the given frame an ancestor of any dirty root?
bool FrameIsAncestorOfAnyElement(nsIFrame* aFrame) const;
- auto IterFromShallowest() const { return Reversed(mList); }
-
- // The number of elements that there are.
- size_t Length() const { return mList.Length(); }
- nsIFrame* ElementAt(size_t i) const { return mList.ElementAt(i); }
- void RemoveElementAt(size_t i) { mList.RemoveElementAt(i); }
+ auto IterFromShallowest() const {
+ EnsureSortedList();
+ return Reversed(mSortedFrames);
+ }
private:
+ // Set of the frames we're tracking and their depth in the frame tree. This
+ // is the primary record maintained by the Add and Remove methods. The sorted
+ // list in mSortedFrames is created on demand when we need to iterate in depth
+ // order.
+ HashMap<nsIFrame*, uint32_t> mFrames;
+
struct FrameAndDepth {
nsIFrame* mFrame;
- const uint32_t mDepth;
+ uint32_t mDepth;
// Easy conversion to nsIFrame*, as it's the most likely need.
operator nsIFrame*() const { return mFrame; }
// Used to sort by reverse depths, i.e., deeper < shallower.
- class CompareByReverseDepth {
- public:
- bool Equals(const FrameAndDepth& aA, const FrameAndDepth& aB) const {
- return aA.mFrame == aB.mFrame;
- }
- bool LessThan(const FrameAndDepth& aA, const FrameAndDepth& aB) const {
- // Reverse depth! So '>' instead of '<'.
- if (aA.mDepth != aB.mDepth) {
- return aA.mDepth > aB.mDepth;
- }
- // Untie with the frame pointer, so that all frames have a unique
- // position in the sorted list.
- return uintptr_t(aA.mFrame) < uintptr_t(aB.mFrame);
- }
- };
+ bool operator<(const FrameAndDepth& aOther) const {
+ // Reverse depth! So '>' instead of '<'.
+ return mDepth > aOther.mDepth;
+ }
};
- // List of all known dirty roots, sorted by decreasing depths.
- nsTArray<FrameAndDepth> mList;
+
+ // The list of frames sorted by decreasing depths; created/updated lazily.
+ mutable nsTArray<FrameAndDepth> mSortedFrames;
+
+ void EnsureSortedList() const {
+ if (mSortedFrames.IsEmpty() && !mFrames.empty()) {
+ BuildSortedList();
+ }
+ }
+
+ void BuildSortedList() const;
};
} // namespace mozilla
diff --git a/layout/generic/StickyScrollContainer.cpp b/layout/generic/StickyScrollContainer.cpp
@@ -336,15 +336,15 @@ void StickyScrollContainer::UpdatePositions(nsPoint aScrollPosition,
OverflowChangedTracker oct;
oct.SetSubtreeRoot(aSubtreeRoot);
- // We need to position ancestors before children, so iter from shallowest. We
- // don't use mFrames.IterFromShallowest() because we want to handle removal of
- // non-first continuations while we iterate.
- for (size_t i = mFrames.Length(); i--;) {
- nsIFrame* f = mFrames.ElementAt(i);
+ // We need to position ancestors before children, so iter from shallowest.
+ // Collect a list of frames to be removed, so that we don't invalidate the
+ // iterator while we're using it.
+ AutoTArray<nsIFrame*, 8> framesToRemove;
+ for (nsIFrame* f : mFrames.IterFromShallowest()) {
if (!nsLayoutUtils::IsFirstContinuationOrIBSplitSibling(f)) {
// This frame was added in nsIFrame::DidSetComputedStyle before we knew it
// wasn't the first ib-split-sibling.
- mFrames.RemoveElementAt(i);
+ framesToRemove.AppendElement(f);
continue;
}
if (aSubtreeRoot) {
@@ -363,6 +363,9 @@ void StickyScrollContainer::UpdatePositions(nsPoint aScrollPosition,
}
}
}
+ for (nsIFrame* f : framesToRemove) {
+ mFrames.Remove(f);
+ }
oct.Flush();
}
diff --git a/layout/style/ServoBindings.toml b/layout/style/ServoBindings.toml
@@ -327,6 +327,7 @@ opaque-types = [
# https://github.com/rust-lang/rust-bindgen/pull/1515
# is available
"mozilla::detail::PointerType",
+ "mozilla::HashMap",
"mozilla::HashSet",
"mozilla::ScrollAxis", # <- For some reason the alignment of this is 4
# for clang.
