Incr: Faster Re-Execution via Bolt-On Incrementalization
Talkat 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26) · 2026-07-13..07-15·
summary
Incr is a bolt-on system that incrementalizes unmodified shell programs by tracing command effects, running each command in a semi-isolated overlay, and memoizing read/write and stream dependencies to skip re-execution when safe. It uses lightweight interposition and component-oriented dependency inference, preserves streaming/pipeline parallelism, and offers optional annotations to lower overheads. Evaluation shows 34.2× average speedup and 373.3× max across Koala benchmarks, a 159.5× example per-execution win and 4× end-to-end workflow reduction, and is behaviorally indistinguishable on 10,000+ Bash tests (3 failures).
AI-written summary · about
chapters (8)
- 0:00Inkrement and incremental execution
- 1:00Real-world shell program example
- 3:29Speedups in re-execution
- 5:15Key techniques in incrementalization
- 7:24Demonstration of incremental execution
- 9:10Evaluation on shell programs
- 11:57Correctness vs Bash test suite
- 13:04Summary
related talks
41mLinux Systems Performance
24mIncremental Computation: What Is the Essence? (Invited Contribution)
42mSupercharge Your Performance with the Optimus Cirrus Platform
13mThe Koala Benchmarks for the Shell: Characterization and Implications
30mBlazingly Fast or Blazingly Hyped?
34mFast Code Without Breaking Things
43mHow to Innovate in a Legacy
45mThe Joy of Building Large Scale Systems