121–130 of 154 posts
Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
This was a great read, thank you. I wish there were more explanations of the "black magic" part of Yjs. I'll have to dig into that.
I recently discarded a serious chunk of time and effort using Logux.io to move to YJS and so far it has been a very good move. This for major evolution of a Knowledge Base/Notes app I'm developing, Clibu Notes.
I was very pleased to read your very positive comments on YJS. Kevin Jahns continues to do great work with YJS.
Great to see this work from a follow Australian.
Earlier quoted context omitted.
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…
> Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and demonstrated its superiority (K. Helsgaun). Does this mean that the Linkern program in the Concorde TSP suite is also implemented incorrectly?
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.
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...
Trees seemed to work pretty well for me here! The problem with trees is usually that people don't pack enough data into each node in the tree. I implemented a skip list in C a few years ago[1]. For a lark I benchmarked its performance against the C++ SGI rope class which was shipped in the C++ header directory somewhere. My skip list was 20x faster - which was suspicious. I looked into what the SGI rope does and it t…
Brian Cantrill also noticed that in his comparison of his C and Rust versions of statemap[0]: Rust had a way, way better cache behaviour than C (96.9 L1 hit rate to 77.9%, and half the L2 misses although the better L1 behaviour also led to >90% less L2 interactions in the first place), and most of that was attributed to using a btreeset instead of an AVL BST.
[0] http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...
Earlier quoted context omitted.
Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least. The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2]. [1]: http://doc.replicated.cc/%5EWiki/ron.sm [2]: https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599...
Thanks! I googled only 1 impl in Rust: https://github.com/dkellner/chronofold which seems to produce invalid results on some inputs. Actually the hard part (integration) is made of hacks there... That PoC Wiki sounds really interesting and the whole replicated.cc project! Any plans on releasing it?
Excellent article! As someone who has to work with collaborative editing I must say the complexity of the whole area is at times daunting to say the least. So many edge-cases. So many mines to step on. Now I think I am convinced that the OT vs CRDT performance comparison is kind of moot point and the question is more about the user experience. Which version produces nicer results when two very diverged documents are…
> Which version produces nicer results when two very diverged documents are merged. From the user’s perspective merging behaviour is basically identical in all of these systems. Diamond supports full per character change tracking. So you know who authored what. I think Yjs does this too. I’m not sure what you mean about materialising areas differently? I’d like to have full branch support in diamond at some point too…
Ah, ok. Neat.
I’m not sure what you mean about materialising areas differently?
I meant finding the ranges of the document that have been changed relative to snapshot x and showing them based on the user id who changed them. If that can be done in real-time as the changes come in that would be really impressive.
Earlier quoted context omitted.
Hi josephg, I'm a CRDT researcher. This is great to see so much work around CRDT nowadays! Some optimizations whom you discuss are already proposed by some papers and implementations. For instance, LogootSplit [1] proposes an implementation based on an AVL tree with extra metadatas to get a range tree. LogootSplit proposes also a block-wise approach that stores strings instead of individual characters. Xray [2], an e…
Cool! It'd be interesting to see those CRDT implementations added to Kevin Jahns' CRDT Benchmarks page[1]. The LogootSplit paper looks interesting. It looks like xray is abandoned, and I'm not sure about teletype. Though teletype's CRDT looks to be entirely implemented in javascript[2]? If the authors are around I'd love to see some benchmarks so we can compare approaches and learn what actually works well. And I'm n…
I understand your point and as a researcher and engineer I know your feeling. I took some cautions by using "Some optimizations". I value engineering as much as research and I'm bothered when I heard any side telling the other side that their work is worthless. Your work and the work of Kevin Jahns are very valuable and could improve the way that researchers and engineers do benchmarks.
This is still hard for me to determine when position-based list CRDT (Logoot, LogootSPlit, ...) are better than tombstone-based list CRDT (RGA, RgaSplit, Yata, ...). It could be worth to assess that.
3 year ago I started an update of LogootSplit. The new CRDT is named Dotted LogootSplit [1] and enables delta-synchronizations. The work is not finished: I had other priorities such as writing my thesis... I have to perform some benchmark. However I'm more interested in the hypothetical advantages of Dotted LogootSplit regarding synchronization over unreliable networks. From an engineering point-of-view, I'm using a partially-persistent-capable AVL tree [2]. Eventually I would like to switch to a partially-persistent-capable b-tree. Unfortunately writing a paper is very time consuming, and time is missing.
I still stick with JS/TS because in my viewpoint Wasm is not mature yet. Ideally, I would like to use a language that compiles both to JS and Wasm. Several years ago I welcomed Rust with a lot of enthusiasm. Now I'm doubtful about Rust due to the inherent complexity of the language.
[1] https://github.com/coast-team/dotted-logootsplit/tree/dev [2] https://github.com/Conaclos/cow-list
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…
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. 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…