Spineless Traversal

• New algorithm to speedup incremental web layout.
• Web layout: one pass in web browser, calculate bounding boxes for each nodes.
• Incremental: web page keep changing, want to recompute only dirtied nodes.
• Problem with SOTA: need to access auxiliary nodes not dirtied, to recompute dirtied nodes. The former might be much larger then the latter.
• Idea: use a queue to store all dirtied nodes, skipping the need of auxiliary nodes.
• Problem: queue order need to respect computation dependencies.
• Solution: priority queue of Order Maintenance objects.
• Design: custom dsl to schedule dependencies statically.
• Optimization: compressed queue, conditional move, custom allocator for compactness and pointer compression
• Result: 1.8x speedup against SOTA
• Also applicable: Other Incremental Attribute Grammar Evaluation Tasks, example: typechecking, compilation, analysis