3 ms·

Character by character changes is almost certainly too low level. I understand wanting symbol by symbol. Heck, I even understand pulling it up the abstraction

by taeric 3y ago

Character by character changes is almost certainly too low level. I understand wanting symbol by symbol. Heck, I even understand pulling it up the abstraction ladder and look at it at the semantic level. Having a diff of the form, "variable name changed, conditional added, etc" looks magical. I recall seeing some good demos of tools that could do this. Unfortunately, none of these efforts have ever panned out. I cannot claim that they are unable to work, but they have not done so, yet. And I'm not clear on why that we think they will. From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. The only algorithm that always works is to bounce it back to a user. With LLMs gaining in power, I suppose you could lean on one of them for the first non-mechanical pass? Which sucks, because quite frankly CRDT and friends are fun data structures. But, they make the easy and trivial cases much much harder. Which is why a series of snapshots is far more effective. Those snapshots are not for the convenience of the tool tracking changes. They are for the convenience of every other tool that you are using.

josephg 3y ago
> From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. CRDTs (and similar algorithms) can do a whole lot better than git does today. They simply have more information to work with about what changed, and where. Git has to reconstruct that from re-diffing snapshots - which is always a lossy process. It hasn’t been done because until recently (the last few years), CRDTs were considered too slow for practical use. It’s just recently that we as a species figured out how to make them fast and lightweight.
- taeric 3y ago
  I feel you are slightly cheating on this, though. I'll explain. If you are only storing snapshots, I worry that you actually cannot do better. If you are willing to store the snapshots as either a list of operations from the last state, or you can decompose state changes to something coherent, then you can maybe do better. That is, the cheat, I feel, is that most of what anyone does with anything from source control, is to work with the snapshot. Building a diff between trees is surprisingly rarely done. Yes, you see the reconstruction of one every time you run `git log -p`, but by and large, that is not what you work with. (And this is ignoring that you often want to see the diff between two tree heads...) Now, you seem to be pushing to change this and to have people always work with the CRDT for everything they do? Does this not push it so that the source control now becomes something that every editing tool in use has to also work with it? Aside, I'm also not at all clear that CRDTs have gotten to the point that they can do octopus merges at a reliable rate. More, I'm not clear on what merges actually look like with CRDTs, in a source control sense. Happy to see any reading, if you have a link.
  - josephg 3y ago
    I don’t understand how I’m “cheating” - at what? Character by character editing traces can be made incredibly efficient with some tweaks. Is that what you’re getting at? In the example traces I’ve gathered, the inserted characters themselves still make up the majority of the resulting file size. That is, files on disk are almost always smaller than 2 bytes per keystroke. And we can always reproduce a document at any snapshot state - quite easily, too. I don’t have a link at the moment, but I’ve ported editing traces from git (by re-running diff match patch) and used CRDTs to do octopus style merges. They merge fine - just as you’d expect. (As I said earlier, the hard problem is adding back any conflict markers so humans can eyeball the result). There’s nothing special in doing branches. You just only merge the set of edits (crdt messages) that show up in any particular branch’s history.
    - taeric 3y ago
      Yes, that is what I was getting at. The cheat is that none of that information is available in the snapshots. And we use the snapshot, as that is what all of the other tooling creates and works with. The fact that most people using git don't refer to the snapshots as a thing is pretty much how invisible that is to all of our tooling. It isn't a special thing, it is the thing. If you are pushing for a state based crdt that can be reconstructed from snapshots, then you aren't needing to change get as a whole, but only the diffing tool? If you want all diffs to be based on the edits users did, you aren't wanting to change get, as much as all of the tooling users use. No?

by taeric 3y ago

josephg 3y ago

> From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. CRDTs (and similar algorithms) can do a whole lot better than git does today. They simply have more information to work with about what changed, and where. Git has to reconstruct that from re-diffing snapshots - which is always a lossy process. It hasn’t been done because until recently (the last few years), CRDTs were considered too slow for practical use. It’s just recently that we as a species figured out how to make them fast and lightweight.

taeric 3y ago
I feel you are slightly cheating on this, though. I'll explain. If you are only storing snapshots, I worry that you actually cannot do better. If you are willing to store the snapshots as either a list of operations from the last state, or you can decompose state changes to something coherent, then you can maybe do better. That is, the cheat, I feel, is that most of what anyone does with anything from source control, is to work with the snapshot. Building a diff between trees is surprisingly rarely done. Yes, you see the reconstruction of one every time you run `git log -p`, but by and large, that is not what you work with. (And this is ignoring that you often want to see the diff between two tree heads...) Now, you seem to be pushing to change this and to have people always work with the CRDT for everything they do? Does this not push it so that the source control now becomes something that every editing tool in use has to also work with it? Aside, I'm also not at all clear that CRDTs have gotten to the point that they can do octopus merges at a reliable rate. More, I'm not clear on what merges actually look like with CRDTs, in a source control sense. Happy to see any reading, if you have a link.
- josephg 3y ago
  I don’t understand how I’m “cheating” - at what? Character by character editing traces can be made incredibly efficient with some tweaks. Is that what you’re getting at? In the example traces I’ve gathered, the inserted characters themselves still make up the majority of the resulting file size. That is, files on disk are almost always smaller than 2 bytes per keystroke. And we can always reproduce a document at any snapshot state - quite easily, too. I don’t have a link at the moment, but I’ve ported editing traces from git (by re-running diff match patch) and used CRDTs to do octopus style merges. They merge fine - just as you’d expect. (As I said earlier, the hard problem is adding back any conflict markers so humans can eyeball the result). There’s nothing special in doing branches. You just only merge the set of edits (crdt messages) that show up in any particular branch’s history.
  - taeric 3y ago
    Yes, that is what I was getting at. The cheat is that none of that information is available in the snapshots. And we use the snapshot, as that is what all of the other tooling creates and works with. The fact that most people using git don't refer to the snapshots as a thing is pretty much how invisible that is to all of our tooling. It isn't a special thing, it is the thing. If you are pushing for a state based crdt that can be reconstructed from snapshots, then you aren't needing to change get as a whole, but only the diffing tool? If you want all diffs to be based on the edits users did, you aren't wanting to change get, as much as all of the tooling users use. No?