search

peer-base / js-delta-crdts

Delta State-based CRDTs in Javascript
192 stars 16 forks source link

RGA implementation #5

Open gritzko opened 6 years ago

gritzko commented 6 years ago

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 commented 5 years ago

Somewhat related: #27

robchristian commented 4 years ago

Next steps, anyone?