{"thread":{"id":"10823","subject":"[BUG] fast-import producing very deep tree deltas","startedAt":"2007-11-12T11:03:56Z","lastAt":"2007-11-13T14:36:00Z","messageCount":6,"participants":["Brian Downing","Linus Torvalds","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"59464","messageId":"20071112110354.GP6212@lavos.net","threadId":"10823","inReplyTo":null,"subject":"[BUG] fast-import producing very deep tree deltas","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-11-12T11:03:56Z","receivedAt":"2007-11-12T11:03:56Z","isPatch":false,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"I've happened upon a case where fast-import produces deep tree deltas.\nHow deep? Really deep. 6035 entries deep to be precise for this case:\n\n depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48\n\n 27b8a20bdf39fecd917e8401d3499013e49449d0 tree 32 99609547 6035 0000000000000000000000000000000000000000\n\nThis was with git-fast-import from 'next' as of a couple days ago,\nrun with the default options (no --depth passed in).\n\nNeedless to say the pack that resulted was just about useless. Trying to\nrepack it resulted in the \"counting objects\" phase running at about five\nobjects per second.\n\nI don't know much about the fast-import code, but I'd guess that the\ndelta_depth member for the tree_content struct is either getting cleared\ninappropriately or is not being propagated correctly. I added a printout\nof the depth just before the store_object call in store_tree and it is\nnever non-zero, even though the pack file clearly was generated with\nplenty of deltas.\n\nI may have time to look at this more later this week, but I just wanted\nit to be known that this problem existed.\n\n-bcd\n"},{"id":"59465","messageId":"20071112111324.GR6212@lavos.net","threadId":"10823","inReplyTo":"20071112110354.GP6212@lavos.net","subject":"[BUG] fast-import quoting broken for renames","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-11-12T11:13:25Z","receivedAt":"2007-11-12T11:13:25Z","isPatch":false,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"While I'm at it...\n\n$ GIT_DIR=foo.git git init\n$ GIT_DIR=foo.git git fast-import < 0 +0000\ndata < 0 +0000\ndata < \n> depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48\n> \n> Needless to say the pack that resulted was just about useless. Trying to\n> repack it resulted in the \"counting objects\" phase running at about five\n> objects per second.\n\nHmm. Quick hack: increase the delta cache window. The reason (I think) why \nperformance turns glacial with really deep delta chains is that it turns \ninto an O(n^2) thing when you don't hit in the delta cache, and your delta \ndepth is so deep that following a *single* delta chain will flush the \ncache.\n\nSo I bet that making the delta cache bigger will \"fix\" it. You probably \ndon't have to make it 6000+ entries, but with the *median* being that \ndeep, making it 2k entries should improve it for most cases.\n\nObviously fastimport should be fixed to not do those insanely deep chains \ntoo, but it might be a good idea to at least make the delta cache a bit \nbigger by default, and perhaps have some config option for setting it.\n\n\t\tLinus\n"},{"id":"59635","messageId":"20071113085307.GC14735@spearce.org","threadId":"10823","inReplyTo":"20071112110354.GP6212@lavos.net","subject":"Re: [BUG] fast-import producing very deep tree deltas","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-13T08:53:07Z","receivedAt":"2007-11-13T08:53:07Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Brian Downing wrote:\n> I've happened upon a case where fast-import produces deep tree deltas.\n> How deep? Really deep. 6035 entries deep to be precise for this case:\n> \n> depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48\n> \n> 27b8a20bdf39fecd917e8401d3499013e49449d0 tree 32 99609547 6035 0000000000000000000000000000000000000000\n> \n> This was with git-fast-import from 'next' as of a couple days ago,\n> run with the default options (no --depth passed in).\n> \n> Needless to say the pack that resulted was just about useless. Trying to\n> repack it resulted in the \"counting objects\" phase running at about five\n> objects per second.\n\nHeh.\n\nI think what's happening here is your active branch cache isn't\nbig enough. We're swapping out the branch and thus recycling the\ntree information (struct tree_content) back into the free pool.\nWhen we later reload the tree we set the delta_depth to 0 but we\nkept the tree we just reloaded as a delta base.\n\nSo if the tree we reloaded was already at the maximum we wouldn't\nknow it and make the new tree a delta. Multiply the number of times\nthe branch cache has to swap out the tree times max_depth (10) and\nyou get the maximum delta depth of a tree created by fast-import.\nGiven your above data of 6035 I'm guessing your active branch cache\nhad to swap the branch out 603/604 times during this import.\n\nI think the fix is going to involve caching the depth within struct\nobject_entry so we can restore it when the tree is reloaded.\n\n-- \nShawn.\n"},{"id":"59637","messageId":"20071113092721.GD14735@spearce.org","threadId":"10823","inReplyTo":"20071113085307.GC14735@spearce.org","subject":"Re: [BUG] fast-import producing very deep tree deltas","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-13T09:27:21Z","receivedAt":"2007-11-13T09:27:21Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"Shawn O. Pearce\" wrote:\n> Brian Downing wrote:\n> > I've happened upon a case where fast-import produces deep tree deltas.\n> > How deep? Really deep. 6035 entries deep to be precise for this case:\n> > \n> > depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48\n> > \n> > 27b8a20bdf39fecd917e8401d3499013e49449d0 tree 32 99609547 6035 0000000000000000000000000000000000000000\n> > \n> > This was with git-fast-import from 'next' as of a couple days ago,\n> > run with the default options (no --depth passed in).\n> > \n> > Needless to say the pack that resulted was just about useless. Trying to\n> > repack it resulted in the \"counting objects\" phase running at about five\n> > objects per second.\n\nBrian, does this fix it?\n\n--8>--\nFrom ff39dd457564b9198344e0cc785afa8cac05b486 Mon Sep 17 00:00:00 2001\nFrom: Shawn O. Pearce \nDate: Tue, 13 Nov 2007 04:26:24 -0500\nSubject: [PATCH] Don't allow fast-import tree delta chains to exceed maximum depth\nTo: Junio C Hamano \nCc: git@vger.kernel.org\n\nBrian Downing noticed fast-import can produce tree depths of up\nto 6,035 objects and even deeper. Long delta chains can create\nvery small packfiles but cause problems during repacking as git\nneeds to unpack each tree to count the reachable blobs.\n\nWhat's happening here is the active branch cache isn't big enough.\nWe're swapping out the branch and thus recycling the tree information\n(struct tree_content) back into the free pool. When we later reload\nthe tree we set the delta_depth to 0 but we kept the tree we just\nreloaded as a delta base.\n\nSo if the tree we reloaded was already at the maximum depth we\nwouldn't know it and make the new tree a delta. Multiply the\nnumber of times the branch cache has to swap out the tree times\nmax_depth (10) and you get the maximum delta depth of a tree created\nby fast-import. In Brian's case above the active branch cache had\nto swap the branch out 603/604 times during this import to produce\na tree with a delta depth of 6035.\n\nSigned-off-by: Shawn O. Pearce \n---\n fast-import.c | 16 ++++++++++++----\n 1 files changed, 12 insertions(+), 4 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex f93d7d6..215f1e7 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -153,13 +153,16 @@ Format of STDIN stream:\n \n #define PACK_ID_BITS 16\n #define MAX_PACK_ID ((1<depth++;\n+\t\te->depth = last->depth;\n \n \t\thdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);\n \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n@@ -1097,6 +1101,7 @@ static int store_object(\n \t} else {\n \t\tif (last)\n \t\t\tlast->depth = 0;\n+\t\te->depth = 0;\n \t\thdrlen = encode_header(type, dat->len, hdr);\n \t\twrite_or_die(pack_data->pack_fd, hdr, hdrlen);\n \t\tpack_size += hdrlen;\n@@ -1160,7 +1165,7 @@ static void load_tree(struct tree_entry *root)\n \tif (myoe && myoe->pack_id != MAX_PACK_ID) {\n \t\tif (myoe->type != OBJ_TREE)\n \t\t\tdie(\"Not a tree: %s\", sha1_to_hex(sha1));\n-\t\tt->delta_depth = 0;\n+\t\tt->delta_depth = myoe->depth;\n \t\tbuf = gfi_unpack_entry(myoe, &size);\n \t} else {\n \t\tenum object_type type;\n@@ -2289,8 +2294,11 @@ int main(int argc, const char **argv)\n \t\t}\n \t\telse if (!prefixcmp(a, \"--max-pack-size=\"))\n \t\t\tmax_packsize = strtoumax(a + 16, NULL, 0) * 1024 * 1024;\n-\t\telse if (!prefixcmp(a, \"--depth=\"))\n+\t\telse if (!prefixcmp(a, \"--depth=\")) {\n \t\t\tmax_depth = strtoul(a + 8, NULL, 0);\n+\t\t\tif (max_depth > MAX_DEPTH)\n+\t\t\t\tdie(\"--depth cannot exceed %u\", MAX_DEPTH);\n+\t\t}\n \t\telse if (!prefixcmp(a, \"--active-branches=\"))\n \t\t\tmax_active_branches = strtoul(a + 18, NULL, 0);\n \t\telse if (!prefixcmp(a, \"--import-marks=\"))\n-- \n1.5.3.5.1661.gcbf0\n\n-- \nShawn.\n"},{"id":"59667","messageId":"20071113143559.GS6212@lavos.net","threadId":"10823","inReplyTo":"20071113092721.GD14735@spearce.org","subject":"Re: [BUG] fast-import producing very deep tree deltas","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-11-13T14:36:00Z","receivedAt":"2007-11-13T14:36:00Z","isPatch":false,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Tue, Nov 13, 2007 at 04:27:21AM -0500, Shawn O. Pearce wrote:\n> Brian, does this fix it?\n> \n> So if the tree we reloaded was already at the maximum depth we\n> wouldn't know it and make the new tree a delta. Multiply the\n> number of times the branch cache has to swap out the tree times\n> max_depth (10) and you get the maximum delta depth of a tree created\n> by fast-import. In Brian's case above the active branch cache had\n> to swap the branch out 603/604 times during this import to produce\n> a tree with a delta depth of 6035.\n> \n> Signed-off-by: Shawn O. Pearce \n\n/Much/ better:\n\ngit-fast-import statistics:\n---------------------------------------------------------------------\nAlloc'd objects: 140000\nTotal objects: 135970 ( 62664 duplicates )\n blobs : 42196 ( 13695 duplicates 19898 deltas)\n trees : 72143 ( 48969 duplicates 62402 deltas)\n commits: 21631 ( 0 duplicates 0 deltas)\n tags : 0 ( 0 duplicates 0 deltas)\nTotal branches: 10 ( 1 loads )\n marks: 1048576 ( 63827 unique )\n atoms: 18971\nMemory total: 8329 KiB\n pools: 2860 KiB\n objects: 5468 KiB\n---------------------------------------------------------------------\npack_report: getpagesize() = 4096\npack_report: core.packedGitWindowSize = 1073741824\npack_report: core.packedGitLimit = 8589934592\npack_report: pack_used_ctr = 273071\npack_report: pack_mmap_calls = 16855\npack_report: pack_open_windows = 50 / 363\npack_report: pack_mapped = 8529277175 / 8589933814\n---------------------------------------------------------------------\n\ndepths: count 135970 total 380519 min 0 max 10 mean 2.80 median 1 std_dev 3.22\n\nIn addition, fast-import ran much (probably 10x) faster and with much less\nmemory usage (last time it peaked around 1GB):\n\n PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND\n13098 bdowning 18 0 8223m 34m 6576 R 72 1.7 0:51.44 git-fast-import\n\nPresumably not having to rebuild the root tree object from a hundreds-deep\ndelta chain many hundreds of times sped things up a bit.\n\nAcked-by: Brian Downing \n\n-bcd\n"}]}