Conference Presentation, Keynote
Incremental
- Implementation challenges will be addressed in the talk's second half, contingent on available time.
- The dependency graph structure is expected to change dynamically with inputs, distinguishing the library from static tools.
- Using
bindis predicted to enable dynamic graphs where functions return entirely new incremental graphs based on input changes. - The
stabilizefunction is expected to give users explicit control over computation timing to prevent exposing inconsistent states. Stabilizewill allow efficient batching of updates, executing all changes only when the user explicitly signals a need.- A
cut-offfeature is anticipated to stop propagation when value changes fall below a specific percentage threshold. - The current implementation is on version eight, with acknowledged room for further improvement.
- The naive two-pass algorithm is expected to fail cooperation with the garbage collector, leading to node accumulation and garbage.
- Ref counting and sentinels with finalizers are predicted to enable the garbage collector to identify and remove dead nodes.
- The naive algorithm is considered broken for cut-offs because propagation decisions require prior computation.
- An optimistic cut-off approach, assuming no propagation and restarting on error, works well for some cases but becomes difficult with others.
- Using a topological sort with a heap is expected to reduce performance by a factor between 1.5 and 4 times.
- Pseudo-timestamps (e.g., "2.5") are predicted to handle dynamic graph changes without requiring repeated topological sorts.
- The heap-based approach is expected to introduce exponential garbage due to the collector detecting collection very late, causing repeated recomputation.
- Explicitly tracking observers via a
stop observingfunction is expected to solve exponential garbage by marking nodes as not live. - A partial order based on pseudo-heights is anticipated to eliminate the need for slow heaps in favor of a simple array of lists.
- The system is expected to throw an error if the height exceeds a configurable threshold, currently set to 128.
- The final version, identified as version six, is expected to restore performance to the original baseline while integrating cut-offs and efficient binds.
- Applying GADTs is predicted to yield two or three speed improvements by storing heterogeneous types without heavy closure allocation.
- Most applications using the library are expected to spend the majority of execution time inside the library, justifying the development of a generic tool.
- Building a generic library enables micro-optimizations, such as rotating record field order for cache efficiency, which are unlikely in bespoke applications.
- Significant future work is expected, including potential modern versions of the library.
- Future possibilities include explicit memory management or collapsing nodes, though these tasks are noted as non-trivial.