{"thread":{"id":"53163","subject":"[PATCH] fast-import: replace custom hash with hashmap.c","startedAt":"2020-04-03T12:15:11Z","lastAt":"2020-04-07T18:37:30Z","messageCount":8,"participants":["Jeff King","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"394659","messageId":"20200403121508.GA638328@coredump.intra.peff.net","threadId":"53163","inReplyTo":null,"subject":"[PATCH] fast-import: replace custom hash with hashmap.c","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-04-03T12:15:08Z","receivedAt":"2020-04-03T12:15:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We use a custom hash in fast-import to store the set of objects we've\nimported so far. It has a fixed set of 2^16 buckets and chains any\ncollisions with a linked list. As the number of objects grows larger\nthan that, the load factor increases and we degrade to O(n) lookups and\nO(n^2) insertions.\n\nWe can scale better by using our hashmap.c implementation, which will\nresize the bucket count as we grow. This does incur an extra memory cost\nof 8 bytes per object, as hashmap stores the integer hash value for each\nentry in its hashmap_entry struct (which we really don't care about\nhere, because we're just reusing the embedded object hash). But I think\nthe numbers below justify this (and our per-object memory cost is\nalready much higher).\n\nI also looked at using khash, but it seemed to perform slightly worse\nthan hashmap at all sizes, and worse even than the existing code for\nsmall sizes. It's also awkward to use here, because we want to look up a\n\"struct object_entry\" from a \"struct object_id\", and it doesn't handle\nmismatched keys as well. Making a mapping of object_id to object_entry\nwould be more natural, but that would require pulling the embedded oid\nout of the object_entry or incurring an extra 32 bytes per object.\n\nIn a synthetic test creating as many cheap, tiny objects as possible\n\n perl -e '\n my $bits = shift;\n my $nr = 2**$bits;\n\n for (my $i = 0; $i < $nr; $i++) {\n print \"blob\\n\";\n print \"data 4\\n\";\n print pack(\"N\", $i);\n }\n ' $bits | git fast-import\n\nI got these results:\n\n nr_objects master khash hashmap\n 2^20 0m4.317s 0m5.109s 0m3.890s\n 2^21 0m10.204s 0m9.702s 0m7.933s\n 2^22 0m27.159s 0m17.911s 0m16.751s\n 2^23 1m19.038s 0m35.080s 0m31.963s\n 2^24 4m18.766s 1m10.233s 1m6.793s\n\nwhich points to hashmap as the winner. We didn't have any perf tests for\nfast-export or fast-import, so I added one as a more real-world case.\nIt uses an export without blobs since that's significantly cheaper than\na full one, but still is an interesting case people might use (e.g., for\nrewriting history). It will emphasize this change in some ways (as a\npercentage we spend more time making objects and less shuffling blob\nbytes around) and less in others (the total object count is lower).\n\nHere are the results for linux.git:\n\n Test HEAD^ HEAD\n ----------------------------------------------------------------------------\n 9300.1: export (no-blobs) 67.64(66.96+0.67) 67.81(67.06+0.75) +0.3%\n 9300.2: import (no-blobs) 284.04(283.34+0.69) 198.09(196.01+0.92) -30.3%\n\nIt only has ~5.2M commits and trees, so this is a larger effect than I\nexpected (the 2^23 case above only improved by 50s or so, but here we\ngained almost 90s). This is probably due to actually performing more\nobject lookups in a real import with trees and commits, as opposed to\njust dumping a bunch of blobs into a pack.\n\nSigned-off-by: Jeff King \n---\n fast-import.c | 62 +++++++++++++++++++-----------\n t/perf/p9300-fast-import-export.sh | 23 +++++++++++\n 2 files changed, 62 insertions(+), 23 deletions(-)\n create mode 100755 t/perf/p9300-fast-import-export.sh\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 202dda11a6..0ef6defc10 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -39,12 +39,28 @@\n \n struct object_entry {\n \tstruct pack_idx_entry idx;\n-\tstruct object_entry *next;\n+\tstruct hashmap_entry ent;\n \tuint32_t type : TYPE_BITS,\n \t\tpack_id : PACK_ID_BITS,\n \t\tdepth : DEPTH_BITS;\n };\n \n+static int object_entry_hashcmp(const void *map_data,\n+\t\t\t\tconst struct hashmap_entry *eptr,\n+\t\t\t\tconst struct hashmap_entry *entry_or_key,\n+\t\t\t\tconst void *keydata)\n+{\n+\tconst struct object_id *oid = keydata;\n+\tconst struct object_entry *e1, *e2;\n+\n+\te1 = container_of(eptr, const struct object_entry, ent);\n+\tif (oid)\n+\t\treturn oidcmp(&e1->idx.oid, oid);\n+\n+\te2 = container_of(entry_or_key, const struct object_entry, ent);\n+\treturn oidcmp(&e1->idx.oid, &e2->idx.oid);\n+}\n+\n struct object_entry_pool {\n \tstruct object_entry_pool *next_pool;\n \tstruct object_entry *next_free;\n@@ -178,7 +194,7 @@ static off_t pack_size;\n /* Table of objects we've written. */\n static unsigned int object_entry_alloc = 5000;\n static struct object_entry_pool *blocks;\n-static struct object_entry *object_table[1 << 16];\n+static struct hashmap object_table;\n static struct mark_set *marks;\n static const char *export_marks_file;\n static const char *import_marks_file;\n@@ -455,44 +471,42 @@ static struct object_entry *new_object(struct object_id *oid)\n \n static struct object_entry *find_object(struct object_id *oid)\n {\n-\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n-\tstruct object_entry *e;\n-\tfor (e = object_table[h]; e; e = e->next)\n-\t\tif (oideq(oid, &e->idx.oid))\n-\t\t\treturn e;\n+\tstruct hashmap_entry lookup_entry, *e;\n+\n+\thashmap_entry_init(&lookup_entry, oidhash(oid));\n+\te = hashmap_get(&object_table, &lookup_entry, oid);\n+\tif (e)\n+\t\treturn container_of(e, struct object_entry, ent);\n \treturn NULL;\n }\n \n static struct object_entry *insert_object(struct object_id *oid)\n {\n-\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n-\tstruct object_entry *e = object_table[h];\n+\tstruct object_entry *e;\n+\tstruct hashmap_entry lookup_entry, *hashent;\n \n-\twhile (e) {\n-\t\tif (oideq(oid, &e->idx.oid))\n-\t\t\treturn e;\n-\t\te = e->next;\n-\t}\n+\thashmap_entry_init(&lookup_entry, oidhash(oid));\n+\thashent = hashmap_get(&object_table, &lookup_entry, oid);\n+\tif (hashent)\n+\t\treturn container_of(hashent, struct object_entry, ent);\n \n \te = new_object(oid);\n-\te->next = object_table[h];\n \te->idx.offset = 0;\n-\tobject_table[h] = e;\n+\te->ent.hash = lookup_entry.hash;\n+\thashmap_add(&object_table, &e->ent);\n \treturn e;\n }\n \n static void invalidate_pack_id(unsigned int id)\n {\n-\tunsigned int h;\n \tunsigned long lu;\n \tstruct tag *t;\n+\tstruct hashmap_iter iter;\n+\tstruct object_entry *e;\n \n-\tfor (h = 0; h < ARRAY_SIZE(object_table); h++) {\n-\t\tstruct object_entry *e;\n-\n-\t\tfor (e = object_table[h]; e; e = e->next)\n-\t\t\tif (e->pack_id == id)\n-\t\t\t\te->pack_id = MAX_PACK_ID;\n+\thashmap_for_each_entry(&object_table, &iter, e, ent) {\n+\t\tif (e->pack_id == id)\n+\t\t\te->pack_id = MAX_PACK_ID;\n \t}\n \n \tfor (lu = 0; lu < branch_table_sz; lu++) {\n@@ -3511,6 +3525,8 @@ int cmd_main(int argc, const char **argv)\n \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n \tmarks = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));\n \n+\thashmap_init(&object_table, object_entry_hashcmp, NULL, 0);\n+\n \t/*\n \t * We don't parse most options until after we've seen the set of\n \t * \"feature\" lines at the start of the stream (which allows the command\ndiff --git a/t/perf/p9300-fast-import-export.sh b/t/perf/p9300-fast-import-export.sh\nnew file mode 100755\nindex 0000000000..c3c743d04a\n--- /dev/null\n+++ b/t/perf/p9300-fast-import-export.sh\n@@ -0,0 +1,23 @@\n+#!/bin/sh\n+\n+test_description='test fast-import and fast-export performance'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+# Use --no-data here to produce a vastly smaller export file.\n+# This is much cheaper to work with but should still exercise\n+# fast-import pretty well (we'll still process all commits and\n+# trees, which account for 60% or more of objects in most repos).\n+#\n+# Use --rencode to avoid the default of aborting on non-utf8 commits,\n+# which lets this test run against a wider variety of sample repos.\n+test_perf 'export (no-blobs)' '\n+\tgit fast-export --reencode=yes --no-data HEAD >export\n+'\n+\n+test_perf 'import (no-blobs)' '\n+\tgit fast-import --force We use a custom hash in fast-import to store the set of objects we've\n> imported so far. It has a fixed set of 2^16 buckets and chains any\n> collisions with a linked list. As the number of objects grows larger\n> than that, the load factor increases and we degrade to O(n) lookups and\n> O(n^2) insertions.\n>\n> We can scale better by using our hashmap.c implementation, which will\n> resize the bucket count as we grow. This does incur an extra memory cost\n> of 8 bytes per object, as hashmap stores the integer hash value for each\n> entry in its hashmap_entry struct (which we really don't care about\n> here, because we're just reusing the embedded object hash). But I think\n> the numbers below justify this (and our per-object memory cost is\n> already much higher).\n>\n> I also looked at using khash, but it seemed to perform slightly worse\n> than hashmap at all sizes, and worse even than the existing code for\n> small sizes. It's also awkward to use here, because we want to look up a\n> \"struct object_entry\" from a \"struct object_id\", and it doesn't handle\n> mismatched keys as well. Making a mapping of object_id to object_entry\n> would be more natural, but that would require pulling the embedded oid\n> out of the object_entry or incurring an extra 32 bytes per object.\n>\n> In a synthetic test creating as many cheap, tiny objects as possible\n>\n> perl -e '\n> my $bits = shift;\n> my $nr = 2**$bits;\n>\n> for (my $i = 0; $i < $nr; $i++) {\n> print \"blob\\n\";\n> print \"data 4\\n\";\n> print pack(\"N\", $i);\n> }\n> ' $bits | git fast-import\n>\n> I got these results:\n>\n> nr_objects master khash hashmap\n> 2^20 0m4.317s 0m5.109s 0m3.890s\n> 2^21 0m10.204s 0m9.702s 0m7.933s\n> 2^22 0m27.159s 0m17.911s 0m16.751s\n> 2^23 1m19.038s 0m35.080s 0m31.963s\n> 2^24 4m18.766s 1m10.233s 1m6.793s\n\nI get similar numbers.\n\n>\n> which points to hashmap as the winner. We didn't have any perf tests for\n> fast-export or fast-import, so I added one as a more real-world case.\n> It uses an export without blobs since that's significantly cheaper than\n> a full one, but still is an interesting case people might use (e.g., for\n> rewriting history). It will emphasize this change in some ways (as a\n> percentage we spend more time making objects and less shuffling blob\n> bytes around) and less in others (the total object count is lower).\n>\n> Here are the results for linux.git:\n>\n> Test HEAD^ HEAD\n> ----------------------------------------------------------------------------\n> 9300.1: export (no-blobs) 67.64(66.96+0.67) 67.81(67.06+0.75) +0.3%\n> 9300.2: import (no-blobs) 284.04(283.34+0.69) 198.09(196.01+0.92) -30.3%\n\nMy numbers look a bit different for this, not sure why:\n\nTest origin/master HEAD\n---------------------------------------------------------------------------\n9300.1: export (no-blobs) 69.36(66.44+1.56) 67.89(66.07+1.56) -2.1%\n9300.2: import (no-blobs) 295.10(293.83+1.19) 283.83(282.91+0.91) -3.8%\n\nThey are still in favor of the patch, just not as strongly as yours.\n\n>\n> It only has ~5.2M commits and trees, so this is a larger effect than I\n> expected (the 2^23 case above only improved by 50s or so, but here we\n> gained almost 90s). This is probably due to actually performing more\n> object lookups in a real import with trees and commits, as opposed to\n> just dumping a bunch of blobs into a pack.\n>\n> Signed-off-by: Jeff King \n> ---\n> fast-import.c | 62 +++++++++++++++++++-----------\n> t/perf/p9300-fast-import-export.sh | 23 +++++++++++\n> 2 files changed, 62 insertions(+), 23 deletions(-)\n> create mode 100755 t/perf/p9300-fast-import-export.sh\n>\n\nI have to warn you up front: I'm not familiar with hashmap or\nfast-import, so I'll focus on stylistic topics -- bikeshedding. The\nactual change looks reasonable to me overall and the performance is\nconvincing.\n\n> diff --git a/fast-import.c b/fast-import.c\n> index 202dda11a6..0ef6defc10 100644\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -39,12 +39,28 @@\n>\n> struct object_entry {\n> \tstruct pack_idx_entry idx;\n> -\tstruct object_entry *next;\n> +\tstruct hashmap_entry ent;\n> \tuint32_t type : TYPE_BITS,\n> \t\tpack_id : PACK_ID_BITS,\n> \t\tdepth : DEPTH_BITS;\n> };\n>\n> +static int object_entry_hashcmp(const void *map_data,\n> +\t\t\t\tconst struct hashmap_entry *eptr,\n> +\t\t\t\tconst struct hashmap_entry *entry_or_key,\n> +\t\t\t\tconst void *keydata)\n> +{\n> +\tconst struct object_id *oid = keydata;\n> +\tconst struct object_entry *e1, *e2;\n> +\n> +\te1 = container_of(eptr, const struct object_entry, ent);\n> +\tif (oid)\n> +\t\treturn oidcmp(&e1->idx.oid, oid);\n> +\n> +\te2 = container_of(entry_or_key, const struct object_entry, ent);\n> +\treturn oidcmp(&e1->idx.oid, &e2->idx.oid);\n\nOther hashmap users express this more tersely, similar to this:\n\n\tconst struct object_entry *e1, *e2;\n\n\te1 = container_of(eptr, const struct object_entry, ent);\n\te2 = container_of(entry_or_key, const struct object_entry, ent);\n\treturn oidcmp(&e1->idx.oid, keydata ? keydata : &e2->idx.oid);\n\n> +}\n> +\n> struct object_entry_pool {\n> \tstruct object_entry_pool *next_pool;\n> \tstruct object_entry *next_free;\n> @@ -178,7 +194,7 @@ static off_t pack_size;\n> /* Table of objects we've written. */\n> static unsigned int object_entry_alloc = 5000;\n> static struct object_entry_pool *blocks;\n> -static struct object_entry *object_table[1 << 16];\n> +static struct hashmap object_table;\n> static struct mark_set *marks;\n> static const char *export_marks_file;\n> static const char *import_marks_file;\n> @@ -455,44 +471,42 @@ static struct object_entry *new_object(struct object_id *oid)\n>\n> static struct object_entry *find_object(struct object_id *oid)\n> {\n> -\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n> -\tstruct object_entry *e;\n> -\tfor (e = object_table[h]; e; e = e->next)\n> -\t\tif (oideq(oid, &e->idx.oid))\n> -\t\t\treturn e;\n> +\tstruct hashmap_entry lookup_entry, *e;\n> +\n> +\thashmap_entry_init(&lookup_entry, oidhash(oid));\n> +\te = hashmap_get(&object_table, &lookup_entry, oid);\n> +\tif (e)\n> +\t\treturn container_of(e, struct object_entry, ent);\n\n(Worth repeating:) No casting trick, yay!\n\n> \treturn NULL;\n> }\n>\n> static struct object_entry *insert_object(struct object_id *oid)\n> {\n> -\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n> -\tstruct object_entry *e = object_table[h];\n> +\tstruct object_entry *e;\n> +\tstruct hashmap_entry lookup_entry, *hashent;\n>\n> -\twhile (e) {\n> -\t\tif (oideq(oid, &e->idx.oid))\n> -\t\t\treturn e;\n> -\t\te = e->next;\n> -\t}\n> +\thashmap_entry_init(&lookup_entry, oidhash(oid));\n> +\thashent = hashmap_get(&object_table, &lookup_entry, oid);\n> +\tif (hashent)\n> +\t\treturn container_of(hashent, struct object_entry, ent);\n\nThat duplicates find_object()...\n\n>\n> \te = new_object(oid);\n> -\te->next = object_table[h];\n> \te->idx.offset = 0;\n> -\tobject_table[h] = e;\n> +\te->ent.hash = lookup_entry.hash;\n\n... except for this part. Would it make sense to replace this line with\na call to hashmap_entry_init()? Seems cleaner to me. It would look\nlike this:\n\n\tstruct object_entry *e = find_object(oid);\n\n\tif (e)\n\t\treturn e;\n\n\te = new_object(oid);\n\te->idx.offset = 0;\n\thashmap_entry_init(&e->ent, oidhash(oid));\n\thashmap_add(&object_table, &e->ent);\n\treturn e;\n\n> +\thashmap_add(&object_table, &e->ent);\n> \treturn e;\n> }\n>\n> static void invalidate_pack_id(unsigned int id)\n> {\n> -\tunsigned int h;\n> \tunsigned long lu;\n> \tstruct tag *t;\n> +\tstruct hashmap_iter iter;\n> +\tstruct object_entry *e;\n>\n> -\tfor (h = 0; h < ARRAY_SIZE(object_table); h++) {\n> -\t\tstruct object_entry *e;\n> -\n> -\t\tfor (e = object_table[h]; e; e = e->next)\n> -\t\t\tif (e->pack_id == id)\n> -\t\t\t\te->pack_id = MAX_PACK_ID;\n> +\thashmap_for_each_entry(&object_table, &iter, e, ent) {\n> +\t\tif (e->pack_id == id)\n> +\t\t\te->pack_id = MAX_PACK_ID;\n> \t}\n>\n> \tfor (lu = 0; lu < branch_table_sz; lu++) {\n> @@ -3511,6 +3525,8 @@ int cmd_main(int argc, const char **argv)\n> \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n> \tmarks = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));\n>\n> +\thashmap_init(&object_table, object_entry_hashcmp, NULL, 0);\n> +\n> \t/*\n> \t * We don't parse most options until after we've seen the set of\n> \t * \"feature\" lines at the start of the stream (which allows the command\n> diff --git a/t/perf/p9300-fast-import-export.sh b/t/perf/p9300-fast-import-export.sh\n> new file mode 100755\n> index 0000000000..c3c743d04a\n> --- /dev/null\n> +++ b/t/perf/p9300-fast-import-export.sh\n> @@ -0,0 +1,23 @@\n> +#!/bin/sh\n> +\n> +test_description='test fast-import and fast-export performance'\n> +. ./perf-lib.sh\n> +\n> +test_perf_default_repo\n> +\n> +# Use --no-data here to produce a vastly smaller export file.\n> +# This is much cheaper to work with but should still exercise\n> +# fast-import pretty well (we'll still process all commits and\n> +# trees, which account for 60% or more of objects in most repos).\n> +#\n> +# Use --rencode to avoid the default of aborting on non-utf8 commits,\n> +# which lets this test run against a wider variety of sample repos.\n> +test_perf 'export (no-blobs)' '\n> +\tgit fast-export --reencode=yes --no-data HEAD >export\n> +'\n> +\n> +test_perf 'import (no-blobs)' '\n> +\tgit fast-import --force +'\n> +\n> +test_done\n>\n"},{"id":"394797","messageId":"20200405185951.GA1309762@coredump.intra.peff.net","threadId":"53163","inReplyTo":"6926f6fe-2e5c-bcbc-fd0a-5b9a70eed06c@web.de","subject":"Re: [PATCH] fast-import: replace custom hash with hashmap.c","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-04-05T18:59:51Z","receivedAt":"2020-04-05T19:00:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 03, 2020 at 08:53:30PM +0200, René Scharfe wrote:\n\n> > Here are the results for linux.git:\n> >\n> > Test HEAD^ HEAD\n> > ----------------------------------------------------------------------------\n> > 9300.1: export (no-blobs) 67.64(66.96+0.67) 67.81(67.06+0.75) +0.3%\n> > 9300.2: import (no-blobs) 284.04(283.34+0.69) 198.09(196.01+0.92) -30.3%\n> \n> My numbers look a bit different for this, not sure why:\n> \n> Test origin/master HEAD\n> ---------------------------------------------------------------------------\n> 9300.1: export (no-blobs) 69.36(66.44+1.56) 67.89(66.07+1.56) -2.1%\n> 9300.2: import (no-blobs) 295.10(293.83+1.19) 283.83(282.91+0.91) -3.8%\n> \n> They are still in favor of the patch, just not as strongly as yours.\n\nInteresting. I re-ran mine just to double check, and got:\n\nTest HEAD^ HEAD \n----------------------------------------------------------------------------\n9300.1: export (no-blobs) 63.11(62.31+0.79) 62.00(61.21+0.79) -1.8% \n9300.2: import (no-blobs) 261.79(261.06+0.72) 188.55(187.87+0.66) -28.0%\n\n(for some reason my whole machine is faster today; maybe I had closed\nslack).\n\nThis is on a fresh-ish clone of linux.git.\n\n> > +\te1 = container_of(eptr, const struct object_entry, ent);\n> > +\tif (oid)\n> > +\t\treturn oidcmp(&e1->idx.oid, oid);\n> > +\n> > +\te2 = container_of(entry_or_key, const struct object_entry, ent);\n> > +\treturn oidcmp(&e1->idx.oid, &e2->idx.oid);\n> \n> Other hashmap users express this more tersely, similar to this:\n> \n> \tconst struct object_entry *e1, *e2;\n> \n> \te1 = container_of(eptr, const struct object_entry, ent);\n> \te2 = container_of(entry_or_key, const struct object_entry, ent);\n> \treturn oidcmp(&e1->idx.oid, keydata ? keydata : &e2->idx.oid);\n\nI wasn't sure if we'd ever see entry_or_key as NULL, in which case the\nsecond container_of() would be undefined behavior. There's a\ncontainer_of_or_null() for this, but it seemed simpler to just avoid the\nderef entirely if we didn't need it.\n\nI think in practice we won't ever pass NULL, though. Even a\nhashmap_get() needs to pass in a hashmap_entry with the hash value in\nit. Though I think that's technically _also_ undefined behavior. If I\nhave a struct where the entry is not at the beginning, like:\n\n struct foo {\n const char *bar;\n struct hashmap_entry ent;\n };\n\nthen:\n\n e2 = container_of(ptr_to_entry, struct foo, ent);\n\nis going to form a pointer at 8 bytes before ptr_to_entry. If it really\nis a \"struct hashmap_entry\" on the stack, then it's pointing at garbage.\n\nWe don't dereference it, so it's likely fine in practice, but even\ncomputing such a pointer does violate the standard.\n\n> > +\thashmap_entry_init(&lookup_entry, oidhash(oid));\n> > +\thashent = hashmap_get(&object_table, &lookup_entry, oid);\n> > +\tif (hashent)\n> > +\t\treturn container_of(hashent, struct object_entry, ent);\n> \n> That duplicates find_object()...\n\nYes. This is how most hashmap users do it. It's only a few lines, and\nsharing without extra work would mean passing the hash value around\n(otherwise we'd have to recompute it again), which is awkward.\n\nThough in our case oidhash() is cheap enough that perhaps it's not worth\nworrying about?\n\n> > \te = new_object(oid);\n> > -\te->next = object_table[h];\n> > \te->idx.offset = 0;\n> > -\tobject_table[h] = e;\n> > +\te->ent.hash = lookup_entry.hash;\n> \n> ... except for this part. Would it make sense to replace this line with\n> a call to hashmap_entry_init()? Seems cleaner to me. It would look\n> like this:\n> \tstruct object_entry *e = find_object(oid);\n> \n> \tif (e)\n> \t\treturn e;\n> \n> \te = new_object(oid);\n> \te->idx.offset = 0;\n> \thashmap_entry_init(&e->ent, oidhash(oid));\n> \thashmap_add(&object_table, &e->ent);\n> \treturn e;\n\nRight, that calls oidhash() again. If we're OK with that, I agree it's a\nbit shorter and not any more awkward. I do worry slightly that it sets a\nbad example, though (you wouldn't want to repeat a strhash(), for\nexample).\n\n-Peff\n"},{"id":"394872","messageId":"020726d4-5a5c-e751-2824-d05004823326@web.de","threadId":"53163","inReplyTo":"20200405185951.GA1309762@coredump.intra.peff.net","subject":"Re: [PATCH] fast-import: replace custom hash with hashmap.c","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-04-06T18:07:45Z","receivedAt":"2020-04-06T18:08:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.20 um 20:59 schrieb Jeff King:\n> On Fri, Apr 03, 2020 at 08:53:30PM +0200, René Scharfe wrote:\n>\n>>> Here are the results for linux.git:\n>>>\n>>> Test HEAD^ HEAD\n>>> ----------------------------------------------------------------------------\n>>> 9300.1: export (no-blobs) 67.64(66.96+0.67) 67.81(67.06+0.75) +0.3%\n>>> 9300.2: import (no-blobs) 284.04(283.34+0.69) 198.09(196.01+0.92) -30.3%\n>>\n>> My numbers look a bit different for this, not sure why:\n>>\n>> Test origin/master HEAD\n>> ---------------------------------------------------------------------------\n>> 9300.1: export (no-blobs) 69.36(66.44+1.56) 67.89(66.07+1.56) -2.1%\n>> 9300.2: import (no-blobs) 295.10(293.83+1.19) 283.83(282.91+0.91) -3.8%\n>>\n>> They are still in favor of the patch, just not as strongly as yours.\n>\n> Interesting. I re-ran mine just to double check, and got:\n>\n> Test HEAD^ HEAD\n> ----------------------------------------------------------------------------\n> 9300.1: export (no-blobs) 63.11(62.31+0.79) 62.00(61.21+0.79) -1.8%\n> 9300.2: import (no-blobs) 261.79(261.06+0.72) 188.55(187.87+0.66) -28.0%\n>\n> (for some reason my whole machine is faster today; maybe I had closed\n> slack).\n>\n> This is on a fresh-ish clone of linux.git.\n\nA second run today reported:\n\nTest origin/master HEAD\n---------------------------------------------------------------------------\n9300.1: export (no-blobs) 61.58(59.93+1.40) 60.63(59.35+1.22) -1.5%\n9300.2: import (no-blobs) 239.64(239.00+0.63) 246.02(245.18+0.82) +2.7%\n\ngit describe says v5.4-3890-g86fd3e9df543 in that repo.\n\nDunno. My PC has thermal issues and stressing it for half an hour straight\nmay cause it to throttle?\n\nWith Git's own repo I just got this:\n\nTest origin/master HEAD\n-----------------------------------------------------------------------\n9300.1: export (no-blobs) 2.58(2.45+0.05) 2.81(2.75+0.05) +8.9%\n9300.2: import (no-blobs) 10.41(10.37+0.03) 10.75(10.72+0.02) +3.3%\n\n>\n>>> +\te1 = container_of(eptr, const struct object_entry, ent);\n>>> +\tif (oid)\n>>> +\t\treturn oidcmp(&e1->idx.oid, oid);\n>>> +\n>>> +\te2 = container_of(entry_or_key, const struct object_entry, ent);\n>>> +\treturn oidcmp(&e1->idx.oid, &e2->idx.oid);\n>>\n>> Other hashmap users express this more tersely, similar to this:\n>>\n>> \tconst struct object_entry *e1, *e2;\n>>\n>> \te1 = container_of(eptr, const struct object_entry, ent);\n>> \te2 = container_of(entry_or_key, const struct object_entry, ent);\n>> \treturn oidcmp(&e1->idx.oid, keydata ? keydata : &e2->idx.oid);\n>\n> I wasn't sure if we'd ever see entry_or_key as NULL, in which case the\n> second container_of() would be undefined behavior. There's a\n> container_of_or_null() for this, but it seemed simpler to just avoid the\n> deref entirely if we didn't need it.\n\nOK. The other users might have the same issue then, though.\n\n> I think in practice we won't ever pass NULL, though. Even a\n> hashmap_get() needs to pass in a hashmap_entry with the hash value in\n> it. Though I think that's technically _also_ undefined behavior. If I\n> have a struct where the entry is not at the beginning, like:\n>\n> struct foo {\n> const char *bar;\n> struct hashmap_entry ent;\n> };\n>\n> then:\n>\n> e2 = container_of(ptr_to_entry, struct foo, ent);\n>\n> is going to form a pointer at 8 bytes before ptr_to_entry. If it really\n> is a \"struct hashmap_entry\" on the stack, then it's pointing at garbage.\n>\n> We don't dereference it, so it's likely fine in practice, but even\n> computing such a pointer does violate the standard.\n\nReally? If ptr_to_entry was NULL then any pointer arithmetic on it would\nbe bad. If it points to a bare hashmap_entry and we lied to container_of\nby telling it that it's embedded in some other struct then that would be\nbad as well. But if there actually is a surrounding struct of the\nspecified type then the resulting pointer must surely be valid, no matter\nif the object it points to was initialized? Do you have the relevant\nchapter and verse handy?\n\n>\n>>> +\thashmap_entry_init(&lookup_entry, oidhash(oid));\n>>> +\thashent = hashmap_get(&object_table, &lookup_entry, oid);\n>>> +\tif (hashent)\n>>> +\t\treturn container_of(hashent, struct object_entry, ent);\n>>\n>> That duplicates find_object()...\n>\n> Yes. This is how most hashmap users do it. It's only a few lines, and\n> sharing without extra work would mean passing the hash value around\n> (otherwise we'd have to recompute it again), which is awkward.\n\nI find touching hashmap_entry members directly more awkward.\n\nCompilers likely inline find_object() here, so the text size and\nperformance should be about the same.\n\n> Though in our case oidhash() is cheap enough that perhaps it's not worth\n> worrying about?\n\nProbably, but I didn't measure. My system is quite noisy..\n\n>\n>>> \te = new_object(oid);\n>>> -\te->next = object_table[h];\n>>> \te->idx.offset = 0;\n>>> -\tobject_table[h] = e;\n>>> +\te->ent.hash = lookup_entry.hash;\n>>\n>> ... except for this part. Would it make sense to replace this line with\n>> a call to hashmap_entry_init()? Seems cleaner to me. It would look\n>> like this:\n>> \tstruct object_entry *e = find_object(oid);\n>>\n>> \tif (e)\n>> \t\treturn e;\n>>\n>> \te = new_object(oid);\n>> \te->idx.offset = 0;\n>> \thashmap_entry_init(&e->ent, oidhash(oid));\n>> \thashmap_add(&object_table, &e->ent);\n>> \treturn e;\n>\n> Right, that calls oidhash() again. If we're OK with that, I agree it's a\n> bit shorter and not any more awkward. I do worry slightly that it sets a\n> bad example, though (you wouldn't want tusing only the API to o repeat a strhash(), for\n> example).\n\nStuffing the oidhash() result into a variable and using it twice with\nhashmap_entry_init() would work as well. This would make the reason for\nthe duplicate find_object() code obvious, while keeping struct\nhashmap_entry opaque.\n\nRené\n"},{"id":"394876","messageId":"20200406183542.GA23753@coredump.intra.peff.net","threadId":"53163","inReplyTo":"020726d4-5a5c-e751-2824-d05004823326@web.de","subject":"Re: [PATCH] fast-import: replace custom hash with hashmap.c","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-04-06T18:35:42Z","receivedAt":"2020-04-06T18:35:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 06, 2020 at 08:07:45PM +0200, René Scharfe wrote:\n\n> > Interesting. I re-ran mine just to double check, and got:\n> [...]\n> A second run today reported:\n> \n> Test origin/master HEAD\n> ---------------------------------------------------------------------------\n> 9300.1: export (no-blobs) 61.58(59.93+1.40) 60.63(59.35+1.22) -1.5%\n> 9300.2: import (no-blobs) 239.64(239.00+0.63) 246.02(245.18+0.82) +2.7%\n> \n> git describe says v5.4-3890-g86fd3e9df543 in that repo.\n\nI'm on v5.6-rc7-188-g1b649e0bcae7, but I can't imagine it makes a big\ndifference.\n\n> Dunno. My PC has thermal issues and stressing it for half an hour straight\n> may cause it to throttle?\n\nYeah. I wonder what the variance is between the 3 runs (assuming you're\nusing ./run and doing 3). I.e., is one run in the first set much faster\nthan the others, and we pick it as best-of-3.\n\n> With Git's own repo I just got this:\n> \n> Test origin/master HEAD\n> -----------------------------------------------------------------------\n> 9300.1: export (no-blobs) 2.58(2.45+0.05) 2.81(2.75+0.05) +8.9%\n> 9300.2: import (no-blobs) 10.41(10.37+0.03) 10.75(10.72+0.02) +3.3%\n\nI get similar numbers here. But I wouldn't expect much. We only have\n~160k commits+trees in git.git, so the average chain length is ~2.5.\n\n> > I think in practice we won't ever pass NULL, though. Even a\n> > hashmap_get() needs to pass in a hashmap_entry with the hash value in\n> > it. Though I think that's technically _also_ undefined behavior. If I\n> > have a struct where the entry is not at the beginning, like:\n> >\n> > struct foo {\n> > const char *bar;\n> > struct hashmap_entry ent;\n> > };\n> >\n> > then:\n> >\n> > e2 = container_of(ptr_to_entry, struct foo, ent);\n> >\n> > is going to form a pointer at 8 bytes before ptr_to_entry. If it really\n> > is a \"struct hashmap_entry\" on the stack, then it's pointing at garbage.\n> >\n> > We don't dereference it, so it's likely fine in practice, but even\n> > computing such a pointer does violate the standard.\n> \n> Really? If ptr_to_entry was NULL then any pointer arithmetic on it would\n> be bad. If it points to a bare hashmap_entry and we lied to container_of\n> by telling it that it's embedded in some other struct then that would be\n> bad as well. But if there actually is a surrounding struct of the\n> specified type then the resulting pointer must surely be valid, no matter\n> if the object it points to was initialized? Do you have the relevant\n> chapter and verse handy?\n\nPointing to uninitialized bits is fine according to the standard (and I\nthink that's what you're asking about for chapter and verse). But we\nreally do lie to container_of(). See remote.c, for example. In\nmake_remote(), we call hashmap_get() with a pointer to lookup_entry,\nwhich is a bare \"struct hashmap_entry\". That should end up in\nremotes_hash_cmp(), which unconditionally computes a pointer to a\n\"struct remote\".\n\nNow the hashmap_entry there is at the beginning of the struct, so the\noffset is 0 and the two pointers are the same. So while the pointer's\ntype is incorrect, we didn't compute an invalid pointer value. And\ntraditionally the hashmap code required that it be at the front of the\ncontaining struct, but that was loosened recently (and container_of\nintroduced) in 5efabc7ed9 (Merge branch 'ew/hashmap', 2019-10-15).\n\nAnd grepping around, I don't see any cases where it's _not_ at the\nbeginning. So perhaps this is a problem waiting to bite us.\n\n> Stuffing the oidhash() result into a variable and using it twice with\n> hashmap_entry_init() would work as well. This would make the reason for\n> the duplicate find_object() code obvious, while keeping struct\n> hashmap_entry opaque.\n\nI'd prefer not to use a separate variable, as that requires giving it a\ntype. Perhaps:\n\n hashmap_entry_init(&e->ent, lookup_entry.hash);\n\nwhich is used elsewhere is OK? That still assumes there's a hash field,\nbut I think hashmap has always been pretty up front about that (the real\nsin in the original is assuming that nothing else needs to be\ninitialized).\n\n-Peff\n"},{"id":"394878","messageId":"20200406184650.GA637746@coredump.intra.peff.net","threadId":"53163","inReplyTo":"20200406183542.GA23753@coredump.intra.peff.net","subject":"Re: [PATCH] fast-import: replace custom hash with hashmap.c","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-04-06T18:46:50Z","receivedAt":"2020-04-06T18:46:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 06, 2020 at 02:35:42PM -0400, Jeff King wrote:\n\n> Pointing to uninitialized bits is fine according to the standard (and I\n> think that's what you're asking about for chapter and verse). But we\n> really do lie to container_of(). See remote.c, for example. In\n> make_remote(), we call hashmap_get() with a pointer to lookup_entry,\n> which is a bare \"struct hashmap_entry\". That should end up in\n> remotes_hash_cmp(), which unconditionally computes a pointer to a\n> \"struct remote\".\n> \n> Now the hashmap_entry there is at the beginning of the struct, so the\n> offset is 0 and the two pointers are the same. So while the pointer's\n> type is incorrect, we didn't compute an invalid pointer value. And\n> traditionally the hashmap code required that it be at the front of the\n> containing struct, but that was loosened recently (and container_of\n> introduced) in 5efabc7ed9 (Merge branch 'ew/hashmap', 2019-10-15).\n> \n> And grepping around, I don't see any cases where it's _not_ at the\n> beginning. So perhaps this is a problem waiting to bite us.\n\nI was curious wither ASan/UBSan might complain if we did something like\nthis:\n\ndiff --git a/oidmap.h b/oidmap.h\nindex c66a83ab1d..1abfe966f2 100644\n--- a/oidmap.h\n+++ b/oidmap.h\n@@ -12,10 +12,10 @@\n * internal_entry field.\n */\n struct oidmap_entry {\n+\tstruct object_id oid;\n+\n \t/* For internal use only */\n \tstruct hashmap_entry internal_entry;\n-\n-\tstruct object_id oid;\n };\n \n\nIt does, but not because of the subtle UB issue. It's just that the rest\nof oidmap still assumes the hashmap-is-first logic, and we need:\n\ndiff --git a/oidmap.c b/oidmap.c\nindex 423aa014a3..4065ea4b79 100644\n--- a/oidmap.c\n+++ b/oidmap.c\n@@ -35,7 +35,10 @@ void *oidmap_get(const struct oidmap *map, const struct object_id *key)\n \tif (!map->map.cmpfn)\n \t\treturn NULL;\n \n-\treturn hashmap_get_from_hash(&map->map, oidhash(key), key);\n+\treturn container_of_or_null(\n+\t\thashmap_get_from_hash(&map->map, oidhash(key), key),\n+\t\tstruct oidmap_entry,\n+\t\tinternal_entry);\n }\n \n void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n struct oidmap {\n@@ -79,7 +79,10 @@ static inline void oidmap_iter_init(struct oidmap *map, struct oidmap_iter *iter\n static inline void *oidmap_iter_next(struct oidmap_iter *iter)\n {\n \t/* TODO: this API could be reworked to do compile-time type checks */\n-\treturn (void *)hashmap_iter_next(&iter->h_iter);\n+\treturn container_of_or_null(\n+\t\thashmap_iter_next(&iter->h_iter),\n+\t\tstruct oidmap_entry,\n+\t\tinternal_entry);\n }\n \n static inline void *oidmap_iter_first(struct oidmap *map,\n\n-Peff\n\n\n"},{"id":"394881","messageId":"20200406194940.GA1242833@coredump.intra.peff.net","threadId":"53163","inReplyTo":"20200403121508.GA638328@coredump.intra.peff.net","subject":"[PATCH v2] fast-import: replace custom hash with hashmap.c","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-04-06T19:49:40Z","receivedAt":"2020-04-06T19:49:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 03, 2020 at 08:15:09AM -0400, Jeff King wrote:\n\n> We use a custom hash in fast-import to store the set of objects we've\n> imported so far. It has a fixed set of 2^16 buckets and chains any\n> collisions with a linked list. As the number of objects grows larger\n> than that, the load factor increases and we degrade to O(n) lookups and\n> O(n^2) insertions.\n> [...]\n\nHere's a v2 which uses some of the more advanced hashmap macros to do\nthe lookup and insertion. That shortens the code a bit, and avoids the\nplaces René didn't like that were intimate with the hashmap_entry (in\nfact we can get away without using the words hashmap_entry at all in\nthose functions).\n\nThe interdiff is:\n\n fast-import.c | 27 +++++++++++----------------\n 1 file changed, 11 insertions(+), 16 deletions(-)\n\n diff --git a/fast-import.c b/fast-import.c\n index 0ef6defc10..c98970274c 100644\n --- a/fast-import.c\n +++ b/fast-import.c\n @@ -471,29 +471,24 @@ static struct object_entry *new_object(struct object_id *oid)\n \n static struct object_entry *find_object(struct object_id *oid)\n {\n -\tstruct hashmap_entry lookup_entry, *e;\n -\n -\thashmap_entry_init(&lookup_entry, oidhash(oid));\n -\te = hashmap_get(&object_table, &lookup_entry, oid);\n -\tif (e)\n -\t\treturn container_of(e, struct object_entry, ent);\n -\treturn NULL;\n +\treturn hashmap_get_entry_from_hash(&object_table, oidhash(oid), oid,\n +\t\t\t\t\t struct object_entry, ent);\n }\n \n static struct object_entry *insert_object(struct object_id *oid)\n {\n \tstruct object_entry *e;\n -\tstruct hashmap_entry lookup_entry, *hashent;\n +\tunsigned int hash = oidhash(oid);\n \n -\thashmap_entry_init(&lookup_entry, oidhash(oid));\n -\thashent = hashmap_get(&object_table, &lookup_entry, oid);\n -\tif (hashent)\n -\t\treturn container_of(hashent, struct object_entry, ent);\n +\te = hashmap_get_entry_from_hash(&object_table, hash, oid,\n +\t\t\t\t\tstruct object_entry, ent);\n +\tif (!e) {\n +\t\te = new_object(oid);\n +\t\te->idx.offset = 0;\n +\t\thashmap_entry_init(&e->ent, hash);\n +\t\thashmap_add(&object_table, &e->ent);\n +\t}\n \n -\te = new_object(oid);\n -\te->idx.offset = 0;\n -\te->ent.hash = lookup_entry.hash;\n -\thashmap_add(&object_table, &e->ent);\n \treturn e;\n }\n \n\n-- >8 --\nSubject: fast-import: replace custom hash with hashmap.c\n\nWe use a custom hash in fast-import to store the set of objects we've\nimported so far. It has a fixed set of 2^16 buckets and chains any\ncollisions with a linked list. As the number of objects grows larger\nthan that, the load factor increases and we degrade to O(n) lookups and\nO(n^2) insertions.\n\nWe can scale better by using our hashmap.c implementation, which will\nresize the bucket count as we grow. This does incur an extra memory cost\nof 8 bytes per object, as hashmap stores the integer hash value for each\nentry in its hashmap_entry struct (which we really don't care about\nhere, because we're just reusing the embedded object hash). But I think\nthe numbers below justify this (and our per-object memory cost is\nalready much higher).\n\nI also looked at using khash, but it seemed to perform slightly worse\nthan hashmap at all sizes, and worse even than the existing code for\nsmall sizes. It's also awkward to use here, because we want to look up a\n\"struct object_entry\" from a \"struct object_id\", and it doesn't handle\nmismatched keys as well. Making a mapping of object_id to object_entry\nwould be more natural, but that would require pulling the embedded oid\nout of the object_entry or incurring an extra 32 bytes per object.\n\nIn a synthetic test creating as many cheap, tiny objects as possible\n\n perl -e '\n my $bits = shift;\n my $nr = 2**$bits;\n\n for (my $i = 0; $i < $nr; $i++) {\n print \"blob\\n\";\n print \"data 4\\n\";\n print pack(\"N\", $i);\n }\n ' $bits | git fast-import\n\nI got these results:\n\n nr_objects master khash hashmap\n 2^20 0m4.317s 0m5.109s 0m3.890s\n 2^21 0m10.204s 0m9.702s 0m7.933s\n 2^22 0m27.159s 0m17.911s 0m16.751s\n 2^23 1m19.038s 0m35.080s 0m31.963s\n 2^24 4m18.766s 1m10.233s 1m6.793s\n\nwhich points to hashmap as the winner. We didn't have any perf tests for\nfast-export or fast-import, so I added one as a more real-world case.\nIt uses an export without blobs since that's significantly cheaper than\na full one, but still is an interesting case people might use (e.g., for\nrewriting history). It will emphasize this change in some ways (as a\npercentage we spend more time making objects and less shuffling blob\nbytes around) and less in others (the total object count is lower).\n\nHere are the results for linux.git:\n\n Test HEAD^ HEAD\n ----------------------------------------------------------------------------\n 9300.1: export (no-blobs) 67.64(66.96+0.67) 67.81(67.06+0.75) +0.3%\n 9300.2: import (no-blobs) 284.04(283.34+0.69) 198.09(196.01+0.92) -30.3%\n\nIt only has ~5.2M commits and trees, so this is a larger effect than I\nexpected (the 2^23 case above only improved by 50s or so, but here we\ngained almost 90s). This is probably due to actually performing more\nobject lookups in a real import with trees and commits, as opposed to\njust dumping a bunch of blobs into a pack.\n\nSigned-off-by: Jeff King \n---\n fast-import.c | 61 ++++++++++++++++++------------\n t/perf/p9300-fast-import-export.sh | 23 +++++++++++\n 2 files changed, 59 insertions(+), 25 deletions(-)\n create mode 100755 t/perf/p9300-fast-import-export.sh\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 202dda11a6..c98970274c 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -39,12 +39,28 @@\n \n struct object_entry {\n \tstruct pack_idx_entry idx;\n-\tstruct object_entry *next;\n+\tstruct hashmap_entry ent;\n \tuint32_t type : TYPE_BITS,\n \t\tpack_id : PACK_ID_BITS,\n \t\tdepth : DEPTH_BITS;\n };\n \n+static int object_entry_hashcmp(const void *map_data,\n+\t\t\t\tconst struct hashmap_entry *eptr,\n+\t\t\t\tconst struct hashmap_entry *entry_or_key,\n+\t\t\t\tconst void *keydata)\n+{\n+\tconst struct object_id *oid = keydata;\n+\tconst struct object_entry *e1, *e2;\n+\n+\te1 = container_of(eptr, const struct object_entry, ent);\n+\tif (oid)\n+\t\treturn oidcmp(&e1->idx.oid, oid);\n+\n+\te2 = container_of(entry_or_key, const struct object_entry, ent);\n+\treturn oidcmp(&e1->idx.oid, &e2->idx.oid);\n+}\n+\n struct object_entry_pool {\n \tstruct object_entry_pool *next_pool;\n \tstruct object_entry *next_free;\n@@ -178,7 +194,7 @@ static off_t pack_size;\n /* Table of objects we've written. */\n static unsigned int object_entry_alloc = 5000;\n static struct object_entry_pool *blocks;\n-static struct object_entry *object_table[1 << 16];\n+static struct hashmap object_table;\n static struct mark_set *marks;\n static const char *export_marks_file;\n static const char *import_marks_file;\n@@ -455,44 +471,37 @@ static struct object_entry *new_object(struct object_id *oid)\n \n static struct object_entry *find_object(struct object_id *oid)\n {\n-\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n-\tstruct object_entry *e;\n-\tfor (e = object_table[h]; e; e = e->next)\n-\t\tif (oideq(oid, &e->idx.oid))\n-\t\t\treturn e;\n-\treturn NULL;\n+\treturn hashmap_get_entry_from_hash(&object_table, oidhash(oid), oid,\n+\t\t\t\t\t struct object_entry, ent);\n }\n \n static struct object_entry *insert_object(struct object_id *oid)\n {\n-\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n-\tstruct object_entry *e = object_table[h];\n+\tstruct object_entry *e;\n+\tunsigned int hash = oidhash(oid);\n \n-\twhile (e) {\n-\t\tif (oideq(oid, &e->idx.oid))\n-\t\t\treturn e;\n-\t\te = e->next;\n+\te = hashmap_get_entry_from_hash(&object_table, hash, oid,\n+\t\t\t\t\tstruct object_entry, ent);\n+\tif (!e) {\n+\t\te = new_object(oid);\n+\t\te->idx.offset = 0;\n+\t\thashmap_entry_init(&e->ent, hash);\n+\t\thashmap_add(&object_table, &e->ent);\n \t}\n \n-\te = new_object(oid);\n-\te->next = object_table[h];\n-\te->idx.offset = 0;\n-\tobject_table[h] = e;\n \treturn e;\n }\n \n static void invalidate_pack_id(unsigned int id)\n {\n-\tunsigned int h;\n \tunsigned long lu;\n \tstruct tag *t;\n+\tstruct hashmap_iter iter;\n+\tstruct object_entry *e;\n \n-\tfor (h = 0; h < ARRAY_SIZE(object_table); h++) {\n-\t\tstruct object_entry *e;\n-\n-\t\tfor (e = object_table[h]; e; e = e->next)\n-\t\t\tif (e->pack_id == id)\n-\t\t\t\te->pack_id = MAX_PACK_ID;\n+\thashmap_for_each_entry(&object_table, &iter, e, ent) {\n+\t\tif (e->pack_id == id)\n+\t\t\te->pack_id = MAX_PACK_ID;\n \t}\n \n \tfor (lu = 0; lu < branch_table_sz; lu++) {\n@@ -3511,6 +3520,8 @@ int cmd_main(int argc, const char **argv)\n \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n \tmarks = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));\n \n+\thashmap_init(&object_table, object_entry_hashcmp, NULL, 0);\n+\n \t/*\n \t * We don't parse most options until after we've seen the set of\n \t * \"feature\" lines at the start of the stream (which allows the command\ndiff --git a/t/perf/p9300-fast-import-export.sh b/t/perf/p9300-fast-import-export.sh\nnew file mode 100755\nindex 0000000000..586161e9ad\n--- /dev/null\n+++ b/t/perf/p9300-fast-import-export.sh\n@@ -0,0 +1,23 @@\n+#!/bin/sh\n+\n+test_description='test fast-import and fast-export performance'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+# Use --no-data here to produce a vastly smaller export file.\n+# This is much cheaper to work with but should still exercise\n+# fast-import pretty well (we'll still process all commits and\n+# trees, which account for 60% or more of objects in most repos).\n+#\n+# Use --reencode to avoid the default of aborting on non-utf8 commits,\n+# which lets this test run against a wider variety of sample repos.\n+test_perf 'export (no-blobs)' '\n+\tgit fast-export --reencode=yes --no-data HEAD >export\n+'\n+\n+test_perf 'import (no-blobs)' '\n+\tgit fast-import --force On Mon, Apr 06, 2020 at 08:07:45PM +0200, René Scharfe wrote:\n>\n>>> Interesting. I re-ran mine just to double check, and got:\n>> [...]\n>> A second run today reported:\n>>\n>> Test origin/master HEAD\n>> ---------------------------------------------------------------------------\n>> 9300.1: export (no-blobs) 61.58(59.93+1.40) 60.63(59.35+1.22) -1.5%\n>> 9300.2: import (no-blobs) 239.64(239.00+0.63) 246.02(245.18+0.82) +2.7%\n>>\n>> git describe says v5.4-3890-g86fd3e9df543 in that repo.\n>\n> I'm on v5.6-rc7-188-g1b649e0bcae7, but I can't imagine it makes a big\n> difference.\n>\n>> Dunno. My PC has thermal issues and stressing it for half an hour straight\n>> may cause it to throttle?\n>\n> Yeah. I wonder what the variance is between the 3 runs (assuming you're\n> using ./run and doing 3). I.e., is one run in the first set much faster\n> than the others, and we pick it as best-of-3.\n\nI did use run with the default three laps. Ran p9300 directly with\npatch v2 applied instead now, got this:\n\nTest this tree\n-----------------------------------------------\n9300.1: export (no-blobs) 64.80(60.95+1.47)\n9300.2: import (no-blobs) 210.00(206.02+2.04)\n9300.1: export (no-blobs) 62.58(60.74+1.35)\n9300.2: import (no-blobs) 209.07(206.78+1.96)\n9300.1: export (no-blobs) 61.33(60.17+1.03)\n9300.2: import (no-blobs) 207.73(205.47+2.04)\n\n> But we\n> really do lie to container_of(). See remote.c, for example. In\n> make_remote(), we call hashmap_get() with a pointer to lookup_entry,\n> which is a bare \"struct hashmap_entry\". That should end up in\n> remotes_hash_cmp(), which unconditionally computes a pointer to a\n> \"struct remote\".\n\nUgh. Any optimization level would delay that to after the keydata\ncheck, though, I guess.\n\nThere's also function pointer casting going on (with patch_util_cmp()\nand sequence_entry_cmp()), which is undefined behavior IIUC.\n\n> Now the hashmap_entry there is at the beginning of the struct, so the\n> offset is 0 and the two pointers are the same. So while the pointer's\n> type is incorrect, we didn't compute an invalid pointer value. And\n> traditionally the hashmap code required that it be at the front of the\n> containing struct, but that was loosened recently (and container_of\n> introduced) in 5efabc7ed9 (Merge branch 'ew/hashmap', 2019-10-15).\n\nHmm, OK.\n\n> And grepping around, I don't see any cases where it's _not_ at the\n> beginning. So perhaps this is a problem waiting to bite us.\n\nPossibly.\n\nSpeaking of grep, I ended up with this oneliner to show all the\ncomparison functions used with hashmaps:\n\ngit grep -W -f <(git grep -wh hashmap_init | cut -f2 -d, | grep -v -e ' .* ' -e NULL -e '^ *$' | sed 's/ //; s/.*)//; s/^/int /' | sort -u)\n\nBut I didn't learn much from looking at them, except that most have\nthat unconditional container_of.\n\n>> Stuffing the oidhash() result into a variable and using it twice with\n>> hashmap_entry_init() would work as well. This would make the reason for\n>> the duplicate find_object() code obvious, while keeping struct\n>> hashmap_entry opaque.\n>\n> I'd prefer not to use a separate variable, as that requires giving it a\n> type.\n\nSpecifying the type that oidhash() returns and hashmap_entry_init()\naccepts is redundant and inconvenient, but that line should be easy to\nfind and adapt when the function signatures are eventually changed.\nWhich is perhaps never going to happen anyway?\n\n> Perhaps:\n>\n> hashmap_entry_init(&e->ent, lookup_entry.hash);\n>\n> which is used elsewhere is OK? That still assumes there's a hash field,\n> but I think hashmap has always been pretty up front about that (the real\n> sin in the original is assuming that nothing else needs to be\n> initialized).\n\nThat conflicts with that statement from the hashmap.h:\n\n * struct hashmap_entry is an opaque structure representing an entry in the\n * hash table.\n\nPatch v2 looks good to me, though!\n\nRené\n"}]}