reference-crdts VS component-model

> 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...

I don't think that's a very good goal. Jettisoning the DOM means jettisoning accessibility and being able to leverage everything that the browser gives you out-of-the-box. You have to render to a canvas and build everything from scratch. I think Wasm is great for supplementing a JS app, not replacing it (e.g. using a Wasm module to do some calculations in a Worker). I like to use the right tool for the job, and trying to use something other than JS to build a web app just seems a little janky to me.

At one point, there was a Host Bindings proposal that would enable you to do DOM manipulation (it looks like it was archived and moved to the Component Model spec [1]). That would probably be the ideal way to avoid as much JS as possible. However, browser vendors have been heavily optimizing their JS runtimes, and in some cases, Wasm may actually be slower than JS.

I've been following Wasm's progress for several years, which has been slow, but steady. Ironically, I think the web is actually the worst place to use it. There's so much cool non-web stuff being done with it and I'm more interested to see where that goes.

[1] https://github.com/WebAssembly/component-model?tab=readme-ov...

Well the great thing about WebAssembly is that you can port QT or anything else to be at a layer below -- thanks to WebAssembly Interface Types[0] and the Component Model specification that works underneath that.

To over-simplify, the Component Model manages language interop, and WIT constrains the boundaries with interfaces.

IMO the problem here is defining a 90% solution for most window, tab, button, etc management, then building embeddings in QT, Flutter/Skia, and other lower level engines. Getting a good cross-platform way of doing data passing, triggering re-renders, serializing window state is probably the meat of the interesting work.

On top of that, you really need great UX. This is normally where projects fall short -- why should I use this solution instead of something like Tauri[2] which is excellent or Electron?

[0]: https://github.com/WebAssembly/component-model/blob/main/des...

[1]: https://github.com/WebAssembly/component-model/blob/main/des...

[2]: https://tauri.app/

While I don't necessarily agree with the unnecessary, unsupported casual, & cheap contempt culture here ("unshackle the web from the mess that is JavaScript", "places that don't really need these problems to be solved")...

WebAssembly component-model is being developed to allow referring to and passing complex objects between different modules and the outside world, by establishing WebAssembly Interface Types (WIT). It's basically a ABI layer for wasm. This is a pre-requisite for host-object bridging, bringing in things like DOM elements.

Long running effort, but it's hard work and there's just not that many hands available for this deep work. Some assorted links with more: https://github.com/WebAssembly/component-model https://www.fermyon.com/blog/webassembly-component-model https://thenewstack.io/can-webassembly-get-its-act-together-...

It's just hard work, it's happening. And I think the advantages Andy talks to here illuminate very real reasons why this tech can be useful broadly. The ability to have plugins to a system that can be safely sandboxed is a huge win. That it's in any language allows much wider ecosystem of interests to participate, versus everyone interested in extending your work also having to be a java or c++ or rust developer.

A. Sure, but it isn't sufficiently beneficial for the cost.

B. WebAssembly is immature for developing a plugin system because of the lack of a sufficient ABI: https://github.com/WebAssembly/component-model

C. There aren't any other languages that meet the criteria. Lua was a no-go from the start. The maintainers did not like the language, and it necessitated adding more C code to Helix which could complicate building even further. https://github.com/helix-editor/helix/discussions/3806#discu...

AFAIK GC is irrelevant for "direct DOM access", you would rather want to hop into the following rabbit hole:

- reference types: https://github.com/WebAssembly/reference-types/blob/master/p...

- interface types (inactive): https://github.com/WebAssembly/interface-types/blob/main/pro...

- component model: https://github.com/WebAssembly/component-model

If this looks like a mess, that's because it is. Compared to that, the current solution to go through a Javascript shim doesn't look too bad IMHO.

The wasm idl (called WIT) is actively being worked on here: https://github.com/WebAssembly/component-model/blob/main/des...

Being able to access DOM is definitely an objective. It's just taking a lot longer than folks guessed to build a modular wasm ABI.

The WASM Component Model

https://github.com/WebAssembly/component-model

Take a look at the python abi to see what the structure looks like for calling into components https://github.com/WebAssembly/component-model/tree/main/design/mvp/canonical-abi