{"thread":{"id":"27819","subject":"[PATCH] Add a 'generation' number to commits","startedAt":"2011-07-14T18:34:09Z","lastAt":"2011-07-16T00:36:24Z","messageCount":4,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"171355","messageId":"alpine.LFD.2.02.1107141126300.4159@i5.linux-foundation.org","threadId":"27819","inReplyTo":null,"subject":"[PATCH] Add a 'generation' number to commits","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-07-14T18:34:09Z","receivedAt":"2011-07-14T18:34:09Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nDate: Thu, 14 Jul 2011 11:09:46 -0700\nSubject: [PATCH] Add a 'generation' number to commits\n\nIt turns out that it's ok with git-fsck, and it's really not that\ncomplicated.\n\nWe unconditionally add the generation number to new commits, but we\ndon't require it in old ones.  Even if mix old and new versions of git,\nonce you have the occasional new user, it's all good: there will be\ngeneration numbers every once in a while, which means that computing new\nones will get cheaper (it's expensive to compute the generation number\nfor a deep tree that doesn't currently have any).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nComments? This is pretty simplistic, and yes, it's slow. On the kernel, it \nnow takes a few seconds to generate a new commit when there are no \ngeneration numbers - and that's on a fast machine.\n\nBut if I as a maintainer start using this, even if nobody else does, my \nmerges and my releases will start having generation numbers in the \ncommits, and once people start using those as the bases for their \ndevelopment, the \"generate the numbers\" cost will quickly start going \ndown. It will always exist for old commits, but those get progressively \nless relevant as time goes by, and soon enough all merging will be based \non stuff that has generation numbers somewhere reasonably recent.\n\nAnd the thing is, we don't actually have to generate the generation \nnumbers very often. New commits, yes (but if you have a series of new \ncommits due to something like quilt import usage, it's only the first one \nthat ends up having that cost). But for the \"might this be a merge base\", \nwe could easily decide to never do any dynamic generation, and only say \nthat \"IF we have pre-generated generation numbers, then we'll use them to \nsay \"this cannot possibly be an ancestor, because it has a bigger \ngeneration number\".\n\nSo we'd not see the advantages immediately, but the downsides would be \npretty small too. And the upside is that eventually new commits _will_ \nhave those generation numbers that we should have added to git originally.\n\n commit.c |   50 ++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h |    1 +\n 2 files changed, 51 insertions(+), 0 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex ac337c7d7dc1..6a6b9978f252 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -89,6 +89,28 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)\n \treturn strtoul(dateptr, NULL, 10);\n }\n \n+static long parse_commit_generation(const char *author, const char *tail)\n+{\n+\tconst char *p = author;\n+\twhile (p + 13 < tail) {\n+\t\t/* Empty line before commit message? */\n+\t\tif (*p == '\\n')\n+\t\t\tbreak;\n+\t\tif (!memcmp(p, \"generation \", 11)) {\n+\t\t\tlong value;\n+\t\t\tchar *end;\n+\n+\t\t\tvalue = strtoul(p+11, &end, 10);\n+\t\t\tif (!value || *end != '\\n')\n+\t\t\t\tbreak;\n+\t\t\treturn value;\n+\t\t}\n+\t\twhile (p < tail && *p++ != '\\n')\n+\t\t\t/* nothing */;\n+\t}\n+\treturn -1;\n+}\n+\n static struct commit_graft **commit_graft;\n static int commit_graft_alloc, commit_graft_nr;\n \n@@ -296,6 +318,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \t\t}\n \t}\n \titem->date = parse_commit_date(bufptr, tail);\n+\titem->generation = parse_commit_generation(bufptr, tail);\n \n \treturn 0;\n }\n@@ -824,6 +847,26 @@ struct commit_list *reduce_heads(struct commit_list *heads)\n \treturn result;\n }\n \n+static long commit_generation(struct commit *commit)\n+{\n+\tstruct commit_list *parents;\n+\tunsigned long max = 0;\n+\n+\tif (parse_commit(commit))\n+\t\treturn -1;\n+\tif (commit->generation >= 0)\n+\t\treturn commit->generation;\n+\tparents = commit->parents;\n+\twhile (parents) {\n+\t\tlong gen = commit_generation(parents->item);\n+\t\tif (gen >= max)\n+\t\t\tmax = gen+1;\n+\t\tparents = parents->next;\n+\t}\n+\tcommit->generation = max;\n+\treturn max;\n+}\n+\n static const char commit_utf8_warn[] =\n \"Warning: commit message does not conform to UTF-8.\\n\"\n \"You may want to amend it after fixing the message, or set the config\\n\"\n@@ -836,6 +879,7 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tint result;\n \tint encoding_is_utf8;\n \tstruct strbuf buffer;\n+\tunsigned long generation = 0;\n \n \tassert_sha1_type(tree, OBJ_TREE);\n \n@@ -851,9 +895,13 @@ int commit_tree(const char *msg, unsigned char *tree,\n \t * if everything else stays the same.\n \t */\n \twhile (parents) {\n+\t\tlong parent_gen;\n \t\tstruct commit_list *next = parents->next;\n \t\tstrbuf_addf(&buffer, \"parent %s\\n\",\n \t\t\tsha1_to_hex(parents->item->object.sha1));\n+\t\tparent_gen = commit_generation(parents->item);\n+\t\tif (parent_gen >= generation)\n+\t\t\tgeneration = parent_gen+1;\n \t\tfree(parents);\n \t\tparents = next;\n \t}\n@@ -865,6 +913,8 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tstrbuf_addf(&buffer, \"committer %s\\n\", git_committer_info(IDENT_ERROR_ON_NO_NAME));\n \tif (!encoding_is_utf8)\n \t\tstrbuf_addf(&buffer, \"encoding %s\\n\", git_commit_encoding);\n+\tif (generation)\n+\t\tstrbuf_addf(&buffer, \"generation %lu\\n\", generation);\n \tstrbuf_addch(&buffer, '\\n');\n \n \t/* And add the comment */\ndiff --git a/commit.h b/commit.h\nindex a2d571b97410..fd36274a2b0a 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -16,6 +16,7 @@ struct commit {\n \tvoid *util;\n \tunsigned int indegree;\n \tunsigned long date;\n+\tlong generation;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n \tchar *buffer;\n-- \n1.7.6.1.g7f306\n"},{"id":"171426","messageId":"7v8vrz1g02.fsf@alter.siamese.dyndns.org","threadId":"27819","inReplyTo":"alpine.LFD.2.02.1107141126300.4159@i5.linux-foundation.org","subject":"Re: [PATCH] Add a 'generation' number to commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-15T19:49:17Z","receivedAt":"2011-07-15T19:49:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"> Comments? This is pretty simplistic, and yes, it's slow. On the kernel, it \n> now takes a few seconds to generate a new commit when there are no \n> generation numbers - and that's on a fast machine.\n\nI agree this is the way to go if we _were_ to use generation number\nassociated with commit objects in the longer term, and if the SLOP\nlogic in still_interesting() in revision.c:\n\n (1) can gracefully fall back to the date based heuristics for older\n     commits without the header; and\n\n (2) can take advantage of the generation numbers in more recent commit.\n\nIf we cannot do (1), we could augment this with Peff's generation number\ncache. I suspect (1) is doable and in that case we do not have to have\n(and we may be better off without) the on-disk cache that could go stale,\nbut nobody so far has shown that yet, so...\n\nAs I mentioned in a review comment of the actual patch, I however am not\nconvinced that generation number is a better substitute for the timestamp\nin the context of \"tag --contains\" optimization.\n"},{"id":"171450","messageId":"CA+55aFw2_n2NkYpm9c1JiKaX_H4W89Ridq4qzBqyamuxpODejA@mail.gmail.com","threadId":"27819","inReplyTo":"7v8vrz1g02.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Add a 'generation' number to commits","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-07-15T23:58:36Z","receivedAt":"2011-07-15T23:58:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, Jul 15, 2011 at 12:49 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> I agree this is the way to go if we _were_ to use generation number\n> associated with commit objects in the longer term,\n\nI have to say, if the main issue was \"git tag/branch --contains\", and\nif the time-based slop approach of the patch I sent out is acceptable,\nI think that we can continue to ignore generation numbers.\n\n                            Linus\n"},{"id":"171451","messageId":"7vvcv3ysc7.fsf@alter.siamese.dyndns.org","threadId":"27819","inReplyTo":"CA+55aFw2_n2NkYpm9c1JiKaX_H4W89Ridq4qzBqyamuxpODejA@mail.gmail.com","subject":"Re: [PATCH] Add a 'generation' number to commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-16T00:36:24Z","receivedAt":"2011-07-16T00:36:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Fri, Jul 15, 2011 at 12:49 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>>\n>> I agree this is the way to go if we _were_ to use generation number\n>> associated with commit objects in the longer term,\n>\n> I have to say, if the main issue was \"git tag/branch --contains\", and\n> if the time-based slop approach of the patch I sent out is acceptable,\n> I think that we can continue to ignore generation numbers.\n\nI think we are in agreement that \"--contains\" can be sped up without\ngeneration numbers.\n\nAs I mentioned elsewhere, rev-list SLOP and merge-base traversal have\ndifferent performance characteristics and requirements from \"--contains\"\n(for one thing, they cannot say \"the commit tagged with v2.6.13 is too old\nthat there is no way this commit made three days ago is contained in it\"\nto optimize the traversal). And I agree that if we had generation header\nin commit in May 2005, optimizing these traversals properly would have\nbeen much cleaner, and it may still be worth doing it.\n"}]}