nikomatsakis/pjs — Issue #2: refactor atoms table (and possibly other structures) to avoid locks
Author: nikomatsakis
Created: 2012-03-07 23:32:45+00:00
State: open

Currently, there is still a need for some locks in the JSRuntime, but they really ought not to be required. Instead, we might consider moving those data structures which can be used by parents and children into an auxiliary, tree-shared structure that mirrors the task tree.

The following extract from an e-mail summarizes the idea (and a possible implementation scheme) in the case of atom tables:

> Well, maybe I start to see a glimpse of what you are saying. I can imagine that there are numerous data structures that could be independent of a runtime. Imagine, for example, a tree of atom tables that mirrors the task structure. Now, to look up an atom, I begin by searching my own table and conceptually walk up to the tables of my parents: if I fail to find a match, then I can create the new atom in my table. To make this faster, you don't have to actually iterate, but you can instead use a persistent b-tree-like structure so that there is only one lookup (like the maps used in Clojure or functional languages). This seems like it would work and would be equally fast (at least theoretically) in the single-threaded case, as the map would just be a hashmap there.

> I've always wanted to build semi-persistent data structures. Maybe this is my excuse. That is, where a traditional persistent data structure is one that is never updated in place, a semi-persistent one would be a data structure where you can do either in-place updates or persistent updates. If you do a persistent update, the result is a new data-structure that makes as much use of the internal nodes from the other data structure as possible. You can then make in-place updates to this new data structure, and in each case it will try to reuse the parent structure where possible. This scheme only works if you have a tree-like pattern like the one I'm talking about, or if you can be sure that the parent data structure is immutable.