LibWeb: Stop putting the FormattingState nodes in a slow hash map

Instead, put them in a Vector<OwnPtr<NodeState>>. Each layout node
has a unique index into the vector. It's a simple serial ID assigned
during layout tree construction. Every new layout restarts the sequence
at 0 for the next ICB.

This is a huge layout speed improvement on all content.

6 files changed, 46 insertions, 46 deletions

diff --git a/Userland/Libraries/LibWeb/DOM/Document.cpp b/Userland/Libraries/LibWeb/DOM/Document.cpp
index 5b2f9a7ca9..cd726b39c7 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Document.cpp
@@ -606,11 +606,13 @@ void Document::update_layout()
     auto viewport_rect = browsing_context()->viewport_rect();
 
     if (!m_layout_root) {
+        m_next_layout_node_serial_id = 0;
         Layout::TreeBuilder tree_builder;
         m_layout_root = static_ptr_cast<Layout::InitialContainingBlock>(tree_builder.build(*this));
     }
 
     Layout::FormattingState formatting_state;
+    formatting_state.nodes.resize(layout_node_count());
     Layout::BlockFormattingContext root_formatting_context(formatting_state, *m_layout_root, nullptr);
 
     auto& icb = static_cast<Layout::InitialContainingBlock&>(*m_layout_root);
diff --git a/Userland/Libraries/LibWeb/DOM/Document.h b/Userland/Libraries/LibWeb/DOM/Document.h
index 563c600a72..5800965f1d 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.h
+++ b/Userland/Libraries/LibWeb/DOM/Document.h
@@ -61,6 +61,9 @@ public:
 
     virtual ~Document() override;
 
+    size_t next_layout_node_serial_id(Badge<Layout::Node>) { return m_next_layout_node_serial_id++; }
+    size_t layout_node_count() const { return m_next_layout_node_serial_id; }
+
     String cookie(Cookie::Source = Cookie::Source::NonHttp);
     void set_cookie(String const&, Cookie::Source = Cookie::Source::NonHttp);
 
@@ -391,6 +394,8 @@ private:
 
     unsigned m_referencing_node_count { 0 };
 
+    size_t m_next_layout_node_serial_id { 0 };
+
     OwnPtr<CSS::StyleComputer> m_style_computer;
     RefPtr<CSS::StyleSheetList> m_style_sheets;
     RefPtr<Node> m_hovered_node;
diff --git a/Userland/Libraries/LibWeb/Layout/FormattingState.cpp b/Userland/Libraries/LibWeb/Layout/FormattingState.cpp
index 4e2339a65d..eedce21856 100644
--- a/Userland/Libraries/LibWeb/Layout/FormattingState.cpp
+++ b/Userland/Libraries/LibWeb/Layout/FormattingState.cpp
@@ -12,48 +12,37 @@ namespace Web::Layout {
 
 FormattingState::NodeState& FormattingState::get_mutable(NodeWithStyleAndBoxModelMetrics const& box)
 {
-    if (m_lookup_cache.box == &box && m_lookup_cache.is_mutable)
-        return *m_lookup_cache.state;
-
-    auto& node_state = [&]() -> NodeState& {
-        if (auto it = nodes.find(&box); it != nodes.end())
-            return *it->value;
-
-        for (auto const* ancestor = m_parent; ancestor; ancestor = ancestor->m_parent) {
-            if (auto it = ancestor->nodes.find(&box); it != ancestor->nodes.end()) {
-                auto cow_node_state = adopt_own(*new NodeState(*it->value));
-                auto* cow_node_state_ptr = cow_node_state.ptr();
-                nodes.set(&box, move(cow_node_state));
-                return *cow_node_state_ptr;
-            }
+    auto serial_id = box.serial_id();
+    if (nodes[serial_id])
+        return *nodes[serial_id];
+
+    for (auto const* ancestor = m_parent; ancestor; ancestor = ancestor->m_parent) {
+        if (ancestor->nodes[serial_id]) {
+            auto cow_node_state = adopt_own(*new NodeState(*ancestor->nodes[serial_id]));
+            auto* cow_node_state_ptr = cow_node_state.ptr();
+            nodes[serial_id] = move(cow_node_state);
+            return *cow_node_state_ptr;
         }
+    }
 
-        return *nodes.ensure(&box, [] { return adopt_own(*new NodeState); });
-    }();
-
-    m_lookup_cache = LookupCache { .box = &box, .state = &node_state, .is_mutable = true };
-
-    return node_state;
+    nodes[serial_id] = adopt_own(*new NodeState);
+    nodes[serial_id]->node = const_cast<NodeWithStyleAndBoxModelMetrics*>(&box);
+    return *nodes[serial_id];
 }
 
 FormattingState::NodeState const& FormattingState::get(NodeWithStyleAndBoxModelMetrics const& box) const
 {
-    if (m_lookup_cache.box == &box)
-        return *m_lookup_cache.state;
+    auto serial_id = box.serial_id();
+    if (nodes[serial_id])
+        return *nodes[serial_id];
 
-    auto& node_state = [&]() -> NodeState const& {
-        if (auto it = nodes.find(&box); it != nodes.end())
-            return *it->value;
-
-        for (auto* ancestor = m_parent; ancestor; ancestor = ancestor->m_parent) {
-            if (auto it = ancestor->nodes.find(&box); it != ancestor->nodes.end())
-                return *it->value;
-        }
-        return *const_cast<FormattingState&>(*this).nodes.ensure(&box, [] { return adopt_own(*new NodeState); });
-    }();
-
-    const_cast<FormattingState*>(this)->m_lookup_cache = LookupCache { .box = &box, .state = const_cast<NodeState*>(&node_state), .is_mutable = false };
-    return node_state;
+    for (auto* ancestor = m_parent; ancestor; ancestor = ancestor->m_parent) {
+        if (ancestor->nodes[serial_id])
+            return *ancestor->nodes[serial_id];
+    }
+    const_cast<FormattingState*>(this)->nodes[serial_id] = adopt_own(*new NodeState);
+    const_cast<FormattingState*>(this)->nodes[serial_id]->node = const_cast<NodeWithStyleAndBoxModelMetrics*>(&box);
+    return *nodes[serial_id];
 }
 
 void FormattingState::commit()
@@ -63,9 +52,11 @@ void FormattingState::commit()
 
     HashTable<Layout::TextNode*> text_nodes;
 
-    for (auto& it : nodes) {
-        auto& node = const_cast<Layout::NodeWithStyleAndBoxModelMetrics&>(*it.key);
-        auto& node_state = *it.value;
+    for (auto& node_state_ptr : nodes) {
+        if (!node_state_ptr)
+            continue;
+        auto& node_state = *node_state_ptr;
+        auto& node = *node_state.node;
 
         // Transfer box model metrics.
         node.box_model().inset = { node_state.inset_top, node_state.inset_right, node_state.inset_bottom, node_state.inset_left };
diff --git a/Userland/Libraries/LibWeb/Layout/FormattingState.h b/Userland/Libraries/LibWeb/Layout/FormattingState.h
index ef3616ce29..e7e98b59d7 100644
--- a/Userland/Libraries/LibWeb/Layout/FormattingState.h
+++ b/Userland/Libraries/LibWeb/Layout/FormattingState.h
@@ -30,6 +30,7 @@ struct FormattingState {
         : m_parent(parent)
         , m_root(find_root())
     {
+        nodes.resize(m_root.nodes.size());
     }
 
     FormattingState const& find_root() const
@@ -41,6 +42,8 @@ struct FormattingState {
     }
 
     struct NodeState {
+        Layout::NodeWithStyleAndBoxModelMetrics* node { nullptr };
+
         float content_width { 0 };
         float content_height { 0 };
         Gfx::FloatPoint offset;
@@ -106,7 +109,7 @@ struct FormattingState {
     // NOTE: get() will not CoW the NodeState.
     NodeState const& get(NodeWithStyleAndBoxModelMetrics const&) const;
 
-    HashMap<NodeWithStyleAndBoxModelMetrics const*, NonnullOwnPtr<NodeState>> nodes;
+    Vector<OwnPtr<NodeState>> nodes;
 
     // We cache intrinsic sizes once determined, as they will not change over the course of a full layout.
     // This avoids computing them several times while performing flex layout.
@@ -123,13 +126,6 @@ struct FormattingState {
 
     FormattingState const* m_parent { nullptr };
     FormattingState const& m_root;
-
-    struct LookupCache {
-        NodeWithStyleAndBoxModelMetrics const* box { nullptr };
-        NodeState* state { nullptr };
-        bool is_mutable { false };
-    };
-    LookupCache m_lookup_cache;
 };
 
 Gfx::FloatRect absolute_content_rect(Box const&, FormattingState const&);
diff --git a/Userland/Libraries/LibWeb/Layout/Node.cpp b/Userland/Libraries/LibWeb/Layout/Node.cpp
index f128662bf3..7d03843352 100644
--- a/Userland/Libraries/LibWeb/Layout/Node.cpp
+++ b/Userland/Libraries/LibWeb/Layout/Node.cpp
@@ -23,6 +23,8 @@ Node::Node(DOM::Document& document, DOM::Node* node)
     : m_document(document)
     , m_dom_node(node)
 {
+    m_serial_id = m_document->next_layout_node_serial_id({});
+
     if (m_dom_node)
         m_dom_node->set_layout_node({}, this);
 }
diff --git a/Userland/Libraries/LibWeb/Layout/Node.h b/Userland/Libraries/LibWeb/Layout/Node.h
index 6de0c37114..02b947d5a8 100644
--- a/Userland/Libraries/LibWeb/Layout/Node.h
+++ b/Userland/Libraries/LibWeb/Layout/Node.h
@@ -34,6 +34,8 @@ class Node : public TreeNode<Node> {
 public:
     virtual ~Node();
 
+    size_t serial_id() const { return m_serial_id; }
+
     bool is_anonymous() const { return !m_dom_node; }
     const DOM::Node* dom_node() const { return m_dom_node; }
     DOM::Node* dom_node() { return m_dom_node; }
@@ -141,6 +143,8 @@ private:
     RefPtr<DOM::Node> m_dom_node;
     RefPtr<Painting::Paintable> m_paintable;
 
+    size_t m_serial_id { 0 };
+
     bool m_inline { false };
     bool m_has_style { false };
     bool m_visible { true };