dpiepgrass
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/