RGA implementation

[gritzko]

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.

[pgte]

Somewhat related: #27

[robchristian]

Next steps, anyone?