Icicle: 利用 Tardis Monad 和缝合图实现破坏性更新

Icicle 是一种高级流式查询语言，它通过编译成 C 语言并利用结构体数组的方式处理数据。为了提高效率，Icicle 编译器原本会在对数组进行修改前插入复制操作。本文介绍了一种利用 Tardis Monad 和缝合图来优化 Icicle 编译器的算法，该算法能够识别并消除大部分冗余的复制操作，从而实现破坏性更新，并使查询运行时间最多减少 50%。该算法通过构建一个引用图来跟踪数组的引用，并利用 Tardis Monad 进行正向和反向遍历，判断是否可以安全地进行破坏性更新。这种方法巧妙地结合了函数式编程的思想和编译时优化技术，为提高流式查询语言的性能提供了新的思路。