Implementation of JavaFX sequence updating
Sequences in JavaFX are powerful, but it is difficult to implement them efficiently. The basic problem is illustrated by this:
var x = [....]; var y = x; x[i] = a; // y[i] must not be modified.
Note the distinction between an immutable sequence value
,
vs a sequence variable
,
which is a named location which can contain different
sequence values at different times.
We will distinguish between (plain) assignment to a
sequence variable:
y = x;
versus modification of a sequence variable, which modfies the old value in some way, either by indexed assignment, inserting new elements, or deleting old elements.
So let's look at various ways to implement the desired semantics.
The copy-on-assignment approach
This is fairly simple. A sequence is implemented on top of an array.
When we assign the sequence to another variable (as in the
initialization of y
from x
above)
we copy the entire sequence including the underlying array.
Then the modification of x
is implemented
by modifying x
's underlying array, without
bothering y
. Sequence indexing is fast for both
read and write. What becomes expensive is sequence assignment,
which includes initialization of sequence variables,
and passing of sequence parameters. The latter might be mitigated
if we're sure the argument isn't modified during the function,
as is normally the case, but that becomes tricky to verify.
The copy-on-shared-write solution proposed later can be thought
of as delaying the copying until needed: Instead of actually
copying the sequence, we set a shared
bit to force copying
if there is a subsequence modification.
The copy-on-modification approach
Another solution is to translate:
x[i] = a;to:
x = [x[0 ..< i], a, x[i+1 ..]];
I.e. we implement modification by creating a new sequence with all the original elements plus the one modification. This is simple, correct, and has fast read performance, but even a single-item modification requires copying the entire sequence.
The delta-chain approach
Rather than creating a modified x we can create a "delta":
x = new ElementReplacementSequence(x, i, a);where
ElementReplacementSequence
is:
class ElementReplacementSequence<T> extends AbstractSequence<T> { Sequence<T> original; int replacementIndex; T replacementValue; public ElementReplacementSequence(Sequence<T> original, int replacementIndex, T replacementValue) { this.original = original; this.replacementIndex = replacementIndex; this.replacementValue = replacementValue; } public T get(int i) { return i == replacementIndex ? replacementValue : original.get(i); } public int size() { return original.size(); } }
This approach was used initially in JavaFX, and had the
advantage of simplicity, correctness, and moderately fast write performance.
(You do have to allocate a new
ElementReplacementSequence
each time.)
It's appealing because we never modify a sequence, only
sequence variables. Thus both the old and new value are directly
accessible, which makes triggers nice and easy.
However, naively implemented it has horrible read performance:
After 1000 replacements, x
will be a chain
of a 1000 ElementReplacementSequence
objects
which has to be searched linearly.
Michael Heinrichs and Brian Goetz implemented various heuristics to come up with a hybrid of delta-list and eager copying: When the delta-list becomes too long or the sequence is short anyway just copy it. This has worked reasonably well in practice, but it's pretty ad hoc, and we're still doing quite a bit more work on both reads and writes compared to indexing into an array.
Persistent arrays
The logical extension of the delta-chain approach
is to use a persistent array
(see
Wikipedia
for some links). This would have the nice properties of
the delta-chain appraoach, but using algorithms and
data structures with guaranteed performance bounds:
either O(1) or at worst O(log(N)), which is presumably tolerable.
An issue with persistent arrays is that the desired performance guarantees require some non-trivial data structure and algorithms, but that is compensated by simplicity elsewhere. A bigger problem is that overhead and constant factors are likely to be significant. I'm guessing that the storage needed would at least be double that of a plain array (consider the extra pointers and flags needed for most balanced-tree implementations); memory locality would be much worse; and tree walking and management would be markedly slower than array indexing.
The copy-when-shared solution
We can optimize the copy-on-modification approach: If the sequence value is represented using an array and there is no other reference to the sequence, then we can just modify the array in place. How do we check that there is no other reference to the sequence? The classical method is to use a reference count. However, maintaining an accurate reference count is expensive, especially if it's not doing double-duty for memory managment. However, we don't need accuracy: If we know there is exactly one reference, then we can modify the underlying array in-place; otherwise (including when we're not sure) we copy, to be safe. Likewise, if the old value is not anArraySequence
(for example it might be a IntRangeSequence
),
then modifying in-place doesn't make sense, so we first
copy the old value into a fresh unshared ArraySequence
before doing the modification.
Even a single-bit reference count works pretty well:
We set that bit (the shared
bit) whenever sharing is introduced.
The original algorithm was to set the shared bit whenever we access
(read) a sequence in a way that could cause sharing.
Reading a single item or the size of a sequence does not cause sharing,
so we don't set the shared bit in those cases.
Using a single bit causes performance loss in some cases:
var x = [ ... ]; ... some modifications to x ....; some_function(x); ... more modifications to x ....; another_function(x);
When some_function
is called, we cause
the current value of x
to be shared. Thus any
more modifications
will force a copy. But almost always
the sharing in some_function
is temporary and harmless, as the
function does not does not modify x
.
However, it's difficult to statically verify this.
One way to solve this is to use a multi-bit reference count,
and make sure we decrement the count. The plan is to add
this in the future. (It is partially implemented.)
Buffer-gap arrays
Replacing a sequence element in-place
is easy to implement
by just modifying an element in the underlying array.
Insertions and deletions may require more work, including
copying elements and allocating a new bigger array.
If insertions and deletions are infrequent, or tend to
cluster or be sequential then it works pretty well to use
a gap buffer
as used by Emacs
and Swing's GapVector
.
This data structure has low memory overhead (basically just the
gap), fast read access, and good memory locality:
There is no pointer-chasing
as in balanced-tree or linked-list data structures.
Modifications that are sequential or clustered around the same position
are also fast, since we don't need to move the gap
much. For example, building a sequence by incrementally
appending new elements is fast, as is replacing all the elements in order.
Modifications that jump around
in the sequence
can be expensive, because you have to move the gap
to the position of the modification. This means copying
elements between the current gap position to the
position of the modification.
The hope is programs that do this are relatively rare,
and the slowness of this case is more than made up for
other common cases being fast.
Note that single-element writes are fast, but only if there are no triggers or other dependencies. See this article for how triggers are implemented.