{"thread":{"id":"31151","subject":"[WIP PATCH] Manual rename correction","startedAt":"2012-07-31T14:15:36Z","lastAt":"2012-08-06T20:38:26Z","messageCount":35,"participants":["Nguyen Thai Ngoc Duy","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"196234","messageId":"20120731141536.GA26283@do","threadId":"31151","inReplyTo":null,"subject":"[WIP PATCH] Manual rename correction","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-07-31T14:15:36Z","receivedAt":"2012-07-31T14:15:36Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Git's rename detection is good but still not perfect. There have been\na few times I wanted to correct git for better output but I\ncouldn't. This PoC WIP patch attempts to address that. It allows to\nbreak/rearrange any file pairs. We can do something crazy like this:\n\n attr.c => dir.c | 1786 ++++++++++++++++++++++++++++++++-----------------\n dir.c => attr.c | 1788 +++++++++++++++++---------------------------------\n t/t1306-xdg-files.sh | 39 ++\n t/test-lib.sh | 1 +\n 4 files changed, 1828 insertions(+), 1786 deletions(-)\n\nThe above output is done with \"git diff --manual-rename=foo A B\"\nand \"foo\" contains (probably not in the best format though)\n\n-- 8< --\nattr.c dir.c\ndir.c attr.c\n-- 8< --\n\nThe plan is to use git-notes to record rename corrections like above\nso that \"git log --patch\" for example can make use of them. I'm not\nsure what to do with merge commits yet (can we track renames in a\nmerge?). We can generate rename file from \"diff -CM\", then users can\nedit and save it.\n\nIf you want to diff between two arbitrary trees, you'll have to feed\nrename corrections via command line as git-notes are for commit diff\nonly.\n\nIn some cases, manual rename may be cheaper than --find-copies-harder,\nso this feature could help reduce cpu usage. Though that's not my main\naim.\n\nOh and I think rename detection in diff other than tree-tree does not\nwork. Maybe I tested it the wrong way?\n\nComments?\n\n-- 8< --\ndiff --git a/diff.c b/diff.c\nindex 62cbe14..c8d55d2 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3547,6 +3547,12 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tDIFF_OPT_SET(options, RENAME_EMPTY);\n \telse if (!strcmp(arg, \"--no-rename-empty\"))\n \t\tDIFF_OPT_CLR(options, RENAME_EMPTY);\n+\telse if (!prefixcmp(arg, \"--manual-rename=\")) {\n+\t\tint ret = strbuf_read_file(&options->renames, arg + 16, 0);\n+\t\tif (ret == -1)\n+\t\t\tdie(\"unable to read %s\", arg + 16);\n+\t\tDIFF_OPT_SET(options, MANUAL_RENAME);\n+\t}\n \telse if (!strcmp(arg, \"--relative\"))\n \t\tDIFF_OPT_SET(options, RELATIVE_NAME);\n \telse if (!prefixcmp(arg, \"--relative=\")) {\n@@ -4621,6 +4627,8 @@ void diffcore_std(struct diff_options *options)\n \tif (options->skip_stat_unmatch)\n \t\tdiffcore_skip_stat_unmatch(options);\n \tif (!options->found_follow) {\n+\t\tif (DIFF_OPT_TST(options, MANUAL_RENAME))\n+\t\t\tdiffcore_manual_rename(options);\n \t\t/* See try_to_follow_renames() in tree-diff.c */\n \t\tif (options->break_opt != -1)\n \t\t\tdiffcore_break(options->break_opt);\ndiff --git a/diff.h b/diff.h\nindex e027650..60d104e 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -61,6 +61,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)\n #define DIFF_OPT_FIND_COPIES_HARDER (1 << 6)\n #define DIFF_OPT_FOLLOW_RENAMES (1 << 7)\n #define DIFF_OPT_RENAME_EMPTY (1 << 8)\n+#define DIFF_OPT_MANUAL_RENAME (1 << 9)\n /* (1 << 9) unused */\n #define DIFF_OPT_HAS_CHANGES (1 << 10)\n #define DIFF_OPT_QUICK (1 << 11)\n@@ -147,6 +148,7 @@ struct diff_options {\n \tint close_file;\n \n \tstruct pathspec pathspec;\n+\tstruct strbuf renames;\n \tchange_fn_t change;\n \tadd_remove_fn_t add_remove;\n \tdiff_format_fn_t format_callback;\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 216a7a4..05da99f 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -722,3 +722,148 @@ void diffcore_rename(struct diff_options *options)\n \trename_src_nr = rename_src_alloc = 0;\n \treturn;\n }\n+\n+struct rename {\n+\tchar *one, *two;\n+\tstruct rename *next_one, *next_two;\n+\tstruct diff_filespec *spec_one;\n+\tstruct diff_filespec *spec_two;\n+};\n+\n+static unsigned int string_hash(const char *s)\n+{\n+\tunsigned int v = 1;\n+\twhile (s && *s)\n+\t\tv += (unsigned char)*s++;\n+\treturn v;\n+}\n+\n+void diffcore_manual_rename(struct diff_options *options)\n+{\n+\tstruct rename *renames = NULL;\n+\tint i, nr = 0, alloc = 0;\n+\tconst char *next, *p, *end;\n+\tstruct hash_table hash_one, hash_two;\n+\tstruct diff_queue_struct *q = &diff_queued_diff;\n+\tstruct diff_queue_struct outq;\n+\n+\t/* parse rename instructions */\n+\tend = options->renames.buf + options->renames.len;\n+\tfor (p = options->renames.buf; p < end; p = next) {\n+\t\tstruct rename *r;\n+\t\tconst char *sep, *nl, *next_sep;\n+\n+\t\tnl = strchr(p, '\\n');\n+\t\tif (!nl)\n+\t\t\tnl = next = end;\n+\t\telse {\n+\t\t\tnext = nl + 1;\n+\t\t\tif (p == nl)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/* one space to separate two paths (for now, quoting can come later) */\n+\t\tsep = strchr(p, ' ');\n+\t\tif (!sep || sep >= nl)\n+\t\t\tdie(\"invalid syntax\");\n+\t\tnext_sep = strchr(sep + 1, ' ');\n+\t\tif (next_sep && next_sep < nl)\n+\t\t\tdie(\"invalid syntax\");\n+\n+\t\tALLOC_GROW(renames, nr + 1, alloc);\n+\t\tr = renames + nr++;\n+\t\tmemset(r, 0, sizeof(*r));\n+\t\tif (p < sep)\n+\t\t\tr->one = xstrndup(p, sep - p);\n+\t\tif (sep < nl)\n+\t\t\tr->two = xstrndup(sep + 1, nl - (sep + 1));\n+\t}\n+\n+\n+\t/* initialize hash tables */\n+\tinit_hash(&hash_one);\n+\tinit_hash(&hash_two);\n+\tfor (i = 0; i < nr; i++) {\n+\t\tstruct rename *r = renames + i;\n+\t\tvoid** p;\n+\t\tp = insert_hash(string_hash(r->one), r, &hash_one);\n+\t\tif (p) {\n+\t\t\tr->next_one = *p;\n+\t\t\t*p = r;\n+\t\t}\n+\t\tp = insert_hash(string_hash(r->two), r, &hash_two);\n+\t\tif (p) {\n+\t\t\tr->next_two = *p;\n+\t\t\t*p = r;\n+\t\t}\n+\t}\n+\n+\t/* rename */\n+\tDIFF_QUEUE_CLEAR(&outq);\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tstruct rename *r1 = NULL, *r2 = NULL;\n+\t\tint hash, skip = 0;\n+\t\tif (DIFF_PAIR_UNMERGED(p))\n+\t\t\tcontinue;\n+\t\tif (DIFF_FILE_VALID(p->one)) {\n+\t\t\thash = string_hash(p->one->path);\n+\t\t\tr1 = lookup_hash(hash, &hash_one);\n+\t\t\twhile (r1) {\n+\t\t\t\tif (!strcmp(p->one->path, r1->one)) {\n+\t\t\t\t\tr1->spec_one = p->one;\n+\t\t\t\t\tskip = 1;\n+\t\t\t\t}\n+\t\t\t\tr1 = r1->next_one;\n+\t\t\t}\n+\t\t}\n+\t\tif (DIFF_FILE_VALID(p->two)) {\n+\t\t\thash = string_hash(p->two->path);\n+\t\t\tr2 = lookup_hash(hash, &hash_two);\n+\t\t\twhile (r2) {\n+\t\t\t\tif (!strcmp(p->two->path, r2->two)) {\n+\t\t\t\t\tr2->spec_two = p->two;\n+\t\t\t\t\tskip = 1;\n+\t\t\t\t}\n+\t\t\t\tr2 = r2->next_two;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* This pair has nothing to do with manual renames,\n+\t\t reinsert it */\n+\t\tif (!skip)\n+\t\t\tdiff_q(&outq, p);\n+\t}\n+\tfree(q->queue);\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tstruct rename *r = renames + i;\n+\t\tstruct diff_filepair *dp;\n+\t\tif (r->spec_one && r->spec_two) {\n+\t\t\tdp = diff_queue(&outq, r->spec_one, r->spec_two);\n+\t\t\tdp->renamed_pair = 1;\n+\t\t\tdp->score = MAX_SCORE;\n+\t\t} else if (r->spec_one && !r->two) {\n+\t\t\tdp = diff_queue(&outq, r->spec_one,\n+\t\t\t\t\talloc_filespec(r->one));\n+\t\t} else if (!r->one && r->spec_two) {\n+\t\t\tdp = diff_queue(&outq, alloc_filespec(r->two),\n+\t\t\t\t\tr->spec_two);\n+\t\t} else {\n+\t\t\tdie(\"incorrect rename %s %s\", r->one, r->two);\n+\t\t}\n+\t}\n+\t*q = outq;\n+\t/* required? */\n+\tdiffcore_fix_diff_index(options);\n+\n+\t/* cleanup */\n+\tfor (i = 0; i < nr; i++) {\n+\t\tstruct rename *r = renames + i;\n+\t\tfree(r->one);\n+\t\tfree(r->two);\n+\t}\n+\tfree(renames);\n+\tfree_hash(&hash_one);\n+\tfree_hash(&hash_two);\n+}\ndiff --git a/diffcore.h b/diffcore.h\nindex be0739c..193bc67 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -107,6 +107,7 @@ extern void diff_q(struct diff_queue_struct *, struct diff_filepair *);\n \n extern void diffcore_break(int);\n extern void diffcore_rename(struct diff_options *);\n+extern void diffcore_manual_rename(struct diff_options *);\n extern void diffcore_merge_broken(void);\n extern void diffcore_pickaxe(struct diff_options *);\n extern void diffcore_order(const char *orderfile);\n-- 8< --\n-- \nDuy\n"},{"id":"196238","messageId":"7vtxwnki1a.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120731141536.GA26283@do","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-07-31T16:32:49Z","receivedAt":"2012-07-31T16:32:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> The above output is done with \"git diff --manual-rename=foo A B\"\n> and \"foo\" contains (probably not in the best format though)\n>\n> -- 8< --\n> attr.c dir.c\n> dir.c attr.c\n> -- 8< --\n> ...\n> Comments?\n\nIt is a good direction to go in, I would think, to give users a way\nto explicitly tell that \"in comparison between these two trees, I\nknow path B in the postimage corresponds to path A in the preimage\".\n\nI however wonder why you did this as a separate function that only\ndoes the explicitly marked ones. Probably it was easier as a POC to\ndo it this way, and that is fine.\n\nThe real version should do this in the same diffcore_rename()\nfunction, by excluding the paths that the user explicitly told you\nabout from the the automatic matching logic, and instead matching\nthem up manually; then you can let the remainder of the paths be\npaired by the existing code.\n\nNotice how the non-nullness of rename_dst[i].pair is used as a cue\nto skip the similarity computation in the expensive matrix part of\ndiffcore_rename()? That comes from find_exact_renames() that is\ncalled earlier in the function. I would imagine that your logic\nwould fit _before_ we call find_exact_renames() as a call to a new\nhelper function (e.g. \"record_explicit_renames()\" perhaps).\nAnything that reduces the cost in the matrix part should come\nearlier, as that reduces the number of pairs we would need to try\nmatching up.\n\nWe might want to introduce a way to express the similarity score for\nsuch a filepair that was manually constructed when showing the\nresult, though.\n"},{"id":"196252","messageId":"20120731192342.GB30808@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7vtxwnki1a.fsf@alter.siamese.dyndns.org","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-07-31T19:23:42Z","receivedAt":"2012-07-31T19:23:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 31, 2012 at 09:32:49AM -0700, Junio C Hamano wrote:\n\n> Nguyen Thai Ngoc Duy writes:\n> \n> > The above output is done with \"git diff --manual-rename=foo A B\"\n> > and \"foo\" contains (probably not in the best format though)\n> >\n> > -- 8< --\n> > attr.c dir.c\n> > dir.c attr.c\n> > -- 8< --\n> > ...\n> > Comments?\n> \n> It is a good direction to go in, I would think, to give users a way\n> to explicitly tell that \"in comparison between these two trees, I\n> know path B in the postimage corresponds to path A in the preimage\".\n\nI do not think that is the right direction. Let's imagine that I have a\ncommit \"A\" and I annotate it (via notes or whatever) to say \"between\nA^^{tree} and A^{tree}, foo.c became bar.c\". That will help me when\ndoing \"git show\" or \"git log\". But it will not help me when I later try\nto merge \"A\" (or its descendent). In that case, I will compute the diff\nbetween \"A\" and the merge-base (or worse, some descendent of \"A\" and the\nmerge-base), and I will miss this hint entirely.\n\nA much better hint is to annotate pairs of sha1s, to say \"do not bother\ndoing inexact rename correlation on this pair; I promise that they have\nvalue N\". Then it will find that pair no matter which trees or commits\nare being diffed, and it will do so relatively inexpensively[1].\n\nThat is not fool-proof, of course. You might have a manual rename from\nsha1 X to sha1 Y, and then a slight modification to Y to make Z. So you\nwould want some kind of transitivity to notice that X and Z correlate.\nI think you could model it as a graph problem; sha1s are nodes, and each\n\"this is a rename\" pair of annotated sha1s has an edge between them.\nThey are the \"same file\" if there is a path.\n\nOf course that gives you bizarre and counter-intuitive results, because\nX and Z might not actually be that similar. And that is why we have\nrename detection in the first place. The idea of file identity (which\nthis fundamentally is) leads to these sorts of weird results.\n\nI'm sure you could get better results by weakening the transitivity\naccording to the rename score, or something like that. But now you are\ngetting pretty complex.\n\n-Peff\n\n[1] We could actually cache rename results by storing pairs of sha1s\n along with their rename score, and should be able to get a good\n speedup (we are still src*dst in comparing, but now the comparison\n is a simple table lookup rather than loading the blobs and computing\n the differences). If we had such a cache, then manually marking a\n rename would just be a matter of priming the cache with your manual\n entries.\n"},{"id":"196262","messageId":"7vfw87isx1.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120731192342.GB30808@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-07-31T20:20:42Z","receivedAt":"2012-07-31T20:20:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> A much better hint is to annotate pairs of sha1s, to say \"do not bother\n> doing inexact rename correlation on this pair; I promise that they have\n> value N\".\n\nSurely. And I suspect that the patch to the current codebase to do\nso would be much less impact if you go that way.\n"},{"id":"196278","messageId":"20120801004238.GA15428@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7vfw87isx1.fsf@alter.siamese.dyndns.org","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-01T00:42:38Z","receivedAt":"2012-08-01T00:42:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 31, 2012 at 01:20:42PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > A much better hint is to annotate pairs of sha1s, to say \"do not bother\n> > doing inexact rename correlation on this pair; I promise that they have\n> > value N\".\n> \n> Surely. And I suspect that the patch to the current codebase to do\n> so would be much less impact if you go that way.\n\nYes. You may remember I wrote a generic caching subsystem last summer\nwhen we were talking about caching commit generations. Plugging in a new\nmap type to map sha1 pairs to 32-bit integers was pretty simple, and\nthat gives the basis for a rename cache.\n\nIt's fairly unimpressive on git.git. My best-of-five for \"git log\n--format=%H --raw -M\" went from 5.83s to 5.74s, which is pretty much\nwithin the run-to-run noise. The resulting cache was 155K.\n\nHowever, it's easy to come up with much more pathological cases. I have\na really ugly rename-and-tweak-tags commit on my photo repository, and\nthose blobs are relatively big. My timings for \"git show\" on that were:\n\n before: 49.724s\n after, run 1: 54.904s\n after, run 2: 0.117s\n\nWhich is pretty darn nice. The resulting cache is 5.3M (the repository\nitself is in the gigabytes, but that's not really relevant; the cache\nwill obviously scale with the number of paths, not with the size of the\nblobs).\n\nIt would also work for copies, too, of course. Here are the results of\n\"git log --format=%H --raw -M -C -C\" on git.git:\n\n before: 1m35s\n after, run 1: 39.7s\n after, run 2: 39.5s\n\nSo it does make much more of a difference for copies, which is obvious;\ngit is doing a lot more work for us to cache. At the same time, our\ncache is much bigger: 32M. Yikes.\n\nMy cache is fairly naive, in that it literally stores 44 bytes of\n for each entry. At the cost of more\ncomplexity, you could store each src_sha1 once, followed by a set of\n pairs. I also didn't take any special care to avoid\nduplicates of and (since presumably these renames would be\ncommutative). I'm not sure it is necessary, though; I think the copy\nmachinery already suppresses this when entries are in both source and\ndestination lists.\n\nSo I don't know. It can definitely speed up some operations, but at the\ncost of a non-trivial cache on disk. I'll spare you all of the generic\ncaching infrastructure, but the actual patch to rename looks like this\n(just to give a sense of where the hooks go):\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 216a7a4..db70878 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,6 +6,7 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n #include \"progress.h\"\n+#include \"metadata-cache.h\"\n \n /* Table of rename/copy destinations */\n \n@@ -137,7 +138,8 @@ static int estimate_similarity(struct diff_filespec *src,\n \t */\n \tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n \tunsigned long delta_limit;\n-\tint score;\n+\tuint32_t score;\n+\tstruct sha1pair pair;\n \n \t/* We deal only with regular files. Symlink renames are handled\n \t * only when they are exact matches --- in other words, no edits\n@@ -175,6 +177,11 @@ static int estimate_similarity(struct diff_filespec *src,\n \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n+\thashcpy(pair.one, src->sha1);\n+\thashcpy(pair.two, dst->sha1);\n+\tif (rename_cache_get(&pair, &score))\n+\t\treturn score;\n+\n \tif (!src->cnt_data && diff_populate_filespec(src, 0))\n \t\treturn 0;\n \tif (!dst->cnt_data && diff_populate_filespec(dst, 0))\n@@ -195,6 +202,7 @@ static int estimate_similarity(struct diff_filespec *src,\n \t\tscore = 0; /* should not happen */\n \telse\n \t\tscore = (int)(src_copied * MAX_SCORE / max_size);\n+\trename_cache_set(&pair, &score);\n \treturn score;\n }\n \n-Peff\n"},{"id":"196279","messageId":"CACsJy8B14qSLkAt9VRQTCkoZx5UtGTpAmMHKyqk+_o14bc9GmQ@mail.gmail.com","threadId":"31151","inReplyTo":"20120731192342.GB30808@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-01T01:10:12Z","receivedAt":"2012-08-01T01:10:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Aug 1, 2012 at 2:23 AM, Jeff King wrote:\n>> It is a good direction to go in, I would think, to give users a way\n>> to explicitly tell that \"in comparison between these two trees, I\n>> know path B in the postimage corresponds to path A in the preimage\".\n>\n> I do not think that is the right direction. Let's imagine that I have a\n> commit \"A\" and I annotate it (via notes or whatever) to say \"between\n> A^^{tree} and A^{tree}, foo.c became bar.c\". That will help me when\n> doing \"git show\" or \"git log\". But it will not help me when I later try\n> to merge \"A\" (or its descendent). In that case, I will compute the diff\n> between \"A\" and the merge-base (or worse, some descendent of \"A\" and the\n> merge-base), and I will miss this hint entirely.\n>\n> A much better hint is to annotate pairs of sha1s, to say \"do not bother\n> doing inexact rename correlation on this pair; I promise that they have\n> value N\".\n\nI haven't had time to think it through yet but I throw my thoughts in\nany way. I actually went with your approach first. But it's more\ndifficult to control the renaming. Assume we want to tell git to\nrename SHA-1 \"A\" to SHA-1 \"B\". What happens if we have two As in the\nsource tree and two Bs in the target tree? What happens if two As and\none B, or one A and two Bs? What if a user defines A -> B and A -> C,\nand we happen to have two As in source tree and B and C in target\ntree?\n\nThere's also the problem with transferring this information. With\ngit-notes I think I can transfer it (though not automatically). How do\nwe transfer sha1 map (that you mentioned in the commit generation mail\nin this thread)?\n\n> Then it will find that pair no matter which trees or commits\n> are being diffed, and it will do so relatively inexpensively[1].\n\nBut does that happen often in practice? I mean diff-ing two arbitrary\ntrees and expect rename correction. I disregarded it as \"git log\" is\nmy main case, but I'm just a single user..\n-- \nDuy\n"},{"id":"196280","messageId":"20120801020124.GA18071@sigill.intra.peff.net","threadId":"31151","inReplyTo":"CACsJy8B14qSLkAt9VRQTCkoZx5UtGTpAmMHKyqk+_o14bc9GmQ@mail.gmail.com","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-01T02:01:24Z","receivedAt":"2012-08-01T02:01:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 01, 2012 at 08:10:12AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > I do not think that is the right direction. Let's imagine that I have a\n> > commit \"A\" and I annotate it (via notes or whatever) to say \"between\n> > A^^{tree} and A^{tree}, foo.c became bar.c\". That will help me when\n> > doing \"git show\" or \"git log\". But it will not help me when I later try\n> > to merge \"A\" (or its descendent). In that case, I will compute the diff\n> > between \"A\" and the merge-base (or worse, some descendent of \"A\" and the\n> > merge-base), and I will miss this hint entirely.\n> >\n> > A much better hint is to annotate pairs of sha1s, to say \"do not bother\n> > doing inexact rename correlation on this pair; I promise that they have\n> > value N\".\n> \n> I haven't had time to think it through yet but I throw my thoughts in\n> any way. I actually went with your approach first. But it's more\n> difficult to control the renaming. Assume we want to tell git to\n> rename SHA-1 \"A\" to SHA-1 \"B\". What happens if we have two As in the\n> source tree and two Bs in the target tree? What happens if two As and\n> one B, or one A and two Bs? What if a user defines A -> B and A -> C,\n> and we happen to have two As in source tree and B and C in target\n> tree?\n\nYes, it disregards path totally. But if you had the exact same movement\nof content from one path to another in one instance, and it is\nconsidered a rename, wouldn't it also be a rename in a second instance?\n\n> There's also the problem with transferring this information. With\n> git-notes I think I can transfer it (though not automatically). How do\n> we transfer sha1 map (that you mentioned in the commit generation mail\n> in this thread)?\n\nThat is orthogonal to the issue of what is being stored. I chose my\nmmap'd disk implementation because it is very fast, which makes it nice\nfor a performance cache. But you could store the same thing in git-notes\n(indexed by dst sha1, I guess, and then pointing to a blob of (src,\nscore) pairs.\n\nIf you want to include path-based hints in a commit, I'd say that using\nsome micro-format in the commit message would be the simplest thing. But\nthat has been discussed before; ultimately the problem is that it only\ncovers _one_ diff that we do with that commit (it is probably the most\ncommon, of course, but it doesn't cover them all).\n\n> > Then it will find that pair no matter which trees or commits\n> > are being diffed, and it will do so relatively inexpensively[1].\n> \n> But does that happen often in practice? I mean diff-ing two arbitrary\n> trees and expect rename correction. I disregarded it as \"git log\" is\n> my main case, but I'm just a single user..\n\nIt happens every time merge-recursive does rename detection, which\nincludes \"git merge\" but also things like \"cherry-pick\".\n\n-Peff\n"},{"id":"196282","messageId":"CACsJy8AYzYTJ+k72ZEuWW-RdKe7arYbbscVALNYakKSfYqD_zw@mail.gmail.com","threadId":"31151","inReplyTo":"20120801020124.GA18071@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-01T04:36:00Z","receivedAt":"2012-08-01T04:36:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Aug 1, 2012 at 9:01 AM, Jeff King wrote:\n> On Wed, Aug 01, 2012 at 08:10:12AM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> > I do not think that is the right direction. Let's imagine that I have a\n>> > commit \"A\" and I annotate it (via notes or whatever) to say \"between\n>> > A^^{tree} and A^{tree}, foo.c became bar.c\". That will help me when\n>> > doing \"git show\" or \"git log\". But it will not help me when I later try\n>> > to merge \"A\" (or its descendent). In that case, I will compute the diff\n>> > between \"A\" and the merge-base (or worse, some descendent of \"A\" and the\n>> > merge-base), and I will miss this hint entirely.\n>> >\n>> > A much better hint is to annotate pairs of sha1s, to say \"do not bother\n>> > doing inexact rename correlation on this pair; I promise that they have\n>> > value N\".\n>>\n>> I haven't had time to think it through yet but I throw my thoughts in\n>> any way. I actually went with your approach first. But it's more\n>> difficult to control the renaming. Assume we want to tell git to\n>> rename SHA-1 \"A\" to SHA-1 \"B\". What happens if we have two As in the\n>> source tree and two Bs in the target tree? What happens if two As and\n>> one B, or one A and two Bs? What if a user defines A -> B and A -> C,\n>> and we happen to have two As in source tree and B and C in target\n>> tree?\n>\n> Yes, it disregards path totally. But if you had the exact same movement\n> of content from one path to another in one instance, and it is\n> considered a rename, wouldn't it also be a rename in a second instance?\n\nYes. This is probably cosmetics only, but without path information, we\nleave it to chance to decide which A to pair with B and C (in the\nA->B, A->C case above). Wrong path might lead to funny effects (i'm\nthinking of git log --follow).\n\n>> There's also the problem with transferring this information. With\n>> git-notes I think I can transfer it (though not automatically). How do\n>> we transfer sha1 map (that you mentioned in the commit generation mail\n>> in this thread)?\n\nI wasn't clear. This is about transferring info across repositories.\n\n> That is orthogonal to the issue of what is being stored. I chose my\n> mmap'd disk implementation because it is very fast, which makes it nice\n> for a performance cache. But you could store the same thing in git-notes\n> (indexed by dst sha1, I guess, and then pointing to a blob of (src,\n> score) pairs.\n>\n> If you want to include path-based hints in a commit, I'd say that using\n> some micro-format in the commit message would be the simplest thing.\n\nRename correction is after the commit is created. I don't think we can\nrecreate commits.\n\n> But\n> that has been discussed before; ultimately the problem is that it only\n> covers _one_ diff that we do with that commit (it is probably the most\n> common, of course, but it doesn't cover them all).\n\nHow about we generate sha1 mapping from commit hints? We try to take\nadvantage of path hints when we can. Else we fall back to sha-1\nmapping. This way we can transfer commit hints as git-notes to another\nrepo, then regenerate sha-1 mapping there. No need to transfer sha1\nmaps.\n\n>> > Then it will find that pair no matter which trees or commits\n>> > are being diffed, and it will do so relatively inexpensively[1].\n>>\n>> But does that happen often in practice? I mean diff-ing two arbitrary\n>> trees and expect rename correction. I disregarded it as \"git log\" is\n>> my main case, but I'm just a single user..\n>\n> It happens every time merge-recursive does rename detection, which\n> includes \"git merge\" but also things like \"cherry-pick\".\n\nThanks. I'll look into merge/cherry-pick.\n-- \nDuy\n"},{"id":"196283","messageId":"7v8vdzgngo.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120801004238.GA15428@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-01T06:01:27Z","receivedAt":"2012-08-01T06:01:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> @@ -175,6 +177,11 @@ static int estimate_similarity(struct diff_filespec *src,\n> \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n> \t\treturn 0;\n> \n> +\thashcpy(pair.one, src->sha1);\n> +\thashcpy(pair.two, dst->sha1);\n> +\tif (rename_cache_get(&pair, &score))\n> +\t\treturn score;\n> +\n\nRandom thoughts.\n\nEven though your \"rename cache\" could be used to reject pairing that\nthe similarity estimator would otherwise give high score, I would\nimagine that in practice, people would always use the mechanism to\nboost the similarity score of desired pairing. This conjecture has\na few interesting implications.\n\n - As we track of only the top NUM_CANDIDATE_PER_DST rename src for\n each dst (see record_if_better()), you should be able to first\n see if pairs that have dst exist in your rename cache, and\n iterate over the pairs, filling m[] with srcs that\n appear in this particular invocation of diff.\n\n - If you find NUM_CANDIDATE_PER_DST srcs from your rename cache,\n you wouldn't have to run estimate_similarity() at all, but that\n is very unlikely. We could however declare that user configured\n similarity boost always wins computed ones, and skip estimation\n for a dst for which you find an entry in the rename cache.\n\n - As entries in rename cache that record high scores have names of\n \"similar\" blobs, pack-objects may be able to take advantage of\n this information.\n\n - If you declare blobs A and B are similar, it is likely that blobs\n C, D, E, ... that are created by making a series of small tweaks\n to B are also similar. Would it make more sense to introduce a\n concept of \"set of similar blobs\" instead of recording pairwise\n scores for (A,B), (A,C), (A,D), ... (B,C), (B,D), ...? If so,\n the body of per-dst loop in diffcore_rename() may become:\n\n\tif (we know where dst came from)\n\t\tcontinue;\n\tif (dst belongs to a known blob family) {\n\t\tfor (each src in rename_src[]) {\n\t\t\tif (src belongs to the same blob family as dst)\n\t\t\t\trecord it in m[];\n }\n\t}\n\tif (the above didn't record anything in m[]) {\n \t... existing estimate_similarity() code ...\n\t}\n\nRegarding your rename-and-tweak-exif photo sets, is the issue that\nthere are too many rename src/dst candidates and filling a large\nmatrix takes a lot of time, or tweaking exif makes the contents\nunnecessarily dissimilar and causes the similarity detection to\nfail? As we still have the pathname in this codepath, I am\nwondering if we would benefit from custom \"content hash\" that knows\nthe nature of payload than the built-in similarity estimator, driven\nby the attribute mechanism (if the latter is the case, that is).\n"},{"id":"196284","messageId":"7v4nongn3e.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"CACsJy8AYzYTJ+k72ZEuWW-RdKe7arYbbscVALNYakKSfYqD_zw@mail.gmail.com","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-01T06:09:25Z","receivedAt":"2012-08-01T06:09:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> Yes. This is probably cosmetics only, but without path information, we\n> leave it to chance to decide which A to pair with B and C (in the\n> A->B, A->C case above). Wrong path might lead to funny effects (i'm\n> thinking of git log --follow).\n\nIsn't that why and can have different scores per object\nname pair? And if you mean by B and C the paths not object names,\nand the blob at B and C are indeed identical, why would it matter?\n\n>>> There's also the problem with transferring this information. With\n>>> git-notes I think I can transfer it (though not automatically). How do\n>>> we transfer sha1 map (that you mentioned in the commit generation mail\n>>> in this thread)?\n>\n> I wasn't clear. This is about transferring info across repositories.\n\nIt is simple to define a portable format to record Jeff's rename\ncache database (it could be a text blob full of \"x40 x40 score\"\nlines), point such a blob with a special ref, and write a Porcelain\nto transfer and merge across repositories, e.g.\n\n\tgit fetch $there refs/rename-cache\n\tnew=$(\n\t(\n git cat-file blob refs/rename-cache\n git cat-file blob FETCH_HEAD\n\t) | sort | uniq | git hash-object -w --stdin)\n\tgit update-ref refs/rename-cache $new\n\nAnd as Jeff said, that is orthogonal to the issue of what is being\nstored. The contents of refs/rename-cache blob could be compiled\ninto a binary form for quicker access at runtime in the Porcelain.\n"},{"id":"196285","messageId":"CACsJy8Aa_YohFEApGQxL5086vOviAKBc1AB0QyWVsda6byrYzg@mail.gmail.com","threadId":"31151","inReplyTo":"7v4nongn3e.fsf@alter.siamese.dyndns.org","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-01T06:34:23Z","receivedAt":"2012-08-01T06:34:23Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Aug 1, 2012 at 1:09 PM, Junio C Hamano wrote:\n> Nguyen Thai Ngoc Duy writes:\n>\n>> Yes. This is probably cosmetics only, but without path information, we\n>> leave it to chance to decide which A to pair with B and C (in the\n>> A->B, A->C case above). Wrong path might lead to funny effects (i'm\n>> thinking of git log --follow).\n>\n> Isn't that why and can have different scores per object\n> name pair? And if you mean by B and C the paths not object names,\n> and the blob at B and C are indeed identical, why would it matter?\n\nI don't see how scores affect that. Suppose I have two trees and a\nrename-cache file:\n\n$ git ls-tree -r HEAD^\n100644 blob d00491 path1/foo\n100644 blob d00491 path2/bar\n$ git ls-tree -r HEAD\n100644 blob 0cfbf0 path1/fooo\n100644 blob 00750e path2/barr\n$ cat rename-cache\nd00491 0cfbf0 \nd00491 00750e \n\nHow can I be sure \"git diff HEAD^!\" will rename path1/foo =>\npath1/fooo and path2/bar => path2/barr, not path1/foo => path2/barr\nand path2/bar => path1/fooo?\n-- \nDuy\n"},{"id":"196304","messageId":"20120801212719.GA16233@sigill.intra.peff.net","threadId":"31151","inReplyTo":"CACsJy8AYzYTJ+k72ZEuWW-RdKe7arYbbscVALNYakKSfYqD_zw@mail.gmail.com","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-01T21:27:20Z","receivedAt":"2012-08-01T21:27:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 01, 2012 at 11:36:00AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > That is orthogonal to the issue of what is being stored. I chose my\n> > mmap'd disk implementation because it is very fast, which makes it nice\n> > for a performance cache. But you could store the same thing in git-notes\n> > (indexed by dst sha1, I guess, and then pointing to a blob of (src,\n> > score) pairs.\n> >\n> > If you want to include path-based hints in a commit, I'd say that using\n> > some micro-format in the commit message would be the simplest thing.\n> \n> Rename correction is after the commit is created. I don't think we can\n> recreate commits.\n\nYes, if you go with a commit-based approach, you can do either notes or\nin-commit messages. In other words, I would break the solutions down as:\n\n 1. Store sha1+sha1 -> score mapping (i.e., what I suggested). This is\n fundamentally a global store, not a per-commit store. For storage,\n you can do one (or a combination) of:\n\n a. Store the mapping in some local file. Fast, but can't be shared.\n\n b. Store the mapping in a note (probably indexed by the destination\n blob sha1). Less efficient, but easy to share.\n\n 2. Store path -> path mapping. This is fundamentally a per-commit\n store, since it is valid only in the diff between two particular\n trees. For storage, you can do one (or a combination) of:\n\n a. Store the mapping inside the commit object. Simple to share, but\n hard to change later.\n\n b. Store it in a note indexed by the commit object. Slightly harder\n to share, but can change later.\n\nI implemented (1a). Implementing (1b) would be easy, but for a full-on\ncache (especially for \"-C\"), I think the resulting size might be\nprohibitive.\n\nAll solutions under (2) suffer from the same problem: they are accurate\nonly for a single diff. For other diffs, you would either have to not\nuse the feature, or you would be stuck traversing the history and\nassigning a temporary file identity (e.g., given commits A->B->C, and in\nA->B we rename \"foo\" to \"bar\", the diff between A and C could discover\nthat A's \"foo\" corresponds to C's \"bar\").\n\nThat is slower than what we do now, but that is only one problem with\nit. Another is that the history relationship between the commits might\nbe complex. In the example above, we had a direct-descendent\nrelationship. But what about one with branching, and one side does the\nrename and the other does not? Or even cherry-picking from an unrelated\npart of history entirely?\n\nAnd I think all forms of (2) will suffer from this, no matter how you\nstore the data. The reason I mentioned specifically putting it in the\ncommit message (i.e., 2a) because that is what people suggested in the\nvery early days of git (e.g., saying that rename detection is OK, but\ncould we supplement it with hints at commit-time?). And all of the\narguments against it back then apply equally now. And apply equally to\nstoring it in notes, because it is just another form of the same thing.\n\n> > But that has been discussed before; ultimately the problem is that\n> > it only covers _one_ diff that we do with that commit (it is\n> > probably the most common, of course, but it doesn't cover them all).\n> \n> How about we generate sha1 mapping from commit hints? We try to take\n> advantage of path hints when we can. Else we fall back to sha-1\n> mapping. This way we can transfer commit hints as git-notes to another\n> repo, then regenerate sha-1 mapping there. No need to transfer sha1\n> maps.\n\nYes. You could definitely pre-seed the sha1 mapping from the per-commit\nhints. However, if you are interested in overriding git's rename\ndetection, then per-commit hints will only let you do part of what you\nwant. For example, consider a linear history like this:\n\n A--B--C\n\nAnd imagine that commit B renamed a file from \"foo\" to \"bar\", and that\ncommit C further modified \"bar\". Let's say that git did not detect the\nrename in B, but you manually annotated it. As a result, we seed the\nsha1 mapping to show that the sha1 of A:foo and the sha1 of B:bar has a\nrename score of 100%.\n\nNow I want to do a diff between A and C (e.g., for rename detection on\none side of a merge). But their sha1s are not in my mapping (because\nC:bar is not the same as B:bar), and I don't find the rename. To find\nit, I cannot seed a per-commit path mapping. I must seed the sha1\nmapping itself.\n\nSo to adapt your per-commit mapping into a sha1 mapping, the seeding\nprocess would have to actually walk the history, transitively creating\nsha1 mapping entries (i.e., seeing that \"bar\" changed between B and C,\nand therefore mapping A:foo to C:bar, as well).\n\nFor this reason, I'm not sure that stored overrides like this are\ngenerally useful in the long run. I think storage is useful for\n_caching_ the results, because it doesn't have to be perfect; it just\nhelps with some repetitive queries. Whereas for overriding, I think it\nis much more interesting to override _particular_ diff. E.g., to say \"I\nam merging X and Y, and please pretend that Y renamed \"foo\" to \"bar\"\nwhen you do rename detection.\n\nAnd in that sense, your \"git log\" example can be considered a\nspecial-case of this: you are saying that the diff from $commit to\n$commit^ is done frequently, so rather than saying \"please pretend...\"\neach time, you would like to store the information forever. And storing\nit in the commit message or a note is one way of doing that.\n\nI don't think there's anything fundamentally _wrong_ with that, but I\nkind of question its usefulness. In other words, what is the point in\ndoing so? If it is inform the user that semantically the commit did a\nrename, even though the content changed enough that rename detection\ndoes not find it, then I would argue that you should simply state it in\nthe commit message (or in a human-readable git-note, if it was only\nrealized after the fact).\n\nBut there is not much point in making it machine-readable, since the\ninteresting machine-readable things we do with renames are:\n\n 1. Show the diff against the rename src, which can often be easier to\n read. Except that if rename detection did not find it, it is\n probably _not_ going to be easier to read.\n\n 2. Applying content to the destination of a merge. But you're almost\n never doing the diff between a commit and its parent, so the\n information would be useless.\n\n-Peff\n"},{"id":"196306","messageId":"20120801213207.GB16233@sigill.intra.peff.net","threadId":"31151","inReplyTo":"CACsJy8Aa_YohFEApGQxL5086vOviAKBc1AB0QyWVsda6byrYzg@mail.gmail.com","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-01T21:32:07Z","receivedAt":"2012-08-01T21:32:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 01, 2012 at 01:34:23PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Wed, Aug 1, 2012 at 1:09 PM, Junio C Hamano wrote:\n> > Nguyen Thai Ngoc Duy writes:\n> >\n> >> Yes. This is probably cosmetics only, but without path information, we\n> >> leave it to chance to decide which A to pair with B and C (in the\n> >> A->B, A->C case above). Wrong path might lead to funny effects (i'm\n> >> thinking of git log --follow).\n> >\n> > Isn't that why and can have different scores per object\n> > name pair? And if you mean by B and C the paths not object names,\n> > and the blob at B and C are indeed identical, why would it matter?\n> \n> I don't see how scores affect that. Suppose I have two trees and a\n> rename-cache file:\n> \n> $ git ls-tree -r HEAD^\n> 100644 blob d00491 path1/foo\n> 100644 blob d00491 path2/bar\n> $ git ls-tree -r HEAD\n> 100644 blob 0cfbf0 path1/fooo\n> 100644 blob 00750e path2/barr\n> $ cat rename-cache\n> d00491 0cfbf0 \n> d00491 00750e \n> \n> How can I be sure \"git diff HEAD^!\" will rename path1/foo =>\n> path1/fooo and path2/bar => path2/barr, not path1/foo => path2/barr\n> and path2/bar => path1/fooo?\n\nYou can't. A pathless mapping can never represent that. I think my (and\nJunio's argument) is more like: why would you care? And that gets back\nto the statement I just made elsewhere in the thread. Which is that you\nneed to consider the purpose of the rename detection. For generating\ndiffs and for merging, it doesn't matter in the above case. If the point\nis to communicate some semantics of the change (e.g., if your change was\n\"double the final letter of each filename, and also make a small change),\nthen that is what the commit message is for.\n\n-Peff\n"},{"id":"196310","messageId":"20120801215414.GC16233@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7v8vdzgngo.fsf@alter.siamese.dyndns.org","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-01T21:54:14Z","receivedAt":"2012-08-01T21:54:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 31, 2012 at 11:01:27PM -0700, Junio C Hamano wrote:\n\n> > @@ -175,6 +177,11 @@ static int estimate_similarity(struct diff_filespec *src,\n> > \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n> > \t\treturn 0;\n> > \n> > +\thashcpy(pair.one, src->sha1);\n> > +\thashcpy(pair.two, dst->sha1);\n> > +\tif (rename_cache_get(&pair, &score))\n> > +\t\treturn score;\n> > +\n> \n> Random thoughts.\n> \n> Even though your \"rename cache\" could be used to reject pairing that\n> the similarity estimator would otherwise give high score, I would\n> imagine that in practice, people would always use the mechanism to\n> boost the similarity score of desired pairing. This conjecture has\n> a few interesting implications.\n\nI agree that is the probable use. But low scores might also have a\npurpose in preventing useless work from being done (IOW, storing a \"0\"\nscore is unlikely to happen manually, but it does let us avoid repeating\nthe calculation).\n\nAs you might have guessed, I am really more interested in caching and\nperformance gains than in manual overrides.\n\n> - As we track of only the top NUM_CANDIDATE_PER_DST rename src for\n> each dst (see record_if_better()), you should be able to first\n> see if pairs that have dst exist in your rename cache, and\n> iterate over the pairs, filling m[] with srcs that\n> appear in this particular invocation of diff.\n\nYes, although I don't know if it makes a big difference. We still run\nestimate_similarity on the candidates to see if they make it into\nrecord_if_better, and that is the expensive part. I don't think you want\nto change that either (e.g., by assuming that cached scores will always\nbe in the top N; it would depend on the particular tree that the cached\nscores came from).\n\nOf course, that changes if it is not a cache at all, and simply a manual\noverride. Or if manual overrides are stored separately and take effect\nfirst.\n\nBut I do not think you even want to care about NUM_CANDIDATE_PER_DST for\nmanual overrides. You simply want to take the highest scored one,\nconsider the it done, and not run estimate_similarity at all. Even if\nyou only had 1 (and NUM_CANDIDATE_PER_DST were 4), there is still no\npoint in looking at the others. The manual override should beat it,\nregardless of score.\n\n> - If you find NUM_CANDIDATE_PER_DST srcs from your rename cache,\n> you wouldn't have to run estimate_similarity() at all, but that\n> is very unlikely. We could however declare that user configured\n> similarity boost always wins computed ones, and skip estimation\n> for a dst for which you find an entry in the rename cache.\n\nRight. See above.\n\n> - As entries in rename cache that record high scores have names of\n> \"similar\" blobs, pack-objects may be able to take advantage of\n> this information.\n\nYeah, although I suspect it is not as big a win as you might hope. In\npractice, you're going to diff a lot fewer objects than pack-objects\nwould consider, so most of the pack-objects candidate pairs will not\nhave a cache entry. Which means that you really need to not rely on the\ncache (since it is very likely that the best candidate is still to be\nfound), and you still do lots of computation.\n\nYou could cache the result of comparisons done by pack-objects, but that\ncache ends up being large. You might remember that one of my very first\npatches was a cache for recording negative delta finds (so we try to\ndelta A against B and find that it is not a good match, and record that\ninformation). Even that cache was huge, and we ended up discarding it in\nfavor of Linus's much more sensible \"if two things are in the same pack\nand not delta'd, then either they are not a good match, or something\nelse is in better\" heuristic. But one with full-on similarity scores\nwould be even bigger.\n\n> - If you declare blobs A and B are similar, it is likely that blobs\n> C, D, E, ... that are created by making a series of small tweaks\n> to B are also similar. Would it make more sense to introduce a\n> concept of \"set of similar blobs\" instead of recording pairwise\n> scores for (A,B), (A,C), (A,D), ... (B,C), (B,D), ...? If so,\n> the body of per-dst loop in diffcore_rename() may become:\n\nYes, this is the transitive bit I mentioned elsewhere. I think there are\ndragons lurking there, as you end up with the edges of the set not\n_really_ being that close to each other. You'd probably want some kind\nof weighted association, like if A->B had 80% similarity, and B->C had\n90% similarity, then A->C would be 72%. But even that is not accurate;\nit is just a lower bound. The differences between A->B and B->C might\noverlap, and A->C might be much more similar.\n\nYou can't know the true value without actually finding the score for\nA->C. And since we output the scores, they should probably be accurate.\n\n> Regarding your rename-and-tweak-exif photo sets, is the issue that\n> there are too many rename src/dst candidates and filling a large\n> matrix takes a lot of time, or tweaking exif makes the contents\n> unnecessarily dissimilar and causes the similarity detection to\n> fail?\n\nThe former. We do find the renames; it is just that there are a lot of\nthem (and worse, they are large blobs, so estimate_similarity is slow to\nrun). I have to use \"-l0\" just to get the rename to run at all.\n\n> As we still have the pathname in this codepath, I am wondering if we\n> would benefit from custom \"content hash\" that knows the nature of\n> payload than the built-in similarity estimator, driven by the\n> attribute mechanism (if the latter is the case, that is).\n\nHmm. Interesting. But I don't think that attributes are a good fit here.\nThey are pathname based, so how do I apply anything related to\nsimilarity of a particular version by pathname? IOW, how does it apply\nin one tree but not another?\n\n-Peff\n"},{"id":"196312","messageId":"7vipd2e00g.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120801215414.GC16233@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-01T22:10:55Z","receivedAt":"2012-08-01T22:10:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Jul 31, 2012 at 11:01:27PM -0700, Junio C Hamano wrote:\n> ...\n>> As we still have the pathname in this codepath, I am wondering if we\n>> would benefit from custom \"content hash\" that knows the nature of\n>> payload than the built-in similarity estimator, driven by the\n>> attribute mechanism (if the latter is the case, that is).\n>\n> Hmm. Interesting. But I don't think that attributes are a good fit here.\n> They are pathname based, so how do I apply anything related to\n> similarity of a particular version by pathname? IOW, how does it apply\n> in one tree but not another?\n\nWhen you move porn/0001.jpg in the preimage to naughty/00001.jpg in\nthe postimage, they both can hit \"*.jpg contentid=jpeg\" line in the\ntop-level .gitattribute file, and the contentid driver for jpeg type\nmay strip exif and hash the remainder bits in the image to come up\nwith a token you can use in a similar way as object ID is used in\nthe exact rename detection phase.\n\nJust thinking aloud.\n"},{"id":"196322","messageId":"7v6291eu2v.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120801215414.GC16233@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-02T05:33:44Z","receivedAt":"2012-08-02T05:33:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Jul 31, 2012 at 11:01:27PM -0700, Junio C Hamano wrote:\n>\n>> - As entries in rename cache that record high scores have names of\n>> \"similar\" blobs, pack-objects may be able to take advantage of\n>> this information.\n>\n> Yeah, although I suspect it is not as big a win as you might hope. In\n> practice, you're going to diff a lot fewer objects than pack-objects\n> would consider, so most of the pack-objects candidate pairs will not\n> have a cache entry. Which means that you really need to not rely on the\n> cache (since it is very likely that the best candidate is still to be\n> found), and you still do lots of computation.\n>\n> You could cache the result of comparisons done by pack-objects, but that\n> cache ends up being large. You might remember that one of my very first\n> patches was a cache for recording negative delta finds (so we try to\n> delta A against B and find that it is not a good match, and record that\n> information). Even that cache was huge, and we ended up discarding it in\n> favor of Linus's much more sensible \"if two things are in the same pack\n> and not delta'd, then either they are not a good match, or something\n> else is in better\" heuristic. But one with full-on similarity scores\n> would be even bigger.\n\nYeah, I forgot about your negative cache. Also the older companion\nheuristics \"if a delta and its base are in an existing pack, use\nthat delta\" works well enough to make a positive cache unnecessary\n(and the \"rename similarity cache\" can only be a subset of such a\ncache).\n\nC.f. http://thread.gmane.org/gmane.comp.version-control.git/16223/focus=16267\n\n>> - If you declare blobs A and B are similar, it is likely that blobs\n>> C, D, E, ... that are created by making a series of small tweaks\n>> to B are also similar. Would it make more sense to introduce a\n>> concept of \"set of similar blobs\" instead of recording pairwise\n>> scores for (A,B), (A,C), (A,D), ... (B,C), (B,D), ...? If so,\n>> the body of per-dst loop in diffcore_rename() may become:\n>\n> Yes, this is the transitive bit I mentioned elsewhere. I think there are\n> dragons lurking there, as you end up with the edges of the set not\n> _really_ being that close to each other. You'd probably want some kind\n> of weighted association, like if A->B had 80% similarity, and B->C had\n> 90% similarity, then A->C would be 72%.\n\nI recall we discussed the transitivity when we were designing the\nbasic rename thing, and rejected it after we realized that it was\nunworkable. You may have a blob A, perform a large-ish edit to\nproduce B, and A and B may be similar by only 60%. You then may\nstart from the same A, perform another large-ish edit to produce C,\nand A and C may be similar by only 55%. Depending on the nature of\nthese two large-ish changes, B and C may be totally dissimilar, or\nif the changes are more or less in the same \"direction\", they may be\n95% similar.\n"},{"id":"196347","messageId":"CACsJy8CndopS7fg4mevFD5T0KJ85ba6jjhamrKDdKvKsWa_fQw@mail.gmail.com","threadId":"31151","inReplyTo":"20120801212719.GA16233@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-02T12:08:25Z","receivedAt":"2012-08-02T12:08:25Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Aug 2, 2012 at 4:27 AM, Jeff King wrote:\n> Yes, if you go with a commit-based approach, you can do either notes or\n> in-commit messages. In other words, I would break the solutions down as:\n>\n> 1. Store sha1+sha1 -> score mapping (i.e., what I suggested). This is\n> fundamentally a global store, not a per-commit store. For storage,\n> you can do one (or a combination) of:\n>\n> a. Store the mapping in some local file. Fast, but can't be shared.\n>\n> b. Store the mapping in a note (probably indexed by the destination\n> blob sha1). Less efficient, but easy to share.\n>\n> I implemented (1a). Implementing (1b) would be easy, but for a full-on\n> cache (especially for \"-C\"), I think the resulting size might be\n> prohibitive.\n\n(1a) is good regardless rename overrides. Why don't you polish and\nsubmit it? We can set some criteria to limit the cache size while\nkeeping computation reasonably low. Caching rename scores for file\npairs that has file size larger than a limit is one. Rename matrix\nsize could also be a candidate. We could even cache just rename scores\nfor recent commits (i.e. close to heads) only with the assumption that\npeople diff/apply recent commits more often.\n\n\n> All solutions under (2) suffer from the same problem: they are accurate\n> only for a single diff. For other diffs, you would either have to not\n> use the feature, or you would be stuck traversing the history and\n> assigning a temporary file identity (e.g., given commits A->B->C, and in\n> A->B we rename \"foo\" to \"bar\", the diff between A and C could discover\n> that A's \"foo\" corresponds to C's \"bar\").\n\nYeah. If we go with manual overrides, I expect users to deal with\nthese manually too. IOW they'll need to create a mapping for A->C\nthemselves. We can help detect that there are manual overrides in some\ncases, like merge, and let users know that manual overrides are\nignored. For merge, I think we can just check for all commits while\ntraversing looking for bases.\n\n> For this reason, I'm not sure that stored overrides like this are\n> generally useful in the long run. I think storage is useful for\n> _caching_ the results, because it doesn't have to be perfect; it just\n> helps with some repetitive queries. Whereas for overriding, I think it\n> is much more interesting to override _particular_ diff. E.g., to say \"I\n> am merging X and Y, and please pretend that Y renamed \"foo\" to \"bar\"\n> when you do rename detection.\n>\n> And in that sense, your \"git log\" example can be considered a\n> special-case of this: you are saying that the diff from $commit to\n> $commit^ is done frequently, so rather than saying \"please pretend...\"\n> each time, you would like to store the information forever. And storing\n> it in the commit message or a note is one way of doing that.\n\nYep, specifying rename overrides between two trees is probably better.\n\n> I don't think there's anything fundamentally _wrong_ with that, but I\n> kind of question its usefulness. In other words, what is the point in\n> doing so? If it is inform the user that semantically the commit did a\n> rename, even though the content changed enough that rename detection\n> does not find it, then I would argue that you should simply state it in\n> the commit message (or in a human-readable git-note, if it was only\n> realized after the fact).\n>\n> But there is not much point in making it machine-readable, since the\n> interesting machine-readable things we do with renames are:\n>\n> 1. Show the diff against the rename src, which can often be easier to\n> read. Except that if rename detection did not find it, it is\n> probably _not_ going to be easier to read.\n\nProbably. Still it helps \"git log --follow\" to follow the correct\ntrack in the 1% case that rename detection does go wrong.\n\n>\n> 2. Applying content to the destination of a merge. But you're almost\n> never doing the diff between a commit and its parent, so the\n> information would be useless.\n\nHaving a way to interfere rename detection, even manually, could be\ngood in this case if it reduces conflicts. We could feed rename\noverrides using command line.\n-- \nDuy\n"},{"id":"196387","messageId":"20120802223733.GA28217@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7vipd2e00g.fsf@alter.siamese.dyndns.org","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-02T22:37:33Z","receivedAt":"2012-08-02T22:37:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 01, 2012 at 03:10:55PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > On Tue, Jul 31, 2012 at 11:01:27PM -0700, Junio C Hamano wrote:\n> > ...\n> >> As we still have the pathname in this codepath, I am wondering if we\n> >> would benefit from custom \"content hash\" that knows the nature of\n> >> payload than the built-in similarity estimator, driven by the\n> >> attribute mechanism (if the latter is the case, that is).\n> >\n> > Hmm. Interesting. But I don't think that attributes are a good fit here.\n> > They are pathname based, so how do I apply anything related to\n> > similarity of a particular version by pathname? IOW, how does it apply\n> > in one tree but not another?\n> \n> When you move porn/0001.jpg in the preimage to naughty/00001.jpg in\n> the postimage, they both can hit \"*.jpg contentid=jpeg\" line in the\n> top-level .gitattribute file, and the contentid driver for jpeg type\n> may strip exif and hash the remainder bits in the image to come up\n> with a token you can use in a similar way as object ID is used in\n> the exact rename detection phase.\n> \n> Just thinking aloud.\n\nAh, I see. That still feels like way too specific a use case to me. A\nmuch more general use case to me would be a contentid driver which\nsplits the file into multiple chunks (which can be concatenated to\narrive at the original content), and marks chunks as \"OK to delta\" or\n\"not able to delta\". In other words, a content-specific version of the\nbup-style splitting that people have proposed.\n\nAssuming we split a jpeg into its EXIF bits (+delta) and its image bits\n(-delta), then you could do a fast rename or pack-objects comparison\nbetween two such files (in fact, with chunked object storage,\npack-objects can avoid looking at the image parts at all).\n\nHowever, it may be the case that such \"smart\" splitting is not\nnecessary, as stupid and generic bup-style splitting may be enough. I\nreally need to start playing with the patches you wrote last year that\nstarted in that direction.\n\n-Peff\n"},{"id":"196388","messageId":"20120802224155.GB28217@sigill.intra.peff.net","threadId":"31151","inReplyTo":"CACsJy8CndopS7fg4mevFD5T0KJ85ba6jjhamrKDdKvKsWa_fQw@mail.gmail.com","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-02T22:41:55Z","receivedAt":"2012-08-02T22:41:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 02, 2012 at 07:08:25PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > I implemented (1a). Implementing (1b) would be easy, but for a full-on\n> > cache (especially for \"-C\"), I think the resulting size might be\n> > prohibitive.\n> \n> (1a) is good regardless rename overrides. Why don't you polish and\n> submit it? We can set some criteria to limit the cache size while\n> keeping computation reasonably low. Caching rename scores for file\n> pairs that has file size larger than a limit is one. Rename matrix\n> size could also be a candidate. We could even cache just rename scores\n> for recent commits (i.e. close to heads) only with the assumption that\n> people diff/apply recent commits more often.\n\nI'll polish and share it. I'm still not 100% sure it's a good idea,\nbecause introducing an on-disk cache means we need to _manage_ that\ncache. How big will it be? Who will prune it when it gets too big? By\nwhat criteria? And so on.\n\nBut if it's all hidden behind a config option, then it won't hurt people\nwho don't use it. And people who do use it can gather data on how the\ncaches grow.\n\n> > All solutions under (2) suffer from the same problem: they are accurate\n> > only for a single diff. For other diffs, you would either have to not\n> > use the feature, or you would be stuck traversing the history and\n> > assigning a temporary file identity (e.g., given commits A->B->C, and in\n> > A->B we rename \"foo\" to \"bar\", the diff between A and C could discover\n> > that A's \"foo\" corresponds to C's \"bar\").\n> \n> Yeah. If we go with manual overrides, I expect users to deal with\n> these manually too. IOW they'll need to create a mapping for A->C\n> themselves. We can help detect that there are manual overrides in some\n> cases, like merge, and let users know that manual overrides are\n> ignored. For merge, I think we can just check for all commits while\n> traversing looking for bases.\n\nYeah, merges are a special case, in that we know the diff we perform\nwill always have a direct-ancestor relationship (since it is always\nbetween a tip and the merge base).\n\n> > But there is not much point in making it machine-readable, since the\n> > interesting machine-readable things we do with renames are:\n> >\n> > 1. Show the diff against the rename src, which can often be easier to\n> > read. Except that if rename detection did not find it, it is\n> > probably _not_ going to be easier to read.\n> \n> Probably. Still it helps \"git log --follow\" to follow the correct\n> track in the 1% case that rename detection does go wrong.\n\nThanks. I didn't think of --follow, but that is a good counterpoint to\nmy argument.\n\n> > 2. Applying content to the destination of a merge. But you're almost\n> > never doing the diff between a commit and its parent, so the\n> > information would be useless.\n> \n> Having a way to interfere rename detection, even manually, could be\n> good in this case if it reduces conflicts. We could feed rename\n> overrides using command line.\n\nYeah. I think I'd start with letting you feed pairs to diff_options,\ngive it a command-line option to see how useful it is, and then later on\nconsider a mechanism for extracting those pairs automatically from\ncommits or notes.\n\n-Peff\n"},{"id":"196389","messageId":"7v6290di1m.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120802223733.GA28217@sigill.intra.peff.net","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-02T22:51:17Z","receivedAt":"2012-08-02T22:51:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Wed, Aug 01, 2012 at 03:10:55PM -0700, Junio C Hamano wrote:\n> ...\n>> When you move porn/0001.jpg in the preimage to naughty/00001.jpg in\n>> the postimage, they both can hit \"*.jpg contentid=jpeg\" line in the\n>> top-level .gitattribute file, and the contentid driver for jpeg type\n>> may strip exif and hash the remainder bits in the image to come up\n>> with a token you can use in a similar way as object ID is used in\n>> the exact rename detection phase.\n>> \n>> Just thinking aloud.\n>\n> Ah, I see. That still feels like way too specific a use case to me. A\n> much more general use case to me would be a contentid driver which\n> splits the file into multiple chunks (which can be concatenated to\n> arrive at the original content), and marks chunks as \"OK to delta\" or\n> \"not able to delta\". In other words, a content-specific version of the\n> bup-style splitting that people have proposed.\n>\n> Assuming we split a jpeg into its EXIF bits (+delta) and its image bits\n> (-delta), then you could do a fast rename or pack-objects comparison\n> between two such files (in fact, with chunked object storage,\n> pack-objects can avoid looking at the image parts at all).\n>\n> However, it may be the case that such \"smart\" splitting is not\n> necessary, as stupid and generic bup-style splitting may be enough. I\n> really need to start playing with the patches you wrote last year that\n> started in that direction.\n\nI wasn't interested in \"packing split object representation\",\nactually. The idea was still within the context of \"rename\".\n"},{"id":"196390","messageId":"20120802225843.GA29208@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7v6290di1m.fsf@alter.siamese.dyndns.org","subject":"Re: [WIP PATCH] Manual rename correction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-02T22:58:44Z","receivedAt":"2012-08-02T22:58:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 02, 2012 at 03:51:17PM -0700, Junio C Hamano wrote:\n\n> > On Wed, Aug 01, 2012 at 03:10:55PM -0700, Junio C Hamano wrote:\n> > ...\n> >> When you move porn/0001.jpg in the preimage to naughty/00001.jpg in\n> >> the postimage, they both can hit \"*.jpg contentid=jpeg\" line in the\n> >> top-level .gitattribute file, and the contentid driver for jpeg type\n> >> may strip exif and hash the remainder bits in the image to come up\n> >> with a token you can use in a similar way as object ID is used in\n> >> the exact rename detection phase.\n> >> \n> >> Just thinking aloud.\n> >\n> > Ah, I see. That still feels like way too specific a use case to me. A\n> > much more general use case to me would be a contentid driver which\n> > splits the file into multiple chunks (which can be concatenated to\n> > arrive at the original content), and marks chunks as \"OK to delta\" or\n> > \"not able to delta\". In other words, a content-specific version of the\n> > bup-style splitting that people have proposed.\n> >\n> > Assuming we split a jpeg into its EXIF bits (+delta) and its image bits\n> > (-delta), then you could do a fast rename or pack-objects comparison\n> > between two such files (in fact, with chunked object storage,\n> > pack-objects can avoid looking at the image parts at all).\n> >\n> > However, it may be the case that such \"smart\" splitting is not\n> > necessary, as stupid and generic bup-style splitting may be enough. I\n> > really need to start playing with the patches you wrote last year that\n> > started in that direction.\n> \n> I wasn't interested in \"packing split object representation\",\n> actually. The idea was still within the context of \"rename\".\n\nBut it would work for rename, too. If you want to compare two files, the\ndriver would give you back { sha1_exif (+delta), sha1_image (-delta) }\nfor each file. You know the size of each chunk and the size of the total\nfile.\n\nThen you would just compare sha1_image for each entry. If they match,\nthen you have a lower bound on similarity of image_chunk_size /\ntotal_size. If they don't, then you have an upper bound of similarity of\n1-(image_chunk_size/total_size). In the former case, you can get the\nexact similarity by doing a real delta on the sha1_exif content. In the\nlatter case, you can either exit early (if you are already below the\nsimilarity threshold, which is likely), or possibly do the delta on the\nsha1_exif content to get an exact value.\n\nBut either way, you never had to do a direct comparison between the big\nimage data; you only needed to know the sha1s. And as a bonus, if you\ndid want to cache results, you can have an O(# of blobs) cache of the\nchunked sha1s of the chunked form (because the information is immutable\nfor a given sha1 and content driver). Whereas by caching the result of\nestimate_similarity, our worst-case cache is the square of that (because\nwe are storing sha1 pairs).\n\n-Peff\n"},{"id":"196460","messageId":"20120804170905.GA19267@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120802224155.GB28217@sigill.intra.peff.net","subject":"[PATCH 0/8] caching rename results","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:09:05Z","receivedAt":"2012-08-04T17:09:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 02, 2012 at 06:41:55PM -0400, Jeff King wrote:\n\n> > (1a) is good regardless rename overrides. Why don't you polish and\n> > submit it? We can set some criteria to limit the cache size while\n> > keeping computation reasonably low. Caching rename scores for file\n> > pairs that has file size larger than a limit is one. Rename matrix\n> > size could also be a candidate. We could even cache just rename scores\n> > for recent commits (i.e. close to heads) only with the assumption that\n> > people diff/apply recent commits more often.\n> \n> I'll polish and share it. I'm still not 100% sure it's a good idea,\n> because introducing an on-disk cache means we need to _manage_ that\n> cache. How big will it be? Who will prune it when it gets too big? By\n> what criteria? And so on.\n> \n> But if it's all hidden behind a config option, then it won't hurt people\n> who don't use it. And people who do use it can gather data on how the\n> caches grow.\n\nHere it is, all polished up. I'm still a little lukewarm on it for two\nreasons:\n\n 1. The whole idea. For the reasons above, I'm a little iffy on doing\n this cache at all. It does yield speedups, but only in some\n specific cases. So it's hidden behind a diff.renamecaches option\n and off by default.\n\n 2. The implementation is a little...gross. Long ago, I had written a\n type-generic map class for git using void pointers. It ended up\n complex and had problems with unaligned accesses. So I rewrote it\n using preprocessor macro expansion (e.g., you'd call\n IMPLEMENT_MAP(foo, const char *, int) or similar). But that wasn't\n quite powerful enough, as I really want conditional compilation\n inside the macro expansion, but you can't #ifdef.\n\n So I really wanted some kind of code generation that could do\n conditionals. Which you can do with the C preprocessor, but rather\n than expanding macros, you have to #include templates that expand\n based on parameters you've set. Which is kind of ugly and\n non-intuitive, but it does work. Look at patch 1 to see what I\n mean.\n\n Also, this sort of pre-processor hackery to create type-generic\n data structures is the first step on the road that eventually led\n to C++ being developed. And that scares me a little.\n\nSo yeah. Here it is. I'm not sure yet if it's a good idea or not.\n\n [1/8]: implement generic key/value map\n\nInfrastructure.\n\n [2/8]: map: add helper functions for objects as keys\n [3/8]: fast-export: use object to uint32 map instead of \"decorate\"\n [4/8]: decorate: use \"map\" for the underlying implementation\n\nThese ones are optional for this series, but since we are introducing\nthe infrastructure anyway (which is really just a generalized form of\nwhat \"decorate\" does), it offsets the code bloat.\n\n [5/8]: map: implement persistent maps\n [6/8]: implement metadata cache subsystem\n\nMore infrastructure.\n\n [7/8]: implement rename cache\n [8/8]: diff: optionally use rename cache\n\nAnd these are the actual rename cache.\n\n-Peff\n"},{"id":"196461","messageId":"20120804171038.GA19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 1/8] implement generic key/value map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:10:38Z","receivedAt":"2012-08-04T17:10:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It is frequently useful to have a fast, generic data\nstructure mapping keys to values. We already have something\nlike this in the \"decorate\" API, but it has two downsides:\n\n 1. The key type must always be a \"struct object *\".\n\n 2. The value type is a void pointer, which means it is\n inefficient and cumbersome for storing small values.\n One must either encode their value inside the void\n pointer, or allocate additional storage for the pointer\n to point to.\n\nThis patch introduces a generic map data structure, mapping\nkeys of arbitrary type to values of arbitrary type.\n\nOne possible strategy for implementation is to have a struct\nthat points to a sequence of bytes for each of the key and\nthe value, and to try to treat them as opaque in the code.\nHowever, this code gets complex, has a lot of casts, and\nruns afoul of violating alignment and strict aliasing rules.\n\nThis patch takes a different approach. We parameterize the\ntypes in each map and putting the declarations and\nimplementations inside macros. This lets the compiler see\nthe actual code, with its real types, and figure out things\nlike struct packing and alignment itself.\n\nSigned-off-by: Jeff King \n---\nThis is the one with the pre-processor grossness. Don't be _too_ scared\noff by the ugliness of test-map.c; it's also trying to be polymorphic\nwith respect to different maps, which makes it even uglier. See patches\n2 and 3 for a more reasonable application.\n\n .gitignore | 1 +\n Documentation/technical/api-map.txt | 214 ++++++++++++++++++++++++++++++++++++\n Makefile | 5 +\n map-decl.h | 22 ++++\n map-done.h | 19 ++++\n map-impl.h | 94 ++++++++++++++++\n map-init.h | 24 ++++\n t/t0007-map.sh | 50 +++++++++\n test-map.c | 182 ++++++++++++++++++++++++++++++\n 9 files changed, 611 insertions(+)\n create mode 100644 Documentation/technical/api-map.txt\n create mode 100644 map-decl.h\n create mode 100644 map-done.h\n create mode 100644 map-impl.h\n create mode 100644 map-init.h\n create mode 100755 t/t0007-map.sh\n create mode 100644 test-map.c\n\ndiff --git a/.gitignore b/.gitignore\nindex bb5c91e..c2bad89 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -184,6 +184,7 @@\n /test-genrandom\n /test-index-version\n /test-line-buffer\n+/test-map\n /test-match-trees\n /test-mergesort\n /test-mktemp\ndiff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt\nnew file mode 100644\nindex 0000000..f86b785\n--- /dev/null\n+++ b/Documentation/technical/api-map.txt\n@@ -0,0 +1,214 @@\n+map API\n+=======\n+\n+The map API is a system for efficiently mapping keys to values in memory. Items\n+are stored in a hash table for fast lookup; storage efficiency is achieved\n+through macro-based code generation, which lets the compiler store values\n+compactly in memory.\n+\n+Due to the code generation, there are two different facets of this API: macros\n+to build new types of mappings (i.e., generate new function and struct\n+definitions), and generated functions to store and retrieve values from a\n+particular mapping.\n+\n+\n+Related APIs\n+------------\n+\n+The hash API provides a similar key/value store. However, it does not deal with\n+hash collisions itself, leaving the caller to handle bucket management (but\n+this is a feature if you are interested in using the collisions as part of an\n+algorithm). Furthermore, it can store only void pointers, making storage of\n+small values inefficient and cumbersome.\n+\n+The decorate API provides a similar interface to map, but is restricted to\n+using \"struct object\" as the key, and a void pointer as the value.\n+\n+\n+Defining New Map Types\n+----------------------\n+\n+A map type is uniquely defined by the pair of its key and value types. To\n+define a new type, you must set up some preprocessor defines to specify\n+the key and values types, along with any special options for the\n+implementation. Then to instantiate the declaration of a map (i.e., the\n+bits that would go in a header file), include \"map-decl.h\". To\n+instantiate the implementation, include \"map-impl.h\". To clean up your\n+preprocessor options, include \"map-done.h\".\n+\n+The following map defines are available:\n+\n+`NAME`::\n+\n+\tRequired. The name of the map. This should syntactically be a C\n+\tidentifier (alphanumeric and underscore), and should describe\n+\tthe types involved in the map (e.g., `object_uint32` to map\n+\tobjects to 32-bit integers).\n+\n+`KEY_TYPE`::\n+\n+\tRequired. The C type of the key, as it will be stored in the\n+\thash (e.g., `struct object *` to store an object pointer).\n+\n+`PASS_KEY_BY_REF`::\n+\n+\tOptional. If defined, indicates that keys are a complex type\n+\tthat should be passed between functions using pointers.\n+\tOtherwise, keys are passed by value.\n+\n+`HASH`::\n+\n+\tRequired. A function that will convert an object of type\n+\t`KEY_TYPE` into an integer hash value.\n+\n+`KEY_EQUAL`::\n+\n+\tRequired. A function that will compare two keys, and return\n+\tnon-zero if and only if they are equal.\n+\n+`VALUE_TYPE`::\n+\n+\tRequired. The C type of the value, as it will be stored in the\n+\thash (e.g., `uint32_t` to store a 32-bit integer).\n+\n+`SENTINEL_NULL`::\n+\n+\tOptional. If defined, indicates that keys can store an all-zero\n+\tsentinel value (e.g., if the key is a pointer). This enables an\n+\toptimization to shrink the size of each map entry, at the cost\n+\tof not being able to store `NULL` key pointers in the map.\n+\n+\n+Data Structures\n+---------------\n+\n+Each defined map type will have its own structure (e.g., `map_object_uint32`).\n+\n+`struct map_NAME`::\n+\n+\tA single map object. This struct should be initialized to all-zeroes.\n+\tThe `nr` field specifies the number of items stored in the map. The\n+\t`size` field specifies the number of hash buckets allocated. The `hash`\n+\tfield stores the actual data. Callers should never need to look at\n+\tthese fields unless they are enumerating all elements of the map (see\n+\tthe example below).\n+\n+`struct map_entry_NAME`::\n+\n+\tA single key/value entry in the hash, which may or may not\n+\tcontain valid data. If `SENTINEL_NULL` is defined, then an empty\n+\tentry will have a NULL key; otherwise, there is a `used` field\n+\twhich will be zero in an empty entry (in which case the contents\n+\tof the `key` field are undefined). If the entry is empty, the\n+\tcontents of the `value` field is undefined. You should never\n+\tneed to use this type directly, unless you are enumerating all\n+\telements of a map.\n+\n+\n+Functions\n+---------\n+\n+Each defined map type will have its own set of access functions (e.g.,\n+`map_get_object_uint32`).\n+\n+`map_get_NAME(struct map_NAME *, KEY_TYPE key, VALUE_TYPE *value)`::\n+\n+\tRetrieve the value corresponding to `key`, returning it via the\n+\tpointer `value`. Returns 1 if an item was found, zero otherwise\n+\t(in which case `value` is unchanged). If `PASS_KEY_BY_REF` is\n+\tdefined, the key is passed in as a `const KEY_TYPE *`.\n+\n+`map_set_NAME(struct map_NAME *, KEY_TYPE key, VALUE_TYPE value, VALUE_TYPE *old)`::\n+\n+\tInsert a mapping from `key` to `value`. If a mapping for `key`\n+\talready existed, the previous value is copied into `old` (if it\n+\tis non-NULL) and the function returns 1. Otherwise, the function\n+\treturns 0. If `PASS_KEY_BY_REF` or `PASS_VALUE_BY_REF` is\n+\tdefined, the key and value are passed in as `const KEY_TYPE *`\n+\tand `const VALUE_TYPE *`, respectively.\n+\n+\n+Examples\n+--------\n+\n+Declare a new mapping type of strings to integers:\n+\n+-------------------------------------------------------------------\n+/* in map-string-int.h */\n+#define NAME string_int\n+#define KEY_TYPE const char *\n+#define VALUE_TYPE int\n+#include \"map-decl.h\"\n+#include \"map-done.h\"\n+-------------------------------------------------------------------\n+\n+Implement the mapping:\n+\n+-------------------------------------------------------------------\n+/* in map-string-int.c */\n+\n+static unsigned int hash_string(const char * const *strp, unsigned int n)\n+{\n+\tunsigned long hash = 0;\n+\tconst char *p;\n+\n+\tfor (p = *strp; *p; p++)\n+\t\thash = (hash << 5) + *p;\n+\treturn hash % n;\n+}\n+\n+static unsigned int string_equal(const char * const *a, const char * const *b)\n+{\n+\treturn !strcmp(*a, *b);\n+}\n+\n+#define NAME string_int\n+#define KEY_TYPE const char *\n+#define VALUE_TYPE int\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\n+-------------------------------------------------------------------\n+\n+Store and retrieve integers by string (note that the map will not\n+duplicate the strings; the type is defined to merely store the\n+pointer values).\n+\n+-------------------------------------------------------------------\n+#include \"map-string-int.h\"\n+\n+static struct map_string_int foos;\n+\n+void store_foo(const char *s, int foo)\n+{\n+\tint old;\n+\tif (map_set_object_int(&foos, xstrdup(s), foo, &old))\n+\t\tprintf(\"old value was %d\\n\", old);\n+}\n+\n+void print_foo(const char *s)\n+{\n+\tint v;\n+\n+\tif (map_get_object_int(&foos, s, &v))\n+\t\tprintf(\"foo: %d\\n\", v);\n+\telse\n+\t\tprintf(\"no such foo\\n\");\n+}\n+-------------------------------------------------------------------\n+\n+Iterate over all map entries:\n+\n+-------------------------------------------------------------------\n+void dump_foos(void)\n+{\n+\tint i;\n+\n+\tprintf(\"there are %u foos:\\n\", foos.nr);\n+\n+\tfor (i = 0; i < foos.size; i++) {\n+\t\tstruct map_entry_string_int *e = foos.hash + i;\n+\t\tif (e->used)\n+\t\t\tprintf(\"%s -> %d\\n\", e->key, e->value);\n+\t}\n+}\n+-------------------------------------------------------------------\ndiff --git a/Makefile b/Makefile\nindex 4b58b91..d512f27 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -491,6 +491,7 @@ TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n TEST_PROGRAMS_NEED_X += test-genrandom\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-line-buffer\n+TEST_PROGRAMS_NEED_X += test-map\n TEST_PROGRAMS_NEED_X += test-match-trees\n TEST_PROGRAMS_NEED_X += test-mergesort\n TEST_PROGRAMS_NEED_X += test-mktemp\n@@ -628,6 +629,10 @@ LIB_H += list-objects.h\n LIB_H += ll-merge.h\n LIB_H += log-tree.h\n LIB_H += mailmap.h\n+LIB_H += map-decl.h\n+LIB_H += map-done.h\n+LIB_H += map-impl.h\n+LIB_H += map-init.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n LIB_H += mergesort.h\ndiff --git a/map-decl.h b/map-decl.h\nnew file mode 100644\nindex 0000000..7d4daaf\n--- /dev/null\n+++ b/map-decl.h\n@@ -0,0 +1,22 @@\n+#include \"map-init.h\"\n+\n+struct THIS(map_entry) {\n+\tKEY_TYPE key;\n+\tVALUE_TYPE value;\n+#ifndef SENTINEL_NULL\n+\tunsigned used:1;\n+#endif\n+};\n+\n+struct THIS(map) {\n+\tunsigned int size, nr;\n+\tstruct THIS(map_entry) *hash;\n+};\n+\n+extern int THIS(map_get)(struct THIS(map) *,\n+\t\t\t KEY_ARG key,\n+\t\t\t VALUE_TYPE *value);\n+extern int THIS(map_set)(struct THIS(map) *,\n+\t\t\t KEY_ARG key,\n+\t\t\t VALUE_ARG value,\n+\t\t\t VALUE_TYPE *old);\ndiff --git a/map-done.h b/map-done.h\nnew file mode 100644\nindex 0000000..65983d3\n--- /dev/null\n+++ b/map-done.h\n@@ -0,0 +1,19 @@\n+#undef NAME\n+#undef KEY_TYPE\n+#undef KEY_ARG\n+#undef PASS_KEY_BY_REF\n+#undef key_ref\n+#undef key_deref\n+#undef VALUE_TYPE\n+#undef VALUE_ARG\n+#undef PASS_VALUE_BY_REF\n+#undef value_ref\n+#undef value_deref\n+#undef HASH\n+#undef KEY_EQUAL\n+#undef SENTINEL_NULL\n+#undef hash_used\n+#undef PASTE2\n+#undef PASTE\n+#undef THIS\n+#undef MAP_UTIL_INITIALIZED\ndiff --git a/map-impl.h b/map-impl.h\nnew file mode 100644\nindex 0000000..844b7f1\n--- /dev/null\n+++ b/map-impl.h\n@@ -0,0 +1,94 @@\n+#include \"map-init.h\"\n+\n+#ifdef PASS_KEY_BY_REF\n+#define key_ref(x) (&(x))\n+#define key_deref(x) (*(x))\n+#else\n+#define key_ref(x) (x)\n+#define key_deref(x) (x)\n+#endif\n+\n+#ifdef PASS_VALUE_BY_REF\n+#define value_ref(x) (&(x))\n+#define value_deref(x) (*(x))\n+#else\n+#define value_ref(x) (x)\n+#define value_deref(x) (x)\n+#endif\n+\n+#ifdef SENTINEL_NULL\n+#define hash_used(x) (x)->key\n+#else\n+#define hash_used(x) (x)->used\n+#endif\n+\n+static int THIS(map_insert)(struct THIS(map) *m,\n+\t\t\t KEY_ARG key,\n+\t\t\t VALUE_ARG value,\n+\t\t\t VALUE_TYPE *old)\n+{\n+\tunsigned int j;\n+\n+\tfor (j = HASH(key, m->size); hash_used(&m->hash[j]); j = (j+1) % m->size) {\n+\t\tif (KEY_EQUAL(key_ref(m->hash[j].key), key)) {\n+\t\t\tif (old)\n+\t\t\t\t*old = m->hash[j].value;\n+\t\t\tm->hash[j].value = value_deref(value);\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\tm->hash[j].key = key_deref(key);\n+\tm->hash[j].value = value_deref(value);\n+#ifndef SENTINEL_NULL\n+\tm->hash[j].used = 1;\n+#endif\n+\tm->nr++;\n+\treturn 0;\n+}\n+\n+static void THIS(map_grow)(struct THIS(map) *m)\n+{\n+\tstruct THIS(map_entry) *old_hash = m->hash;\n+\tunsigned int old_size = m->size;\n+\tunsigned int i;\n+\n+\tm->size = (old_size + 1000) * 3 / 2;\n+\tm->hash = xcalloc(m->size, sizeof(*m->hash));\n+\tm->nr = 0;\n+\n+\tfor (i = 0; i < old_size; i++) {\n+\t\tif (!hash_used(&old_hash[i]))\n+\t\t\tcontinue;\n+\t\tTHIS(map_insert)(m, key_ref(old_hash[i].key), value_ref(old_hash[i].value), NULL);\n+\t}\n+\tfree(old_hash);\n+}\n+\n+int THIS(map_set)(struct THIS(map) *m,\n+\t\t KEY_ARG key,\n+\t\t VALUE_ARG value,\n+\t\t VALUE_TYPE *old)\n+{\n+\tif (m->nr >= m->size * 2 / 3)\n+\t\tTHIS(map_grow)(m);\n+\treturn THIS(map_insert)(m, key, value, old);\n+}\n+\n+int THIS(map_get)(struct THIS(map) *m,\n+\t\t KEY_ARG key,\n+\t\t VALUE_TYPE *value)\n+{\n+\tunsigned int j;\n+\n+\tif (!m->size)\n+\t\treturn 0;\n+\n+\tfor (j = HASH(key, m->size); hash_used(&m->hash[j]); j = (j+1) % m->size) {\n+\t\tif (KEY_EQUAL(key_ref(m->hash[j].key), key)) {\n+\t\t\t*value = m->hash[j].value;\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\ndiff --git a/map-init.h b/map-init.h\nnew file mode 100644\nindex 0000000..1d2c4b3\n--- /dev/null\n+++ b/map-init.h\n@@ -0,0 +1,24 @@\n+#ifndef MAP_UTIL_INITIALIZED\n+#define MAP_UTIL_INITIALIZED\n+\n+/*\n+ * C preprocessor recursion hackery. Macros are not expanded next\n+ * to ## tokens, so we have to add an extra level of indirection.\n+ */\n+#define PASTE2(x,y) x ## _ ## y\n+#define PASTE(x,y) PASTE2(x,y)\n+#define THIS(x) PASTE(x, NAME)\n+\n+#ifdef PASS_KEY_BY_REF\n+#define KEY_ARG const KEY_TYPE *\n+#else\n+#define KEY_ARG KEY_TYPE\n+#endif\n+\n+#ifdef PASS_VALUE_BY_REF\n+#define VALUE_ARG const VALUE_TYPE *\n+#else\n+#define VALUE_ARG VALUE_TYPE\n+#endif\n+\n+#endif\ndiff --git a/t/t0007-map.sh b/t/t0007-map.sh\nnew file mode 100755\nindex 0000000..b5845f4\n--- /dev/null\n+++ b/t/t0007-map.sh\n@@ -0,0 +1,50 @@\n+#!/bin/sh\n+\n+test_description='basic tests for the map implementation'\n+. ./test-lib.sh\n+\n+test_expect_success 'setup input' '\n+\tcat >input <<-\\EOF\n+\tf 6\n+\tb 2\n+\ta 1\n+\te 5\n+\ti 9\n+\tg 7\n+\td 4\n+\th 8\n+\tc 3\n+\tEOF\n+'\n+\n+for type in pointer struct; do\n+\ttest_expect_success \"look up elements ($type)\" \"\n+\t\tcat >expect <<-\\EOF &&\n+\t\ta: 1\n+\t\ti: 9\n+\t\td: 4\n+\t\tEOF\n+\t\ttest-map $type find a i d actual &&\n+\t\ttest_cmp expect actual\n+\t\"\n+\n+\ttest_expect_success \"iterate over elements ($type)\" \"\n+\t\tcat >expect <<-\\EOF &&\n+\t\ta: 1\n+\t\tb: 2\n+\t\tc: 3\n+\t\td: 4\n+\t\te: 5\n+\t\tf: 6\n+\t\tg: 7\n+\t\th: 8\n+\t\ti: 9\n+\t\tEOF\n+\t\ttest-map $type print actual &&\n+\t\t# iteration order is hash-dependent, so we must sort\n+\t\tsort actual.sorted &&\n+\t\ttest_cmp expect actual.sorted\n+\t\"\n+done\n+\n+test_done\ndiff --git a/test-map.c b/test-map.c\nnew file mode 100644\nindex 0000000..b5f74a1\n--- /dev/null\n+++ b/test-map.c\n@@ -0,0 +1,182 @@\n+#include \"git-compat-util.h\"\n+\n+static const char usage_msg[] =\n+\"test-map [args]\";\n+\n+static inline unsigned int hash_string(const char *str, unsigned int n)\n+{\n+\tunsigned long hash = 0;\n+\n+\tfor (; *str; str++)\n+\t\thash = (hash << 5) + *str;\n+\treturn hash % n;\n+}\n+\n+static inline unsigned int string_equal(const char *a, const char *b)\n+{\n+\treturn !strcmp(a, b);\n+}\n+\n+#define NAME string_int\n+#define KEY_TYPE const char *\n+#define VALUE_TYPE int\n+#define HASH hash_string\n+#define KEY_EQUAL string_equal\n+#define SENTINEL_NULL\n+#include \"map-decl.h\"\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\n+\n+struct foo {\n+\tchar buf[10];\n+};\n+\n+static inline unsigned int hash_foo(const struct foo *f, unsigned int n)\n+{\n+\treturn hash_string(f->buf, n);\n+}\n+\n+static inline unsigned int foo_equal(const struct foo *a, const struct foo *b)\n+{\n+\treturn string_equal(a->buf, b->buf);\n+}\n+\n+#define NAME foo_foo\n+#define KEY_TYPE struct foo\n+#define VALUE_TYPE struct foo\n+#define HASH hash_foo\n+#define KEY_EQUAL foo_equal\n+#define PASS_KEY_BY_REF\n+#define PASS_VALUE_BY_REF\n+#include \"map-decl.h\"\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\n+\n+static void read_map(void *vm,\n+\t\t void (*store)(void *, const char *, const char *))\n+{\n+\tchar buf[1024];\n+\n+\twhile (fgets(buf, sizeof(buf), stdin)) {\n+\t\tchar *delim;\n+\n+\t\tif (strlen(buf) > 0 && buf[strlen(buf)-1] == '\\n')\n+\t\t\tbuf[strlen(buf)-1] = '\\0';\n+\n+\t\tdelim = strchr(buf, ' ');\n+\t\tif (!delim)\n+\t\t\tdie(\"invalid input: %s\", buf);\n+\t\t*delim++ = '\\0';\n+\n+\t\tstore(vm, buf, delim);\n+\t}\n+}\n+\n+static void store_string_int(void *vm, const char *k, const char *v)\n+{\n+\tstruct map_string_int *m = vm;\n+\tmap_set_string_int(m, xstrdup(k), atoi(v), NULL);\n+}\n+\n+static void store_foo_foo(void *vm, const char *k, const char *v)\n+{\n+\tstruct map_foo_foo *m = vm;\n+\tstruct foo kf, vf;\n+\tsnprintf(kf.buf, sizeof(kf.buf), \"%s\", k);\n+\tsnprintf(vf.buf, sizeof(vf.buf), \"%s\", v);\n+\tmap_set_foo_foo(m, &kf, &vf, NULL);\n+}\n+\n+static int fetch_string_int(void *vm, const char *k)\n+{\n+\tstruct map_string_int *m = vm;\n+\tint value;\n+\tif (map_get_string_int(m, k, &value))\n+\t\treturn value;\n+\treturn 0;\n+}\n+\n+static int fetch_foo_foo(void *vm, const char *k)\n+{\n+\tstruct map_foo_foo *m = vm;\n+\tstruct foo key, value;\n+\tsnprintf(key.buf, sizeof(key.buf), \"%s\", k);\n+\tif (map_get_foo_foo(m, &key, &value))\n+\t\treturn atoi(value.buf);\n+\treturn 0;\n+}\n+\n+static void print_string_int(void *vm)\n+{\n+\tstruct map_string_int *m = vm;\n+\tint i;\n+\tfor (i = 0; i < m->size; i++) {\n+\t\tstruct map_entry_string_int *e = m->hash + i;\n+\n+\t\tif (e->key)\n+\t\t\tprintf(\"%s: %d\\n\", e->key, e->value);\n+\t}\n+}\n+\n+static void print_foo_foo(void *vm)\n+{\n+\tstruct map_foo_foo *m = vm;\n+\tint i;\n+\tfor (i = 0; i < m->size; i++) {\n+\t\tstruct map_entry_foo_foo *e = m->hash + i;\n+\n+\t\tif (e->used)\n+\t\t\tprintf(\"%s: %s\\n\", e->key.buf, e->value.buf);\n+\t}\n+}\n+\n+static void do_op(void *vm,\n+\t\t void (*print)(void *),\n+\t\t int (*fetch)(void *, const char *),\n+\t\t const char **argv)\n+{\n+\tconst char *op = *argv++;\n+\tif (!op)\n+\t\tusage(usage_msg);\n+\n+\tif (!strcmp(op, \"print\"))\n+\t\tprint(vm);\n+\telse if (!strcmp(op, \"find\")) {\n+\t\tfor (; *argv; argv++) {\n+\t\t\tconst char *key = *argv;\n+\t\t\tint value = fetch(vm, key);\n+\n+\t\t\tif (value)\n+\t\t\t\tprintf(\"%s: %d\\n\", key, value);\n+\t\t\telse\n+\t\t\t\tprintf(\"%s: not found\\n\", key);\n+\t\t}\n+\t}\n+\telse\n+\t\tusage(usage_msg);\n+}\n+\n+int main(int argc, const char **argv)\n+{\n+\tconst char *type;\n+\n+\targv++;\n+\ttype = *argv++;\n+\tif (!type)\n+\t usage(usage_msg);\n+\n+\tif (!strcmp(type, \"pointer\")) {\n+\t\tstruct map_string_int m = {0};\n+\t\tread_map(&m, store_string_int);\n+\t\tdo_op(&m, print_string_int, fetch_string_int, argv);\n+\t}\n+\telse if (!strcmp(type, \"struct\")) {\n+\t\tstruct map_foo_foo m = {0};\n+\t\tread_map(&m, store_foo_foo);\n+\t\tdo_op(&m, print_foo_foo, fetch_foo_foo, argv);\n+\t}\n+\telse\n+\t\tusage(usage_msg);\n+\n+\treturn 0;\n+}\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196462","messageId":"20120804171047.GB19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 2/8] map: add helper functions for objects as keys","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:10:47Z","receivedAt":"2012-08-04T17:10:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"These functions can be used as HASH and KEY_EQUAL functions\nwhen defining new maps with \"struct object *\" as their key.\n\nSigned-off-by: Jeff King \n---\n Makefile | 1 +\n map-object.h | 19 +++++++++++++++++++\n 2 files changed, 20 insertions(+)\n create mode 100644 map-object.h\n\ndiff --git a/Makefile b/Makefile\nindex d512f27..1d29a95 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -633,6 +633,7 @@ LIB_H += map-decl.h\n LIB_H += map-done.h\n LIB_H += map-impl.h\n LIB_H += map-init.h\n+LIB_H += map-object.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n LIB_H += mergesort.h\ndiff --git a/map-object.h b/map-object.h\nnew file mode 100644\nindex 0000000..4f98413\n--- /dev/null\n+++ b/map-object.h\n@@ -0,0 +1,19 @@\n+#ifndef MAP_OBJECT_H\n+#define MAP_OBJECT_H\n+\n+#include \"object.h\"\n+\n+static unsigned int hash_obj(const struct object *obj, unsigned int n)\n+{\n+\tunsigned int hash;\n+\n+\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n+\treturn hash % n;\n+}\n+\n+static int obj_equal(const struct object *a, const struct object *b)\n+{\n+\treturn a == b;\n+}\n+\n+#endif /* MAP_OBJECT_H */\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196464","messageId":"20120804171103.GC19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 3/8] fast-export: use object to uint32 map instead of \"decorate\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:11:03Z","receivedAt":"2012-08-04T17:11:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Previously we encoded the \"mark\" mapping inside the \"void *\"\nfield of a \"struct decorate\". It's a little more natural for\nus to do so using a data structure made for holding actual\nvalues.\n\nSigned-off-by: Jeff King \n---\n builtin/fast-export.c | 46 +++++++++++++++++++++-------------------------\n 1 file changed, 21 insertions(+), 25 deletions(-)\n\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 9ab6db3..03e8f5f 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -12,7 +12,7 @@\n #include \"diffcore.h\"\n #include \"log-tree.h\"\n #include \"revision.h\"\n-#include \"decorate.h\"\n+#include \"map-object.h\"\n #include \"string-list.h\"\n #include \"utf8.h\"\n #include \"parse-options.h\"\n@@ -61,7 +61,17 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,\n \treturn 0;\n }\n \n-static struct decoration idnums;\n+#define NAME object_uint32\n+#define KEY_TYPE struct object *\n+#define VALUE_TYPE uint32_t\n+#define HASH hash_obj\n+#define KEY_EQUAL obj_equal\n+#define SENTINEL_NULL\n+#include \"map-decl.h\"\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\n+\n+static struct map_object_uint32 idnums;\n static uint32_t last_idnum;\n \n static int has_unshown_parent(struct commit *commit)\n@@ -75,20 +85,9 @@ static int has_unshown_parent(struct commit *commit)\n \treturn 0;\n }\n \n-/* Since intptr_t is C99, we do not use it here */\n-static inline uint32_t *mark_to_ptr(uint32_t mark)\n-{\n-\treturn ((uint32_t *)NULL) + mark;\n-}\n-\n-static inline uint32_t ptr_to_mark(void * mark)\n-{\n-\treturn (uint32_t *)mark - (uint32_t *)NULL;\n-}\n-\n static inline void mark_object(struct object *object, uint32_t mark)\n {\n-\tadd_decoration(&idnums, object, mark_to_ptr(mark));\n+\tmap_set_object_uint32(&idnums, object, mark, NULL);\n }\n \n static inline void mark_next_object(struct object *object)\n@@ -98,10 +97,9 @@ static inline void mark_next_object(struct object *object)\n \n static int get_object_mark(struct object *object)\n {\n-\tvoid *decoration = lookup_decoration(&idnums, object);\n-\tif (!decoration)\n-\t\treturn 0;\n-\treturn ptr_to_mark(decoration);\n+\tuint32_t ret = 0;\n+\tmap_get_object_uint32(&idnums, object, &ret);\n+\treturn ret;\n }\n \n static void show_progress(void)\n@@ -557,8 +555,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)\n static void export_marks(char *file)\n {\n \tunsigned int i;\n-\tuint32_t mark;\n-\tstruct object_decoration *deco = idnums.hash;\n \tFILE *f;\n \tint e = 0;\n \n@@ -567,15 +563,15 @@ static void export_marks(char *file)\n \t\tdie_errno(\"Unable to open marks file %s for writing.\", file);\n \n \tfor (i = 0; i < idnums.size; i++) {\n-\t\tif (deco->base && deco->base->type == 1) {\n-\t\t\tmark = ptr_to_mark(deco->decoration);\n-\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", mark,\n-\t\t\t\tsha1_to_hex(deco->base->sha1)) < 0) {\n+\t\tconst struct map_entry_object_uint32 *m = idnums.hash + i;\n+\n+\t\tif (m->key && m->key->type == 1) {\n+\t\t\tif (fprintf(f, \":%\"PRIu32\" %s\\n\", m->value,\n+\t\t\t\tsha1_to_hex(m->key->sha1)) < 0) {\n \t\t\t e = 1;\n \t\t\t break;\n \t\t\t}\n \t\t}\n-\t\tdeco++;\n \t}\n \n \te |= ferror(f);\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196463","messageId":"20120804171115.GD19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 4/8] decorate: use \"map\" for the underlying implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:11:15Z","receivedAt":"2012-08-04T17:11:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The decoration API maps objects to void pointers. This is a\nsubset of what the map API is capable of, so let's get rid\nof the duplicate implementation.\n\nWe could just fix all callers of decorate to call the map\nAPI directly. However, the map API is very generic since it\nis meant to handle any type. In particular, it can't use\nsentinel values like \"NULL\" to indicate \"entry not found\"\n(since it doesn't know whether the type can represent such a\nsentinel value), which makes the interface slightly more\ncomplicated.\n\nInstead, let's keep the existing decorate API as a wrapper\non top of map. No callers need to be updated at all.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-decorate.txt | 38 +++++++++++++-\n Makefile | 3 ++\n decorate.c | 85 +++-----------------------------\n decorate.h | 10 ++--\n map-object-void-params.h | 6 +++\n map-object-void.c | 7 +++\n map-object-void.h | 8 +++\n 7 files changed, 70 insertions(+), 87 deletions(-)\n create mode 100644 map-object-void-params.h\n create mode 100644 map-object-void.c\n create mode 100644 map-object-void.h\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex 1d52a6c..3c1197a 100644\n--- a/Documentation/technical/api-decorate.txt\n+++ b/Documentation/technical/api-decorate.txt\n@@ -1,6 +1,40 @@\n decorate API\n ============\n \n-Talk about \n+The decorate API is a system for efficiently mapping objects to values\n+in memory. It is slightly slower than an actual member of an object\n+struct (because it incurs a hash lookup), but it uses less memory when\n+the mapping is not in use, or when the number of decorated objects is\n+small compared to the total number of objects.\n \n-(Linus)\n+The decorate API is a special form of the `map` link:api-map.html[map\n+API]. It has slightly simpler calling conventions, but only use objects\n+as keys, and can only store void pointers as values.\n+\n+\n+Data Structures\n+---------------\n+\n+`struct decoration`::\n+\n+\tThis structure represents a single mapping of objects to values.\n+\tThe `name` field is not used by the decorate API itself, but may\n+\tbe used by calling code. The `map` field represents the actual\n+\tmapping of objects to void pointers (see the\n+\tlink:api-map.html[map API] for details).\n+\n+\n+Functions\n+---------\n+\n+`add_decoration`::\n+\n+\tAdd a mapping from an object to a void pointer. If there was a\n+\tprevious value for this object, the function returns this value;\n+\totherwise, the function returns NULL.\n+\n+`lookup_decoration`::\n+\n+\tRetrieve the stored value pointer for an object from the\n+\tmapping. The return value is the value pointer, or `NULL` if\n+\tthere is no value for this object.\ndiff --git a/Makefile b/Makefile\nindex 1d29a95..7684a76 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -633,6 +633,8 @@ LIB_H += map-decl.h\n LIB_H += map-done.h\n LIB_H += map-impl.h\n LIB_H += map-init.h\n+LIB_H += map-object-void-params.h\n+LIB_H += map-object-void.h\n LIB_H += map-object.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n@@ -747,6 +749,7 @@ LIB_OBJS += ll-merge.o\n LIB_OBJS += lockfile.o\n LIB_OBJS += log-tree.o\n LIB_OBJS += mailmap.o\n+LIB_OBJS += map-object-void.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..31e9656 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -1,88 +1,17 @@\n-/*\n- * decorate.c - decorate a git object with some arbitrary\n- * data.\n- */\n #include \"cache.h\"\n-#include \"object.h\"\n #include \"decorate.h\"\n \n-static unsigned int hash_obj(const struct object *obj, unsigned int n)\n-{\n-\tunsigned int hash;\n-\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n-}\n-\n-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n-{\n-\tint size = n->size;\n-\tstruct object_decoration *hash = n->hash;\n-\tunsigned int j = hash_obj(base, size);\n-\n-\twhile (hash[j].base) {\n-\t\tif (hash[j].base == base) {\n-\t\t\tvoid *old = hash[j].decoration;\n-\t\t\thash[j].decoration = decoration;\n-\t\t\treturn old;\n-\t\t}\n-\t\tif (++j >= size)\n-\t\t\tj = 0;\n-\t}\n-\thash[j].base = base;\n-\thash[j].decoration = decoration;\n-\tn->nr++;\n-\treturn NULL;\n-}\n-\n-static void grow_decoration(struct decoration *n)\n-{\n-\tint i;\n-\tint old_size = n->size;\n-\tstruct object_decoration *old_hash = n->hash;\n-\n-\tn->size = (old_size + 1000) * 3 / 2;\n-\tn->hash = xcalloc(n->size, sizeof(struct object_decoration));\n-\tn->nr = 0;\n-\n-\tfor (i = 0; i < old_size; i++) {\n-\t\tconst struct object *base = old_hash[i].base;\n-\t\tvoid *decoration = old_hash[i].decoration;\n-\n-\t\tif (!base)\n-\t\t\tcontinue;\n-\t\tinsert_decoration(n, base, decoration);\n-\t}\n-\tfree(old_hash);\n-}\n-\n-/* Add a decoration pointer, return any old one */\n void *add_decoration(struct decoration *n, const struct object *obj,\n-\t\tvoid *decoration)\n+\t\t void *decoration)\n {\n-\tint nr = n->nr + 1;\n-\n-\tif (nr > n->size * 2 / 3)\n-\t\tgrow_decoration(n);\n-\treturn insert_decoration(n, obj, decoration);\n+\tvoid *ret = NULL;\n+\tmap_set_object_void(&n->map, obj, decoration, &ret);\n+\treturn ret;\n }\n \n-/* Lookup a decoration pointer */\n void *lookup_decoration(struct decoration *n, const struct object *obj)\n {\n-\tunsigned int j;\n-\n-\t/* nothing to lookup */\n-\tif (!n->size)\n-\t\treturn NULL;\n-\tj = hash_obj(obj, n->size);\n-\tfor (;;) {\n-\t\tstruct object_decoration *ref = n->hash + j;\n-\t\tif (ref->base == obj)\n-\t\t\treturn ref->decoration;\n-\t\tif (!ref->base)\n-\t\t\treturn NULL;\n-\t\tif (++j == n->size)\n-\t\t\tj = 0;\n-\t}\n+\tvoid *ret = NULL;\n+\tmap_get_object_void(&n->map, obj, &ret);\n+\treturn ret;\n }\ndiff --git a/decorate.h b/decorate.h\nindex e732804..c58acbc 100644\n--- a/decorate.h\n+++ b/decorate.h\n@@ -1,15 +1,11 @@\n #ifndef DECORATE_H\n #define DECORATE_H\n \n-struct object_decoration {\n-\tconst struct object *base;\n-\tvoid *decoration;\n-};\n+#include \"map-object-void.h\"\n \n struct decoration {\n-\tconst char *name;\n-\tunsigned int size, nr;\n-\tstruct object_decoration *hash;\n+\tchar *name;\n+\tstruct map_object_void map;\n };\n \n extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);\ndiff --git a/map-object-void-params.h b/map-object-void-params.h\nnew file mode 100644\nindex 0000000..471fbdc\n--- /dev/null\n+++ b/map-object-void-params.h\n@@ -0,0 +1,6 @@\n+#define NAME object_void\n+#define KEY_TYPE const struct object *\n+#define VALUE_TYPE void *\n+#define HASH hash_obj\n+#define KEY_EQUAL obj_equal\n+#define SENTINEL_NULL\ndiff --git a/map-object-void.c b/map-object-void.c\nnew file mode 100644\nindex 0000000..4934642\n--- /dev/null\n+++ b/map-object-void.c\n@@ -0,0 +1,7 @@\n+#include \"cache.h\"\n+#include \"map-object-void.h\"\n+\n+#include \"map-object.h\"\n+#include \"map-object-void-params.h\"\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\ndiff --git a/map-object-void.h b/map-object-void.h\nnew file mode 100644\nindex 0000000..b4bc64d\n--- /dev/null\n+++ b/map-object-void.h\n@@ -0,0 +1,8 @@\n+#ifndef MAP_OBJECT_VOID_H\n+#define MAP_OBJECT_VOID_H\n+\n+#include \"map-object-void-params.h\"\n+#include \"map-decl.h\"\n+#include \"map-done.h\"\n+\n+#endif /* MAP_OBJECT_VOID_H */\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196465","messageId":"20120804171130.GE19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 5/8] map: implement persistent maps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:11:30Z","receivedAt":"2012-08-04T17:11:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It's sometimes useful to keep a mapping across program\ninvocations (e.g., because a space/time tradeoff makes it\nworth keeping a cache of calculated metadata for some\nobjects).\n\nThis adds a persistent version of the map API which can be\nbacked by a flat memory store (like an mmap'd file). By\nitself, it's not very pleasant to use, as the caller is\nresponsible for actually opening and mapping files. But it\nprovides the building blocks for disk caches, which will\ncome in the next patch.\n\nSigned-off-by: Jeff King \n---\n .gitignore | 1 +\n Documentation/technical/api-map.txt | 77 +++++++++++++++++++\n Makefile | 1 +\n map-decl.h | 18 +++++\n map-impl.h | 148 ++++++++++++++++++++++++++++++++++++\n t/t0007-map.sh | 24 ++++++\n test-map-persist.c | 125 ++++++++++++++++++++++++++++++\n 7 files changed, 394 insertions(+)\n create mode 100644 test-map-persist.c\n\ndiff --git a/.gitignore b/.gitignore\nindex c2bad89..14350f4 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -185,6 +185,7 @@\n /test-index-version\n /test-line-buffer\n /test-map\n+/test-map-persist\n /test-match-trees\n /test-mergesort\n /test-mktemp\ndiff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt\nindex f86b785..256bddf 100644\n--- a/Documentation/technical/api-map.txt\n+++ b/Documentation/technical/api-map.txt\n@@ -25,6 +25,21 @@ The decorate API provides a similar interface to map, but is restricted to\n using \"struct object\" as the key, and a void pointer as the value.\n \n \n+Persistent Maps\n+---------------\n+\n+Maps come in two flavors: persistent and in-core. In-core maps are\n+represented by a hash table, and can contain any C type. Persistent maps\n+are backed by flat storage, such as an mmap'd file, and store values\n+between program runs. Key and value types must be serializable to\n+fixed-width byte values.\n+\n+The flat storage is a sorted array of key/value pairs, with no\n+delimiters between pairs or between elements of a pair. Persistent maps\n+use an in-core map for newly-added values, and then merge the new\n+values into the flat storage on request.\n+\n+\n Defining New Map Types\n ----------------------\n \n@@ -78,6 +93,39 @@ The following map defines are available:\n \toptimization to shrink the size of each map entry, at the cost\n \tof not being able to store `NULL` key pointers in the map.\n \n+`PERSIST`::\n+\n+\tOptional. If defined, functions for storing the map to disk are\n+\talso created.\n+\n+`KEY_SIZE`::\n+\n+\tRequired by `PERSIST`. The fixed-width size of the on-disk\n+\trepresentation of a key, in bytes.\n+\n+`VALUE_SIZE`::\n+\n+\tRequired by `PERSIST`. The fixed-width size of the on-disk\n+\trepresentation of a value, in bytes.\n+\n+`KEY_TO_DISK(KEY_ARG key, unsigned char *out)`::\n+\n+\tRequired by `PERSIST`. A function that will convert the\n+\tin-memory representation of a key into its on-disk\n+\trepresentation. Note that the reverse transformation does not\n+\thave to be possible.\n+\n+`VALUE_TO_DISK(VALUE_ARG value, unsigned char *out)`::\n+\n+\tRequired by `PERSIST`. A function that will convert the\n+\tin-memory representation of a value into its on-disk\n+\trepresentation.\n+\n+`DISK_TO_VALUE(unsigned char *in, VALUE_TYPE *value)`::\n+\n+\tRequired by `PERSIST`. A function that will convert the on-disk\n+\trepresentation of a value into its in-memory representation.\n+\n \n Data Structures\n ---------------\n@@ -104,6 +152,14 @@ Each defined map type will have its own structure (e.g., `map_object_uint32`).\n \tneed to use this type directly, unless you are enumerating all\n \telements of a map.\n \n+`struct map_persist_NAME`::\n+\n+\tA persistent map. This struct should be initialized to\n+\tall-zeroes. The `map` field contains a complete in-core map. The\n+\t`disk_entries` and `disk_nr` fields specify the flat storage.\n+\tThese should not be set directly, but rather through the\n+\t`attach` function.\n+\n \n Functions\n ---------\n@@ -127,6 +183,27 @@ Each defined map type will have its own set of access functions (e.g.,\n \tdefined, the key and value are passed in as `const KEY_TYPE *`\n \tand `const VALUE_TYPE *`, respectively.\n \n+`map_persist_get_NAME(struct map_persist_NAME *, KEY_TYPE key, VALUE_TYPE *value)`::\n+\n+\tSame as `map_get_NAME`, but for a persistent map.\n+\n+`map_persist_set_NAME(struct map_persist_NAME *, KEY_TYPE key, VALUE_TYPE value)`::\n+\n+\tSame as `map_set_name`, but for a persistent map. It does\n+\tnot provide the \"old\" value for the key.\n+\n+`map_persist_attach_NAME`::\n+\n+\tAttach storage from `buf` of size `len` bytes as the flat\n+\tbacking store for the map. The map does not copy the storage;\n+\tthe caller is responsible for making sure it stays around as\n+\tlong as the map does.\n+\n+`map_persist_flush_NAME`::\n+\n+\tMerge in-core entries with those found in the backing store, and\n+\twrite the result to `fd`. Returns 0 for success, -1 for failure.\n+\n \n Examples\n --------\ndiff --git a/Makefile b/Makefile\nindex 7684a76..e38ae9e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -492,6 +492,7 @@ TEST_PROGRAMS_NEED_X += test-genrandom\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-line-buffer\n TEST_PROGRAMS_NEED_X += test-map\n+TEST_PROGRAMS_NEED_X += test-map-persist\n TEST_PROGRAMS_NEED_X += test-match-trees\n TEST_PROGRAMS_NEED_X += test-mergesort\n TEST_PROGRAMS_NEED_X += test-mktemp\ndiff --git a/map-decl.h b/map-decl.h\nindex 7d4daaf..1ba7157 100644\n--- a/map-decl.h\n+++ b/map-decl.h\n@@ -20,3 +20,21 @@ extern int THIS(map_set)(struct THIS(map) *,\n \t\t\t KEY_ARG key,\n \t\t\t VALUE_ARG value,\n \t\t\t VALUE_TYPE *old);\n+\n+#ifdef PERSIST\n+struct THIS(map_persist) {\n+\tconst unsigned char *disk_entries;\n+\tunsigned int disk_nr;\n+\tstruct THIS(map) mem;\n+};\n+extern int THIS(map_persist_get)(struct THIS(map_persist) *,\n+\t\t\t\t KEY_ARG key,\n+\t\t\t\t VALUE_TYPE *value);\n+extern int THIS(map_persist_set)(struct THIS(map_persist) *,\n+\t\t\t\t KEY_ARG key,\n+\t\t\t\t VALUE_ARG value);\n+extern void THIS(map_persist_attach)(struct THIS(map_persist) *,\n+\t\t\t\t const unsigned char *buf,\n+\t\t\t\t unsigned int len);\n+extern int THIS(map_persist_flush)(struct THIS(map_persist) *, int fd);\n+#endif\ndiff --git a/map-impl.h b/map-impl.h\nindex 844b7f1..c44d0a0 100644\n--- a/map-impl.h\n+++ b/map-impl.h\n@@ -92,3 +92,151 @@ int THIS(map_get)(struct THIS(map) *m,\n \t}\n \treturn 0;\n }\n+\n+#ifdef PERSIST\n+static const unsigned char *THIS(disk_lookup)(const unsigned char *buf, int nr,\n+\t\t\t\t\t int ksize, int vsize,\n+\t\t\t\t\t const unsigned char *key)\n+{\n+\tunsigned lo = 0, hi = nr;\n+\n+\tdo {\n+\t\tunsigned mi = (lo + hi) / 2;\n+\t\tconst unsigned char *e = buf + mi * (ksize + vsize);\n+\t\tint cmp = memcmp(key, e, ksize);\n+\n+\t\tif (!cmp)\n+\t\t\treturn e + ksize;\n+\t\tif (cmp < 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t} while (lo < hi);\n+\n+\treturn NULL;\n+}\n+\n+int THIS(map_persist_get)(struct THIS(map_persist) *m,\n+\t\t\t KEY_ARG key,\n+\t\t\t VALUE_TYPE *value)\n+{\n+\tunsigned char disk_key[KEY_SIZE];\n+\tconst unsigned char *disk_value;\n+\n+\tif (THIS(map_get)(&m->mem, key, value))\n+\t\treturn 1;\n+\n+\tif (!m->disk_entries)\n+\t\treturn 0;\n+\n+\tKEY_TO_DISK(key, disk_key);\n+\tdisk_value = THIS(disk_lookup)(m->disk_entries, m->disk_nr,\n+\t\t\t\t KEY_SIZE, VALUE_SIZE, disk_key);\n+\tif (disk_value) {\n+\t\tDISK_TO_VALUE(disk_value, value);\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+int THIS(map_persist_set)(struct THIS(map_persist) *m,\n+\t\t\t KEY_ARG key,\n+\t\t\t VALUE_ARG value)\n+{\n+\treturn THIS(map_set)(&m->mem, key, value, NULL);\n+}\n+\n+void THIS(map_persist_attach)(struct THIS(map_persist) *m,\n+\t\t\t const unsigned char *buf,\n+\t\t\t unsigned int len)\n+{\n+\tm->disk_entries = buf;\n+\tm->disk_nr = len / (KEY_SIZE + VALUE_SIZE);\n+}\n+\n+static unsigned char *THIS(flatten_mem)(struct THIS(map_persist) *m)\n+{\n+\tunsigned char *ret, *out;\n+\tint i, nr;\n+\n+\tout = ret = xmalloc(m->mem.nr * (KEY_SIZE + VALUE_SIZE));\n+\tnr = 0;\n+\tfor (i = 0; i < m->mem.size; i++) {\n+\t\tstruct THIS(map_entry) *e = m->mem.hash + i;\n+\n+\t\tif (!hash_used(e))\n+\t\t\tcontinue;\n+\n+\t\tif (nr++ == m->mem.nr)\n+\t\t\tdie(\"BUG: map hash contained extra values\");\n+\n+\t\tKEY_TO_DISK(key_ref(e->key), out);\n+\t\tout += KEY_SIZE;\n+\t\tVALUE_TO_DISK(value_ref(e->value), out);\n+\t\tout += VALUE_SIZE;\n+\t}\n+\n+\tif (nr != m->mem.nr)\n+\t\tdie(\"BUG: map hash had fewer values than claimed\");\n+\n+\treturn ret;\n+}\n+\n+static int THIS(keycmp)(const void *a, const void *b)\n+{\n+\treturn memcmp(a, b, KEY_SIZE);\n+}\n+\n+static int THIS(merge_entries)(int fd,\n+\t\t\t const unsigned char *left, unsigned nr_left,\n+\t\t\t const unsigned char *right, unsigned nr_right)\n+{\n+#define ADVANCE(name) \\\n+\tdo { \\\n+\t\tname += KEY_SIZE + VALUE_SIZE; \\\n+\t\tnr_##name--; \\\n+\t} while (0)\n+#define WRITE_ENTRY(name) \\\n+\tdo { \\\n+\t\tif (write_in_full(fd, name, KEY_SIZE + VALUE_SIZE) < 0) \\\n+\t\t\treturn -1; \\\n+\t\tADVANCE(name); \\\n+\t} while (0)\n+\n+\twhile (nr_left && nr_right) {\n+\t\tint cmp = THIS(keycmp)(left, right);\n+\n+\t\t/* skip duplicates, preferring left to right */\n+\t\tif (cmp == 0)\n+\t\t\tADVANCE(right);\n+\t\telse if (cmp < 0)\n+\t\t\tWRITE_ENTRY(left);\n+\t\telse\n+\t\t\tWRITE_ENTRY(right);\n+\t}\n+\twhile (nr_left)\n+\t\tWRITE_ENTRY(left);\n+\twhile (nr_right)\n+\t\tWRITE_ENTRY(right);\n+\n+#undef WRITE_ENTRY\n+#undef ADVANCE\n+\n+\treturn 0;\n+}\n+\n+int THIS(map_persist_flush)(struct THIS(map_persist) *m, int fd)\n+{\n+\tunsigned char *mem_entries;\n+\tint r;\n+\n+\tmem_entries = THIS(flatten_mem)(m);\n+\tqsort(mem_entries, m->mem.nr, KEY_SIZE + VALUE_SIZE, THIS(keycmp));\n+\n+\tr = THIS(merge_entries)(fd, mem_entries, m->mem.nr,\n+\t\t\t\tm->disk_entries, m->disk_nr);\n+\tfree(mem_entries);\n+\treturn r;\n+}\n+#endif\ndiff --git a/t/t0007-map.sh b/t/t0007-map.sh\nindex b5845f4..14187d6 100755\n--- a/t/t0007-map.sh\n+++ b/t/t0007-map.sh\n@@ -47,4 +47,28 @@ for type in pointer struct; do\n \t\"\n done\n \n+test_expect_success 'put some items in a persistent map' '\n+\ttest-map-persist foo d:4 a:1 c:3 b:2\n+'\n+\n+test_expect_success 'retrieve persistent items' '\n+\tcat >expect <<-\\EOF &&\n+\tc: 3\n+\ta: 1\n+\te: not found\n+\tEOF\n+\ttest-map-persist foo c a e >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'new entries override disk entries' '\n+\tcat >expect <<-\\EOF &&\n+\tc: 3\n+\ta: 5\n+\te: not found\n+\tEOF\n+\ttest-map-persist foo a:5 c a e >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\ndiff --git a/test-map-persist.c b/test-map-persist.c\nnew file mode 100644\nindex 0000000..1334cdd\n--- /dev/null\n+++ b/test-map-persist.c\n@@ -0,0 +1,125 @@\n+#include \"cache.h\"\n+\n+static const char usage_msg[] =\n+\"test-map-persist [keys]\";\n+\n+static inline unsigned int hash_string(const char *str, unsigned int n)\n+{\n+\tunsigned long hash = 0;\n+\n+\tfor (; *str; str++)\n+\t\thash = (hash << 5) + *str;\n+\treturn hash % n;\n+}\n+\n+static inline unsigned int string_equal(const char *a, const char *b)\n+{\n+\treturn !strcmp(a, b);\n+}\n+\n+static inline void string_to_disk(const char *s, unsigned char *out)\n+{\n+\t/*\n+\t * we need a fixed-width representation, so let's just store 10 bytes,\n+\t * padded with zeroes\n+\t */\n+\tint len = strlen(s);\n+\tif (len > 10)\n+\t\tlen = 10;\n+\tmemcpy(out, s, len);\n+\tmemset(out + len, 0, 10 - len);\n+}\n+\n+static inline void uint32_to_disk(uint32_t v, unsigned char *out)\n+{\n+\tv = htonl(v);\n+\tmemcpy(out, &v, 4);\n+}\n+\n+static inline void disk_to_uint32(const unsigned char *in, uint32_t *v)\n+{\n+\tmemcpy(v, in, 4);\n+\t*v = ntohl(*v);\n+}\n+\n+#define NAME string_uint32\n+#define PERSIST\n+#define KEY_TYPE const char *\n+#define KEY_SIZE 10\n+#define KEY_TO_DISK string_to_disk\n+#define KEY_EQUAL string_equal\n+#define HASH hash_string\n+#define DISK_LOOKUP_FUN lookup_string\n+#define SENTINEL_NULL\n+#define VALUE_TYPE uint32_t\n+#define VALUE_SIZE 4\n+#define VALUE_TO_DISK uint32_to_disk\n+#define DISK_TO_VALUE disk_to_uint32\n+#include \"map-decl.h\"\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\n+\n+static void open_map(const char *path, struct map_persist_string_uint32 *m)\n+{\n+\tint fd;\n+\tstruct stat sb;\n+\tconst unsigned char *buf;\n+\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn;\n+\n+\tfstat(fd, &sb);\n+\tbuf = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\n+\tmap_persist_attach_string_uint32(m, buf, sb.st_size);\n+}\n+\n+static void flush_map(const char *path, struct map_persist_string_uint32 *m)\n+{\n+\tchar tmp[1024];\n+\tint fd;\n+\n+\tsnprintf(tmp, sizeof(tmp), \"%s.tmp\", path);\n+\tfd = open(tmp, O_WRONLY|O_CREAT, 0666);\n+\tif (fd < 0)\n+\t\tdie_errno(\"unable to open '%s' for writing\", tmp);\n+\tif (map_persist_flush_string_uint32(m, fd) < 0 || close(fd) < 0)\n+\t\tdie_errno(\"unable to write new map\");\n+\tif (rename(tmp, path) < 0)\n+\t\tdie_errno(\"unable to rename new map into place\");\n+}\n+\n+int main(int argc, const char **argv)\n+{\n+\tstruct map_persist_string_uint32 m = {0};\n+\tconst char *path;\n+\tconst char *spec;\n+\n+\targv++;\n+\tpath = *argv++;\n+\tif (!path)\n+\t\tusage(usage_msg);\n+\n+\topen_map(path, &m);\n+\n+\twhile ((spec = *argv++)) {\n+\t\tchar *colon = strchr(spec, ':');\n+\t\tif (colon) {\n+\t\t\t*colon++ = '\\0';\n+\t\t\tmap_persist_set_string_uint32(&m, spec, atoi(colon));\n+\t\t}\n+\t\telse {\n+\t\t\tuint32_t value;\n+\t\t\tif (map_persist_get_string_uint32(&m, spec, &value))\n+\t\t\t\tprintf(\"%s: %d\\n\", spec, value);\n+\t\t\telse\n+\t\t\t\tprintf(\"%s: not found\\n\", spec);\n+\t\t}\n+\t}\n+\n+\tflush_map(path, &m);\n+\n+\treturn 0;\n+}\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196466","messageId":"20120804171146.GF19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 6/8] implement metadata cache subsystem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:11:46Z","receivedAt":"2012-08-04T17:11:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There are some calculations that git makes repeatedly, even\nthough the results are invariant for a certain input (e.g.,\nthe patch-id of a certain commit). We can make a space/time\ntradeoff by caching these on disk between runs.\n\nEven though these may be immutable for a certain commit, we\ndon't want to directly store the results in the commit\nobjects themselves, for a few reasons:\n\n 1. They are not necessarily used by all algorithms, so\n bloating the commit object might slow down other\n algorithms.\n\n 2. Because they can be calculated from the existing\n commits, they are redundant with the existing\n information. Thus they are an implementation detail of\n our current algorithms, and should not be cast in stone\n by including them in the commit sha1.\n\n 3. They may only be immutable under a certain set of\n conditions (e.g., which grafts or replace refs we are\n using). Keeping the storage external means we can\n invalidate and regenerate the cache whenever those\n conditions change.\n\nThe persistent map API already provides the storage we need.\nThis new API takes care of the details of opening and\nclosing the cache files automatically. Callers need only get\nand set values as they see fit.\n\nSigned-off-by: Jeff King \n---\n Documentation/technical/api-metadata-cache.txt | 67 ++++++++++\n Makefile | 2 +\n metadata-cache.c | 169 +++++++++++++++++++++++++\n metadata-cache.h | 8 ++\n 4 files changed, 246 insertions(+)\n create mode 100644 Documentation/technical/api-metadata-cache.txt\n create mode 100644 metadata-cache.c\n create mode 100644 metadata-cache.h\n\ndiff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt\nnew file mode 100644\nindex 0000000..5f4422d\n--- /dev/null\n+++ b/Documentation/technical/api-metadata-cache.txt\n@@ -0,0 +1,67 @@\n+metadata cache API\n+==================\n+\n+The metadata cache API provides simple-to-use, persistent key/value\n+storage. It is built on the link:api-map.html[map API], so keys and\n+values can have any serializable type.\n+\n+Caches are statically allocated, and no explicit initialization is\n+required. Callers can simply call the \"get\" and \"set\" functions for a\n+given cache. At program exit, any new entries in the cache are flushed\n+to disk.\n+\n+\n+Defining a New Cache\n+--------------------\n+\n+You need to provide three pieces of information to define a new cache:\n+\n+name::\n+\tThis name will be used both as part of the C identifier and as\n+\tpart of the filename under which the cache is stored. Restrict\n+\tthe characters used to alphanumerics and underscore.\n+\n+map::\n+\tThe type of map (declared by `DECLARE_MAP`) that this cache will\n+\tstore.\n+\n+validity::\n+\tA function that will generate a 20-byte \"validity token\"\n+\trepresenting the conditions under which the cache is valid.\n+\tFor example, a cache that depended on the structure of the\n+\thistory graph would be valid only under a given set of grafts\n+\tand replace refs. That set could be stirred into a sha1 and used\n+\tas a validity token.\n+\n+You must declare the cache in metadata-cache.h using\n+`DECLARE_METADATA_CACHE`, and then implement it in metadata-cache.c\n+using `IMPLEMENT_METADATA_CACHE`.\n+\n+\n+Using a Cache\n+-------------\n+\n+Interaction with a cache consists entirely of getting and setting\n+values. No initialization or cleanup is required. The get and set\n+functions mirror their \"map\" counterparts; see the\n+link:api-map.html[map API] for details.\n+\n+\n+File Format\n+-----------\n+\n+Cache files are stored in the $GIT_DIR/cache directory. Each cache gets\n+its own directory, named after the `name` parameter in the cache\n+definition. Within each directory is a set of files, one cache per file,\n+named after their validity tokens. Caches for multiple sets of\n+conditions can simultaneously exist, and git will use whichever is\n+appropriate.\n+\n+The files themselves consist of an 8-byte header. The first four bytes\n+are the magic sequence \"MTAC\" (for \"MeTA Cache\"), followed by a 4-byte\n+version number, in network byte order. This document describes version\n+1.\n+\n+The rest of the file consists of the persistent map data. This is a\n+compact, sorted list of keys and values; see the link:api-map.html[map\n+API] for details.\ndiff --git a/Makefile b/Makefile\nindex e38ae9e..08ddfa7 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -640,6 +640,7 @@ LIB_H += map-object.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n LIB_H += mergesort.h\n+LIB_H += metadata-cache.h\n LIB_H += notes-cache.h\n LIB_H += notes-merge.h\n LIB_H += notes.h\n@@ -755,6 +756,7 @@ LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n+LIB_OBJS += metadata-cache.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/metadata-cache.c b/metadata-cache.c\nnew file mode 100644\nindex 0000000..94eabfb\n--- /dev/null\n+++ b/metadata-cache.c\n@@ -0,0 +1,169 @@\n+#include \"cache.h\"\n+#include \"metadata-cache.h\"\n+\n+struct metadata_cache {\n+\tconst char *name;\n+\tvoid (*attach)(unsigned char *buf, unsigned long len);\n+\tint (*flush)(int fd);\n+\tint (*empty)(void);\n+\tvoid (*validity)(unsigned char[20]);\n+\tint fd;\n+\tunsigned char *buf;\n+\tunsigned long len;\n+\tstruct metadata_cache *next;\n+\tint initialized;\n+};\n+\n+struct metadata_cache *caches;\n+\n+static const char *metadata_cache_path(struct metadata_cache *mc)\n+{\n+\tunsigned char token[20];\n+\n+\tif (mc->validity)\n+\t\tmc->validity(token);\n+\telse\n+\t\thashcpy(token, null_sha1);\n+\treturn git_path(\"cache/%s/%s\", mc->name, sha1_to_hex(token));\n+}\n+\n+static void write_one_cache(struct metadata_cache *mc)\n+{\n+\tconst char *path;\n+\tstruct strbuf tempfile = STRBUF_INIT;\n+\tint fd = -1;\n+\n+\tif (mc->empty())\n+\t\treturn;\n+\n+\tpath = metadata_cache_path(mc);\n+\tstrbuf_addf(&tempfile, \"%s.XXXXXX\", path);\n+\n+\tif (safe_create_leading_directories(tempfile.buf) < 0)\n+\t\tgoto fail;\n+\tfd = git_mkstemp_mode(tempfile.buf, 0444);\n+\tif (fd < 0)\n+\t\tgoto fail;\n+\n+\tif (write_in_full(fd, \"MTAC\\x00\\x00\\x00\\x01\", 8) < 0)\n+\t\tgoto fail;\n+\tif (mc->flush(fd) < 0)\n+\t\tgoto fail;\n+\tif (close(fd) < 0)\n+\t\tgoto fail;\n+\tif (rename(tempfile.buf, path) < 0)\n+\t\tgoto fail;\n+\n+\tstrbuf_release(&tempfile);\n+\treturn;\n+\n+fail:\n+\tclose(fd);\n+\tunlink(tempfile.buf);\n+\tstrbuf_release(&tempfile);\n+}\n+\n+static void write_all_caches(void)\n+{\n+\tstruct metadata_cache *mc;\n+\tfor (mc = caches; mc; mc = mc->next)\n+\t\twrite_one_cache(mc);\n+}\n+\n+void metadata_cache_init(struct metadata_cache *mc)\n+{\n+\tconst char *path;\n+\tstruct stat st;\n+\tconst unsigned char *p;\n+\tuint32_t version;\n+\tint fd;\n+\n+\tif (mc->initialized)\n+\t\treturn;\n+\n+\tif (!caches)\n+\t\tatexit(write_all_caches);\n+\tmc->next = caches;\n+\tcaches = mc;\n+\tmc->initialized = 1;\n+\n+\tpath = metadata_cache_path(mc);\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn;\n+\n+\tif (fstat(fd, &st) < 0)\n+\t\tgoto fail;\n+\tmc->len = st.st_size;\n+\tmc->buf = xmmap(NULL, mc->len, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (!mc->buf)\n+\t\tgoto fail;\n+\tclose(fd);\n+\tfd = -1;\n+\n+\tif (mc->len < 8) {\n+\t\twarning(\"cache '%s' is missing header\", path);\n+\t\tgoto fail;\n+\t}\n+\tp = mc->buf;\n+\tif (memcmp(p, \"MTAC\", 4)) {\n+\t\twarning(\"cache '%s' has invalid magic: %c%c%c%c\",\n+\t\t\tpath, p[0], p[1], p[2], p[3]);\n+\t\tgoto fail;\n+\t}\n+\tp += 4;\n+\tmemcpy(&version, p, 4);\n+\tversion = ntohl(version);\n+\tif (version != 1) {\n+\t\twarning(\"cache '%s' has unknown version: %\"PRIu32,\n+\t\t\tpath, version);\n+\t\tgoto fail;\n+\t}\n+\n+\tmc->attach(mc->buf + 8, mc->len - 8);\n+\treturn;\n+\n+fail:\n+\tclose(fd);\n+\tif (mc->buf)\n+\t\tmunmap(mc->buf, mc->len);\n+\tmc->buf = NULL;\n+\tmc->len = 0;\n+}\n+\n+#define IMPLEMENT_CACHE(name, maptype, ktype, vtype) \\\n+static struct map_persist_sha1pair_uint32 name##_map; \\\n+\\\n+static void name##_cache_attach(unsigned char *buf, unsigned long len) \\\n+{ \\\n+\tmap_persist_attach_##maptype(&name##_map, buf, len); \\\n+} \\\n+\\\n+static int name##_cache_flush(int fd) \\\n+{ \\\n+\treturn map_persist_flush_##maptype(&name##_map, fd); \\\n+} \\\n+\\\n+static int name##_cache_empty(void) \\\n+{ \\\n+\treturn !name##_map.mem.nr; \\\n+} \\\n+\\\n+static struct metadata_cache name##_cache = { \\\n+\t#name, \\\n+\tname##_cache_attach, \\\n+\tname##_cache_flush, \\\n+\tname##_cache_empty, \\\n+}; \\\n+\\\n+int name##_cache_get(ktype key, vtype *value) \\\n+{ \\\n+\tmetadata_cache_init(&name##_cache); \\\n+\treturn map_persist_get_##maptype(&name##_map, key, value); \\\n+} \\\n+\\\n+void name##_cache_set(ktype key, vtype value) \\\n+{ \\\n+\tmetadata_cache_init(&name##_cache); \\\n+\tmap_persist_set_##maptype(&name##_map, key, value); \\\n+}\ndiff --git a/metadata-cache.h b/metadata-cache.h\nnew file mode 100644\nindex 0000000..4354023\n--- /dev/null\n+++ b/metadata-cache.h\n@@ -0,0 +1,8 @@\n+#ifndef METADATA_CACHE_H\n+#define METADATA_CACHE_H\n+\n+#define DECLARE_CACHE(name, ktype, vtype) \\\n+int name##_cache_get(ktype, vtype *); \\\n+void name##_cache_set(ktype, vtype);\n+\n+#endif /* METADATA_CACHE_H */\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196467","messageId":"20120804171232.GG19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 7/8] implement rename cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:12:32Z","receivedAt":"2012-08-04T17:12:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This just stores pairs of sha1s mapped to their similarity scores.\n\nSigned-off-by: Jeff King \n---\n Makefile | 5 +++++\n cache.h | 5 +++++\n map-sha1pair-uint32-params.h | 12 ++++++++++++\n map-sha1pair-uint32.c | 8 ++++++++\n map-sha1pair-uint32.h | 8 ++++++++\n map-sha1pair.h | 22 ++++++++++++++++++++++\n map-uint32.h | 16 ++++++++++++++++\n metadata-cache.c | 3 +++\n metadata-cache.h | 2 ++\n 9 files changed, 81 insertions(+)\n create mode 100644 map-sha1pair-uint32-params.h\n create mode 100644 map-sha1pair-uint32.c\n create mode 100644 map-sha1pair-uint32.h\n create mode 100644 map-sha1pair.h\n create mode 100644 map-uint32.h\n\ndiff --git a/Makefile b/Makefile\nindex 08ddfa7..f020994 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -637,6 +637,10 @@ LIB_H += map-init.h\n LIB_H += map-object-void-params.h\n LIB_H += map-object-void.h\n LIB_H += map-object.h\n+LIB_H += map-sha1pair-uint32-params.h\n+LIB_H += map-sha1pair-uint32.h\n+LIB_H += map-sha1pair.h\n+LIB_H += map-uint32.h\n LIB_H += merge-file.h\n LIB_H += merge-recursive.h\n LIB_H += mergesort.h\n@@ -752,6 +756,7 @@ LIB_OBJS += lockfile.o\n LIB_OBJS += log-tree.o\n LIB_OBJS += mailmap.o\n LIB_OBJS += map-object-void.o\n+LIB_OBJS += map-sha1pair-uint32.o\n LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\ndiff --git a/cache.h b/cache.h\nindex 67f28b4..23a2f93 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -677,6 +677,11 @@ static inline int is_empty_blob_sha1(const unsigned char *sha1)\n \treturn !hashcmp(sha1, EMPTY_BLOB_SHA1_BIN);\n }\n \n+struct sha1pair {\n+\tunsigned char one[20];\n+\tunsigned char two[20];\n+};\n+\n int git_mkstemp(char *path, size_t n, const char *template);\n \n int git_mkstemps(char *path, size_t n, const char *template, int suffix_len);\ndiff --git a/map-sha1pair-uint32-params.h b/map-sha1pair-uint32-params.h\nnew file mode 100644\nindex 0000000..74c6506\n--- /dev/null\n+++ b/map-sha1pair-uint32-params.h\n@@ -0,0 +1,12 @@\n+#define NAME sha1pair_uint32\n+#define PERSIST\n+#define KEY_TYPE struct sha1pair\n+#define PASS_KEY_BY_REF\n+#define KEY_EQUAL sha1pair_equal\n+#define KEY_SIZE 40\n+#define KEY_TO_DISK sha1pair_to_disk\n+#define HASH hash_sha1pair\n+#define VALUE_TYPE uint32_t\n+#define VALUE_SIZE 4\n+#define VALUE_TO_DISK uint32_to_disk\n+#define DISK_TO_VALUE disk_to_uint32\ndiff --git a/map-sha1pair-uint32.c b/map-sha1pair-uint32.c\nnew file mode 100644\nindex 0000000..93b3c16\n--- /dev/null\n+++ b/map-sha1pair-uint32.c\n@@ -0,0 +1,8 @@\n+#include \"cache.h\"\n+#include \"map-sha1pair-uint32.h\"\n+\n+#include \"map-sha1pair.h\"\n+#include \"map-uint32.h\"\n+#include \"map-sha1pair-uint32-params.h\"\n+#include \"map-impl.h\"\n+#include \"map-done.h\"\ndiff --git a/map-sha1pair-uint32.h b/map-sha1pair-uint32.h\nnew file mode 100644\nindex 0000000..6e022fb\n--- /dev/null\n+++ b/map-sha1pair-uint32.h\n@@ -0,0 +1,8 @@\n+#ifndef MAP_SHA1PAIR_UINT32_H\n+#define MAP_SHA1PAIR_UINT32_H\n+\n+#include \"map-sha1pair-uint32-params.h\"\n+#include \"map-decl.h\"\n+#include \"map-done.h\"\n+\n+#endif /* MAP_SHA1PAIR_UINT32_H */\ndiff --git a/map-sha1pair.h b/map-sha1pair.h\nnew file mode 100644\nindex 0000000..ea7ead8\n--- /dev/null\n+++ b/map-sha1pair.h\n@@ -0,0 +1,22 @@\n+#ifndef MAP_SHA1PAIR_H\n+#define MAP_SHA1PAIR_H\n+\n+static inline unsigned int hash_sha1pair(const struct sha1pair *k, unsigned int n)\n+{\n+\tunsigned int hash;\n+\tmemcpy(&hash, k, sizeof(unsigned int));\n+\treturn hash % n;\n+}\n+\n+static inline int sha1pair_equal(const struct sha1pair *a, const struct sha1pair *b)\n+{\n+\treturn !hashcmp(a->one, b->one) && !hashcmp(a->two, b->two);\n+}\n+\n+static inline void sha1pair_to_disk(const struct sha1pair *v, unsigned char *out)\n+{\n+\thashcpy(out, v->one);\n+\thashcpy(out+20, v->two);\n+}\n+\n+#endif /* MAP_SHA1PAIR_H */\ndiff --git a/map-uint32.h b/map-uint32.h\nnew file mode 100644\nindex 0000000..ce63dac\n--- /dev/null\n+++ b/map-uint32.h\n@@ -0,0 +1,16 @@\n+#ifndef MAP_UINT32_H\n+#define MAP_UINT32_H\n+\n+static inline void uint32_to_disk(uint32_t v, unsigned char *out)\n+{\n+\tv = htonl(v);\n+\tmemcpy(out, &v, 4);\n+}\n+\n+static inline void disk_to_uint32(const unsigned char *in, uint32_t *v)\n+{\n+\tmemcpy(v, in, 4);\n+\t*v = ntohl(*v);\n+}\n+\n+#endif /* MAP_UINT32_H */\ndiff --git a/metadata-cache.c b/metadata-cache.c\nindex 94eabfb..d70d116 100644\n--- a/metadata-cache.c\n+++ b/metadata-cache.c\n@@ -1,5 +1,6 @@\n #include \"cache.h\"\n #include \"metadata-cache.h\"\n+#include \"map-sha1pair-uint32.h\"\n \n struct metadata_cache {\n \tconst char *name;\n@@ -167,3 +168,5 @@ void name##_cache_set(ktype key, vtype value) \\\n \tmetadata_cache_init(&name##_cache); \\\n \tmap_persist_set_##maptype(&name##_map, key, value); \\\n }\n+\n+IMPLEMENT_CACHE(rename, sha1pair_uint32, const struct sha1pair *, uint32_t)\ndiff --git a/metadata-cache.h b/metadata-cache.h\nindex 4354023..f3e6f51 100644\n--- a/metadata-cache.h\n+++ b/metadata-cache.h\n@@ -5,4 +5,6 @@\n int name##_cache_get(ktype, vtype *); \\\n void name##_cache_set(ktype, vtype);\n \n+DECLARE_CACHE(rename, const struct sha1pair *, uint32_t)\n+\n #endif /* METADATA_CACHE_H */\n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196468","messageId":"20120804171421.GH19378@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804170905.GA19267@sigill.intra.peff.net","subject":"[PATCH 8/8] diff: optionally use rename cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-04T17:14:21Z","receivedAt":"2012-08-04T17:14:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This speeds up estimate_similarity by caching the similarity\nscore of pairs of blob sha1s.\n\nSigned-off-by: Jeff King \n---\nSome interesting things to time with this are:\n\n - \"git log --raw -M\" on a repo with a lot of paths or a lot of renames\n (I found on git.git, the speedup was not that impressive)\n\n - \"git log --raw -C -C\" on any repo (this speeds up a lot in git.git).\n\n - \"git show -M\" on commits with very large blobs\n\n cache.h | 1 +\n diff.c | 6 ++++++\n diffcore-rename.c | 11 ++++++++++-\n 3 files changed, 17 insertions(+), 1 deletion(-)\n\ndiff --git a/cache.h b/cache.h\nindex 23a2f93..7ee1caf 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1228,6 +1228,7 @@ int add_files_to_cache(const char *prefix, const char **pathspec, int flags);\n \n /* diff.c */\n extern int diff_auto_refresh_index;\n+extern int diff_cache_renames;\n \n /* match-trees.c */\n void shift_tree(const unsigned char *, const unsigned char *, unsigned char *, int);\ndiff --git a/diff.c b/diff.c\nindex 95706a5..c84e043 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -34,6 +34,7 @@ static int diff_no_prefix;\n static int diff_stat_graph_width;\n static int diff_dirstat_permille_default = 30;\n static struct diff_options default_diff_options;\n+int diff_cache_renames;\n \n static char diff_colors[][COLOR_MAXLEN] = {\n \tGIT_COLOR_RESET,\n@@ -214,6 +215,11 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"diff.cacherenames\")) {\n+\t\tdiff_cache_renames = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!prefixcmp(var, \"submodule.\"))\n \t\treturn parse_submodule_config_option(var, value);\n \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 216a7a4..611e1d3 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,6 +6,7 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n #include \"progress.h\"\n+#include \"metadata-cache.h\"\n \n /* Table of rename/copy destinations */\n \n@@ -137,7 +138,8 @@ static int estimate_similarity(struct diff_filespec *src,\n \t */\n \tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n \tunsigned long delta_limit;\n-\tint score;\n+\tuint32_t score;\n+\tstruct sha1pair pair;\n \n \t/* We deal only with regular files. Symlink renames are handled\n \t * only when they are exact matches --- in other words, no edits\n@@ -175,6 +177,11 @@ static int estimate_similarity(struct diff_filespec *src,\n \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n+\thashcpy(pair.one, src->sha1);\n+\thashcpy(pair.two, dst->sha1);\n+\tif (diff_cache_renames && rename_cache_get(&pair, &score))\n+\t\t\treturn score;\n+\n \tif (!src->cnt_data && diff_populate_filespec(src, 0))\n \t\treturn 0;\n \tif (!dst->cnt_data && diff_populate_filespec(dst, 0))\n@@ -195,6 +202,8 @@ static int estimate_similarity(struct diff_filespec *src,\n \t\tscore = 0; /* should not happen */\n \telse\n \t\tscore = (int)(src_copied * MAX_SCORE / max_size);\n+\tif (diff_cache_renames)\n+\t\trename_cache_set(&pair, score);\n \treturn score;\n }\n \n-- \n1.7.12.rc1.7.g7a223a6\n"},{"id":"196477","messageId":"7vk3xe8dc1.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120804171146.GF19378@sigill.intra.peff.net","subject":"Re: [PATCH 6/8] implement metadata cache subsystem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-04T22:49:12Z","receivedAt":"2012-08-04T22:49:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> There are some calculations that git makes repeatedly, even\n> though the results are invariant for a certain input (e.g.,\n> the patch-id of a certain commit). We can make a space/time\n> tradeoff by caching these on disk between runs.\n>\n> Even though these may be immutable for a certain commit, we\n> don't want to directly store the results in the commit\n> objects themselves, for a few reasons:\n>\n> 1. They are not necessarily used by all algorithms, so\n> bloating the commit object might slow down other\n> algorithms.\n>\n> 2. Because they can be calculated from the existing\n> commits, they are redundant with the existing\n> information. Thus they are an implementation detail of\n> our current algorithms, and should not be cast in stone\n> by including them in the commit sha1.\n>\n> 3. They may only be immutable under a certain set of\n> conditions (e.g., which grafts or replace refs we are\n> using). Keeping the storage external means we can\n> invalidate and regenerate the cache whenever those\n> conditions change.\n\n4. The algorithm used to compute such values could improve over\ntime. The same advantage argument as 3 applies to this case.\n"},{"id":"196478","messageId":"7vehnm8dbv.fsf@alter.siamese.dyndns.org","threadId":"31151","inReplyTo":"20120804171038.GA19378@sigill.intra.peff.net","subject":"Re: [PATCH 1/8] implement generic key/value map","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-04T22:58:10Z","receivedAt":"2012-08-04T22:58:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It is frequently useful to have a fast, generic data\n> structure mapping keys to values. We already have something\n> like this in the \"decorate\" API, but it has two downsides:\n>\n> 1. The key type must always be a \"struct object *\".\n>\n> 2. The value type is a void pointer, which means it is\n> inefficient and cumbersome for storing small values.\n> One must either encode their value inside the void\n> pointer, or allocate additional storage for the pointer\n> to point to.\n>\n> This patch introduces a generic map data structure, mapping\n> keys of arbitrary type to values of arbitrary type.\n\nDoes the type of keys in a map have to be of the same size, or can a\nkey of a type with variable size (e.g. struct with a flex member at\nthe end)? Same question for the type of values.\n\nIs the type of keys in a map required to have a total order over it,\nor is it suffice only to have equality defined?\n\nThe latter might matter once we start talking about a huge map that\nwe may not want to hold in-core.\n"},{"id":"196561","messageId":"20120806203154.GA11977@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7vk3xe8dc1.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 6/8] implement metadata cache subsystem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-06T20:31:54Z","receivedAt":"2012-08-06T20:31:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 04, 2012 at 03:49:12PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > There are some calculations that git makes repeatedly, even\n> > though the results are invariant for a certain input (e.g.,\n> > the patch-id of a certain commit). We can make a space/time\n> > tradeoff by caching these on disk between runs.\n> >\n> > Even though these may be immutable for a certain commit, we\n> > don't want to directly store the results in the commit\n> > objects themselves, for a few reasons:\n> >\n> > 1. They are not necessarily used by all algorithms, so\n> > bloating the commit object might slow down other\n> > algorithms.\n> >\n> > 2. Because they can be calculated from the existing\n> > commits, they are redundant with the existing\n> > information. Thus they are an implementation detail of\n> > our current algorithms, and should not be cast in stone\n> > by including them in the commit sha1.\n> >\n> > 3. They may only be immutable under a certain set of\n> > conditions (e.g., which grafts or replace refs we are\n> > using). Keeping the storage external means we can\n> > invalidate and regenerate the cache whenever those\n> > conditions change.\n> \n> 4. The algorithm used to compute such values could improve over\n> time. The same advantage argument as 3 applies to this case.\n\nYeah, agreed. That commit message is a year old, and was written for an\nearlier iteration of the patch which was used for caching commit\ngenerations. There's not really a better algorithm there, but your\ncomment certainly applies to rename similarities.\n\n-Peff\n"},{"id":"196563","messageId":"20120806203558.GB11977@sigill.intra.peff.net","threadId":"31151","inReplyTo":"7vehnm8dbv.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/8] implement generic key/value map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-06T20:35:58Z","receivedAt":"2012-08-06T20:35:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 04, 2012 at 03:58:10PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > It is frequently useful to have a fast, generic data\n> > structure mapping keys to values. We already have something\n> > like this in the \"decorate\" API, but it has two downsides:\n> >\n> > 1. The key type must always be a \"struct object *\".\n> >\n> > 2. The value type is a void pointer, which means it is\n> > inefficient and cumbersome for storing small values.\n> > One must either encode their value inside the void\n> > pointer, or allocate additional storage for the pointer\n> > to point to.\n> >\n> > This patch introduces a generic map data structure, mapping\n> > keys of arbitrary type to values of arbitrary type.\n> \n> Does the type of keys in a map have to be of the same size, or can a\n> key of a type with variable size (e.g. struct with a flex member at\n> the end)? Same question for the type of values.\n\nBoth have to be fixed size, since we represent the hash table using an\narray. But there is nothing stopping you from storing a fixed-size\npointer to a variable-sized item (that is what is happening with \"struct\nobject *\", anyway; the actual storage is inside a \"struct commit\",\n\"struct tree\", etc). But then you get the accompanying memory-management\nissues (which are easy for \"struct object\", as our policy is to keep a\nglobal valid-until-the-program-exits store of all objects we ever see).\n\n> Is the type of keys in a map required to have a total order over it,\n> or is it suffice only to have equality defined?\n\nNo, you only have to define equality. However, for the later patch which\nadds a persistent backing store, you need to be able to serialize keys\nto a byte representation, which provides an implicit total order (by\nsorting the bytes).\n\n> The latter might matter once we start talking about a huge map that\n> we may not want to hold in-core.\n\nRight. See patch 5/8.\n\n-Peff\n"},{"id":"196564","messageId":"20120806203826.GA12073@sigill.intra.peff.net","threadId":"31151","inReplyTo":"20120804171146.GF19378@sigill.intra.peff.net","subject":"Re: [PATCH 6/8] implement metadata cache subsystem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-06T20:38:26Z","receivedAt":"2012-08-06T20:38:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 04, 2012 at 01:11:46PM -0400, Jeff King wrote:\n\n> +#define IMPLEMENT_CACHE(name, maptype, ktype, vtype) \\\n> +static struct map_persist_sha1pair_uint32 name##_map; \\\n\nA minor fixup, but this should obviously be \"map_persist_##maptype\". It\ndoesn't matter for this series (since we only instantiate one cache, and\nit uses a sha1pair_uint32 map), but obviously this was meant to be\ngeneric...\n\n-Peff\n"}]}