About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code.
It used many of the tricks as described in the text, even the optimization where you remember the last insertion point. So I am terribly glad it all gets rediscovered.
The code is on GitHub [1] There is also an article which might be a tough reading, so no link.
Recently I greatly improved CTs by introducing the Chronofold data structure [2].
Regarding that benchmark article, I spent many years in academia, so the quality of content problem is familiar to me. In other words, I don't take such articles seriously.
CRDTs are fast enough, that is not a concern.
I remember seeing that (regex CTs) and immediately thinking "wtf, why would anyone want to do that". Took me quite a while to understand that it's actually a pretty clever way to write fast state machines in browserland. So thank you for this work!
Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least.
The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2].
I googled only 1 impl in Rust: https://github.com/dkellner/chronofold which seems to produce invalid results on some inputs. Actually the hard part (integration) is made of hacks there...
That PoC Wiki sounds really interesting and the whole replicated.cc project! Any plans on releasing it?
May I ask which inputs produced invalid results for you and which parts you consider hacky? I'd very much like to improve the implementation, so a reply here or an issue on e.g. GitHub would be highly appreciated. Thanks!
Some time ago (~7-8months) I tried to implement a chronofold-based app myself in not so fancy language (c#). The data structure itself is very nicely described in the paper, but for merging strategy there are only references to other papers... So I tried to find it implemented in other langs, most of repos were bare bones, yours was the most complete, so I took it as a reference. I lifted the merging strategy verbatim from it, and it passed all the tests in repo plus some additional tests. But when faced a real user input strange things happened.
I will try to find exact cases and open an issue, but not today, unfortunately :(
Edit: AFAIR, I had problems with this func:
https://github.com/dkellner/chronofold/blob/16773193b2d21f81... and the problem manifested itself for concurrent deletes. Plus it has reversed order for consecutive deletes regarding to original paper. I have not succeeded with fixing it and just scratched the whole thing and used a simpler (yet not as performant) merging strategy...
Don't worry, your details already help a lot! I will look into it later this week.
The published version indeed has one bug regarding inserts referencing a deleted element. Maybe that is (part of) what you saw as well. I've fixed that locally already, but unfortunately only after I've made signifant other changes which are still to be refactored & published ;-). Probably time to just backport the fix and release it.
The code is on GitHub [1] There is also an article which might be a tough reading, so no link. Recently I greatly improved CTs by introducing the Chronofold data structure [2]. Regarding that benchmark article, I spent many years in academia, so the quality of content problem is familiar to me. In other words, I don't take such articles seriously. CRDTs are fast enough, that is not a concern.
[1]: https://github.com/gritzko/citrea-model
[2]: https://arxiv.org/abs/2002.09511