3 ms·

Big congratulations to the Automerge folks for shipping this after years of work. At this point both Yjs and Automerge have Rust libraries and (soon?) bindings

by jitl 4y ago

Big congratulations to the Automerge folks for shipping this after years of work. At this point both Yjs and Automerge have Rust libraries and (soon?) bindings for more languages than just JS that stay in sync. Yjs (pure javascript?) is quoted on the paper benchmark at 1,074ms and 10,141,696 bytes of memory, compared to Automerge 2.0.2-unstable at 661ms and 22,953,984 bytes of memory. It looks like Automerge 2 latest is faster than Yjs, but still uses 2x more memory. I wonder if this is comparing usage from JS via bindings, or directly comparing two different rust implementations, or comparing Automerge 2.0.2-unstable via Rust to Yjs via NodeJS. I am still not sure which set of tools I would recommend; I believe Yjs is more actively deployed in production since the Automerge implementation was so far behind performance wise until now. However one of the Peritext authors (https://twitter.com/sliminality https://twitter.com/sliminality who is on my team at Notion) tells me that Automerge is better at text because it doesn't suffer from interleaved characters like Yjs does. So consider it instead of Yjs!

josephg 4y ago
I’ve spent a lot of time benchmarking both libraries and talking to the authors. The main difference is that yjs has an extra optimization that’s still missing from automerge: Yjs does internal run-length encoding of adjacent inserted items. And adjacent inserts come up a lot in real text editing traces. Adding this optimization to diamond types, in pure rust, improved performance by another order of magnitude (25ms for the same test with this tweak). It also dropped memory usage to about 2MB. The automerge engineers know about this trick (I’ve talked to them about it). So I assume it’s in the pipeline somewhere. And yjs is working on a rust reimplementation, which should bring its performance in line too.
- satvikpendem 4y ago
  diamond-types (for reference for others [0]) still only supports plain text, is that right? I was thinking of using it for more general use cases such as an offline habit tracker, which isn't text of course, but I was interested to hear more on the progress towards other data types such as generic JSON data. Currently for this use case I've been using autosurgeon [1] so far which has a nice Rust API for structs, even if it might be slower than yjs (or yrs, its Rust implementation) or diamond-types. [0] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types [1] https://github.com/automerge/autosurgeon https://github.com/automerge/autosurgeon
  - josephg 4y ago
    Yep; sadly still true. I started some work last year to simultaneously add support for arbitrary JSON data and add a database-like storage layer to allow us to safely stream changes to disk. (Automerge and yjs usually require the entire data set to be re-saved in its entirety when updates happen). Its taken longer than I thought, because I've gone through a bunch of different designs for both pieces. We'll get there; everything just takes longer than you want when you do it for the first time. I'll look at autosurgeon. Having similar APIs is good for everyone.
- memorythought 4y ago
  This optimization is indeed in the pipeline, although there are other things nearer the front because performance is currently Good Enough ™ that other things are more pressing (other things being e.g. completing the Peritext implementation, improving the sync protocol).
meitros 4y ago
Was also curious how the comparisons were being done. Isn’t there a new non-negligible overhead of converting and passing data structures between js and rust?
- josephg 4y ago
  I've gotten similar performance from yjs (about 1 second from this test). To do it, I ran the benchmark itself in nodejs / V8. When I benchmarked in rust, the same data set was loaded from JSON and benchmarked using pure rust code. Its not a fair test if you'll be running this code in a browser, since the rust code will need to be compiled to wasm (and suffer a ~3x performance penalty), while the javascript code will run at the same speed. But whether that matters to you depends on what you're doing.
  - lll-o-lll 4y ago
    Wow, 3x perf penalty? I thought wasm was supposed to get us to “near native speeds”. Is this typical of the penalty paid, or something specific to automerge?
    - josephg 4y ago
      Yep. At least, thats the slowdown rate I saw porting my own (very optimized) CRDT to wasm last year. I haven't measured automerge's wasm build but 3x slower is a reasonable baseline for wasm's performance compared to x86_64 code. Some of that difference is a lack of auto-vectorization in wasm. Wasm SIMD is pretty new, and not well supported in wasm runtimes yet as far as I know.
  - kevincox 4y ago
    3x semms unusually high. It definitely depends what you are doing but I recently compared a Ricochet Robots solver that I wrote (A* search) and it took only about 110% of native time. When I benchmarked it a couple of years ago it took about 2x so things have definitely improved a lot. I'm sure the use case matters a lot. But at least in come cases the result can be very close to native.

by jitl 4y ago

josephg 4y ago

I’ve spent a lot of time benchmarking both libraries and talking to the authors. The main difference is that yjs has an extra optimization that’s still missing from automerge: Yjs does internal run-length encoding of adjacent inserted items. And adjacent inserts come up a lot in real text editing traces. Adding this optimization to diamond types, in pure rust, improved performance by another order of magnitude (25ms for the same test with this tweak). It also dropped memory usage to about 2MB. The automerge engineers know about this trick (I’ve talked to them about it). So I assume it’s in the pipeline somewhere. And yjs is working on a rust reimplementation, which should bring its performance in line too.

satvikpendem 4y ago
diamond-types (for reference for others [0]) still only supports plain text, is that right? I was thinking of using it for more general use cases such as an offline habit tracker, which isn't text of course, but I was interested to hear more on the progress towards other data types such as generic JSON data. Currently for this use case I've been using autosurgeon [1] so far which has a nice Rust API for structs, even if it might be slower than yjs (or yrs, its Rust implementation) or diamond-types. [0] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types [1] https://github.com/automerge/autosurgeon https://github.com/automerge/autosurgeon
- josephg 4y ago
  Yep; sadly still true. I started some work last year to simultaneously add support for arbitrary JSON data and add a database-like storage layer to allow us to safely stream changes to disk. (Automerge and yjs usually require the entire data set to be re-saved in its entirety when updates happen). Its taken longer than I thought, because I've gone through a bunch of different designs for both pieces. We'll get there; everything just takes longer than you want when you do it for the first time. I'll look at autosurgeon. Having similar APIs is good for everyone.
memorythought 4y ago
This optimization is indeed in the pipeline, although there are other things nearer the front because performance is currently Good Enough ™ that other things are more pressing (other things being e.g. completing the Peritext implementation, improving the sync protocol).

meitros 4y ago

Was also curious how the comparisons were being done. Isn’t there a new non-negligible overhead of converting and passing data structures between js and rust?

josephg 4y ago
I've gotten similar performance from yjs (about 1 second from this test). To do it, I ran the benchmark itself in nodejs / V8. When I benchmarked in rust, the same data set was loaded from JSON and benchmarked using pure rust code. Its not a fair test if you'll be running this code in a browser, since the rust code will need to be compiled to wasm (and suffer a ~3x performance penalty), while the javascript code will run at the same speed. But whether that matters to you depends on what you're doing.
- lll-o-lll 4y ago
  Wow, 3x perf penalty? I thought wasm was supposed to get us to “near native speeds”. Is this typical of the penalty paid, or something specific to automerge?
  - josephg 4y ago
    Yep. At least, thats the slowdown rate I saw porting my own (very optimized) CRDT to wasm last year. I haven't measured automerge's wasm build but 3x slower is a reasonable baseline for wasm's performance compared to x86_64 code. Some of that difference is a lack of auto-vectorization in wasm. Wasm SIMD is pretty new, and not well supported in wasm runtimes yet as far as I know.
- kevincox 4y ago
  3x semms unusually high. It definitely depends what you are doing but I recently compared a Ricochet Robots solver that I wrote (A* search) and it took only about 110% of native time. When I benchmarked it a couple of years ago it took about 2x so things have definitely improved a lot. I'm sure the use case matters a lot. But at least in come cases the result can be very close to native.