{"thread":{"id":"1814","subject":"Re-organize \"git-rev-list --objects\" logic","startedAt":"2005-09-15T22:14:29Z","lastAt":"2005-09-16T18:11:35Z","messageCount":3,"participants":["Linus Torvalds","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"8641","messageId":"Pine.LNX.4.58.0509151507380.26803@g5.osdl.org","threadId":"1814","inReplyTo":null,"subject":"Re-organize \"git-rev-list --objects\" logic","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-15T22:14:29Z","receivedAt":"2005-09-15T22:14:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThe logic to calculate the full object list used to be very inter-twined \nwith the logic that looked up the commits.\n\nFor no good reason - it's actually a lot simpler to just do that logic \nas a separate pass.\n\nThis improves performance a bit, and uses slightly less memory in my \ntests, but more importantly it makes the code simpler to work with and \nfollow what it does.\n\nThe performance win is less than I had hoped for, but I get:\n\nBefore:\n\n\t[torvalds@g5 linux]$ /usr/bin/time git-rev-list --objects v2.6.12..HEAD | wc -l\n\t13.64user 0.42system 0:14.13elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n\t0inputs+0outputs (0major+47947minor)pagefaults 0swaps\n\t58945\n\nAfter:\n\n\t[torvalds@g5 linux]$ /usr/bin/time git-rev-list --objects v2.6.12..HEAD | wc -l\n\t11.80user 0.36system 0:12.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n\t0inputs+0outputs (0major+42684minor)pagefaults 0swaps\n\t58945\n\nie it improved by 2 seconds, and took a 5000+ fewer pages (hey, that's \n20MB out of 174MB to go). And got the same number of objects (in theory, \nthe more expensive one might find some more shared objects to avoid. In \npractice it obviously doesn't).\n\nI know how to make it use _lots_ less memory, which will probably speed it \nup. But that's for another time, and I'd prefer to see this go in first.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n----\n\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -231,8 +231,6 @@ static void mark_parents_uninteresting(s\n {\n \tstruct commit_list *parents = commit->parents;\n \n-\tif (tree_objects)\n-\t\tmark_tree_uninteresting(commit->tree);\n \twhile (parents) {\n \t\tstruct commit *commit = parents->item;\n \t\tcommit->object.flags |= UNINTERESTING;\n@@ -272,29 +270,6 @@ static int everybody_uninteresting(struc\n \t\t\tcontinue;\n \t\treturn 0;\n \t}\n-\n-\t/*\n-\t * Ok, go back and mark all the edge trees uninteresting,\n-\t * since otherwise we can have situations where a parent\n-\t * that was marked uninteresting (and we never even had\n-\t * to look at) had lots of objects that we don't want to\n-\t * include.\n-\t *\n-\t * NOTE! This still doesn't mean that the object list is\n-\t * \"correct\", since we may end up listing objects that\n-\t * even older commits (that we don't list) do actually\n-\t * reference, but it gets us to a minimal list (or very\n-\t * close) in practice.\n-\t */\n-\tif (!tree_objects)\n-\t\treturn 1;\n-\n-\twhile (orig) {\n-\t\tstruct commit *commit = orig->item;\n-\t\tif (!parse_commit(commit) && commit->tree)\n-\t\t\tmark_tree_uninteresting(commit->tree);\n-\t\torig = orig->next;\n-\t}\n \treturn 1;\n }\n \n@@ -370,6 +345,19 @@ static struct commit_list *find_bisectio\n \treturn best;\n }\n \n+static void mark_edges_uninteresting(struct commit_list *list)\n+{\n+\tfor ( ; list; list = list->next) {\n+\t\tstruct commit_list *parents = list->item->parents;\n+\n+\t\tfor ( ; parents; parents = parents->next) {\n+\t\t\tstruct commit *commit = parents->item;\n+\t\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t}\n+\t}\n+}\n+\n static struct commit_list *limit_list(struct commit_list *list)\n {\n \tstruct commit_list *newlist = NULL;\n@@ -388,6 +376,8 @@ static struct commit_list *limit_list(st\n \t\t}\n \t\tp = &commit_list_insert(commit, p)->next;\n \t}\n+\tif (tree_objects)\n+\t\tmark_edges_uninteresting(newlist);\n \tif (bisect_list)\n \t\tnewlist = find_bisection(newlist);\n \treturn newlist;\n"},{"id":"8642","messageId":"Pine.LNX.4.63.0509160026010.20359@wgmdd8.biozentrum.uni-wuerzburg.de","threadId":"1814","inReplyTo":"Pine.LNX.4.58.0509151507380.26803@g5.osdl.org","subject":"Re: Re-organize \"git-rev-list --objects\" logic","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-09-15T22:27:30Z","receivedAt":"2005-09-15T22:27:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 15 Sep 2005, Linus Torvalds wrote:\n\n> I know how to make it use _lots_ less memory, which will probably speed it \n> up. But that's for another time, and I'd prefer to see this go in first.\n\nMind to elaborate just a bit?\n"},{"id":"8697","messageId":"Pine.LNX.4.58.0509161051350.26803@g5.osdl.org","threadId":"1814","inReplyTo":"Pine.LNX.4.63.0509160026010.20359@wgmdd8.biozentrum.uni-wuerzburg.de","subject":"Re: Re-organize \"git-rev-list --objects\" logic","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-16T18:11:35Z","receivedAt":"2005-09-16T18:11:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Sep 2005, Johannes Schindelin wrote:\n> \n> On Thu, 15 Sep 2005, Linus Torvalds wrote:\n> \n> > I know how to make it use _lots_ less memory, which will probably speed it \n> > up. But that's for another time, and I'd prefer to see this go in first.\n> \n> Mind to elaborate just a bit?\n\nRight now we keep track of every single object we parse, and never free \nit.\n\nSome of it is necessary to keep track of whether a SHA has been seen or\nnot, but: we also keep every single relation list around. They're small,\nbut they are _many_. We can trivially free those after following them.\nThat should get us back another few tens of megabytes easily. It's the\nparent pointers, and the \"struct tree_entry\" lists.\n\nNow, some memory usage is very fundamental, and we can't get rid of the\n\"struct object\" for each thing we've listed (or each thing we've\ndetermined needs to be pruned). We can perhaps shrink it some, but we'll\nalways need to have at a minimum the 20-byte sha1 of every object. So if\nwe list/blacklist a hundred thousand objects, there's no way we can avoid\nusing a couple of megs just to keep track of that fact in order to avoid\nduplicates.\n\nHowever, I _think_ the majority of the memory use is in the refs. Even a \nfull kernel tree only has about 95,000 objects, but we have many _many_ \nmore of these relationship links. We've got ~9,000 commits, and pretty \nmuch each of them will have a different root tree with 20+ entries in it, \nand even when most of them end up pointing to the same blobs/trees (which \nis why we only have 95,000 objects - there's _tons_ of sharing), they'll \nall end up generating a \"tree_entry\" thing. So just there, you'll have \nsomething like 180,000 small allocations.\n\nAnd yes, a \"tree_entry\" is smaller than a \"struct object\" or \"struct\ntree\", but with twice as many \"struct tree_entries\" as there are objects\nin _total_, that sure adds up pretty quickly.\n\nAnd the refs. git-fsck-cache needs to be able to look through the \ndependency chains for all objects. git-rev-list doesn't. Again, they're \nsmall, but they're all over.\n\nSo I suspect half the memory allocations is just for these things. Maybe \nI'm overly optimistic. But I think that even without shrinking the object \nstructures themselves, we should be able to make git-rev-list use a lot \nless memory.\n\n\t\t\tLinus\n"}]}