By the way, as someone who has published academic papers, if you're ever bothered about a paper or have some comments, don't hesitate to mail the authors. (Their e-mail addresses are always on the paper; especially target the first author because they have normally done the work.) We are happy to hear when someone has read our work and I at least would've liked to have known if someone found a problem with my papers.
Faster CRDTs: An Adventure in Optimization
81–90 of 154 posts
Re: Faster CRDTs: An Adventure in Optimization
#82Excellent article! As someone who has to work with collaborative editing I must say the complexity of the whole area is at times daunting to say the least. So many edge-cases. So many mines to step on.
Now I think I am convinced that the OT vs CRDT performance comparison is kind of moot point and the question is more about the user experience. Which version produces nicer results when two very diverged documents are merged. Maybe one of these days I'll read an article about that too.
To get off on a tangent a little bit, I'd be interested to know how one could add in tracking of changes to Diamond or other CRDT? Can you add an arbitrary payload to the operation and then just materialize the areas different from the original snapshot? I know Yjs can do this by creating snapshots and then comparing them to another snapshot but it seemed a bit awkward and not suited for real-time editing.
Re: Faster CRDTs: An Adventure in Optimization
#83Very nice, when I read "double linked list" I immediately thought "what about a btree like structure?" I guess Martins idea to replace the IDs comes from the "vector clock" idea for concurrent updates
If anyone is looking for the combination of a piecetable and b+tree (which appears to be what is talked about in this article), I have one that I've been using for years across various GTK components.
Re: Faster CRDTs: An Adventure in Optimization
#84Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
Have you seen my Xi CRDT writeup from 2017 before? https://xi-editor.io/docs/crdt-details.html It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we p…
Out of curiosity, what do you use to make those diagrams?
Re: Faster CRDTs: An Adventure in Optimization
#85Reminds me of the data structures in this markdown library https://github.com/markdown-it/markdown-it/blob/master/docs/...
The author hand waves away the possibility that there could be memory locality performance benefits by using arrays in JS but my hunch is that there is something in that. I know the react code base for example went for a monomorphic Object structure to represent components to leverage inline caching of hidden classes.
Re: Faster CRDTs: An Adventure in Optimization
#86Damn! What a fantastic read ! And of course brilliant coding/thinking :)
Well done sir !
Re: Faster CRDTs: An Adventure in Optimization
#87Earlier quoted context omitted.
Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT. CRDTs certainly do have a mathematical elegance to them.
Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CR…
> And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document.
Operations in a CRDT must be commutative for merge/update to be well-defined, so it's not immediately clear how a "rename" operation can be expected to work properly.
Re: Faster CRDTs: An Adventure in Optimization
#88Earlier quoted context omitted.
Have you seen my Xi CRDT writeup from 2017 before? https://xi-editor.io/docs/crdt-details.html It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we p…
Out of curiosity, what do you use to make those diagrams?
https://www.figma.com/ and putting a lot of effort into them
Re: Faster CRDTs: An Adventure in Optimization
#89> my range tree is just a slightly modified b-tree. But usually when people talk about b-trees they mean a BTreeMap. Thats not what I'm doing here. Instead of storing keys, each internal node of the b-tree stores the total number of characters (recursively) in that item's children. So we can look up any item in the document by character position, or insert or delete anywhere in the document in log(n) time.
Cool! This is essentially the same idea I implemented in 2012; I call it the AList or A-List data structure: http://core.loyc.net/collections/alists-part1
Ever since I made it, I've been looking for a good application for it. I guess this is it! I mean, I knew A-List was a good data structure for text editing, but most applications can use a Gap Buffer which is much simpler. But when it comes to concurrent editing, you've got multiple editing points so a Gap Buffer is suddenly much less attractive.
> Honestly I'm shocked and a little suspicious of how little ram Yjs uses in this test.
It's good, but still it uses ~30x as much RAM as plain string edits. Not surprisingly, you got 3x better memory usage by using A-List and a more efficient language (Rust in this case, but C# and C/C++ can also do well.)
There is a great article about a CRDT concept called "Causal Trees[1]. I wonder how it compares to flat-list-based CRDTs (it's been too long since I researched this).
By the way, Microsoft has a new set of libraries for concurrent editing called Fluid Framework[2]. I'm told it's a "generalized data structure" that was inspired by Causal Trees but with a unique and intention-preserving editing scheme. I found out about it after they decided to use my fast-cloning-copy-on-write B+Tree for TypeScript[3]... they sent me a pull request for diffing versions of B+ trees, but I haven't yet looked into the architecture of their concurrent data type.
[1] http://archagon.net/blog/2018/03/24/data-laced-with-history/
Re: Faster CRDTs: An Adventure in Optimization
#90On a meta-level, does anyone else think that the whole idea of writing a peer reviewed paper that is just a benchmark of different algorithms should be really rigorously reviewed before being accepted? Writing good benchmarks is hard, and so highly contextual that writing fair comparisons beteen algorithms (or data structures) is almost impossible unless you're an expert in all of the algorithms involved.
Yeah, I've also seen several academic papers on performance or "optimization" of existing algorithms which just demonstrate a complete lack of knowledge about how those algorithms are implemented in practice. For example, there was a paper explaining how you could optimize the GJK algorithm by reducing the number of distance checks required, and in turn the number of square-roots... Despite the fact that everyone (in…
> Despite the fact that everyone (including the authors of the original GJK algorithm) knows that you don't actually need to do a square-root to compare distances..
Academia's purpose is to produce research, typically measured in publications per unit time. Optimizing one paper leads to a global reduction in the size of the literature by pruning opportunities for subsequent research, harming the overall performance of the system.