{"thread":{"id":"52364","subject":"[PATCH] packfile.c: speed up loading lots of packfiles.","startedAt":"2019-11-27T23:35:33Z","lastAt":"2019-12-04T18:15:29Z","messageCount":15,"participants":["Colin Stolley","Eric Wong","Junio C Hamano","Jeff King","SZEDER Gábor","Taylor Blau","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"387252","messageId":"20191127222453.GA3765@owl.colinstolley.com","threadId":"52364","inReplyTo":null,"subject":"[PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Colin Stolley","fromEmail":"cstolley@runbox.com","sentAt":"2019-11-27T22:24:53Z","receivedAt":"2019-11-27T23:35:33Z","isPatch":true,"sender":{"key":"cstolley@runbox.com","avatar":null},"body":"When loading packfiles on start-up, we traverse the internal packfile\nlist once per file to avoid reloading packfiles that have already\nbeen loaded. This check runs in quadratic time, so for poorly\nmaintained repos with a large number of packfiles, it can be pretty\nslow.\n\nAdd a hashmap containing the packfile names as we load them so that\nthe average runtime cost of checking for already-loaded packs becomes\nconstant.\n\nAdd a perf test to p5303 to show speed-up.\n\nThe existing p5303 test runtimes are dominated by other factors and do\nnot show an appreciable speed-up. The new test in p5303 clearly exposes\na speed-up in bad cases. In this test we create 10,000 packfiles and\nmeasure the start-up time of git rev-parse, which does little else\nbesides load in the packs.\n\nHere are the numbers for the new p5303 test:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n5303.12: load 10,000 packs 1.03(0.92+0.10) 0.12(0.02+0.09) -88.3%\n\nThanks-to: Jeff King \nSigned-off-by: Colin Stolley \n---\n object-store.h | 21 +++++++++++++++++++++\n object.c | 3 +++\n packfile.c | 21 +++++++++++----------\n t/perf/p5303-many-packs.sh | 18 ++++++++++++++++++\n 4 files changed, 53 insertions(+), 10 deletions(-)\n\ndiff --git a/object-store.h b/object-store.h\nindex 7f7b3cdd80..55ee639350 100644\n--- a/object-store.h\n+++ b/object-store.h\n@@ -60,6 +60,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb,\n void odb_clear_loose_cache(struct object_directory *odb);\n \n struct packed_git {\n+\tstruct hashmap_entry packmap_ent;\n \tstruct packed_git *next;\n \tstruct list_head mru;\n \tstruct pack_window *windows;\n@@ -88,6 +89,20 @@ struct packed_git {\n \n struct multi_pack_index;\n \n+static inline int pack_map_entry_cmp(const void *unused_cmp_data,\n+\t\t\t\t const struct hashmap_entry *entry,\n+\t\t\t\t const struct hashmap_entry *entry2,\n+\t\t\t\t const void *keydata)\n+{\n+\tconst char *key = keydata;\n+\tconst struct packed_git *pg1, *pg2;\n+\n+\tpg1 = container_of(entry, const struct packed_git, packmap_ent);\n+\tpg2 = container_of(entry2, const struct packed_git, packmap_ent);\n+\n+\treturn strcmp(pg1->pack_name, key ? key : pg2->pack_name);\n+}\n+\n struct raw_object_store {\n \t/*\n \t * Set of all object directories; the main directory is first (and\n@@ -131,6 +146,12 @@ struct raw_object_store {\n \t/* A most-recently-used ordered version of the packed_git list. */\n \tstruct list_head packed_git_mru;\n \n+\t/*\n+\t * A map of packfiles to packed_git structs for tracking which\n+\t * packs have been loaded already.\n+\t */\n+\tstruct hashmap pack_map;\n+\n \t/*\n \t * A fast, rough count of the number of objects in the repository.\n \t * These two fields are not meant for direct access. Use\ndiff --git a/object.c b/object.c\nindex 3b8b8c55c9..142ef69399 100644\n--- a/object.c\n+++ b/object.c\n@@ -479,6 +479,7 @@ struct raw_object_store *raw_object_store_new(void)\n \n \tmemset(o, 0, sizeof(*o));\n \tINIT_LIST_HEAD(&o->packed_git_mru);\n+\thashmap_init(&o->pack_map, pack_map_entry_cmp, NULL, 0);\n \treturn o;\n }\n \n@@ -518,6 +519,8 @@ void raw_object_store_clear(struct raw_object_store *o)\n \tINIT_LIST_HEAD(&o->packed_git_mru);\n \tclose_object_store(o);\n \to->packed_git = NULL;\n+\n+\thashmap_free(&o->pack_map);\n }\n \n void parsed_object_pool_clear(struct parsed_object_pool *o)\ndiff --git a/packfile.c b/packfile.c\nindex 355066de17..253559fa87 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -856,20 +856,21 @@ static void prepare_pack(const char *full_name, size_t full_name_len,\n \n \tif (strip_suffix_mem(full_name, &base_len, \".idx\") &&\n \t !(data->m && midx_contains_pack(data->m, file_name))) {\n-\t\t/* Don't reopen a pack we already have. */\n-\t\tfor (p = data->r->objects->packed_git; p; p = p->next) {\n-\t\t\tsize_t len;\n-\t\t\tif (strip_suffix(p->pack_name, \".pack\", &len) &&\n-\t\t\t len == base_len &&\n-\t\t\t !memcmp(p->pack_name, full_name, len))\n-\t\t\t\tbreak;\n-\t\t}\n+\t\tstruct hashmap_entry hent;\n+\t\tchar *pack_name = xstrfmt(\"%.*s.pack\", (int)base_len, full_name);\n+\t\tunsigned int hash = strhash(pack_name);\n+\t\thashmap_entry_init(&hent, hash);\n \n-\t\tif (!p) {\n+\t\t/* Don't reopen a pack we already have. */\n+\t\tif (!hashmap_get(&data->r->objects->pack_map, &hent, pack_name)) {\n \t\t\tp = add_packed_git(full_name, full_name_len, data->local);\n-\t\t\tif (p)\n+\t\t\tif (p) {\n+\t\t\t\thashmap_entry_init(&p->packmap_ent, hash);\n+\t\t\t\thashmap_add(&data->r->objects->pack_map, &p->packmap_ent);\n \t\t\t\tinstall_packed_git(data->r, p);\n+\t\t\t}\n \t\t}\n+\t\tfree(pack_name);\n \t}\n \n \tif (!report_garbage)\ndiff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\nindex 3779851941..ede78e19e2 100755\n--- a/t/perf/p5303-many-packs.sh\n+++ b/t/perf/p5303-many-packs.sh\n@@ -84,4 +84,22 @@ do\n \t'\n done\n \n+# Measure pack loading with 10,000 packs.\n+test_expect_success 'generate lots of packs' '\n+\tfor i in $(test_seq 10000); do\n+\t\techo \"blob\"\n+\t\techo \"data < wrote:\n> When loading packfiles on start-up, we traverse the internal packfile\n> list once per file to avoid reloading packfiles that have already\n> been loaded. This check runs in quadratic time, so for poorly\n> maintained repos with a large number of packfiles, it can be pretty\n> slow.\n\nCool! Thanks for looking into this, and I've been having\ntrouble in that department with big alternates files.\n\n> Add a hashmap containing the packfile names as we load them so that\n> the average runtime cost of checking for already-loaded packs becomes\n> constant.\n\nBtw, would you have time to do a comparison against khash?\n\nAFAIK hashmap predates khash in git; and hashmap was optimized\nfor removal. Removals don't seem to be a problem for pack\nloading.\n\nI'm interested in exploring the removing of hashmap entirely in\nfavor of khash to keep our codebase smaller and easier-to-learn.\nkhash shows up more in other projects, and ought to have better\ncache-locality.\n\nThanks again.\n"},{"id":"387341","messageId":"xmqqeexp2rm8.fsf@gitster-ct.c.googlers.com","threadId":"52364","inReplyTo":"20191128004202.GA25910@dcvr","subject":"Re: hashmap vs khash? Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-11-30T17:36:47Z","receivedAt":"2019-11-30T17:36:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Wong writes:\n\n> Colin Stolley wrote:\n>> When loading packfiles on start-up, we traverse the internal packfile\n>> list once per file to avoid reloading packfiles that have already\n>> been loaded. This check runs in quadratic time, so for poorly\n>> maintained repos with a large number of packfiles, it can be pretty\n>> slow.\n>\n> Cool! Thanks for looking into this, and I've been having\n> trouble in that department with big alternates files.\n>\n>> Add a hashmap containing the packfile names as we load them so that\n>> the average runtime cost of checking for already-loaded packs becomes\n>> constant.\n>\n> Btw, would you have time to do a comparison against khash?\n>\n> AFAIK hashmap predates khash in git; and hashmap was optimized\n> for removal. Removals don't seem to be a problem for pack\n> loading.\n>\n> I'm interested in exploring the removing of hashmap entirely in\n> favor of khash to keep our codebase smaller and easier-to-learn.\n> khash shows up more in other projects, and ought to have better\n> cache-locality.\n\nSounds fun ;-) and useful.\n"},{"id":"387401","messageId":"20191202143944.GA18276@sigill.intra.peff.net","threadId":"52364","inReplyTo":"20191128004202.GA25910@dcvr","subject":"Re: hashmap vs khash? Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-02T14:39:44Z","receivedAt":"2019-12-02T14:39:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Nov 28, 2019 at 12:42:02AM +0000, Eric Wong wrote:\n\n> > Add a hashmap containing the packfile names as we load them so that\n> > the average runtime cost of checking for already-loaded packs becomes\n> > constant.\n> \n> Btw, would you have time to do a comparison against khash?\n> \n> AFAIK hashmap predates khash in git; and hashmap was optimized\n> for removal. Removals don't seem to be a problem for pack\n> loading.\n\nActually, they came around simultaneously. I think hashmap.[ch] was\nmostly a response to our open-coded hashes, like the one in object.c\n(which still uses neither of the reusable forms!). Those didn't handle\nremoval at all. khash does handle removal, though you pay a price in\ntombstone entries until the next resize operation.\n\n> I'm interested in exploring the removing of hashmap entirely in\n> favor of khash to keep our codebase smaller and easier-to-learn.\n> khash shows up more in other projects, and ought to have better\n> cache-locality.\n\nI have been tempted to push for that, too. Every timing I have ever done\nshows khash as faster (though for a trivial use like this one, I would\nbe quite surprised if it mattered either way).\n\nMy hesitation is that khash can be harder to debug because of the macro\nimplementation. But I have rarely needed to look beneath its API.\n\n-Peff\n"},{"id":"387407","messageId":"20191202174035.GJ23183@szeder.dev","threadId":"52364","inReplyTo":"20191127222453.GA3765@owl.colinstolley.com","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-12-02T17:40:35Z","receivedAt":"2019-12-02T17:40:42Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, Nov 27, 2019 at 04:24:53PM -0600, Colin Stolley wrote:\n> When loading packfiles on start-up, we traverse the internal packfile\n> list once per file to avoid reloading packfiles that have already\n> been loaded. This check runs in quadratic time, so for poorly\n> maintained repos with a large number of packfiles, it can be pretty\n> slow.\n> \n> Add a hashmap containing the packfile names as we load them so that\n> the average runtime cost of checking for already-loaded packs becomes\n> constant.\n> \n> Add a perf test to p5303 to show speed-up.\n> \n> The existing p5303 test runtimes are dominated by other factors and do\n> not show an appreciable speed-up. The new test in p5303 clearly exposes\n> a speed-up in bad cases. In this test we create 10,000 packfiles and\n> measure the start-up time of git rev-parse, which does little else\n> besides load in the packs.\n> \n> Here are the numbers for the new p5303 test:\n> \n> Test HEAD^ HEAD\n> ---------------------------------------------------------------------\n> 5303.12: load 10,000 packs 1.03(0.92+0.10) 0.12(0.02+0.09) -88.3%\n> \n> Thanks-to: Jeff King \n> Signed-off-by: Colin Stolley \n> ---\n\nThis patch break test 'gc --keep-largest-pack' in 't6500-gc.sh' when\nrun with GIT_TEST_MULTI_PACK_INDEX=1, because there is a duplicate\nentry in '.git/objects/info/packs':\n\n expecting success of 6500.7 'gc --keep-largest-pack':\n test_create_repo keep-pack &&\n (\n cd keep-pack &&\n test_commit one &&\n test_commit two &&\n test_commit three &&\n git gc &&\n ( cd .git/objects/pack && ls *.pack ) >pack-list &&\n test_line_count = 1 pack-list &&\n BASE_PACK=.git/objects/pack/pack-*.pack &&\n test_commit four &&\n git repack -d &&\n test_commit five &&\n git repack -d &&\n ( cd .git/objects/pack && ls *.pack ) >pack-list &&\n test_line_count = 3 pack-list &&\n git gc --keep-largest-pack &&\n ( cd .git/objects/pack && ls *.pack ) >pack-list &&\n test_line_count = 2 pack-list &&\n awk \"/^P /{print \\$2}\" <.git/objects/info/packs >pack-info &&\n test_line_count = 2 pack-info &&\n test_path_is_file $BASE_PACK &&\n git fsck\n )\n \n + test_create_repo keep-pack\n Initialized empty Git repository in /home/szeder/src/git/t/trash directory.t6500-gc/keep-pack/.git/\n + cd keep-pack\n + test_commit one\n [master (root-commit) d79ce16] one\n Author: A U Thor \n 1 file changed, 1 insertion(+)\n create mode 100644 one.t\n + test_commit two\n [master 139b20d] two\n Author: A U Thor \n 1 file changed, 1 insertion(+)\n create mode 100644 two.t\n + test_commit three\n [master 7c7cd71] three\n Author: A U Thor \n 1 file changed, 1 insertion(+)\n create mode 100644 three.t\n + git gc\n Computing commit graph generation numbers: 33% (1/3)^MComputing commit graph generation numbers: 66% (2/3)^MComputing commit graph generation numbers: 100% (3/3)^MComputing commit graph generation numbers: 100% (3/3), done.\n + cd .git/objects/pack\n + ls pack-a4b37b9b5458e8116b1c1840185b39fb5e6b8726.pack\n + test_line_count = 1 pack-list\n + BASE_PACK=.git/objects/pack/pack-*.pack\n + test_commit four\n [master fd8d77e] four\n Author: A U Thor \n 1 file changed, 1 insertion(+)\n create mode 100644 four.t\n + git repack -d\n + test_commit five\n [master a383792] five\n Author: A U Thor \n 1 file changed, 1 insertion(+)\n create mode 100644 five.t\n + git repack -d\n + cd .git/objects/pack\n + ls pack-057d7f493a7c26d58090f4777ff66d4c226c4408.pack pack-54feec766fc7d2d204b03879d96f4595d7e48c37.pack pack-a4b37b9b5458e8116b1c1840185b39fb5e6b8726.pack\n + test_line_count = 3 pack-list\n + git gc --keep-largest-pack\n Computing commit graph generation numbers: 20% (1/5)^MComputing commit graph generation numbers: 40% (2/5)^MComputing commit graph generation numbers: 60% (3/5)^MComputing commit graph generation numbers: 80% (4/5)^MComputing commit graph generation numbers: 100% (5/5)^MComputing commit graph generation numbers: 100% (5/5), done.\n + cd .git/objects/pack\n + ls pack-390dbbb8e27c014b080c08dfc482d4982d4c6644.pack pack-a4b37b9b5458e8116b1c1840185b39fb5e6b8726.pack\n + test_line_count = 2 pack-list\n + awk /^P /{print $2}\n + test_line_count = 2 pack-info\n test_line_count: line count for pack-info != 2\n pack-a4b37b9b5458e8116b1c1840185b39fb5e6b8726.pack\n pack-a4b37b9b5458e8116b1c1840185b39fb5e6b8726.pack\n pack-390dbbb8e27c014b080c08dfc482d4982d4c6644.pack\n error: last command exited with $?=1\n not ok 7 - gc --keep-largest-pack\n\n\n"},{"id":"387415","messageId":"20191202194231.GA10707@sigill.intra.peff.net","threadId":"52364","inReplyTo":"20191202174035.GJ23183@szeder.dev","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-02T19:42:31Z","receivedAt":"2019-12-02T19:42:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 02, 2019 at 06:40:35PM +0100, SZEDER Gábor wrote:\n\n> > When loading packfiles on start-up, we traverse the internal packfile\n> > list once per file to avoid reloading packfiles that have already\n> > been loaded. This check runs in quadratic time, so for poorly\n> > maintained repos with a large number of packfiles, it can be pretty\n> > slow.\n> > \n> > Add a hashmap containing the packfile names as we load them so that\n> > the average runtime cost of checking for already-loaded packs becomes\n> > constant.\n> [...]\n> This patch break test 'gc --keep-largest-pack' in 't6500-gc.sh' when\n> run with GIT_TEST_MULTI_PACK_INDEX=1, because there is a duplicate\n> entry in '.git/objects/info/packs':\n\nGood catch. The issue is that we only add entries to the hashmap in\nprepare_packed_git(), but they may be added to the pack list by other\ncallers of install_packed_git(). It probably makes sense to just push\nthe hashmap maintenance down into that function, like below. That\nrequires an extra strhash() when inserting a new pack, but I don't think\nthat's a big deal.\n\ndiff --git a/packfile.c b/packfile.c\nindex 253559fa87..f0dc63e92f 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -757,6 +757,9 @@ void install_packed_git(struct repository *r, struct packed_git *pack)\n \n \tpack->next = r->objects->packed_git;\n \tr->objects->packed_git = pack;\n+\n+\thashmap_entry_init(&pack->packmap_ent, strhash(pack->pack_name));\n+\thashmap_add(&r->objects->pack_map, &pack->packmap_ent);\n }\n \n void (*report_garbage)(unsigned seen_bits, const char *path);\n@@ -864,11 +867,8 @@ static void prepare_pack(const char *full_name, size_t full_name_len,\n \t\t/* Don't reopen a pack we already have. */\n \t\tif (!hashmap_get(&data->r->objects->pack_map, &hent, pack_name)) {\n \t\t\tp = add_packed_git(full_name, full_name_len, data->local);\n-\t\t\tif (p) {\n-\t\t\t\thashmap_entry_init(&p->packmap_ent, hash);\n-\t\t\t\thashmap_add(&data->r->objects->pack_map, &p->packmap_ent);\n+\t\t\tif (p)\n \t\t\t\tinstall_packed_git(data->r, p);\n-\t\t\t}\n \t\t}\n \t\tfree(pack_name);\n \t}\n\n-Peff\n"},{"id":"387428","messageId":"20191203061744.GA74594@syl.local","threadId":"52364","inReplyTo":"20191202194231.GA10707@sigill.intra.peff.net","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2019-12-03T06:17:44Z","receivedAt":"2019-12-03T06:17:49Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Dec 02, 2019 at 02:42:31PM -0500, Jeff King wrote:\n> On Mon, Dec 02, 2019 at 06:40:35PM +0100, SZEDER Gábor wrote:\n>\n> > > When loading packfiles on start-up, we traverse the internal packfile\n> > > list once per file to avoid reloading packfiles that have already\n> > > been loaded. This check runs in quadratic time, so for poorly\n> > > maintained repos with a large number of packfiles, it can be pretty\n> > > slow.\n> > >\n> > > Add a hashmap containing the packfile names as we load them so that\n> > > the average runtime cost of checking for already-loaded packs becomes\n> > > constant.\n> > [...]\n> > This patch break test 'gc --keep-largest-pack' in 't6500-gc.sh' when\n> > run with GIT_TEST_MULTI_PACK_INDEX=1, because there is a duplicate\n> > entry in '.git/objects/info/packs':\n>\n> Good catch. The issue is that we only add entries to the hashmap in\n> prepare_packed_git(), but they may be added to the pack list by other\n> callers of install_packed_git(). It probably makes sense to just push\n> the hashmap maintenance down into that function, like below. That\n> requires an extra strhash() when inserting a new pack, but I don't think\n> that's a big deal.\n\nAh, great catch, and thanks for pointing it out. We have been running\nthis patch in production at GitHub for a few weeks now, but didn't\nnotice this because we never run tests with\n'GIT_TEST_MULTI_PACK_INDEX=1' in the environment.\n\nPerhaps in the future that might change, but I think that for now that\ncan explain why the failure wasn't noticed earlier.\n\n> diff --git a/packfile.c b/packfile.c\n> index 253559fa87..f0dc63e92f 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -757,6 +757,9 @@ void install_packed_git(struct repository *r, struct packed_git *pack)\n>\n> \tpack->next = r->objects->packed_git;\n> \tr->objects->packed_git = pack;\n> +\n> +\thashmap_entry_init(&pack->packmap_ent, strhash(pack->pack_name));\n> +\thashmap_add(&r->objects->pack_map, &pack->packmap_ent);\n> }\n>\n> void (*report_garbage)(unsigned seen_bits, const char *path);\n> @@ -864,11 +867,8 @@ static void prepare_pack(const char *full_name, size_t full_name_len,\n> \t\t/* Don't reopen a pack we already have. */\n> \t\tif (!hashmap_get(&data->r->objects->pack_map, &hent, pack_name)) {\n> \t\t\tp = add_packed_git(full_name, full_name_len, data->local);\n> -\t\t\tif (p) {\n> -\t\t\t\thashmap_entry_init(&p->packmap_ent, hash);\n> -\t\t\t\thashmap_add(&data->r->objects->pack_map, &p->packmap_ent);\n> +\t\t\tif (p)\n> \t\t\t\tinstall_packed_git(data->r, p);\n> -\t\t\t}\n> \t\t}\n> \t\tfree(pack_name);\n> \t}\n>\n> -Peff\nThanks,\nTaylor\n"},{"id":"387429","messageId":"20191203061954.GB74594@syl.local","threadId":"52364","inReplyTo":"20191127222453.GA3765@owl.colinstolley.com","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2019-12-03T06:19:54Z","receivedAt":"2019-12-03T06:19:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Colin,\n\nOn Wed, Nov 27, 2019 at 04:24:53PM -0600, Colin Stolley wrote:\n> When loading packfiles on start-up, we traverse the internal packfile\n> list once per file to avoid reloading packfiles that have already\n> been loaded. This check runs in quadratic time, so for poorly\n> maintained repos with a large number of packfiles, it can be pretty\n> slow.\n\nThanks for sending your patches to the list, and for working on this! I\nhave been most excited to see this develop internally, and I'm glad that\nthe new paths have been exercised enough to send the patches.\n\nSo, I'm quite interested to see what you find in terms of wiring this\ncode up to work with khash. If that's something that you don't have time\nfor, please do let me know and I'd be happy to take it up myself.\n\nOther than that, this has been thoroughly reviewed internally, and so I\ndon't have much more to add to this patch than what we have already\ndiscussed.\n\n\nThanks,\nTaylor\n"},{"id":"387453","messageId":"20191203153415.GA5813@sigill.intra.peff.net","threadId":"52364","inReplyTo":"20191203061744.GA74594@syl.local","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-03T15:34:15Z","receivedAt":"2019-12-03T15:34:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 02, 2019 at 10:17:44PM -0800, Taylor Blau wrote:\n\n> > Good catch. The issue is that we only add entries to the hashmap in\n> > prepare_packed_git(), but they may be added to the pack list by other\n> > callers of install_packed_git(). It probably makes sense to just push\n> > the hashmap maintenance down into that function, like below. That\n> > requires an extra strhash() when inserting a new pack, but I don't think\n> > that's a big deal.\n> \n> Ah, great catch, and thanks for pointing it out. We have been running\n> this patch in production at GitHub for a few weeks now, but didn't\n> notice this because we never run tests with\n> 'GIT_TEST_MULTI_PACK_INDEX=1' in the environment.\n> \n> Perhaps in the future that might change, but I think that for now that\n> can explain why the failure wasn't noticed earlier.\n\nIt would trigger in other contexts, too: anywhere we call\ninstall_packed_git() outside of prepare_packed_git(). I think the main\nreason we didn't notice in the tests or in production is that:\n\n - it would generally require re-scanning the pack directory, which\n implies an unexpected missing object (or a racy repack), which is\n not likely to happen during the tests\n\n - in most cases duplicates don't impact the outcome of the command at\n all. A duplicate entry in the packed_git list would just mean an\n extra pack to check for lookups. Most objects would be found in\n other packs (including its doppelganger entry), so the duplicate\n would float to the bottom of the MRU order. It's only lookups for\n objects we don't have that would pay a penalty (and it would be\n relatively small).\n\nBut obviously it's still worth fixing.\n\n-Peff\n"},{"id":"387458","messageId":"xmqq7e3d75vk.fsf@gitster-ct.c.googlers.com","threadId":"52364","inReplyTo":"20191202194231.GA10707@sigill.intra.peff.net","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-12-03T16:04:15Z","receivedAt":"2019-12-03T16:04:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Good catch. The issue is that we only add entries to the hashmap in\n> prepare_packed_git(), but they may be added to the pack list by other\n> callers of install_packed_git(). It probably makes sense to just push\n> the hashmap maintenance down into that function, like below.\n\nMakes sense to me.\n\nLet me locally squash your fix in and credit you with helped-by\nfooter in the amended log message. Strictly speaking, this may\ninvalidate the perf numbers, but I do not think the scenario p5303\nsets up alone is all that interesting anyway---if you have 10,000\npacks, not just registering them (which is improved with this patch)\nbut using objects from them would be slower than necessary X-<.\n\nThanks.\n\n -- >8 --\n\nFrom: Colin Stolley \nDate: Wed, 27 Nov 2019 16:24:53 -0600\nSubject: [PATCH] packfile.c: speed up loading lots of packfiles\n\nWhen loading packfiles on start-up, we traverse the internal packfile\nlist once per file to avoid reloading packfiles that have already\nbeen loaded. This check runs in quadratic time, so for poorly\nmaintained repos with a large number of packfiles, it can be pretty\nslow.\n\nAdd a hashmap containing the packfile names as we load them so that\nthe average runtime cost of checking for already-loaded packs becomes\nconstant.\n\nAdd a perf test to p5303 to show speed-up.\n\nThe existing p5303 test runtimes are dominated by other factors and do\nnot show an appreciable speed-up. The new test in p5303 clearly exposes\na speed-up in bad cases. In this test we create 10,000 packfiles and\nmeasure the start-up time of git rev-parse, which does little else\nbesides load in the packs.\n\nHere are the numbers for the new p5303 test:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n5303.12: load 10,000 packs 1.03(0.92+0.10) 0.12(0.02+0.09) -88.3%\n\nSigned-off-by: Colin Stolley \nHelped-by: Jeff King \n[jc: squashed the change to call hashmap in install_packed_git() by peff]\nSigned-off-by: Junio C Hamano \n---\n object-store.h | 21 +++++++++++++++++++++\n object.c | 3 +++\n packfile.c | 19 ++++++++++---------\n t/perf/p5303-many-packs.sh | 18 ++++++++++++++++++\n 4 files changed, 52 insertions(+), 9 deletions(-)\n\ndiff --git a/object-store.h b/object-store.h\nindex 7f7b3cdd80..55ee639350 100644\n--- a/object-store.h\n+++ b/object-store.h\n@@ -60,6 +60,7 @@ struct oid_array *odb_loose_cache(struct object_directory *odb,\n void odb_clear_loose_cache(struct object_directory *odb);\n \n struct packed_git {\n+\tstruct hashmap_entry packmap_ent;\n \tstruct packed_git *next;\n \tstruct list_head mru;\n \tstruct pack_window *windows;\n@@ -88,6 +89,20 @@ struct packed_git {\n \n struct multi_pack_index;\n \n+static inline int pack_map_entry_cmp(const void *unused_cmp_data,\n+\t\t\t\t const struct hashmap_entry *entry,\n+\t\t\t\t const struct hashmap_entry *entry2,\n+\t\t\t\t const void *keydata)\n+{\n+\tconst char *key = keydata;\n+\tconst struct packed_git *pg1, *pg2;\n+\n+\tpg1 = container_of(entry, const struct packed_git, packmap_ent);\n+\tpg2 = container_of(entry2, const struct packed_git, packmap_ent);\n+\n+\treturn strcmp(pg1->pack_name, key ? key : pg2->pack_name);\n+}\n+\n struct raw_object_store {\n \t/*\n \t * Set of all object directories; the main directory is first (and\n@@ -131,6 +146,12 @@ struct raw_object_store {\n \t/* A most-recently-used ordered version of the packed_git list. */\n \tstruct list_head packed_git_mru;\n \n+\t/*\n+\t * A map of packfiles to packed_git structs for tracking which\n+\t * packs have been loaded already.\n+\t */\n+\tstruct hashmap pack_map;\n+\n \t/*\n \t * A fast, rough count of the number of objects in the repository.\n \t * These two fields are not meant for direct access. Use\ndiff --git a/object.c b/object.c\nindex 3b8b8c55c9..142ef69399 100644\n--- a/object.c\n+++ b/object.c\n@@ -479,6 +479,7 @@ struct raw_object_store *raw_object_store_new(void)\n \n \tmemset(o, 0, sizeof(*o));\n \tINIT_LIST_HEAD(&o->packed_git_mru);\n+\thashmap_init(&o->pack_map, pack_map_entry_cmp, NULL, 0);\n \treturn o;\n }\n \n@@ -518,6 +519,8 @@ void raw_object_store_clear(struct raw_object_store *o)\n \tINIT_LIST_HEAD(&o->packed_git_mru);\n \tclose_object_store(o);\n \to->packed_git = NULL;\n+\n+\thashmap_free(&o->pack_map);\n }\n \n void parsed_object_pool_clear(struct parsed_object_pool *o)\ndiff --git a/packfile.c b/packfile.c\nindex 355066de17..f0dc63e92f 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -757,6 +757,9 @@ void install_packed_git(struct repository *r, struct packed_git *pack)\n \n \tpack->next = r->objects->packed_git;\n \tr->objects->packed_git = pack;\n+\n+\thashmap_entry_init(&pack->packmap_ent, strhash(pack->pack_name));\n+\thashmap_add(&r->objects->pack_map, &pack->packmap_ent);\n }\n \n void (*report_garbage)(unsigned seen_bits, const char *path);\n@@ -856,20 +859,18 @@ static void prepare_pack(const char *full_name, size_t full_name_len,\n \n \tif (strip_suffix_mem(full_name, &base_len, \".idx\") &&\n \t !(data->m && midx_contains_pack(data->m, file_name))) {\n-\t\t/* Don't reopen a pack we already have. */\n-\t\tfor (p = data->r->objects->packed_git; p; p = p->next) {\n-\t\t\tsize_t len;\n-\t\t\tif (strip_suffix(p->pack_name, \".pack\", &len) &&\n-\t\t\t len == base_len &&\n-\t\t\t !memcmp(p->pack_name, full_name, len))\n-\t\t\t\tbreak;\n-\t\t}\n+\t\tstruct hashmap_entry hent;\n+\t\tchar *pack_name = xstrfmt(\"%.*s.pack\", (int)base_len, full_name);\n+\t\tunsigned int hash = strhash(pack_name);\n+\t\thashmap_entry_init(&hent, hash);\n \n-\t\tif (!p) {\n+\t\t/* Don't reopen a pack we already have. */\n+\t\tif (!hashmap_get(&data->r->objects->pack_map, &hent, pack_name)) {\n \t\t\tp = add_packed_git(full_name, full_name_len, data->local);\n \t\t\tif (p)\n \t\t\t\tinstall_packed_git(data->r, p);\n \t\t}\n+\t\tfree(pack_name);\n \t}\n \n \tif (!report_garbage)\ndiff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\nindex 3779851941..ede78e19e2 100755\n--- a/t/perf/p5303-many-packs.sh\n+++ b/t/perf/p5303-many-packs.sh\n@@ -84,4 +84,22 @@ do\n \t'\n done\n \n+# Measure pack loading with 10,000 packs.\n+test_expect_success 'generate lots of packs' '\n+\tfor i in $(test_seq 10000); do\n+\t\techo \"blob\"\n+\t\techo \"data < Let me locally squash your fix in and credit you with helped-by\n> footer in the amended log message. Strictly speaking, this may\n\nI'm also happy to provide a khash version if that is still desired,\nperhaps as a separate patch.\n\nThanks for spotting that bug and providing a fix.\n"},{"id":"387467","messageId":"20191203221730.GA28419@sigill.intra.peff.net","threadId":"52364","inReplyTo":"xmqq7e3d75vk.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-03T22:17:30Z","receivedAt":"2019-12-03T22:17:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 03, 2019 at 08:04:15AM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Good catch. The issue is that we only add entries to the hashmap in\n> > prepare_packed_git(), but they may be added to the pack list by other\n> > callers of install_packed_git(). It probably makes sense to just push\n> > the hashmap maintenance down into that function, like below.\n> \n> Makes sense to me.\n> \n> Let me locally squash your fix in and credit you with helped-by\n> footer in the amended log message. Strictly speaking, this may\n> invalidate the perf numbers, but I do not think the scenario p5303\n> sets up alone is all that interesting anyway---if you have 10,000\n> packs, not just registering them (which is improved with this patch)\n> but using objects from them would be slower than necessary X-<.\n\nThanks, that sounds good.\n\nI actually re-checked the perf numbers (mostly to make sure I didn't\nscrew anything up) and got similar results.\n\nI agree that 10,000 packs is ridiculous, but we do see it (and worse)\noccasionally from people pushing in a loop before our scheduled\nmaintenance kicks in. And it's quadratic, so if you hit 30k packs, it's\nanother factor of 9 worse. It makes even diagnosing the repository\npretty painful. :)\n\nAlso a fun fact: Linux actually has a limit on the number of\nsimultaneous mmaps that a process can have, which defaults to ~64k. But\nif you have if you have 32k packs, then we'll map both the packs and the\nidx files. Plus whatever you need for mapping the binary, libraries,\netc, plus any maps opened by malloc() for large requests.\n\nI have occasionally run into this trying to repack some very\nout-of-control cases (the magic fix is to double the limit with `sysctl\n-w vm.max_map_count=131060`, if you are curious). I also wondered if\nthis might be made worse by the recent change to drop\nrelease_pack_memory(). But I ran into it even before that change,\nbecause zlib calls malloc() directly. We're also pretty aggressive about\ndying when mmap() returns an error (rather than closing packs and trying\nagain).\n\nI think Git _could_ be handle this more gracefully by just trying to\nkeep fewer packs open at one time (the way we similarly try not to use\nup all of the file descriptors). But I have a hard time caring too much,\nsince it's such a ridiculous situation in the first place. Bumping the\nlimits is an easy operational fix.\n\n-Peff\n"},{"id":"387468","messageId":"20191203221819.GB28419@sigill.intra.peff.net","threadId":"52364","inReplyTo":"20191203173334.GA20027@owl.colinstolley.com","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-03T22:18:19Z","receivedAt":"2019-12-03T22:18:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 03, 2019 at 11:33:34AM -0600, Colin Stolley wrote:\n\n> Junio C Hamano wrote:\n> \n> > Let me locally squash your fix in and credit you with helped-by\n> > footer in the amended log message. Strictly speaking, this may\n> \n> I'm also happy to provide a khash version if that is still desired,\n> perhaps as a separate patch.\n\nPersonally I'd be OK with it as-is, or with a conversion to khash (as I\nsaid earlier, I prefer khash myself, but it's not like there aren't tons\nof other hashmap.c users in the code).\n\n-Peff\n"},{"id":"387473","messageId":"20191204042332.GG214771@google.com","threadId":"52364","inReplyTo":"20191203221730.GA28419@sigill.intra.peff.net","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2019-12-04T04:23:32Z","receivedAt":"2019-12-04T04:23:40Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jeff King wrote:\n\n> I agree that 10,000 packs is ridiculous, but we do see it (and worse)\n> occasionally from people pushing in a loop before our scheduled\n> maintenance kicks in.\n\nOn that subject: one thing Martin Fick (cc-ed) has suggested is moving\nmore of the garbage collection work \"inline\" into the push path. That\nis, instead of letting someone push 10,000 packs in a loop, build\nconcatenated packs (\"exponential rollup\") in the push path and don't\nreturn success and commit the packs into the object store until we're\ndone. That way a reasonably small amortized cost is paid up front by\nthe pusher instead of later by everyone.\n\nMidx changes things a little: it might make sense to build\nconcatenated idxes instead of packs, which would still avoid the same\nquadratic behavior.\n\nJust a random thought,\nJonathan\n"},{"id":"387499","messageId":"xmqqsgm03qkk.fsf@gitster-ct.c.googlers.com","threadId":"52364","inReplyTo":"20191203221819.GB28419@sigill.intra.peff.net","subject":"Re: [PATCH] packfile.c: speed up loading lots of packfiles.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-12-04T18:15:23Z","receivedAt":"2019-12-04T18:15:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Dec 03, 2019 at 11:33:34AM -0600, Colin Stolley wrote:\n>\n>> Junio C Hamano wrote:\n>> \n>> > Let me locally squash your fix in and credit you with helped-by\n>> > footer in the amended log message. Strictly speaking, this may\n>> \n>> I'm also happy to provide a khash version if that is still desired,\n>> perhaps as a separate patch.\n>\n> Personally I'd be OK with it as-is, or with a conversion to khash (as I\n> said earlier, I prefer khash myself, but it's not like there aren't tons\n> of other hashmap.c users in the code).\n\nExactly me feeling. Thanks.\n"}]}