{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:07:14Z","timestamp":1784200034457,"version":"3.55.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","funder":[{"name":"National Science Foundation, Directorate for Computer and Information Science and Engineering","award":["CCF-2340192"],"award-info":[{"award-number":["CCF-2340192"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>\n                    Latency is a major concern for web rendering engines like those in Chrome, Safari, and Firefox. These engines reduce latency by using an\n                    <jats:italic toggle=\"yes\">incremental layout algorithm<\/jats:italic>\n                    to redraw the page when the user interacts with it. In such an algorithm, elements that change frame-to-frame are marked dirty, and only those elements are processed to draw the next frame, dramatically reducing latency. However, the standard incremental layout algorithm must search the page for dirty elements, accessing auxiliary elements in the process. These auxiliary elements add cache misses and stalled cycles, and are responsible for a sizable fraction of all layout latency.\n                  <\/jats:p>\n                  <jats:p>We introduce a new, faster incremental layout algorithm called Spineless Traversal. Spineless Traversal uses a cache-friendlier priority queue algorithm that avoids accessing auxiliary nodes and thus reduces cache traffic and stalls. This leads to dramatic speedups on the most latency-critical interactions such as hovering, typing, and animation. Moreover, thanks to numerous low-level optimizations, Spineless Traversal is competitive across the whole spectrum of incremental layout workloads. Spineless Traversal is faster than the standard approach on 83.0% of 2216 benchmarks, with a mean speedup of 1.80\u00d7 concentrated in the most latency-critical interactions.<\/jats:p>","DOI":"10.1145\/3729322","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1791-1813","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Spineless Traversal for Layout Invalidation"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3418-4835","authenticated-orcid":false,"given":"Marisa","family":"Kirisame","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7002-6011","authenticated-orcid":false,"given":"Tiezhi","family":"Wang","sequence":"additional","affiliation":[{"name":"Tongji University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2621-3592","authenticated-orcid":false,"given":"Pavel","family":"Panchekha","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1480945.1480946"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/1087939"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806650"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461799"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_17"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507751"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802184"},{"key":"e_1_3_2_9_2","unstructured":"Tali Garseil. 2009. How browsers work. https:\/\/taligarsiel.com\/Projects\/howbrowserswork1.htm#Dirty_bit_system."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814305"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594324"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1855591.1855598"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","unstructured":"Oleg Kiselyov. 2018. Reconciling Abstraction with High Performance: A MetaOCaml approach. Foundations and Trends\u00ae in Programming Languages 5 1 (2018) 1-101. doi:10.1561\/2500000038","DOI":"10.1561\/2500000038"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591246"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3635800.3637447"},{"key":"e_1_3_2_16_2","unstructured":"Frank McSherry Derek Murray Rebecca Isaacs and Michael Isard. 2013. Differential dataflow. In Proceedings of CIDR 2013. https:\/\/www.microsoft.com\/en-us\/research\/publication\/differential-dataflow\/"},{"key":"e_1_3_2_17_2","volume-title":"Parallel Layout Engines: Synthesis and Optimization of Tree Traversals.","author":"Meyerovich Leo Alexander","year":"2013","unstructured":"Leo Alexander Meyerovich. 2013. Parallel Layout Engines: Synthesis and Optimization of Tree Traversals. University of California, Berkeley."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772763"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","unstructured":"Donald Michie. 1968.\u201cMemo\u201d Functions and Machine Learning. Nature 218 (1968) 19-22. doi:10.1038\/218019a0","DOI":"10.1038\/218019a0"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Robin Milner. 1978. A theory of type polymorphism in programming. 7. Comput. System Sci. 17 3 (1978) 348-375. doi:10.1016\/0022-0000(78)90014-4","DOI":"10.1016\/0022-0000(78)90014-4"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","unstructured":"Pavel Panchekha Adam T. Geller Michael D. Ernst Zachary Tatlock and Shoaib Kamil. 2018. Verifying that web pages have accessible layout. SIGPLAN Not. 53 4 (June 2018) 1-14. doi:10.1145\/3296979.3192407","DOI":"10.1145\/3296979.3192407"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1093\/9780198913887.001.0001"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984010"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","unstructured":"Irfan Prazina \u0160eila Be\u0107irovi\u0107 Emir Cogo and Vensada Okanovi\u0107. 2023. Methods for Automatic Web Page Layout Testing and Analysis: A Review. IEEE Access 11 (2023) 13948-13964. doi:10.1109\/ACCESS.2023.3242549","DOI":"10.1109\/ACCESS.2023.3242549"},{"key":"e_1_3_2_25_2","unstructured":"Servo Project. 2023. Layout 2013 and Layout 2020.https:\/\/servo.org\/blog\/2023\/04\/13\/layout-2013-vs-2020\/."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75305"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158710"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582172"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/512644.512645"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314626"},{"key":"e_1_3_2_31_2","unstructured":"Chrome Team. 2024. Avoid an excessive DOM size | Lighthouse | Chrome for Developers. https:\/\/developer.chrome.com\/docs\/lighthouse\/performance\/dom-size."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:07:28Z","timestamp":1784196448000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":30,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729322"],"URL":"https:\/\/doi.org\/10.1145\/3729322","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}