The new JavaScript Incremental Computing Library provides a better user experience for single-page applications

The team behind the collaboration board tldraw recently released a library that brings incremental computing to JavaScript. Signia strives to overcome the fundamental performance limitations of tldraw’s choice of UI and reactive framework, ultimately providing better interactive applications with a better user experience. However, Signia can be used on its own 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 a lot of data in memory that changes frequently, much of which comes from other data.
We spent several months building a new version of tldraw using a popular reactive state framework. However, we quickly ran into two big issues that made it impossible to accommodate the number of shapes and multiplayer users we knew browsers could handle.

[…] Both of these issues were fundamental limitations of the framework’s reactivity model.

Derived data would be recomputed every time their data dependencies changed. These recalculations can be expensive for large derived collections. In some contexts, derived data can also be recomputed if it could be fetched from the cache instead.

Highly interactive single page web applications like tldraw tend to see user experience as a key element of their value proposition. Responsiveness to user input, itself a key component of user experience, is related to the amount of computation triggered on the main thread.

Part of the calculation is due to the game’s framework. At some scale, performance gaps from the framework can noticeably affect the user experience and must be addressed. Raph Levien, in his article Towards a unified theory of the reactive user interfacesaid:

React is most famous for introducing the “virtual DOM”. It works well on small systems, but causes serious performance problems as the user interface scales. React has many techniques to work around full-tree differences, which is pragmatic, but again makes it difficult to develop a clean mental model.

Some developers may use reactive data libraries (eg jotai, recoil, zustand) to reduce the amount of unnecessary calculations performed by the framework. Alternatively, they can turn to UI frameworks that already embed similar reactive data capabilities and perform less unnecessary computation.

Another part of the calculation to be performed concerns the synchronization of the dependent data with their dependencies. Efficiency is achieved by computing dependent data lazily (as needed) instead of eagerly (as soon as their dependency changes); once instead of changing a dependency each time (e.g. through topological ordering of the reactivity graph); or more efficiently. Incremental computing handles computation-dependent data faster.

As Denis Firsov and Wolfgang Jeltsch explained in their paper (Purely functional incremental computing):

Many applications need to maintain evolving data sources and views of those sources. If the sources change, the corresponding views must be modified. A complete recalculation of views is usually too expensive. Another option is to convert source changes to view changes and apply them to views. This is the key idea of ​​incremental computing.

Signia’s documentation shows an example of derived data that can be useful with incremental calculation. Let’s assume an array arr of 10,000 values ​​and a derived variable y as arr.map(f). When arr gets a new value valnaive way to recalculate y is to run the map operation above the value 10,001. With the incremental computation approach, the cached mapped array of 10,000 values ​​is simply appended f(val). This leads to a single run f vs. 10.001 for the naive approach. The incremental approach generalizes a
filter, reduce, sortand many other operations (see Self-adjusting calculationUmut A. Acar, 2005).

Signia provides a reactive API that allows developers to define, among other things atoms (independent data) and it mattered data (derived from atoms), along with the appropriate 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 computation APIs that store a history of input changes. The API user can then incrementally calculate the updated derived value from the cached derived value and the change history. Signia’s documentation provides an example of leveraging Immer’s immutable state library patch format. Changes are stored as actions in the system (e.g. add it, change it, remove it), which match the corresponding incremental calculation with a pattern (e.g. splice).

Incremental computing is not a new approach. JSON patching can be used to avoid sending the entire document if only part of it has changed. Used in conjunction with the HTTP PATCH method, it allows HTTP APIs to be partially updated in a standards-compliant manner. The D3 visualization library allows developers to incrementally define how to update a visualization enter, updateand exit from the input data.

However, Signia is new in that it provides a generic JavaScript API for incremental computation. The commercial company Janestreet maintains a like-minded OCaml library additional. Yaron Minsky noted already 7 years ago:

Given that incrementality appears in all web frameworks in one form or another, it’s quite striking how rarely it is discussed. Of course, when we talk about virtual DOM, people tend to focus on the simplicity of blindly generating the virtual DOM and letting the diff algorithm solve the problems. We leave the subtleties of incrementalization as a footnote.

This is understandable, as for many applications you can get away without worrying about increasing the virtual DOM computation. But still, it’s worth paying attention to, since more complex user interfaces require incrementalization, and the incrementalization strategy has quite a profound influence on the design of the UI framework. […] To think about something Additional in the context of GUI development, it led us to some new ideas about creating powerful JavaScript GUIs.

Signia is open source software released under the MIT license. Feedback and comments are welcome and must follow our contribution guidelines.