INCR - a new library for incremental computation

• Main Author: Dou, Maokang
• Other Authors: Lin Shang-Wei
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2022
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/156641
• Institution: Nanyang Technological University

This project presents a C++ library, named INCR, for writing incremental programs - programs that automatically adjust to changes to their input data. The library is developed with performance, readability and scalability in mind, differentiating itself from other existing solutions that are mostly experimental and bounded by the performance of the programming languages in which they are written. The library follows commonly used algorithms and data structures in incremental computing to implement a run-time that keeps track of data dependencies in dependency graphs, caches sub-computations by memoization, and repairs outdated computations via change propagation. On top of the system run-time, the library also provides a collection of standard generic algorithms, including transform, filter and accumulate, for writing clear, accurate and fast incremental programs with ease. The experiments show the library produces accurate results while providing significant speedups over computing from scratch.