Icicle: Destructive Updates via Tardis Monad and Stitching Graph

Icicle, a high-level streaming query language, compiles to C using a struct-of-arrays approach. To ensure purity, the compiler initially inserts copy operations before array mutations. This post details an optimization using the Tardis Monad and a stitching graph to eliminate most of these copies, enabling destructive updates and achieving up to a 50% runtime reduction. The algorithm builds a reference graph to track array references, using forward and backward traversals with the Tardis Monad to determine safe destructive updates. This cleverly combines functional programming concepts with compile-time optimization, offering a novel approach to improving streaming query language performance.