7 ms·

Linus Torvalds proposes a change to the Git commit object format

153 points by avar 15y ago

macrael 15y ago
I'd love an explanation of what "generation numbers" are.
- pufuwozu 15y ago
  Looking at the diff, it seems like a generation number is just a number the parents that a commit has. For example: Commit a553af has no parents, it has generation number of 0. Commit c464e0 is the next commit, it has generation number 1. And so on. Branches count independently of one another. When commits have multiple parents (e.g. merges), the generation number starts counting from the previous maximum.
  - pyre 15y ago
    > just a number the parents that a commit has It's the max length from a commit to reach a root node in the graph. So any time that you hit a fork in the path you take the longest route.
- malkia 15y ago
  http://news.ycombinator.com/item?id=2765942 http://news.ycombinator.com/item?id=2765942 >> OK, finally found a decent explanation of what a Git generation number actually IS: http://www.spinics.net/lists/git/msg161165.html http://www.spinics.net/lists/git/msg161165.html
breckinloggins 15y ago
Can someone explain what generation numbers are? Googling "git generation numbers" pulls up mostly this discussion thread. I'm assuming they're easy-to-remember incremental numbers tied to commit? Like 1, 2, 3, or tied to commit and branch, like master/1, etc.?
- Kliment 15y ago
  Here is how I understand the problem. At the moment, each commit stores a reference to the parent tree. By parsing that tree and reading the entire history you can obtain a hierarchy of commits. Because you need to order commits in many situations, reading the entire history is extremely inefficient, so git uses timestamps to determine the ordering of commits. This of course fails if the system clock on a given machine is off. With a generation number, you can get an ordering locally from the latest commits, without having to rely on timestamps or read the entire tree. When you have a commit with generation n, any later commits that include it wound have generation >n, so to tell the relation between commits, you only need look as far back as n, and you can immediately get the order of any intermediate commits. It has nothing to do with "easy to remember". It's about making git more efficient and robust.
breckinloggins 15y ago
OK, finally found a decent explanation of what a Git generation number actually IS: http://www.spinics.net/lists/git/msg161165.html http://www.spinics.net/lists/git/msg161165.html
- pak 15y ago
  Beisdes analyzing properties of the commit graph, which doesn't seem to be a common task, what about them is so useful that they need to be stored in commit headers now? For instance, what day-to-day operations do they actually make faster? At first, it sounded like it might be for easier navigability (e.g. expanding git-rev-parse) but I don't see that in this description.
  - davvid 15y ago
    "git tag --contains" needs to know the generation number of old tags, which is expensive to calculate. "git describe" would be faster for the same reason.
- andrewflnr 15y ago
  So it's almost, but not quite, like the revision numbers everyone else has always had?
  - iclelland 15y ago
    Yes -- almost, but not quite. If you and I each create a branch off of a commit with gen #123, then, as I understand it, the subsequent commits in my branch would be #124, #125, etc., and your commits in your branch would also be #124, #125, etc. Contrast this with CVS, where I would have 1.124.1.1, 1.124.1.2, erc., and you would have 1.124.2.1, 1.124.2.2, or with Subversion, where I might get revisions 125, 128, and 129, while the server gave your commits #124, 127 and 130, and someone else, on a totally different part of the project got #126. As long as development proceeds linearly, on a single branch, then yeah, it's about the save as revision numbers in a centralized RCS -- once you start branching and merging, though, it represents a different concept entirely.
nplusone 15y ago
Change last name to 'Torvalds' (edit: name in title changed)
mscarborough 15y ago
I don't generally come across Linus' dev threads, but it's usually in the context of some linkbaity 'watch Linus smack this dude down' or something of that nature. This reads like a really productive thread from my limited understanding of git internals. It's pretty cool how much good engineering thought is going into this proposal. Maybe that's why git rocks so hard.
- jacknagel 15y ago
  Minor smackdown from this thread here: http://article.gmane.org/gmane.comp.version-control.git/177186 http://article.gmane.org/gmane.comp.version-control.git/1771...
Peaker 15y ago
Why call it a "generation number" and not "depth"?
- rs 15y ago
  Think they're using "generation" here in the context of number of parents (yes, "depth" would work fine as well, but is a more general term)
  - pyre 15y ago
    > number of parents s/parents/ancestors/ But that statement only holds up on branches without any merge commits. Because the actual algorithm does not just total up the number of ancestors.
- caf 15y ago
  Perhaps because "Generation" continues the Parent/Child allegorical language.
- Canopy 15y ago
  "Depth" would (at least for me) evoke the shortest path to a commit. The generation number is the longest path.
- beza1e1 15y ago
  Since gitk and others put new commits on top, i'd propose "height" instead of "depth" ;)
derrickpetzold 15y ago
I was wondering how they got along without generation numbers for so long. It was by comparing timestamps and those are unreliable because systems can be misconfigured. How they are going to handle legacy repos with that problem I still don't get. I am guessing that history is f'd.
- mdwrigh2 15y ago
  New versions of git will actually go back and generate this information for old commits. This will lead to git being slightly slower when in old repositories until all the commits contain the generation information, but that should happen fairly quickly.
  - derrickpetzold 15y ago
    I was talking about the case where the timestamps are off. I don't think there is any way to fix that.
    - ajuc 15y ago
      You just go the whole way up to the root node counting parents (taking max length when there are many routes), no problem with amiguity. The problem is - it's slow.
  - iclelland 15y ago
    Not necessarily "all the commits", as I understand it (there's some debate in the thread, so I could be wrong) As long as at least one commit in each merged branch has a generation stored, it's simple to compute without going all the way back to all the roots.
rlpb 15y ago
What I like about git is that it stores only the minimum amount of information, and this makes it easy to explain. A commit hash is a hash of canonical information, not of derived information. It seems really ugly to store derived information in a commit (specifically, that the hash would be altered by it). It seems that Jeff has said the same thing, but Linus disagrees. Vocally. http://www.spinics.net/lists/git/msg161336.html http://www.spinics.net/lists/git/msg161336.html
- derrickpetzold 15y ago
  >It seems really ugly to store derived information in a commit I don't understand how generation numbers are derived information. They are used to find the position of the commit in relation to another. That makes them information that is essential to the commit. The problem was to get around them not being there timestamps were compared and that is not reliable for obvious reasons. So I really don't understand why any one would complain about this.
  - iclelland 15y ago
    They're derived. You can tell that they're derived information by the fact that you can compute them for old commits, long after commit time, which is exactly what part of this proposal is to do. You can derive them simply by counting the maximum number of steps between a commit and any of its roots. The essential information isn't the generation numbers; it's the structure of the commit history -- the actual chains of commits, with all of the branches and merges. Generation numbers are just an artifact of counting. On the other hand, this information is very handy, once you have it, for certain algorithms, and it could be expensive to re-compute all the time, which is why the proposal is to generate and store them explicitly. (This is also the reason that timestamps have been used before, even if they were a bit of a hack -- they're readily available, and way faster than recomputing generation numbers all the time)
- ryannielsen 15y ago
  From my understanding, they're essentially adding this as an additional bit of information that's minimally required. The currently used timestamps are error prone and thus will be replaced by generation numbers which are more robust. They're still adhering to the principle of only storing the minimum amount of information, they're just adding generation numbers to that set. In fact, you could make the argument that timestamps are the derived information that git has been storing all along while generation numbers are the canonical information which should have been stored from the beginning. Generation numbers are a result of the state of the tree, while timestamps are derived from the ambient (and potentially incorrect!) environment from which the commit was made.
cypherpunks01 15y ago
What operations would be sped up by having generation numbers? I see Jeff King's message that they would make certain bounding traversals faster, but when do bounding traversals need to be computed when I'm using git day-to-day?
- Rauchg 15y ago
  It's also about making git not error-prone, which the current timestamp approach seems to do.
gregschlom 15y ago
Ah! I knew I was going to stumble upon Linus' signature "that's total and utter bullshit" somewhere: http://www.spinics.net/lists/git/msg161348.html http://www.spinics.net/lists/git/msg161348.html
pyre 15y ago
I like the suggestion of storing the generation numbers in the pack index. When you generate a pack you're already parsing the entire tree. That makes more sense than requiring all future git objects to have 'generation numbers' jammed into them. Especially because it introduces an incompatibility with current git objects, which it would probably be best to avoid.

153 points by avar 15y ago

macrael 15y ago

I'd love an explanation of what "generation numbers" are.

pufuwozu 15y ago
Looking at the diff, it seems like a generation number is just a number the parents that a commit has. For example: Commit a553af has no parents, it has generation number of 0. Commit c464e0 is the next commit, it has generation number 1. And so on. Branches count independently of one another. When commits have multiple parents (e.g. merges), the generation number starts counting from the previous maximum.
- pyre 15y ago
  > just a number the parents that a commit has It's the max length from a commit to reach a root node in the graph. So any time that you hit a fork in the path you take the longest route.
malkia 15y ago
http://news.ycombinator.com/item?id=2765942 http://news.ycombinator.com/item?id=2765942 >> OK, finally found a decent explanation of what a Git generation number actually IS: http://www.spinics.net/lists/git/msg161165.html http://www.spinics.net/lists/git/msg161165.html

breckinloggins 15y ago

Can someone explain what generation numbers are? Googling "git generation numbers" pulls up mostly this discussion thread. I'm assuming they're easy-to-remember incremental numbers tied to commit? Like 1, 2, 3, or tied to commit and branch, like master/1, etc.?

Kliment 15y ago
Here is how I understand the problem. At the moment, each commit stores a reference to the parent tree. By parsing that tree and reading the entire history you can obtain a hierarchy of commits. Because you need to order commits in many situations, reading the entire history is extremely inefficient, so git uses timestamps to determine the ordering of commits. This of course fails if the system clock on a given machine is off. With a generation number, you can get an ordering locally from the latest commits, without having to rely on timestamps or read the entire tree. When you have a commit with generation n, any later commits that include it wound have generation >n, so to tell the relation between commits, you only need look as far back as n, and you can immediately get the order of any intermediate commits. It has nothing to do with "easy to remember". It's about making git more efficient and robust.

breckinloggins 15y ago

OK, finally found a decent explanation of what a Git generation number actually IS: http://www.spinics.net/lists/git/msg161165.html http://www.spinics.net/lists/git/msg161165.html

pak 15y ago
Beisdes analyzing properties of the commit graph, which doesn't seem to be a common task, what about them is so useful that they need to be stored in commit headers now? For instance, what day-to-day operations do they actually make faster? At first, it sounded like it might be for easier navigability (e.g. expanding git-rev-parse) but I don't see that in this description.
- davvid 15y ago
  "git tag --contains" needs to know the generation number of old tags, which is expensive to calculate. "git describe" would be faster for the same reason.
andrewflnr 15y ago
So it's almost, but not quite, like the revision numbers everyone else has always had?
- iclelland 15y ago
  Yes -- almost, but not quite. If you and I each create a branch off of a commit with gen #123, then, as I understand it, the subsequent commits in my branch would be #124, #125, etc., and your commits in your branch would also be #124, #125, etc. Contrast this with CVS, where I would have 1.124.1.1, 1.124.1.2, erc., and you would have 1.124.2.1, 1.124.2.2, or with Subversion, where I might get revisions 125, 128, and 129, while the server gave your commits #124, 127 and 130, and someone else, on a totally different part of the project got #126. As long as development proceeds linearly, on a single branch, then yeah, it's about the save as revision numbers in a centralized RCS -- once you start branching and merging, though, it represents a different concept entirely.

nplusone 15y ago

Change last name to 'Torvalds' (edit: name in title changed)

mscarborough 15y ago

I don't generally come across Linus' dev threads, but it's usually in the context of some linkbaity 'watch Linus smack this dude down' or something of that nature. This reads like a really productive thread from my limited understanding of git internals. It's pretty cool how much good engineering thought is going into this proposal. Maybe that's why git rocks so hard.

jacknagel 15y ago
Minor smackdown from this thread here: http://article.gmane.org/gmane.comp.version-control.git/177186 http://article.gmane.org/gmane.comp.version-control.git/1771...

Peaker 15y ago

Why call it a "generation number" and not "depth"?

rs 15y ago
Think they're using "generation" here in the context of number of parents (yes, "depth" would work fine as well, but is a more general term)
- pyre 15y ago
  > number of parents s/parents/ancestors/ But that statement only holds up on branches without any merge commits. Because the actual algorithm does not just total up the number of ancestors.
caf 15y ago
Perhaps because "Generation" continues the Parent/Child allegorical language.
Canopy 15y ago
"Depth" would (at least for me) evoke the shortest path to a commit. The generation number is the longest path.
beza1e1 15y ago
Since gitk and others put new commits on top, i'd propose "height" instead of "depth" ;)

derrickpetzold 15y ago

I was wondering how they got along without generation numbers for so long. It was by comparing timestamps and those are unreliable because systems can be misconfigured. How they are going to handle legacy repos with that problem I still don't get. I am guessing that history is f'd.

mdwrigh2 15y ago
New versions of git will actually go back and generate this information for old commits. This will lead to git being slightly slower when in old repositories until all the commits contain the generation information, but that should happen fairly quickly.
- derrickpetzold 15y ago
  I was talking about the case where the timestamps are off. I don't think there is any way to fix that.
  - ajuc 15y ago
    You just go the whole way up to the root node counting parents (taking max length when there are many routes), no problem with amiguity. The problem is - it's slow.
- iclelland 15y ago
  Not necessarily "all the commits", as I understand it (there's some debate in the thread, so I could be wrong) As long as at least one commit in each merged branch has a generation stored, it's simple to compute without going all the way back to all the roots.

rlpb 15y ago

What I like about git is that it stores only the minimum amount of information, and this makes it easy to explain. A commit hash is a hash of canonical information, not of derived information. It seems really ugly to store derived information in a commit (specifically, that the hash would be altered by it). It seems that Jeff has said the same thing, but Linus disagrees. Vocally. http://www.spinics.net/lists/git/msg161336.html http://www.spinics.net/lists/git/msg161336.html

derrickpetzold 15y ago
>It seems really ugly to store derived information in a commit I don't understand how generation numbers are derived information. They are used to find the position of the commit in relation to another. That makes them information that is essential to the commit. The problem was to get around them not being there timestamps were compared and that is not reliable for obvious reasons. So I really don't understand why any one would complain about this.
- iclelland 15y ago
  They're derived. You can tell that they're derived information by the fact that you can compute them for old commits, long after commit time, which is exactly what part of this proposal is to do. You can derive them simply by counting the maximum number of steps between a commit and any of its roots. The essential information isn't the generation numbers; it's the structure of the commit history -- the actual chains of commits, with all of the branches and merges. Generation numbers are just an artifact of counting. On the other hand, this information is very handy, once you have it, for certain algorithms, and it could be expensive to re-compute all the time, which is why the proposal is to generate and store them explicitly. (This is also the reason that timestamps have been used before, even if they were a bit of a hack -- they're readily available, and way faster than recomputing generation numbers all the time)
ryannielsen 15y ago
From my understanding, they're essentially adding this as an additional bit of information that's minimally required. The currently used timestamps are error prone and thus will be replaced by generation numbers which are more robust. They're still adhering to the principle of only storing the minimum amount of information, they're just adding generation numbers to that set. In fact, you could make the argument that timestamps are the derived information that git has been storing all along while generation numbers are the canonical information which should have been stored from the beginning. Generation numbers are a result of the state of the tree, while timestamps are derived from the ambient (and potentially incorrect!) environment from which the commit was made.

cypherpunks01 15y ago

What operations would be sped up by having generation numbers? I see Jeff King's message that they would make certain bounding traversals faster, but when do bounding traversals need to be computed when I'm using git day-to-day?

Rauchg 15y ago
It's also about making git not error-prone, which the current timestamp approach seems to do.

gregschlom 15y ago

Ah! I knew I was going to stumble upon Linus' signature "that's total and utter bullshit" somewhere: http://www.spinics.net/lists/git/msg161348.html http://www.spinics.net/lists/git/msg161348.html

pyre 15y ago

I like the suggestion of storing the generation numbers in the pack index. When you generate a pack you're already parsing the entire tree. That makes more sense than requiring all future git objects to have 'generation numbers' jammed into them. Especially because it introduces an incompatibility with current git objects, which it would probably be best to avoid.