Faster CRDTs: An Adventure in Optimization • Hacker News Board

Re: Faster CRDTs: An Adventure in Optimization

#71

Post by trishume » Sat, Jul 31, 2021, 4:39 PM UTC

josephg wrote: post #2

Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia

Have you seen my Xi CRDT writeup from 2017 before? https://xi-editor.io/docs/crdt-details.html

It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we put off some of the speed optimizations you've done, like using a range tree instead of a Vec of ranges. I think it also uses a different style of algorithm without any parents.

We never finished the optimizing and polished it up, so it's awesome that there's now an optimized text CRDT in Rust people can use!

Re: Faster CRDTs: An Adventure in Optimization

#72

Post by vlovich123 » Sat, Jul 31, 2021, 4:44 PM UTC

bouk wrote: post #38

paulgb wrote: post #9

This is great! I'd like to quote a line here, because I think the answer is “someone on HN knows” and I'd like to hear the answer as well. > V8 is actually suspiciously fast at this part, so maybe v8 isn't using an array internally to implement Arrays? Who knows!

The V8 blog is a good starting point for learning how it works under the hood: https://v8.dev/blog/fast-properties

Hmm... I would have thought they implemented something similar to a std::deque so that you have ammortized O(1) insertions into the middle of a vector.

Re: Faster CRDTs: An Adventure in Optimization

#73

Post by hodgesrm » Sat, Jul 31, 2021, 5:09 PM UTC

makmanalp wrote: post #31

knuthsat wrote: post #14

Earlier quoted context omitted.

Problem is that academics are rarely experts at programming or have knowledge of computer architectures as much as someone in the industry. There are various tricks that are never taught at college, therefore academics have no idea some stuff even exists. Best example is discrete optimization research (traveling salesman, vehicle routing and its variants, schedule rostering etc.). Stuff you find in the papers there a…

> Problem is that academics are rarely experts at programming or have knowledge of computer architectures as much as someone in the industry. There are various tricks that are never taught at college, therefore academics have no idea some stuff even exists. I want to push back on this generalization a bit. The academics that are focused on pushing the mathematical boundaries of discrete optimization are focused, no s…

100x +1. The whole field of query optimization has been devoted to improvement of efficiency and speed of database systems for decades. [1] Academic results are studied quite closely in industry. Also, "academic" includes people like Mike Stonebraker and Andy Pavlo. They aren't exactly slouches regarding issues of performance.

More generally, major waves of performance innovation in the IT field have been driven by advances in storage, compression, vectorization, virtualization, etc. Academic results have led to entirely new products like Vertica (from C-Store [2]) or VMware (from the Disco system [3]).

[1] https://en.wikipedia.org/wiki/Query_optimization

[2] https://w6113.github.io/files/papers/cstore-vldb05.pdf

[3] http://www.cs.cmu.edu/~15712/papers/bugnion97.pdf

edit: clarity

Re: Faster CRDTs: An Adventure in Optimization

#74

Post by iampims » Sat, Jul 31, 2021, 5:10 PM UTC

This is a fantastic write-up. Worth a read even if you don’t care about CRDTs.

Re: Faster CRDTs: An Adventure in Optimization

#75

Post by hinkley » Sat, Jul 31, 2021, 5:20 PM UTC

I'm getting mixed messages on CRDTs. Are we at the point now where they are general enough that the human observer is not constantly confronted with 'surprises' from the behavior of the system?

Some of the talks by Kleppmann go straight into the weeds and make it hard to tell if he's just nerding out about finer points or lamenting unsolved problems, or even paradoxes.

Re: Faster CRDTs: An Adventure in Optimization

#76

Post by jg23 » Sat, Jul 31, 2021, 5:23 PM UTC

josephg wrote: post #36

Majromax wrote: post #27

Earlier quoted context omitted.

When you write: > Yjs does one more thing to improve performance. Humans usually type in runs of characters. So when we type "hello" in a document, instead of storing ['h','e','l','l,'o'], Yjs just stores: ['hello']. [...] This is the same information, just stored more compactly. Isn't this not just the same information when faced with multiple editors? In the first implementation, if I pause to think after typing 'h…

I didn't explain this well but the transformation is lossless. No data is lost from compressing like this. It has no impact on the concurrency protocol or network protocol; it just impacts how the data is stored locally. If we need to, we could split the run back out again into individual characters without losing information. And that does happen - we do that if something later gets inserted into the middle of the r…

I have a related question to this, if you’re storing [“hello”] as one chunk, what happens when you perform an edit to say adding an extra [“e”] after the [“e”]? In the unoptimised structure I know you can just add the new [“e”] as a child of the original [“e”]. So here would you then delete the chunk [“hello”] and split it into two halves like [“he”] and [“llo”]?

Re: Faster CRDTs: An Adventure in Optimization

#77

Post by kevinjahns » Sat, Jul 31, 2021, 5:32 PM UTC

lewisjoe wrote: post #47

I've been looking for a practical OT alternative for our online word processor ( https://zoho.com/writer ). We already use OT for syncing our realtime edits and exploring CRDTs targetting stronger consistency for tackling offline edits (which are typically huge & defragmented, since the edits are not syncing in realtime) So the baseline is that OT has a better model for holding state in terms of performance/memory, s…

I know that it is hard to comprehend why modern CRDT implementations are fast. But the data confirms that they work great. OT seems to be much simpler, but there are real advantages in using CRDTs. The performance problems have been solved through an efficient representation of the CRDT model.

The gist of the below [1] read is that it is impossible for a human to create a document that Yjs can't handle (even in the worst case scenario). But yes, it handles real-world scenarios particularily well.

The concept of "hidden classes" is super old. It has first been implemented in a fork of smalltalk and then became foundational concept of runtime engines for scripting languages. It is implemented in V8, python, ruby, spidermonkey, ..

Yjs does not assume a "real-world scenario" and it is not optimized for any specific runtime engine. It runs fast in any browser. The benchmarks confirm this. [2]

Yjs is being used in practice by several companies (eg Nimbus Notes with >3 million users) for quite some time now. I'm not aware of any performance problems.

[1]: https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi... [2]: https://github.com/dmonad/crdt-benchmarks

Re: Faster CRDTs: An Adventure in Optimization

#78

Post by pookeh » Sat, Jul 31, 2021, 6:10 PM UTC

josephg wrote: post #2

Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia

Wait it doesn't look like you used the performance branch of automerge (which is now merged into master). It is significantly faster.

https://github.com/automerge/automerge/pull/253

Re: Faster CRDTs: An Adventure in Optimization

#79

Post by JW_00000 » Sat, Jul 31, 2021, 6:19 PM UTC

josephg wrote: post #29

mirekrusin wrote: post #5

Earlier quoted context omitted.

It seeems that the issue of reproducibility in computer science where no gigantic/proprietary datasets are needed should not be a problem by simply publishing repository with the code. Are there any forces present that make it so rare in practice?

Credit where its due, the academics did publish the code they wrote on github. But I don't know if anyone - reviewers or readers - actually took the time to read it. Let alone understand why it throws doubt on the paper's conclusions.

Usually, (at least in my specific niche of the computer science field,) if the code is published it's only published after the paper has been reviewed. This is partly to preserve anonymity during the review process, and also because usually the code isn't seen as "part of the paper" (i.e. "the paper should stand on its own"). Although I agree that you could argue that for papers about benchmarks, the code should definitely be considered an essential part of the paper.

Re: Faster CRDTs: An Adventure in Optimization

#80

Post by Rusky » Sat, Jul 31, 2021, 6:19 PM UTC

__s wrote: post #43

feikname wrote: post #15

Correct me I'm mistaken The difference between diamond native and diamond WASM demonstrates how, even with WASM, native implementations beat browsers hard , and native implementations performance-wise are still very worth, specially for lower powered devices, and, perhaps, reducing battery usage (as consequence of less CPU use) in mobile devices.

Yes. Ultimately WASM is executing within a sandbox & involves being JIT compiled (read: not heavily optimized except for hot loops eventually). If native compilation is an option it makes sense to go that route WASM competes with asm.js not asm (or, arguably, jvm etc)

WASM JIT implementations tend to be quite a bit different from JavaScript JIT, so that's not really where the perf difference comes from.

First, WASM gets all the heavy AOT optimizations from the middle end of the compiler producing it. At runtime, WASM JIT doesn't start from program source, but from something that's already been through inlining, constant propagation, common subexpression elimination, loop optimizations, dead code elimination, etc. And WASM is already typed, so the JIT doesn't have to bother with inline caching, collecting type feedback, or supporting deoptimization.

Because of that, the only really beneficial work left to do is from the back end (i.e. arch-specific) part of the compiler- basically, register allocation and instruction selection. WASM JIT compilers don't bother trying to find hot loops or functions before optimizing. Instead, they do a fast "streaming" or "baseline" codegen pass for fast startup, and then eagerly run a smarter tier over the whole module and hot-swap it in as soon as possible. (See e.g. https://hacks.mozilla.org/2018/01/making-webassembly-even-fa...)

The perf difference vs native rather comes from the sandboxing itself- memory access is bounds checked, support for threads and SIMD is limited (for now), talking to the browser has some overhead from crossing the boundary into JavaScript (though this overhead will go down over time as WASM evolves), etc.