I could have just implemented GOTO (Generic Operational Transformation Optimized) with Tombstone Transformation Functions, and that that would have made a pretty good demonstration of collaborative editing with a small, simple codebase. That would have had most of the advantages I’m claiming, including the ability to work in arbitrary peer-to-peer network topologies rather than requiring a centralized server. In addition, since OT techniques represent the string as a string rather than a graph or tree of character nodes (as in WOOT and similar CRDT’s), they are quite RAM-efficient. I don’t consider GOTO to be harmful.

But I went farther. In particular, my code has an efficient (balanced binary tree) data structure for representing sets of indices. Even so, the entire codebase, including admittedly very sparse UI, is 400 lines of JavaScript, probably one of the smallest and simplest collaborative editing prototypes ever shown.

Efficient tombstones

The tombstone approach represents the document as a sequence of all characters ever inserted, whether they were deleted or not. The traditional tombstone approach would be to store those characters in a string, alongside a set of deleted characters. To reconstruct the actual document, you’d apply a read function consisting of deleting the characters from that set (this is called viewToModel in the TTF paper).

However, it’s not actually necessary to store the deleted characters in the string, only to record the fact that the character has been deleted. The TTF paper (in section III.D) describes how to do this; you delete characters out of the string, and keep a data structure alongside that tracks deleted characters. There are two coordinate spaces, one indexing the string, and one indexing the (virtual) string that also contains the tombstones. The TTF paper suggests a straightforward linear-time algorithm for computing the transform between these two spaces.

My code stores the set of deleted indices in a balanced binary tree, and can compute both the forward (xi in the code) and inverse transformation (xi_inv) in O(log n) time. Operations to delete a single character (union_one) and increment all indices past an insertion point (xi_one) are also logarithmic. The data structure is about 150 lines of JavaScript, a non-trivial fraction of the total, but the efficiency improvement is substantial.

Using a set to represent a coordinate transform has some interesting mathematical properties. Here’s a mathematical description of the forward transformation of the index i through the set S:

Ξ_{S}(i) = maxⱼ|{k | k<j ∧ k ∉ S}| = i

And here’s a picture of the transformation, for a single character at index 1. Note the similarity to the traditional OT transformation for insertion:

The forward transform is a strictly increasing function over the natural numbers. There is a one-to-one correspondence between sets and such functions; for example, the set of non-primes would represent the function giving the nth prime. The composition of such functions is associative, which is a valuable property for manipulating them more efficiently. (The JavaScript codebase doesn’t have a function for directly composing two such sets, but there is an implementation in xi-editor, based on a run-length rather than balanced binary tree representation of sets). I don’t know of any existing mathematical literature that deals with or generalizes these concepts, but I wouldn’t be surprised to learn of it.

Efficient merge using coordinate transformation

The inner loop of GOTO’s merge operation strongly resembles an insertion sort; it does pairwise transposition of adjacent operations in the log until it’s ordered appropriately (which in this case means that the operations present in the incoming operation’s context all precede those not present in that context). That algorithm is, like insertion sort, O(n²), where here n is a measure of the number of concurrent operations in flight.

The traditional OT model requires consideration of one operation against only a single other operation. In that model, it’s hard to imagine doing better than quadratic. However, my code is not constrained to compute IT and ET transforms on pairs of operations. Rather, I use that same O(log n) data structure to represent the effect of jumping over a whole sequence of n operations. Thus, my merge algorithm (merge_op in the code) is O(n log n), a significant speedup from, as far as I know, any previous known OT algorithm.

If you look at the merge_op code, it’s fairly dense mathematically, even though not very many lines of code. For the brave and curious who want to dig into it, it will probably help to know that it computes exactly the same thing as Algorithm 2 in the GOTO paper, just more efficiently. The loop over transform_ins near the end of the function is pretty much just LIT from the GOTO paper.

An invitation

I believe the ideas in this code would make a pretty good academic paper. Among other things, the asymptotic complexity bounds are significantly improved from previous results. Further, while this implementation is obviously a toy, I think it could be the basis for a practical, efficient collaborative editing system.

Unfortunately, this work has been very much a side project, and it’s very hard for me to find the time to prepare a proper academic paper. There’s quite a bit to do, including making a convincing argument for the correctness of the whole thing. I personally believe it’s correct based on automated randomized testing of an earlier prototype, but an analytic argument would be better for an academic paper.

I think that taking this work to a publishable paper would make an excellent project, potentially at the scope of a Master’s thesis. If there’s anyone out there who is interested, I’d be interested in a collaboration.

In the meantime, I did want to get this code out there, so that people building the next generation of collaborative editing systems can see the value in adopting a hybrid approach that combines the best advantages of both Operational Transformation and CRDT.

Performance results

First, the numbers. This is a measurement of how long it takes to render “g” from Roboto Regular, at pixel/em settings between 1 and 200. Measurements were done on a 2.9 GHz Xeon E5–2690. The comparisons are FreeType 2.6.5, font-rs using only pure Rust, and a version of font-rs with SIMD speedup.

With the SIMD speedup, font-rs is approximately 7.6x faster than FreeType in larger sizes (keep in mind that 42 pixels/em is the default for xxhdpi Android devices). Even at a relatively small size of 12 pixels/em, it’s over 4x faster. The speedup is even bigger (over 6x at 12 pixels/em) when measured on a CJK typeface (the majority of CPU cycles spent rendering fonts in the world).

Font rendering, where does the time go?

There are basically 3 CPU-intensive components to font rendering: parsing the binary outline from the font, drawing into an accumulation buffer, and integrating the accumulation buffer, storing the results into an 8 bit per pixel bitmap.

During drawing, the accumulation buffer stores the finite difference (in scan-line order) of the actual signed area. All pixels fully inside or outside the glyph (not touched by the edge) are zero. More importantly, in the first difference, the sum of the signed area is just the sum of the contribution of each of the edges.

For more details on the signed area approach, see How the stb_truetype Anti-Aliased Software Rasterizer v2 Works.

Here’s a graph showing the breakdown:

One interesting observation is the contrast between asymptotic complexity and associated constant factors. The accumulation buffer is O(n²), so allocating it and filling it with zeros is also quadratic. But it’s such a trivial operation that it hardly contributes. Drawing the path is O(n), but with a large constant factor because it’s doing complicated exact-area calculations for each pixel crossed by the outline. Finally, integrating the accumulation buffer is also O(n²), but insignificant at sizes up to 60 pixels/em or so. For very large glyphs, the quadratic parts would dominate.

Parsing: no allocation

Font-rs takes about 460ns to parse the binary font data and convert it into a sequence of lines and quadratic Bezier curves. There are 30 such, so it’s about 15ns per path element.

Usually, binary parsers are written as a function that accesses the binary font data, and produces a data structure (often a vector) containing the result. However, just collecting the result into a vector per contour would add 870ns, almost tripling the parsing time. At normal text sizes (where total rendering time is ~5µs), this added time would be significant.

By contrast, in Rust it is very idiomatic to write the parser as an iterator, an object with a `next` method called repeatedly. The state for these iterators is usually allocated on the stack, rather than on the heap. Thus, parsing takes place with absolutely no heap allocations.

The font-rs parser is actually written as two iterators, composed together. The first parses the binary font data into a sequence of on-curve and off-curve points, and the second converts that into lines and beziers. It’s possible to write Rust-style iterators in other languages, but it’s not especially common to see. Note, though, that there is a library for C++, intended to eventually become part of the standard.

Drawing into the accumulation buffer: dense and immediate

Different renderers use different strategies of how to store the accumulation buffer, and when to sequence drawing operations into it. Many renderers (including FreeType) use a sparse representation, trying to exploit the fact that many entries remain zero. Further, many renderers try to order the rendering by scanlines, or at least stripes. This requires some reordering, as the outlines are not stored in scanline order.

The approach of font-rs is to represent the accumulation buffer as a simple array, one 4-byte float per pixel. Thus, addressing the buffer is one machine instruction, with no branches. In addition, all drawing operations come straight from the parser into the buffer.

Sparseness is always a tradeoff. At a certain point, not having to touch empty parts of the structure exceeds the overhead from the sparse representation itself. Where this tradeoff crosses over depends on the problem and the size of the datasets. However, dense representations have a huge advantage when data-parallelism is an option, as we’ll see in the next section.

Final integration: SIMD

The integration consists of four operations, applied to every pixel: cumulative sum, absolute value (to implement the nonzero winding rule), clamping to [0, 1], and conversion to an 8-bit pixel. There are SIMD techniques for cumulative sum, and the other three are embarrassingly parallel. In addition, since cumulative sum is usually latency-limited, interleaving the two can be even faster than doing them separately.

Another innovation in font-rs is to just run cumulative sum over the entire buffer, rather than restarting a loop at every line. Thus, the inner loop runs very “hot” with basically no overhead due to branch mis-prediction. In addition, the width doesn’t need to be aligned to any power-of-2 boundary.

I wrote the inner loop in about 15 lines of SSSE3 intrinsics. Since Rust doesn’t (yet) have SIMD intrinsic support, I wrote those in C. Fortunately, dropping a C function into a Rust codebase is pretty easy. At larger sizes, the speedup is dramatic, more than double. At smaller sizes, the impact is not so great, dominated by the O(n) path drawing.

What next?

Possibly font-rs becomes production-ready. This would depend on community interest. Another definite possibility is to adapt the ideas into existing renderers such as FreeType. In any case, font-rs shows what performance is possible. It’s also a strong demonstration that Rust is an appealing language for creating “fastest in class” modules. It has essentially the same performance as C++ for low-level fragments of code, but better support in the language and standard library for stitching these low-level fragments into higher level constructs that match the semantics of the problem being solved.

The future of fast rendering may not be software. New advances in GPU-based rendering, particularly Multi-channel signed distance fields, may yield even higher performance. However, those techniques usually require a time-consuming preprocessing step, and nontrivial memory to hold the intermediate bitmaps. For the task of going from a binary font to rendered pixel data, software renderers such as font-rs still deliver the absolute lowest end-to-end latency.

Lately I’ve been diving deep into the literature on collaborative text editing. There are basically two opposing camps: Operational Transformation, which dates back to the 1989 Grove system and is the basis of most collaborative editors today, and the much newer Conflict-free Replicated Data Types (CRDT) approach. However, I’ve come to realize that there is a common theory which unifies at least a subclass of OT and CRDT’s. I believe the two camps have potentially much to learn from each other.

The so-called Transaction Property 2 (TP2) is something of a faultline running through the OT literature. A landmark 1996 paper by Ressel et al introduced the property, proved that it was necessary and sufficient for correctness of their system, then proceeded to propose a set of operations for editing strings that, in hindsight, did not satisfy TP2. Oops. For a decade or so, TP2 was something of a philosopher’s stone, with several alchemists of OT claiming that they had found a set of transforms satisfying TP2, only for counterexamples to emerge later. Only with the 2006 publication of Tombstone Transformation Functions was actual gold struck, but at a cost; instead of doing insert and delete operations directly on the string as in the original OT vision, the document state is augmented with tombstones that record the locations where deletions would happen. A separate read function is required to erase the tombstones and yield the user-visible string.

Incidentally, the authors of the tombstone paper were, at the same time, working on WOOT (“WithOut Operational Transformation”), which is now seen as an early instance of CRDT. The CRDT approach uses a simple merge function, basically a generalization of set union (more formally, monotonic operations over a semi-lattice, which has a commutative, associative, and idempotent join operator), and an even more complex read function to reconstruct the string from the document state. Even so, it is appealing because the simple merge function means that it is very easy to reason about convergence.

Almost all practical implementations of OT forego TP2, and solve the problem by limiting concurrency in some way, generally requiring a central server to decide on a canonical ordering of the operations (but still using transformations to let clients apply operations out-of-order just a little bit). In fact, practical OT today is based firmly on the 1995 Jupiter system, with approximately the last 21 years of academic work having essentially no impact. I should mention Google Wave here, which restricts concurrency even more (only allowing a single operation from each client in flight). This approach simplifies the construction of servers, but still has basically the same concurrency and operation model as Jupiter. Jupiter and Wave are based on a strict serialization concurrency model, while both CRDT’s and OT with TP2 are eventually consistent. A good paper is Specification and Complexity of Collaborative Text Editing, which also characterizes the former as satisfying the weak list specification, while the latter satisfies the strong counterpart.

Adopting TP2 eliminates the need for the central server, allows peer-to-peer configurations, and can reduce latency (including eliminating the need for Wave-style “batching” of operations). It’s possible to implement OT with TP2 reasonably simply and efficiently, but this fact doesn’t seem to be much appreciated in the oral tradition of people actually building OT systems. I’d like to try to change that, a bit.

An OT system satisfying TP2 has properties very similar to CRDT-based text editing. I’ll argue that this is no coincidence, that a unified theory underlies both.

I’ll try to explain an idealized OT system, closely based on GOTO (Generic Operational Transformation Optimized) and SOCT2 (Sérialisation des Opérations Concurrentes par Transposition). This will necessarily be a high-level overview, and for a full understanding readers are directed to those papers (with considerable sympathy from me, the OT literature as a whole is difficult).

This OT system represents the document state as a history log, which is at heart a sequence of operations. The key to OT is that each operation has a context, basically the set of operations that precede it in the log, and that contexts always match up. When merging an operation from another node’s document state, the context in general won’t match up, so the operation needs to be transformed. The standard notation for this is IT(Oa, Ob), where Oa and Ob have the same context, yielding a transformed O’a. This transformed operation additionally has Ob in its context, but does the same thing as the original Oa. In this notation, IT stands for “Inclusion Transformation”. Early OT systems used just IT, but this approach requires keeping the original transformations, some explicit representation of context, and a lot of juggling.

Transformation of operations changes their contexts, but it also makes sense to track their original context (that is to say, not affected by the transformation). When one operation appears in the original context of a second, we say that the second is causally dependent on the first. When neither appears in the other, we say they are concurrent.

SOCT2 and GOTO use a second transformation, often written ET (Exclusion Transform. It’s basically an inverse of IT, and removes one operation from an operation’s context. I prefer transpose(Oa, Ob), where the context of Ob is that of Oa plus Oa itself, yielding O’b and O’a in which the context relation is reversed. The context of O’a is that of O’b plus O’b itself. You can write transpose in terms of ET: transpose(Oa, Ob) = [ET(Ob, Oa), IT(Oa, ET(Ob, Oa))].

The idea of these two algorithms is that doing the transpose doesn’t affect the semantics of the history log as a whole. Also, you don’t need the original operations, so it can be done more simply and efficiently. The correctness of these algorithms relies on the fact that you only do the transpose on concurrent operations, that is to say all the permutation respects the partial order of original context. Of course, proving such a thing is not easy. Frankly, I didn’t really understand the proofs in those papers, and didn’t really trust that it was true until I did automated randomized testing on my own implementation.

It’s also important to note that the TP2 property is required for all this to work. Otherwise, you’ll find that while the transposes don’t affect the document, they do affect how an operation is transformed through a sequence of other operations. TP2 gives you exactly the guarantee you need: as long as the two operations are concurrent with respect to their original context, the transpose basically doesn’t change anything; there’s no way to observe the difference.

I’ll dive into a little more detail. Consider a peer-to-peer model where every node has its own copy of a document state. Each peer is continually sending updates to all its neighbors (the topology can be anything from a star to a spanning tree to a complete graph). The communication is assumed to be in-order, but of course is subject to unpredictable delays (essentially the same communication model of TCP/IP and WebSockets). To simplify, an update is considered appending one operation to the node’s document model.

When a node receives an update from another node, it’s already received all preceding updates (thanks to the in-order nature of the communication channel), and has merged these into its own document state. Its document state contains all operations of the other node’s document state, plus additional operations that the other node had not (yet) seen at the time it sent the update. If, in a lucky coincidence, these operations are clustered so all those in the second set come after those in the first, doing the transformations is easy, just do an IT transformation of the new operation through each of those in sequence. This figure shows it graphically:

Here, the white squares represent operations common to both document states. The three light shaded squares are additional operations we have that the other node hasn’t seen. The dark shaded square is the new operation from the remote node that we want to integrate. As stated above, we just run this new operation through an IT transform of the three operations we have that the other node doesn’t. If you’re following along with the GOTO paper, the sequential application of IT transforms is the LIT function, and the above picture corresponds to case 2 in their Algorithm 2.

The above is the case where these light-shaded operations are clustered together. Note that this can be enforced when there are only two concurrent users (basically the case that the original Grove system handled correctly). Things get more complex when there are three or more. The central idea of GOTO and SOCT2 is to permute the history log, using transpose operations as defined above, to establish that clustering. Without presenting the algorithm in detail (see the papers), the following figure should give a good idea what’s going on.

Here, each point where two arrows cross is a transpose operation. If you’re following along with the GOTO paper, each line in the above figure corresponds to one invocation of their LTranspose function, and the above picture corresponds to case 3a in their Algorithm 2.

The concept of transposing and permutation is also, I think, the key to analyzing these OT algorithms in the CRDT framework. Define an equivalence relation: two document states are equivalent iff one is a permutation of the other, and all swap operations comprising the permutation respect the partial order induced by original context. Under this equivalence relation, the merge operation on two document states satisfies the semilattice property required by CRDT; merge is commutative, associative, and idempotent. Proving that formally is an exercise for the reader, but it basically follows from the correctness proofs of GOTO and SOCT2 (again, the reader has my deepest sympathies).

There’s one small sleight-of-hand here. The equivalence relation above is defined on mathematical objects in which each operation contains its original context. Let’s say you’ve got two document states in which one user has typed “a” and the other user has typed “b”. If these operations happen concurrently, then the document states [Oa, O’b] and [Ob, O’a] are considered equivalent. However, if the second user waits for the first operation, then they’re not. The GOTO and SOCT2 algorithms don’t carry this extra metadata around in the document state. Even though that means they’re missing information needed to evaluate the equivalence relation, from a practical perspective I consider that a good thing. In fact, I’d say that one of the strongest criticisms of CRDT is that it generally requires a lot of metadata to build a tree or graph structure to make merging easier, which is then erased in the read function. Keeping that around requires more RAM and more communications bandwidth, compared to more OT-flavored approaches.

You could hand-wave and say that a theoretical model of GOTO/SOCT2 that includes the context metadata is a CRDT, and that erasing this data is merely an implementation detail, but to me that’s unsatisfying. If the definition of the equivalence relation includes the original context, then the document state of a GOTO/SOCT2 algorithm is not a CRDT under that definition.

There is an alternative, which I personally find more appealing. Instead of saying that two operations can only be transposed if they were in fact concurrent, loosen the definition. Basically, if the history can be explained by two concurrent operations, allow the swap. In the example above, let’s say that the tie-breaking rules place edits from user A before those of user B on concurrent insert. So “a” and “b” entered concurrently result in “ab”. Allow “ab” to be swapped whether the operations were in fact concurrent or not, as there is no difference in the observable state. There are no two concurrent operations that can yield “ba”, so that pair would still not be swappable.

More formally, consider the sequence [Oa, Ob] to be transposable iff IT(Oa, O’b) = O’a, and IT(O’b, O’a) = Ob, where [O’a, O’b] = transpose(Oa, Ob). In the “ba” example above, this would fail, as Oa and O’b would be concurrent inserts of “a” and “b” at the same location, and the tie-breaking rule in IT would resolve those to “ab”, not a match.

Since this new equivalence relation is defined entirely on information actually contained in the document state, the GOTO/SOCT2 merge operation can then rightfully be considered a CRDT (assuming no correctness mistakes, of course).

Further, I’d say that the looser equivalence relation is actually useful, not just a mathematical trick. For example, you can permute the document state so that it compresses better. If two users are concurrently typing in distant parts of the same document, then the original context induces nearly a total order (actually a total order if latency is fast enough), but in reality the edits of one user can be transposed with the edits of the other without harm. The looser equivalence relation lets you do that.

What of non-TP2 operational transformation? I’ve thought about ways of jamming that into the CRDT framework. In particular, you can attach a timestamp to each operation, then use a read function to play the operations back in timestamp order. In practice, while this might be a CRDT in some technical sense, it’s a really bad one. If you integrate an operation with an early timestamp relative to the rest of your buffer, then it can force replay of a lot of operations, which is both slow and can make weird changes to the document. In particular, situations like TP2 puzzles (see Fig. 3 of the tombstone paper for a great explanation) can cause the reordering of big chunks of text, which would usually be a terrible experience. If these are your transformation functions, it’s better to rely on a central server to actually limit concurrency so that doesn’t happen.

Thus, I assert that the TP2-conforming subclass of OT can be considered an instance of CRDT, and so the OT and CRDT camps aren’t as far apart as maybe they first seemed. The OT camp offers efficient implementation techniques, in particular teaching that retaining graph-structure metadata is not absolutely required. In turn, the CRDT camp offers a sounder basis for mathematical reasoning (the track record of the OT literature certainly demonstrates that it is very difficult to reason about the correctness of OT transformations) and a potentially rich set of techniques for composing and combining CRDTs.

I hope this blog post suggests ways for the OT and CRDT communities to work together. I’d also encourage designers of collaborative editing systems (and academic researchers) hoping for the benefits of CRDT (in particular, peer-to-peer operation rather than requiring a centralized server) to take another look at OT. Just because there are so many flawed proposals in the literature is not a good reason to write off the entire field in favor of the seemingly greener pastures of CRDT.