Live data from Hacker News

Why CRDT didn't work out as well for collaborative editing xi-editor

github.com

71–80 of 86 posts

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#71
post #64
post #51

Earlier quoted context omitted.

Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed…

> Instead of batch compiling artifacts to disk like its 1970 [...] I am delighted to see people discussing this. Batch orientation made sense in a very resource-constrained era. But at this point we have more RAM and CPU than we know what to do with. It seems so obvious to me that the correct solution is to prioritize developer experience and keep everything hot. My single biggest barrier to developing faster is the…

The perfect place to start would be support in LLVM backends, maybe they are already working on this.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#72
post #29

Maybe first build a capable editor, with plugins, etc (xi-editor is not that yet) and worry about "collaborative editing" later? And even for that, I think simply "taking turns" (where users share an editor session, can chat with each other, and can switch on sequentially who gets to actively edit) is enough for 99% of cases, and is not more difficult than mere single-person editing (since there are no conflicts).

Collaborative editing is not something you can just bolt on after the fact if you want it to actually work well. Things like building a robust server that can be exposed to the internet can certainly wait, but how you are you supposed to develop a plugin ecosystem when you haven't even settled on a conceptual model for how to store and manipulate text yet?

>Collaborative editing is not something you can just bolt on after the fact if you want it to actually work well.

Yes, but my comment also alludes to the opinion that "well working collaborative editing" is not a real problem people have, and a much easier (and easier to bolt on) use case, of consecutive (serialized with "locks") collaborative editing should cover most people's needs...

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#73
post #29

Maybe first build a capable editor, with plugins, etc (xi-editor is not that yet) and worry about "collaborative editing" later? And even for that, I think simply "taking turns" (where users share an editor session, can chat with each other, and can switch on sequentially who gets to actively edit) is enough for 99% of cases, and is not more difficult than mere single-person editing (since there are no conflicts).

Start by redoing everything that the mature alternatives do is an advice for creating neither successful not useful things. By all means, focus on creating a kick-ass collaborative editor, and add just the editing capabilities needed to make it good at collaborative editing.

>Start by redoing everything that the mature alternatives do is an advice for creating neither successful not useful things.

It's the best advice in order to see any update.

There are plenty of programs that do some unique things very well, but fail on doing "everything that the mature alternatives do", so they fail to ever get mainstream traction themselves.

People want a complete solution that ALSO does X unique thing, if they are to drop their existing editors. Not something that they'll have to use alongside them for that special case.

(Joel on Software has written some nice posts about this idea, and why "minimal" competitors, who don't do "everything that the mature alternatives do" frequently fail, though I can't find the link right now)

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#74

Earlier quoted context omitted.

Well (strokes grey beard), before we talk about offline support, we should consider that there are two kinds of "online editing." The first kind of "online editing" is where you make a request to a server, and nothing happens until the server acknowledges it and sends you an approval. That's synchronous. The second type of "online editing" is where you have an independent process in your browser or client, and it com…

Mosh has this idea that you can keep typing and sending asynchronously even though you need the ACKs to find out what really happened, then when you get them you just redraw accordingly. Humans won't type too fast for too long, so eventually there will be time to catch up and let the user see what actually happened. The key is to distinguish client-side speculative outcomes from actual outcomes. Imagine that the text…

You are describing classic branch-and-merge. “Here’s my branch that I created offline.”

“Sorry, there are merge conflicts, please resolve them before resubmitting,” or, “I resolved them without consulting you.”

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#75
post #51

Earlier quoted context omitted.

TL;DR CRDT is completely irrelevant to any of the highlighting/etc stuff Most highlighters are lexers. Advanced highlighters/folders are parsers. The lexing/parsing that is required for highlighting is easy to make incremental for all sane programming languages. for LL(star) grammars, adding incrementality is completely trivial (i sent patches to ANTLR4 to do this) for LR(k) grammars, it's more annoying but possible…

Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed…

I have done exactly this in the Markdown editor I developed: Stylo: https://www.textually.net if you're curious.

I used what I call "partial compilation" for each edit made in the Markdown editor that "re-compiles" only affected parts of the text. A function is responsible for computing the ranges to be recompiled based on the edits made in the text. In Stylo it was absolutely essential since CSS is used for syntax highlighting and a complete DOM is kept in memory for the complete Markdown text. The necessity to keep the complete DOM in memory could have been avoided without "following sibling" selectors handling but I really wanted "complete" CSS support. Since Markdown can be used for texts ranging from 1 word to 2000 pages, complete recompilation was unthinkable, so partial one with some exceptions was implemented.

The main difficulty with this kind of approach is that it's possible that the compilation, for whatever range determined, does not stop. Meaning that the effect of the edit goes far beyond the determined range, which function can not know this without compiling... It can happen for example if you edit in C and type "{" then all the scopes below are affected by this opened (and not closed yet) scope. In Markdown it can happen when you open a fence code block (using the ``` opening fence). So you need to have a proper way to handle these edge cases. The other problem is to handle the state associated with these regions and handle the non-stopping compilation case talked before.

All this, as I have discovered, make this kind of compilation and it's associated syntax highlighting really difficult to implement properly and fast enough.

In order to be fast, this process needed to be as asynchronous as possible, because there was some tiny but noticeable lags on the main thread. Even partial compilation was more around 8ms to 12ms on my computer (an old macbook pro 2012). But there is also some cases where asynchronous is not suitable, in which cases synchronous processing is used, but, only when absolutely necessary. So, a mechanic which allows to switch between asynchronous and synchronous processing was needed.

All this to say, it's possible but really difficult to do properly. Every bit of the CPU power have to be extracted to make it comfortable to use. I can just imagine with the complexity of C++ what a nightmare it would be to manage, but it should be possible with a proper compiler architecture that modularise partial compilation and encapsulates the inherent complexity of this approach.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#76

Earlier quoted context omitted.

Mosh has this idea that you can keep typing and sending asynchronously even though you need the ACKs to find out what really happened, then when you get them you just redraw accordingly. Humans won't type too fast for too long, so eventually there will be time to catch up and let the user see what actually happened. The key is to distinguish client-side speculative outcomes from actual outcomes. Imagine that the text…

You are describing classic branch-and-merge. “Here’s my branch that I created offline.” “Sorry, there are merge conflicts, please resolve them before resubmitting,” or, “I resolved them without consulting you.”

Yes, but I'm saying that that can work very well for a visual, interactive application.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#77

I think CRDTs would make much more sense in a projectional editor than a text one. When the changes are mutations to the abstract syntax tree its more well defined how a merge would end. Also, the merge results don't have the opportunity to be invalid syntax.

It is really crazy that we go through these massive hoops to simulate what would be trivial to do in an AST editor. I recently read through some of the literature on projectional editors, and while they have historically had some usability issus I really hope that this will change in the future.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#78
post #70

Earlier quoted context omitted.

TL;DR CRDT is completely irrelevant to any of the highlighting/etc stuff Most highlighters are lexers. Advanced highlighters/folders are parsers. The lexing/parsing that is required for highlighting is easy to make incremental for all sane programming languages. for LL(star) grammars, adding incrementality is completely trivial (i sent patches to ANTLR4 to do this) for LR(k) grammars, it's more annoying but possible…

Very interesting and informative. But I suppose what the user really wants is the next step: not just incremental parsing, but also incremental compilation (or at least the error-checking part of the compilation process).

The basic error checking comes with incremental parsing. A lot of semantic error checking is also not that bad to make incremental (though some languages are just really really bad here).

Incremental compilation depends on the constraints on environment (IE are you trying to incrementally produce normal object files or what)

The more you relax the environmental constraints the easier it gets.

It also depends on just how non-local an effect the programming language allows. For most programming language, general incremental compilation requires either strongly overestimating possibly-modified sets, or global interprocedural dataflow + pointer analysis.

Most choose the former, or don't do general incremental, but instead something like "edits to functions are incremental, edits to global data/types/etc are not"

(This is even without compiler optimization on).

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#79
post #51

Earlier quoted context omitted.

TL;DR CRDT is completely irrelevant to any of the highlighting/etc stuff Most highlighters are lexers. Advanced highlighters/folders are parsers. The lexing/parsing that is required for highlighting is easy to make incremental for all sane programming languages. for LL(star) grammars, adding incrementality is completely trivial (i sent patches to ANTLR4 to do this) for LR(k) grammars, it's more annoying but possible…

Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed…

"Even on very large C++ project like Chrome, there's no reason why incremental updates should take more than 1-2ms. If all you're doing is changing a single function in the binary file, why do our linkers rewrite the whole thing"

Because it requires N^3+ dataflow problems to track what is possibly changed with significant accuracy.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#80
post #71
post #64

Earlier quoted context omitted.

> Instead of batch compiling artifacts to disk like its 1970 [...] I am delighted to see people discussing this. Batch orientation made sense in a very resource-constrained era. But at this point we have more RAM and CPU than we know what to do with. It seems so obvious to me that the correct solution is to prioritize developer experience and keep everything hot. My single biggest barrier to developing faster is the…

The perfect place to start would be support in LLVM backends, maybe they are already working on this.

I don’t know that that’s true. I doubt you could do this sort of redesign simply in an LLVM backend because a “hot” compiler would work differently at so many levels of abstraction. I think an easier place to start would be a self contained compiler with a little less scope than llvm. There we could figure out the patterns, find a clean set of internal APIs and make some sweet demos. And then with that approach the same task in LLVM.
Post reply on HN