{"thread":{"id":"28709","subject":"[PATCH 1/4] pack-objects: mark add_to_write_order() as inline","startedAt":"2011-10-18T05:21:21Z","lastAt":"2011-11-14T05:40:37Z","messageCount":10,"participants":["Dan McGee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"177920","messageId":"1318915284-6361-1-git-send-email-dpmcgee@gmail.com","threadId":"28709","inReplyTo":null,"subject":"[PATCH 1/4] pack-objects: mark add_to_write_order() as inline","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-10-18T05:21:21Z","receivedAt":"2011-10-18T05:21:21Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"This function is a whole 26 bytes when compiled on x86_64, but is\ncurrently invoked over 1.037 billion times when running pack-objects on\nthe Linux kernel git repository. This is hitting the point where\nmicro-optimizations do make a difference, and inlining it only increases\nthe object file size by 38 bytes.\n\nAs reported by perf, this dropped task-clock from 84183 to 83373 ms, and\ntotal cycles from 223.5 billion to 221.6 billion. Not astronomical, but\nworth getting for adding one word.\n\nSigned-off-by: Dan McGee \n---\n builtin/pack-objects.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 2b18de5..0ab3a3b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -454,7 +454,7 @@ static int mark_tagged(const char *path, const unsigned char *sha1, int flag,\n \treturn 0;\n }\n \n-static void add_to_write_order(struct object_entry **wo,\n+static inline void add_to_write_order(struct object_entry **wo,\n \t\t\t int *endp,\n \t\t\t struct object_entry *e)\n {\n-- \n1.7.7\n"},{"id":"177921","messageId":"1318915284-6361-2-git-send-email-dpmcgee@gmail.com","threadId":"28709","inReplyTo":"1318915284-6361-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 2/4] pack-objects: use unsigned int for counter and offset values","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-10-18T05:21:22Z","receivedAt":"2011-10-18T05:21:22Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"This is done in some of the new pack layout code introduced in commit\n1b4bb16b9ec331c. This more closely matches the nr_objects global that is\nunsigned that these variables are based off of and bounded by.\n\nSigned-off-by: Dan McGee \n---\n builtin/pack-objects.c | 12 ++++++------\n 1 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0ab3a3b..0de10d2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -455,7 +455,7 @@ static int mark_tagged(const char *path, const unsigned char *sha1, int flag,\n }\n \n static inline void add_to_write_order(struct object_entry **wo,\n-\t\t\t int *endp,\n+\t\t\t unsigned int *endp,\n \t\t\t struct object_entry *e)\n {\n \tif (e->filled)\n@@ -465,7 +465,7 @@ static inline void add_to_write_order(struct object_entry **wo,\n }\n \n static void add_descendants_to_write_order(struct object_entry **wo,\n-\t\t\t\t\t int *endp,\n+\t\t\t\t\t unsigned int *endp,\n \t\t\t\t\t struct object_entry *e)\n {\n \tstruct object_entry *child;\n@@ -477,7 +477,7 @@ static void add_descendants_to_write_order(struct object_entry **wo,\n }\n \n static void add_family_to_write_order(struct object_entry **wo,\n-\t\t\t\t int *endp,\n+\t\t\t\t unsigned int *endp,\n \t\t\t\t struct object_entry *e)\n {\n \tstruct object_entry *root;\n@@ -490,7 +490,7 @@ static void add_family_to_write_order(struct object_entry **wo,\n \n static struct object_entry **compute_write_order(void)\n {\n-\tint i, wo_end;\n+\tunsigned int i, wo_end;\n \n \tstruct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));\n \n@@ -506,8 +506,8 @@ static struct object_entry **compute_write_order(void)\n \t * Make sure delta_sibling is sorted in the original\n \t * recency order.\n \t */\n-\tfor (i = nr_objects - 1; 0 <= i; i--) {\n-\t\tstruct object_entry *e = &objects[i];\n+\tfor (i = nr_objects; i > 0;) {\n+\t\tstruct object_entry *e = &objects[--i];\n \t\tif (!e->delta)\n \t\t\tcontinue;\n \t\t/* Mark me as the first child */\n-- \n1.7.7\n"},{"id":"177923","messageId":"1318915284-6361-3-git-send-email-dpmcgee@gmail.com","threadId":"28709","inReplyTo":"1318915284-6361-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 3/4] pack-objects: don't traverse objects unnecessarily","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-10-18T05:21:23Z","receivedAt":"2011-10-18T05:21:23Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"This brings back some of the performance lost in optimizing recency\norder inside pack objects. We were doing extreme amounts of object\nre-traversal: for the 2.14 million objects in the Linux kernel\nrepository, we were calling add_to_write_order() over 1.03 billion times\n(a 0.2% hit rate, making 99.8% of of these calls extraneous).\n\nTwo optimizations take place here- we can start our objects array\niteration from a known point where we left off before we started trying\nto find our tags, and we don't need to do the deep dives required by\nadd_family_to_write_order() if the object has already been marked as\nfilled.\n\nThese two optimizations bring some pretty spectacular results via `perf\nstat`:\n\ntask-clock: 83373 ms --> 43800 ms (50% faster)\ncycles: 221,633,461,676 --> 116,307,209,986 (47% fewer)\ninstructions: 149,299,179,939 --> 122,998,800,184 (18% fewer)\n\nSigned-off-by: Dan McGee \n---\n builtin/pack-objects.c | 18 ++++++++++++------\n 1 files changed, 12 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0de10d2..d9fb202 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -490,7 +490,7 @@ static void add_family_to_write_order(struct object_entry **wo,\n \n static struct object_entry **compute_write_order(void)\n {\n-\tunsigned int i, wo_end;\n+\tunsigned int i, wo_end, last_untagged;\n \n \tstruct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));\n \n@@ -521,7 +521,7 @@ static struct object_entry **compute_write_order(void)\n \tfor_each_tag_ref(mark_tagged, NULL);\n \n \t/*\n-\t * Give the commits in the original recency order until\n+\t * Give the objects in the original recency order until\n \t * we see a tagged tip.\n \t */\n \tfor (i = wo_end = 0; i < nr_objects; i++) {\n@@ -529,6 +529,7 @@ static struct object_entry **compute_write_order(void)\n \t\t\tbreak;\n \t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n \t}\n+\tlast_untagged = i;\n \n \t/*\n \t * Then fill all the tagged tips.\n@@ -541,7 +542,7 @@ static struct object_entry **compute_write_order(void)\n \t/*\n \t * And then all remaining commits and tags.\n \t */\n-\tfor (i = 0; i < nr_objects; i++) {\n+\tfor (i = last_untagged; i < nr_objects; i++) {\n \t\tif (objects[i].type != OBJ_COMMIT &&\n \t\t objects[i].type != OBJ_TAG)\n \t\t\tcontinue;\n@@ -551,7 +552,7 @@ static struct object_entry **compute_write_order(void)\n \t/*\n \t * And then all the trees.\n \t */\n-\tfor (i = 0; i < nr_objects; i++) {\n+\tfor (i = last_untagged; i < nr_objects; i++) {\n \t\tif (objects[i].type != OBJ_TREE)\n \t\t\tcontinue;\n \t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n@@ -560,8 +561,13 @@ static struct object_entry **compute_write_order(void)\n \t/*\n \t * Finally all the rest in really tight order\n \t */\n-\tfor (i = 0; i < nr_objects; i++)\n-\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n+\tfor (i = last_untagged; i < nr_objects; i++) {\n+\t\tif (!objects[i].filled)\n+\t\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n+\t}\n+\n+\tif(wo_end != nr_objects)\n+\t\tdie(\"ordered %u objects, expected %u\", wo_end, nr_objects);\n \n \treturn wo;\n }\n-- \n1.7.7\n"},{"id":"177922","messageId":"1318915284-6361-4-git-send-email-dpmcgee@gmail.com","threadId":"28709","inReplyTo":"1318915284-6361-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 4/4] pack-objects: rewrite add_descendants_to_write_order() iteratively","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-10-18T05:21:24Z","receivedAt":"2011-10-18T05:21:24Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"This removes the need to call this function recursively, shinking the\ncode size slightly and netting a small performance increase.\n\nSigned-off-by: Dan McGee \n---\n builtin/pack-objects.c | 44 +++++++++++++++++++++++++++++++++++++-------\n 1 files changed, 37 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex d9fb202..9efd1a7 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -468,12 +468,43 @@ static void add_descendants_to_write_order(struct object_entry **wo,\n \t\t\t\t\t unsigned int *endp,\n \t\t\t\t\t struct object_entry *e)\n {\n-\tstruct object_entry *child;\n-\n-\tfor (child = e->delta_child; child; child = child->delta_sibling)\n-\t\tadd_to_write_order(wo, endp, child);\n-\tfor (child = e->delta_child; child; child = child->delta_sibling)\n-\t\tadd_descendants_to_write_order(wo, endp, child);\n+\tint add_to_order = 1;\n+\twhile (e) {\n+\t\tif (add_to_order) {\n+\t\t\tstruct object_entry *s;\n+\t\t\t/* add this node... */\n+\t\t\tadd_to_write_order(wo, endp, e);\n+\t\t\t/* all its siblings... */\n+\t\t\tfor (s = e->delta_sibling; s; s = s->delta_sibling) {\n+\t\t\t\tadd_to_write_order(wo, endp, s);\n+\t\t\t}\n+\t\t}\n+\t\t/* drop down a level to add left subtree nodes if possible */\n+\t\tif (e->delta_child) {\n+\t\t\tadd_to_order = 1;\n+\t\t\te = e->delta_child;\n+\t\t} else {\n+\t\t\tadd_to_order = 0;\n+\t\t\t/* our sibling might have some children, it is next */\n+\t\t\tif (e->delta_sibling) {\n+\t\t\t\te = e->delta_sibling;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\t/* go back to our parent node */\n+\t\t\te = e->delta;\n+\t\t\twhile (e && !e->delta_sibling) {\n+\t\t\t\t/* we're on the right side of a subtree, keep\n+\t\t\t\t * going up until we can go right again */\n+\t\t\t\te = e->delta;\n+\t\t\t}\n+\t\t\tif (!e) {\n+\t\t\t\t/* done- we hit our original root node */\n+\t\t\t\treturn;\n+\t\t\t}\n+\t\t\t/* pass it off to sibling at this level */\n+\t\t\te = e->delta_sibling;\n+\t\t}\n+\t};\n }\n \n static void add_family_to_write_order(struct object_entry **wo,\n@@ -484,7 +515,6 @@ static void add_family_to_write_order(struct object_entry **wo,\n \n \tfor (root = e; root->delta; root = root->delta)\n \t\t; /* nothing */\n-\tadd_to_write_order(wo, endp, root);\n \tadd_descendants_to_write_order(wo, endp, root);\n }\n \n-- \n1.7.7\n"},{"id":"178381","messageId":"7vty6uxeua.fsf@alter.siamese.dyndns.org","threadId":"28709","inReplyTo":"1318915284-6361-4-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 4/4] pack-objects: rewrite add_descendants_to_write_order() iteratively","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-27T22:13:49Z","receivedAt":"2011-10-27T22:13:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n> This removes the need to call this function recursively, shinking the\n> code size slightly and netting a small performance increase.\n>\n> Signed-off-by: Dan McGee \n\nTricky.\n\nAs long as this is done after compute_write_order() populates\ndelta_sibling vs delta link in a consistent way, the new logic should\nproduce exactly the same result as the original code.\n\nThanks.\n"},{"id":"178383","messageId":"7vk47qxe9x.fsf@alter.siamese.dyndns.org","threadId":"28709","inReplyTo":"1318915284-6361-3-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 3/4] pack-objects: don't traverse objects unnecessarily","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-27T22:26:02Z","receivedAt":"2011-10-27T22:26:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n> Two optimizations take place here- we can start our objects array\n> iteration from a known point where we left off before we started trying\n> to find our tags,\n\nThis I would understand (but I am somewhat curious how much last_untagged\nwould advance relative to nr_objects for this half of the optimization to\nbe worth it), but...\n\n> and we don't need to do the deep dives required by\n> add_family_to_write_order() if the object has already been marked as\n> filled.\n\nI am not sure if this produces the identical result that was benchmarked\nin the original series.\n\nFor example, if you have a tagged object that is not a commit (say a\nblob), you would have written that blob in the second phase (write tagged\nobjects together), so the family of blobs that share same delta parent as\nthat blob will not be written in this \"Finally all the rest\" in the right\nplace in the original list, no?\n\nI do not think this change would forget to fill an object that needs to be\nfilled, but it would affect the resulting ordering of the list, so...\n\n> @@ -560,8 +561,13 @@ static struct object_entry **compute_write_order(void)\n> \t/*\n> \t * Finally all the rest in really tight order\n> \t */\n> -\tfor (i = 0; i < nr_objects; i++)\n> -\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n> +\tfor (i = last_untagged; i < nr_objects; i++) {\n> +\t\tif (!objects[i].filled)\n> +\t\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n> +\t}\n> +\n> +\tif(wo_end != nr_objects)\n> +\t\tdie(\"ordered %u objects, expected %u\", wo_end, nr_objects);\n"},{"id":"179196","messageId":"CAEik5nNmAnPni+rnLm7n5tO7f=LV_1TuTbVqxgjVaoqqaF_Ukw@mail.gmail.com","threadId":"28709","inReplyTo":"7vk47qxe9x.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] pack-objects: don't traverse objects unnecessarily","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-11-09T04:31:48Z","receivedAt":"2011-11-09T04:31:48Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Thu, Oct 27, 2011 at 5:26 PM, Junio C Hamano wrote:\n> Dan McGee writes:\n>\n>> Two optimizations take place here- we can start our objects array\n>> iteration from a known point where we left off before we started trying\n>> to find our tags,\n>\n> This I would understand (but I am somewhat curious how much last_untagged\n> would advance relative to nr_objects for this half of the optimization to\n> be worth it), but...\nFirst off, sorry I wasn't able to respond to you until now, I've been\na bit swamped with other projects. I saw this made it into the 1.7.7.3\nmaint release today, but wanted to at least try to respond to the\npoints you raised (if you didn't investigate them by yourself\nalready).\n\nIf I remember right, the last_untagged optimization was pretty minor-\naround 10% advancement of the pointer, never that much more. However,\nit was a very easy change to make so I figured it was worth the slight\nadditional code (~5 lines changed for that part on its own).\n\n>\n>> and we don't need to do the deep dives required by\n>> add_family_to_write_order() if the object has already been marked as\n>> filled.\n>\n> I am not sure if this produces the identical result that was benchmarked\n> in the original series.\nI was not either when I wrote the patch, and I had hoped to confirm\nthe results you showed in the message of 1b4bb16b9ec. However, I was\nunable to figure out how you generated those numbers so I wasn't able\nto do so (and had planned to get back to you to find out how you made\nthose tables). Were you able to verify the ordering did not regress?\n\n> For example, if you have a tagged object that is not a commit (say a\n> blob), you would have written that blob in the second phase (write tagged\n> objects together), so the family of blobs that share same delta parent as\n> that blob will not be written in this \"Finally all the rest\" in the right\n> place in the original list, no?\nTrue, I think. They would not be written in the same place, but is\nthat necessarily the right place? The delta parent of an\nalready-filled tag object would eventually come up in the array as not\nfilled, and then we would do a full deep dive at that point, so the\nmajority of the objects would still be in close proximity.\n\nNote that either way, we still have a gap between the original tagged\nobject and its \"family\"- potentially all the other tagged tips, tags,\ncommits, and trees before the blobs are finally hit and laid out in\nfamily groups. So there is at least one potentially big seek that\ncan't be avoided.\n\n> I do not think this change would forget to fill an object that needs to be\n> filled, but it would affect the resulting ordering of the list, so...\nThis was the purpose of the added \"if (wo_end != nr_objects) die()\"\nline; it confirms we have traversed and hit every object we originally\nfound.\n\n-Dan\n"},{"id":"179346","messageId":"7v1utdrfsf.fsf@alter.siamese.dyndns.org","threadId":"28709","inReplyTo":"CAEik5nNmAnPni+rnLm7n5tO7f=LV_1TuTbVqxgjVaoqqaF_Ukw@mail.gmail.com","subject":"Re: [PATCH 3/4] pack-objects: don't traverse objects unnecessarily","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-11-12T06:55:12Z","receivedAt":"2011-11-12T06:55:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n> On Thu, Oct 27, 2011 at 5:26 PM, Junio C Hamano wrote:\n>\n>> I am not sure if this produces the identical result that was benchmarked\n>> in the original series.\n> I was not either when I wrote the patch, and I had hoped to confirm\n> the results you showed in the message of 1b4bb16b9ec.\n\nI actually am reasonably sure the result will not be identical, but I also\ndo not think it matters. The differences would appear only for entries\nthat have been filled earlier, which should be a minority.\n\n> unable to figure out how you generated those numbers so I wasn't able\n> to do so (and had planned to get back to you to find out how you made\n> those tables). Were you able to verify the ordering did not regress?\n\nNo; I was hoping you would redo the benchmark using 5f44324 (core: log\noffset pack data accesses happened, 2011-07-06).\n"},{"id":"179397","messageId":"CAEik5nPJ3r6gp9Lttzh5aQmiPRFxpZvhTBXZoreY98QV6Cocdg@mail.gmail.com","threadId":"28709","inReplyTo":"7v1utdrfsf.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/4] pack-objects: don't traverse objects unnecessarily","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-11-13T22:34:04Z","receivedAt":"2011-11-13T22:34:04Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Sat, Nov 12, 2011 at 12:55 AM, Junio C Hamano wrote:\n> Dan McGee writes:\n>\n>> On Thu, Oct 27, 2011 at 5:26 PM, Junio C Hamano wrote:\n>>\n>>> I am not sure if this produces the identical result that was benchmarked\n>>> in the original series.\n>> I was not either when I wrote the patch, and I had hoped to confirm\n>> the results you showed in the message of 1b4bb16b9ec.\n>\n> I actually am reasonably sure the result will not be identical, but I also\n> do not think it matters. The differences would appear only for entries\n> that have been filled earlier, which should be a minority.\n>\n>> unable to figure out how you generated those numbers so I wasn't able\n>> to do so (and had planned to get back to you to find out how you made\n>> those tables). Were you able to verify the ordering did not regress?\n>\n> No; I was hoping you would redo the benchmark using 5f44324 (core: log\n> offset pack data accesses happened, 2011-07-06).\n\nI'm still not sure what you used to parse these results, so I had to\nspend a good amount of time writing up scripts to parse that output.\nAnyway, I ran tests that nearly correspond to the ones you quoted on\nfour different pack-object versions as noted below. The first is one\nrevision before your original changes, the next two are\nself-explanatory, and the final version is with the short diff\nincluded below.\n\nObservations:\n* Perhaps I did something wrong, but the v1.7.7.2 numbers don't seem\nto agree with the figures you came up with- not sure why that is,\nhowever, and I've already spent a lot of time on this today and don't\nreally have more time to sink into this.\n* The diff included below seems to make a significant difference in\nsome of the seek values.\n\ndmcgee@galway ~/logs-git\n$ ~/projects/git/parse_pack_access.py *git_log.txt\n 1b4bb16b9ec~1 v1.7.7.2 v1.7.7.3\nadd-whole-family\n 0.0: 32 32 32\n 32\n 10.0: 256 256 256\n 256\n 20.0: 293 293 293\n 293\n 30.0: 327 327 327\n 327\n 40.0: 366 366 366\n 366\n 50.0: 421 421 421\n 421\n 60.0: 526 526 526\n 526\n 70.0: 894 894 894\n 895\n 80.0: 11612 11625 11622\n 11625\n 90.0: 97405 97487 97487\n 97510\n 95.0: 280123 280391 280396\n 280391\n 99.0: 1251812 1254871 1252919\n 1253318\n 99.5: 1850181 1853291 1853100\n 1853106\n 99.9: 4008778 4013897 3988759\n 4013897\n accesses: 280450 280464 280457\n 280461\n <2MiB seek: 99.61 99.61 99.61\n 99.61\n\ndmcgee@galway ~/logs-git\n$ ~/projects/git/parse_pack_access.py *git_log_drivers_net.txt\n 1b4bb16b9ec~1 v1.7.7.2 v1.7.7.3\nadd-whole-family\n 0.0: 0 0 0\n 0\n 10.0: 144 46 46\n 46\n 20.0: 233 48 48\n 48\n 30.0: 317 98 97\n 97\n 40.0: 512 1396 1367\n 990\n 50.0: 2921 773060 786210\n 399996\n 60.0: 774452 11594348 10156053\n 4532415\n 70.0: 333258049 424530065 428113049\n 101687854\n 80.0: 411869214 438733385 438510929\n 106316734\n 90.0: 426972983 444510034 443993824\n 112362757\n 95.0: 432061866 447253337 446466814\n 116078451\n 99.0: 434915514 453076229 451430514\n 118597896\n 99.5: 435032830 454359692 452394830\n 119008652\n 99.9: 435123054 456005056 454017949\n 119605604\n accesses: 601405 600780 601732\n 601219\n <2MiB seek: 61.68 53.06 53.53\n 56.21\n\ndmcgee@galway ~/logs-git\n$ ~/projects/git/parse_pack_access.py *blame*.txt\n 1b4bb16b9ec~1 v1.7.7.2 v1.7.7.3\nadd-whole-family\n 0.0: 0 0 0\n 0\n 10.0: 137 46 46\n 46\n 20.0: 192 48 48\n 48\n 30.0: 309 97 97\n 97\n 40.0: 774 5246 5244\n 4034\n 50.0: 32585 2643798 2585078\n 1518706\n 60.0: 376168864 434624162 434479253\n 102257691\n 70.0: 415045893 438464313 438213313\n 104681256\n 80.0: 425668210 441472744 441222839\n 107541644\n 90.0: 430603653 445070643 444450126\n 112494824\n 95.0: 433514511 447215535 446450183\n 116456428\n 99.0: 435037297 453431874 451707047\n 118722564\n 99.5: 435065325 454459123 452652312\n 119165598\n 99.9: 435149193 456205377 454197863\n 119710538\n accesses: 199249 194708 194738\n 194875\n <2MiB seek: 54.31 49.25 49.43\n 50.94\n\ndmcgee@galway ~/logs-git\n$ ~/projects/git/parse_pack_access.py *index*.txt\n 1b4bb16b9ec~1 v1.7.7.2 v1.7.7.3\nadd-whole-family\n 0.0: 9 9 9\n 9\n 10.0: 137 45 45\n 45\n 20.0: 224 47 47\n 47\n 30.0: 315 71 71\n 71\n 40.0: 449 96 96\n 96\n 50.0: 808 164 165\n 165\n 60.0: 2693 289 290\n 287\n 70.0: 46913 456 458\n 448\n 80.0: 1456359 966 975\n 905\n 90.0: 12555961 3423 3486\n 2836\n 95.0: 44134452 10211 10616\n 7075\n 99.0: 269753078 304302120 314414250\n 35401\n 99.5: 353346206 386205936 388585783\n 59897\n 99.9: 408908212 414260557 415445310\n 244643\n accesses: 3050155 3045012 3045025\n 3045141\n <2MiB seek: 81.56 98.71 98.65\n 99.98\n\n\nThe scripts used, obviously some hardcoded magic here should be able\nto use them if you want:\n\n$ cat test_pack.sh\n#!/bin/bash -e\n\nversions=('1b4bb16b9ec~1' 'v1.7.7.2' 'v1.7.7.3' 'add-whole-family')\ncommands=('git log' 'git log drivers/net' 'git blame\ndrivers/net/netconsole.c' 'git index-pack -v\n.git/objects/pack/*.pack')\n\ngitdir=/home/dmcgee/projects/git\nlinuxdir=/home/dmcgee/projects/linux\n\nexport GIT_EXEC_DIR=$gitdir\n\nfor version in \"${versions[@]}\"; do\n\techo $version\n\tcd $gitdir\n\tgit checkout $version\n\tmake -j6 CFLAGS=\"-march=native -mtune=native -O2 -pipe -g\"\nPYTHON_PATH=/usr/bin/python2\n\tcd $linuxdir\n\tgit config core.logpackaccess \"/tmp/$version-repack.txt\"\n\t$gitdir/git repack -a -d\n\tfor command in \"${commands[@]}\"; do\n\t\tclean_cmd=${command//\\//_}\n\t\tclean_cmd=${clean_cmd// /_}\n\t\tgit config core.logpackaccess \"/tmp/$version-$clean_cmd.txt\"\n\t\techo $command\n\t\t$gitdir/$command >/dev/null\n\tdone\n\tgit config --unset core.logpackaccess\ndone\n\n\n$ cat parse_pack_access.py\n#!/usr/bin/python2\n\nfrom collections import defaultdict\nimport sys\n\ndef read_file(filename):\n packs = defaultdict(list)\n with open(filename, 'r') as data:\n for line in data.readlines():\n pack, position = line.strip().split(' ')\n packs[pack].append(int(position))\n return packs\n\ndef calculate_seeks(positions):\n seeks = []\n prev = positions[0]\n for position in positions[1:]:\n seeks.append(abs(position - prev))\n prev = position\n return sorted(seeks)\n\ndef bucket_seeks(seeks):\n percents = [0.0, 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 70.0, 80.0, 90.0,\n 95.0, 99.0, 99.5, 99.9]\n results = []\n for percent in percents:\n index = int(percent/100.0 * len(seeks))\n offset = seeks[index]\n results.append((percent, offset))\n\n return results\n\ndef print_result_line(label, results):\n print '%12s%s' % (label,\n ''.join('%18s' % result for result in results))\n\ndef main(filenames):\n known_versions = ['1b4bb16b9ec~1', 'v1.7.7.2', 'v1.7.7.3',\n'add-whole-family']\n pack_accesses = {}\n\n for filename in filenames:\n pack_accesses[filename] = read_file(filename)\n\n bucket_table = defaultdict(list)\n accesses = []\n under_twomb = []\n for version in known_versions:\n filename = [fn for fn in pack_accesses.keys() if\nfn.startswith(version)][0]\n access = pack_accesses[filename]\n\n for pack, positions in access.items():\n seeks = calculate_seeks(positions)\n results = bucket_seeks(seeks)\n for percent, offset in results:\n bucket_table[percent].append(offset)\n accesses.append(len(positions))\n under_twomb.append(sum(1 for s in seeks if s < 2 * 1024 *\n1024) * 100.0 / len(seeks))\n\n print_result_line('', known_versions)\n for k in sorted(bucket_table.keys()):\n print_result_line('%.1f:' % k, bucket_table[k])\n print_result_line('accesses:', accesses)\n print_result_line('<2MiB seek:', ('%.2f' % under for under in under_twomb))\n\nif __name__ == '__main__':\n main(sys.argv[1:])\n\n\n\n>From dfee7999b95442a5de2a7a0232c75262d13a28d6 Mon Sep 17 00:00:00 2001\nFrom: Dan McGee \nDate: Sun, 13 Nov 2011 15:07:13 -0600\nSubject: [PATCH] Add whole family when packing objects\n\nSigned-off-by: Dan McGee \n---\n builtin/pack-objects.c | 6 +++---\n 1 files changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 80ab6c3..0a9e761 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -566,7 +566,7 @@ static struct object_entry **compute_write_order(void)\n \t */\n \tfor (; i < nr_objects; i++) {\n \t\tif (objects[i].tagged)\n-\t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n \t}\n\n \t/*\n@@ -576,7 +576,7 @@ static struct object_entry **compute_write_order(void)\n \t\tif (objects[i].type != OBJ_COMMIT &&\n \t\t objects[i].type != OBJ_TAG)\n \t\t\tcontinue;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n \t}\n\n \t/*\n@@ -585,7 +585,7 @@ static struct object_entry **compute_write_order(void)\n \tfor (i = last_untagged; i < nr_objects; i++) {\n \t\tif (objects[i].type != OBJ_TREE)\n \t\t\tcontinue;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n \t}\n\n \t/*\n-- \n1.7.7.3\n"},{"id":"179408","messageId":"7vaa7zl0ru.fsf@alter.siamese.dyndns.org","threadId":"28709","inReplyTo":"CAEik5nPJ3r6gp9Lttzh5aQmiPRFxpZvhTBXZoreY98QV6Cocdg@mail.gmail.com","subject":"Re: [PATCH 3/4] pack-objects: don't traverse objects unnecessarily","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-11-14T05:40:37Z","receivedAt":"2011-11-14T05:40:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n>>> unable to figure out how you generated those numbers so I wasn't able\n>>> to do so (and had planned to get back to you to find out how you made\n>>> those tables). Were you able to verify the ordering did not regress?\n>>\n>> No; I was hoping you would redo the benchmark using 5f44324 (core: log\n>> offset pack data accesses happened, 2011-07-06).\n>\n> I'm still not sure what you used to parse these results,...\n\nAh, in the kernel repository, after running \"repack -a -d -f\" with\nversions of git and copying the resulting packfiles in PACK-OLD/ and\nPACK-NEW/, I used these scripts to examine the access pattern.\n\n-- >8 -- DOIT.sh -- >8 --\n#!/bin/sh\n\ntmp=/var/tmp/ll$\ntrap 'rm -f \"$tmp.*\"' 0\n\nln -f PACK-OLD/* .git/objects/pack/. || exit\nlog=\"$tmp.old\"\neval '/usr/bin/time rungit test -c core.logpackaccess=\"$log\" '\"$*\"\n\nln -f PACK-NEW/* .git/objects/pack/. || exit\nlog=\"$tmp.new\"\neval '/usr/bin/time rungit test -c core.logpackaccess=\"$log\" '\"$*\"\n\nperl OFS.perl \"$tmp.old\" \"$tmp.new\"\n-- 8< -- DOIT.sh -- 8< --\n\n-- >8 -- OFS.perl -- >8 --\n#!/usr/bin/perl\n\nuse strict;\nuse warnings;\nuse Getopt::Long;\n\nmy $verbose;\n\nexit(1) if (!GetOptions(\"verbose\" => \\$verbose));\n\nsub take_one {\n\tmy ($filename) = @_;\n\tmy (%lofs, $num);\n\tmy @diff;\n\topen my $in, '<', $filename;\n\n\t$num = 0;\n\twhile (<$in>) {\n\t\tmy ($file, $ofs) = split(' ');\n\t\tif (!exists $lofs{$file}) {\n\t\t\t$lofs{$file} = [$num++, 0];\n\t\t}\n\t\tmy $diff = $ofs - $lofs{$file}[1];\n\t\t$lofs{$file}[1] = $ofs;\n\t\tpush @diff, abs($diff);\n\t\tprint \"$lofs{$file}[0] $diff $ofs\\n\" if $verbose;\n\t}\n\treturn \\@diff;\n}\n\nsub bsearch {\n\tmy ($list, $target) = @_;\n\tmy ($hi, $lo) = ((scalar @$list), 0);\n\n\twhile ($lo < $hi) {\n\t\tmy $mi = int(($lo + $hi) / 2);\n\t\tif ($list->[$mi] == $target) {\n\t\t\treturn $mi;\n\t\t} elsif ($list->[$mi] < $target) {\n\t\t\t$lo = $mi + 1;\n\t\t} else {\n\t\t\t$hi = $mi;\n\t\t}\n\t}\n\treturn $hi;\n}\n\nmy @percentile = ();\nfor (my $i = 0; $i < 100; $i += 10) {\n\tpush @percentile, $i;\n}\npush @percentile, 95, 99, 99.9, 99.99;\n\nsub thcomma {\n\tmy ($intval) = @_;\n\tmy $result = \"\";\n\twhile ($intval > 1000) {\n\t\tmy $rem = $intval % 1000;\n\t\tif ($result ne \"\") {\n\t\t\t$result = sprintf \"%03d,%s\", $rem, $result;\n\t\t} else {\n\t\t\t$result = sprintf \"%03d\", $rem;\n\t\t}\n\t\t$intval -= $rem;\n\t\t$intval /= 1000;\n\t}\n\tif ($intval) {\n\t\tif ($result ne \"\") {\n\t\t\t$result = sprintf \"%d,%s\", $intval, $result;\n\t\t} else {\n\t\t\t$result = sprintf \"%d\", $intval;\n\t\t}\n\t}\n\t$result =~ s/^[0,]*//;\n\t$result = \"0\" if ($result eq \"\");\n\treturn $result;\n}\n\nsub show_stat {\n\tmy ($diff1, $diff2) = @_;\n\tmy ($i, $ix);\n\tif ($diff2) {\n\t\t@$diff2 = sort { $a <=> $b } @$diff2;\n\t}\n\t@$diff1 = sort { $a <=> $b } @$diff1;\n\tprintf \"\\nTotal number of access : %12s\", thcomma(scalar(@$diff1));\n\tprintf \"%12s\", thcomma(scalar(@$diff2)) if ($diff2);\n\tfor $i (@percentile) {\n\t\t$ix = scalar(@$diff1) * $i / 100;\n\t\tprintf \"\\n %5.2f%% percentile : %12s\", $i, thcomma($diff1->[$ix]);\n\t\tif ($diff2) {\n\t\t\t$ix = scalar(@$diff2) * $i / 100;\n\t\t\tprintf \"%12s\", thcomma($diff2->[$ix]);\n\t\t}\n\t}\n\n\t$ix = bsearch($diff1, 2 * 1024 * 1024);\n\tprintf \"\\n Less than 2MiB seek : %5.2f%%\", ($ix * 100.0 / @$diff1);\n\tif ($diff2) {\n\t\t$ix = bsearch($diff2, 2 * 1024 * 1024);\n\t\tprintf \" %5.2f%%\", ($ix * 100.0 / @$diff2);\n\t}\n\n\tprint \"\\n\";\n}\n\nmy ($diff1, $diff2);\n$diff1 = take_one($ARGV[0]);\n$diff2 = take_one($ARGV[1]) if ($ARGV[1]);\n\nshow_stat($diff1, $diff2);\n-- 8< -- OFS.perl -- 8< --\n\n\n\t\n"}]}