3 ms·

Very cool seeing this pop up again! I've done a bunch more optimization since I wrote this post last year, and I'm in the process of writing a follow-up. Spoi

Very cool seeing this pop up again! I've done a bunch more optimization since I wrote this post last year, and I'm in the process of writing a follow-up. Spoilers: - Since last year I've made this algorithm run another ~2x faster. The performance improvement comes about largely thanks to replacing ropey with my own jumprope[1] library. (~60ms -> 30ms) - I've written a new CRDT algorithm which is another 10x faster. (time drops to 4ms). But the algorithm is only faster when the editing history is largely linear. So, its a better approach for something like google docs (where most edits are made by one user or online). But its much worse for something like Git. I think its possible to make it better in every case, but I haven't figured out how to do that yet. I re-tested automerge a couple of months ago. Automerge-rs has adopted a lot of the tricks I listed in this post, which is delightful to see. Performance has gotten a lot better (5 minutes in 2021 dropped to 400ms in 2022). But its still 100x slower than diamond types and uses 100x more RAM (200mb for automerge vs 2mb for diamond types). The main optimization automerge is missing is the internal run-length encoding trick that Yjs pioneered. [1] https://crates.io/crates/jumprope https://crates.io/crates/jumprope

dspillett 4y ago
> I think its possible to make it better in every case, but I haven't figured out how to do that yet. There are some processes for which there is no one-algo-fits all solution. Rather than trying to find a general solution that is not terrible for either case but also not optimal for either case, could it be more efficient overall to try detect which case you have and apply the most suitable method? Of course you'd still have to implement & maintain both methods, and there is the cost of the check on each use, and the higher cost if the check's heuristic sometimes picks the less optimal method - that might all add up to meaning a single method that is good enough for all but not ideal for either may still be the best option. Unless there is a method to be found that is ideal (or reasonably close to) for all cases.
- josephg 4y ago
  That may well be where I end up, but I'm not ready to give up hope of a single unified fast algorithm just yet.
DennisP 4y ago
Last year you wrote "maybe the future of all software - but I'm not ready to talk about that yet." Are you ready to talk about it?
- josephg 4y ago
  I think its ridiculous we still use binary files in native software. I want a world where the operating system stores semantically rich data (imagine if all files on your computer were JSON or something). Instead of an app "saving" by overwriting the entire file, an app could send a patch (diff) to the OS, which could store a transactional change log. Immediately we'd get faster saving, and no chance at data corruption when things get saved. And we could have optional change tracking for everything. Then rather than loading the data from disk at startup, apps could subscribe to a change feed from the OS. I want to be able to open the same file in 2 apps. As I edit the file in one app, I should see my changes immediately appear in the other app. CLI tools like wc could update the word count of a file live, as its being edited. Compilers could consume code changes live, and update binaries based on super fine-grained incremental compilation, without needing to diff. And this model could be extended to the cloud. Right now you can't really store a google doc on your local computer and have it sync in an intelligent way with actual google docs. And if you use Dropbox and two users edit the same file, the file ends up in an unresolvable conflict state. With this model, and using CRDTs, we could seamlessly replicate changes between devices and users. So, I could edit a file locally (on a plane), it could replicate over wifi to my phone and I can keep editing it there. And then I could share it with another user, who can see my changes, edit it with me and so on. And the same data could be exposed through a collaborative editor in the browser, or with native apps. Thats the model I want for computers. None of this "native vs web app" distinction. Just a user's work, transparently replicated. I'm working on building a platform for this, but I'm not ready to demo it yet.

dspillett 4y ago

> I think its possible to make it better in every case, but I haven't figured out how to do that yet. There are some processes for which there is no one-algo-fits all solution. Rather than trying to find a general solution that is not terrible for either case but also not optimal for either case, could it be more efficient overall to try detect which case you have and apply the most suitable method? Of course you'd still have to implement & maintain both methods, and there is the cost of the check on each use, and the higher cost if the check's heuristic sometimes picks the less optimal method - that might all add up to meaning a single method that is good enough for all but not ideal for either may still be the best option. Unless there is a method to be found that is ideal (or reasonably close to) for all cases.

josephg 4y ago
That may well be where I end up, but I'm not ready to give up hope of a single unified fast algorithm just yet.

DennisP 4y ago

Last year you wrote "maybe the future of all software - but I'm not ready to talk about that yet." Are you ready to talk about it?

josephg 4y ago
I think its ridiculous we still use binary files in native software. I want a world where the operating system stores semantically rich data (imagine if all files on your computer were JSON or something). Instead of an app "saving" by overwriting the entire file, an app could send a patch (diff) to the OS, which could store a transactional change log. Immediately we'd get faster saving, and no chance at data corruption when things get saved. And we could have optional change tracking for everything. Then rather than loading the data from disk at startup, apps could subscribe to a change feed from the OS. I want to be able to open the same file in 2 apps. As I edit the file in one app, I should see my changes immediately appear in the other app. CLI tools like wc could update the word count of a file live, as its being edited. Compilers could consume code changes live, and update binaries based on super fine-grained incremental compilation, without needing to diff. And this model could be extended to the cloud. Right now you can't really store a google doc on your local computer and have it sync in an intelligent way with actual google docs. And if you use Dropbox and two users edit the same file, the file ends up in an unresolvable conflict state. With this model, and using CRDTs, we could seamlessly replicate changes between devices and users. So, I could edit a file locally (on a plane), it could replicate over wifi to my phone and I can keep editing it there. And then I could share it with another user, who can see my changes, edit it with me and so on. And the same data could be exposed through a collaborative editor in the browser, or with native apps. Thats the model I want for computers. None of this "native vs web app" distinction. Just a user's work, transparently replicated. I'm working on building a platform for this, but I'm not ready to demo it yet.