reference-crdts VS wit-bindgen

> The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client.

Argh not getting this stuff right is really frustrating. I've been working on collaborative editing for over a decade now, and I still can't implement any of these algorithms correctly without the help of a fuzz testing. But fuzz testing done right finds all of these problems! There's no excuse!

Fuzzers work so well here because all of these algorithms have a clear correctness criteria: After syncing, state should always converge to the same result. So its pretty easy to write code which does this in a loop:

1. Generates some random changes on some fake "peers"

2. Picks 2 peers at random and sync their changes, using your new fancy synchronization algorithm

3. Assert that the state has converged between the peers

I've been working on this stuff for over a decade. I've implemented dozens of these algorithms. And every single time I write a fuzzy boi to check my work I find convergence bugs. Playing whack-a-mole with a fuzzer is a rite of passage for implementing systems like this.

When your fuzzer runs all night, you should never have lingering convergence bugs like you're describing with Word.

As an example, here's a simple fuzzer for a reference list CRDT implementation: https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b4...

The code is so small it almost fits on my laptop screen.

> In this case, the bottleneck at 9 million LoC is not CPU cycles but memory usage. That's where I am considering pushing down into WebAssembly

How often does this come up in practice? I can't think of many files I've opened which were 9 million lines long. And you say "LoC" (lines of code). Are you doing syntax highlighting on 9 million lines of source code in javascript? Thats impressive!

> I guess my point is why do you need balanced trees? Is this a CRDT specific thing? Can you implement CRDT with just an array of lines / gap buffer?

Of course! Its just going to be slower. I made a simple reference implementation of Yjs, Automerge and Sync9's list types in javascript here[1]. This code is not optimized, and it takes 30 seconds to process an editing trace that diamond types (in native rust) takes 0.01 seconds to process. We could speed that up - yjs does the same thing in 1 second. But I don't think javascript will ever run as fast as optimized rust code.

The b-tree in diamond types is used for merging. If you're merging 2 branches, we need to map insert locations from the incoming branch into positions in the target (merged) branch. As items are inserted, the mapping changes dynamically. The benchmark I've been using for this is how long it takes to replay (and re-merge) all the changes in the most edited file in the nodejs git repository. That file has just shy of 1M single character insert / delete operations. If you're curious, the causal graph of changes looks like this[2].

Currently it takes 250ms to re-merge the entire causal graph. This is much slower than I'd like, but we can cache the merged positions in about 4kb on disk or something so we only need to do it once. I also want to replace the b-tree with a skip list. I think that'll make the code faster and smaller.

A gap buffer in javascript might work ok... if you're keen, I'd love to see that benchmark. The code to port is here: [3]

> Undo support -> In which case, you only have to stack / remember the set of commands and not have to store the state on every change. I'm not sure if this overlaps with the data structure choice, other than implementation details.

Yeah, I basically never store a snapshot of the state. Not on every change. Not really at all. Everything involves sending around patches. But you can't just roll back the changes when you undo.

Eg: I type "aaa" at position 0 (the start of the document). You type "bbb" at the start of the document. The document is now "bbbaaa". I hit undo. What should happen? Surely, we delete the "aaa" - now at position 3.

Translating from position 0 to position 3 is essentially the same algorithm we need to run in order to merge.

> I was just looking into TypedArrays.

I tried optimizing a physics library a few years ago by putting everything in typedarrays and it was weirdly slower than using raw javascript arrays. I have no idea why - but maybe thats fixed now.

TypedArrays are useful, but they're no panacea. You could probably write a custom b-tree on top of a typedarray in javascript if you really want to - assuming your data also fits into typedarrays. But at that point you may as well just use wasm. It'll be way faster and more ergonomic.

[1] https://github.com/josephg/reference-crdts

[2] https://home.seph.codes/public/node_graph.svg

[3] https://github.com/josephg/diamond-types/tree/master/src/lis...

The component model is already shipping in Wasmtime, and will be stable for use in Node.js and in browsers via jco (https://github.com/bytecodealliance/jco) soon. WASI Preview 2 will be done in December or January, giving component model users a stable set of interfaces to use for scheduling, streams, and higher level functionality like stdio, filesystem, sockets, and http on an opt-in basis. You should look at wit-bindgen (https://github.com/bytecodealliance/wit-bindgen) to see some of the languages currently supported, and more that will be mature enough to use very soon (https://github.com/bytecodealliance/componentize-py)

Right now jco will automatically generate the JS glue code which implements a Component Model runtime on top of the JS engine's existing WebAssembly implementation. So, yes, Components are a composition of Wasm Modules and JS code is handling passing values from one module/instance to another. You still get the performance benefits of running computation in Wasm.

One day further down the standardization road, we would like to see Web engines ship a native implementation of the Component Model, which might be able to make certain optimizations that the JS implementation cannot. Until then you can consider jco a polyfill for a native implementation, and it still gives you the power to compose isolated programs written in many languages and run them in many different contexts, including the Web.

(Disclosure: I am co-chair of WASI, Wasmtime maintainer, implemented many parts of WASI/CM)

Thank you!

To your point, the primary consideration for choosing the languages is their support for WebAssembly, and WASI in particular.

Due to Spin's heavy use of WASI and the component model, languages that have first party support in the WIT bindings generator (https://github.com/bytecodealliance/wit-bindgen) are the easiest to implement, followed by languages that can be built on top of the support for those with first party support.

For example, the JavaScript support is built by embedding QuickJS (in particular, Shopify's Javy project — https://github.com/fermyon/spin-js-sdk), which then uses the Rust SDK.

There are many options, but what worked best for me is compiling with cargo-wasi and loading the resulting Wasm file with browser_wasi_shim. Using wasm32-wasi instead of wasm32-unknown-unknown requires a bit more work (the communication with JS has to be set up manually), but gives the flexibility of having just a Wasm file that can be dropped in and loaded dynamically. (There's wit-bindgen for generating wrapping code according to an interface definition but I didn't have much success with it.)

I've been playing with creating a go version of the abi for use with wit-bindgen because the current one uses cgo https://github.com/bytecodealliance/wit-bindgen

wit-bindgen - Language Binding Generator for WASM Interface Type

wit-bindgen-rust = { git = "https://github.com/bytecodealliance/wit-bindgen.git", rev = "60e3c5b41e616fee239304d92128e117dd9be0a7" }

Yep, you're right. For this, there are a few options. The ones most relevant to you are fp-bindgen, which targets Wasmer, and wit-bindgen, which targets wasmtime.

Are you evaluating if WebAssembly Component Model, its WIT format and related tooling like wit-bindgen could be a good fit for your multiple languages support?

[package] name = "sentiment" version = "0.1.0" edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] wit-bindgen-rust = { git = "https://github.com/bytecodealliance/wit-bindgen.git", rev = "60e3c5b41e616fee239304d92128e117dd9be0a7" } vader_sentiment = { git = "https://github.com/ckw017/vader-sentiment-rust" } lazy_static = "1.4.0" [lib] crate-type = ["cdylib"]