What I like about "tests" in software development is that anyone can run them, just download the source code, then run ./test or right click and "run tests". It would be cool if computer science could offer the same experience, just download the source code and run it, compare if you got the same result, inspect and learn from the source code, etc. Instead of "here's some pseudo-code we've never tried", and here's a mathematical formula that you need to be a mathematics professor to understand... Yes we know you are not a professional software developer, the code is going to be at a beginners level, but that is fine, I am not reading your paper to criticize your code for being "impure", or not using the latest syntax and frameworks, I'm reading it to understand how to implement something, to solve a problem.
Faster CRDTs: An Adventure in Optimization
21–30 of 154 posts
Re: Faster CRDTs: An Adventure in Optimization
#22Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
[deleted]
Re: Faster CRDTs: An Adventure in Optimization
#23Earlier quoted context omitted.
Article mentions at the beginning that the author used CRDT in Google Wave/ShareJS.
AFAIK Wave and ShareJS both used OT (which the paper that this article referred to was also attempting to benchmark). FWIW, I am myself also curious about this (the question of comparing CRDT to non-CRDT solutions): I found OT beautiful, but never really felt CRDT had the same feeling of elegance; and so I am downright fascinated to see the person I have always seen as a "god of OT" deciding to forsake it and move to…
Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT.
CRDTs certainly do have a mathematical elegance to them.
Re: Faster CRDTs: An Adventure in Optimization
#24On 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…
From what I saw (I worked in an academia-consulting partnership to solve scheduling problems in transports), the OR researchers very frequently work in association with OR consulting shops, and they're well-aware of the difference between academic datasets and industrial datasets. In the conferences I saw, it was not infrequent to see different tracks for industrial and academic papers, both attended by the same crowd.
The point I agree with, though, is that this is not reflected in the papers. Academic papers focus on academic instances because they are more general (and usually harder, as you said) and because optimizations of specific instances of the problem are not that useful from an academic pov.
It's hard to know who works with who and who has experience with what if you're not an insider, though.
Re: Faster CRDTs: An Adventure in Optimization
#25Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
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 children of (seph, 0) the only possibilities are, either ending up with "aXbc" or "abXc" right? Or is there a legitimate possibility of ending up with "abcX" ?
I'm assuming we'll apply a common sorting logic only to clashing siblings.
Re: Faster CRDTs: An Adventure in Optimization
#26Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
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 have a blog, or any recommendations for stuff to read by you or others?
Re: Faster CRDTs: An Adventure in Optimization
#27Hello 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 'hel', another editor might be able to interject with 'd' to finish the word in another way.
In my view, these data structures are only "the same information" if you provide for a reasonably-sized, fixed quantum of synchronization. The merging makes sense if e.g. you batch changes every one or two seconds. It makes less sense if you would otherwise stream changes to the coordinating agent as they happen, even with latency.
Re: Faster CRDTs: An Adventure in Optimization
#28Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
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 only valid orderings are, as I said, "aXbc" or "abcX". But without knowing how "b" and "X" should be ordered, its ambiguous which one to use.
Let me know if thats still confusing! This stuff is hard to explain without a whiteboard.
Re: Faster CRDTs: An Adventure in Optimization
#29Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
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.
Re: Faster CRDTs: An Adventure in Optimization
#30On 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.
Yeah, I've also seen several academic papers on performance or "optimization" of existing algorithms which just demonstrate a complete lack of knowledge about how those algorithms are implemented in practice.
For example, there was a paper explaining how you could optimize the GJK algorithm by reducing the number of distance checks required, and in turn the number of square-roots... Despite the fact that everyone (including the authors of the original GJK algorithm) knows that you don't actually need to do a square-root to compare distances...