Spineless Traversal for Layout Invalidation
summary
A new incremental-layout algorithm, Spineless Traversal, replaces top-down tree scans with a pointer queue ordered by order-maintenance timestamps to avoid touching auxiliary nodes; implementation adds a custom allocator, pointer compression, and conditional-move assembly for 5-cycle comparisons. A prototype on a browser-like DSL and Ladybird-style traces shows wins on 83.0% of 2,216 frames with a 1.80× mean speedup, at ~128 bits per node extra memory.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 0:22Web browser layout pipeline
- 1:04Incrementalization and amortization
- 2:26State-of-the-art algorithm
- 3:48Spineless traversal queue
- 5:14Queue processing and dependencies
- 6:18Queue order and performance
- 7:21Time stamps and priority queue
- 8:46Performance comparison
- 10:13Optimizing comparison function
- 12:22Evaluation on real-world sites
- 13:51Performance results
- 14:55General framework
- 15:38Q&A: Memory footprint
- 16:41Q&A: Transferability
related talks
19mDecoupling Data Layouts from Bounding Volume Hierarchies
22mDOM implementation techniques
22mConflict-Driven Synthesis for Layout Engines
27mChanging The Layout Game
30mvirtual-scroller: Let there be less (DOM)
01h 02mCache-friendly Design in Robot Path Planning with C++
51mData Orientation For The Win!
55mWriting Cache-Friendly C++