{"thread":{"id":"27776","subject":"[PATCH 0/2] For improved pack locality","startedAt":"2011-07-08T00:24:15Z","lastAt":"2011-10-28T09:17:44Z","messageCount":14,"participants":["Junio C Hamano","Shawn Pearce","Nicolas Pitre","Ævar Arnfjörð Bjarmason","Jakub Narebski"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"171004","messageId":"1310084657-16790-1-git-send-email-gitster@pobox.com","threadId":"27776","inReplyTo":null,"subject":"[PATCH 0/2] For improved pack locality","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-08T00:24:15Z","receivedAt":"2011-07-08T00:24:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn kept bugging me about the locality of data in the packfiles\ngenerated by C-git (see pack-heuristics.txt in Documentation/technical)\nis often horrible, so here is my stab at it. The idea is to make sure\nthat the majority of pack accesses fall to nearby locations in the\nmmapped packfile to reduce minor faults (which would help if you are\naccessing the packfile over slow link like NFS, or starting from a cold\ncache).\n\nJunio C Hamano (2):\n core: log offset pack data accesses happened\n pack-objects: optimize \"recency order\"\n\n builtin/pack-objects.c | 138 +++++++++++++++++++++++++++++++++++++++++++++++-\n cache.h | 3 +\n config.c | 3 +\n environment.c | 1 +\n sha1_file.c | 21 +++++++\n 5 files changed, 165 insertions(+), 1 deletions(-)\n\n-- \n1.7.6.134.gcf13f6\n"},{"id":"171005","messageId":"1310084657-16790-2-git-send-email-gitster@pobox.com","threadId":"27776","inReplyTo":"1310084657-16790-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/2] core: log offset pack data accesses happened","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-08T00:24:16Z","receivedAt":"2011-07-08T00:24:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In a workload other than \"git log\" (without pathspec nor any option that\ncauses us to inspect trees and blobs), the recency pack order is said to\ncause the access jump around quite a bit. Add a hook to allow us observe\nhow bad it is.\n\n\"git config core.logpackaccess /var/tmp/pal.txt\" will give you the log in\nthe specified file, one line per access, the name of the packfile and the\noffset of the accessed location in the packfile. This data can be massaged\nto show how large a seek is involved in between each pair of adjacent\naccesses to the same packfile.\n\nSigned-off-by: Junio C Hamano \n---\n cache.h | 3 +++\n config.c | 3 +++\n environment.c | 1 +\n sha1_file.c | 21 +++++++++++++++++++++\n 4 files changed, 28 insertions(+), 0 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex f4bb43e..16a8c7c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -784,6 +784,9 @@ extern int force_object_loose(const unsigned char *sha1, time_t mtime);\n /* global flag to enable extra checks when accessing packed objects */\n extern int do_check_packed_object_crc;\n \n+/* for development: log offset of pack access */\n+extern const char *log_pack_access;\n+\n extern int check_sha1_signature(const unsigned char *sha1, void *buf, unsigned long size, const char *type);\n \n extern int move_temp_to_file(const char *tmpfile, const char *filename);\ndiff --git a/config.c b/config.c\nindex e0b3b80..5ef3f39 100644\n--- a/config.c\n+++ b/config.c\n@@ -569,6 +569,9 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.logpackaccess\"))\n+\t\treturn git_config_string(&log_pack_access, var, value);\n+\n \tif (!strcmp(var, \"core.autocrlf\")) {\n \t\tif (value && !strcasecmp(value, \"input\")) {\n \t\t\tif (core_eol == EOL_CRLF)\ndiff --git a/environment.c b/environment.c\nindex 94d58fd..1935102 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -36,6 +36,7 @@ size_t packed_git_window_size = DEFAULT_PACKED_GIT_WINDOW_SIZE;\n size_t packed_git_limit = DEFAULT_PACKED_GIT_LIMIT;\n size_t delta_base_cache_limit = 16 * 1024 * 1024;\n unsigned long big_file_threshold = 512 * 1024 * 1024;\n+const char *log_pack_access;\n const char *pager_program;\n int pager_use_color = 1;\n const char *editor_program;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 064a330..baf5da1 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1839,6 +1839,24 @@ static void *unpack_delta_entry(struct packed_git *p,\n \treturn result;\n }\n \n+static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n+{\n+\tstatic FILE *log_file;\n+\n+\tif (!log_file) {\n+\t\tlog_file = fopen(log_pack_access, \"w\");\n+\t\tif (!log_file) {\n+\t\t\terror(\"cannot open pack access log '%s' for writing: %s\",\n+\t\t\t log_pack_access, strerror(errno));\n+\t\t\tlog_pack_access = NULL;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\tfprintf(log_file, \"%s %\"PRIuMAX\"\\n\",\n+\t\tp->pack_name, (uintmax_t)obj_offset);\n+\tfflush(log_file);\n+}\n+\n int do_check_packed_object_crc;\n \n void *unpack_entry(struct packed_git *p, off_t obj_offset,\n@@ -1848,6 +1866,9 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \toff_t curpos = obj_offset;\n \tvoid *data;\n \n+\tif (log_pack_access)\n+\t\twrite_pack_access_log(p, obj_offset);\n+\n \tif (do_check_packed_object_crc && p->index_version > 1) {\n \t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n \t\tunsigned long len = revidx[1].offset - obj_offset;\n-- \n1.7.6.134.gcf13f6\n"},{"id":"171006","messageId":"1310084657-16790-3-git-send-email-gitster@pobox.com","threadId":"27776","inReplyTo":"1310084657-16790-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-08T00:24:17Z","receivedAt":"2011-07-08T00:24:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This optimizes the \"recency order\" (see pack-heuristics.txt in\nDocumentation/technical/ directory) used to order objects within a\npackfile in three ways:\n\n - Commits at the tip of tags are written together, in the hope that\n revision traversal done in incremental fetch (which starts by\n putting them in a revision queue marked as UNINTERESTING) will see a\n better locality of these objects;\n\n - In the original recency order, trees and blobs are intermixed. Write\n trees together before blobs, in the hope that this will improve\n locality when running pathspec-limited revision traversal, i.e.\n \"git log paths...\";\n\n - When writing blob objects out, write the whole family of blobs that use\n the same delta base object together, by starting from the root of the\n delta chain, and writing its immediate children in a width-first\n manner, in the hope that this will again improve locality when reading\n blobs that belong to the same path, which are likely to be deltified\n against each other.\n\nI tried various workloads in the Linux kernel repositories (HEAD at\nv3.0-rc6-71-g4dd1b49) packed with v1.7.6 and with this patch, counting how\nlarge seeks are needed between adjacent accesses to objects in the pack,\nand the result looks promising. The history has 2072052 objects, weighing\nsome 490MiB.\n\n * Simple commit-only log.\n\n $ git log >/dev/null\n\n There are 254656 commits in total.\n\n v1.7.6 with patch\n Total number of access : 258,031 258,032\n\t 0.0% percentile : 12 12\n\t 10.0% percentile : 259 259\n\t 20.0% percentile : 294 294\n\t 30.0% percentile : 326 326\n\t 40.0% percentile : 363 363\n\t 50.0% percentile : 415 415\n\t 60.0% percentile : 513 513\n\t 70.0% percentile : 857 858\n\t 80.0% percentile : 10,434 10,441\n\t 90.0% percentile : 91,985 91,996\n\t 95.0% percentile : 260,852 260,885\n\t 99.0% percentile : 1,150,680 1,152,811\n\t 99.9% percentile : 3,148,435 3,148,435\n Less than 2MiB seek: 99.70% 99.69%\n\n 95% of the pack accesses look at data that is no further than 260kB\n from the previous location we accessed. The patch does not change the\n order of commit objects very much, and the result is very similar.\n\n * Pathspec-limited log.\n\n $ git log drivers/net >/dev/null\n\n The path is touched by 26551 commits and merges (among 254656 total).\n\n v1.7.6 with patch\n Total number of access : 559,511 558,663\n\t 0.0% percentile : 0 0\n\t 10.0% percentile : 182 167\n\t 20.0% percentile : 259 233\n\t 30.0% percentile : 357 304\n\t 40.0% percentile : 714 485\n\t 50.0% percentile : 5,046 3,976\n\t 60.0% percentile : 688,671 443,578\n\t 70.0% percentile : 319,574,732 110,370,100\n\t 80.0% percentile : 361,647,599 123,707,229\n\t 90.0% percentile : 393,195,669 128,947,636\n\t 95.0% percentile : 405,496,875 131,609,321\n\t 99.0% percentile : 412,942,470 133,078,115\n\t 99.5% percentile : 413,172,266 133,163,349\n\t 99.9% percentile : 413,354,356 133,240,445\n Less than 2MiB seek: 61.71% 62.87%\n\n With the current pack heuristics, more than 30% of accesses have to\n seek further than 300MB; the updated pack heuristics ensures that less\n than 0.1% of accesses have to seek further than 135MB. This is largely\n due to the fact that the updated heuristics does not mix blobs and\n trees together.\n\n * Blame.\n\n $ git blame drivers/net/ne.c >/dev/null\n\n The path is touched by 34 commits and merges.\n\n v1.7.6 with patch\n Total number of access : 178,147 178,166\n\t 0.0% percentile : 0 0\n\t 10.0% percentile : 142 139\n\t 20.0% percentile : 222 194\n\t 30.0% percentile : 373 300\n\t 40.0% percentile : 1,168 837\n\t 50.0% percentile : 11,248 7,334\n\t 60.0% percentile : 305,121,284 106,850,130\n\t 70.0% percentile : 361,427,854 123,709,715\n\t 80.0% percentile : 388,127,343 128,171,047\n\t 90.0% percentile : 399,987,762 130,200,707\n\t 95.0% percentile : 408,230,673 132,174,308\n\t 99.0% percentile : 412,947,017 133,181,160\n\t 99.5% percentile : 413,312,798 133,220,425\n\t 99.9% percentile : 413,352,366 133,269,051\n Less than 2MiB seek: 56.47% 56.83%\n\n The result is very similar to the pathspec-limited log above, which\n only looks at the tree objects.\n\n * Packing recent history.\n\n $ (git for-each-ref --format='^%(refname)' refs/tags; echo HEAD) |\n git pack-objects --revs --stdout >/dev/null\n\n This should pack data worth 71 commits.\n\n v1.7.6 with patch\n Total number of access : 11,511 11,514\n\t 0.0% percentile : 0 0\n\t 10.0% percentile : 48 47\n\t 20.0% percentile : 134 98\n\t 30.0% percentile : 332 178\n\t 40.0% percentile : 1,386 293\n\t 50.0% percentile : 8,030 478\n\t 60.0% percentile : 33,676 1,195\n\t 70.0% percentile : 147,268 26,216\n\t 80.0% percentile : 9,178,662 464,598\n\t 90.0% percentile : 67,922,665 965,782\n\t 95.0% percentile : 87,773,251 1,226,102\n\t 99.0% percentile : 98,011,763 1,932,377\n\t 99.5% percentile : 100,074,427 33,642,128\n\t 99.9% percentile : 105,336,398 275,772,650\n Less than 2MiB seek: 77.09% 99.04%\n\n The long-tail part of the result looks worse with the patch, but\n the change helps majority of the access. 99.04% of the accesses\n need less than 2MiB of seeking, compared to 77.09% with the current\n packing heuristics.\n\n * Index pack.\n\n $ git index-pack -v .git/objects/pack/pack*.pack\n\n v1.7.6 with patch\n Total number of access : 2,791,228 2,788,802\n\t 0.0% percentile : 9 9\n\t 10.0% percentile : 140 89\n\t 20.0% percentile : 233 167\n\t 30.0% percentile : 322 235\n\t 40.0% percentile : 464 310\n\t 50.0% percentile : 862 423\n\t 60.0% percentile : 2,566 686\n\t 70.0% percentile : 25,827 1,498\n\t 80.0% percentile : 1,317,862 4,971\n\t 90.0% percentile : 11,926,385 119,398\n\t 95.0% percentile : 41,304,149 952,519\n\t 99.0% percentile : 227,613,070 6,709,650\n\t 99.5% percentile : 321,265,121 11,734,871\n\t 99.9% percentile : 382,919,785 33,155,191\n Less than 2MiB seek: 81.73% 96.92%\n\n As the index-pack command already walks objects in the delta chain\n order, writing the blobs out in the delta chain order seems to\n drastically improve the locality of access.\n\nNote that a half-a-gigabyte packfile comfortably fits in the buffer cache,\nand you would unlikely to see much performance difference on a modern and\nreasonably beefy machine with enough memory and local disks. Benchmarking\nwith cold cache (or over NFS) would be interesting.\n\nSigned-off-by: Junio C Hamano \n---\n builtin/pack-objects.c | 138 +++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 137 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f402a84..27132bb 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -51,6 +51,8 @@ struct object_entry {\n \t\t\t\t * objects against.\n \t\t\t\t */\n \tunsigned char no_try_delta;\n+\tunsigned char tagged; /* near the very tip of refs */\n+\tunsigned char filled; /* assigned write-order */\n };\n \n /*\n@@ -95,6 +97,7 @@ static unsigned long window_memory_limit = 0;\n */\n static int *object_ix;\n static int object_ix_hashsz;\n+static struct object_entry *locate_object_entry(const unsigned char *sha1);\n \n /*\n * stats\n@@ -199,6 +202,7 @@ static void copy_pack_data(struct sha1file *f,\n \t}\n }\n \n+/* Return 0 if we will bust the pack-size limit */\n static unsigned long write_object(struct sha1file *f,\n \t\t\t\t struct object_entry *entry,\n \t\t\t\t off_t write_offset)\n@@ -433,6 +437,134 @@ static int write_one(struct sha1file *f,\n \treturn 1;\n }\n \n+static int mark_tagged(const char *path, const unsigned char *sha1, int flag,\n+\t\t void *cb_data)\n+{\n+\tunsigned char peeled[20];\n+\tstruct object_entry *entry = locate_object_entry(sha1);\n+\n+\tif (entry)\n+\t\tentry->tagged = 1;\n+\tif (!peel_ref(path, peeled)) {\n+\t\tentry = locate_object_entry(peeled);\n+\t\tif (entry)\n+\t\t\tentry->tagged = 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static 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+\tif (e->filled)\n+\t\treturn;\n+\two[(*endp)++] = e;\n+\te->filled = 1;\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 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+}\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 struct object_entry *e)\n+{\n+\tstruct object_entry *root;\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+static struct object_entry **compute_write_order(void)\n+{\n+\tint i, wo_end;\n+\n+\tstruct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));\n+\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tobjects[i].tagged = 0;\n+\t\tobjects[i].filled = 0;\n+\t\tobjects[i].delta_child = NULL;\n+\t\tobjects[i].delta_sibling = NULL;\n+\t}\n+\n+\t/*\n+\t * Fully connect delta_child/delta_sibling network.\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+\t\tif (!e->delta)\n+\t\t\tcontinue;\n+\t\t/* Mark me as the first child */\n+\t\te->delta_sibling = e->delta->delta_child;\n+\t\te->delta->delta_child = e;\n+\t}\n+\n+\t/*\n+\t * Mark objects that are at the tip of tags.\n+\t */\n+\tfor_each_tag_ref(mark_tagged, NULL);\n+\n+\t/*\n+\t * Give the commits 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+\t\tif (objects[i].tagged)\n+\t\t\tbreak;\n+\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t}\n+\n+\t/*\n+\t * Then fill all the tagged tips.\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}\n+\n+\t/*\n+\t * And then all remaining commits and tags.\n+\t */\n+\tfor (i = 0; 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+\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t}\n+\n+\t/*\n+\t * And then all the trees.\n+\t */\n+\tfor (i = 0; 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}\n+\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+\n+\treturn wo;\n+}\n+\n static void write_pack_file(void)\n {\n \tuint32_t i = 0, j;\n@@ -441,10 +573,12 @@ static void write_pack_file(void)\n \tstruct pack_header hdr;\n \tuint32_t nr_remaining = nr_result;\n \ttime_t last_mtime = 0;\n+\tstruct object_entry **write_order;\n \n \tif (progress > pack_to_stdout)\n \t\tprogress_state = start_progress(\"Writing objects\", nr_result);\n \twritten_list = xmalloc(nr_objects * sizeof(*written_list));\n+\twrite_order = compute_write_order();\n \n \tdo {\n \t\tunsigned char sha1[20];\n@@ -468,7 +602,8 @@ static void write_pack_file(void)\n \t\toffset = sizeof(hdr);\n \t\tnr_written = 0;\n \t\tfor (; i < nr_objects; i++) {\n-\t\t\tif (!write_one(f, objects + i, &offset))\n+\t\t\tstruct object_entry *e = write_order[i];\n+\t\t\tif (!write_one(f, e, &offset))\n \t\t\t\tbreak;\n \t\t\tdisplay_progress(progress_state, written);\n \t\t}\n@@ -545,6 +680,7 @@ static void write_pack_file(void)\n \t} while (nr_remaining && i < nr_objects);\n \n \tfree(written_list);\n+\tfree(write_order);\n \tstop_progress(&progress_state);\n \tif (written != nr_result)\n \t\tdie(\"wrote %\"PRIu32\" objects while expecting %\"PRIu32,\n-- \n1.7.6.134.gcf13f6\n"},{"id":"171010","messageId":"CAJo=hJtEnGGH8yjTGHiVjjaiRd6TVznW+5DwpibNSN6JEY=Trw@mail.gmail.com","threadId":"27776","inReplyTo":"1310084657-16790-3-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-07-08T02:08:11Z","receivedAt":"2011-07-08T02:08:11Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Jul 7, 2011 at 17:24, Junio C Hamano wrote:\n> This optimizes the \"recency order\" (see pack-heuristics.txt in\n> Documentation/technical/ directory) used to order objects within a\n> packfile in three ways:\n\nYay!\n\n>  - Commits at the tip of tags are written together, in the hope that\n>   revision traversal done in incremental fetch (which starts by\n>   putting them in a revision queue marked as UNINTERESTING) will see a\n>   better locality of these objects;\n\nPutting these together after the first tagged commit is an interesting\napproach. Currently JGit drops these after 1024 recent commits have\nbeen produced, the alternative here parks them around the most recent\nrelease. I wonder which is really the better approach for the\nupload-pack workload. I chose 1024 because linux-2.6 seemed to be\ngetting several thousand commits per MB of pack data, so 1024 would\npark the tagged commits within the first MB (making a cold-cache\nupload-pack slightly faster), but doesn't harm `git log` going through\nthe pager too badly because this block is 1024 commits back.\n\nHave you tried putting commits in parse order rather than recency order?\n\nBy this I mean the revision traversal code needs to parse the parents\nof a commit in order to get their commit date and enqueue them into\nthe priority queue at the right position. The order the commits get\nparsed in is different from the order they are popped in, especially\nwhen a commit is created on an older revision and there is much\nconcurrent activity on a different branch between the commit and its\nancestor. This pattern is very typical in repositories that pull from\nothers to merge changes in... aka linux, git.git, etc.\n\nMy intuition says emulating the priority queue in pack-objects and\nusing that to influence the order commits are written out (so its the\norder commits enter the queue, rather than leave it) will further\nreduce minor page faults during the `git log >/dev/null` test, and\npossibly also help the other log based workloads. Its certainly a lot\nmore work to code than this patch, but I wonder if it produces better\nordering.\n\n>  - In the original recency order, trees and blobs are intermixed. Write\n>   trees together before blobs, in the hope that this will improve\n>   locality when running pathspec-limited revision traversal, i.e.\n>   \"git log paths...\";\n\nFWIW JGit has been doing \"commits-then-trees-then-blobs\" for a long\ntime now and we have generally found the same results as you did here,\nsegregating by object type helps page faults.\n\n>  - When writing blob objects out, write the whole family of blobs that use\n>   the same delta base object together, by starting from the root of the\n>   delta chain, and writing its immediate children in a width-first\n>   manner, in the hope that this will again improve locality when reading\n>   blobs that belong to the same path, which are likely to be deltified\n>   against each other.\n\nThis is an interesting approach, and one I had not considered before.\n\n>  * Simple commit-only log.\n>\n>   $ git log >/dev/null\n...\n>   95% of the pack accesses look at data that is no further than 260kB\n>   from the previous location we accessed. The patch does not change the\n>   order of commit objects very much, and the result is very similar.\n\nI think a more interesting thing to examine is how often do we have to\n\"skip back\" to an earlier part of the file. Consider the case that the\n~190MBish of commits does not fully fit into kernel buffer cache, but\nwe do have read-ahead support in the kernel. Forward references are\nrelatively free, because read-ahead should populate that page before\nwe need it. Backward references are horribly expensive, because they\nmay have been evicted to make room for more read-ahead. From what I\ncould tell of similar traces in JGit, the recency commit ordering\ncauses a lot more backwards references than the parse ordering.\n\n>  * Pathspec-limited log.\n>\n>   $ git log drivers/net >/dev/null\n>\n>   The path is touched by 26551 commits and merges (among 254656 total).\n>\n>                                  v1.7.6  with patch\n>   Total number of access :      559,511     558,663\n...\n>         70.0% percentile :  319,574,732 110,370,100\n>         80.0% percentile :  361,647,599 123,707,229\n>         90.0% percentile :  393,195,669 128,947,636\n>         95.0% percentile :  405,496,875 131,609,321\n...\n\nDoes this result suggest that we needed less of the pack in-memory in\norder to produce the result? That is, on a cold cache we should be\ntouching fewer pages of the pack when this patch was used to create\nit, and fewer page references would allow the command to complete more\nquickly on a cold cache.\n\n> Note that a half-a-gigabyte packfile comfortably fits in the buffer cache,\n> and you would unlikely to see much performance difference on a modern and\n> reasonably beefy machine with enough memory and local disks. Benchmarking\n> with cold cache (or over NFS) would be interesting.\n\nIt would also be easy to test these cases by setting the pack window\nsize to something small (e.g. 1 MB) and the pack limit to something\nequally small (e.g. 25 MB), and stuffing a delay of 20 ms into the\ncode path that xmmaps a new window when its not already opened.\n\nI'm glad you started working on this, it looks like it may lead to a\nbetter pack ordering.\n\n-- \nShawn.\n"},{"id":"171016","messageId":"7voc14fyy8.fsf@alter.siamese.dyndns.org","threadId":"27776","inReplyTo":"1310084657-16790-3-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-08T17:45:51Z","receivedAt":"2011-07-08T17:45:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I wrote:\n\n> - In the original recency order, trees and blobs are intermixed. Write\n> trees together before blobs, in the hope that this will improve\n> locality when running pathspec-limited revision traversal, i.e.\n> \"git log paths...\";\n>\n> - When writing blob objects out, write the whole family of blobs that use\n> the same delta base object together, by starting from the root of the\n> delta chain, and writing its immediate children in a width-first\n> manner, in the hope that this will again improve locality when reading\n> blobs that belong to the same path, which are likely to be deltified\n> against each other.\n\nAn interesting tangent.\n\nWith a single-liner change to apply the same \"write the entire family as a\ngroup\" logic also to tree objects, we get a superb improvement to the\n\"index-pack\" workload, while \"log pathspec\" becomes measurably worse.\n\n> * Pathspec-limited log.\n> $ git log drivers/net >/dev/null\n> v1.7.6 with patch\n> \t 60.0% percentile : 688,671 443,578\n> \t 70.0% percentile : 319,574,732 110,370,100\n> \t 99.0% percentile : 412,942,470 133,078,115\n> \t 99.5% percentile : 413,172,266 133,163,349\n> \t 99.9% percentile : 413,354,356 133,240,445\n> Less than 2MiB seek: 61.71% 62.87%\n\n 60.00% percentile : 2,240,841\n 70.00% percentile : 115,729,538\n 99.00% percentile : 132,912,877\n 99.90% percentile : 133,129,574\n Less than 2MiB seek : 59.77%\n\nThis of course is because trees tend to delta well against each other and\nwriting out everything in the same family tends to coalesce ancient and\nrecent trees close together, while the history traversal wants to see the\ntrees at the same path in adjacent commits, and the process to jump over\nto the \"next tree\" in the same commit need to seek a lot more.\n\n> * Blame.\n> $ git blame drivers/net/ne.c >/dev/null\n> v1.7.6 with patch\n> \t 50.0% percentile : 11,248 7,334\n> \t 95.0% percentile : 408,230,673 132,174,308\n> Less than 2MiB seek: 56.47% 56.83%\n\n 50.00% percentile : 79,182\n 95.00% percentile : 132,547,959\n Less than 2MiB seek : 56.16%\n\nThis also is harmed by trees in adjacent commits being further apart, but\nblame needs to read a lot of blobs as well, so the effect is not as grave\nas tree-only \"log pathspec\" case. \n\n> * Index pack.\n> $ git index-pack -v .git/objects/pack/pack*.pack\n> v1.7.6 with patch\n> \t 80.0% percentile : 1,317,862 4,971\n> \t 90.0% percentile : 11,926,385 119,398\n> \t 99.9% percentile : 382,919,785 33,155,191\n> Less than 2MiB seek: 81.73% 96.92%\n\n 80.00% percentile : 745\n 90.00% percentile : 1,891\n 99.90% percentile : 80,001\n Less than 2MiB seek : 100.00%\n\nIt is so obvious that the in pack object ordering with \"the whole family\nat once\" tweak is extremely tuned for this workload that the result is not\neven funny.\n\nThe moral of the story is that index-pack is not a workload to optimize\nfor ;-) and the following is a wrong patch to apply. In general, we have\nto be extremely careful not to tune for a particular workload while\nunknowingly sacrificing other workloads.\n\nI wonder if we would get a better locality for \"blame\" by not writing the\nwhole family at once for blobs, but only a smaller subset.\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 27132bb..adcb509 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -553,7 +553,7 @@ static struct object_entry **compute_write_order(void)\n \tfor (i = 0; 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"},{"id":"171020","messageId":"7vfwmgfkzo.fsf@alter.siamese.dyndns.org","threadId":"27776","inReplyTo":"1310084657-16790-3-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-08T22:47:23Z","receivedAt":"2011-07-08T22:47:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This updates the codepath to write commit objects so that when a commit is\nemitted, its parents are scheduled to be output next (but this does not go\nrecursively), in the hope that it may help a typical \"rev-list\" traversal.\n\nI've tried various workloads from the previous message; while this patch\ndoes not regress any of them significantly, it does not seem to improve\nthem significantly, either.\n\n\n\n builtin/pack-objects.c | 96 ++++++++++++++++++++++++++++++++++-------------\n 1 files changed, 69 insertions(+), 27 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 27132bb..46ae610 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -487,6 +487,74 @@ static void add_family_to_write_order(struct object_entry **wo,\n \tadd_descendants_to_write_order(wo, endp, root);\n }\n \n+static void add_commit_to_write_order(struct object_entry **wo,\n+\t\t\t\t int *endp,\n+\t\t\t\t struct object_entry *e)\n+{\n+\t/*\n+\t * A typical rev-list traversal looks at the parent of a\n+\t * commit before deciding to emit the commit; if it ends up\n+\t * emitting this commit, it is likely that it needs an early\n+\t * access of its parents.\n+\t */\n+\tstruct commit *commit;\n+\tstruct commit_list *parents;\n+\n+\tif (e->filled)\n+\t\treturn;\n+\tadd_to_write_order(wo, endp, e);\n+\tcommit = lookup_commit(e->idx.sha1);\n+\tif (!commit ||\n+\t (!commit->object.parsed && parse_commit(commit)))\n+\t\tdie(\"BUG: calling add_commit with a non-commit???\");\n+\tfor (parents = commit->parents; parents; parents = parents->next) {\n+\t\tstruct object_entry *pe;\n+\t\tstruct commit *parent = parents->item;\n+\t\tpe = locate_object_entry(parent->object.sha1);\n+\t\tif (pe)\n+\t\t\tadd_to_write_order(wo, endp, pe);\n+\t}\n+}\n+\n+static int add_commits_to_write_order(struct object_entry **wo)\n+{\n+\tint i, wo_end;\n+\n+\t/*\n+\t * Give the commits 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+\t\tif (objects[i].type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\t\tif (objects[i].tagged)\n+\t\t\tbreak;\n+\t\tadd_commit_to_write_order(wo, &wo_end, &objects[i]);\n+\t}\n+\n+\t/*\n+\t * Then fill all the tagged tips.\n+\t */\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tif (objects[i].type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\t\tif (objects[i].tagged)\n+\t\t\tadd_commit_to_write_order(wo, &wo_end, &objects[i]);\n+\t}\n+\n+\t/*\n+\t * And then all remaining commits and tags.\n+\t */\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tif (objects[i].type == OBJ_COMMIT)\n+\t\t\tadd_commit_to_write_order(wo, &wo_end, &objects[i]);\n+\t\telse if (objects[i].type != OBJ_TAG)\n+\t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t}\n+\n+\treturn wo_end;\n+}\n+\n static struct object_entry **compute_write_order(void)\n {\n \tint i, wo_end;\n@@ -519,33 +587,7 @@ static struct object_entry **compute_write_order(void)\n \t */\n \tfor_each_tag_ref(mark_tagged, NULL);\n \n-\t/*\n-\t * Give the commits 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-\t\tif (objects[i].tagged)\n-\t\t\tbreak;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n-\t}\n-\n-\t/*\n-\t * Then fill all the tagged tips.\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}\n-\n-\t/*\n-\t * And then all remaining commits and tags.\n-\t */\n-\tfor (i = 0; 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-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n-\t}\n+\two_end = add_commits_to_write_order(wo);\n \n \t/*\n \t * And then all the trees.\n"},{"id":"171027","messageId":"CAJo=hJv3_-G3w+jREONFJyXp1HtDfNcUv17RfGvzziNJUZ=_pA@mail.gmail.com","threadId":"27776","inReplyTo":"7vfwmgfkzo.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-07-09T00:42:38Z","receivedAt":"2011-07-09T00:42:38Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Jul 8, 2011 at 15:47, Junio C Hamano wrote:\n> This updates the codepath to write commit objects so that when a commit is\n> emitted, its parents are scheduled to be output next (but this does not go\n> recursively), in the hope that it may help a typical \"rev-list\" traversal.\n>\n> I've tried various workloads from the previous message; while this patch\n> does not regress any of them significantly, it does not seem to improve\n> them significantly, either.\n\nI'll have to do some more testing then... I feel like this improves\nthings when the underlying storage has higher latency than 0 (aka cold\ncache, or NFS). But its good to hear this didn't make the workloads\nworse. :-)\n\n-- \nShawn.\n"},{"id":"171116","messageId":"alpine.LFD.2.00.1107111846260.14596@xanadu.home","threadId":"27776","inReplyTo":"7voc14fyy8.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2011-07-11T22:49:57Z","receivedAt":"2011-07-11T22:49:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 8 Jul 2011, Junio C Hamano wrote:\n\n> The moral of the story is that index-pack is not a workload to optimize\n> for ;-) and the following is a wrong patch to apply.\n\nRight. And if it was possible to slow down index-pack while speeding up \nthe other workloads then this would actually be worthwhile because \nindex-pack is not used as often and people are not expecting it to be \nfast either.\n\n\nNicolas\n"},{"id":"178377","messageId":"CACBZZX6Ss4jLtdrDhLUNKCUjEHjHHKzfv-LMkOyTPDhRUXm4sQ@mail.gmail.com","threadId":"27776","inReplyTo":"1310084657-16790-3-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-10-27T21:01:50Z","receivedAt":"2011-10-27T21:01:50Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Fri, Jul 8, 2011 at 02:24, Junio C Hamano wrote:\n\n>  - Commits at the tip of tags are written together, in the hope that\n>   revision traversal done in incremental fetch (which starts by\n>   putting them in a revision queue marked as UNINTERESTING) will see a\n>   better locality of these objects;\n\nWe recently upgraded to 1.7.7 and I've traced a very large slowdown in\npacking down to this commit.\n\nOn our repository packing used to take around 30 seconds, it now takes\nabout 4 minutes. Which means that cloning the repository went from\nbeing slightly slow to pretty intolerable.\n\nI haven't dug into why this is but I'm pretty sure it's because this\npatch makes Git behave pathologically on repositories with a large\namount of tags. git.git itself has ~27k revs / and ~450 tags, or a tag\nevery ~60 revisions.\n\nTry it on e.g. a repository with a couple of hundred thousand revs and\na tag every 10-20 revisions.\n"},{"id":"178378","messageId":"CACBZZX6ZWOF=j-k8o-4NHmjS2HpyS+PmKjJh_QKevWurBf9pbA@mail.gmail.com","threadId":"27776","inReplyTo":"CACBZZX6Ss4jLtdrDhLUNKCUjEHjHHKzfv-LMkOyTPDhRUXm4sQ@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-10-27T21:49:14Z","receivedAt":"2011-10-27T21:49:14Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Oct 27, 2011 at 23:01, Ævar Arnfjörð Bjarmason wrote:\n\n> I haven't dug into why this is but I'm pretty sure it's because this\n> patch makes Git behave pathologically on repositories with a large\n> amount of tags. git.git itself has ~27k revs / and ~450 tags, or a tag\n> every ~60 revisions.\n>\n> Try it on e.g. a repository with a couple of hundred thousand revs and\n> a tag every 10-20 revisions.\n\nActually it just seems slow in general, not just on repositories with\na lot of tags, on linux-2.6.git with this patch:\n\n $ time ~/g/git/git-pack-objects --keep-true-parents\n--honor-pack-keep --non-empty --all --reflog\n--delta-base-offs); print $sha\nif $i++ % 10 == 0' | parallel \"git tag test-tag-{} {}\"\n\nResulting in:\n\n $ git rev-list HEAD | wc -l\n 269514\n $ git tag -l | wc -l\n 13733\n\nThis'll be the time with this patch reverted, i.e. almost exactly the\nsame as with just ~250 tags:\n\n real 0m52.860s\n user 0m44.907s\n sys 0m3.172s\n\nAnd with it applied, i.e. almost exactly the same as with just ~250\ntags:\n\n real 1m29.080s\n user 1m21.825s\n sys 0m3.096s\n"},{"id":"178379","messageId":"CACBZZX7tghoHhxCygEj9DZSxvKyTvybawVA2HwHBkjBaH73Ujg@mail.gmail.com","threadId":"27776","inReplyTo":"CACBZZX6ZWOF=j-k8o-4NHmjS2HpyS+PmKjJh_QKevWurBf9pbA@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-10-27T22:02:44Z","receivedAt":"2011-10-27T22:02:44Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Oct 27, 2011 at 23:49, Ævar Arnfjörð Bjarmason wrote:\n\n> Actually it just seems slow in general, not just on repositories with\n> a lot of tags, on linux-2.6.git with this patch:\n\nHere's profiling with gprof for everything with >1% of execution time\nwith the patch applied:\n\n Each sample counts as 0.01 seconds.\n % cumulative self self total\n time seconds seconds calls s/call s/call name\n 21.07 15.99 15.99 2184059 0.00 0.00\nadd_descendants_to_write_order\n 20.25 31.35 15.37 1146371554 0.00 0.00 add_to_write_order\n 11.94 40.41 9.06 142180385 0.00 0.00 hashcmp\n 5.55 44.62 4.21 90592818 0.00 0.00 lookup_object\n 4.64 48.14 3.52 72804470 0.00 0.00 hashcmp\n 3.87 51.08 2.94 90007452 0.00 0.00 get_mode\n 3.31 53.59 2.51 90007452 0.00 0.00 decode_tree_entry\n 1.90 55.03 1.44 2184059 0.00 0.00\nadd_family_to_write_order\n 1.79 56.39 1.36 43247856 0.00 0.00 hashcmp\n 1.29 57.37 0.98 pack_offset_sort\n 1.27 58.33 0.96 90007452 0.00 0.00 update_tree_entry\n 1.27 59.29 0.96 90592817 0.00 0.00 hashtable_index\n 1.20 60.20 0.91 4009188 0.00 0.00 find_pack_revindex\n 1.19 61.10 0.90 5899321 0.00 0.00 find_pack_entry_one\n 1.12 61.95 0.85 269514 0.00 0.00\ncommit_list_insert_by_date\n 1.08 62.77 0.82 5387773 0.00 0.00 patch_delta\n\nAnd without:\n\n Each sample counts as 0.01 seconds.\n % cumulative self self total\n time seconds seconds calls s/call s/call name\n 21.29 9.13 9.13 142180385 0.00 0.00 hashcmp\n 10.59 13.67 4.54 90592818 0.00 0.00 lookup_object\n 8.48 17.31 3.64 72638478 0.00 0.00 hashcmp\n 6.60 20.14 2.83 90007452 0.00 0.00 decode_tree_entry\n 6.15 22.77 2.64 90007452 0.00 0.00 get_mode\n 2.99 24.05 1.28 43247182 0.00 0.00 hashcmp\n 2.96 25.32 1.27 90592817 0.00 0.00 hashtable_index\n 2.47 26.38 1.06 90007452 0.00 0.00 update_tree_entry\n 2.26 27.35 0.97 4009188 0.00 0.00 find_pack_revindex\n 2.05 28.23 0.88 269245 0.00 0.00 process_tree\n 1.96 29.07 0.84 269514 0.00 0.00\ncommit_list_insert_by_date\n 1.94 29.90 0.83 pack_offset_sort\n 1.73 30.64 0.74 5389900 0.00 0.00 patch_delta\n 1.70 31.37 0.73 5885588 0.00 0.00 find_pack_entry_one\n 1.38 31.96 0.59 8692967 0.00 0.00 hashcmp\n 1.24 32.49 0.53 8175096 0.00 0.00\nunpack_object_header_buffer\n 1.14 32.98 0.49 1 0.49 0.59 write_idx_file\n 1.12 33.46 0.48 5885588 0.00 0.00\nnth_packed_object_offset\n 1.12 33.94 0.48 6051632 0.00 0.00\nlocate_object_entry_hash\n"},{"id":"178380","messageId":"7vy5w6xf7n.fsf@alter.siamese.dyndns.org","threadId":"27776","inReplyTo":"CACBZZX6Ss4jLtdrDhLUNKCUjEHjHHKzfv-LMkOyTPDhRUXm4sQ@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-27T22:05:48Z","receivedAt":"2011-10-27T22:05:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n\n> We recently upgraded to 1.7.7 and I've traced a very large slowdown in\n> packing down to this commit.\n\nDoes Dan McGee's series leading to 38d4deb (pack-objects: don't traverse\nobjects unnecessarily, 2011-10-18) help?\n"},{"id":"178385","messageId":"m3ehxy5aoe.fsf@localhost.localdomain","threadId":"27776","inReplyTo":"CACBZZX7tghoHhxCygEj9DZSxvKyTvybawVA2HwHBkjBaH73Ujg@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-10-27T22:32:06Z","receivedAt":"2011-10-27T22:32:06Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n\n> On Thu, Oct 27, 2011 at 23:49, Ævar Arnfjörð Bjarmason wrote:\n> \n> > Actually it just seems slow in general, not just on repositories with\n> > a lot of tags, on linux-2.6.git with this patch:\n> \n> Here's profiling with gprof for everything with >1% of execution time\n> with the patch applied:\n> \n> Each sample counts as 0.01 seconds.\n> % cumulative self self total\n> time seconds seconds calls s/call s/call name\n> 21.07 15.99 15.99 2184059 0.00 0.00 add_descendants_to_write_order\n> 20.25 31.35 15.37 1146371554 0.00 0.00 add_to_write_order\n[...]\n> \n> And without:\n> \n> Each sample counts as 0.01 seconds.\n> % cumulative self self total\n> time seconds seconds calls s/call s/call name\n> 21.29 9.13 9.13 142180385 0.00 0.00 hashcmp\n> 10.59 13.67 4.54 90592818 0.00 0.00 lookup_object\n[...]\n\nErrr... do or do not gprof results include time spend in libraries?\nThough that might not matter for this case.\n\nCan you repeat profiling using \"perf events\" or something using it\n(e.g. via PAPI library like HPCToolkit)?\n\n-- \nJakub Narębski\n"},{"id":"178402","messageId":"CACBZZX7taoaRWALYd_scf6Z2Hr-xo3voNh=vx8LoPvU8Xo290w@mail.gmail.com","threadId":"27776","inReplyTo":"7vy5w6xf7n.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] pack-objects: optimize \"recency order\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-10-28T09:17:44Z","receivedAt":"2011-10-28T09:17:44Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Fri, Oct 28, 2011 at 00:05, Junio C Hamano wrote:\n> Ævar Arnfjörð Bjarmason writes:\n>\n>> We recently upgraded to 1.7.7 and I've traced a very large slowdown in\n>> packing down to this commit.\n>\n> Does Dan McGee's series leading to 38d4deb (pack-objects: don't traverse\n> objects unnecessarily, 2011-10-18) help?\n\nYes it does!\n\nWhen I do:\n\n git cherry-pick 703f05ad5835cff92b12c29aecf8d724c8c847e2..38d4deb\n\nHere's the time on the linux-2.6.git repack with that series:\n\n real 0m53.969s\n user 0m47.063s\n sys 0m3.020s\n\nOn the repository I was having troubles with this was the result on\nmaster:\n\n Total 911023 (delta 687744), reused 905500 (delta 683064)\n\n real 6m0.487s\n user 4m1.751s\n sys 1m56.331s\n\nAnd with the cherry-pick:\n\n Total 911023 (delta 687744), reused 911023 (delta 687744)\n\n real 1m44.192s\n user 0m32.169s\n sys 0m4.383s\n\nAnd with 1b4bb16b9ec331c91e28d2e3e7dee5070534b6a2 reverted:\n\n Total 911023 (delta 687744), reused 911023 (delta 687744)\n\n real 1m23.796s\n user 0m31.931s\n sys 0m3.549s\n\nSo it's still slower, but not intolerably slower. I'd be interested to\nfind out why we have that 20% difference that doesn't show up on\nlinux-2.6.git though, the repository is mostly source code but there\nare some binary blobs in it as well, although not very large, the\noverall size of the entire repository is <500MB.\n"}]}