{"thread":{"id":"16210","subject":"[PATCH 1/2] diffcore-rename: support rename cache","startedAt":"2008-11-07T14:35:32Z","lastAt":"2008-11-09T02:04:13Z","messageCount":10,"participants":["Nguyễn Thái Ngọc Duy","Yann Dirson","Junio C Hamano","Nguyen Thai Ngoc Duy","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"95127","messageId":"1226068533-10152-1-git-send-email-pclouds@gmail.com","threadId":"16210","inReplyTo":null,"subject":"[PATCH 1/2] diffcore-rename: support rename cache","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-07T14:35:32Z","receivedAt":"2008-11-07T14:35:32Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This patch teaches diffcore_rename() to look into\n$GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\nWith proper cache, there should be no available entry for estimation\nafter exact matching.\n\nRename caching is per commit. I don't think abitrary tree-tree caching\nis worth it.\n\n$GIT_DIR/rename-cache spans out like $GIT_DIR/objects. Each file\ncorresponds to one commit. Its content consists of lines like this\n\n \n\nThis can be used to:\n\n - Make --find-copies-harder pratically usable for moderate-size\n repositories. The first \"git show\" on a linux kernel commit was 5.3\n sec, it then went down to 0.13 sec.\n - Give git-svn a chance to (locally) import explicit renames from\n Subversion\n - People may correct rename results for better diff, if automatic\n rename detection is not good enough.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n diff.h | 2 +\n diffcore-rename.c | 142 ++++++++++++++++++++++++++++++++++++++++++++++-\n log-tree.c | 2 +\n t/t4030-rename-cache.sh | 55 ++++++++++++++++++\n 4 files changed, 199 insertions(+), 2 deletions(-)\n create mode 100755 t/t4030-rename-cache.sh\n\ndiff --git a/diff.h b/diff.h\nindex a49d865..8b68f6f 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -110,6 +110,8 @@ struct diff_options {\n \tadd_remove_fn_t add_remove;\n \tdiff_format_fn_t format_callback;\n \tvoid *format_callback_data;\n+\n+\tstruct commit *commit;\n };\n \n enum color_diff {\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 168a95b..598cc8d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,6 +5,7 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"hash.h\"\n+#include \"commit.h\"\n \n /* Table of rename/copy destinations */\n \n@@ -409,13 +410,130 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+struct cached_filepair {\n+\tunsigned char dst[20];\n+\tunsigned char src[20];\n+\tint score;\n+};\n+\n+static int free_cached_filepair(void *p)\n+{\n+\tfree(p);\n+\treturn 0;\n+}\n+\n+static void load_rename_cache(struct diff_queue_struct *q,\n+\t\t\t struct diff_queue_struct *cacheq,\n+\t\t\t struct diff_options *options)\n+{\n+\tchar *sha1_hex;\n+\tFILE *fp;\n+\tstruct hash_table filepair_table;\n+\tstruct hash_table src_table;\n+\tstruct cached_filepair *pp;\n+\tint i, hash;\n+\tstatic int no_cache_available = -1;\n+\tstruct stat st;\n+\tchar *path;\n+\n+\tif (no_cache_available == -1)\n+\t\tno_cache_available = stat(git_path(\"rename-cache\"), &st) || !S_ISDIR(st.st_mode);\n+\n+\t/* return soon so we don't need to waste CPU */\n+\tif (no_cache_available > 0)\n+\t\treturn;\n+\n+\n+\t/* src_table initialization */\n+\tinit_hash(&src_table);\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tif (DIFF_FILE_VALID(p->one)) {\n+\t\t\tunsigned int hash = hash_filespec(p->one);\n+\t\t\tinsert_hash(hash, p, &src_table);\n+\t\t}\n+\t}\n+\n+\t/* filepair_table initialization */\n+\tinit_hash(&filepair_table);\n+\tsha1_hex = sha1_to_hex(options->commit->object.sha1);\n+\tpath = git_path(\"rename-cache/%c%c/%s\",sha1_hex[0], sha1_hex[1], sha1_hex+2);\n+\tif (stat(path, &st))\n+\t\tfp = NULL;\n+\telse\n+\t\tfp = fopen(path, \"r\");\n+\tif (fp) {\n+\t\tchar src_sha1_hex[41], dst_sha1_hex[41];\n+\t\tstruct cached_filepair p;\n+\n+\t\tsrc_sha1_hex[40] = dst_sha1_hex[40] = '\\0';\n+\t\twhile (fscanf(fp, \"%40c %40c %d\\n\", dst_sha1_hex, src_sha1_hex, &p.score) == 3) {\n+\t\t\tif (get_sha1_hex(src_sha1_hex, p.src) ||\n+\t\t\t get_sha1_hex(dst_sha1_hex, p.dst))\n+\t\t\t\tbreak;\n+\n+\t\t\tpp = xmalloc(sizeof(*pp));\n+\t\t\tmemcpy(pp, &p, sizeof(*pp));\n+\t\t\tmemcpy(&hash, p.dst, sizeof(hash));\n+\t\t\tinsert_hash(hash, pp, &filepair_table);\n+\t\t}\n+\t\tfclose(fp);\n+\t}\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tstruct diff_filepair *dp, *src;\n+\n+\t\t/* find remote_dst */\n+\t\tif (DIFF_FILE_VALID(p->one) ||\n+\t\t !DIFF_FILE_VALID(p->two) ||\n+\t\t (options->single_follow && strcmp(options->single_follow, p->two->path)))\n+\t\t\tcontinue;\n+\n+\t\tmemcpy(&hash, p->two->sha1, sizeof(hash));\n+\t\tpp = lookup_hash(hash, &filepair_table);\n+\t\tif (!pp || memcmp(p->two->sha1, pp->dst, 20))\n+\t\t\tcontinue;\n+\n+\t\t/* create pair */\n+\t\tif (is_null_sha1(pp->src)) {\n+\t\t\tif (DIFF_FILE_VALID(p->one))\n+\t\t\t\tcontinue;\n+\t\t\tdiff_q(cacheq, p);\n+\t\t\tq->queue[i] = NULL;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tmemcpy(&hash, pp->src, sizeof(hash));\n+\t\tsrc = lookup_hash(hash, &src_table);\n+\t\tif (!src || memcmp(pp->src, src->one->sha1, 20))\n+\t\t\tcontinue;\n+\n+\t\tsrc->one->rename_used++;\n+\t\tsrc->one->count++;\n+\t\tp->two->count++;\n+\n+\t\tdp = diff_queue(NULL, src->one, p->two);\n+\t\tdp->renamed_pair = 1;\n+\t\tdp->score = pp->score;\n+\n+\t\tdiff_q(cacheq, dp);\n+\t\tq->queue[i] = NULL;\n+\t\tdiff_free_filepair(p);\n+\t}\n+\n+\tfor_each_hash(&filepair_table, free_cached_filepair);\n+\tfree_hash(&src_table);\n+\tfree_hash(&filepair_table);\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n \tint minimum_score = options->rename_score;\n \tint rename_limit = options->rename_limit;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct diff_queue_struct outq;\n+\tstruct diff_queue_struct outq, cacheq;\n \tstruct diff_score *mx;\n \tint i, j, rename_count;\n \tint num_create, num_src, dst_cnt;\n@@ -423,8 +541,19 @@ void diffcore_rename(struct diff_options *options)\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n+\tcacheq.queue = NULL;\n+\tcacheq.nr = cacheq.alloc = 0;\n+\n+\tif (detect_rename && options->commit)\n+\t\tload_rename_cache(q, &cacheq, options);\n+\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n+\n+\t\t/* was consumed by rename cache */\n+\t\tif (!p)\n+\t\t\tcontinue;\n+\n \t\tif (!DIFF_FILE_VALID(p->one)) {\n \t\t\tif (!DIFF_FILE_VALID(p->two))\n \t\t\t\tcontinue; /* unmerged */\n@@ -563,10 +692,17 @@ void diffcore_rename(struct diff_options *options)\n \t */\n \toutq.queue = NULL;\n \toutq.nr = outq.alloc = 0;\n-\tfor (i = 0; i < q->nr; i++) {\n+\tfor (i = j = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n \t\tstruct diff_filepair *pair_to_free = NULL;\n \n+\t\tif (!p) {\n+\t\t\tif (j >= cacheq.nr)\n+\t\t\t\tdie(\"Internal error: running out of cacheq.\");\n+\t\t\tdiff_q(&outq, cacheq.queue[j++]);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n \t\t\t * Creation\n@@ -635,6 +771,8 @@ void diffcore_rename(struct diff_options *options)\n \tdiff_debug_queue(\"done copying original\", &outq);\n \n \tfree(q->queue);\n+\tif (cacheq.queue)\n+\t\tfree(cacheq.queue);\n \t*q = outq;\n \tdiff_debug_queue(\"done collapsing\", q);\n \ndiff --git a/log-tree.c b/log-tree.c\nindex cec3c06..a67ef6d 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -518,6 +518,7 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit)\n \tlog.commit = commit;\n \tlog.parent = NULL;\n \topt->loginfo = &log;\n+\topt->diffopt.commit = commit;\n \n \tshown = log_tree_diff(opt, commit, &log);\n \tif (!shown && opt->loginfo && opt->always_show_header) {\n@@ -527,5 +528,6 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit)\n \t}\n \topt->loginfo = NULL;\n \tmaybe_flush_or_die(stdout, \"stdout\");\n+\topt->diffopt.commit = NULL;\n \treturn shown;\n }\ndiff --git a/t/t4030-rename-cache.sh b/t/t4030-rename-cache.sh\nnew file mode 100755\nindex 0000000..0d8390c\n--- /dev/null\n+++ b/t/t4030-rename-cache.sh\n@@ -0,0 +1,55 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2008 Nguyen Thai Ngoc Duy\n+#\n+\n+test_description='Test diff rename cache'\n+. ./test-lib.sh\n+\n+cat >expected < d (100%)\n+EOF\n+test_expect_success 'setup' '\n+\tfor i in a b c\n+\tdo\n+\t\techo $i > $i\n+\tdone\n+\tcp a d\n+\tA_SHA1=$(git hash-object a)\n+\tB_SHA1=$(git hash-object b)\n+\tC_SHA1=$(git hash-object c)\n+\tD_SHA1=$(git hash-object d)\n+\tgit add a b\n+\tgit commit -m first\n+\tgit add c d\n+\tgit commit -m second\n+\tgit show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result\n+\ttest_cmp expected result\n+'\n+\n+cat >expected < c (100%)\n+ copy a => d (100%)\n+EOF\n+test_expect_success 'load rename pair cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\") &&\n+\tmkdir -p $(dirname $P)\n+\techo $C_SHA1 $A_SHA1 60000 >> $P\n+\tgit show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result\n+\ttest_cmp expected result\n+'\n+\n+cat >expected < c (100%)\n+ create mode 100644 d\n+EOF\n+test_expect_success 'load create pair cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\") &&\n+\tmkdir -p $(dirname $P)\n+\techo $D_SHA1 0000000000000000000000000000000000000000 0 >> $P\n+\tgit show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result\n+\ttest_cmp expected result\n+'\n+\n+test_done\n-- \n1.6.0.3.802.g47c38\n"},{"id":"95128","messageId":"1226068533-10152-2-git-send-email-pclouds@gmail.com","threadId":"16210","inReplyTo":"1226068533-10152-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/2] diffcore-rename: add config option to allow to cache renames","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-07T14:35:33Z","receivedAt":"2008-11-07T14:35:33Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"If diff.cacherenames is true, then renames will be cached to\n$GIT_DIR/rename-cache. By default, it will not overwrite existing\ncache. Add --refresh-cache to overwrite.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n if git-svn is going to use this, then perharps we should add a rule to prevent\n overwriting certain cache files with .keep files, so that git-svn generated cache\n does not get lost\n\n Documentation/config.txt | 5 ++++\n Documentation/diff-options.txt | 5 ++++\n diff.c | 12 +++++++++++\n diff.h | 2 +\n diffcore-rename.c | 41 ++++++++++++++++++++++++++++++++++++++++\n t/t4030-rename-cache.sh | 27 ++++++++++++++++++++++++++\n 6 files changed, 92 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 29369d0..81160d3 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -630,6 +630,11 @@ diff.renames::\n \twill enable basic rename detection. If set to \"copies\" or\n \t\"copy\", it will detect copies, as well.\n \n+diff.cacherenames::\n+\tTells git to automatically cache renames when detected. The\n+\tcache resides in $GIT_DIR/rename-cache, which is used by git\n+\tif exists.\n+\n fetch.unpackLimit::\n \tIf the number of objects fetched over the git native\n \ttransfer is below this\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex c62b45c..d477a40 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -102,6 +102,11 @@ endif::git-format-patch[]\n \tTurn off rename detection, even when the configuration\n \tfile gives the default to do so.\n \n+--refresh-rename-cache::\n+\tBy default, when git finds a cached version of a commit, it\n+\twill not overwrite the cache. This option makes git overwrite\n+\told cache or create a new one.\n+\n --check::\n \tWarn if changes introduce trailing whitespace\n \tor an indent that uses a space before a tab. Exits with\ndiff --git a/diff.c b/diff.c\nindex e368fef..1d65bd9 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -26,6 +26,7 @@ int diff_use_color_default = -1;\n static const char *external_diff_cmd_cfg;\n int diff_auto_refresh_index = 1;\n static int diff_mnemonic_prefix;\n+static int diff_cache_renames;\n \n static char diff_colors[][COLOR_MAXLEN] = {\n \t\"\\033[m\",\t/* reset */\n@@ -109,6 +110,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, \"diff.color.\") || !prefixcmp(var, \"color.diff.\")) {\n \t\tint slot = parse_diff_color_slot(var, 11);\n \t\tif (!value)\n@@ -2248,6 +2254,8 @@ int diff_setup_done(struct diff_options *options)\n \n \tif (options->detect_rename && options->rename_limit < 0)\n \t\toptions->rename_limit = diff_rename_limit_default;\n+\tif (options->detect_rename)\n+\t\toptions->cache_renames = diff_cache_renames;\n \tif (options->setup & DIFF_SETUP_USE_CACHE) {\n \t\tif (!active_cache)\n \t\t\t/* read-cache does not die even when it fails\n@@ -2415,6 +2423,10 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tDIFF_OPT_SET(options, RELATIVE_NAME);\n \t\toptions->prefix = arg + 11;\n \t}\n+\telse if (!strcmp(arg, \"--refresh-rename-cache\")) {\n+\t\toptions->cache_renames = 1;\n+\t\toptions->refresh_rename_cache = 1;\n+\t}\n \n \t/* xdiff options */\n \telse if (!strcmp(arg, \"-w\") || !strcmp(arg, \"--ignore-all-space\"))\ndiff --git a/diff.h b/diff.h\nindex 8b68f6f..eb97955 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -85,6 +85,8 @@ struct diff_options {\n \tint pickaxe_opts;\n \tint rename_score;\n \tint rename_limit;\n+\tint cache_renames;\n+\tint refresh_rename_cache;\n \tint warn_on_too_large_rename;\n \tint dirstat_percent;\n \tint setup;\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 598cc8d..2b87e4e 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -527,6 +527,44 @@ static void load_rename_cache(struct diff_queue_struct *q,\n \tfree_hash(&filepair_table);\n }\n \n+static void save_rename_cache(struct diff_queue_struct *outq,\n+\t\t\t struct diff_options *options)\n+{\n+\tint i;\n+\tFILE *fp = NULL;\n+\tstruct stat st;\n+\n+\tfor (i = 0;i < outq->nr; i++) {\n+\t\tstruct diff_filepair *dp = outq->queue[i];\n+\n+\t\tif (!(dp->renamed_pair || /* rename pair */\n+\t\t (!DIFF_FILE_VALID(dp->one) && DIFF_FILE_VALID(dp->two)))) /* create pair */\n+\t\t\tcontinue;\n+\n+\t\tif (!fp) {\n+\t\t\tchar *sha1 = sha1_to_hex(options->commit->object.sha1);\n+\t\t\tchar *path = git_path(\"rename-cache/%c%c/%s\", sha1[0], sha1[1], sha1+2);\n+\n+\t\t\t/* Already cached. If not force refresh, move on */\n+\t\t\tif (!stat(path, &st) && !options->refresh_rename_cache)\n+\t\t\t\treturn;\n+\n+\t\t\tsafe_create_leading_directories(path);\n+\t\t\tfp = fopen(path, \"w\");\n+\n+\t\t\tif (!fp)\n+\t\t\t\treturn;\n+\t\t}\n+\n+\t\tfprintf(fp, \"%s \", sha1_to_hex(dp->two->sha1));\n+\t\tfprintf(fp, \"%s %d\\n\",\n+\t\t\tsha1_to_hex(DIFF_FILE_VALID(dp->one) ? dp->one->sha1 : null_sha1),\n+\t\t\tdp->score);\n+\t}\n+\tif (fp)\n+\t\tfclose(fp);\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -770,6 +808,9 @@ void diffcore_rename(struct diff_options *options)\n \t}\n \tdiff_debug_queue(\"done copying original\", &outq);\n \n+\tif (options->commit && options->cache_renames)\n+\t\tsave_rename_cache(&outq, options);\n+\n \tfree(q->queue);\n \tif (cacheq.queue)\n \t\tfree(cacheq.queue);\ndiff --git a/t/t4030-rename-cache.sh b/t/t4030-rename-cache.sh\nindex 0d8390c..24d3667 100755\n--- a/t/t4030-rename-cache.sh\n+++ b/t/t4030-rename-cache.sh\n@@ -52,4 +52,31 @@ test_expect_success 'load create pair cache' '\n \ttest_cmp expected result\n '\n \n+cat >expected < /dev/null\n+\ttest_cmp expected $P\n+'\n+\n+test_expect_success 'subsequent command does not change cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\") &&\n+\techo corrupted >> $P\n+\t! test_cmp expected $P &&\n+\tgit show --summary -C -M --find-copies-harder HEAD > /dev/null &&\n+\t! test_cmp expected $P\n+'\n+\n+test_expect_success 'overwrite cache with --refresh-rename-cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\") &&\n+\t! test_cmp expected $P &&\n+\tgit show --summary -C -M --find-copies-harder --refresh-rename-cache HEAD > /dev/null &&\n+\ttest_cmp expected $P\n+'\n+\n test_done\n-- \n1.6.0.3.802.g47c38\n"},{"id":"95163","messageId":"20081107222128.GB4030@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"16210","inReplyTo":"1226068533-10152-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-11-07T22:21:28Z","receivedAt":"2008-11-07T22:21:28Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"On Fri, Nov 07, 2008 at 09:35:32PM +0700, Nguy???n Thái Ng???c Duy wrote:\n> This patch teaches diffcore_rename() to look into\n> $GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\n> With proper cache, there should be no available entry for estimation\n> after exact matching.\n\nThis is something I have thought about in the past, good to see that\nimplemented :)\n\n> Rename caching is per commit. I don't think abitrary tree-tree caching\n> is worth it.\n\nThat could be a nice complement to my directory-rename patch.\n"},{"id":"95174","messageId":"7vy6zvdt25.fsf@gitster.siamese.dyndns.org","threadId":"16210","inReplyTo":"20081107222128.GB4030@nan92-1-81-57-214-146.fbx.proxad.net","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-11-07T23:17:54Z","receivedAt":"2008-11-07T23:17:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yann Dirson writes:\n\n> On Fri, Nov 07, 2008 at 09:35:32PM +0700, Nguy???n Thái Ng???c Duy wrote:\n>> This patch teaches diffcore_rename() to look into\n>> $GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\n>> With proper cache, there should be no available entry for estimation\n>> after exact matching.\n>\n> This is something I have thought about in the past, good to see that\n> implemented :)\n>\n>> Rename caching is per commit. I don't think abitrary tree-tree caching\n>> is worth it.\n>\n> That could be a nice complement to my directory-rename patch.\n\nHas anybody thought about interaction between that caching and pathspec\nlimited operation?\n"},{"id":"95186","messageId":"fcaeb9bf0811072001o6df7ae00k1b1bffaadf75d3a1@mail.gmail.com","threadId":"16210","inReplyTo":"7vy6zvdt25.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-08T04:01:20Z","receivedAt":"2008-11-08T04:01:20Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On 11/8/08, Junio C Hamano wrote:\n> Yann Dirson writes:\n>\n> > On Fri, Nov 07, 2008 at 09:35:32PM +0700, Nguy???n Thái Ng???c Duy wrote:\n> >> This patch teaches diffcore_rename() to look into\n> >> $GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\n> >> With proper cache, there should be no available entry for estimation\n> >> after exact matching.\n> >\n> > This is something I have thought about in the past, good to see that\n> > implemented :)\n> >\n> >> Rename caching is per commit. I don't think abitrary tree-tree caching\n> >> is worth it.\n> >\n> > That could be a nice complement to my directory-rename patch.\n>\n>\n> Has anybody thought about interaction between that caching and pathspec\n> limited operation?\n>\n\nI didn't. But I think all out-of-pathspec diff pairs are removed\nbefore it reaches diffcore_rename() so the cache has nothing to do\nwith it (except it still loads full cache for a commit).\n-- \nDuy\n"},{"id":"95203","messageId":"20081108092409.GD4030@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"16210","inReplyTo":"fcaeb9bf0811072001o6df7ae00k1b1bffaadf75d3a1@mail.gmail.com","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-11-08T09:24:10Z","receivedAt":"2008-11-08T09:24:10Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"On Sat, Nov 08, 2008 at 11:01:20AM +0700, Nguyen Thai Ngoc Duy wrote:\n> On 11/8/08, Junio C Hamano wrote:\n> > Yann Dirson writes:\n> >\n> > > On Fri, Nov 07, 2008 at 09:35:32PM +0700, Nguy???n Thái Ng???c Duy wrote:\n> > >> This patch teaches diffcore_rename() to look into\n> > >> $GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\n> > >> With proper cache, there should be no available entry for estimation\n> > >> after exact matching.\n> > >\n> > > This is something I have thought about in the past, good to see that\n> > > implemented :)\n> > >\n> > >> Rename caching is per commit. I don't think abitrary tree-tree caching\n> > >> is worth it.\n> > >\n> > > That could be a nice complement to my directory-rename patch.\n> >\n> >\n> > Has anybody thought about interaction between that caching and pathspec\n> > limited operation?\n> >\n> \n> I didn't. But I think all out-of-pathspec diff pairs are removed\n> before it reaches diffcore_rename() so the cache has nothing to do\n> with it (except it still loads full cache for a commit).\n\nWell, it could be that an out-of-pathspec pair would have a better\nscore than an in-pathspec one. Maybe cache recording should be turned\noff when doing pathspec limitation ?\n"},{"id":"95204","messageId":"fcaeb9bf0811080129g7b97dd0au872ec66484a9a7f5@mail.gmail.com","threadId":"16210","inReplyTo":"20081108092409.GD4030@nan92-1-81-57-214-146.fbx.proxad.net","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-08T09:29:47Z","receivedAt":"2008-11-08T09:29:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On 11/8/08, Yann Dirson wrote:\n> On Sat, Nov 08, 2008 at 11:01:20AM +0700, Nguyen Thai Ngoc Duy wrote:\n> > On 11/8/08, Junio C Hamano wrote:\n> > > Yann Dirson writes:\n> > >\n> > > > On Fri, Nov 07, 2008 at 09:35:32PM +0700, Nguy???n Thái Ng???c Duy wrote:\n> > > >> This patch teaches diffcore_rename() to look into\n> > > >> $GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\n> > > >> With proper cache, there should be no available entry for estimation\n> > > >> after exact matching.\n> > > >\n> > > > This is something I have thought about in the past, good to see that\n> > > > implemented :)\n> > > >\n> > > >> Rename caching is per commit. I don't think abitrary tree-tree caching\n> > > >> is worth it.\n> > > >\n> > > > That could be a nice complement to my directory-rename patch.\n> > >\n> > >\n> > > Has anybody thought about interaction between that caching and pathspec\n> > > limited operation?\n> > >\n> >\n> > I didn't. But I think all out-of-pathspec diff pairs are removed\n> > before it reaches diffcore_rename() so the cache has nothing to do\n> > with it (except it still loads full cache for a commit).\n>\n>\n> Well, it could be that an out-of-pathspec pair would have a better\n> score than an in-pathspec one. Maybe cache recording should be turned\n> off when doing pathspec limitation ?\n\nRight, recording should be turned off or something. Let me see..\n-- \nDuy\n"},{"id":"95209","messageId":"20081108114719.GA4989@sigill.intra.peff.net","threadId":"16210","inReplyTo":"20081108092409.GD4030@nan92-1-81-57-214-146.fbx.proxad.net","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-11-08T11:47:20Z","receivedAt":"2008-11-08T11:47:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Nov 08, 2008 at 10:24:10AM +0100, Yann Dirson wrote:\n\n> Well, it could be that an out-of-pathspec pair would have a better\n> score than an in-pathspec one. Maybe cache recording should be turned\n> off when doing pathspec limitation ?\n\nOne thing I notice is that the cache works at the level of \"here is the\nbest rename for this commit.\" Maybe it could go down a level and say\n\"here is the inexact rename score between these blobs\". Then you would\nstill find the best score between two blobs each time, but save the\nreally computationally intensive part (which is comparing the actual\n_content_ of the blobs).\n\nThat should work in the face of path limiting or any other option,\nbecause it is caching something immutable: this is the similarity score\nbetween two pieces of content. And then you get arbitrary tree-to-tree\nspeedups for free, since such a cache would be valid for every commit.\n\nThe downsides are:\n\n - your cache is potentially bigger, since you are caching the score of\n every pair you look at, instead of just \"good\" pairs (OTOH, you are\n not doing a per-commit cache, which helps reduce the size)\n\n - you can still \"lie\" about a score to pre-seed imported SVN renames,\n but such lying will actually apply to all commits.\n\n-Peff\n"},{"id":"95211","messageId":"fcaeb9bf0811080400h7ea5377cvaa8d658335811c23@mail.gmail.com","threadId":"16210","inReplyTo":"20081108114719.GA4989@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-08T12:00:10Z","receivedAt":"2008-11-08T12:00:10Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On 11/8/08, Jeff King wrote:\n> On Sat, Nov 08, 2008 at 10:24:10AM +0100, Yann Dirson wrote:\n>\n> > Well, it could be that an out-of-pathspec pair would have a better\n> > score than an in-pathspec one. Maybe cache recording should be turned\n> > off when doing pathspec limitation ?\n>\n>\n> One thing I notice is that the cache works at the level of \"here is the\n> best rename for this commit.\" Maybe it could go down a level and say\n> \"here is the inexact rename score between these blobs\". Then you would\n> still find the best score between two blobs each time, but save the\n> really computationally intensive part (which is comparing the actual\n> _content_ of the blobs).\n> That should work in the face of path limiting or any other option,\n> because it is caching something immutable: this is the similarity score\n> between two pieces of content. And then you get arbitrary tree-to-tree\n> speedups for free, since such a cache would be valid for every commit.\n\nI did that and realized the cost was not from each diff, in\n--find-copies-harder case, but from the number of diffs you had to do.\nEven with exact matching on linux-2.6.git, it could take significant\ntime (it was about 5 minutes in no-cache case, 1 minute without exact\nmatch cache, and less than 1 sec if everything is cached).\n\n>\n> The downsides are:\n>\n> - your cache is potentially bigger, since you are caching the score of\n> every pair you look at, instead of just \"good\" pairs (OTOH, you are\n> not doing a per-commit cache, which helps reduce the size)\n\nIt is huge if you accidentially add --find-copies-harder to your\ncommand, considering that every new file will be compared against\nevery files in tree (about 25k).\n\n> - you can still \"lie\" about a score to pre-seed imported SVN renames,\n> but such lying will actually apply to all commits.\n-- \nDuy\n"},{"id":"95247","messageId":"20081109020413.GA31408@coredump.intra.peff.net","threadId":"16210","inReplyTo":"fcaeb9bf0811080400h7ea5377cvaa8d658335811c23@mail.gmail.com","subject":"Re: [PATCH 1/2] diffcore-rename: support rename cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-11-09T02:04:13Z","receivedAt":"2008-11-09T02:04:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Nov 08, 2008 at 07:00:10PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > The downsides are:\n> >\n> > - your cache is potentially bigger, since you are caching the score of\n> > every pair you look at, instead of just \"good\" pairs (OTOH, you are\n> > not doing a per-commit cache, which helps reduce the size)\n> \n> It is huge if you accidentially add --find-copies-harder to your\n> command, considering that every new file will be compared against\n> every files in tree (about 25k).\n\nHmm, yeah. I was thinking you might be able to do some kind of cut-off\non the caching (i.e., don't bother storing anything that didn't come\nclose). But you can't safely assume that because an entry isn't there,\nit isn't worth seeing (since it might also just not have been computed\nyet). You could still organize by commit, and then each commit is either\nfully computed or not. But then you still have a pathspec problem.\n\nOne thing you could do is just compute the rename score between all\npairs, even if a pathspec is given, limit it to values over \"0.5\" (or\nsomething low, but that eliminates the totally uninteresting cases), and\nthen store that as the complete cache for that commit (or tree pair, if\nyou want to support that).\n\nThen you would have the full information and could do an arbitrary\npathspec limit on it. If you wanted to set the rename threshold below\n0.5, then we would have to recompute without the cache (but in practice,\nthat should be rare).\n\nThe real downside is that you pay for the whole-tree detection when you\nhave asked for a pathspec (but only the first time, after which you can\nalways generate from cache).\n\nJust thinking out loud...\n\n-Peff\n"}]}