js-delta-crdts
js-delta-crdts copied to clipboard
peer-base
RGA implementation
Hi!
I checked the RGA implementation out and I think we should discuss the technique.
https://github.com/ipfs-shipyard/js-delta-crdts/blob/master/src/rga.js#L15
Here, you use js objects and containers for the RGA tree structure. That leads to very non-trivial overheads because of js object headers, allocation and js garbage collection. That is completely unnecessary. I know a guy who implemented a collaborative editor like that. At least in 2015, it couldn't handle more than half a page of text because of js overheads.
I think, I myself implemented it like that in 2008, but I was using C hash tables, which are fundamentally arrays. If I recall correctly, the 2011 RGA paper (Goh et al) also implied C hash tables.
My 2010 Causal Trees paper used a different technique already: the metadata was kept in an inert buffer. The clean data was kept as a normal string.
I have no idea why everyone keeps citing Goh et al. Algebraically, CT and RGA is the same thing. Maybe I am bad at explaining. You may check out the Replicated Object Notation at http://github.com/gritzko/ron and its "RGA" implementation https://github.com/gritzko/ron/blob/master/rdt/rga.go (which is actually Causal Trees, but the word "tree" adds to confusion here).
There is no need to actually keep metadata and the CT/RGA tree structure as objects in memory. That's way too expensive. The thing may live in a compressed byte buffer, iterated as needed.
Cheers.
