Article originally posted on InfoQ. Visit InfoQ

The team behind the collaborative whiteboard tldraw recently published a library that brings incremental computing to JavaScript. Signia seeks to overcome fundamental performance limitations of tldraw’s chosen UI and reactive framework and ultimately provide better interactive apps with better user experience. Signia can however be used standalone or in conjunction with any UI framework.

The tldraw team explained their motivation as follows:

tldraw is a collaborative digital whiteboard built with React. It has an unusually active client state, with lots of in-memory data that changes often and much of which is derived from other data.
We spent several months building tldraw’s new version using a popular reactive state framework. However, we quickly ran into two big problems that made it impossible for us to scale to the number of shapes and multiplayer users that we knew browsers could handle.
[…] Both issues were fundamental limitations of the framework’s reactivity model.

Derived data would be recomputed every time their data dependencies would change. Those recomputations could be expensive for large derived collections. In some contexts, derived data may also be recomputed when they could be retrieved instead from a cache.

Highly interactive single-page web applications like tldraw generally consider the user experience to be a key component of their value proposition. The responsiveness to user inputs, itself a key component of the user experience, relates to the amount of computation that they trigger on the main thread.

A part of the computation occurs due to the framework at play. At some level of scale, the performance inefficiencies due to the framework may noticeably impact the user experience and must be addressed. Raph Levien, in his article Towards a unified theory of reactive UI, said:

React is most famous for introducing the “virtual DOM”. It works well for small systems but causes serious performance issues as the UI scales up. React has a number of techniques for bypassing full tree diffs, which is pragmatic but again, makes it harder to form a clean mental model.

Some developers may resort to reactive data libraries (e.g., jotai, recoil, zustand) to reduce the amount of unnecessary computation performed by the framework. They may alternatively resort to UI frameworks that already embed similar reactive data capabilities and perform less unnecessary computations by design.

Another part of the computation to perform relates to keeping dependent data synchronized with their dependencies. Efficiency can be gained by computing dependent data lazily (when needed) instead of eagerly (as soon as their dependencies change); once instead of every time one dependency changes (e.g., through topological sorting of the reactivity graph); or more efficiently. Incremental computing deals with computing dependent data faster.

As Denis Firsov and Wolfgang Jeltsch explained in their paper (Purely Functional Incremental Computing):

Many applications have to maintain evolving data sources as well as views on these sources. If sources change, the corresponding views have to be adapted. Complete recomputation of views is typically too expensive. An alternative is to convert source changes into view changes and apply these to the views. This is the key idea of incremental computing.

Signia’s documentation gives an example of derived data that may benefit from incremental computation. Let’s assume an array arr of 10,000 values, and a derived variable y obtained as arr.map(f). When arr is pushed a new value val, a naïve way to recompute y is to rerun the map operation over the 10,001 values. With an incremental computing approach, the mapped array of 10,000 values that was cached is simply appended f(val). This leads to one single run of f vs. 10,001 in the case of the naïve approach. The incremental approach generalizes to
filter, reduce, sort, and many other operations (see Self-adjusting computation, Umut A. Acar, 2005).

Signia provides a reactive API that allows developers, among other things, to define atoms (independent data) and computed data (derived from atoms), together with the respective setters and getters:

import  { computed, atom }  from  'signia'
  
const firstName =  atom('firstName',  'David')
firstName.set('John')  
console.log(firstName.value)  
firstName.update((value)  => value.toUpperCase())  
console.log(firstName.value)  

firstName.set('John')  
const lastName =  atom('lastName',  'Bowie')  
const fullName =  computed('fullName',  ()  =>  {  
  return  `${firstName.value} ${lastName.value}`  
})  
  
console.log(fullName.value)  

To these reactive APIs, Signia adds incremental computing APIs that store a history of input changes. The API user can then incrementally compute the updated derived value from the cached derived value and the change history. Signia’s documentation provides an example that leverages the patch format of the immutable state library Immer. Changes are stored as operations (e.g., add, replace, remove) that are pattern-matched to the corresponding incremental computation (e.g., splice).

Incremental computing is not a new approach. JSON Patch can be used to avoid sending a whole document when only a part has changed. When used in combination with the HTTP PATCH method, it allows partial updates for HTTP APIs in a standards-compliant way. The D3 visualization library lets developers specify incrementally how to update a visualization on enter, update, and exit of input data.

Signia is however new in that it provides a generic JavaScript API for incremental computing. The trading firm Janestreet maintains a similar-minded OCaml library called incremental. Yaron Minsky noted already 7 years ago:

Given that incrementality seems to show up in one form or another in all of these web frameworks, it’s rather striking how rarely it’s talked about. Certainly, when discussing virtual DOM, people tend to focus on the simplicity of just blindly generating your virtual DOM and letting the diff algorithm sort out the problems. The subtleties of incrementalization are left as a footnote.

That’s understandable, since for many applications you can get away without worrying about incrementalizing the computation of the virtual DOM. But it’s worth paying attention to nonetheless, since more complex UIs need incrementalization, and the incrementalization strategy affects the design of a UI framework quite deeply […] Thinking about Incremental in the context of GUI development has led us to some new ideas about how to build efficient JavaScript GUIs.

Signia is open-source software released under the MIT license. Feedback and contributions are welcome and should follow the contribution guidelines.