Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Git is Inconsistent

r6.ca

Post reply on HN
Print view View original

41–50 of 82 posts

Re: Git is Inconsistent

#41

Post by pjscott »

saalweachter wrote: post #26

Is there any reason to assume that merges should be associative? Hell, of the four normed division algebras, only three are associative; just because you can say "operations on octonions should be associative" doesn't mean that you can necessarily create a system of octonions where it's true. For what it's worth, "git pull --rebase" does enforce a specific order to changes (local changes always happen after remote ch…

There are ways of making a DVCS that allow all merges to be associative, and all patches commutative except when there's a causal dependency between them, e.g. if patch A creates a file, and patch B edits that file, then they cannot commute. I believe darcs makes these guarantees, and making a correct implementation is relatively straightforward. (Making it fast is more complicated, but definitely doable.)

Ultimately, though, what you really want is for the VCS to just do what you mean. That's a lot trickier than providing mathematical guarantees about patch reordering and convergence.

Re: Git is Inconsistent

#42

Post by knowtheory »

davidmathers wrote: post #30
Peaker wrote: post #22

Earlier quoted context omitted.

> Git is consistent: a merge will always produce the same result for the same files I thought the point was that if you pull the exact same commits in different order the merge will produce a different result for the same files, meaning that in git the history does matter. Whereas darcs/etc will always produce the same result, such that history does not matter?

pull the exact same commits in different order Sort of. The OP doesn't write clearly. He's also confused about how git works. What he means is.. Say Bob has 2 commits (B1-B2) and Alice has 1 (A1) Scenario 1: Alice merges each of Bob's commits in sequence (i.e. she replays his commit history onto her repo: A1-B1-B2). Scenario 2: Alice merges only B2 (A1-B2). The point is that, with git, Alice's repo will be different…

That's what i don't get.

I don't understand where or how you could encounter a circumstance where this would matter. This complaint seems to be an abstract theoretical point (maybe to support git alternatives? dunno) that even esoteric usage of a DSCV would never come across.

I dunno, maybe i'm not being creative enough in my use of histories.

EDIT: Okay this explains everything in a considerably more concise fashion than the article does: http://news.ycombinator.com/item?id=2456529

Re: Git is Inconsistent

#43

Post by davidmathers »

ob wrote: post #40
davidmathers wrote: post #14

Here's the short version: I am the original sentence. Alice commits a change in her repo: I am a different sentence. Bob commits a change in his repo: I am the original sentence. I am the original sentence. Now Alice pulls Bob's commit. What should happen? The argument is that in certain cases it can be known which of Bob's 2 sentences is the original and which is the copy (due to context provided by an intermediate…

No, you are totally wrong. Did you even try this in Git? Any sensible VC system will give you a conflict here. The article discusses auto-merge behaviour. You ABSOLUTELY can get auto-merge to work 100% of the time. When it doesn't you get a conflict that you need to manually resolve. BitKeeper does get this right (disclaimer: I am one of the developers of BitKeeper).

What a powerful insight. Only now do I see how truly wrong I was. I don't know how I could have been so blind.

Re: Git is Inconsistent

#44

Post by tytso »

psykotic wrote: post #34
DennisP wrote: post #31

Earlier quoted context omitted.

Joel Spolsky describes mercurial as storing lists of changes, rather than a series of file snapshots. "And so, when we want to merge our code together, Mercurial actually has a whole lot more information: it knows what each of us changed and can reapply those changes, rather than just looking at the final product and trying to guess how to put it together. "For example, if I change a function a little bit, and then m…

The short of it is that Joel is wrong. Git and Mercurial use similar data structures and neither of them store changes in the way that Darcs stores changes. Maybe he knows that full well but is telling a white lie to get a teaching point across. If you make a change to a file in Git and commit it, the new version will store the full updated contents of that file (delta compression is an orthogonal issue). Indeed, my…

Jeol is half-right and half-wrong. Mercurial stores its version history as a series of deltas, yes. Git stores its version history as a series of snapshots. (Git does do delta compression, but the delta compression is done independently of the version history, which is why git can be highly efficient at storing its complete version history in its repositories.) This doesn't matter, though, since you can get from snapshots to deltas and vice-versa very easily; the two systems are dual from each other. In that way, he is also wrong --- the reason why git and mercurial are smarter than svn is not because of how they store their commits, since that really is an implementation detail.

At least for git, git will do start by doing a 3-way merge, and if that fails, only then will it try to resolve the merge conflict by looking at the intermediate history. This is much faster, and for Linus, who wants to encourage lots of branching and merging, merge speed is highly important. This is what makes git fundamentally better than svn or cvs; the fact that it can get many more merge cases right, and that it can do this quickly and painlessly. So the darcs folks who say that git only does 3-way merges is incorrect; git can do much more sophisticated things than just 3-way merges. However, it only pulls out these more sophisticated weapons when the simple approach doesn't work (and 95+% of the time, the simple approach works just great).

What Darcs did is it focused on the "get many, many, MANY more merge cases right", but it completely ignored the "quickly" part of the equation. That's partially because it's amazingly complicated. Just take a look at the Darcs "Theory of Patches", and its obsessive fixation on being able to whether or not you different patches are commutative, etc., and that gives you a very strong hint of its complexity right here: http://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theor...

The question is whether this complexity is necessary or not. It certainly does slow things down. And fundamentally, that's the question; is it worth it to slow down nearly every single SCM operation just so that a few corner cases can be handled automatically, instead of requiring minimal human intervention? Since people of good will can disagree on this, the controversy certainly continues to exist. But I think a very large number of people are quite happy with the engineering tradeoff made by systems such as Git and Mercurial.

Re: Git is Inconsistent

#45

Post by lambda »

yuvadam wrote: post #6

To quote Johannes Schindelin [1] : This all just proves again that there can be no perfect merge strategy; you'll always have to verify that the right thing was done. [1] - http://thread.gmane.org/gmane.comp.version-control.git/10574...

It's obvious that there is no perfect merge strategy. There will always be ambiguous cases, cases in which the merge algorithm doesn't have enough information to make an informed decision, or cases in which there are changes that effect lines not caught by doing line-by-line diffs. I think that the point that Zooko and Russel O'Connor are making is that there are cases in which the merge algorithm does have available to it the information necessary to make a better decision (that is, the entire history of changes, rather than just just the two changes being merged and their common ancestor), but in Git, that information isn't being taken into account. While you are never going to have a perfect merge strategy, the argument is that you can have one that is better.

Some people, however, feel that the Git algorithm is good enough, and doing it the Darcs way would be slower without much benefit other than for fairly artificial examples (you have to be doing something where you move a block of code, and then re-introduce that same block back in the original place on one side of the merge, while patching that block on the other side of the merge). Personally, I've found Git's merge strategy adequate for everything I've used it for. Git has support for multiple merge strategies, so if someone wanted to implement a better but slower one as an opt-in, they could do so.

Re: Git is Inconsistent

#46

Post by psykotic »

tytso wrote: post #44
psykotic wrote: post #34

Earlier quoted context omitted.

The short of it is that Joel is wrong. Git and Mercurial use similar data structures and neither of them store changes in the way that Darcs stores changes. Maybe he knows that full well but is telling a white lie to get a teaching point across. If you make a change to a file in Git and commit it, the new version will store the full updated contents of that file (delta compression is an orthogonal issue). Indeed, my…

Jeol is half-right and half-wrong. Mercurial stores its version history as a series of deltas, yes. Git stores its version history as a series of snapshots. (Git does do delta compression, but the delta compression is done independently of the version history, which is why git can be highly efficient at storing its complete version history in its repositories.) This doesn't matter, though, since you can get from snap…

Great summary!

I stopped using Darcs a few years ago, but I heard the current generation at least resolved the notorious exponential time slowdowns.

Git's speed is definitely a big selling point. More than that, the ecosystem and services like GitHub are what really sold me on it versus alternatives. But Mercurial has a lot to offer and its simpler user interface, better Windows support and extensions like BFiles make it a much better fit for certain use cases.

I shouldn't have been so hasty to say that Mercurial doesn't store changes. But I'd argue, and you seem to agree, that Mercurial's revlog does not reflect a difference from Git in the basic philosophy of merging and the status and role of versions. In both cases you're basically dealing with genealogically annotated purely functional trees. By comparison, Darcs's theory of patches represents a radical departure. At the very least I'm happy that someone is trying to think deep and different thoughts in this area.

Re: Git is Inconsistent

#47

Post by Groxx »

Super-simple-summary:

Git doesn't use history to determine merge behavior (edit: in this circumstance). Git behaves like applying patches. Darcs uses the history to make "intelligent" patches.

It's a matter of taste. If you look at Git as having a history, therefore should use the history, yes, it's incorrect. But if you look at it as a patch manager, it's behaving as it should, and Darcs is frighteningly unpredictable - the numbers on the patch might not match the numbers of the lines it modifies.

I side with Git on this. I can generate patches from Git that will work anywhere, and use them 100% identically within Git as manually applying them. The same cannot be said for Darcs.

Re: Git is Inconsistent

#48

Post by Groxx »

davidmathers wrote: post #14

Here's the short version: I am the original sentence. Alice commits a change in her repo: I am a different sentence. Bob commits a change in his repo: I am the original sentence. I am the original sentence. Now Alice pulls Bob's commit. What should happen? The argument is that in certain cases it can be known which of Bob's 2 sentences is the original and which is the copy (due to context provided by an intermediate…

This is not an accurate summary. The claim is that a "correct" VCS will detect a move, not a copy, which is an entirely different beast - if it were a copy, it might be correct to apply the patch to both lines in some situations.

Re: Git is Inconsistent

#49

Post by Groxx »

knowtheory wrote: post #42
davidmathers wrote: post #30

Earlier quoted context omitted.

pull the exact same commits in different order Sort of. The OP doesn't write clearly. He's also confused about how git works. What he means is.. Say Bob has 2 commits (B1-B2) and Alice has 1 (A1) Scenario 1: Alice merges each of Bob's commits in sequence (i.e. she replays his commit history onto her repo: A1-B1-B2). Scenario 2: Alice merges only B2 (A1-B2). The point is that, with git, Alice's repo will be different…

That's what i don't get. I don't understand where or how you could encounter a circumstance where this would matter. This complaint seems to be an abstract theoretical point (maybe to support git alternatives? dunno) that even esoteric usage of a DSCV would never come across. I dunno, maybe i'm not being creative enough in my use of histories. EDIT: Okay this explains everything in a considerably more concise fashion…

It would matter in this situation:

In the beginning:

  function A(){
    return 1;
  }
Now commit this in one branch:

  function B(){
    return 1;
  }
  function A(){
    return 1;
  }
then this:

  function A(){
    return 1;
  }
  function B(){
    return 1;
  }
  function A(){
    return 1;
  }
And then this in another branch off the base:

  function A(){
    return 2;
  }
Now merge the two end points. Which is correct? This, assuming a purely line-based diff:

  function A(){
    return 2;
  }
  function B(){
    return 1;
  }
  function A(){
    return 1;
  }
or this, assuming knowledge of the history of events?

  function A(){
    return 1;
  }
  function B(){
    return 1;
  }
  function A(){
    return 2;
  }
In Javascript, where such code is acceptable, `A()` now returns 1 or 2.

In Git, or by applying patches manually, it depends on the order in which you merge. If you merge the `B()A()` branch with the `return 2` branch and then the `A()B()A()` one, you'll get the second result. But if you merge the `A()B()A()` directly with the `return 2` branch, you'll get first one. The same set of changes producing different outcomes.

In Darcs, the history between `A()`, `B()A()`, and `A()B()A()` are checked, and it's seen that the second `A()` is the "original" one, so the `return 2` is applied to that one.

Which means that you won't necessarily get the same behavior merging two Darcs patches as you would merging it within the repository, where there is a history. Git behaves exactly as if you were dealing with patches. I side with Git on this, personally, but it's a valid point - you have history, why not use it?

Re: Git is Inconsistent

#50

Post by tzs »

davidmathers wrote: post #14

Here's the short version: I am the original sentence. Alice commits a change in her repo: I am a different sentence. Bob commits a change in his repo: I am the original sentence. I am the original sentence. Now Alice pulls Bob's commit. What should happen? The argument is that in certain cases it can be known which of Bob's 2 sentences is the original and which is the copy (due to context provided by an intermediate…

Based on the article and the Reddit discussion, that is not correct. It's more like this:

Scenario #1:

Alice and Bob both make changes. Alice pulls Bob's change and merges it. Bob makes a second change. Alice pulls the second change and merges it.

Scenario #2:

Alice and Bob both make changes. Bob makes a second change. Alice pulls Bob's changes and merges.

The final result, which is Alice's change merged with Bob's two changes, ends up different in the two cases, and there were no merge conflicts.

Post reply on HN