{"thread":{"id":"33799","subject":"[PATCH] patch-ids.c: cache patch IDs in a notes tree","startedAt":"2013-05-11T19:54:19Z","lastAt":"2013-05-13T15:52:41Z","messageCount":18,"participants":["John Keeping","Linus Torvalds","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"217038","messageId":"9d9e56d323b40fe9ea2a6484e35f0afcd3a3a85b.1368301939.git.john@keeping.me.uk","threadId":"33799","inReplyTo":null,"subject":"[PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-11T19:54:19Z","receivedAt":"2013-05-11T19:54:19Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"This adds a new configuration variable \"patchid.cacheRef\" which controls\nwhether (and where) patch IDs will be cached in a notes tree.\n\nCaching patch IDs in this way results in a performance improvement in\nevery case I have tried, for example when comparing the git-gui tree to\ngit.git (where git-gui has been merged into git.git but most git.git\ncommits do not appear in git-gui):\n\nWithout patch ID caching:\n$ time git log --cherry master...git-gui/master >/dev/null\nreal    0m32.981s\nuser    0m32.364s\nsys     0m0.621s\n\nPrime the cache:\n$ time git -c patchid.cacheref=patchids log --cherry \\\n\tmaster...git-gui/master >/dev/null\nreal    0m33.860s\nuser    0m32.832s\nsys     0m0.986s\n\nWith all patch IDs cached:\n$ time git -c patchid.cacheref=patchids log --cherry \\\n\tmaster...git-gui/master >/dev/null\nreal    0m1.041s\nuser    0m0.679s\nsys     0m0.363s\n\nSigned-off-by: John Keeping <john@keeping.me.uk>\n---\nThis is another approach to fixing the \"log --cherry\" takes a long time\nissue I encountered comparing commits built on git-gui to those in\ngit.git [1][2].\n\nI think this is a useful feature even outside that use case.  I measured\na small improvement (when the cache is primed) even comparing two\nbranches with 1 and 2 different commits respectively.\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/223959\n[2] http://article.gmane.org/gmane.comp.version-control.git/223956\n\n Documentation/config.txt             |  7 +++\n patch-ids.c                          | 91 +++++++++++++++++++++++++++++++++++-\n patch-ids.h                          |  1 +\n t/t6007-rev-list-cherry-pick-file.sh | 16 +++++++\n 4 files changed, 114 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 6e53fc5..e36585c 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -1798,6 +1798,13 @@ pager.<cmd>::\n \tprecedence over this option.  To disable pagination for all\n \tcommands, set `core.pager` or `GIT_PAGER` to `cat`.\n \n+patchid.cacheRef::\n+\tThe name of a notes ref in which to store patch IDs for commits.\n+\tThe ref is taken to be in `refs/notes/` if it is not qualified.\n++\n+Note that the patch ID notes are never pruned automatically, so you may\n+wish to periodically run `git notes --ref <ref> prune` against this ref.\n+\n pretty.<name>::\n \tAlias for a --pretty= format string, as specified in\n \tlinkgit:git-log[1]. Any aliases defined here can be used just\ndiff --git a/patch-ids.c b/patch-ids.c\nindex bc8a28f..cb05eec 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -1,6 +1,9 @@\n #include \"cache.h\"\n+#include \"blob.h\"\n #include \"diff.h\"\n #include \"commit.h\"\n+#include \"notes.h\"\n+#include \"refs.h\"\n #include \"sha1-lookup.h\"\n #include \"patch-ids.h\"\n \n@@ -34,12 +37,38 @@ struct patch_id_bucket {\n \tstruct patch_id bucket[BUCKET_SIZE];\n };\n \n+static int patch_id_config(const char *var, const char *value, void *cb)\n+{\n+\tconst char **cacheref = cb;\n+\n+\tif (!strcmp(var, \"patchid.cacheref\"))\n+\t\treturn git_config_string(cacheref, var, value);\n+\n+\treturn 0;\n+}\n+\n int init_patch_ids(struct patch_ids *ids)\n {\n+\tchar *cacheref = NULL;\n+\n \tmemset(ids, 0, sizeof(*ids));\n \tdiff_setup(&ids->diffopts);\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n+\n+\tgit_config(patch_id_config, &cacheref);\n+\tif (cacheref) {\n+\t\tstruct strbuf sb = STRBUF_INIT;\n+\t\tstrbuf_addstr(&sb, cacheref);\n+\t\texpand_notes_ref(&sb);\n+\n+\t\tids->cache = xcalloc(1, sizeof(*ids->cache));\n+\t\tinit_notes(ids->cache, sb.buf, combine_notes_overwrite, 0);\n+\n+\t\tstrbuf_release(&sb);\n+\t\tfree(cacheref);\n+\t}\n+\n \treturn 0;\n }\n \n@@ -52,9 +81,67 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\tif (ids->cache) {\n+\t\tunsigned char notes_sha1[20];\n+\t\tif (write_notes_tree(ids->cache, notes_sha1) ||\n+\t\t    update_ref(\"patch-id: update cache\", ids->cache->ref,\n+\t\t\t\tnotes_sha1, NULL, 0, QUIET_ON_ERR))\n+\t\t\terror(_(\"failed to write patch ID cache\"));\n+\n+\t\tfree_notes(ids->cache);\n+\t\tids->cache = NULL;\n+\t}\n+\n \treturn 0;\n }\n \n+static int load_cached_patch_id(struct commit *commit,\n+\t\tstruct notes_tree *cache, unsigned char *sha1)\n+{\n+\tconst unsigned char *note_sha1;\n+\tchar *note;\n+\tenum object_type type;\n+\tunsigned long notelen;\n+\tint result = 1;\n+\n+\tif (!cache)\n+\t\treturn 1;\n+\n+\tnote_sha1 = get_note(cache, commit->object.sha1);\n+\tif (!note_sha1)\n+\t\treturn 1;\n+\n+\tif (!(note = read_sha1_file(note_sha1, &type, &notelen)) || !notelen ||\n+\t\t\ttype != OBJ_BLOB)\n+\t\tgoto out;\n+\n+\tif (get_sha1_hex(note, sha1))\n+\t\tgoto out;\n+\n+\tresult = 0;\n+out:\n+\tfree(note);\n+\treturn result;\n+}\n+\n+static void save_cached_patch_id(struct commit *commit,\n+\t\tstruct notes_tree *cache, unsigned char *sha1)\n+{\n+\tunsigned char note_sha1[20];\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tif (!cache)\n+\t\treturn;\n+\n+\tstrbuf_addstr(&sb, sha1_to_hex(sha1));\n+\tstrbuf_addch(&sb, '\\n');\n+\tif (write_sha1_file(sb.buf, sb.len, blob_type, note_sha1) ||\n+\t    add_note(cache, commit->object.sha1, note_sha1, NULL))\n+\t\terror(_(\"unable to save patch ID in cache\"));\n+\n+\tstrbuf_release(&sb);\n+}\n+\n static struct patch_id *add_commit(struct commit *commit,\n \t\t\t\t   struct patch_ids *ids,\n \t\t\t\t   int no_add)\n@@ -64,11 +151,13 @@ static struct patch_id *add_commit(struct commit *commit,\n \tunsigned char sha1[20];\n \tint pos;\n \n-\tif (commit_patch_id(commit, &ids->diffopts, sha1))\n+\tif (load_cached_patch_id(commit, ids->cache, sha1) &&\n+\t    commit_patch_id(commit, &ids->diffopts, sha1))\n \t\treturn NULL;\n \tpos = patch_pos(ids->table, ids->nr, sha1);\n \tif (0 <= pos)\n \t\treturn ids->table[pos];\n+\tsave_cached_patch_id(commit, ids->cache, sha1);\n \tif (no_add)\n \t\treturn NULL;\n \ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..cffb0eb 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -8,6 +8,7 @@ struct patch_id {\n \n struct patch_ids {\n \tstruct diff_options diffopts;\n+\tstruct notes_tree *cache;\n \tint nr, alloc;\n \tstruct patch_id **table;\n \tstruct patch_id_bucket *patches;\ndiff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\nindex 28d4f6b..1b112c3 100755\n--- a/t/t6007-rev-list-cherry-pick-file.sh\n+++ b/t/t6007-rev-list-cherry-pick-file.sh\n@@ -207,4 +207,20 @@ test_expect_success '--count --left-right' '\n \ttest_cmp expect actual\n '\n \n+cat >expect <<EOF\n+1\t1\t2\n+EOF\n+\n+test_expect_success 'rev-list --cherry-mark caches patch ids' '\n+\ttest_config patchid.cacheref patchids &&\n+\tgit rev-list --cherry-mark --left-right --count F...E -- bar >actual &&\n+\ttest_cmp expect actual &&\n+\tgit notes --ref patchids show master >cached_master &&\n+\tgit log -p -1 master | git patch-id | sed -e \"s/ .*//\" >patch-id_master &&\n+\ttest_cmp patch-id_master cached_master &&\n+\t# Get the patch IDs again, now they should be cached\n+\tgit rev-list --cherry-mark --left-right --count F...E -- bar >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n1.8.3.rc1.289.gcb3647f\n"},{"id":"217043","messageId":"CA+55aFyn0+Q4CA6yQZipaCRB0w9cW4YpuL3XuxU2JR5QPp98XQ@mail.gmail.com","threadId":"33799","inReplyTo":"9d9e56d323b40fe9ea2a6484e35f0afcd3a3a85b.1368301939.git.john@keeping.me.uk","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2013-05-11T21:10:01Z","receivedAt":"2013-05-11T21:10:01Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Sat, May 11, 2013 at 12:54 PM, John Keeping <john@keeping.me.uk> wrote:\n> This adds a new configuration variable \"patchid.cacheRef\" which controls\n> whether (and where) patch IDs will be cached in a notes tree.\n\nPatch ID's aren't stable wrt different diff options, so I think this\nis potentially a very bad idea.\n\n           Linus\n"},{"id":"217046","messageId":"20130511214900.GF2299@serenity.lan","threadId":"33799","inReplyTo":"CA+55aFyn0+Q4CA6yQZipaCRB0w9cW4YpuL3XuxU2JR5QPp98XQ@mail.gmail.com","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-11T21:49:00Z","receivedAt":"2013-05-11T21:49:00Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sat, May 11, 2013 at 02:10:01PM -0700, Linus Torvalds wrote:\n> On Sat, May 11, 2013 at 12:54 PM, John Keeping <john@keeping.me.uk> wrote:\n> > This adds a new configuration variable \"patchid.cacheRef\" which controls\n> > whether (and where) patch IDs will be cached in a notes tree.\n> \n> Patch ID's aren't stable wrt different diff options, so I think this\n> is potentially a very bad idea.\n\nHmm... I hadn't realised that.  Looking a bit closer, it looks like\ninit_patch_ids sets up its own diffopts so its not affected by the\ncommand line (except for pathspecs which would be easy to check for).\nOf course that still means it can be affected by settings in the user's\nconfiguration.\n\nIt's a pity that this can't be done since it gives a significant\nperformance improvement for some tasks that I perform relatively\nfrequently.  Is there a reason patch IDs couldn't be generated using\nfixed diff options?  Since there's no way to control it from the command\nline it seems surprising that the results of \"log --cherry\" might be\ndifferent based on what's in your config.\n\nThat could go either way I suppose - is it useful to be able to change\npatch IDs based on command line arguments or is it wrong that as we add\npersistent diff settings to the configuration we've been silently\nchanging the behaviour of \"git patch-id\" and \"git cherry\".\n"},{"id":"217050","messageId":"CA+55aFzinmXA2HtA3hmN1VVOcLPWedfqJRws0RJMEc1By1VLLg@mail.gmail.com","threadId":"33799","inReplyTo":"20130511214900.GF2299@serenity.lan","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2013-05-11T22:41:35Z","receivedAt":"2013-05-11T22:41:35Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Sat, May 11, 2013 at 2:49 PM, John Keeping <john@keeping.me.uk> wrote:\n>\n> Hmm... I hadn't realised that.  Looking a bit closer, it looks like\n> init_patch_ids sets up its own diffopts so its not affected by the\n> command line (except for pathspecs which would be easy to check for).\n> Of course that still means it can be affected by settings in the user's\n> configuration.\n\n.. and in the actual diff algorithm.\n\nThe thing is - patches ARE NOT STABLE. There are many valid ways to\nget a patch from one version to another, and even without command line\nchanges, we've had different versions of git generating different\npatches. There are heuristics in xdiff to avoid some nasty \"use up\ntons of CPU-time\" things that have been tweaked over time. And even\nfor simple cases there are ambiguous ways to describe the patch.\n\nNow, maybe we don't care, because in practice, most of the time this\njust doesn't much matter. And anybody who uses patch-ID's had better\nnot rely on them being guaranteed to be unique anyway, so it's more of\na \"if the patch ID is the same, it's almost guaranteed to be the same\npatch\", but that's a big \"almost\". And no, it's not some theoretical\n\"SHA1 collisions are very unlikely\" kind of thing, it's a \"the patch\nID actually ignores a lot of data in order to give the same ID even if\nlins have been added above it, and the patch is at different line\nnumbers etc\".\n\nSo maybe it doesn't matter. But at the same time, I really think\ncaching patch ID's should be something people should be aware of is\nfundamentally wrong, even if it might work.\n\nAnd quite frankly, if you do rebases etc so much that you think patch\nID's are so important that they need to be cached, you may be doing\nodd/wrong things.\n\n             Linus\n"},{"id":"217053","messageId":"alpine.DEB.1.00.1305111846160.8213@s15462909.onlinehome-server.info","threadId":"33799","inReplyTo":"CA+55aFzinmXA2HtA3hmN1VVOcLPWedfqJRws0RJMEc1By1VLLg@mail.gmail.com","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2013-05-11T23:57:02Z","receivedAt":"2013-05-11T23:57:02Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi John & Linus,\n\nOn Sat, 11 May 2013, Linus Torvalds wrote:\n\n> [...] I really think caching patch ID's should be something people\n> should be aware of is fundamentally wrong, even if it might work.\n\nGiven the incredible performance win, I would say it is still worth\nlooking into.\n\nIf you store also a hash of Git version and diff options (may even be the\nhash of the raw bytes of the diff options if you do not plan to share the\nref between machines) with the patch ID, you can make it safe.\n\nThat hash would be generated at patch_id init time and\nload_cached_patch_id() would check this hash in addition to the return\nvalue of get_sha1() (and ignore the note if the version/diff options\ndiffer).\n\nIf you are following git.git slavishly, maybe hashing just the major/minor\nGit version would be in order to avoid frequent regeneration of identical\npatch IDs.\n\n> And quite frankly, if you do rebases etc so much that you think patch\n> ID's are so important that they need to be cached, you may be doing\n> odd/wrong things.\n\nAFAICT John actually gave a very valid scenario that validates his use\ncase: git-gui patches are best tested in the git.git scenario but have to\nbe contributed via git-gui.git. It's not John's fault that this typically\nrequires a lot of rebasing between vastly divergent histories.\n\nJohn, do you think you can incorporate that \"finger-print\" of the patch ID\ngeneration and store it in the same note?\n\nCiao,\nJohannes\n"},{"id":"217055","messageId":"7v1u9cx5pf.fsf@alter.siamese.dyndns.org","threadId":"33799","inReplyTo":"CA+55aFzinmXA2HtA3hmN1VVOcLPWedfqJRws0RJMEc1By1VLLg@mail.gmail.com","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-12T03:00:44Z","receivedAt":"2013-05-12T03:00:44Z","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 Sat, May 11, 2013 at 2:49 PM, John Keeping <john@keeping.me.uk> wrote:\n>>\n>> Hmm... I hadn't realised that.  Looking a bit closer, it looks like\n>> init_patch_ids sets up its own diffopts so its not affected by the\n>> command line (except for pathspecs which would be easy to check for).\n>> Of course that still means it can be affected by settings in the user's\n>> configuration.\n>\n> .. and in the actual diff algorithm.\n\nAs to the \"objection\" side of the argument, I already said\nessentially the same thing several months ago:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/202654/focus=202898\n\nand do not have much to add [*1*].\n\nHowever.\n\nThe use of patch-id in cherry and rebase is to facilitate avoiding\nto replay commits that are obviously identical to the ones you have\nin your history.  The cached patch id for an existing old commit may\ndiffer from a patch id you freshly compute for a new commit you are\ntrying to see if it truly new, even though they may represent the\nsame change.  So we may incorrectly think such a new commit is not\nyet in your history and attempt to replay it.\n\nBut it is not a big problem.  Either 3-way merge notices that there\nis nothing new, or you get a conflict and have chance to inspect\nwhat is going on.\n\nA conceptually much larger and more problematic issue is that we may\ndiscard a truly new change that you still need as an old one you\nalready have due to a hash collision and discard it.  Because the\nhash space of SHA-1 is so large, however, it is not a problem in\npractice, and more importantly, that hash space is just as large as\nthe hash space used by Git to reduce a patch to a patch id, the\nfiltering done with patch-id in cherry and rebase _already_ have\nthat exact problem with or without this additional cache layer. A\nstale cache may make the possibility of lost change due to such a\nhash collision merely twice as likely.\n\n> ... it's a \"the patch ID actually ignores a lot of data in order\n> to give the same ID even if lins have been added above it, and the\n> patch is at different line numbers etc\".\n\nYes.\n\n> So maybe it doesn't matter. But at the same time, I really think\n> caching patch ID's should be something people should be aware of is\n> fundamentally wrong, even if it might work.\n\nI do not think it is \"caching patch ID\" that people should be aware\nof is fundamentally wrong.  What is fundamentally wrong, even if it\nmight work, is \"using patch ID\" itself.\n\n> And quite frankly, if you do rebases etc so much that you think patch\n> ID's are so important that they need to be cached, you may be doing\n> odd/wrong things.\n\nAnd that, too ;-)\n\n\n[Footnote]\n\n*1* For people listening from the sidelines, the fact that Git\nalgorithm can improve over time is a real issue, and and has caused\none issue that still hasn't been solved in the k.org upload process.\nSomebody who has a repository there could *theoretically*:\n\n - push her v1.1 release via Git (\"git push origin v1.1\");\n - create a tarball (\"git archive -o v1.1.tar v1.1\") and diff since the\n   last release (\"git diff v1.0 v1.1 >v1.0-v1.1.diff\") locally;\n - GPG sign them (\"gpg -b v1.1.tar\", \"gpg -b v1.0-v1.1.diff\"); and\n - upload only the signature files\n\nand have k.org create the tarballs and diff to save bandwidth of\nuploading logically derivable stuff over and over again.  But that\ncan be done only when output from \"git archive\" and \"git diff\" are\nstable, which is not the case.  We changed how extended header fields\nare used in the tar archive for a long pathname recently, and also\nwe changed use of XDF_NEED_MINIMAL a couple of years ago in \"git diff\";\nboth of these affect the output.\n"},{"id":"217060","messageId":"20130512085934.GG2299@serenity.lan","threadId":"33799","inReplyTo":"7v1u9cx5pf.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-12T08:59:34Z","receivedAt":"2013-05-12T08:59:34Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sat, May 11, 2013 at 08:00:44PM -0700, Junio C Hamano wrote:\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n> \n> > On Sat, May 11, 2013 at 2:49 PM, John Keeping <john@keeping.me.uk> wrote:\n> >>\n> >> Hmm... I hadn't realised that.  Looking a bit closer, it looks like\n> >> init_patch_ids sets up its own diffopts so its not affected by the\n> >> command line (except for pathspecs which would be easy to check for).\n> >> Of course that still means it can be affected by settings in the user's\n> >> configuration.\n> >\n> > .. and in the actual diff algorithm.\n> \n> As to the \"objection\" side of the argument, I already said\n> essentially the same thing several months ago:\n> \n>   http://thread.gmane.org/gmane.comp.version-control.git/202654/focus=202898\n> \n> and do not have much to add [*1*].\n> \n> However.\n> \n> The use of patch-id in cherry and rebase is to facilitate avoiding\n> to replay commits that are obviously identical to the ones you have\n> in your history.  The cached patch id for an existing old commit may\n> differ from a patch id you freshly compute for a new commit you are\n> trying to see if it truly new, even though they may represent the\n> same change.  So we may incorrectly think such a new commit is not\n> yet in your history and attempt to replay it.\n> \n> But it is not a big problem.  Either 3-way merge notices that there\n> is nothing new, or you get a conflict and have chance to inspect\n> what is going on.\n\nIt's not a problem here, but false negatives would be annoying if you're\nlooking at \"git log --cherry-mark\".\n\n> A conceptually much larger and more problematic issue is that we may\n> discard a truly new change that you still need as an old one you\n> already have due to a hash collision and discard it.  Because the\n> hash space of SHA-1 is so large, however, it is not a problem in\n> practice, and more importantly, that hash space is just as large as\n> the hash space used by Git to reduce a patch to a patch id, the\n> filtering done with patch-id in cherry and rebase _already_ have\n> that exact problem with or without this additional cache layer. A\n> stale cache may make the possibility of lost change due to such a\n> hash collision merely twice as likely.\n> \n> > ... it's a \"the patch ID actually ignores a lot of data in order\n> > to give the same ID even if lins have been added above it, and the\n> > patch is at different line numbers etc\".\n> \n> Yes.\n> \n> > So maybe it doesn't matter. But at the same time, I really think\n> > caching patch ID's should be something people should be aware of is\n> > fundamentally wrong, even if it might work.\n> \n> I do not think it is \"caching patch ID\" that people should be aware\n> of is fundamentally wrong.  What is fundamentally wrong, even if it\n> might work, is \"using patch ID\" itself.\n> \n> > And quite frankly, if you do rebases etc so much that you think patch\n> > ID's are so important that they need to be cached, you may be doing\n> > odd/wrong things.\n> \n> And that, too ;-)\n\nI've never noticed a problem with rebases, it's when I use \"git log\n--cherry master...\" to see if patches I've sent to a mailing list have\nbeen picked up.\n\nTo take Git as an example (albeit a bad one because \"What's Cooking\" is\na more useful way to track patch state here), if I compare this patch to\npu I have:\n\n\t$ git rev-list --left-right --count pu...\n\t234\t1\n\nand caching patch IDs takes that from ~0.6s to ~0.1s.  When doing that\nover several branches consecutively that makes a big difference to the\noverall runtime, especially because most of the commits of interest will\nbe cached during the first one.\n"},{"id":"217061","messageId":"20130512090850.GH2299@serenity.lan","threadId":"33799","inReplyTo":"alpine.DEB.1.00.1305111846160.8213@s15462909.onlinehome-server.info","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-12T09:08:51Z","receivedAt":"2013-05-12T09:08:51Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sat, May 11, 2013 at 06:57:02PM -0500, Johannes Schindelin wrote:\n> On Sat, 11 May 2013, Linus Torvalds wrote:\n> \n> > [...] I really think caching patch ID's should be something people\n> > should be aware of is fundamentally wrong, even if it might work.\n> \n> Given the incredible performance win, I would say it is still worth\n> looking into.\n> \n> If you store also a hash of Git version and diff options (may even be the\n> hash of the raw bytes of the diff options if you do not plan to share the\n> ref between machines) with the patch ID, you can make it safe.\n> \n> That hash would be generated at patch_id init time and\n> load_cached_patch_id() would check this hash in addition to the return\n> value of get_sha1() (and ignore the note if the version/diff options\n> differ).\n\nI was thinking about this overnight, glad to see someone else had the\nsame idea :-)\n\nIt's slightly annoying because the diff options can be customized after\nwe return from init_patch_ids() so we either need a new\nsetup_patch_ids() function to be run after init once diff options have\nbeen set or to set it lazily.  I'll try introducing a setup function.\n\n> If you are following git.git slavishly, maybe hashing just the major/minor\n> Git version would be in order to avoid frequent regeneration of identical\n> patch IDs.\n\nI think just storing the version is quite good here, and it avoids pain\nwhen a topic that affects patch IDs is working its way through pu and\nnext.\n\n> > And quite frankly, if you do rebases etc so much that you think patch\n> > ID's are so important that they need to be cached, you may be doing\n> > odd/wrong things.\n> \n> AFAICT John actually gave a very valid scenario that validates his use\n> case: git-gui patches are best tested in the git.git scenario but have to\n> be contributed via git-gui.git. It's not John's fault that this typically\n> requires a lot of rebasing between vastly divergent histories.\n\nActually, I don't think that use case is valid.  Because it's a subtree\nmerge I can be absolutely certain that nothing on the LHS of\nmaster...git-gui/master is patch identical to anything on the RHS since\nall the paths are different.  So doing \"git log --cherry-mark\" in that\ncase is completely useless.  I think my script should be able to learn\nthat, which gets rid of the really horrible case I was seeing, but it\nwould be nice to improve the \"fast enough\" cases as well if it can be\ndone without too much effort.\n"},{"id":"217066","messageId":"20130512114131.GI2299@serenity.lan","threadId":"33799","inReplyTo":"20130512090850.GH2299@serenity.lan","subject":"[RFC/PATCH v2] patch-ids: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-12T11:41:31Z","receivedAt":"2013-05-12T11:41:31Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"This adds a new configuration variable \"patchid.cacheRef\" which controls\nwhether (and where) patch IDs will be cached in a notes tree.  The cache\nincludes a hash of the diff options in place when the cache was\ngenerated as well as the version of Git that generated it.\n\nWhen the diff options hash changes we simply ignore that cache entry and\nreplace it with the new patch ID with the new diff options.  But if the\nGit version changes we throw away the entire cache tree on the\nassumption that the user is unlikely to be simply flipping between\ndifferent versions of Git.\n\nCaching patch IDs in this way results in a performance improvement in\nevery case I have tried, for example if I run a script which checks\nwhether any of six local branches have been picked up upstream I get the\nfollowing results:\n\nWithout patchid.cacheRef enabled:\n\n\t$ time git integration --status jk/pu >/dev/null\n\n\treal    0m4.295s\n\tuser    0m3.927s\n\tsys     0m0.270s\n\nWith patchid.cacheRef set but not yet initialised:\n\n\t$ time git integration --status jk/pu >/dev/null\n\n\treal    0m2.317s\n\tuser    0m2.036s\n\tsys     0m0.187s\n\nWith patchid.cacheRef and cache primed:\n\n\t$ time git integration --status jk/pu >/dev/null\n\n\treal    0m1.565s\n\tuser    0m1.310s\n\tsys     0m0.153s\n\nThe script basically does:\n\n\tgit log --cherry pu...<branch>\n\nfor each of six branches in turn (with some additional commands around\nthat which are now the bottleneck).\n\nSigned-off-by: John Keeping <john@keeping.me.uk>\n---\nOn Sun, May 12, 2013 at 10:08:51AM +0100, John Keeping wrote:\n> On Sat, May 11, 2013 at 06:57:02PM -0500, Johannes Schindelin wrote:\n> > On Sat, 11 May 2013, Linus Torvalds wrote:\n> > \n> > > [...] I really think caching patch ID's should be something people\n> > > should be aware of is fundamentally wrong, even if it might work.\n> > \n> > Given the incredible performance win, I would say it is still worth\n> > looking into.\n> > \n> > If you store also a hash of Git version and diff options (may even be the\n> > hash of the raw bytes of the diff options if you do not plan to share the\n> > ref between machines) with the patch ID, you can make it safe.\n> > \n> > That hash would be generated at patch_id init time and\n> > load_cached_patch_id() would check this hash in addition to the return\n> > value of get_sha1() (and ignore the note if the version/diff options\n> > differ).\n> \n> I was thinking about this overnight, glad to see someone else had the\n> same idea :-)\n> \n> It's slightly annoying because the diff options can be customized after\n> we return from init_patch_ids() so we either need a new\n> setup_patch_ids() function to be run after init once diff options have\n> been set or to set it lazily.  I'll try introducing a setup function.\n\nThis is what that looks like.  I think the way I'm hashing the diff\noptions is sensible but another pair of eyes would be useful there.\n\nA cache entry looks like this:\n\n\t9e99e9dbf5c6a717ac60f7ee425c53e87ffd821a\n\tdiffopts:f8ca35c3d9d57076338dff8abf91b07157bb6329\n\t1.8.3.rc1.45.gcb72da6.dirty\n\n Documentation/config.txt             |   7 ++\n builtin/log.c                        |   1 +\n patch-ids.c                          | 215 ++++++++++++++++++++++++++++++++++-\n patch-ids.h                          |   4 +\n revision.c                           |   1 +\n t/t6007-rev-list-cherry-pick-file.sh |  16 +++\n 6 files changed, 243 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 6e53fc5..e36585c 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -1798,6 +1798,13 @@ pager.<cmd>::\n \tprecedence over this option.  To disable pagination for all\n \tcommands, set `core.pager` or `GIT_PAGER` to `cat`.\n \n+patchid.cacheRef::\n+\tThe name of a notes ref in which to store patch IDs for commits.\n+\tThe ref is taken to be in `refs/notes/` if it is not qualified.\n++\n+Note that the patch ID notes are never pruned automatically, so you may\n+wish to periodically run `git notes --ref <ref> prune` against this ref.\n+\n pretty.<name>::\n \tAlias for a --pretty= format string, as specified in\n \tlinkgit:git-log[1]. Any aliases defined here can be used just\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 6e56a50..dd6c24d 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -758,6 +758,7 @@ static void get_patch_ids(struct rev_info *rev, struct patch_ids *ids)\n \t\tdie(_(\"Not a range.\"));\n \n \tinit_patch_ids(ids);\n+\tsetup_patch_ids(ids);\n \n \t/* given a range a..b get all patch ids for b..a */\n \tinit_revisions(&check_rev, rev->prefix);\ndiff --git a/patch-ids.c b/patch-ids.c\nindex bc8a28f..73b2aaf 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -1,8 +1,12 @@\n #include \"cache.h\"\n+#include \"blob.h\"\n #include \"diff.h\"\n #include \"commit.h\"\n+#include \"notes.h\"\n+#include \"refs.h\"\n #include \"sha1-lookup.h\"\n #include \"patch-ids.h\"\n+#include \"version.h\"\n \n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t    unsigned char *sha1)\n@@ -34,6 +38,16 @@ struct patch_id_bucket {\n \tstruct patch_id bucket[BUCKET_SIZE];\n };\n \n+static int patch_id_config(const char *var, const char *value, void *cb)\n+{\n+\tconst char **cacheref = cb;\n+\n+\tif (!strcmp(var, \"patchid.cacheref\"))\n+\t\treturn git_config_string(cacheref, var, value);\n+\n+\treturn 0;\n+}\n+\n int init_patch_ids(struct patch_ids *ids)\n {\n \tmemset(ids, 0, sizeof(*ids));\n@@ -43,6 +57,108 @@ int init_patch_ids(struct patch_ids *ids)\n \treturn 0;\n }\n \n+static void sha1_update_str(git_SHA_CTX *ctx, const char *s)\n+{\n+\tsize_t len = s ? strlen(s) + 1 : 0;\n+\tlong nl = htonl((long) len);\n+\tgit_SHA1_Update(ctx, &nl, sizeof(nl));\n+\tgit_SHA1_Update(ctx, s, len);\n+}\n+\n+static void sha1_update_int(git_SHA_CTX *ctx, int v)\n+{\n+\tlong nv = htonl((long) v);\n+\tgit_SHA1_Update(ctx, &nv, sizeof(nv));\n+}\n+\n+static void sha1_update_pathspec(git_SHA_CTX *ctx, struct pathspec *pathspec)\n+{\n+\tint i;\n+\t/*\n+\t * Pathspecs are uniquely identified by their number and match string\n+\t * providing that we take limit_pathspec_to_literal into account.\n+\t */\n+\tsha1_update_int(ctx, limit_pathspec_to_literal());\n+\tsha1_update_int(ctx, pathspec->nr);\n+\tfor (i = 0; i < pathspec->nr; i++)\n+\t\tsha1_update_str(ctx, pathspec->items[i].match);\n+}\n+\n+static void hash_diff_options(struct diff_options *options, unsigned char *sha1)\n+{\n+\tgit_SHA_CTX ctx;\n+\tgit_SHA1_Init(&ctx);\n+\n+\tsha1_update_str(&ctx, options->filter);\n+\t/* ignore options->orderfile (see setup_patch_ids) */\n+\tsha1_update_str(&ctx, options->pickaxe);\n+\tsha1_update_str(&ctx, options->single_follow);\n+\t/* a_prefix and b_prefix aren't used for patch IDs */\n+\n+\tsha1_update_int(&ctx, options->flags);\n+\t/* use_color isn't used for patch IDs */\n+\tsha1_update_int(&ctx, options->context);\n+\tsha1_update_int(&ctx, options->interhunkcontext);\n+\tsha1_update_int(&ctx, options->break_opt);\n+\tsha1_update_int(&ctx, options->detect_rename);\n+\tsha1_update_int(&ctx, options->irreversible_delete);\n+\tsha1_update_int(&ctx, options->skip_stat_unmatch);\n+\t/* line_termination isn't used for patch IDs */\n+\t/* output_format isn't used for patch IDs */\n+\tsha1_update_int(&ctx, options->pickaxe_opts);\n+\tsha1_update_int(&ctx, options->rename_score);\n+\tsha1_update_int(&ctx, options->rename_limit);\n+\t/* needed_rename_limit is set while diffing */\n+\t/* degraded_cc_to_c is set while diffing */\n+\t/* show_rename_progress isn't used for patch IDs */\n+\t/* dirstat_permille isn't used for patch IDs */\n+\t/* setup isn't used for patch IDs */\n+\t/* abbrev isn't used for patch IDs */\n+\t/* prefix and prefix_length aren't used for patch IDs */\n+\t/* stat_sep isn't used for patch IDs */\n+\tsha1_update_int(&ctx, options->xdl_opts);\n+\n+\t/* stat arguments aren't used for patch IDs */\n+\tsha1_update_str(&ctx, options->word_regex);\n+\tsha1_update_int(&ctx, options->word_diff);\n+\n+\tsha1_update_pathspec(&ctx, &options->pathspec);\n+\n+\tgit_SHA1_Final(sha1, &ctx);\n+}\n+\n+int setup_patch_ids(struct patch_ids *ids)\n+{\n+\tchar *cacheref = NULL;\n+\n+\t/*\n+\t * Make extra sure we aren't using an orderfile as it is unnecessary\n+\t * and will break caching.\n+\t */\n+\tids->diffopts.orderfile = NULL;\n+\n+\tgit_config(patch_id_config, &cacheref);\n+\tif (cacheref) {\n+\t\tunsigned char diffopts_raw_hash[20];\n+\t\tstruct strbuf sb = STRBUF_INIT;\n+\t\tstrbuf_addstr(&sb, cacheref);\n+\t\texpand_notes_ref(&sb);\n+\n+\t\tids->cache = xcalloc(1, sizeof(*ids->cache));\n+\t\tinit_notes(ids->cache, sb.buf, combine_notes_overwrite, 0);\n+\n+\t\thash_diff_options(&ids->diffopts, diffopts_raw_hash);\n+\t\tstrbuf_reset(&sb);\n+\t\tstrbuf_addf(&sb, \"diffopts:%s\\n\", sha1_to_hex(diffopts_raw_hash));\n+\t\tids->diffopts_hash_len = sb.len;\n+\t\tids->diffopts_hash = strbuf_detach(&sb, NULL);\n+\n+\t\tfree(cacheref);\n+\t}\n+\n+\treturn 0;\n+}\n+\n int free_patch_ids(struct patch_ids *ids)\n {\n \tstruct patch_id_bucket *next, *patches;\n@@ -52,9 +168,104 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\tif (ids->cache) {\n+\t\tunsigned char notes_sha1[20];\n+\t\tif (write_notes_tree(ids->cache, notes_sha1) ||\n+\t\t    update_ref(\"patch-id: update cache\", ids->cache->ref,\n+\t\t\t\tnotes_sha1, NULL, 0, QUIET_ON_ERR))\n+\t\t\terror(_(\"failed to write patch ID cache\"));\n+\n+\t\tfree_notes(ids->cache);\n+\t\tids->cache = NULL;\n+\n+\t\tfree(ids->diffopts_hash);\n+\t\tids->diffopts_hash = NULL;\n+\t}\n+\n \treturn 0;\n }\n \n+static int load_cached_patch_id(struct commit *commit,\n+\t\tstruct patch_ids *ids, unsigned char *sha1)\n+{\n+\tconst unsigned char *note_sha1;\n+\tchar *orig_note;\n+\tchar *note;\n+\tenum object_type type;\n+\tunsigned long notelen;\n+\tint result = 1;\n+\n+\tif (!ids->cache)\n+\t\treturn 1;\n+\n+\tnote_sha1 = get_note(ids->cache, commit->object.sha1);\n+\tif (!note_sha1)\n+\t\treturn 1;\n+\n+\tif (!(orig_note = read_sha1_file(note_sha1, &type, &notelen)) ||\n+\t\t\t!notelen || type != OBJ_BLOB)\n+\t\tgoto out;\n+\n+\tnote = orig_note;\n+\tif (get_sha1_hex(note, sha1))\n+\t\tgoto out;\n+\n+\t/* Advance past the patch ID */\n+\tnote += 41;\n+\t/* Was the cached patch ID generated with the same diffopts? */\n+\tif (strncmp(note, ids->diffopts_hash, ids->diffopts_hash_len)) {\n+\t\tgoto out;\n+\t}\n+\n+\tnote += ids->diffopts_hash_len;\n+\tif (note[strlen(note) - 1] == '\\n')\n+\t\tnote[strlen(note) - 1] = '\\0';\n+\tif (strcmp(note, git_version_string)) {\n+\t\tstruct notes_tree *new_cache;\n+\t\t/*\n+\t\t * If the Git version has changed, throw away the entire\n+\t\t * caching notes tree on the assumption that the user will\n+\t\t * not return to the previous version.  We can bail out of\n+\t\t * this function sooner next time round if we don't find a\n+\t\t * note for the commit at all.\n+\t\t */\n+\t\tnew_cache = xcalloc(1, sizeof(*new_cache));\n+\t\tinit_notes(new_cache, ids->cache->ref,\n+\t\t\tids->cache->combine_notes, NOTES_INIT_EMPTY);\n+\t\tfree_notes(ids->cache);\n+\t\tfree(ids->cache);\n+\t\tids->cache = new_cache;\n+\t\tgoto out;\n+\t}\n+\n+\tresult = 0;\n+out:\n+\tfree(orig_note);\n+\treturn result;\n+}\n+\n+static void save_cached_patch_id(struct commit *commit,\n+\t\tstruct patch_ids *ids, unsigned char *sha1)\n+{\n+\tunsigned char note_sha1[20];\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tif (!ids->cache)\n+\t\treturn;\n+\n+\tstrbuf_addstr(&sb, sha1_to_hex(sha1));\n+\tstrbuf_addch(&sb, '\\n');\n+\tstrbuf_add(&sb, ids->diffopts_hash, ids->diffopts_hash_len);\n+\tstrbuf_addstr(&sb, git_version_string);\n+\tstrbuf_addch(&sb, '\\n');\n+\n+\tif (write_sha1_file(sb.buf, sb.len, blob_type, note_sha1) ||\n+\t    add_note(ids->cache, commit->object.sha1, note_sha1, NULL))\n+\t\terror(_(\"unable to save patch ID in cache\"));\n+\n+\tstrbuf_release(&sb);\n+}\n+\n static struct patch_id *add_commit(struct commit *commit,\n \t\t\t\t   struct patch_ids *ids,\n \t\t\t\t   int no_add)\n@@ -64,11 +275,13 @@ static struct patch_id *add_commit(struct commit *commit,\n \tunsigned char sha1[20];\n \tint pos;\n \n-\tif (commit_patch_id(commit, &ids->diffopts, sha1))\n+\tif (load_cached_patch_id(commit, ids, sha1) &&\n+\t    commit_patch_id(commit, &ids->diffopts, sha1))\n \t\treturn NULL;\n \tpos = patch_pos(ids->table, ids->nr, sha1);\n \tif (0 <= pos)\n \t\treturn ids->table[pos];\n+\tsave_cached_patch_id(commit, ids, sha1);\n \tif (no_add)\n \t\treturn NULL;\n \ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..08d4dd3 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -8,12 +8,16 @@ struct patch_id {\n \n struct patch_ids {\n \tstruct diff_options diffopts;\n+\tstruct notes_tree *cache;\n+\tchar *diffopts_hash;\n+\tsize_t diffopts_hash_len;\n \tint nr, alloc;\n \tstruct patch_id **table;\n \tstruct patch_id_bucket *patches;\n };\n \n int init_patch_ids(struct patch_ids *);\n+int setup_patch_ids(struct patch_ids *);\n int free_patch_ids(struct patch_ids *);\n struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\n struct patch_id *has_commit_patch_id(struct commit *, struct patch_ids *);\ndiff --git a/revision.c b/revision.c\nindex a67b615..0de4168 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -632,6 +632,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \tleft_first = left_count < right_count;\n \tinit_patch_ids(&ids);\n \tids.diffopts.pathspec = revs->diffopt.pathspec;\n+\tsetup_patch_ids(&ids);\n \n \t/* Compute patch-ids for one side */\n \tfor (p = list; p; p = p->next) {\ndiff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\nindex 28d4f6b..378cf3e 100755\n--- a/t/t6007-rev-list-cherry-pick-file.sh\n+++ b/t/t6007-rev-list-cherry-pick-file.sh\n@@ -207,4 +207,20 @@ test_expect_success '--count --left-right' '\n \ttest_cmp expect actual\n '\n \n+cat >expect <<EOF\n+3\t2\t0\n+EOF\n+\n+test_expect_success 'rev-list --cherry-mark caches patch ids' '\n+\ttest_config patchid.cacheref patchids &&\n+\tgit rev-list --cherry-mark --left-right --count F...E >actual &&\n+\ttest_cmp expect actual &&\n+\tgit notes --ref patchids show master >cached_master &&\n+\tgit log -p -1 master | git patch-id | sed -e \"s/ .*//\" >patch-id_master &&\n+\ttest_cmp patch-id_master cached_master &&\n+\t# Get the patch IDs again, now they should be cached\n+\tgit rev-list --cherry-mark --left-right --count F...E >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n1.8.3.rc1.45.gcb72da6.dirty\n"},{"id":"217075","messageId":"20130512115743.GJ2299@serenity.lan","threadId":"33799","inReplyTo":"20130512114131.GI2299@serenity.lan","subject":"Re: [RFC/PATCH v2] patch-ids: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-12T11:57:43Z","receivedAt":"2013-05-12T11:57:43Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sun, May 12, 2013 at 12:41:31PM +0100, John Keeping wrote:\n> diff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\n> index 28d4f6b..378cf3e 100755\n> --- a/t/t6007-rev-list-cherry-pick-file.sh\n> +++ b/t/t6007-rev-list-cherry-pick-file.sh\n> @@ -207,4 +207,20 @@ test_expect_success '--count --left-right' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> +cat >expect <<EOF\n> +3\t2\t0\n> +EOF\n> +\n> +test_expect_success 'rev-list --cherry-mark caches patch ids' '\n> +\ttest_config patchid.cacheref patchids &&\n> +\tgit rev-list --cherry-mark --left-right --count F...E >actual &&\n> +\ttest_cmp expect actual &&\n> +\tgit notes --ref patchids show master >cached_master &&\n\nI forgot to update this test, it needs a \"| sed -e 1q\" in the middle of\nthis line to make sure that we're only checking the patch ID and not the\ndiffopts hash and Git version.\n\n> +\tgit log -p -1 master | git patch-id | sed -e \"s/ .*//\" >patch-id_master &&\n> +\ttest_cmp patch-id_master cached_master &&\n> +\t# Get the patch IDs again, now they should be cached\n> +\tgit rev-list --cherry-mark --left-right --count F...E >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n>  test_done\n"},{"id":"217096","messageId":"7v1u9bvo1m.fsf@alter.siamese.dyndns.org","threadId":"33799","inReplyTo":"20130512085934.GG2299@serenity.lan","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-12T22:19:49Z","receivedAt":"2013-05-12T22:19:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping <john@keeping.me.uk> writes:\n\n>> But it is not a big problem.  Either 3-way merge notices that there\n>> is nothing new, or you get a conflict and have chance to inspect\n>> what is going on.\n>\n> It's not a problem here, but false negatives would be annoying if you're\n> looking at \"git log --cherry-mark\".\n\nThe primary thing to notice is that it is not a new problem with or\nwithout the caching layer.  As Linus mentioned how patch-ids are\ncomputed by ignoring offsets and whitespaces, the filtering is done\nas a crude approximation and false negatives are part of design, so\nmaking the cache more complex by recording hash of the binary and/or\noptions used to compute misses the fundamental.\n"},{"id":"217134","messageId":"20130513075906.GP2299@serenity.lan","threadId":"33799","inReplyTo":"7v1u9bvo1m.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-13T07:59:07Z","receivedAt":"2013-05-13T07:59:07Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sun, May 12, 2013 at 03:19:49PM -0700, Junio C Hamano wrote:\n> John Keeping <john@keeping.me.uk> writes:\n> \n> >> But it is not a big problem.  Either 3-way merge notices that there\n> >> is nothing new, or you get a conflict and have chance to inspect\n> >> what is going on.\n> >\n> > It's not a problem here, but false negatives would be annoying if you're\n> > looking at \"git log --cherry-mark\".\n> \n> The primary thing to notice is that it is not a new problem with or\n> without the caching layer.  As Linus mentioned how patch-ids are\n> computed by ignoring offsets and whitespaces, the filtering is done\n> as a crude approximation and false negatives are part of design, so\n> making the cache more complex by recording hash of the binary and/or\n> options used to compute misses the fundamental.\n\nThe caching layer could also introduce false positives though, which is\nmore serious.  If you cache patch IDs with a pathspec restriction and\nthen run a command that uses the cache with no such restriction you\ncould hit a patch that is the same for those paths but also touches\nother paths that you don't want to ignore and mark it as patch identical\neven though it is not.\n\nAdding a hash of the diffopts fixes that.\n"},{"id":"217171","messageId":"7vzjvzoujq.fsf@alter.siamese.dyndns.org","threadId":"33799","inReplyTo":"20130513075906.GP2299@serenity.lan","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-13T13:53:29Z","receivedAt":"2013-05-13T13:53:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping <john@keeping.me.uk> writes:\n\n> The caching layer could also introduce false positives though, which is\n> more serious.  If you cache patch IDs with a pathspec restriction ...\n\nWhat?  What business does patch-id have with pathspec-limited diff\ngeneration?  You do not rebase or cherry-pick with pathspec, so\nunless you are populating the patch-id cache at a wrong point (like,\nsay whenevern \"git show $commit\" is run), I am not sure why pathspec\nlimit becomes even an issue.\n"},{"id":"217177","messageId":"20130513140243.GQ2299@serenity.lan","threadId":"33799","inReplyTo":"7vzjvzoujq.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-13T14:02:43Z","receivedAt":"2013-05-13T14:02:43Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Mon, May 13, 2013 at 06:53:29AM -0700, Junio C Hamano wrote:\n> John Keeping <john@keeping.me.uk> writes:\n> \n> > The caching layer could also introduce false positives though, which is\n> > more serious.  If you cache patch IDs with a pathspec restriction ...\n> \n> What?  What business does patch-id have with pathspec-limited diff\n> generation?  You do not rebase or cherry-pick with pathspec, so\n> unless you are populating the patch-id cache at a wrong point (like,\n> say whenevern \"git show $commit\" is run), I am not sure why pathspec\n> limit becomes even an issue.\n\nrevision.c::cherry_pick_list() sets the pathspec to what was specified\nin the revision options.  It's done that since commit 36d56de (Fix\n--cherry-pick with given paths, 2007-07-10) and t6007 tests that it\nworks.\n"},{"id":"217187","messageId":"7v38tros3y.fsf@alter.siamese.dyndns.org","threadId":"33799","inReplyTo":"20130513140243.GQ2299@serenity.lan","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-13T14:46:09Z","receivedAt":"2013-05-13T14:46:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping <john@keeping.me.uk> writes:\n\n> On Mon, May 13, 2013 at 06:53:29AM -0700, Junio C Hamano wrote:\n>> John Keeping <john@keeping.me.uk> writes:\n>> \n>> > The caching layer could also introduce false positives though, which is\n>> > more serious.  If you cache patch IDs with a pathspec restriction ...\n>> \n>> What?  What business does patch-id have with pathspec-limited diff\n>> generation?  You do not rebase or cherry-pick with pathspec, so\n>> unless you are populating the patch-id cache at a wrong point (like,\n>> say whenevern \"git show $commit\" is run), I am not sure why pathspec\n>> limit becomes even an issue.\n>\n> revision.c::cherry_pick_list() sets the pathspec to what was specified\n> in the revision options.  It's done that since commit 36d56de (Fix\n> --cherry-pick with given paths, 2007-07-10) and t6007 tests that it\n> works.\n\nThen the caching should be automatically turned off when pathspec is\ngiven.\n"},{"id":"217193","messageId":"20130513145948.GR2299@serenity.lan","threadId":"33799","inReplyTo":"7v38tros3y.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-13T14:59:48Z","receivedAt":"2013-05-13T14:59:48Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Mon, May 13, 2013 at 07:46:09AM -0700, Junio C Hamano wrote:\n> John Keeping <john@keeping.me.uk> writes:\n> \n> > On Mon, May 13, 2013 at 06:53:29AM -0700, Junio C Hamano wrote:\n> >> John Keeping <john@keeping.me.uk> writes:\n> >> \n> >> > The caching layer could also introduce false positives though, which is\n> >> > more serious.  If you cache patch IDs with a pathspec restriction ...\n> >> \n> >> What?  What business does patch-id have with pathspec-limited diff\n> >> generation?  You do not rebase or cherry-pick with pathspec, so\n> >> unless you are populating the patch-id cache at a wrong point (like,\n> >> say whenevern \"git show $commit\" is run), I am not sure why pathspec\n> >> limit becomes even an issue.\n> >\n> > revision.c::cherry_pick_list() sets the pathspec to what was specified\n> > in the revision options.  It's done that since commit 36d56de (Fix\n> > --cherry-pick with given paths, 2007-07-10) and t6007 tests that it\n> > works.\n> \n> Then the caching should be automatically turned off when pathspec is\n> given.\n\nThat was my first thought, but since we can be affected by other diff\noptions set in the user's config as well it ended up being simpler to\ninclude it in the options hash and use that.\n\nThis has the advantage that you get the benefit of the cache if you run\n\"git log --cherry-mark\" with the same paths more than once.  In my\ntesting the cache is beneficial as soon as you examine more than one\nsimilar range (e.g. master...feature-A and then master...feature-B).\n"},{"id":"217201","messageId":"7vd2suopda.fsf@alter.siamese.dyndns.org","threadId":"33799","inReplyTo":"20130513145948.GR2299@serenity.lan","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-13T15:45:21Z","receivedAt":"2013-05-13T15:45:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping <john@keeping.me.uk> writes:\n\n> This has the advantage that you get the benefit of the cache if you run\n> \"git log --cherry-mark\" with the same paths more than once.  In my\n> testing the cache is beneficial as soon as you examine more than one\n> similar range (e.g. master...feature-A and then master...feature-B).\n\nOK, so perhaps the notes that are keyed with commit ID will record\nmultiple entries, one for each invocation pattern (i.e. all pathspec\ngiven, possibly with nonstandard options)?\n\n\"git diff -- t Documentation\" and \"git diff -- Docu\\* t\", even\nthough they use different pathspec, would produce the same diff;\ninstead of pathspec you may need to key with the actual list of\npaths in the patch, though.\n"},{"id":"217203","messageId":"20130513155241.GS2299@serenity.lan","threadId":"33799","inReplyTo":"7vd2suopda.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] patch-ids.c: cache patch IDs in a notes tree","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-13T15:52:41Z","receivedAt":"2013-05-13T15:52:41Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Mon, May 13, 2013 at 08:45:21AM -0700, Junio C Hamano wrote:\n> John Keeping <john@keeping.me.uk> writes:\n> \n> > This has the advantage that you get the benefit of the cache if you run\n> > \"git log --cherry-mark\" with the same paths more than once.  In my\n> > testing the cache is beneficial as soon as you examine more than one\n> > similar range (e.g. master...feature-A and then master...feature-B).\n> \n> OK, so perhaps the notes that are keyed with commit ID will record\n> multiple entries, one for each invocation pattern (i.e. all pathspec\n> given, possibly with nonstandard options)?\n\nThat would be possible, but I didn't do it in the current version of the\npatch.\n\n> \"git diff -- t Documentation\" and \"git diff -- Docu\\* t\", even\n> though they use different pathspec, would produce the same diff;\n> instead of pathspec you may need to key with the actual list of\n> paths in the patch, though.\n\nMaybe, but I think that would be overkill.\n\nI'm interested to see how much of a benefit we could get by not\ncalculating the patch ID of any commits on the larger side of a\nsymmetric range that touch paths outside the set touched by the smaller\nside.  (revision.c::cherry_pick_list() remembers patch IDs for the\nsmaller side of a symmetric range and then checks if anything on the\nlarger side matches so this fits in naturally.)\n\nIn my usage I generally compare a relatively small topic branch against\nwhatever has happened in some upstream branch so I think this could give\na big improvement but I haven't had time to try it yet.\n"}]}