Faster CRDTs: An Adventure in Optimization • Hacker News Board

Re: Faster CRDTs: An Adventure in Optimization

#31

Post by makmanalp » Sat, Jul 31, 2021, 1:34 PM UTC

knuthsat wrote: post #14

vanderZwan wrote: post #7

On a meta-level, does anyone else think that the whole idea of writing a peer reviewed paper that is just a benchmark of different algorithms should be really rigorously reviewed before being accepted? Writing good benchmarks is hard, and so highly contextual that writing fair comparisons beteen algorithms (or data structures) is almost impossible unless you're an expert in all of the algorithms involved.

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 surprise, on only that. If theoretical improvements is not what you want, don't read those papers, read ones what people more focused on applications. Read literally any databases paper, or stuff like hyperscan, simdjson. I'd argue that a non-trivial amount of these are vastly /ahead/ of what's standard in industry, but industry is slow to adapt new ideas and catch up because of legacy software and existing codebases. Very similar stuff in the programming languages sphere, it took ages for industry to adapt ideas that were popular in academia for a long time (eg: Rust, LINQ). The idea that academia (at least in CS) is an ivory tower, far from the concerns of industry, is not very true as of recent. There's a lot of cross pollination and a revolving door of people going back and forth from one to the other spreading ideas.

Re: Faster CRDTs: An Adventure in Optimization

#32

Post by goldenkey » Sat, Jul 31, 2021, 1:38 PM UTC

Majromax wrote: post #27

josephg wrote: post #2

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

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…

The chunking should depend entirely on the network synchronization. If synchronization is editing-debounced, then chunking could be applied rather safely.

Re: Faster CRDTs: An Adventure in Optimization

#33

Post by thechao » Sat, Jul 31, 2021, 1:38 PM UTC

josephg wrote: post #26

thechao wrote: post #18

Earlier quoted context omitted.

I love high level systems languages like C/++ and Rust… but everything you said about JavaScript being slow is the same thing assembly programmers experience when optimizing high level systems languages. In general, when I see C code and I’m asked to speed it up, I always use “100x” as my target baseline.

Whoa thats a really impressive baseline to reach for when optimizing C code! I'd love to hear some war stories. As you can probably tell from my article, most of my skill at this stuff is from hard won tricks I've picked up over the years - like reducing heap allocations and packing memory for cache coherency. There's probably lots of things I just haven't learned because I haven't discovered it on my own. Do you hav…

I learned low level programming while at Intel, working with one of their performance teams; so, nothing written. In general, though, assembly is more expressive than higher level languages; it lets you “tighten up” the code the computer executes, reducing work & bandwidth.

Specifically, a guy named Mike Abrash taught me some of this stuff, and he’s got some books explaining the theory in terms of practice.

Re: Faster CRDTs: An Adventure in Optimization

#34

Post by stephc_int13 » Sat, Jul 31, 2021, 1:42 PM UTC

Trees are a powerful and practical data structure, but even if it does not appear clearly when doing O(n) style complexity analysis, they are usually slow.

Unfortunately, the difference between slow and fast can be several orders of magnitude, while the perception of the programmer doing a back of the envelope analysis seems to be a logarithmic scaling of the reality...

Re: Faster CRDTs: An Adventure in Optimization

#35

Post by gritzko » Sat, Jul 31, 2021, 1:52 PM UTC

About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code. It used many of the tricks as described in the text, even the optimization where you remember the last insertion point. So I am terribly glad it all gets rediscovered.

The code is on GitHub [1] There is also an article which might be a tough reading, so no link. Recently I greatly improved CTs by introducing the Chronofold data structure [2]. Regarding that benchmark article, I spent many years in academia, so the quality of content problem is familiar to me. In other words, I don't take such articles seriously. CRDTs are fast enough, that is not a concern.

[1]: https://github.com/gritzko/citrea-model

[2]: https://arxiv.org/abs/2002.09511

Re: Faster CRDTs: An Adventure in Optimization

#36

Post by josephg » Sat, Jul 31, 2021, 1:55 PM UTC

Majromax wrote: post #27

josephg wrote: post #2

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

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 run of characters. Pausing doesn't help. Even the same user could later type something in the middle of a word they'd typed previously.

This limits what we can run-length encode. The code in diamond only run-length encodes items when they are:

- Typed sequentially in time

- And sequentially in insert location (position 10, 11, 12, 13, ...)

- And either all of the characters have been deleted or none of them have been deleted

Notice the other fields in that example in the post. Each subsequent character has:

- An id field = the previous id + 1

- A parent field = the id of the previous item

- The same value for isDeleted

If any of this stuff didn't match, the run would be split up.

Instead of storing those fields individually, we can store the id and parent of the first item, an isDeleted flag and a length field. Thats all the information we actually need to store. With yjs style entries (which is what diamond-types actually implements), the code is here if you can make heads or tails of it. The poorly named "truncate" method splits an item in two. Spans are only extended if can_append() returns true: https://github.com/josephg/diamond-types/blob/c4d24499b70a23...

With real data from Martin's editing trace, 182 000 inserted characters get compacted down to 12 500 list items. Which is still pretty good - thats 14x fewer entries. And it means performance doesn't stutter when large paste events happen.

Re: Faster CRDTs: An Adventure in Optimization

#37

Post by lewisjoe » Sat, Jul 31, 2021, 1:57 PM UTC

josephg wrote: post #28

lewisjoe wrote: post #25

Earlier quoted context omitted.

Thank you for writing this piece Joseph. Just want to make sure if something's a possible typo or I'm getting it all wrong :) Quote: "But how do we figure out which character goes first? We could just sort using their agent IDs or something. But argh, if we do that the document could end up as abcX , even though Mike inserted X before the b. That would be really confusing." Since the conflict is only between the chil…

Good question. That part of the article could probably use another diagram to explain it. The resulting document is generated by doing a depth-first prefix traversal of the tree. The ambiguity comes because "b" and "X" are both direct children of "a". So its not clear how they should be ordered relative to each other. Because "c" is a child of "b" in this example, the "X" can't appear between the "c" and "b". The onl…

Clear enough Joseph. Thanks :)

Re: Faster CRDTs: An Adventure in Optimization

#38

Post by bouk » Sat, Jul 31, 2021, 1:58 PM UTC

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

Re: Faster CRDTs: An Adventure in Optimization

#39

Post by username91 » Sat, Jul 31, 2021, 2:02 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

It's a great article - really informative and enjoyable to read. Thanks for making it happen. :)

Re: Faster CRDTs: An Adventure in Optimization

#40

Post by knuthsat » Sat, Jul 31, 2021, 2:07 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…

I must say that when it comes to discrete optimization, the genetic/ant/simulated annealing/etc. stuff is more popular in academia than in industry (at least the industry that doesn't heavily include academics).

Works like Lin-Kernighan heuristic are extremely rare and a bunch of knowledge exists in industry only. Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and demonstrated its superiority (K. Helsgaun).

I mean, most of the code that gets released today, doesn't even handle time windows constraint in the best way possible (optimal updates, constant time feasibility evaluations etc.). I believe all open source vehicle routing libraries do not have any data-structure relevant optimizations for handling time windows, task precedence, dynamic workshift starts etc. All are fairly simple implementation tricks that just got lost under giant amounts of population based heuristics or mathematical linear programming approaches.