{"thread":{"id":"58804","subject":"[PATCH] delta-islands: free island-related data after use","startedAt":"2022-11-16T11:04:10Z","lastAt":"2023-02-02T00:11:27Z","messageCount":9,"participants":["Eric Wong","Ævar Arnfjörð Bjarmason","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"467362","messageId":"20221116105013.1777440-1-e@80x24.org","threadId":"58804","inReplyTo":null,"subject":"[PATCH] delta-islands: free island-related data after use","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2022-11-16T10:50:13Z","receivedAt":"2022-11-16T11:04:10Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"On my use case involving 771 islands of Linux on kernel.org,\nthis reduces memory usage by around 25MB.  The bulk of that\ncomes from free_remote_islands, since free_island_regexes only\nsaves around 40k.\n\nThis memory is saved early in the memory-intensive pack process,\nmaking it available for the remainder of the long process.\n\nSigned-off-by: Eric Wong <e@80x24.org>\n---\n  Note: I only noticed this when I screwed up up a pack.island RE,\n  ended up with hundreds of thousands of islands instead of 771,\n  and kept OOM-ing :x\n\n  Memory savings were measured using the following patch which\n  relies on a patched LD_PRELOAD-based malloc debugger:\n  https://80x24.org/spew/20221116095404.3974691-1-e@80x24.org/raw\n\n  Will try to hunt down more memory savings in the nearish future.\n\n delta-islands.c | 27 +++++++++++++++++++++++++++\n 1 file changed, 27 insertions(+)\n\ndiff --git a/delta-islands.c b/delta-islands.c\nindex 26f9e99e1a..391e947cc6 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -454,6 +454,31 @@ static void deduplicate_islands(struct repository *r)\n \tfree(list);\n }\n \n+static void free_island_regexes(void)\n+{\n+\tunsigned int i;\n+\n+\tfor (i = 0; i < island_regexes_nr; i++)\n+\t\tregfree(&island_regexes[i]);\n+\n+\tFREE_AND_NULL(island_regexes);\n+\tisland_regexes_alloc = island_regexes_nr = 0;\n+}\n+\n+static void free_remote_islands(void)\n+{\n+\tconst char *island_name;\n+\tstruct remote_island *rl;\n+\n+\tkh_foreach(remote_islands, island_name, rl, {\n+\t\tfree((void *)island_name);\n+\t\toid_array_clear(&rl->oids);\n+\t\tfree(rl);\n+\t});\n+\tkh_destroy_str(remote_islands);\n+\tremote_islands = NULL;\n+}\n+\n void load_delta_islands(struct repository *r, int progress)\n {\n \tisland_marks = kh_init_oid_map();\n@@ -461,7 +486,9 @@ void load_delta_islands(struct repository *r, int progress)\n \n \tgit_config(island_config_callback, NULL);\n \tfor_each_ref(find_island_for_ref, NULL);\n+\tfree_island_regexes();\n \tdeduplicate_islands(r);\n+\tfree_remote_islands();\n \n \tif (progress)\n \t\tfprintf(stderr, _(\"Marked %d islands, done.\\n\"), island_counter);\n"},{"id":"467373","messageId":"221116.861qq2kieu.gmgdl@evledraar.gmail.com","threadId":"58804","inReplyTo":"20221116105013.1777440-1-e@80x24.org","subject":"Re: [PATCH] delta-islands: free island-related data after use","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-11-16T15:44:31Z","receivedAt":"2022-11-16T15:50:40Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Nov 16 2022, Eric Wong wrote:\n\n> On my use case involving 771 islands of Linux on kernel.org,\n> this reduces memory usage by around 25MB.  The bulk of that\n> comes from free_remote_islands, since free_island_regexes only\n> saves around 40k.\n>\n> This memory is saved early in the memory-intensive pack process,\n> making it available for the remainder of the long process.\n>\n> Signed-off-by: Eric Wong <e@80x24.org>\n> ---\n>   Note: I only noticed this when I screwed up up a pack.island RE,\n>   ended up with hundreds of thousands of islands instead of 771,\n>   and kept OOM-ing :x\n>\n>   Memory savings were measured using the following patch which\n>   relies on a patched LD_PRELOAD-based malloc debugger:\n>   https://80x24.org/spew/20221116095404.3974691-1-e@80x24.org/raw\n\nFWIW SANITIZE=leak will find this if you stick a \"remote_islands = NULL\"\nand run e.g. t5320-delta-islands.sh, but maybe you needed this closer to\nproduction.\n\nValgrind will also work, but of course be *much* slower.\n\n>   Will try to hunt down more memory savings in the nearish future.\n>\n>  delta-islands.c | 27 +++++++++++++++++++++++++++\n>  1 file changed, 27 insertions(+)\n>\n> diff --git a/delta-islands.c b/delta-islands.c\n> index 26f9e99e1a..391e947cc6 100644\n> --- a/delta-islands.c\n> +++ b/delta-islands.c\n> @@ -454,6 +454,31 @@ static void deduplicate_islands(struct repository *r)\n>  \tfree(list);\n>  }\n>  \n> +static void free_island_regexes(void)\n> +{\n> +\tunsigned int i;\n> +\n> +\tfor (i = 0; i < island_regexes_nr; i++)\n> +\t\tregfree(&island_regexes[i]);\n> +\n> +\tFREE_AND_NULL(island_regexes);\n> +\tisland_regexes_alloc = island_regexes_nr = 0;\n> +}\n> +\n> +static void free_remote_islands(void)\n> +{\n> +\tconst char *island_name;\n> +\tstruct remote_island *rl;\n> +\n> +\tkh_foreach(remote_islands, island_name, rl, {\n> +\t\tfree((void *)island_name);\n> +\t\toid_array_clear(&rl->oids);\n> +\t\tfree(rl);\n> +\t});\n> +\tkh_destroy_str(remote_islands);\n> +\tremote_islands = NULL;\n> +}\n> +\n>  void load_delta_islands(struct repository *r, int progress)\n>  {\n>  \tisland_marks = kh_init_oid_map();\n> @@ -461,7 +486,9 @@ void load_delta_islands(struct repository *r, int progress)\n>  \n>  \tgit_config(island_config_callback, NULL);\n>  \tfor_each_ref(find_island_for_ref, NULL);\n> +\tfree_island_regexes();\n>  \tdeduplicate_islands(r);\n> +\tfree_remote_islands();\n>  \n>  \tif (progress)\n>  \t\tfprintf(stderr, _(\"Marked %d islands, done.\\n\"), island_counter);\n\nPerfect shouldn't be the enemy of the good & all that, but in this case\nit's not too much more effort to just give this data an appropriate\nlifetime instead of the global, I tried that out for just the \"regex\"\npart of this below.\n\nThe free_remote_islands() seems to be similarly alive between\n\"find_island_for_ref\" and \"deduplicate_islands\".\n\nYour version also works, but the root cause of this sort of thing is\nthese global lifetimes, which sometimes we do for a good reason, but in\nthis case we don't.\n\nIt's more lines, but e.g. your FREE_AND_NULL() and resetting \"nr\" and\n\"alloc\" makes one wonder how the data might be used outside fo that\nload_delta_islands() chain (which is needed, if we invoke it again),\nwhen we can just init a stack variable to hold it instead...\n\ndiff --git a/delta-islands.c b/delta-islands.c\nindex 26f9e99e1a9..ef86a91059c 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -312,29 +312,41 @@ void resolve_tree_islands(struct repository *r,\n \tfree(todo);\n }\n \n-static regex_t *island_regexes;\n-static unsigned int island_regexes_alloc, island_regexes_nr;\n+struct island_config_data {\n+\tregex_t *rx;\n+\tsize_t nr;\n+\tsize_t alloc;\n+};\n static const char *core_island_name;\n \n-static int island_config_callback(const char *k, const char *v, void *cb UNUSED)\n+static void island_config_data_release(struct island_config_data *icd)\n+{\n+\tfor (size_t i = 0; i < icd->nr; i++)\n+\t\tregfree(&icd->rx[i]);\n+\tfree(icd->rx);\n+}\n+\n+static int island_config_callback(const char *k, const char *v, void *cb)\n {\n+\tstruct island_config_data *data = cb;\n+\n \tif (!strcmp(k, \"pack.island\")) {\n \t\tstruct strbuf re = STRBUF_INIT;\n \n \t\tif (!v)\n \t\t\treturn config_error_nonbool(k);\n \n-\t\tALLOC_GROW(island_regexes, island_regexes_nr + 1, island_regexes_alloc);\n+\t\tALLOC_GROW(data->rx, data->nr + 1, data->alloc);\n \n \t\tif (*v != '^')\n \t\t\tstrbuf_addch(&re, '^');\n \t\tstrbuf_addstr(&re, v);\n \n-\t\tif (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED))\n+\t\tif (regcomp(&data->rx[data->nr], re.buf, REG_EXTENDED))\n \t\t\tdie(_(\"failed to load island regex for '%s': %s\"), k, re.buf);\n \n \t\tstrbuf_release(&re);\n-\t\tisland_regexes_nr++;\n+\t\tdata->nr++;\n \t\treturn 0;\n \t}\n \n@@ -365,8 +377,10 @@ static void add_ref_to_island(const char *island_name, const struct object_id *o\n }\n \n static int find_island_for_ref(const char *refname, const struct object_id *oid,\n-\t\t\t       int flags UNUSED, void *data UNUSED)\n+\t\t\t       int flags UNUSED, void *cb)\n {\n+\tstruct island_config_data *data = cb;\n+\n \t/*\n \t * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,\n \t * so we can diagnose below a config with more capture groups\n@@ -377,8 +391,8 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,\n \tstruct strbuf island_name = STRBUF_INIT;\n \n \t/* walk backwards to get last-one-wins ordering */\n-\tfor (i = island_regexes_nr - 1; i >= 0; i--) {\n-\t\tif (!regexec(&island_regexes[i], refname,\n+\tfor (i = data->nr - 1; i >= 0; i--) {\n+\t\tif (!regexec(&data->rx[i], refname,\n \t\t\t     ARRAY_SIZE(matches), matches, 0))\n \t\t\tbreak;\n \t}\n@@ -456,11 +470,14 @@ static void deduplicate_islands(struct repository *r)\n \n void load_delta_islands(struct repository *r, int progress)\n {\n+\tstruct island_config_data data = { 0 };\n+\n \tisland_marks = kh_init_oid_map();\n \tremote_islands = kh_init_str();\n \n-\tgit_config(island_config_callback, NULL);\n-\tfor_each_ref(find_island_for_ref, NULL);\n+\tgit_config(island_config_callback, &data);\n+\tfor_each_ref(find_island_for_ref, &data);\n+\tisland_config_data_release(&data);\n \tdeduplicate_islands(r);\n \n \tif (progress)\n"},{"id":"467378","messageId":"Y3UvhsRC9uCXJJ8P@coredump.intra.peff.net","threadId":"58804","inReplyTo":"20221116105013.1777440-1-e@80x24.org","subject":"Re: [PATCH] delta-islands: free island-related data after use","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-11-16T18:44:22Z","receivedAt":"2022-11-16T18:46:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 16, 2022 at 10:50:13AM +0000, Eric Wong wrote:\n\n> On my use case involving 771 islands of Linux on kernel.org,\n> this reduces memory usage by around 25MB.  The bulk of that\n> comes from free_remote_islands, since free_island_regexes only\n> saves around 40k.\n> \n> This memory is saved early in the memory-intensive pack process,\n> making it available for the remainder of the long process.\n\nI think this works and is a reasonable thing to do. The non-obvious\nquestion is whether the island data is ever used later in the process.\nCertainly the island bitmaps themselves are, but the initial mapping of\nrefs to islands doesn't.\n\nI do agree with Ævar that it would be a lot easier to confirm that if\nthese variables were given a more appropriate scope (this was mostly\njust laziness on my part writing the initial delta-island code; so much\nof it has to stick around for the whole process and I didn't distinguish\nbetween the two).\n\n>   Will try to hunt down more memory savings in the nearish future.\n\nYes, you've probably noticed that pack-objects does not distinguish much\nbetween what is necessary for the various phases. A few obvious things\nto look at:\n\n  1. After the write phase, you can probably ditch the island bitmaps,\n     too. In many repacks we're basically done then, but if you're\n     generating bitmaps, that happens afterwards in the same process.\n\n  2. The object traversal for pack-objects is done in-process these\n     days. But after it finishes, I suspect that we do not generally\n     need those object structs anymore, because all of the book-keeping\n     is done in the bit object_entry array in packing_data.\n\n     The exception would be generating bitmaps, which does need to do\n     some traversal (and I think may hang on to actual \"struct commit\"\n     pointers).\n\n     I also don't think we have any code that clears obj_hash or\n     released the pooled object pointers.\n\n     So it's probably pretty tricky, but I suspect would yield big\n     savings, since it's a per-object cost on the order of 64 bytes (so\n     ~640MB on the kernel).\n\n  3. During the bitmap phase I'm not sure if we still care about the\n     object_entry struct in packing_data. It's the other big\n     bytes-per-object user of memory. We need it all the way through the\n     write phase for obvious reasons, but if we could ditch it for the\n     bitmap phase, that may reduce peak memory during that phase.\n\n-Peff\n"},{"id":"467475","messageId":"20221117230658.M516129@dcvr","threadId":"58804","inReplyTo":"221116.861qq2kieu.gmgdl@evledraar.gmail.com","subject":"[PATCH v2] delta-islands: free island-related data after use","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2022-11-17T23:06:58Z","receivedAt":"2022-11-17T23:07:12Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:\n> On Wed, Nov 16 2022, Eric Wong wrote:\n> >   Memory savings were measured using the following patch which\n> >   relies on a patched LD_PRELOAD-based malloc debugger:\n> >   https://80x24.org/spew/20221116095404.3974691-1-e@80x24.org/raw\n> \n> FWIW SANITIZE=leak will find this if you stick a \"remote_islands = NULL\"\n> and run e.g. t5320-delta-islands.sh, but maybe you needed this closer to\n> production.\n> \n> Valgrind will also work, but of course be *much* slower.\n\nYeah, I run that LD_PRELOAD thing in production since it's\ncheap compared to valgrind.\n\n> Perfect shouldn't be the enemy of the good & all that, but in this case\n> it's not too much more effort to just give this data an appropriate\n> lifetime instead of the global, I tried that out for just the \"regex\"\n> part of this below.\n> \n> The free_remote_islands() seems to be similarly alive between\n> \"find_island_for_ref\" and \"deduplicate_islands\".\n> \n> Your version also works, but the root cause of this sort of thing is\n> these global lifetimes, which sometimes we do for a good reason, but in\n> this case we don't.\n\nAgreed on all points.  Overall, the amount of globals in git has\nlong seemed excessive and offputting to me (and likely other\ndrive-by hackers).\n\n> diff --git a/delta-islands.c b/delta-islands.c\n> index 26f9e99e1a9..ef86a91059c 100644\n> --- a/delta-islands.c\n> +++ b/delta-islands.c\n> @@ -312,29 +312,41 @@ void resolve_tree_islands(struct repository *r,\n>  \tfree(todo);\n>  }\n>  \n> -static regex_t *island_regexes;\n> -static unsigned int island_regexes_alloc, island_regexes_nr;\n> +struct island_config_data {\n> +\tregex_t *rx;\n> +\tsize_t nr;\n> +\tsize_t alloc;\n> +};\n\nI've added kh_str_t *remote_islands and renamed\ns/island_config_data/island_load_data/ in the below version\nto reflect the slightly different scope of remote_islands.\n\n>  static const char *core_island_name;\n>  \n> -static int island_config_callback(const char *k, const char *v, void *cb UNUSED)\n> +static void island_config_data_release(struct island_config_data *icd)\n> +{\n> +\tfor (size_t i = 0; i < icd->nr; i++)\n> +\t\tregfree(&icd->rx[i]);\n> +\tfree(icd->rx);\n> +}\n\nicd => ild since config => load\n\n> +static int island_config_callback(const char *k, const char *v, void *cb)\n>  {\n> +\tstruct island_config_data *data = cb;\n> +\n\ndata => ild\n\nI don't like the name `data' for a typed variable.\n\nAside from that, v2 below still frees the regex memory early on\nin the hopes deduplicate_islands() can reuse some of the freed\nregexp memory.\n\nAnyways, here's v2, which seems to work.  I'm still trying to\nfigure out SATA errors+resets after replacing a CMOS battery,\nbut I really hope this patch isn't the cause.\n\n-----8<-----\nFrom: Eric Wong <e@80x24.org>\nSubject: [PATCH] delta-islands: free island-related data after use\n\nOn my use case involving 771 islands of Linux on kernel.org,\nthis reduces memory usage by around 25MB.  The bulk of that\ncomes from free_remote_islands, since free_config_regexes only\nsaves around 40k.\n\nThis memory is saved early in the memory-intensive pack process,\nmaking it available for the remainder of the long process.\n\nSigned-off-by: Eric Wong <e@80x24.org>\nCo-authored-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n---\n v2: reduce scope of load-time data structures with hints from Ævar\n\n delta-islands.c | 71 +++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 51 insertions(+), 20 deletions(-)\n\ndiff --git a/delta-islands.c b/delta-islands.c\nindex 26f9e99e1a..90c0d6958f 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -26,8 +26,6 @@ static kh_oid_map_t *island_marks;\n static unsigned island_counter;\n static unsigned island_counter_core;\n \n-static kh_str_t *remote_islands;\n-\n struct remote_island {\n \tuint64_t hash;\n \tstruct oid_array oids;\n@@ -312,29 +310,55 @@ void resolve_tree_islands(struct repository *r,\n \tfree(todo);\n }\n \n-static regex_t *island_regexes;\n-static unsigned int island_regexes_alloc, island_regexes_nr;\n+struct island_load_data {\n+\tkh_str_t *remote_islands;\n+\tregex_t *rx;\n+\tsize_t nr;\n+\tsize_t alloc;\n+};\n static const char *core_island_name;\n \n-static int island_config_callback(const char *k, const char *v, void *cb UNUSED)\n+static void free_config_regexes(struct island_load_data *ild)\n {\n+\tfor (size_t i = 0; i < ild->nr; i++)\n+\t\tregfree(&ild->rx[i]);\n+\tfree(ild->rx);\n+}\n+\n+static void free_remote_islands(kh_str_t *remote_islands)\n+{\n+\tconst char *island_name;\n+\tstruct remote_island *rl;\n+\n+\tkh_foreach(remote_islands, island_name, rl, {\n+\t\tfree((void *)island_name);\n+\t\toid_array_clear(&rl->oids);\n+\t\tfree(rl);\n+\t});\n+\tkh_destroy_str(remote_islands);\n+}\n+\n+static int island_config_callback(const char *k, const char *v, void *cb)\n+{\n+\tstruct island_load_data *ild = cb;\n+\n \tif (!strcmp(k, \"pack.island\")) {\n \t\tstruct strbuf re = STRBUF_INIT;\n \n \t\tif (!v)\n \t\t\treturn config_error_nonbool(k);\n \n-\t\tALLOC_GROW(island_regexes, island_regexes_nr + 1, island_regexes_alloc);\n+\t\tALLOC_GROW(ild->rx, ild->nr + 1, ild->alloc);\n \n \t\tif (*v != '^')\n \t\t\tstrbuf_addch(&re, '^');\n \t\tstrbuf_addstr(&re, v);\n \n-\t\tif (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED))\n+\t\tif (regcomp(&ild->rx[ild->nr], re.buf, REG_EXTENDED))\n \t\t\tdie(_(\"failed to load island regex for '%s': %s\"), k, re.buf);\n \n \t\tstrbuf_release(&re);\n-\t\tisland_regexes_nr++;\n+\t\tild->nr++;\n \t\treturn 0;\n \t}\n \n@@ -344,7 +368,8 @@ static int island_config_callback(const char *k, const char *v, void *cb UNUSED)\n \treturn 0;\n }\n \n-static void add_ref_to_island(const char *island_name, const struct object_id *oid)\n+static void add_ref_to_island(kh_str_t *remote_islands, const char *island_name,\n+\t\t\t\tconst struct object_id *oid)\n {\n \tuint64_t sha_core;\n \tstruct remote_island *rl = NULL;\n@@ -365,8 +390,10 @@ static void add_ref_to_island(const char *island_name, const struct object_id *o\n }\n \n static int find_island_for_ref(const char *refname, const struct object_id *oid,\n-\t\t\t       int flags UNUSED, void *data UNUSED)\n+\t\t\t       int flags UNUSED, void *cb)\n {\n+\tstruct island_load_data *ild = cb;\n+\n \t/*\n \t * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,\n \t * so we can diagnose below a config with more capture groups\n@@ -377,8 +404,8 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,\n \tstruct strbuf island_name = STRBUF_INIT;\n \n \t/* walk backwards to get last-one-wins ordering */\n-\tfor (i = island_regexes_nr - 1; i >= 0; i--) {\n-\t\tif (!regexec(&island_regexes[i], refname,\n+\tfor (i = ild->nr - 1; i >= 0; i--) {\n+\t\tif (!regexec(&ild->rx[i], refname,\n \t\t\t     ARRAY_SIZE(matches), matches, 0))\n \t\t\tbreak;\n \t}\n@@ -403,12 +430,12 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,\n \t\tstrbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);\n \t}\n \n-\tadd_ref_to_island(island_name.buf, oid);\n+\tadd_ref_to_island(ild->remote_islands, island_name.buf, oid);\n \tstrbuf_release(&island_name);\n \treturn 0;\n }\n \n-static struct remote_island *get_core_island(void)\n+static struct remote_island *get_core_island(kh_str_t *remote_islands)\n {\n \tif (core_island_name) {\n \t\tkhiter_t pos = kh_get_str(remote_islands, core_island_name);\n@@ -419,7 +446,7 @@ static struct remote_island *get_core_island(void)\n \treturn NULL;\n }\n \n-static void deduplicate_islands(struct repository *r)\n+static void deduplicate_islands(kh_str_t *remote_islands, struct repository *r)\n {\n \tstruct remote_island *island, *core = NULL, **list;\n \tunsigned int island_count, dst, src, ref, i = 0;\n@@ -445,7 +472,7 @@ static void deduplicate_islands(struct repository *r)\n \t}\n \n \tisland_bitmap_size = (island_count / 32) + 1;\n-\tcore = get_core_island();\n+\tcore = get_core_island(remote_islands);\n \n \tfor (i = 0; i < island_count; ++i) {\n \t\tmark_remote_island_1(r, list[i], core && list[i]->hash == core->hash);\n@@ -456,12 +483,16 @@ static void deduplicate_islands(struct repository *r)\n \n void load_delta_islands(struct repository *r, int progress)\n {\n+\tstruct island_load_data ild = { 0 };\n+\n \tisland_marks = kh_init_oid_map();\n-\tremote_islands = kh_init_str();\n \n-\tgit_config(island_config_callback, NULL);\n-\tfor_each_ref(find_island_for_ref, NULL);\n-\tdeduplicate_islands(r);\n+\tgit_config(island_config_callback, &ild);\n+\tild.remote_islands = kh_init_str();\n+\tfor_each_ref(find_island_for_ref, &ild);\n+\tfree_config_regexes(&ild);\n+\tdeduplicate_islands(ild.remote_islands, r);\n+\tfree_remote_islands(ild.remote_islands);\n \n \tif (progress)\n \t\tfprintf(stderr, _(\"Marked %d islands, done.\\n\"), island_counter);\n"},{"id":"467481","messageId":"221118.86zgcog2lp.gmgdl@evledraar.gmail.com","threadId":"58804","inReplyTo":"20221117230658.M516129@dcvr","subject":"Re: [PATCH v2] delta-islands: free island-related data after use","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-11-18T01:51:34Z","receivedAt":"2022-11-18T07:10:17Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Nov 17 2022, Eric Wong wrote:\n\n> Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:\n>> On Wed, Nov 16 2022, Eric Wong wrote:\n>> >   Memory savings were measured using the following patch which\n>> >   relies on a patched LD_PRELOAD-based malloc debugger:\n>> >   https://80x24.org/spew/20221116095404.3974691-1-e@80x24.org/raw\n>> \n>> FWIW SANITIZE=leak will find this if you stick a \"remote_islands = NULL\"\n>> and run e.g. t5320-delta-islands.sh, but maybe you needed this closer to\n>> production.\n>> \n>> Valgrind will also work, but of course be *much* slower.\n>\n> Yeah, I run that LD_PRELOAD thing in production since it's\n> cheap compared to valgrind.\n>\n>> Perfect shouldn't be the enemy of the good & all that, but in this case\n>> it's not too much more effort to just give this data an appropriate\n>> lifetime instead of the global, I tried that out for just the \"regex\"\n>> part of this below.\n>> \n>> The free_remote_islands() seems to be similarly alive between\n>> \"find_island_for_ref\" and \"deduplicate_islands\".\n>> \n>> Your version also works, but the root cause of this sort of thing is\n>> these global lifetimes, which sometimes we do for a good reason, but in\n>> this case we don't.\n>\n> Agreed on all points.  Overall, the amount of globals in git has\n> long seemed excessive and offputting to me (and likely other\n> drive-by hackers).\n>\n>> diff --git a/delta-islands.c b/delta-islands.c\n>> index 26f9e99e1a9..ef86a91059c 100644\n>> --- a/delta-islands.c\n>> +++ b/delta-islands.c\n>> @@ -312,29 +312,41 @@ void resolve_tree_islands(struct repository *r,\n>>  \tfree(todo);\n>>  }\n>>  \n>> -static regex_t *island_regexes;\n>> -static unsigned int island_regexes_alloc, island_regexes_nr;\n>> +struct island_config_data {\n>> +\tregex_t *rx;\n>> +\tsize_t nr;\n>> +\tsize_t alloc;\n>> +};\n>\n> I've added kh_str_t *remote_islands and renamed\n> s/island_config_data/island_load_data/ in the below version\n> to reflect the slightly different scope of remote_islands.\n>\n>>  static const char *core_island_name;\n>>  \n>> -static int island_config_callback(const char *k, const char *v, void *cb UNUSED)\n>> +static void island_config_data_release(struct island_config_data *icd)\n>> +{\n>> +\tfor (size_t i = 0; i < icd->nr; i++)\n>> +\t\tregfree(&icd->rx[i]);\n>> +\tfree(icd->rx);\n>> +}\n>\n> icd => ild since config => load\n>\n>> +static int island_config_callback(const char *k, const char *v, void *cb)\n>>  {\n>> +\tstruct island_config_data *data = cb;\n>> +\n>\n> data => ild\n>\n> I don't like the name `data' for a typed variable.\n\nHah! My thought process when deciding on it was \"hrm, what *do* we call\nthe two variables when we have a void * and turn it into a 'util'?\ndata? cb? util? ... and which one was which?\"\n\nI started grepping, then decided I was wasting too much time on that for\na one-off reply, and just went with the first thing I found. The names\nyou picked are a lot better :)\n\n> Aside from that, v2 below still frees the regex memory early on\n> in the hopes deduplicate_islands() can reuse some of the freed\n> regexp memory.\n>\n> Anyways, here's v2, which seems to work.  I'm still trying to\n> figure out SATA errors+resets after replacing a CMOS battery,\n> but I really hope this patch isn't the cause.\n>\n> -----8<-----\n> From: Eric Wong <e@80x24.org>\n> Subject: [PATCH] delta-islands: free island-related data after use\n>\n> On my use case involving 771 islands of Linux on kernel.org,\n> this reduces memory usage by around 25MB.  The bulk of that\n> comes from free_remote_islands, since free_config_regexes only\n> saves around 40k.\n>\n> This memory is saved early in the memory-intensive pack process,\n> making it available for the remainder of the long process.\n>\n> Signed-off-by: Eric Wong <e@80x24.org>\n> Co-authored-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n\nThis all looks good to me, thanks a lot for the follow-up.\n"},{"id":"467810","messageId":"Y30vf76mdrSv4We4@coredump.intra.peff.net","threadId":"58804","inReplyTo":"20221117230658.M516129@dcvr","subject":"Re: [PATCH v2] delta-islands: free island-related data after use","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-11-22T20:22:23Z","receivedAt":"2022-11-22T20:22:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Nov 17, 2022 at 11:06:58PM +0000, Eric Wong wrote:\n\n> Aside from that, v2 below still frees the regex memory early on\n> in the hopes deduplicate_islands() can reuse some of the freed\n> regexp memory.\n> \n> Anyways, here's v2, which seems to work.  I'm still trying to\n> figure out SATA errors+resets after replacing a CMOS battery,\n> but I really hope this patch isn't the cause.\n\nThis looks OK to me, though I think it would have been easier to review\nsplit into two patches (one pushing the globals into local variables and\nthe other adding the freeing).\n\nTwo small notes:\n\n>  void load_delta_islands(struct repository *r, int progress)\n>  {\n> +\tstruct island_load_data ild = { 0 };\n> +\n>  \tisland_marks = kh_init_oid_map();\n> -\tremote_islands = kh_init_str();\n>  \n> -\tgit_config(island_config_callback, NULL);\n> -\tfor_each_ref(find_island_for_ref, NULL);\n> -\tdeduplicate_islands(r);\n> +\tgit_config(island_config_callback, &ild);\n> +\tild.remote_islands = kh_init_str();\n\nThe initialization of the remote_islands khash is now moved after we\nread the config. That's OK, because our callback doesn't read it, but\nit's not immediately obvious without going back to check the callback.\n\nSplitting it into:\n\n  struct island_load_data {\n\tkh_str_t *remote_islands;\n\tstruct island_regexes regexes {\n\t\tregex_t *rx;\n\t\tsize_t nr;\n\t\tsize_t alloc;\n\t};\n  };\n\nlets you pass:\n\n  git_config(island_config_callback, &ild.regexes);\n\nwhich makes it clear that the khash part isn't touched. But you still\nget to pass the whole &ild around later. Of course that's all going\nthrough a void pointer, so you're praying that the callback expects the\nright type anyway. ;)\n\nAnd with your code we'd hopefully notice the problem right away since\nthe khash pointer is NULL. So it might not be that big a deal.\n\n> +\tfor_each_ref(find_island_for_ref, &ild);\n> +\tfree_config_regexes(&ild);\n> +\tdeduplicate_islands(ild.remote_islands, r);\n> +\tfree_remote_islands(ild.remote_islands);\n\nHere we free the regexes, but they're pointing to garbage memory still.\nBut since we pass just the remote_islands part of the struct to those\nfunctions, we know they can't look at the garbage regexes. Good.\n\nI'd have said it ought to be two separate variables, but the\nfor_each_ref() callback forces your hand there.\n\n-Peff\n"},{"id":"471219","messageId":"20230201092027.M96461@dcvr","threadId":"58804","inReplyTo":"Y3UvhsRC9uCXJJ8P@coredump.intra.peff.net","subject":"pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2023-02-01T09:20:27Z","receivedAt":"2023-02-01T09:25:59Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King <peff@peff.net> wrote:\n> On Wed, Nov 16, 2022 at 10:50:13AM +0000, Eric Wong wrote:\n> >   Will try to hunt down more memory savings in the nearish future.\n> \n> Yes, you've probably noticed that pack-objects does not distinguish much\n> between what is necessary for the various phases. A few obvious things\n> to look at:\n> \n>   1. After the write phase, you can probably ditch the island bitmaps,\n>      too. In many repacks we're basically done then, but if you're\n>      generating bitmaps, that happens afterwards in the same process.\n\nAlso, island_marks oid_map gets pretty big itself (300M?), and\nrealloc gets painful when resizing a big khash especially on\nnon-GNU/Linux systems without MREMAP_MAYMOVE realloc.  Currently\nexperimenting with tweaks to make oidtree handle kh_oid_map\nfunctionality to avoid resizes...[1]\n\n>   2. The object traversal for pack-objects is done in-process these\n>      days. But after it finishes, I suspect that we do not generally\n>      need those object structs anymore, because all of the book-keeping\n>      is done in the bit object_entry array in packing_data.\n\npdata->objects is 1.4G for me atm after many hours (still going).\nI think packing_data could be split to avoid reallocs, but that\nmight need to touch a lot of code...\n\nI need to get better data on my next attempts.  I suspect gcc\n-O2 is throwing off mwrap-perl[2]+addr2line and I need to\nrebuild w/ -O0.\n\n[1] WIP oidtree map, but I feel like I forgot C, again :<\n\ndiff --git a/delta-islands.c b/delta-islands.c\nindex 90c0d6958f..9e824d7a0d 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -18,11 +18,13 @@\n #include \"pack-objects.h\"\n #include \"delta-islands.h\"\n #include \"oid-array.h\"\n+#include \"oidtree.h\"\n #include \"config.h\"\n \n KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)\n \n-static kh_oid_map_t *island_marks;\n+struct oidtree island_marks_storage;\n+static struct oidtree *island_marks;\n static unsigned island_counter;\n static unsigned island_counter_core;\n \n@@ -93,7 +95,7 @@ static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n \n int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n {\n-\tkhiter_t trg_pos, src_pos;\n+\tstruct island_bitmap *trg, *src;\n \n \t/* If we aren't using islands, assume everything goes together. */\n \tif (!island_marks)\n@@ -103,37 +105,30 @@ int in_same_island(const struct object_id *trg_oid, const struct object_id *src_\n \t * If we don't have a bitmap for the target, we can delta it\n \t * against anything -- it's not an important object\n \t */\n-\ttrg_pos = kh_get_oid_map(island_marks, *trg_oid);\n-\tif (trg_pos >= kh_end(island_marks))\n+\ttrg = oidtree_get(island_marks, trg_oid);\n+\tif (!trg)\n \t\treturn 1;\n \n \t/*\n \t * if the source (our delta base) doesn't have a bitmap,\n \t * we don't want to base any deltas on it!\n \t */\n-\tsrc_pos = kh_get_oid_map(island_marks, *src_oid);\n-\tif (src_pos >= kh_end(island_marks))\n+\tsrc = oidtree_get(island_marks, src_oid);\n+\tif (!src)\n \t\treturn 0;\n \n-\treturn island_bitmap_is_subset(kh_value(island_marks, trg_pos),\n-\t\t\t\tkh_value(island_marks, src_pos));\n+\treturn island_bitmap_is_subset(trg, src);\n }\n \n int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n {\n-\tkhiter_t a_pos, b_pos;\n-\tstruct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;\n+\tstruct island_bitmap *a_bitmap, *b_bitmap;\n \n \tif (!island_marks)\n \t\treturn 0;\n \n-\ta_pos = kh_get_oid_map(island_marks, *a);\n-\tif (a_pos < kh_end(island_marks))\n-\t\ta_bitmap = kh_value(island_marks, a_pos);\n-\n-\tb_pos = kh_get_oid_map(island_marks, *b);\n-\tif (b_pos < kh_end(island_marks))\n-\t\tb_bitmap = kh_value(island_marks, b_pos);\n+\ta_bitmap = oidtree_get(island_marks, a);\n+\tb_bitmap = oidtree_get(island_marks, b);\n \n \tif (a_bitmap) {\n \t\tif (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))\n@@ -149,30 +144,28 @@ int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n \n static struct island_bitmap *create_or_get_island_marks(struct object *obj)\n {\n-\tkhiter_t pos;\n-\tint hash_ret;\n+\tvoid **val;\n+\tsize_t n = sizeof(struct island_bitmap *);\n \n-\tpos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);\n-\tif (hash_ret)\n-\t\tkh_value(island_marks, pos) = island_bitmap_new(NULL);\n+\tif (oidtree_put(island_marks, &obj->oid, &val, n))\n+\t\t*val = island_bitmap_new(NULL);\n \n-\treturn kh_value(island_marks, pos);\n+\treturn *val;\n }\n \n static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n {\n \tstruct island_bitmap *b;\n-\tkhiter_t pos;\n-\tint hash_ret;\n+\tvoid **val;\n+\tsize_t n = sizeof(struct island_bitmap *);\n \n-\tpos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);\n-\tif (hash_ret) {\n+\tif (oidtree_put(island_marks, &obj->oid, &val, n)) {\n \t\t/*\n \t\t * We don't have one yet; make a copy-on-write of the\n \t\t * parent.\n \t\t */\n \t\tmarks->refcount++;\n-\t\tkh_value(island_marks, pos) = marks;\n+\t\t*val = marks;\n \t\treturn;\n \t}\n \n@@ -180,10 +173,10 @@ static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n \t * We do have it. Make sure we split any copy-on-write before\n \t * updating.\n \t */\n-\tb = kh_value(island_marks, pos);\n+\tb = *val;\n \tif (b->refcount > 1) {\n \t\tb->refcount--;\n-\t\tb = kh_value(island_marks, pos) = island_bitmap_new(b);\n+\t\t*val = b = island_bitmap_new(b);\n \t}\n \tisland_bitmap_or(b, marks);\n }\n@@ -275,14 +268,11 @@ void resolve_tree_islands(struct repository *r,\n \t\tstruct tree *tree;\n \t\tstruct tree_desc desc;\n \t\tstruct name_entry entry;\n-\t\tkhiter_t pos;\n \n-\t\tpos = kh_get_oid_map(island_marks, ent->idx.oid);\n-\t\tif (pos >= kh_end(island_marks))\n+\t\troot_marks = oidtree_get(island_marks, &ent->idx.oid);\n+\t\tif (!root_marks)\n \t\t\tcontinue;\n \n-\t\troot_marks = kh_value(island_marks, pos);\n-\n \t\ttree = lookup_tree(r, &ent->idx.oid);\n \t\tif (!tree || parse_tree(tree) < 0)\n \t\t\tdie(_(\"bad tree object %s\"), oid_to_hex(&ent->idx.oid));\n@@ -485,7 +475,8 @@ void load_delta_islands(struct repository *r, int progress)\n {\n \tstruct island_load_data ild = { 0 };\n \n-\tisland_marks = kh_init_oid_map();\n+\toidtree_init(&island_marks_storage);\n+\tisland_marks = &island_marks_storage;\n \n \tgit_config(island_config_callback, &ild);\n \tild.remote_islands = kh_init_str();\n@@ -500,11 +491,11 @@ void load_delta_islands(struct repository *r, int progress)\n \n void propagate_island_marks(struct commit *commit)\n {\n-\tkhiter_t pos = kh_get_oid_map(island_marks, commit->object.oid);\n+\tstruct island_bitmap *root_marks;\n \n-\tif (pos < kh_end(island_marks)) {\n+\troot_marks = oidtree_get(island_marks, &commit->object.oid);\n+\tif (root_marks) {\n \t\tstruct commit_list *p;\n-\t\tstruct island_bitmap *root_marks = kh_value(island_marks, pos);\n \n \t\tparse_commit(commit);\n \t\tset_island_marks(&get_commit_tree(commit)->object, root_marks);\n@@ -522,16 +513,13 @@ int compute_pack_layers(struct packing_data *to_pack)\n \n \tfor (i = 0; i < to_pack->nr_objects; ++i) {\n \t\tstruct object_entry *entry = &to_pack->objects[i];\n-\t\tkhiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid);\n+\t\tstruct island_bitmap *bitmap;\n \n \t\toe_set_layer(to_pack, entry, 1);\n \n-\t\tif (pos < kh_end(island_marks)) {\n-\t\t\tstruct island_bitmap *bitmap = kh_value(island_marks, pos);\n-\n-\t\t\tif (island_bitmap_get(bitmap, island_counter_core))\n-\t\t\t\toe_set_layer(to_pack, entry, 0);\n-\t\t}\n+\t\tbitmap = oidtree_get(island_marks, &entry->idx.oid);\n+\t\tif (bitmap && island_bitmap_get(bitmap, island_counter_core))\n+\t\t\toe_set_layer(to_pack, entry, 0);\n \t}\n \n \treturn 2;\ndiff --git a/oidtree.c b/oidtree.c\nindex 0d39389bee..eb7e76335e 100644\n--- a/oidtree.c\n+++ b/oidtree.c\n@@ -28,15 +28,16 @@ void oidtree_clear(struct oidtree *ot)\n \t}\n }\n \n-void oidtree_insert(struct oidtree *ot, const struct object_id *oid)\n+static void **oidtree_insert3(struct oidtree *ot, const struct object_id *oid,\n+\t\t\t\tsize_t extra)\n {\n \tstruct cb_node *on;\n \tstruct object_id k;\n \n \tif (!oid->algo)\n-\t\tBUG(\"oidtree_insert requires oid->algo\");\n+\t\tBUG(\"oidtree insertion requires oid->algo\");\n \n-\ton = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid));\n+\ton = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid) + extra);\n \n \t/*\n \t * Clear the padding and copy the result in separate steps to\n@@ -45,19 +46,22 @@ void oidtree_insert(struct oidtree *ot, const struct object_id *oid)\n \toidcpy_with_padding(&k, oid);\n \tmemcpy(on->k, &k, sizeof(k));\n \n-\t/*\n-\t * n.b. Current callers won't get us duplicates, here.  If a\n-\t * future caller causes duplicates, there'll be a a small leak\n-\t * that won't be freed until oidtree_clear.  Currently it's not\n-\t * worth maintaining a free list\n-\t */\n-\tcb_insert(&ot->tree, on, sizeof(*oid));\n+\tif (!cb_insert(&ot->tree, on, sizeof(*oid)))\n+\t\treturn (void **)(on->k + sizeof(k)); /* success */\n+\n+\twarning(\"oidtree leak (check contains/get before insert/put)\");\n+\treturn NULL;\n }\n \n+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)\n+{\n+\t(void)oidtree_insert3(ot, oid, 0);\n+}\n \n-int oidtree_contains(struct oidtree *ot, const struct object_id *oid)\n+static void **oidtree_find(struct oidtree *ot, const struct object_id *oid)\n {\n \tstruct object_id k;\n+\tstruct cb_node *on;\n \tsize_t klen = sizeof(k);\n \n \toidcpy_with_padding(&k, oid);\n@@ -69,7 +73,31 @@ int oidtree_contains(struct oidtree *ot, const struct object_id *oid)\n \tklen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) <\n \t\t\t\toffsetof(struct object_id, algo));\n \n-\treturn cb_lookup(&ot->tree, (const uint8_t *)&k, klen) ? 1 : 0;\n+\ton = cb_lookup(&ot->tree, (const uint8_t *)&k, klen);\n+\treturn on ? (void **)(on->k + sizeof(k)) : NULL;\n+}\n+\n+int oidtree_put(struct oidtree *ot, const struct object_id *oid,\n+\t\tvoid ***p, size_t n)\n+{\n+\t*p = oidtree_find(ot, oid);\n+\tif (*p)\n+\t\treturn 0;\n+\n+\t*p = oidtree_insert3(ot, oid, n);\n+\tassert(*p);\n+\treturn 1;\n+}\n+\n+void *oidtree_get(struct oidtree *ot, const struct object_id *oid)\n+{\n+\tvoid **p = oidtree_find(ot, oid);\n+\treturn p ? *p : NULL;\n+}\n+\n+int oidtree_contains(struct oidtree *ot, const struct object_id *oid)\n+{\n+\treturn oidtree_find(ot, oid) ? 1 : 0;\n }\n \n static enum cb_next iter(struct cb_node *n, void *arg)\ndiff --git a/oidtree.h b/oidtree.h\nindex 77898f510a..2f6e6f1beb 100644\n--- a/oidtree.h\n+++ b/oidtree.h\n@@ -12,6 +12,8 @@ struct oidtree {\n \n void oidtree_init(struct oidtree *);\n void oidtree_clear(struct oidtree *);\n+\n+/* oid_set-like API */\n void oidtree_insert(struct oidtree *, const struct object_id *);\n int oidtree_contains(struct oidtree *, const struct object_id *);\n \n@@ -19,4 +21,17 @@ typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *data);\n void oidtree_each(struct oidtree *, const struct object_id *,\n \t\t\tsize_t oidhexsz, oidtree_iter, void *data);\n \n+/* oid_map-like API */\n+\n+/* returns a pointer to the data payload associated with object_id */\n+void *oidtree_get(struct oidtree *, const struct object_id *);\n+\n+/*\n+ * points @p to the destination of the value\n+ * @n must be consistent for the entire oidtree\n+ * returns true if a new oidtree node was created,\n+ * returns false if reusing an existing oidtree node\n+ */\n+int oidtree_put(struct oidtree *, const struct object_id *,\n+\t\tvoid ***p, size_t n);\n #endif /* OIDTREE_H */\n\n\n[2] https://80x24.org/mwrap-perl.git\n\n    # after install, run gc under mwrap-perl with backtrace 10\n    MWRAP=socket_dir:/tmp/mwrap,bt:10 mwrap-perl git gc\n\n    # recommended: use GNU addr2line 2.39+ (Aug 2022) for +OFFSET decoding\n\n    # start HTTP reverse proxy\n    ADDR2LINE='/path/to/addr2line -p -f -i' \\\n\tmwrap-rproxy --socket-dir=/tmp/mwrap\n\n    # the per-PID each/2000 URLs can get really expensive for browsers\n    # even w3m struggles:\n    w3m http://0:5000/ # follow per-PID links\n"},{"id":"471269","messageId":"20230201220929.M549554@dcvr","threadId":"58804","inReplyTo":"20230201092027.M96461@dcvr","subject":"Re: pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2023-02-01T22:09:29Z","receivedAt":"2023-02-01T22:10:09Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Eric Wong <e@80x24.org> wrote:\n> [1] WIP oidtree map, but I feel like I forgot C, again :<\n\nWell, it hasn't crashed.  It's just much slower compared to khash.\n\nI'm thinking `struct object_id' should be pooled+deduplicated\nlike hash keys in the Perl/Ruby interpreters and we'd pass\n4/8-byte pointers instead of 36-byte structs.\n"},{"id":"471293","messageId":"Y9r/rLhB1L9EnTKR@coredump.intra.peff.net","threadId":"58804","inReplyTo":"20230201220929.M549554@dcvr","subject":"Re: pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-02-02T00:11:24Z","receivedAt":"2023-02-02T00:11:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Feb 01, 2023 at 10:09:29PM +0000, Eric Wong wrote:\n\n> Eric Wong <e@80x24.org> wrote:\n> > [1] WIP oidtree map, but I feel like I forgot C, again :<\n> \n> Well, it hasn't crashed.  It's just much slower compared to khash.\n\nI experimented a bit with critbit trees several years ago, mostly for\nthe main obj_hash. I could never make them faster than hashing. I think\npart of it is that \"hashing\" an oid is basically free, since we just\npull off the first 4 bytes. And we keep our table factors quite low.\nWhereas for trie structures, even though the big-O behavior is good,\nthere's a lot of branching that ends up being slow.\n\n> I'm thinking `struct object_id' should be pooled+deduplicated\n> like hash keys in the Perl/Ruby interpreters and we'd pass\n> 4/8-byte pointers instead of 36-byte structs.\n\nI think that could work, but it feels like it would be pretty major\nsurgery, given how often object_ids appear in the code.\n\n-Peff\n"}]}