[v2,07/10] strmap: enable faster clearing and reusing of strmaps

Commit Message

Elijah Newren Oct. 13, 2020, 12:40 a.m. UTC

From: Elijah Newren <[e-mail]>

When strmaps are used heavily, such as is done by my new merge-ort
algorithm, and strmaps need to be cleared but then re-used (because of
e.g. picking multiple commits to cherry-pick, or due to a recursive
merge having several different merges while recursing), free-ing and
reallocating map->table repeatedly can add up in time, especially since
it will likely be reallocated to a much smaller size but the previous
merge provides a good guide to the right size to use for the next merge.

Introduce strmap_partial_clear() to take advantage of this type of
situation; it will act similar to strmap_clear() except that
map->table's entries are zeroed instead of map->table being free'd.
Making use of this function reduced the cost of reset_maps() by about
20% in mert-ort, and dropped the overall runtime of my rebase testcase
by just under 2%.

Signed-off-by: Elijah Newren <[e-mail]>
---
 strmap.c | 6 ++++++
 strmap.h | 6 ++++++
 2 files changed, 12 insertions(+)

Comments

Jeff King Oct. 30, 2020, 2:27 p.m. UTC | #1

On Tue, Oct 13, 2020 at 12:40:47AM +0000, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <[e-mail]>
> 
> When strmaps are used heavily, such as is done by my new merge-ort
> algorithm, and strmaps need to be cleared but then re-used (because of
> e.g. picking multiple commits to cherry-pick, or due to a recursive
> merge having several different merges while recursing), free-ing and
> reallocating map->table repeatedly can add up in time, especially since
> it will likely be reallocated to a much smaller size but the previous
> merge provides a good guide to the right size to use for the next merge.
> 
> Introduce strmap_partial_clear() to take advantage of this type of
> situation; it will act similar to strmap_clear() except that
> map->table's entries are zeroed instead of map->table being free'd.
> Making use of this function reduced the cost of reset_maps() by about
> 20% in mert-ort, and dropped the overall runtime of my rebase testcase
> by just under 2%.

Oh, these were the real numbers I was looking for earlier. :)

Of course it's a little confusing because reset_maps() doesn't exist yet
in the code base this is being applied on, but I can live with that.

> +/*
> + * Similar to strmap_clear() but leaves map->map->table allocated and
> + * pre-sized so that subsequent uses won't need as many rehashings.
> + */
> +void strmap_partial_clear(struct strmap *map, int free_values);

Oh good, you anticipated my free_values suggestion from earlier. But...

> +void strmap_partial_clear(struct strmap *map, int free_util)
> +{
> +	strmap_free_entries_(map, free_util);
> +	hashmap_partial_clear(&map->map);
> +}

...the implementation didn't catch up.

Other than that the patch looks obviously correct.

-Peff

Patch

diff --git a/strmap.c b/strmap.c
index 909b9fbedf..47cbf11ec7 100644
--- a/strmap.c
+++ b/strmap.c
@@ -64,6 +64,12 @@  void strmap_clear(struct strmap *map, int free_util)
 	hashmap_free(&map->map);
 }
 
+void strmap_partial_clear(struct strmap *map, int free_util)
+{
+	strmap_free_entries_(map, free_util);
+	hashmap_partial_clear(&map->map);
+}
+
 void *strmap_put(struct strmap *map, const char *str, void *data)
 {
 	struct strmap_entry *entry = find_strmap_entry(map, str);
diff --git a/strmap.h b/strmap.h
index e49d020970..5bb7650d65 100644
--- a/strmap.h
+++ b/strmap.h
@@ -34,6 +34,12 @@  void strmap_ocd_init(struct strmap *map,
  */
 void strmap_clear(struct strmap *map, int free_values);
 
+/*
+ * Similar to strmap_clear() but leaves map->map->table allocated and
+ * pre-sized so that subsequent uses won't need as many rehashings.
+ */
+void strmap_partial_clear(struct strmap *map, int free_values);
+
 /*
  * Insert "str" into the map, pointing to "data".
  *