delta-islands: free island-related data after use
PATCH 1/1 delta-islands: free island-related data after use
On my use case involving 771 islands of Linux on kernel.org, this reduces memory usage by around 25MB. The bulk of that comes from free_remote_islands, since free_island_regexes only saves around 40k.
This memory is saved early in the memory-intensive pack process, making it available for the remainder of the long process.
---
Note: I only noticed this when I screwed up up a pack.island RE, ended up with hundreds of thousands of islands instead of 771, and kept OOM-ing :x
Memory savings were measured using the following patch which relies on a patched LD_PRELOAD-based malloc debugger:
https://80x24.org/spew/[email protected]/raw
Will try to hunt down more memory savings in the nearish future.
delta-islands.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)
delta-islands.c +27 -0
@@ -454,6 +454,31 @@ static void deduplicate_islands(struct repository *r)free (list); } +static void free_island_regexes (void ) +{ +unsigned int i; + +for (i =0 ; i < island_regexes_nr; i++) +regfree (&island_regexes[i]); + +FREE_AND_NULL (island_regexes); + island_regexes_alloc = island_regexes_nr =0 ; +} + +static void free_remote_islands (void ) +{ +const char *island_name; +struct remote_island *rl; + +kh_foreach (remote_islands, island_name, rl, { +free ((void *)island_name); +oid_array_clear (&rl->oids); +free (rl); + }); +kh_destroy_str (remote_islands); + remote_islands =NULL ; +} +void load_delta_islands (struct repository *r,int progress) { island_marks =kh_init_oid_map ();
@@ -461,7 +486,9 @@ void load_delta_islands(struct repository *r, int progress)git_config (island_config_callback,NULL );for_each_ref (find_island_for_ref,NULL ); +free_island_regexes ();deduplicate_islands (r); +free_remote_islands ();if (progress)fprintf (stderr,_ ("Marked %d islands, done.\n" ), island_counter);
Quoted 9 lines · Eric Wong
On my use case involving 771 islands of Linux on kernel.org, this reduces memory usage by around 25MB. The bulk of that comes from
free_remote_islands, sincefree_island_regexesonly saves around 40k.This memory is saved early in the memory-intensive pack process, making it available for the remainder of the long process.
Signed-off-by Eric Wong <[email protected]>
Quoted 8 lines
---
Note: I only noticed this when I screwed up up a pack.island RE, ended up with hundreds of thousands of islands instead of 771, and kept OOM-ing :xMemory savings were measured using the following patch which relies on a patched LD_PRELOAD-based malloc debugger:
https://80x24.org/spew/[email protected]/raw
FWIW SANITIZE=leak will find this if you stick a "remote_islands = NULL" and run e.g. t5320-delta-islands.sh, but maybe you needed this closer to production.
Valgrind will also work, but of course be *much* slower.
Quoted 42 lines
Will try to hunt down more memory savings in the nearish future.
delta-islands.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)delta-islands.c +25
-0@@ -454,6 +454,31 @@ static void deduplicate_islands(struct repository *r)free (list); } +static void free_island_regexes (void ) +{ +unsigned int i; + +for (i =0 ; i < island_regexes_nr; i++) +regfree (&island_regexes[i]); + +FREE_AND_NULL (island_regexes); + island_regexes_alloc = island_regexes_nr =0 ; +} + +static void free_remote_islands (void ) +{ +const char *island_name; +struct remote_island *rl; + +kh_foreach (remote_islands, island_name, rl, { +free ((void *)island_name); +oid_array_clear (&rl->oids); +free (rl); + }); +kh_destroy_str (remote_islands); + remote_islands =NULL ; +} +void load_delta_islands (struct repository *r,int progress) { island_marks =kh_init_oid_map ();
delta-islands.c void load_delta_islands(struct repository *r, int progress) · line 494
Quoted 9 lines
delta-islands.c +2
-0@@ -461,7 +486,9 @@ void load_delta_islands(struct repository *r, int progress)git_config (island_config_callback,NULL );for_each_ref (find_island_for_ref,NULL ); +free_island_regexes ();deduplicate_islands (r); +free_remote_islands ();if (progress)fprintf (stderr,_ ("Marked %d islands, done.\n" ), island_counter);
Perfect shouldn't be the enemy of the good & all that, but in this case it's not too much more effort to just give this data an appropriate lifetime instead of the global, I tried that out for just the "regex" part of this below.
The free_remote_islands() seems to be similarly alive between "find_island_for_ref" and "deduplicate_islands".
Your version also works, but the root cause of this sort of thing is these global lifetimes, which sometimes we do for a good reason, but in this case we don't.
It's more lines, but e.g. your FREE_AND_NULL() and resetting "nr" and "alloc" makes one wonder how the data might be used outside fo that load_delta_islands() chain (which is needed, if we invoke it again), when we can just init a stack variable to hold it instead...
delta-islands.c +28 -11
@@ -312,29 +312,41 @@ void resolve_tree_islands(struct repository *r,free (todo); } -static regex_t *island_regexes; -static unsigned int island_regexes_alloc, island_regexes_nr; +struct island_config_data { +regex_t *rx; +size_t nr; +size_t alloc; +};static const char *core_island_name; -static int island_config_callback(const char *k, const char *v, void *cb UNUSED) +static void island_config_data_release (struct island_config_data *icd) +{ +for (size_t i =0 ; i < icd->nr; i++) +regfree (&icd->rx[i]); +free (icd->rx); +} + +static int island_config_callback (const char *k,const char *v,void *cb) { +struct island_config_data *data = cb; +if (!strcmp (k,"pack.island" )) {struct strbuf re =STRBUF_INIT ;if (!v)return config_error_nonbool (k); -ALLOC_GROW (island_regexes, island_regexes_nr +1 , island_regexes_alloc); +ALLOC_GROW (data->rx, data->nr +1 , data->alloc);if (*v !='^' )strbuf_addch (&re,'^' );strbuf_addstr (&re, v); -if (regcomp (&island_regexes[island_regexes_nr], re.buf,REG_EXTENDED )) +if (regcomp (&data->rx[data->nr], re.buf,REG_EXTENDED ))die (_ ("failed to load island regex for '%s': %s" ), k, re.buf);strbuf_release (&re); - island_regexes_nr++; + data->nr++;return 0 ; }
@@ -365,8 +377,10 @@ static void add_ref_to_island(const char *island_name, const struct object_id *o }static int find_island_for_ref (const char *refname,const struct object_id *oid, - int flags UNUSED, void *data UNUSED) + int flags UNUSED, void *cb) { +struct island_config_data *data = cb; +/* * We should advertise 'ARRAY_SIZE(matches) - 2' as the max, * so we can diagnose below a config with more capture groups
@@ -377,8 +391,8 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,struct strbuf island_name =STRBUF_INIT ;/* walk backwards to get last-one-wins ordering */ -for (i = island_regexes_nr -1 ; i >=0 ; i--) { -if (!regexec (&island_regexes[i], refname, +for (i = data->nr -1 ; i >=0 ; i--) { +if (!regexec (&data->rx[i], refname,ARRAY_SIZE (matches), matches,0 ))break ; }
@@ -456,11 +470,14 @@ static void deduplicate_islands(struct repository *r)void load_delta_islands (struct repository *r,int progress) { +struct island_config_data data = {0 }; + island_marks =kh_init_oid_map (); remote_islands =kh_init_str (); -git_config (island_config_callback,NULL ); -for_each_ref (find_island_for_ref,NULL ); +git_config (island_config_callback, &data); +for_each_ref (find_island_for_ref, &data); +island_config_data_release (&data);deduplicate_islands (r);if (progress)
PATCH v2 1/1 delta-islands: free island-related data after use
Quoted 10 lines · Ævar Arnfjörð Bjarmason
Quoted 3 lines · Eric Wong
Memory savings were measured using the following patch which relies on a patched LD_PRELOAD-based malloc debugger:
https://80x24.org/spew/[email protected]/rawFWIW SANITIZE=leak will find this if you stick a "
remote_islands= NULL" and run e.g.t5320-delta-islands.sh, but maybe you needed this closer to production.Valgrind will also work, but of course be *much* slower.
Yeah, I run that LD_PRELOAD thing in production since it's cheap compared to valgrind.
Quoted 11 lines
Perfect shouldn't be the enemy of the good & all that, but in this case it's not too much more effort to just give this data an appropriate lifetime instead of the global, I tried that out for just the "regex" part of this below.
The
free_remote_islands()seems to be similarly alive between "find_island_for_ref" and "deduplicate_islands".Your version also works, but the root cause of this sort of thing is these global lifetimes, which sometimes we do for a good reason, but in this case we don't.
Agreed on all points. Overall, the amount of globals in git has long seemed excessive and offputting to me (and likely other drive-by hackers).
Quoted 5 lines
delta-islands.c +0
-0
delta-islands.c void resolve_tree_islands(struct repository *r, · line 319
Quoted 10 lines
delta-islands.c +5
-2@@ -312,29 +312,41 @@ void resolve_tree_islands(struct repository *r,free (todo); } -static regex_t *island_regexes; -static unsigned int island_regexes_alloc, island_regexes_nr; +struct island_config_data { +regex_t *rx; +size_t nr; +size_t alloc; +};
I've added kh_str_t *remote_islands and renamed s/island_config_data/island_load_data/ in the below version to reflect the slightly different scope of remote_islands.
delta-islands.c void resolve_tree_islands(struct repository *r, · line 327
Quoted 9 lines
delta-islands.c +6
-1static const char *core_island_name; -static int island_config_callback(const char *k, const char *v, void *cb UNUSED) +static void island_config_data_release (struct island_config_data *icd) +{ +for (size_t i =0 ; i < icd->nr; i++) +regfree (&icd->rx[i]); +free (icd->rx); +}
icd => ild since config => load
delta-islands.c void resolve_tree_islands(struct repository *r, · line 331
Quoted 4 lines
delta-islands.c +3
-0+static int island_config_callback (const char *k,const char *v,void *cb) { +struct island_config_data *data = cb; +
data => ild
I don't like the name `data' for a typed variable.
Aside from that, v2 below still frees the regex memory early on in the hopes deduplicate_islands() can reuse some of the freed regexp memory.
Anyways, here's v2, which seems to work. I'm still trying to figure out SATA errors+resets after replacing a CMOS battery, but I really hope this patch isn't the cause.
-----8<-----
From: Eric Wong <[email protected]>
Subject: [PATCH] delta-islands: free island-related data after use
On my use case involving 771 islands of Linux on kernel.org, this reduces memory usage by around 25MB. The bulk of that comes from free_remote_islands, since free_config_regexes only saves around 40k.
This memory is saved early in the memory-intensive pack process, making it available for the remainder of the long process.
---
v2: reduce scope of load-time data structures with hints from Ævar
delta-islands.c | 71 +++++++++++++++++++++++++++++++++++-------------- 1 file changed, 51 insertions(+), 20 deletions(-)
delta-islands.c +51 -20
@@ -26,8 +26,6 @@ static kh_oid_map_t *island_marks;static unsigned island_counter;static unsigned island_counter_core; -static kh_str_t *remote_islands; -struct remote_island {uint64_t hash;struct oid_array oids;
@@ -312,29 +310,55 @@ void resolve_tree_islands(struct repository *r,free (todo); } -static regex_t *island_regexes; -static unsigned int island_regexes_alloc, island_regexes_nr; +struct island_load_data { +kh_str_t *remote_islands; +regex_t *rx; +size_t nr; +size_t alloc; +};static const char *core_island_name; -static int island_config_callback(const char *k, const char *v, void *cb UNUSED) +static void free_config_regexes (struct island_load_data *ild) { +for (size_t i =0 ; i < ild->nr; i++) +regfree (&ild->rx[i]); +free (ild->rx); +} + +static void free_remote_islands (kh_str_t *remote_islands) +{ +const char *island_name; +struct remote_island *rl; + +kh_foreach (remote_islands, island_name, rl, { +free ((void *)island_name); +oid_array_clear (&rl->oids); +free (rl); + }); +kh_destroy_str (remote_islands); +} + +static int island_config_callback (const char *k,const char *v,void *cb) +{ +struct island_load_data *ild = cb; +if (!strcmp (k,"pack.island" )) {struct strbuf re =STRBUF_INIT ;if (!v)return config_error_nonbool (k); -ALLOC_GROW (island_regexes, island_regexes_nr +1 , island_regexes_alloc); +ALLOC_GROW (ild->rx, ild->nr +1 , ild->alloc);if (*v !='^' )strbuf_addch (&re,'^' );strbuf_addstr (&re, v); -if (regcomp (&island_regexes[island_regexes_nr], re.buf,REG_EXTENDED )) +if (regcomp (&ild->rx[ild->nr], re.buf,REG_EXTENDED ))die (_ ("failed to load island regex for '%s': %s" ), k, re.buf);strbuf_release (&re); - island_regexes_nr++; + ild->nr++;return 0 ; }
@@ -344,7 +368,8 @@ static int island_config_callback(const char *k, const char *v, void *cb UNUSED)return 0 ; } -static void add_ref_to_island (const char *island_name,const struct object_id *oid) +static void add_ref_to_island (kh_str_t *remote_islands,const char *island_name, +const struct object_id *oid) {uint64_t sha_core;struct remote_island *rl =NULL ;
@@ -365,8 +390,10 @@ static void add_ref_to_island(const char *island_name, const struct object_id *o }static int find_island_for_ref (const char *refname,const struct object_id *oid, - int flags UNUSED, void *data UNUSED) + int flags UNUSED, void *cb) { +struct island_load_data *ild = cb; +/* * We should advertise 'ARRAY_SIZE(matches) - 2' as the max, * so we can diagnose below a config with more capture groups
@@ -377,8 +404,8 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,struct strbuf island_name =STRBUF_INIT ;/* walk backwards to get last-one-wins ordering */ -for (i = island_regexes_nr -1 ; i >=0 ; i--) { -if (!regexec (&island_regexes[i], refname, +for (i = ild->nr -1 ; i >=0 ; i--) { +if (!regexec (&ild->rx[i], refname,ARRAY_SIZE (matches), matches,0 ))break ; }
@@ -403,12 +430,12 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,strbuf_add (&island_name, refname + match->rm_so, match->rm_eo - match->rm_so); } -add_ref_to_island (island_name.buf, oid); +add_ref_to_island (ild->remote_islands, island_name.buf, oid);strbuf_release (&island_name);return 0 ; } -static struct remote_island *get_core_island (void ) +static struct remote_island *get_core_island (kh_str_t *remote_islands) {if (core_island_name) {khiter_t pos =kh_get_str (remote_islands, core_island_name);
@@ -419,7 +446,7 @@ static struct remote_island *get_core_island(void)return NULL ; } -static void deduplicate_islands (struct repository *r) +static void deduplicate_islands (kh_str_t *remote_islands,struct repository *r) {struct remote_island *island, *core =NULL , **list;unsigned int island_count, dst, src, ref, i =0 ;
@@ -445,7 +472,7 @@ static void deduplicate_islands(struct repository *r) } island_bitmap_size = (island_count /32 ) +1 ; - core =get_core_island (); + core =get_core_island (remote_islands);for (i =0 ; i < island_count; ++i) {mark_remote_island_1 (r, list[i], core && list[i]->hash == core->hash);
@@ -456,12 +483,16 @@ static void deduplicate_islands(struct repository *r)void load_delta_islands (struct repository *r,int progress) { +struct island_load_data ild = {0 }; + island_marks =kh_init_oid_map (); - remote_islands =kh_init_str (); -git_config (island_config_callback,NULL ); -for_each_ref (find_island_for_ref,NULL ); -deduplicate_islands (r); +git_config (island_config_callback, &ild); + ild.remote_islands =kh_init_str (); +for_each_ref (find_island_for_ref, &ild); +free_config_regexes (&ild); +deduplicate_islands (ild.remote_islands, r); +free_remote_islands (ild.remote_islands);if (progress)fprintf (stderr,_ ("Marked %d islands, done.\n" ), island_counter);
Quoted 63 lines · Eric Wong
Quoted 10 lines · Ævar Arnfjörð Bjarmason
Quoted 3 lines · Eric Wong
Memory savings were measured using the following patch which relies on a patched LD_PRELOAD-based malloc debugger:
https://80x24.org/spew/[email protected]/rawFWIW SANITIZE=leak will find this if you stick a "
remote_islands= NULL" and run e.g.t5320-delta-islands.sh, but maybe you needed this closer to production.Valgrind will also work, but of course be *much* slower.
Yeah, I run that
LD_PRELOADthing in production since it's cheap compared to valgrind.Quoted 11 lines
Perfect shouldn't be the enemy of the good & all that, but in this case it's not too much more effort to just give this data an appropriate lifetime instead of the global, I tried that out for just the "regex" part of this below.
The
free_remote_islands()seems to be similarly alive between "find_island_for_ref" and "deduplicate_islands".Your version also works, but the root cause of this sort of thing is these global lifetimes, which sometimes we do for a good reason, but in this case we don't.
Agreed on all points. Overall, the amount of globals in git has long seemed excessive and offputting to me (and likely other drive-by hackers).
Quoted 5 lines
delta-islands.c +0
-0delta-islands.c void resolve_tree_islands(struct repository *r, · line 319
Quoted 10 lines
delta-islands.c +5
-2@@ -312,29 +312,41 @@ void resolve_tree_islands(struct repository *r,free (todo); } -static regex_t *island_regexes; -static unsigned int island_regexes_alloc, island_regexes_nr; +struct island_config_data { +regex_t *rx; +size_t nr; +size_t alloc; +};I've added
kh_str_t*remote_islandsand renamed s/island_config_data/island_load_data/ in the below version to reflect the slightly different scope ofremote_islands.delta-islands.c void resolve_tree_islands(struct repository *r, · line 339
Quoted 9 lines
delta-islands.c +6
-1static const char *core_island_name; -static int island_config_callback(const char *k, const char *v, void *cb UNUSED) +static void island_config_data_release (struct island_config_data *icd) +{ +for (size_t i =0 ; i < icd->nr; i++) +regfree (&icd->rx[i]); +free (icd->rx); +}icd => ild since config => load
Quoted 8 lines
delta-islands.c void resolve_tree_islands(struct repository *r, · line 344
Quoted 4 lines
delta-islands.c +3
-0+static int island_config_callback (const char *k,const char *v,void *cb) { +struct island_config_data *data = cb; +data => ild
I don't like the name `data' for a typed variable.
Hah! My thought process when deciding on it was "hrm, what *do* we call the two variables when we have a void * and turn it into a 'util'? data? cb? util? ... and which one was which?"
I started grepping, then decided I was wasting too much time on that for a one-off reply, and just went with the first thing I found. The names you picked are a lot better :)
Quoted 17 lines
Aside from that, v2 below still frees the regex memory early on in the hopes
deduplicate_islands()can reuse some of the freed regexp memory.Anyways, here's v2, which seems to work. I'm still trying to figure out SATA errors+resets after replacing a CMOS battery, but I really hope this patch isn't the cause.
-----8<-----
From: Eric Wong <[email protected]>
Subject: [PATCH] delta-islands: free island-related data after useOn my use case involving 771 islands of Linux on kernel.org, this reduces memory usage by around 25MB. The bulk of that comes from
free_remote_islands, sincefree_config_regexesonly saves around 40k.
Quoted 5 lines
This memory is saved early in the memory-intensive pack process, making it available for the remainder of the long process.
Signed-off-by Eric Wong <[email protected]>Co-authored-by Ævar Arnfjörð Bjarmason <[email protected]>
This all looks good to me, thanks a lot for the follow-up.
Quoted 7 lines · Eric Wong
Aside from that, v2 below still frees the regex memory early on in the hopes
deduplicate_islands()can reuse some of the freed regexp memory.Anyways, here's v2, which seems to work. I'm still trying to figure out SATA errors+resets after replacing a CMOS battery, but I really hope this patch isn't the cause.
This looks OK to me, though I think it would have been easier to review split into two patches (one pushing the globals into local variables and the other adding the freeing).
Two small notes:
delta-islands.c static void deduplicate_islands(struct repository *r) · line 491
Quoted 12 lines
void
load_delta_islands(struct repository *r, int progress){delta-islands.c +4
-4+struct island_load_data ild = {0 }; + island_marks =kh_init_oid_map (); - remote_islands =kh_init_str (); -git_config (island_config_callback,NULL ); -for_each_ref (find_island_for_ref,NULL ); -deduplicate_islands (r); +git_config (island_config_callback, &ild); + ild.remote_islands =kh_init_str ();
The initialization of the remote_islands khash is now moved after we read the config. That's OK, because our callback doesn't read it, but it's not immediately obvious without going back to check the callback.
Splitting it into:
struct island_load_data {
kh_str_t *remote_islands;
struct island_regexes regexes {
regex_t *rx;
size_t nr;
size_t alloc;
};};
lets you pass:
git_config(island_config_callback, &ild.regexes);
which makes it clear that the khash part isn't touched. But you still get to pass the whole &ild around later. Of course that's all going through a void pointer, so you're praying that the callback expects the right type anyway. ;)
And with your code we'd hopefully notice the problem right away since the khash pointer is NULL. So it might not be that big a deal.
delta-islands.c static void deduplicate_islands(struct repository *r) · line 495
Quoted 4 lines
delta-islands.c +4
-0+for_each_ref (find_island_for_ref, &ild); +free_config_regexes (&ild); +deduplicate_islands (ild.remote_islands, r); +free_remote_islands (ild.remote_islands);
Here we free the regexes, but they're pointing to garbage memory still. But since we pass just the remote_islands part of the struct to those functions, we know they can't look at the garbage regexes. Good.
I'd have said it ought to be two separate variables, but the for_each_ref() callback forces your hand there.
-Peff
Quoted 7 lines · Eric Wong
On my use case involving 771 islands of Linux on kernel.org, this reduces memory usage by around 25MB. The bulk of that comes from
free_remote_islands, sincefree_island_regexesonly saves around 40k.This memory is saved early in the memory-intensive pack process, making it available for the remainder of the long process.
I think this works and is a reasonable thing to do. The non-obvious question is whether the island data is ever used later in the process. Certainly the island bitmaps themselves are, but the initial mapping of refs to islands doesn't.
I do agree with Ævar that it would be a lot easier to confirm that if these variables were given a more appropriate scope (this was mostly just laziness on my part writing the initial delta-island code; so much of it has to stick around for the whole process and I didn't distinguish between the two).
Quoted 1 line
Will try to hunt down more memory savings in the nearish future.
Yes, you've probably noticed that pack-objects does not distinguish much between what is necessary for the various phases. A few obvious things to look at:
1. After the write phase, you can probably ditch the island bitmaps, too. In many repacks we're basically done then, but if you're generating bitmaps, that happens afterwards in the same process.
2. The object traversal for pack-objects is done in-process these days. But after it finishes, I suspect that we do not generally need those object structs anymore, because all of the book-keeping is done in the bit object_entry array in packing_data.
The exception would be generating bitmaps, which does need to do some traversal (and I think may hang on to actual "struct commit" pointers).
I also don't think we have any code that clears obj_hash or released the pooled object pointers.
So it's probably pretty tricky, but I suspect would yield big savings, since it's a per-object cost on the order of 64 bytes (so ~640MB on the kernel).
3. During the bitmap phase I'm not sure if we still care about the object_entry struct in packing_data. It's the other big bytes-per-object user of memory. We need it all the way through the write phase for obvious reasons, but if we could ditch it for the bitmap phase, that may reduce peak memory during that phase.
-Peff
pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]
Quoted 10 lines · Jeff King
Quoted 1 line · Eric Wong
Will try to hunt down more memory savings in the nearish future.
Yes, you've probably noticed that pack-objects does not distinguish much between what is necessary for the various phases. A few obvious things to look at:
1. After the write phase, you can probably ditch the island bitmaps, too. In many repacks we're basically done then, but if you're generating bitmaps, that happens afterwards in the same process.
Also, island_marks oid_map gets pretty big itself (300M?), and realloc gets painful when resizing a big khash especially on non-GNU/Linux systems without MREMAP_MAYMOVE realloc. Currently experimenting with tweaks to make oidtree handle kh_oid_map functionality to avoid resizes...[1]
Quoted 4 lines
2. The object traversal for pack-objects is done in-process these days. But after it finishes, I suspect that we do not generally need those object structs anymore, because all of the book-keeping is done in the bit
object_entryarray inpacking_data.
pdata->objects is 1.4G for me atm after many hours (still going). I think packing_data could be split to avoid reallocs, but that might need to touch a lot of code...
I need to get better data on my next attempts. I suspect gcc -O2 is throwing off mwrap-perl[2]+addr2line and I need to rebuild w/ -O0.
[1] WIP oidtree map, but I feel like I forgot C, again :<
delta-islands.c +34 -46
@@ -18,11 +18,13 @@#include "pack-objects.h" #include "delta-islands.h" #include "oid-array.h" +#include "oidtree.h" #include "config.h" KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal) -static kh_oid_map_t *island_marks; +struct oidtree island_marks_storage; +static struct oidtree *island_marks;static unsigned island_counter;static unsigned island_counter_core;
@@ -93,7 +95,7 @@ static int island_bitmap_get(struct island_bitmap *self, uint32_t i)int in_same_island (const struct object_id *trg_oid,const struct object_id *src_oid) { -khiter_t trg_pos, src_pos; +struct island_bitmap *trg, *src;/* If we aren't using islands, assume everything goes together. */ if (!island_marks)
@@ -103,37 +105,30 @@ int in_same_island(const struct object_id *trg_oid, const struct object_id *src_* If we don't have a bitmap for the target, we can delta it * against anything -- it's not an important object */ - trg_pos =kh_get_oid_map (island_marks, *trg_oid); -if (trg_pos >=kh_end (island_marks)) + trg =oidtree_get (island_marks, trg_oid); +if (!trg)return 1 ;/* * if the source (our delta base) doesn't have a bitmap, * we don't want to base any deltas on it! */ - src_pos =kh_get_oid_map (island_marks, *src_oid); -if (src_pos >=kh_end (island_marks)) + src =oidtree_get (island_marks, src_oid); +if (!src)return 0 ; -return island_bitmap_is_subset (kh_value (island_marks, trg_pos), -kh_value (island_marks, src_pos)); +return island_bitmap_is_subset (trg, src); }int island_delta_cmp (const struct object_id *a,const struct object_id *b) { -khiter_t a_pos, b_pos; -struct island_bitmap *a_bitmap =NULL , *b_bitmap =NULL ; +struct island_bitmap *a_bitmap, *b_bitmap;if (!island_marks)return 0 ; - a_pos =kh_get_oid_map (island_marks, *a); -if (a_pos <kh_end (island_marks)) - a_bitmap =kh_value (island_marks, a_pos); - - b_pos =kh_get_oid_map (island_marks, *b); -if (b_pos <kh_end (island_marks)) - b_bitmap =kh_value (island_marks, b_pos); + a_bitmap =oidtree_get (island_marks, a); + b_bitmap =oidtree_get (island_marks, b);if (a_bitmap) {if (!b_bitmap || !island_bitmap_is_subset (a_bitmap, b_bitmap))
@@ -149,30 +144,28 @@ int island_delta_cmp(const struct object_id *a, const struct object_id *b)static struct island_bitmap *create_or_get_island_marks (struct object *obj) { -khiter_t pos; -int hash_ret; +void **val; +size_t n =sizeof (struct island_bitmap *); - pos =kh_put_oid_map (island_marks, obj->oid, &hash_ret); -if (hash_ret) -kh_value (island_marks, pos) =island_bitmap_new (NULL ); +if (oidtree_put (island_marks, &obj->oid, &val, n)) + *val =island_bitmap_new (NULL ); -return kh_value (island_marks, pos); +return *val; }static void set_island_marks (struct object *obj,struct island_bitmap *marks) {struct island_bitmap *b; -khiter_t pos; -int hash_ret; +void **val; +size_t n =sizeof (struct island_bitmap *); - pos =kh_put_oid_map (island_marks, obj->oid, &hash_ret); -if (hash_ret) { +if (oidtree_put (island_marks, &obj->oid, &val, n)) {/* * We don't have one yet; make a copy-on-write of the * parent. */ marks->refcount++; -kh_value (island_marks, pos) = marks; + *val = marks;return ; }
@@ -180,10 +173,10 @@ static void set_island_marks(struct object *obj, struct island_bitmap *marks)* We do have it. Make sure we split any copy-on-write before * updating. */ - b =kh_value (island_marks, pos); + b = *val;if (b->refcount >1 ) { b->refcount--; - b =kh_value (island_marks, pos) =island_bitmap_new (b); + *val = b =island_bitmap_new (b); }island_bitmap_or (b, marks); }
@@ -275,14 +268,11 @@ void resolve_tree_islands(struct repository *r,struct tree *tree;struct tree_desc desc;struct name_entry entry; -khiter_t pos; - pos =kh_get_oid_map (island_marks, ent->idx.oid); -if (pos >=kh_end (island_marks)) + root_marks =oidtree_get (island_marks, &ent->idx.oid); +if (!root_marks)continue ; - root_marks =kh_value (island_marks, pos); - tree =lookup_tree (r, &ent->idx.oid);if (!tree ||parse_tree (tree) <0 )die (_ ("bad tree object %s" ),oid_to_hex (&ent->idx.oid));
@@ -485,7 +475,8 @@ void load_delta_islands(struct repository *r, int progress) {struct island_load_data ild = {0 }; - island_marks =kh_init_oid_map (); +oidtree_init (&island_marks_storage); + island_marks = &island_marks_storage;git_config (island_config_callback, &ild); ild.remote_islands =kh_init_str ();
@@ -500,11 +491,11 @@ void load_delta_islands(struct repository *r, int progress)void propagate_island_marks (struct commit *commit) { -khiter_t pos =kh_get_oid_map (island_marks, commit->object.oid); +struct island_bitmap *root_marks; -if (pos <kh_end (island_marks)) { + root_marks =oidtree_get (island_marks, &commit->object.oid); +if (root_marks) {struct commit_list *p; -struct island_bitmap *root_marks =kh_value (island_marks, pos);parse_commit (commit);set_island_marks (&get_commit_tree (commit)->object, root_marks);
@@ -522,16 +513,13 @@ int compute_pack_layers(struct packing_data *to_pack)for (i =0 ; i < to_pack->nr_objects; ++i) {struct object_entry *entry = &to_pack->objects[i]; -khiter_t pos =kh_get_oid_map (island_marks, entry->idx.oid); +struct island_bitmap *bitmap;oe_set_layer (to_pack, entry,1 ); -if (pos <kh_end (island_marks)) { -struct island_bitmap *bitmap =kh_value (island_marks, pos); - -if (island_bitmap_get (bitmap, island_counter_core)) -oe_set_layer (to_pack, entry,0 ); - } + bitmap =oidtree_get (island_marks, &entry->idx.oid); +if (bitmap &&island_bitmap_get (bitmap, island_counter_core)) +oe_set_layer (to_pack, entry,0 ); }return 2 ;
oidtree.c +40 -12
81 lines not on this page · raw message
oidtree.h +15 -0
@@ -12,6 +12,8 @@ struct oidtree {void oidtree_init (struct oidtree *);void oidtree_clear (struct oidtree *); + +/* oid_set-like API */ void oidtree_insert (struct oidtree *,const struct object_id *);int oidtree_contains (struct oidtree *,const struct object_id *);
@@ -19,4 +21,17 @@ typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *data);void oidtree_each (struct oidtree *,const struct object_id *,size_t oidhexsz,oidtree_iter ,void *data); +/* oid_map-like API */ + +/* returns a pointer to the data payload associated with object_id */ +void *oidtree_get (struct oidtree *,const struct object_id *); + +/* +* points @p to the destination of the value +* @n must be consistent for the entire oidtree +* returns true if a new oidtree node was created, +* returns false if reusing an existing oidtree node +*/ +int oidtree_put (struct oidtree *,const struct object_id *, +void ***p,size_t n);#endif /* OIDTREE_H */
[2] https://80x24.org/mwrap-perl.git
# after install, run gc under mwrap-perl with backtrace 10
MWRAP=socket_dir:/tmp/mwrap,bt:10 mwrap-perl git gc# recommended: use GNU addr2line 2.39+ (Aug 2022) for +OFFSET decoding
# start HTTP reverse proxy
ADDR2LINE='/path/to/addr2line -p -f -i' \
mwrap-rproxy --socket-dir=/tmp/mwrap
# the per-PID each/2000 URLs can get really expensive for browsers # even w3m struggles:
w3m http://0:5000/ # follow per-PID links
Re: pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]
Quoted 1 line · Eric Wong
[1] WIP oidtree map, but I feel like I forgot C, again :<
Well, it hasn't crashed. It's just much slower compared to khash.
I'm thinking `struct object_id' should be pooled+deduplicated like hash keys in the Perl/Ruby interpreters and we'd pass 4/8-byte pointers instead of 36-byte structs.
Re: pack-objects memory use observations [was: [PATCH] delta-islands: free island-related data after use]
Quoted 4 lines · Eric Wong
Quoted 1 line · Eric Wong
[1] WIP oidtree map, but I feel like I forgot C, again :<
Well, it hasn't crashed. It's just much slower compared to khash.
I experimented a bit with critbit trees several years ago, mostly for the main obj_hash. I could never make them faster than hashing. I think part of it is that "hashing" an oid is basically free, since we just pull off the first 4 bytes. And we keep our table factors quite low. Whereas for trie structures, even though the big-O behavior is good, there's a lot of branching that ends up being slow.
Quoted 3 lines
I'm thinking `struct
object_id' should be pooled+deduplicated like hash keys in the Perl/Ruby interpreters and we'd pass 4/8-byte pointers instead of 36-byte structs.
I think that could work, but it feels like it would be pretty major surgery, given how often object_ids appear in the code.
-Peff