[PATCH v3 08/13] strmap: enable faster clearing and reusing of strmaps

From: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>
Date: Nov 2, 2020, 18:55 UTC
Message-ID: <ea942eb8035686af4b284e66affa3a0a1d2a5b0c.1604343314.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.835.v3.git.git.1604343313.gitgitgadget@gmail.com>

From: Elijah Newren <newren@gmail.com>

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 clear_or_reinit_internal_opts() by about 20% in mert-ort, and dropped the overall runtime of my rebase testcase by just under 2%.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 strmap.c | 6 ++++++
 strmap.h | 6 ++++++
 2 files changed, 12 insertions(+)

diff --git a/strmap.c b/strmap.c
index 829f1bc095..c410c5241a 100644
--- a/strmap.c
+++ b/strmap.c
@@ -64,6 +64,12 @@ void strmap_clear(struct strmap *map, int free_values)
 	hashmap_clear(&map->map);
 }
 
+void strmap_partial_clear(struct strmap *map, int free_values)
+{
+	strmap_free_entries_(map, free_values);
+	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 ee4307cca5..10b4642860 100644
--- a/strmap.h
+++ b/strmap.h
@@ -42,6 +42,12 @@ void strmap_init_with_options(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".
  *

-- 
gitgitgadget