{"thread":{"id":"28052","subject":"git diff is slow (--patience is fast)","startedAt":"2011-08-09T07:51:44Z","lastAt":"2011-08-27T08:50:31Z","messageCount":16,"participants":["Marat Radchenko","Tay Ray Chuan","Junio C Hamano","Jeff King","Johannes Sixt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"173201","messageId":"loom.20110809T093124-847@post.gmane.org","threadId":"28052","inReplyTo":null,"subject":"git diff is slow (--patience is fast)","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2011-08-09T07:51:44Z","receivedAt":"2011-08-09T07:51:44Z","isPatch":false,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"Warning, downloaded files are 7.5Mb each.\n\n~ $ git --version\ngit version 1.7.6\n~ $ mkdir tmp\n~ $ cd tmp\n~/tmp $ git init\nInitialized empty Git repository in /home/marat/tmp/.git/\n~/tmp $ wget http://slonopotamus.org/git-diff/foo 2> /dev/null \n~/tmp $ git add -A\n~/tmp $ git commit -am \"initial\"\n[master (root-commit) 6b68e83] initial\n 1 files changed, 410461 insertions(+), 0 deletions(-)\n create mode 100644 foo\n~/tmp $ wget http://slonopotamus.org/git-diff/foo2 -O foo 2> /dev/null \n~/tmp $ time git diff > /dev/null \n\nreal    0m6.513s\nuser    0m6.490s\nsys     0m0.020s\n~/tmp $ time git diff --patience > /dev/null \n\nreal    0m0.237s\nuser    0m0.180s\nsys     0m0.050s\n\nCould something be done to `git diff` speed? I would be happy with patience \ndiff, but other git commands call standard diff algorithm internally without \ngiving an option to choose patience.\n\ngprof output against git master:\nhttp://slonopotamus.org/git-diff/gmon.txt\n"},{"id":"173205","messageId":"CALUzUxpOR-YZh-GKzivyKVpff9ue-t3qEoNK4wGsZZjX_a1=-A@mail.gmail.com","threadId":"28052","inReplyTo":"loom.20110809T093124-847@post.gmane.org","subject":"Re: git diff is slow (--patience is fast)","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-09T10:49:15Z","receivedAt":"2011-08-09T10:49:15Z","isPatch":false,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Tue, Aug 9, 2011 at 3:51 PM, Marat Radchenko <marat@slonopotamus.org> wrote:\n> Warning, downloaded files are 7.5Mb each.\n\nI'm having some speed issues. Is it possible to make your repo\npublicly available (eg github)? Perhaps the compression git does for\nits objects could help make downloads zippier.\n\n-- \nCheers,\nRay Chuan\n"},{"id":"173206","messageId":"loom.20110809T133735-979@post.gmane.org","threadId":"28052","inReplyTo":"CALUzUxpOR-YZh-GKzivyKVpff9ue-t3qEoNK4wGsZZjX_a1=-A@mail.gmail.com","subject":"Re: git diff is slow (--patience is fast)","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2011-08-09T11:39:12Z","receivedAt":"2011-08-09T11:39:12Z","isPatch":false,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"Good idea.\n\nNew steps to reproduce:\n~ $ git clone git://slonopotamus.org/git-diff\nCloning into git-diff...\nremote: Counting objects: 6, done.\nremote: Compressing objects: 100% (4/4), done.\nremote: Total 6 (delta 1), reused 0 (delta 0)\nReceiving objects: 100% (6/6), 478.87 KiB | 722 KiB/s, done.\nResolving deltas: 100% (1/1), done.\n~ $ cd git-diff\n~/git-diff $ time git diff HEAD^ > /dev/null \n\nreal    0m6.585s\nuser    0m6.540s\nsys     0m0.040s\n~/git-diff $ time git diff --patience HEAD^ > /dev/null \n\nreal    0m0.259s\nuser    0m0.220s\nsys     0m0.030s\n"},{"id":"173567","messageId":"CALUzUxopva0p28+OtVwy1gpfuzc9xVet7fGP4gne42n4W_8kcA@mail.gmail.com","threadId":"28052","inReplyTo":"loom.20110809T133735-979@post.gmane.org","subject":"Re: git diff is slow (--patience is fast)","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-16T03:01:26Z","receivedAt":"2011-08-16T03:01:26Z","isPatch":false,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Tue, Aug 9, 2011 at 7:39 PM, Marat Radchenko <marat@slonopotamus.org> wrote:\n> Good idea.\n>\n> New steps to reproduce:\n> ~ $ git clone git://slonopotamus.org/git-diff\n> Cloning into git-diff...\n\nThanks.\n\nI traced this to a O(n*m) spot in\nxdiff/xprepare.c::xdl_classify_record(). Patch coming up.\n\n-- \nCheers,\nRay Chuan\n"},{"id":"173568","messageId":"1313464312-5132-1-git-send-email-rctay89@gmail.com","threadId":"28052","inReplyTo":"loom.20110809T093124-847@post.gmane.org","subject":"[PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-16T03:11:52Z","receivedAt":"2011-08-16T03:11:52Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"In xdl_cleanup_records(), we see O(n*m) performance, where n is the\nnumber of records from xdf->dstart to xdf->dend, and m is the size of a\nbucket in xdf->rhash (<= by mlim).\n\nHere, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\nin xdl_classify_record().\n\nReported-by: Marat Radchenko <marat@slonopotamus.org>\nSigned-off-by: Tay Ray Chuan <rctay89@gmail.com>\n---\n\nOn my msysgit machine:\n  \n  rctay@TEST-123 /tmp/slono\n  $ time git show >/dev/null\n  \n  real    0m8.538s\n  user    0m0.000s\n  sys     0m0.031s\n  \n  rctay@TEST-123 /tmp/slono\n  $ time /git/git show >/dev/null\n  \n  real    0m0.672s\n  user    0m0.031s\n  sys     0m0.031s\n\n\n xdiff/xprepare.c |   87 +++++++++++++++++++++++++++++++-----------------------\n 1 files changed, 50 insertions(+), 37 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 620fc9a..1043fb7 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -36,6 +36,7 @@ typedef struct s_xdlclass {\n \tchar const *line;\n \tlong size;\n \tlong idx;\n+\tlong len1, len2;\n } xdlclass_t;\n \n typedef struct s_xdlclassifier {\n@@ -43,6 +44,8 @@ typedef struct s_xdlclassifier {\n \tlong hsize;\n \txdlclass_t **rchash;\n \tchastore_t ncha;\n+\txdlclass_t **rcrecs;\n+\tlong alloc;\n \tlong count;\n \tlong flags;\n } xdlclassifier_t;\n@@ -52,15 +55,15 @@ typedef struct s_xdlclassifier {\n \n static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);\n static void xdl_free_classifier(xdlclassifier_t *cf);\n-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n-\t\t\t       xrecord_t *rec);\n-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,\n+\t\t\t       unsigned int hbits, xrecord_t *rec);\n+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf);\n static void xdl_free_ctx(xdfile_t *xdf);\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e);\n-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);\n-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n \n \n \n@@ -82,6 +85,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {\n \t}\n \tmemset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *));\n \n+\tcf->alloc = size;\n+\tif (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {\n+\n+\t\txdl_free(cf->rchash);\n+\t\txdl_cha_free(&cf->ncha);\n+\t\treturn -1;\n+\t}\n+\n \tcf->count = 0;\n \n \treturn 0;\n@@ -95,11 +106,12 @@ static void xdl_free_classifier(xdlclassifier_t *cf) {\n }\n \n \n-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n-\t\t\t       xrecord_t *rec) {\n+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,\n+\t\t\t       unsigned int hbits, xrecord_t *rec) {\n \tlong hi;\n \tchar const *line;\n \txdlclass_t *rcrec;\n+\txdlclass_t **rcrecs;\n \n \tline = rec->ptr;\n \thi = (long) XDL_HASHLONG(rec->ha, cf->hbits);\n@@ -115,13 +127,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n \t\t\treturn -1;\n \t\t}\n \t\trcrec->idx = cf->count++;\n+\t\tif (cf->count > cf->alloc) {\n+\t\t\tcf->alloc *= 2;\n+\t\t\tif (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {\n+\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\tcf->rcrecs = rcrecs;\n+\t\t}\n+\t\tcf->rcrecs[rcrec->idx] = rcrec;\n \t\trcrec->line = line;\n \t\trcrec->size = rec->size;\n \t\trcrec->ha = rec->ha;\n+\t\trcrec->len1 = rcrec->len2 = 0;\n \t\trcrec->next = cf->rchash[hi];\n \t\tcf->rchash[hi] = rcrec;\n \t}\n \n+\t(pass == 1) ? rcrec->len1++ : rcrec->len2++;\n+\n \trec->ha = (unsigned long) rcrec->idx;\n \n \thi = (long) XDL_HASHLONG(rec->ha, hbits);\n@@ -132,7 +156,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n }\n \n \n-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf) {\n \tunsigned int hbits;\n \tlong nrec, hsize, bsize;\n@@ -185,7 +209,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\trecs[nrec++] = crec;\n \n \t\t\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n-\t\t\t\txdl_classify_record(cf, rhash, hbits, crec) < 0)\n+\t\t\t\txdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n \t\t\t\tgoto abort;\n \t\t}\n \t}\n@@ -257,30 +281,30 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \n-\tif (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n+\tif (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n \n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n-\tif (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n+\tif (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf1);\n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n \n-\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF))\n-\t\txdl_free_classifier(&cf);\n-\n \tif (!(xpp->flags & XDF_PATIENCE_DIFF) &&\n \t\t\t!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n-\t\t\txdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n+\t\t\txdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf2);\n \t\txdl_free_ctx(&xe->xdf1);\n \t\treturn -1;\n \t}\n \n+\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF))\n+\t\txdl_free_classifier(&cf);\n+\n \treturn 0;\n }\n \n@@ -355,11 +379,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n  * matches on the other file. Also, lines that have multiple matches\n  * might be potentially discarded if they happear in a run of discardable.\n  */\n-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n-\tlong i, nm, rhi, nreff, mlim;\n-\tunsigned long hav;\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n+\tlong i, nm, nreff;\n \txrecord_t **recs;\n-\txrecord_t *rec;\n+\txdlclass_t *rcrec;\n \tchar *dis, *dis1, *dis2;\n \n \tif (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {\n@@ -370,26 +393,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n \tdis1 = dis;\n \tdis2 = dis1 + xdf1->nrec + 1;\n \n-\tif ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)\n-\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n-\t\thav = (*recs)->ha;\n-\t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n-\t\tfor (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n-\t\t\t\tbreak;\n-\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\trcrec = cf->rcrecs[(*recs)->ha];\n+\t\tnm = rcrec ? rcrec->len2 : 0;\n+\t\tdis1[i] = (nm == 0) ? 0: 1;\n \t}\n \n-\tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n-\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n-\t\thav = (*recs)->ha;\n-\t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n-\t\tfor (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n-\t\t\t\tbreak;\n-\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\trcrec = cf->rcrecs[(*recs)->ha];\n+\t\tnm = rcrec ? rcrec->len1 : 0;\n+\t\tdis2[i] = (nm == 0) ? 0: 1;\n \t}\n \n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n@@ -451,10 +464,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {\n }\n \n \n-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n \n \tif (xdl_trim_ends(xdf1, xdf2) < 0 ||\n-\t    xdl_cleanup_records(xdf1, xdf2) < 0) {\n+\t    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {\n \n \t\treturn -1;\n \t}\n-- \n1.7.6\n"},{"id":"173569","messageId":"20110816113710.000025a7@unknown","threadId":"28052","inReplyTo":"1313464312-5132-1-git-send-email-rctay89@gmail.com","subject":"Re: [PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-16T03:37:10Z","receivedAt":"2011-08-16T03:37:10Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":">From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001\nFrom: Tay Ray Chuan <rctay89@gmail.com>\nDate: Tue, 16 Aug 2011 11:35:28 +0800\nSubject: [PATCH] xdiff/xprepare: improve O(n*m) performance in\n xdl_cleanup_records()\n\nIn xdl_cleanup_records(), we see O(n*m) performance, where n is the\nnumber of records from xdf->dstart to xdf->dend, and m is the size of a\nbucket in xdf->rhash (<= by mlim).\n\nHere, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\nin xdl_classify_record().\n\nReported-by: Marat Radchenko <marat@slonopotamus.org>\nSigned-off-by: Tay Ray Chuan <rctay89@gmail.com>\n---\n\nJunio, this one is rebased on v1.7.6, instead of rc/histogram-diff.\n\n xdiff/xprepare.c |   85 +++++++++++++++++++++++++++++++-----------------------\n 1 files changed, 49 insertions(+), 36 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 1689085..ebbec19 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -34,6 +34,7 @@ typedef struct s_xdlclass {\n \tchar const *line;\n \tlong size;\n \tlong idx;\n+\tlong len1, len2;\n } xdlclass_t;\n \n typedef struct s_xdlclassifier {\n@@ -41,6 +42,8 @@ typedef struct s_xdlclassifier {\n \tlong hsize;\n \txdlclass_t **rchash;\n \tchastore_t ncha;\n+\txdlclass_t **rcrecs;\n+\tlong alloc;\n \tlong count;\n \tlong flags;\n } xdlclassifier_t;\n@@ -50,15 +53,15 @@ typedef struct s_xdlclassifier {\n \n static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);\n static void xdl_free_classifier(xdlclassifier_t *cf);\n-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n-\t\t\t       xrecord_t *rec);\n-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,\n+\t\t\t       unsigned int hbits, xrecord_t *rec);\n+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf);\n static void xdl_free_ctx(xdfile_t *xdf);\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e);\n-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);\n-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n \n \n \n@@ -83,6 +86,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {\n \tfor (i = 0; i < cf->hsize; i++)\n \t\tcf->rchash[i] = NULL;\n \n+\tcf->alloc = size;\n+\tif (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {\n+\n+\t\txdl_free(cf->rchash);\n+\t\txdl_cha_free(&cf->ncha);\n+\t\treturn -1;\n+\t}\n+\n \tcf->count = 0;\n \n \treturn 0;\n@@ -96,11 +107,12 @@ static void xdl_free_classifier(xdlclassifier_t *cf) {\n }\n \n \n-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n-\t\t\t       xrecord_t *rec) {\n+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,\n+\t\t\t       unsigned int hbits, xrecord_t *rec) {\n \tlong hi;\n \tchar const *line;\n \txdlclass_t *rcrec;\n+\txdlclass_t **rcrecs;\n \n \tline = rec->ptr;\n \thi = (long) XDL_HASHLONG(rec->ha, cf->hbits);\n@@ -116,13 +128,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n \t\t\treturn -1;\n \t\t}\n \t\trcrec->idx = cf->count++;\n+\t\tif (cf->count > cf->alloc) {\n+\t\t\tcf->alloc *= 2;\n+\t\t\tif (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {\n+\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\tcf->rcrecs = rcrecs;\n+\t\t}\n+\t\tcf->rcrecs[rcrec->idx] = rcrec;\n \t\trcrec->line = line;\n \t\trcrec->size = rec->size;\n \t\trcrec->ha = rec->ha;\n+\t\trcrec->len1 = rcrec->len2 = 0;\n \t\trcrec->next = cf->rchash[hi];\n \t\tcf->rchash[hi] = rcrec;\n \t}\n \n+\t(pass == 1) ? rcrec->len1++ : rcrec->len2++;\n+\n \trec->ha = (unsigned long) rcrec->idx;\n \n \thi = (long) XDL_HASHLONG(rec->ha, hbits);\n@@ -133,7 +157,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n }\n \n \n-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf) {\n \tunsigned int hbits;\n \tlong i, nrec, hsize, bsize;\n@@ -200,7 +224,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\tcrec->ha = hav;\n \t\t\trecs[nrec++] = crec;\n \n-\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0) {\n+\t\t\tif (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) {\n \n \t\t\t\txdl_free(rhash);\n \t\t\t\txdl_free(recs);\n@@ -276,28 +300,28 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \n-\tif (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n+\tif (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n \n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n-\tif (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n+\tif (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf1);\n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n \n-\txdl_free_classifier(&cf);\n-\n \tif (!(xpp->flags & XDF_PATIENCE_DIFF) &&\n-\t\t\txdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n+\t\t\txdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf2);\n \t\txdl_free_ctx(&xe->xdf1);\n \t\treturn -1;\n \t}\n \n+\txdl_free_classifier(&cf);\n+\n \treturn 0;\n }\n \n@@ -372,11 +396,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n  * matches on the other file. Also, lines that have multiple matches\n  * might be potentially discarded if they happear in a run of discardable.\n  */\n-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n-\tlong i, nm, rhi, nreff, mlim;\n-\tunsigned long hav;\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n+\tlong i, nm, nreff;\n \txrecord_t **recs;\n-\txrecord_t *rec;\n+\txdlclass_t *rcrec;\n \tchar *dis, *dis1, *dis2;\n \n \tif (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {\n@@ -387,26 +410,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n \tdis1 = dis;\n \tdis2 = dis1 + xdf1->nrec + 1;\n \n-\tif ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)\n-\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n-\t\thav = (*recs)->ha;\n-\t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n-\t\tfor (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n-\t\t\t\tbreak;\n-\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\trcrec = cf->rcrecs[(*recs)->ha];\n+\t\tnm = rcrec ? rcrec->len2 : 0;\n+\t\tdis1[i] = (nm == 0) ? 0: 1;\n \t}\n \n-\tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n-\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n-\t\thav = (*recs)->ha;\n-\t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n-\t\tfor (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n-\t\t\t\tbreak;\n-\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\trcrec = cf->rcrecs[(*recs)->ha];\n+\t\tnm = rcrec ? rcrec->len1 : 0;\n+\t\tdis2[i] = (nm == 0) ? 0: 1;\n \t}\n \n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n@@ -468,10 +481,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {\n }\n \n \n-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n \n \tif (xdl_trim_ends(xdf1, xdf2) < 0 ||\n-\t    xdl_cleanup_records(xdf1, xdf2) < 0) {\n+\t    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {\n \n \t\treturn -1;\n \t}\n-- \n1.7.6\n"},{"id":"173622","messageId":"7vd3g5i7ci.fsf@alter.siamese.dyndns.org","threadId":"28052","inReplyTo":"20110816113710.000025a7@unknown","subject":"Re: [PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-16T17:39:25Z","receivedAt":"2011-08-16T17:39:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Tay Ray Chuan <rctay89@gmail.com> writes:\n\n> From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001\n> From: Tay Ray Chuan <rctay89@gmail.com>\n> Date: Tue, 16 Aug 2011 11:35:28 +0800\n> Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in\n>  xdl_cleanup_records()\n\nYou do not need these four lines. Thanks.\n\n> In xdl_cleanup_records(), we see O(n*m) performance, where n is the\n> number of records from xdf->dstart to xdf->dend, and m is the size of a\n> bucket in xdf->rhash (<= by mlim).\n>\n> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\n> in xdl_classify_record().\n\nCould we have some benchmarks to let the readers get a feel of how much\nimprovement this patch brings in?\n\nThis tries to trade cycles with memory, right? How much bloat are we\ntalking about here?\n"},{"id":"173655","messageId":"1313546037-4104-1-git-send-email-rctay89@gmail.com","threadId":"28052","inReplyTo":"7vd3g5i7ci.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-17T01:53:57Z","receivedAt":"2011-08-17T01:53:57Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"In xdl_cleanup_records(), we see O(n*m) performance, where n is the\nnumber of records from xdf->dstart to xdf->dend, and m is the size of a\nbucket in xdf->rhash (<= by mlim).\n\nHere, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\nin xdl_classify_record().\n\nReported-by: Marat Radchenko <marat@slonopotamus.org>\nSigned-off-by: Tay Ray Chuan <rctay89@gmail.com>\n---\n\nChanged in v2:\n - free() xdlclassifier_t->rcrecs\n\nOn Wed, Aug 17, 2011 at 1:39 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Tay Ray Chuan <rctay89@gmail.com> writes:\n>\n>> From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001\n>> From: Tay Ray Chuan <rctay89@gmail.com>\n>> Date: Tue, 16 Aug 2011 11:35:28 +0800\n>> Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in\n>> ?xdl_cleanup_records()\n>\n> You do not need these four lines. Thanks.\n\nOops, I directly pasted git-format-patch output into Claws-mail, sorry\nabout that.\n\n>> In xdl_cleanup_records(), we see O(n*m) performance, where n is the\n>> number of records from xdf->dstart to xdf->dend, and m is the size of a\n>> bucket in xdf->rhash (<= by mlim).\n>>\n>> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\n>> in xdl_classify_record().\n>\n> Could we have some benchmarks to let the readers get a feel of how much\n> improvement this patch brings in?\n\nOn my msysgit machine with Marat's problematic repo\n(git://slonopotamus.org/git-diff):\n\n rctay@TEST-123 /tmp/slono\n $ time git show >/dev/null\n\n real    0m8.538s\n user    0m0.000s\n sys     0m0.031s\n\n rctay@TEST-123 /tmp/slono\n $ time /git/git show >/dev/null\n\n real    0m0.672s\n user    0m0.031s\n sys     0m0.031s\n\n> This tries to trade cycles with memory, right? How much bloat are we\n> talking about here?\n\nThe main source of memory bloat would be the xdlclassifier_t->rcrecs\nlookup table. This is needed to find the classifier record (xdlclass_t)\nassociated with a xrecord_t.\n\nIn an earlier iteration, I had a pointer on each xrecord_t to the\nclassifier record, instead of a lookup table, but I casted it to void*,\nsince I wasn't sure if the xdlclass_t definition should be shifted to\nxtypes.h (and thus made public to xdiff and git).\n\nThe first is cleaner but the second is lighter. I'd appreciate comments\non this.\n\n xdiff/xprepare.c |   86 +++++++++++++++++++++++++++++++----------------------\n 1 files changed, 50 insertions(+), 36 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 1689085..05a8f01 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -34,6 +34,7 @@ typedef struct s_xdlclass {\n \tchar const *line;\n \tlong size;\n \tlong idx;\n+\tlong len1, len2;\n } xdlclass_t;\n\n typedef struct s_xdlclassifier {\n@@ -41,6 +42,8 @@ typedef struct s_xdlclassifier {\n \tlong hsize;\n \txdlclass_t **rchash;\n \tchastore_t ncha;\n+\txdlclass_t **rcrecs;\n+\tlong alloc;\n \tlong count;\n \tlong flags;\n } xdlclassifier_t;\n@@ -50,15 +53,15 @@ typedef struct s_xdlclassifier {\n\n static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);\n static void xdl_free_classifier(xdlclassifier_t *cf);\n-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n-\t\t\t       xrecord_t *rec);\n-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,\n+\t\t\t       unsigned int hbits, xrecord_t *rec);\n+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf);\n static void xdl_free_ctx(xdfile_t *xdf);\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e);\n-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);\n-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);\n\n\n\n@@ -83,6 +86,14 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {\n \tfor (i = 0; i < cf->hsize; i++)\n \t\tcf->rchash[i] = NULL;\n\n+\tcf->alloc = size;\n+\tif (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {\n+\n+\t\txdl_free(cf->rchash);\n+\t\txdl_cha_free(&cf->ncha);\n+\t\treturn -1;\n+\t}\n+\n \tcf->count = 0;\n\n \treturn 0;\n@@ -91,16 +102,18 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {\n\n static void xdl_free_classifier(xdlclassifier_t *cf) {\n\n+\txdl_free(cf->rcrecs);\n \txdl_free(cf->rchash);\n \txdl_cha_free(&cf->ncha);\n }\n\n\n-static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n-\t\t\t       xrecord_t *rec) {\n+static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,\n+\t\t\t       unsigned int hbits, xrecord_t *rec) {\n \tlong hi;\n \tchar const *line;\n \txdlclass_t *rcrec;\n+\txdlclass_t **rcrecs;\n\n \tline = rec->ptr;\n \thi = (long) XDL_HASHLONG(rec->ha, cf->hbits);\n@@ -116,13 +129,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n \t\t\treturn -1;\n \t\t}\n \t\trcrec->idx = cf->count++;\n+\t\tif (cf->count > cf->alloc) {\n+\t\t\tcf->alloc *= 2;\n+\t\t\tif (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {\n+\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\tcf->rcrecs = rcrecs;\n+\t\t}\n+\t\tcf->rcrecs[rcrec->idx] = rcrec;\n \t\trcrec->line = line;\n \t\trcrec->size = rec->size;\n \t\trcrec->ha = rec->ha;\n+\t\trcrec->len1 = rcrec->len2 = 0;\n \t\trcrec->next = cf->rchash[hi];\n \t\tcf->rchash[hi] = rcrec;\n \t}\n\n+\t(pass == 1) ? rcrec->len1++ : rcrec->len2++;\n+\n \trec->ha = (unsigned long) rcrec->idx;\n\n \thi = (long) XDL_HASHLONG(rec->ha, hbits);\n@@ -133,7 +158,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n }\n\n\n-static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n+static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t   xdlclassifier_t *cf, xdfile_t *xdf) {\n \tunsigned int hbits;\n \tlong i, nrec, hsize, bsize;\n@@ -200,7 +225,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\tcrec->ha = hav;\n \t\t\trecs[nrec++] = crec;\n\n-\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0) {\n+\t\t\tif (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) {\n\n \t\t\t\txdl_free(rhash);\n \t\t\t\txdl_free(recs);\n@@ -276,28 +301,28 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n\n-\tif (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n+\tif (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n\n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n-\tif (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n+\tif (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n\n \t\txdl_free_ctx(&xe->xdf1);\n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n\n-\txdl_free_classifier(&cf);\n-\n \tif (!(xpp->flags & XDF_PATIENCE_DIFF) &&\n-\t\t\txdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n+\t\t\txdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {\n\n \t\txdl_free_ctx(&xe->xdf2);\n \t\txdl_free_ctx(&xe->xdf1);\n \t\treturn -1;\n \t}\n\n+\txdl_free_classifier(&cf);\n+\n \treturn 0;\n }\n\n@@ -372,11 +397,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n  * matches on the other file. Also, lines that have multiple matches\n  * might be potentially discarded if they happear in a run of discardable.\n  */\n-static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n-\tlong i, nm, rhi, nreff, mlim;\n-\tunsigned long hav;\n+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n+\tlong i, nm, nreff;\n \txrecord_t **recs;\n-\txrecord_t *rec;\n+\txdlclass_t *rcrec;\n \tchar *dis, *dis1, *dis2;\n\n \tif (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {\n@@ -387,26 +411,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n \tdis1 = dis;\n \tdis2 = dis1 + xdf1->nrec + 1;\n\n-\tif ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)\n-\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n-\t\thav = (*recs)->ha;\n-\t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n-\t\tfor (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n-\t\t\t\tbreak;\n-\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\trcrec = cf->rcrecs[(*recs)->ha];\n+\t\tnm = rcrec ? rcrec->len2 : 0;\n+\t\tdis1[i] = (nm == 0) ? 0: 1;\n \t}\n\n-\tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n-\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n-\t\thav = (*recs)->ha;\n-\t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n-\t\tfor (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++nm == mlim)\n-\t\t\t\tbreak;\n-\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n+\t\trcrec = cf->rcrecs[(*recs)->ha];\n+\t\tnm = rcrec ? rcrec->len1 : 0;\n+\t\tdis2[i] = (nm == 0) ? 0: 1;\n \t}\n\n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n@@ -468,10 +482,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {\n }\n\n\n-static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {\n+static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {\n\n \tif (xdl_trim_ends(xdf1, xdf2) < 0 ||\n-\t    xdl_cleanup_records(xdf1, xdf2) < 0) {\n+\t    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {\n\n \t\treturn -1;\n \t}\n--\n1.7.6.12.g6486a.dirty\n"},{"id":"173662","messageId":"20110817052147.GA11253@sigill.intra.peff.net","threadId":"28052","inReplyTo":"1313546037-4104-1-git-send-email-rctay89@gmail.com","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-17T05:21:47Z","receivedAt":"2011-08-17T05:21:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 17, 2011 at 09:53:57AM +0800, Tay Ray Chuan wrote:\n\n> > Could we have some benchmarks to let the readers get a feel of how much\n> > improvement this patch brings in?\n> \n> On my msysgit machine with Marat's problematic repo\n> (git://slonopotamus.org/git-diff):\n> \n>  rctay@TEST-123 /tmp/slono\n>  $ time git show >/dev/null\n> \n>  real    0m8.538s\n>  user    0m0.000s\n>  sys     0m0.031s\n> \n>  rctay@TEST-123 /tmp/slono\n>  $ time /git/git show >/dev/null\n> \n>  real    0m0.672s\n>  user    0m0.031s\n>  sys     0m0.031s\n\nWait, what? It was using 0 seconds of user time before, but still taking\n8.5 seconds? What was it doing? Did you actually warm up your disk cache\nbefore taking these measurements?\n\n-Peff\n"},{"id":"173678","messageId":"CALUzUxovdmhnRKPaEq01-q0pvez91s_Z_rHWg-FkwcU0VD3HQQ@mail.gmail.com","threadId":"28052","inReplyTo":"20110817052147.GA11253@sigill.intra.peff.net","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-17T15:55:32Z","receivedAt":"2011-08-17T15:55:32Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Wed, Aug 17, 2011 at 1:21 PM, Jeff King <peff@peff.net> wrote:\n> Wait, what? It was using 0 seconds of user time before, but still taking\n> 8.5 seconds? What was it doing? Did you actually warm up your disk cache\n> before taking these measurements?\n\nThree runs on the same machine, after a restart.\n\n  $ time git show >/dev/null\n\n  real    0m6.505s\n  user    0m0.031s\n  sys     0m0.015s\n\n  rctay@TEST-123 /tmp/slono\n  $ time git show >/dev/null\n\n  real    0m5.429s\n  user    0m0.000s\n  sys     0m0.031s\n\n  rctay@TEST-123 /tmp/slono\n  $ time git show >/dev/null\n\n  real    0m5.336s\n  user    0m0.000s\n  sys     0m0.016s\n\n-- \nCheers,\nRay Chuan\n"},{"id":"173807","messageId":"20110818224427.GB8481@sigill.intra.peff.net","threadId":"28052","inReplyTo":"CALUzUxovdmhnRKPaEq01-q0pvez91s_Z_rHWg-FkwcU0VD3HQQ@mail.gmail.com","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-18T22:44:27Z","receivedAt":"2011-08-18T22:44:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 17, 2011 at 11:55:32PM +0800, Tay Ray Chuan wrote:\n\n> On Wed, Aug 17, 2011 at 1:21 PM, Jeff King <peff@peff.net> wrote:\n> > Wait, what? It was using 0 seconds of user time before, but still taking\n> > 8.5 seconds? What was it doing? Did you actually warm up your disk cache\n> > before taking these measurements?\n> \n> Three runs on the same machine, after a restart.\n> \n>   $ time git show >/dev/null\n> \n>   real    0m6.505s\n>   user    0m0.031s\n>   sys     0m0.015s\n> [...]\n\nSo it is spending only .046s of CPU time, but is taking 6.5 seconds of\nwall clock time. Which implies to me that the dataset doesn't fit in\nyour disk cache, or it is swapping a lot. Or you are on a really\nbogged-down multiuser system. :)\n\nBut if I understand correctly, your patch is about increasing runtime\nperformance of a slow algorithm. So is actually the improvement of an\nO(m*n) algorithm to an O(n) one, or does your new algorithm have better\nmemory access patterns that avoid trashing swap?\n\nDownloading the files from the original problem report, I see much\ndifferent timings:\n\n  [before]\n  $ time git diff >/dev/null\n  real    0m7.690s\n  user    0m7.648s\n  sys     0m0.024s\n\n  [after (your v2 patch)]\n  real    0m0.272s\n  user    0m0.236s\n  sys     0m0.036s\n\nSo I think your patch _is_ an improvement in algorithmic runtime. I just\ndon't see how your numbers make any sense. Am I missing something? Is\nmsysgit's bash \"time\" just broken?\n\n-Peff\n"},{"id":"173867","messageId":"CALUzUxoPwNhziRX3WU-YhSEXkjm_FvVLmN=pAffexr-QpmhGgg@mail.gmail.com","threadId":"28052","inReplyTo":"20110818224427.GB8481@sigill.intra.peff.net","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-19T17:12:49Z","receivedAt":"2011-08-19T17:12:49Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Fri, Aug 19, 2011 at 6:44 AM, Jeff King <peff@peff.net> wrote:\n> On Wed, Aug 17, 2011 at 11:55:32PM +0800, Tay Ray Chuan wrote:\n>\n>> On Wed, Aug 17, 2011 at 1:21 PM, Jeff King <peff@peff.net> wrote:\n>> > Wait, what? It was using 0 seconds of user time before, but still taking\n>> > 8.5 seconds? What was it doing? Did you actually warm up your disk cache\n>> > before taking these measurements?\n>>\n>> Three runs on the same machine, after a restart.\n>>\n>>   $ time git show >/dev/null\n>>\n>>   real    0m6.505s\n>>   user    0m0.031s\n>>   sys     0m0.015s\n>> [...]\n>\n> So it is spending only .046s of CPU time, but is taking 6.5 seconds of\n> wall clock time. Which implies to me that the dataset doesn't fit in\n> your disk cache, or it is swapping a lot. Or you are on a really\n> bogged-down multiuser system. :)\n>\n> But if I understand correctly, your patch is about increasing runtime\n> performance of a slow algorithm. So is actually the improvement of an\n> O(m*n) algorithm to an O(n) one, or does your new algorithm have better\n> memory access patterns that avoid trashing swap?\n>\n> [snip]\n>\n> So I think your patch _is_ an improvement in algorithmic runtime. I just\n> don't see how your numbers make any sense. Am I missing something? Is\n> msysgit's bash \"time\" just broken?\n\nNope, available memory is more than enough, so I don't believe\nswapping is taking place. I think it's more likely that it's an issue\nwith time on msysgit.\n\nJohannes, care to shed some light on this?\n\n-- \nCheers,\nRay Chuan\n"},{"id":"173954","messageId":"4E50CED3.10704@kdbg.org","threadId":"28052","inReplyTo":"CALUzUxoPwNhziRX3WU-YhSEXkjm_FvVLmN=pAffexr-QpmhGgg@mail.gmail.com","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2011-08-21T09:24:35Z","receivedAt":"2011-08-21T09:24:35Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 19.08.2011 19:12, schrieb Tay Ray Chuan:\n>> Is msysgit's bash \"time\" just broken?\n\nI think it is broken. The only thing I would use it is to record elapsed \ntime (the 'real' part).\n\n-- Hannes\n"},{"id":"174138","messageId":"loom.20110824T082807-840@post.gmane.org","threadId":"28052","inReplyTo":"1313546037-4104-1-git-send-email-rctay89@gmail.com","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2011-08-24T06:29:12Z","receivedAt":"2011-08-24T06:29:12Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"Tay Ray Chuan <rctay89 <at> gmail.com> writes:\n> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\n> in xdl_classify_record().\n> \n> Reported-by: Marat Radchenko <marat <at> slonopotamus.org>\n> Signed-off-by: Tay Ray Chuan <rctay89 <at> gmail.com>\n\nSo, will this be applied to git master? Very impressive speed improvement.\n"},{"id":"174139","messageId":"loom.20110824T083156-530@post.gmane.org","threadId":"28052","inReplyTo":"loom.20110824T082807-840@post.gmane.org","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2011-08-24T06:32:53Z","receivedAt":"2011-08-24T06:32:53Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"Marat Radchenko <marat <at> slonopotamus.org> writes:\n> So, will this be applied to git master? Very impressive speed improvement.\n\nSorry, just discovered it is already in pu.\n"},{"id":"174374","messageId":"1314435031.9095.2.camel@n900.home.ru","threadId":"28052","inReplyTo":"1313546037-4104-1-git-send-email-rctay89@gmail.com","subject":"Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()","fromName":"Marat Radchenko","fromEmail":"marat@slonopotamus.org","sentAt":"2011-08-27T08:50:31Z","receivedAt":"2011-08-27T08:50:31Z","isPatch":true,"sender":{"key":"marat@slonopotamus.org","avatar":"https://avatars.githubusercontent.com/u/92637?v=4"},"body":"On ср 17 авг 2011 05:53:57 MSD, Tay Ray Chuan <rctay89@gmail.com> wrote:\n\n> In xdl_cleanup_records(), we see O(n*m) performance, where n is the\n> number of records from xdf->dstart to xdf->dend, and m is the size of a\n> bucket in xdf->rhash (<= by mlim).\n> \n> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))\n> in xdl_classify_record().\n\nThanks for your patch, btw, now diff is much faster\n"}]}