{"thread":{"id":"28176","subject":"[PATCH 1/2] fast-import: count and report # of calls to diff_delta in stats","startedAt":"2011-08-20T19:04:10Z","lastAt":"2011-08-21T11:01:09Z","messageCount":5,"participants":["Dmitry Ivankov","Jonathan Nieder","David Michael Barr"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"173930","messageId":"1313867052-11993-1-git-send-email-divanorama@gmail.com","threadId":"28176","inReplyTo":null,"subject":"[PATCH 0/2] fast-import: improve deltas for blobs","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-20T19:04:10Z","receivedAt":"2011-08-20T19:04:10Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Currently delta base for blob objects is just a previous blob object\nwritten. This way we just keep the last one in memory and it's cheap\n(not too smart though and gains no pack size reduction most of the time).\nIf we also keep as last blob a response to cat-blob (whose main purpose\nis to provide delta bases for a importer), svn-fe imports become faster\nand packs produced become smaller.\n\n1/2 adds a diff_delta attemps count as a related and interesting number\n2/2 gives a nice performance improvement for svn-fe produced imports\n\nDmitry Ivankov (2):\n fast-import: count and report # of calls to diff_delta in stats\n fast-import: treat cat-blob as a delta base hint for next blob\n\n fast-import.c | 17 ++++++++++++-----\n 1 files changed, 12 insertions(+), 5 deletions(-)\n\n-- \n1.7.3.4\n"},{"id":"173929","messageId":"1313867052-11993-2-git-send-email-divanorama@gmail.com","threadId":"28176","inReplyTo":"1313867052-11993-1-git-send-email-divanorama@gmail.com","subject":"[PATCH 1/2] fast-import: count and report # of calls to diff_delta in stats","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-20T19:04:11Z","receivedAt":"2011-08-20T19:04:11Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"It's an interesting number, how often do we try to deltify each type of\nobjects and how often do we succeed. So do add it to stats.\n\nSuccess doesn't mean much gain in pack size though. As we allow delta to\nbe as big as (data.len - 20). And delta close to data.len gains nothing\ncompared to no delta at all even after zlib compression (delta is pretty\nmuch the same as data, just with few modifications).\n\nWe should try to make less attempts that result in huge deltas as these\nconsume more cpu than trivial small deltas. Either by choosing a better\ndelta base or reducing delta size upper bound or doing less delta attempts\nat all.\n\nCurrently, delta base for blobs is a waste literally. Each blob delta\nbase is chosen as a previously stored blob. Disabling deltas for blobs\ndoesn't increase pack size and reduce import time, or at least doesn't\nincrease time for all fast-import streams I've tried.\n\nSigned-off-by: Dmitry Ivankov \n---\n fast-import.c | 10 ++++++----\n 1 files changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 7cc2262..2b069e3 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -284,6 +284,7 @@ static uintmax_t marks_set_count;\n static uintmax_t object_count_by_type[1 << TYPE_BITS];\n static uintmax_t duplicate_count_by_type[1 << TYPE_BITS];\n static uintmax_t delta_count_by_type[1 << TYPE_BITS];\n+static uintmax_t delta_count_attempts_by_type[1 << TYPE_BITS];\n static unsigned long object_count;\n static unsigned long branch_count;\n static unsigned long branch_load_count;\n@@ -1045,6 +1046,7 @@ static int store_object(\n \t}\n \n \tif (last && last->data.buf && last->depth < max_depth && dat->len > 20) {\n+\t\tdelta_count_attempts_by_type[type]++;\n \t\tdelta = diff_delta(last->data.buf, last->data.len,\n \t\t\tdat->buf, dat->len,\n \t\t\t&deltalen, dat->len - 20);\n@@ -3338,10 +3340,10 @@ int main(int argc, const char **argv)\n \t\tfprintf(stderr, \"---------------------------------------------------------------------\\n\");\n \t\tfprintf(stderr, \"Alloc'd objects: %10\" PRIuMAX \"\\n\", alloc_count);\n \t\tfprintf(stderr, \"Total objects: %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates )\\n\", total_count, duplicate_count);\n-\t\tfprintf(stderr, \" blobs : %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas)\\n\", object_count_by_type[OBJ_BLOB], duplicate_count_by_type[OBJ_BLOB], delta_count_by_type[OBJ_BLOB]);\n-\t\tfprintf(stderr, \" trees : %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas)\\n\", object_count_by_type[OBJ_TREE], duplicate_count_by_type[OBJ_TREE], delta_count_by_type[OBJ_TREE]);\n-\t\tfprintf(stderr, \" commits: %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas)\\n\", object_count_by_type[OBJ_COMMIT], duplicate_count_by_type[OBJ_COMMIT], delta_count_by_type[OBJ_COMMIT]);\n-\t\tfprintf(stderr, \" tags : %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas)\\n\", object_count_by_type[OBJ_TAG], duplicate_count_by_type[OBJ_TAG], delta_count_by_type[OBJ_TAG]);\n+\t\tfprintf(stderr, \" blobs : %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas of %10\" PRIuMAX\" attempts)\\n\", object_count_by_type[OBJ_BLOB], duplicate_count_by_type[OBJ_BLOB], delta_count_by_type[OBJ_BLOB], delta_count_attempts_by_type[OBJ_BLOB]);\n+\t\tfprintf(stderr, \" trees : %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas of %10\" PRIuMAX\" attempts)\\n\", object_count_by_type[OBJ_TREE], duplicate_count_by_type[OBJ_TREE], delta_count_by_type[OBJ_TREE], delta_count_attempts_by_type[OBJ_TREE]);\n+\t\tfprintf(stderr, \" commits: %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas of %10\" PRIuMAX\" attempts)\\n\", object_count_by_type[OBJ_COMMIT], duplicate_count_by_type[OBJ_COMMIT], delta_count_by_type[OBJ_COMMIT], delta_count_attempts_by_type[OBJ_COMMIT]);\n+\t\tfprintf(stderr, \" tags : %10\" PRIuMAX \" (%10\" PRIuMAX \" duplicates %10\" PRIuMAX \" deltas of %10\" PRIuMAX\" attempts)\\n\", object_count_by_type[OBJ_TAG], duplicate_count_by_type[OBJ_TAG], delta_count_by_type[OBJ_TAG], delta_count_attempts_by_type[OBJ_TAG]);\n \t\tfprintf(stderr, \"Total branches: %10lu (%10lu loads )\\n\", branch_count, branch_load_count);\n \t\tfprintf(stderr, \" marks: %10\" PRIuMAX \" (%10\" PRIuMAX \" unique )\\n\", (((uintmax_t)1) << marks->shift) * 1024, marks_set_count);\n \t\tfprintf(stderr, \" atoms: %10u\\n\", atom_cnt);\n-- \n1.7.3.4\n"},{"id":"173931","messageId":"1313867052-11993-3-git-send-email-divanorama@gmail.com","threadId":"28176","inReplyTo":"1313867052-11993-1-git-send-email-divanorama@gmail.com","subject":"[PATCH 2/2] fast-import: treat cat-blob as a delta base hint for next blob","fromName":"Dmitry Ivankov","fromEmail":"divanorama@gmail.com","sentAt":"2011-08-20T19:04:12Z","receivedAt":"2011-08-20T19:04:12Z","isPatch":true,"sender":{"key":"divanorama@gmail.com","avatar":"https://avatars.githubusercontent.com/u/158999?v=4"},"body":"Delta base for blobs is chosen as a previously saved blob. If we\ntreat cat-blob's blob as a delta base for the next blob, nothing\nis likely to become worse.\n\nFor fast-import stream producer like svn-fe cat-blob is used like\nfollowing:\n- svn-fe reads file delta in svn format\n- to apply it, svn-fe asks cat-blob 'svn delta base'\n- applies 'svn delta' to the response\n- produces a blob command to store the result\n\nCurrently there is no way for svn-fe to give fast-import a hint on\nobject delta base. While what's requested in cat-blob is most of\nthe time a best delta base possible. Of course, it could be not a\ngood delta base, but we don't know any better one anyway.\n\nSo do treat cat-blob's result as a delta base for next blob. The\nprofit is nice: 2x to 7x reduction in pack size AND 1.2x to 3x\ntime speedup due to diff_delta being faster on good deltas. git gc\n--aggressive can compress it even more, by 10% to 70%, utilizing\nmore cpu time, real time and 3 cpu cores.\n\nTested on 213M and 2.7G fast-import streams, resulting packs are 22M\nand 113M, import time is 7s and 60s, both streams are produced by\nsvn-fe, sniffed and then used as raw input for fast-import.\n\nFor git-fast-export produced streams there is no change as it doesn't\nuse cat-blob and doesn't try to reorder blobs in some smart way to\nmake successive deltas small.\n\nSigned-off-by: Dmitry Ivankov \n---\n fast-import.c | 7 ++++++-\n 1 files changed, 6 insertions(+), 1 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 2b069e3..0480fbf 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2802,7 +2802,12 @@ static void cat_blob(struct object_entry *oe, unsigned char sha1[20])\n \tstrbuf_release(&line);\n \tcat_blob_write(buf, size);\n \tcat_blob_write(\"\\n\", 1);\n-\tfree(buf);\n+\tif (oe && oe->pack_id == pack_id) {\n+\t\tlast_blob.offset = oe->idx.offset;\n+\t\tstrbuf_attach(&last_blob.data, buf, size, size);\n+\t\tlast_blob.depth = oe->depth;\n+\t} else\n+\t\tfree(buf);\n }\n \n static void parse_cat_blob(void)\n-- \n1.7.3.4\n"},{"id":"173936","messageId":"20110820191754.GA22833@elie.gateway.2wire.net","threadId":"28176","inReplyTo":"1313867052-11993-3-git-send-email-divanorama@gmail.com","subject":"Re: [PATCH 2/2] fast-import: treat cat-blob as a delta base hint for next blob","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-08-20T19:17:55Z","receivedAt":"2011-08-20T19:17:55Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dmitry Ivankov wrote:\n\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -2802,7 +2802,12 @@ static void cat_blob(struct object_entry *oe, unsigned char sha1[20])\n> \tstrbuf_release(&line);\n> \tcat_blob_write(buf, size);\n> \tcat_blob_write(\"\\n\", 1);\n> -\tfree(buf);\n> +\tif (oe && oe->pack_id == pack_id) {\n> +\t\tstrbuf_attach(&last_blob.data, buf, size, size);\n> +\t\tlast_blob.offset = oe->idx.offset;\n> +\t\tlast_blob.depth = oe->depth;\n> +\t} else\n> +\t\tfree(buf);\n> }\n\nNeat. For what it's worth,\nAcked-by: Jonathan Nieder \n"},{"id":"173956","messageId":"CAFfmPPNOdCAZxtVHx3Px+ACad4fCdL2Op+3sezf14EMSBqwiJg@mail.gmail.com","threadId":"28176","inReplyTo":"20110820191754.GA22833@elie.gateway.2wire.net","subject":"Re: [PATCH 2/2] fast-import: treat cat-blob as a delta base hint for next blob","fromName":"David Michael Barr","fromEmail":"davidbarr@google.com","sentAt":"2011-08-21T11:01:09Z","receivedAt":"2011-08-21T11:01:09Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"On Sun, Aug 21, 2011 at 5:17 AM, Jonathan Nieder wrote:\n> Dmitry Ivankov wrote:\n>\n>> --- a/fast-import.c\n>> +++ b/fast-import.c\n>> @@ -2802,7 +2802,12 @@ static void cat_blob(struct object_entry *oe, unsigned char sha1[20])\n>>       strbuf_release(&line);\n>>       cat_blob_write(buf, size);\n>>       cat_blob_write(\"\\n\", 1);\n>> -     free(buf);\n>> +     if (oe && oe->pack_id == pack_id) {\n>> +             strbuf_attach(&last_blob.data, buf, size, size);\n>> +             last_blob.offset = oe->idx.offset;\n>> +             last_blob.depth = oe->depth;\n>> +     } else\n>> +             free(buf);\n>>  }\n>\n> Neat.  For what it's worth,\n> Acked-by: Jonathan Nieder \n>\n\nBrilliant!\n\nAcked-by: David Barr \n"}]}