{"thread":{"id":"54087","subject":"[PATCH 0/5] Add struct strmap and associated utility functions","startedAt":"2020-08-21T18:52:43Z","lastAt":"2020-11-11T20:35:15Z","messageCount":144,"participants":["Elijah Newren via GitGitGadget","Jeff King","Elijah Newren","Junio C Hamano","Phillip Wood","Chris Torek"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"404183","messageId":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","threadId":"54087","inReplyTo":null,"subject":"[PATCH 0/5] Add struct strmap and associated utility functions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-08-21T18:52:24Z","receivedAt":"2020-08-21T18:52:43Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Here I introduce a new strmap type, which my new merge backed, merge-ort,\nuses heavily. (I also made significant use of it in my changes to\ndiffcore-rename). This strmap type was based on Peff's proposal from a\ncouple years ago[1], but has additions that I made as I used it. I also\nstart the series off with a quick documentation improvement to hashmap.c to\ndifferentiate between hashmap_free() and hashmap_free_entries(), since I\npersonally had difficulty understanding them and it affects how\nstrmap_clear()/strmap_free() are written.\n\nThe biggest issue I know about currently concerns the convenience functions\nfor a string->integer mapping. I wanted such a mapping that didn't need to\nallocate an extra int but instead works by just type-casting the void*\npointer to an int instead. That all seems to work, but I needed a separate\nname for that type, and the problem is that I couldn't come up with a good\none as you'll see in the last patch. Suggestions for better naming are very\nmuch welcome. As are, of course, suggestions for other API or implementation\nimprovements.\n\n[1] \nhttps://lore.kernel.org/git/20180906191203.GA26184@sigill.intra.peff.net/\n\nElijah Newren (5):\n hashmap: add usage documentation explaining hashmap_free[_entries]()\n strmap: new utility functions\n strmap: add more utility functions\n strmap: add strdup_strings option\n strmap: add functions facilitating use as a string->int map\n\n Makefile | 1 +\n hashmap.h | 27 +++++++++++-\n strmap.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n strmap.h | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 275 insertions(+), 2 deletions(-)\n create mode 100644 strmap.c\n create mode 100644 strmap.h\n\n\nbase-commit: 675a4aaf3b226c0089108221b96559e0baae5de9\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-835%2Fnewren%2Fstrmap-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-835/newren/strmap-v1\nPull-Request: https://github.com/git/git/pull/835\n-- \ngitgitgadget\n"},{"id":"404184","messageId":"5bda171d0c1562573800d4bcbfac4799f01d9c20.1598035949.git.gitgitgadget@gmail.com","threadId":"54087","inReplyTo":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","subject":"[PATCH 3/5] strmap: add more utility functions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-08-21T18:52:27Z","receivedAt":"2020-08-21T18:52:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThis adds a number of additional convienence functions I want/need:\n * strmap_empty()\n * strmap_get_size()\n * strmap_remove()\n * strmap_for_each_entry()\n * strmap_free()\n * strmap_get_item()\n\nI suspect the first four are self-explanatory.\n\nstrmap_free() differs from strmap_clear() in that the data structure is\nnot reusable after it is called; strmap_clear() is not sufficient for\nthe API because without strmap_free() we will leak memory.\n\nstrmap_get_item() is similar to strmap_get() except that instead of just\nreturning the void* value that the string maps to, it returns the\nstring_list_item that contains both the string and the void* value (or\nNULL if the string isn't in the map). This is helpful because it avoids\nmultiple lookups, e.g. in some cases a caller would need to call:\n * strmap_contains() to check that the map has an entry for the string\n * strmap_get() to get the void* value\n * \n * strmap_put() to update/overwrite the value\nIf the void* pointer returned really is a pointer, then the last step is\nunnecessary, but if the void* pointer is just cast to an integer then\nstrmap_put() will be needed. In contrast, one can call strmap_get_item()\nand then:\n * check if the string was in the map by whether the pointer is NULL\n * access the value via item->util\n * directly update item->util\nmeaning that we can replace two or three hash table lookups with one.\n\nSigned-off-by: Elijah Newren \n---\n strmap.c | 35 ++++++++++++++++++++++++++++++-----\n strmap.h | 43 +++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 73 insertions(+), 5 deletions(-)\n\ndiff --git a/strmap.c b/strmap.c\nindex 1c9fdb3b1e..a4bfffcd8b 100644\n--- a/strmap.c\n+++ b/strmap.c\n@@ -27,7 +27,7 @@ void strmap_init(struct strmap *map)\n \thashmap_init(&map->map, cmp_str_entry, NULL, 0);\n }\n \n-void strmap_clear(struct strmap *map, int free_util)\n+void strmap_free(struct strmap *map, int free_util)\n {\n \tstruct hashmap_iter iter;\n \tstruct str_entry *e;\n@@ -35,12 +35,19 @@ void strmap_clear(struct strmap *map, int free_util)\n \tif (!map)\n \t\treturn;\n \n-\thashmap_for_each_entry(&map->map, &iter, e, ent /* member name */) {\n-\t\tfree(e->item.string);\n-\t\tif (free_util)\n-\t\t\tfree(e->item.util);\n+\tif (free_util) {\n+\t\thashmap_for_each_entry(&map->map, &iter, e, ent) {\n+\t\t\tfree(e->item.string);\n+\t\t\tif (free_util)\n+\t\t\t\tfree(e->item.util);\n+\t\t}\n \t}\n \thashmap_free_entries(&map->map, struct str_entry, ent);\n+}\n+\n+void strmap_clear(struct strmap *map, int free_util)\n+{\n+\tstrmap_free(map, free_util);\n \tstrmap_init(map);\n }\n \n@@ -69,6 +76,13 @@ void *strmap_put(struct strmap *map, const char *str, void *data)\n \treturn old;\n }\n \n+struct string_list_item *strmap_get_item(struct strmap *map,\n+\t\t\t\t\t const char *str)\n+{\n+\tstruct str_entry *entry = find_str_entry(map, str);\n+\treturn entry ? &entry->item : NULL;\n+}\n+\n void *strmap_get(struct strmap *map, const char *str)\n {\n \tstruct str_entry *entry = find_str_entry(map, str);\n@@ -79,3 +93,14 @@ int strmap_contains(struct strmap *map, const char *str)\n {\n \treturn find_str_entry(map, str) != NULL;\n }\n+\n+void strmap_remove(struct strmap *map, const char *str, int free_util)\n+{\n+\tstruct str_entry entry, *ret;\n+\thashmap_entry_init(&entry.ent, strhash(str));\n+\tentry.item.string = (char *)str;\n+\tret = hashmap_remove_entry(&map->map, &entry, ent, NULL);\n+\tif (ret && free_util)\n+\t\tfree(ret->item.util);\n+\tfree(ret);\n+}\ndiff --git a/strmap.h b/strmap.h\nindex eb5807f6fa..45d0a4f714 100644\n--- a/strmap.h\n+++ b/strmap.h\n@@ -21,6 +21,11 @@ void strmap_init(struct strmap *map);\n /*\n * Remove all entries from the map, releasing any allocated resources.\n */\n+void strmap_free(struct strmap *map, int free_values);\n+\n+/*\n+ * Same as calling strmap_free() followed by strmap_init().\n+ */\n void strmap_clear(struct strmap *map, int free_values);\n \n /*\n@@ -32,6 +37,12 @@ void strmap_clear(struct strmap *map, int free_values);\n */\n void *strmap_put(struct strmap *map, const char *str, void *data);\n \n+/*\n+ * Return the string_list_item mapped by \"str\", or NULL if there is not such\n+ * an item in map.\n+ */\n+struct string_list_item *strmap_get_item(struct strmap *map, const char *str);\n+\n /*\n * Return the data pointer mapped by \"str\", or NULL if the entry does not\n * exist.\n@@ -44,4 +55,36 @@ void *strmap_get(struct strmap *map, const char *str);\n */\n int strmap_contains(struct strmap *map, const char *str);\n \n+/*\n+ * Remove the given entry from the strmap. If the string isn't in the\n+ * strmap, the map is not altered.\n+ */\n+void strmap_remove(struct strmap *map, const char *str, int free_value);\n+\n+/*\n+ * Return whether the strmap is empty.\n+ */\n+static inline int strmap_empty(struct strmap *map)\n+{\n+\treturn hashmap_get_size(&map->map) == 0;\n+}\n+\n+/*\n+ * Return how many entries the strmap has.\n+ */\n+static inline unsigned int strmap_get_size(struct strmap *map)\n+{\n+\treturn hashmap_get_size(&map->map);\n+}\n+\n+/*\n+ * iterate through @map using @iter, @var is a pointer to a type str_entry\n+ */\n+#define strmap_for_each_entry(mystrmap, iter, var)\t\\\n+\tfor (var = hashmap_iter_first_entry_offset(&(mystrmap)->map, iter, \\\n+\t\t\t\t\t\t OFFSETOF_VAR(var, ent)); \\\n+\t\tvar; \\\n+\t\tvar = hashmap_iter_next_entry_offset(iter, \\\n+\t\t\t\t\t\tOFFSETOF_VAR(var, ent)))\n+\n #endif /* STRMAP_H */\n-- \ngitgitgadget\n\n"},{"id":"404185","messageId":"b295e9393a8998b3b9263ab7cd195907d4002e36.1598035949.git.gitgitgadget@gmail.com","threadId":"54087","inReplyTo":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","subject":"[PATCH 1/5] hashmap: add usage documentation explaining hashmap_free[_entries]()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-08-21T18:52:25Z","receivedAt":"2020-08-21T18:52:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe existence of hashmap_free() and hashmap_free_entries() confused me,\nand the docs weren't clear enough. I had to consult other source code\nexamples and the implementation. Add a brief note to clarify,\nespecially since hashmap_clear*() variants may be added in the future.\n\nSigned-off-by: Elijah Newren \n---\n hashmap.h | 27 +++++++++++++++++++++++++--\n 1 file changed, 25 insertions(+), 2 deletions(-)\n\ndiff --git a/hashmap.h b/hashmap.h\nindex ef220de4c6..a2f4adc1b3 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -236,13 +236,36 @@ void hashmap_init(struct hashmap *map,\n void hashmap_free_(struct hashmap *map, ssize_t offset);\n \n /*\n- * Frees a hashmap structure and allocated memory, leaves entries undisturbed\n+ * Frees a hashmap structure and allocated memory for the table, but does not\n+ * free the entries nor anything they point to.\n+ *\n+ * Usage note:\n+ *\n+ * Many callers will need to iterate over all entries and free the data each\n+ * entry points to; in such a case, they can free the entry itself while at it.\n+ * Thus, you might see:\n+ * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {\n+ * free(e->somefield);\n+ * free(e);\n+ * }\n+ * hashmap_free(map);\n+ * instead of\n+ * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {\n+ * free(e->somefield);\n+ * }\n+ * hashmap_free_entries(map, struct my_entry_struct, hashmap_entry_name);\n+ * to avoid the implicit extra loop over the entries. However, if there are\n+ * no special fields in your entry that need to be freed beyond the entry\n+ * itself, it is probably simpler to avoid the explicit loop and just call\n+ * hashmap_free_entries().\n */\n #define hashmap_free(map) hashmap_free_(map, -1)\n \n /*\n * Frees @map and all entries. @type is the struct type of the entry\n- * where @member is the hashmap_entry struct used to associate with @map\n+ * where @member is the hashmap_entry struct used to associate with @map.\n+ *\n+ * See usage note above hashmap_free().\n */\n #define hashmap_free_entries(map, type, member) \\\n \thashmap_free_(map, offsetof(type, member));\n-- \ngitgitgadget\n\n"},{"id":"404186","messageId":"418975b46039f63476852a868ca6221244b5d88e.1598035949.git.gitgitgadget@gmail.com","threadId":"54087","inReplyTo":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","subject":"[PATCH 5/5] strmap: add functions facilitating use as a string->int map","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-08-21T18:52:29Z","receivedAt":"2020-08-21T18:52:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAlthough strmap could be used as a string->int map, one either had to\nallocate an int for every entry and then deallocate later, or one had to\ndo a bunch of casting between (void*) and (intptr_t).\n\nAdd some special functions that do the casting. Also, rename put->set\nfor such wrapper functions since 'put' implied there may be some\ndeallocation needed if the string was already found in the map, which\nisn't the case when we're storing an int value directly in the void*\nslot instead of using the void* slot as a pointer to data.\n\nA note on the name: strintmap looks and sounds pretty lame to me, but\nafter trying to come up with something better and having no luck, I\nfigured I'd just go with it for a while and then at some point some\nbetter and obvious name would strike me and I could replace it. Several\nmonths later, I still don't have a better name. Hopefully someone else\nhas one.\n\nSigned-off-by: Elijah Newren \n---\n strmap.c | 11 +++++++++++\n strmap.h | 32 ++++++++++++++++++++++++++++++++\n 2 files changed, 43 insertions(+)\n\ndiff --git a/strmap.c b/strmap.c\nindex 03eb6af45d..cbb99f4030 100644\n--- a/strmap.c\n+++ b/strmap.c\n@@ -113,3 +113,14 @@ void strmap_remove(struct strmap *map, const char *str, int free_util)\n \t\tfree(ret->item.util);\n \tfree(ret);\n }\n+\n+void strintmap_incr(struct strmap *map, const char *str, intptr_t amt)\n+{\n+\tstruct str_entry *entry = find_str_entry(map, str);\n+\tif (entry) {\n+\t\tintptr_t *whence = (intptr_t*)&entry->item.util;\n+\t\t*whence += amt;\n+\t}\n+\telse\n+\t\tstrintmap_set(map, str, amt);\n+}\ndiff --git a/strmap.h b/strmap.h\nindex 28a98c5a4b..5d9dd3ef58 100644\n--- a/strmap.h\n+++ b/strmap.h\n@@ -88,4 +88,36 @@ static inline unsigned int strmap_get_size(struct strmap *map)\n \t\tvar = hashmap_iter_next_entry_offset(iter, \\\n \t\t\t\t\t\tOFFSETOF_VAR(var, ent)))\n \n+/*\n+ * Helper functions for using strmap as map of string -> int, using the void*\n+ * field to store the int instead of allocating an int and having the void*\n+ * member point to the allocated int.\n+ */\n+\n+static inline int strintmap_get(struct strmap *map, const char *str,\n+\t\t\t\tint default_value)\n+{\n+\tstruct string_list_item *result = strmap_get_item(map, str);\n+\tif (!result)\n+\t\treturn default_value;\n+\treturn (intptr_t)result->util;\n+}\n+\n+static inline void strintmap_set(struct strmap *map, const char *str, intptr_t v)\n+{\n+\tstrmap_put(map, str, (void *)v);\n+}\n+\n+void strintmap_incr(struct strmap *map, const char *str, intptr_t amt);\n+\n+static inline void strintmap_clear(struct strmap *map)\n+{\n+\tstrmap_clear(map, 0);\n+}\n+\n+static inline void strintmap_free(struct strmap *map)\n+{\n+\tstrmap_free(map, 0);\n+}\n+\n #endif /* STRMAP_H */\n-- \ngitgitgadget\n"},{"id":"404187","messageId":"a86fd5fdcc47baf85046eb07257f4db9f9498084.1598035949.git.gitgitgadget@gmail.com","threadId":"54087","inReplyTo":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","subject":"[PATCH 2/5] strmap: new utility functions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-08-21T18:52:26Z","receivedAt":"2020-08-21T18:52:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd strmap as a new struct and associated utility functions,\nspecifically for hashmaps that map strings to some value. The API is\ntaken directly from Peff's proposal at\nhttps://lore.kernel.org/git/20180906191203.GA26184@sigill.intra.peff.net/\n\nPeff only included the header, not the implementation, so it isn't clear what\nthe structure was he was going to use for the hash entries. Instead of having\nmy str_entry struct have three subfields (the hashmap_entry, the string, and\nthe void* value), I made it only have two -- the hashmap_entry and a\nstring_list_item, for two reasons:\n\n 1) a strmap is often the data structure we want where string_list has\n been used in the past. Using the same building block for\n individual entries in both makes it easier to adopt and reuse\n parts of the string_list API in strmap.\n\n 2) In some cases, after doing lots of other work, I want to be able\n to iterate over the items in my strmap in sorted order. hashmap\n obviously doesn't support that, but I wanted to be able to export\n the strmap to a string_list easily and then use its functions.\n (Note: I do not need the data structure to both be sorted and have\n efficient lookup at all times. If I did, I might use a B-tree\n instead, as suggested by brian in response to Peff in the thread\n noted above. In my case, most strmaps will never need sorting, but\n in one special case at the very end of a bunch of other work I want\n to iterate over the items in sorted order without doing any more\n lookups afterward.)\n\nAlso, I removed the STRMAP_INIT macro, since it cannot be used to\ncorrectly initialize a strmap; the underlying hashmap needs a call to\nhashmap_init() to allocate the hash table first.\n\nSigned-off-by: Elijah Newren \n---\n Makefile | 1 +\n strmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n strmap.h | 47 ++++++++++++++++++++++++++++++++\n 3 files changed, 129 insertions(+)\n create mode 100644 strmap.c\n create mode 100644 strmap.h\n\ndiff --git a/Makefile b/Makefile\nindex 65f8cfb236..0da15a9ee5 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -988,6 +988,7 @@ LIB_OBJS += strbuf.o\n LIB_OBJS += strvec.o\n LIB_OBJS += streaming.o\n LIB_OBJS += string-list.o\n+LIB_OBJS += strmap.o\n LIB_OBJS += sub-process.o\n LIB_OBJS += submodule-config.o\n LIB_OBJS += submodule.o\ndiff --git a/strmap.c b/strmap.c\nnew file mode 100644\nindex 0000000000..1c9fdb3b1e\n--- /dev/null\n+++ b/strmap.c\n@@ -0,0 +1,81 @@\n+#include \"git-compat-util.h\"\n+#include \"strmap.h\"\n+\n+static int cmp_str_entry(const void *hashmap_cmp_fn_data,\n+\t\t\t const struct hashmap_entry *entry1,\n+\t\t\t const struct hashmap_entry *entry2,\n+\t\t\t const void *keydata)\n+{\n+\tconst struct str_entry *e1, *e2;\n+\n+\te1 = container_of(entry1, const struct str_entry, ent);\n+\te2 = container_of(entry2, const struct str_entry, ent);\n+\treturn strcmp(e1->item.string, e2->item.string);\n+}\n+\n+static struct str_entry *find_str_entry(struct strmap *map,\n+\t\t\t\t\tconst char *str)\n+{\n+\tstruct str_entry entry;\n+\thashmap_entry_init(&entry.ent, strhash(str));\n+\tentry.item.string = (char *)str;\n+\treturn hashmap_get_entry(&map->map, &entry, ent, NULL);\n+}\n+\n+void strmap_init(struct strmap *map)\n+{\n+\thashmap_init(&map->map, cmp_str_entry, NULL, 0);\n+}\n+\n+void strmap_clear(struct strmap *map, int free_util)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct str_entry *e;\n+\n+\tif (!map)\n+\t\treturn;\n+\n+\thashmap_for_each_entry(&map->map, &iter, e, ent /* member name */) {\n+\t\tfree(e->item.string);\n+\t\tif (free_util)\n+\t\t\tfree(e->item.util);\n+\t}\n+\thashmap_free_entries(&map->map, struct str_entry, ent);\n+\tstrmap_init(map);\n+}\n+\n+/*\n+ * Insert \"str\" into the map, pointing to \"data\". A copy of \"str\" is made, so\n+ * it does not need to persist after the this function is called.\n+ *\n+ * If an entry for \"str\" already exists, its data pointer is overwritten, and\n+ * the original data pointer returned. Otherwise, returns NULL.\n+ */\n+void *strmap_put(struct strmap *map, const char *str, void *data)\n+{\n+\tstruct str_entry *entry = find_str_entry(map, str);\n+\tvoid *old = NULL;\n+\n+\tif (entry) {\n+\t\told = entry->item.util;\n+\t\tentry->item.util = data;\n+\t} else {\n+\t\tentry = xmalloc(sizeof(*entry));\n+\t\thashmap_entry_init(&entry->ent, strhash(str));\n+\t\tentry->item.string = strdup(str);\n+\t\tentry->item.util = data;\n+\t\thashmap_add(&map->map, &entry->ent);\n+\t}\n+\treturn old;\n+}\n+\n+void *strmap_get(struct strmap *map, const char *str)\n+{\n+\tstruct str_entry *entry = find_str_entry(map, str);\n+\treturn entry ? entry->item.util : NULL;\n+}\n+\n+int strmap_contains(struct strmap *map, const char *str)\n+{\n+\treturn find_str_entry(map, str) != NULL;\n+}\ndiff --git a/strmap.h b/strmap.h\nnew file mode 100644\nindex 0000000000..eb5807f6fa\n--- /dev/null\n+++ b/strmap.h\n@@ -0,0 +1,47 @@\n+#ifndef STRMAP_H\n+#define STRMAP_H\n+\n+#include \"hashmap.h\"\n+#include \"string-list.h\"\n+\n+struct strmap {\n+\tstruct hashmap map;\n+};\n+\n+struct str_entry {\n+\tstruct hashmap_entry ent;\n+\tstruct string_list_item item;\n+};\n+\n+/*\n+ * Initialize an empty strmap\n+ */\n+void strmap_init(struct strmap *map);\n+\n+/*\n+ * Remove all entries from the map, releasing any allocated resources.\n+ */\n+void strmap_clear(struct strmap *map, int free_values);\n+\n+/*\n+ * Insert \"str\" into the map, pointing to \"data\". A copy of \"str\" is made, so\n+ * it does not need to persist after the this function is called.\n+ *\n+ * If an entry for \"str\" already exists, its data pointer is overwritten, and\n+ * the original data pointer returned. Otherwise, returns NULL.\n+ */\n+void *strmap_put(struct strmap *map, const char *str, void *data);\n+\n+/*\n+ * Return the data pointer mapped by \"str\", or NULL if the entry does not\n+ * exist.\n+ */\n+void *strmap_get(struct strmap *map, const char *str);\n+\n+/*\n+ * Return non-zero iff \"str\" is present in the map. This differs from\n+ * strmap_get() in that it can distinguish entries with a NULL data pointer.\n+ */\n+int strmap_contains(struct strmap *map, const char *str);\n+\n+#endif /* STRMAP_H */\n-- \ngitgitgadget\n\n"},{"id":"404188","messageId":"b3095d97d8ee9d6576292731cc100492e7c64f13.1598035949.git.gitgitgadget@gmail.com","threadId":"54087","inReplyTo":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","subject":"[PATCH 4/5] strmap: add strdup_strings option","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-08-21T18:52:28Z","receivedAt":"2020-08-21T18:53:08Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nJust as it is sometimes useful for string_list to duplicate and take\nownership of memory management of the strings it contains, the same is\nsometimes true for strmaps as well. Add the same flag from string_list\nto strmap.\n\nSigned-off-by: Elijah Newren \n---\n strmap.c | 23 ++++++++++++++++-------\n strmap.h | 9 +++++----\n 2 files changed, 21 insertions(+), 11 deletions(-)\n\ndiff --git a/strmap.c b/strmap.c\nindex a4bfffcd8b..03eb6af45d 100644\n--- a/strmap.c\n+++ b/strmap.c\n@@ -22,9 +22,10 @@ static struct str_entry *find_str_entry(struct strmap *map,\n \treturn hashmap_get_entry(&map->map, &entry, ent, NULL);\n }\n \n-void strmap_init(struct strmap *map)\n+void strmap_init(struct strmap *map, int strdup_strings)\n {\n \thashmap_init(&map->map, cmp_str_entry, NULL, 0);\n+\tmap->strdup_strings = strdup_strings;\n }\n \n void strmap_free(struct strmap *map, int free_util)\n@@ -35,9 +36,10 @@ void strmap_free(struct strmap *map, int free_util)\n \tif (!map)\n \t\treturn;\n \n-\tif (free_util) {\n+\tif (map->strdup_strings || free_util) {\n \t\thashmap_for_each_entry(&map->map, &iter, e, ent) {\n-\t\t\tfree(e->item.string);\n+\t\t\tif (map->strdup_strings)\n+\t\t\t\tfree(e->item.string);\n \t\t\tif (free_util)\n \t\t\t\tfree(e->item.util);\n \t\t}\n@@ -48,12 +50,11 @@ void strmap_free(struct strmap *map, int free_util)\n void strmap_clear(struct strmap *map, int free_util)\n {\n \tstrmap_free(map, free_util);\n-\tstrmap_init(map);\n+\tstrmap_init(map, map->strdup_strings);\n }\n \n /*\n- * Insert \"str\" into the map, pointing to \"data\". A copy of \"str\" is made, so\n- * it does not need to persist after the this function is called.\n+ * Insert \"str\" into the map, pointing to \"data\".\n *\n * If an entry for \"str\" already exists, its data pointer is overwritten, and\n * the original data pointer returned. Otherwise, returns NULL.\n@@ -69,7 +70,13 @@ void *strmap_put(struct strmap *map, const char *str, void *data)\n \t} else {\n \t\tentry = xmalloc(sizeof(*entry));\n \t\thashmap_entry_init(&entry->ent, strhash(str));\n-\t\tentry->item.string = strdup(str);\n+\t\t/*\n+\t\t * We won't modify entry->item.string so it really should be\n+\t\t * const, but changing string_list_item to use a const char *\n+\t\t * is a bit too big of a change at this point.\n+\t\t */\n+\t\tentry->item.string =\n+\t\t\tmap->strdup_strings ? xstrdup(str) : (char *)str;\n \t\tentry->item.util = data;\n \t\thashmap_add(&map->map, &entry->ent);\n \t}\n@@ -100,6 +107,8 @@ void strmap_remove(struct strmap *map, const char *str, int free_util)\n \thashmap_entry_init(&entry.ent, strhash(str));\n \tentry.item.string = (char *)str;\n \tret = hashmap_remove_entry(&map->map, &entry, ent, NULL);\n+\tif (map->strdup_strings)\n+\t\tfree(ret->item.string);\n \tif (ret && free_util)\n \t\tfree(ret->item.util);\n \tfree(ret);\ndiff --git a/strmap.h b/strmap.h\nindex 45d0a4f714..28a98c5a4b 100644\n--- a/strmap.h\n+++ b/strmap.h\n@@ -6,6 +6,7 @@\n \n struct strmap {\n \tstruct hashmap map;\n+\tunsigned int strdup_strings:1;\n };\n \n struct str_entry {\n@@ -14,9 +15,10 @@ struct str_entry {\n };\n \n /*\n- * Initialize an empty strmap\n+ * Initialize the members of the strmap, set `strdup_strings`\n+ * member according to the value of the second parameter.\n */\n-void strmap_init(struct strmap *map);\n+void strmap_init(struct strmap *map, int strdup_strings);\n \n /*\n * Remove all entries from the map, releasing any allocated resources.\n@@ -29,8 +31,7 @@ void strmap_free(struct strmap *map, int free_values);\n void strmap_clear(struct strmap *map, int free_values);\n \n /*\n- * Insert \"str\" into the map, pointing to \"data\". A copy of \"str\" is made, so\n- * it does not need to persist after the this function is called.\n+ * Insert \"str\" into the map, pointing to \"data\".\n *\n * If an entry for \"str\" already exists, its data pointer is overwritten, and\n * the original data pointer returned. Otherwise, returns NULL.\n-- \ngitgitgadget\n\n"},{"id":"404195","messageId":"20200821192224.GC1165@coredump.intra.peff.net","threadId":"54087","inReplyTo":"b295e9393a8998b3b9263ab7cd195907d4002e36.1598035949.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/5] hashmap: add usage documentation explaining hashmap_free[_entries]()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T19:22:24Z","receivedAt":"2020-08-21T19:22:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 06:52:25PM +0000, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n> \n> The existence of hashmap_free() and hashmap_free_entries() confused me,\n> and the docs weren't clear enough. I had to consult other source code\n> examples and the implementation. Add a brief note to clarify,\n> especially since hashmap_clear*() variants may be added in the future.\n\nThanks, I think this is worth doing and the text looks clear and correct\nto me.\n\n> /*\n> - * Frees a hashmap structure and allocated memory, leaves entries undisturbed\n> + * Frees a hashmap structure and allocated memory for the table, but does not\n> + * free the entries nor anything they point to.\n> + *\n> + * Usage note:\n> + *\n> + * Many callers will need to iterate over all entries and free the data each\n> + * entry points to; in such a case, they can free the entry itself while at it.\n> + * Thus, you might see:\n> + * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {\n> + * free(e->somefield);\n> + * free(e);\n> + * }\n> + * hashmap_free(map);\n> + * instead of\n> + * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) {\n> + * free(e->somefield);\n> + * }\n> + * hashmap_free_entries(map, struct my_entry_struct, hashmap_entry_name);\n> + * to avoid the implicit extra loop over the entries. However, if there are\n> + * no special fields in your entry that need to be freed beyond the entry\n> + * itself, it is probably simpler to avoid the explicit loop and just call\n> + * hashmap_free_entries().\n\nA minor nit, but a blank line between the code snippets and the text\nmight make it a little more readable.\n\n-Peff\n"},{"id":"404196","messageId":"20200821194857.GD1165@coredump.intra.peff.net","threadId":"54087","inReplyTo":"a86fd5fdcc47baf85046eb07257f4db9f9498084.1598035949.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/5] strmap: new utility functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T19:48:57Z","receivedAt":"2020-08-21T19:49:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 06:52:26PM +0000, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n> \n> Add strmap as a new struct and associated utility functions,\n> specifically for hashmaps that map strings to some value. The API is\n> taken directly from Peff's proposal at\n> https://lore.kernel.org/git/20180906191203.GA26184@sigill.intra.peff.net/\n\nUh oh. You are encouraging me in the belief that I can send half-baked\nideas to the list and somebody will come along and implement them for\nme. ;)\n\n> Peff only included the header, not the implementation, so it isn't clear what\n> the structure was he was going to use for the hash entries. Instead of having\n> my str_entry struct have three subfields (the hashmap_entry, the string, and\n> the void* value), I made it only have two -- the hashmap_entry and a\n> string_list_item, for two reasons:\n\nI'd probably have done:\n\n struct strmap_entry {\n\tstruct hashmap_entry ent;\n\tvoid *value;\n\tchar key[FLEX_ALLOC];\n };\n\nThat saves 8 bytes (plus malloc overhead)per item, plus avoids an extra\npointer-chase for each item we consider when looking up.\n\n> 1) a strmap is often the data structure we want where string_list has\n> been used in the past. Using the same building block for\n> individual entries in both makes it easier to adopt and reuse\n> parts of the string_list API in strmap.\n\nI can see that there might be some value in being able to interchange\nthe items for code that's expecting a string_list_item. But I have to\nwonder if the potential for confusion is worth it. I.e., should that\ncode really be expecting a raw string pointer (possibly with a separate\nvoid pointer, or even better an actual typed pointer).\n\nI'll keep an eye out as I read the rest of the series for code which\nuses this.\n\n> 2) In some cases, after doing lots of other work, I want to be able\n> to iterate over the items in my strmap in sorted order. hashmap\n> obviously doesn't support that, but I wanted to be able to export\n> the strmap to a string_list easily and then use its functions.\n> (Note: I do not need the data structure to both be sorted and have\n> efficient lookup at all times. If I did, I might use a B-tree\n> instead, as suggested by brian in response to Peff in the thread\n> noted above. In my case, most strmaps will never need sorting, but\n> in one special case at the very end of a bunch of other work I want\n> to iterate over the items in sorted order without doing any more\n> lookups afterward.)\n\nHmm. Likewise, I'll keep an eye open for how this works in practice. I\ndo suspect that a B-tree might be a better solution here, but\nimplementing it is non-trivial, and most callers don't care about this\nproperty.\n\nIf the interim solution is to just dump it to a string_list and sort\nthat, that's really not that bad, assuming it just happens once after\nwe've added everything. I'm not sure there's that big a benefit to using\nstring_list_item internally, since presumably that conversion needs to\nwrite a whole new array of string_list_items anyway.\n\n> Also, I removed the STRMAP_INIT macro, since it cannot be used to\n> correctly initialize a strmap; the underlying hashmap needs a call to\n> hashmap_init() to allocate the hash table first.\n\nSince access to the underlying hashmap happens through strmap functions,\nthey could lazily initialize it. That's how oidmap works.\n\n> diff --git a/strmap.c b/strmap.c\n> new file mode 100644\n> index 0000000000..1c9fdb3b1e\n> --- /dev/null\n> +++ b/strmap.c\n> @@ -0,0 +1,81 @@\n> +#include \"git-compat-util.h\"\n> +#include \"strmap.h\"\n> +\n> +static int cmp_str_entry(const void *hashmap_cmp_fn_data,\n> +\t\t\t const struct hashmap_entry *entry1,\n> +\t\t\t const struct hashmap_entry *entry2,\n> +\t\t\t const void *keydata)\n> +{\n> +\tconst struct str_entry *e1, *e2;\n> +\n> +\te1 = container_of(entry1, const struct str_entry, ent);\n> +\te2 = container_of(entry2, const struct str_entry, ent);\n> +\treturn strcmp(e1->item.string, e2->item.string);\n> +}\n\nIf you do go the FLEX_ALLOC route, obviously lookups won't want to\nallocate a str_entry struct for the lookup key. You'd use keydata there\n(and prefer it over looking at entry2 at all). See remotes_hash_cmp()\nfor an example.\n\n> +static struct str_entry *find_str_entry(struct strmap *map,\n> +\t\t\t\t\tconst char *str)\n> +{\n> +\tstruct str_entry entry;\n> +\thashmap_entry_init(&entry.ent, strhash(str));\n> +\tentry.item.string = (char *)str;\n> +\treturn hashmap_get_entry(&map->map, &entry, ent, NULL);\n> +}\n\nCasting away constness here is awkward. It could likewise benefit from\nusing keydata, so you wouldn't need to create a temporary\nstring_list_item (which is where the non-constness comes from).\n\n> +void strmap_clear(struct strmap *map, int free_util)\n> +{\n> +\tstruct hashmap_iter iter;\n> +\tstruct str_entry *e;\n> +\n> +\tif (!map)\n> +\t\treturn;\n\nIn a lazy-init world, this becomes:\n\n if (!map || !map->map.table)\n\nOf course it would be better still if the hashmap code learned to do the\nlazy-init stuff itself.\n\n> +\thashmap_for_each_entry(&map->map, &iter, e, ent /* member name */) {\n> +\t\tfree(e->item.string);\n> +\t\tif (free_util)\n> +\t\t\tfree(e->item.util);\n> +\t}\n> +\thashmap_free_entries(&map->map, struct str_entry, ent);\n\nWith a flex-alloc struct, you can avoid the extra string free. But I\nguess you still wouldn't avoid the loop if you want to support\nfree_entries().\n\nI wonder if it would make the API simpler if the struct knew whether it\nowned the void pointer values or not. Then you'd do:\n\n struct strmap foo = { .free_values = 1 };\n ...\n strmap_put(&foo, \"key\", value);\n ...\n strmap_clear(&foo);\n\nand wouldn't have to remember to do the right thing at clear-time. It is\na little less flexible (e.g., if you transfer ownership after a certain\npoint in the code), but I wonder if any callers actually need that (and\nthey could always set the free_values flag then).\n\n> +/*\n> + * Insert \"str\" into the map, pointing to \"data\". A copy of \"str\" is made, so\n> + * it does not need to persist after the this function is called.\n> + *\n> + * If an entry for \"str\" already exists, its data pointer is overwritten, and\n> + * the original data pointer returned. Otherwise, returns NULL.\n> + */\n> +void *strmap_put(struct strmap *map, const char *str, void *data)\n\nMinor, but IMHO we should avoid copying the docstrings to the\nimplementation, since it gives two places that people have to remember\nto update if the API changes.\n\n> +void *strmap_put(struct strmap *map, const char *str, void *data)\n> +{\n> +\tstruct str_entry *entry = find_str_entry(map, str);\n> +\tvoid *old = NULL;\n\nIn a lazy-init world, this is:\n\n if (!map->map.table) {\n\tstrmap_init(map);\n\tentry = NULL;\n } else {\n entry = find_str_entry(map, str);\n }\n\n(or just call find_str_entry() in both cases and let it realize there's\nnothing to find).\n\n> +\tif (entry) {\n> +\t\told = entry->item.util;\n> +\t\tentry->item.util = data;\n> +\t} else {\n> +\t\tentry = xmalloc(sizeof(*entry));\n> +\t\thashmap_entry_init(&entry->ent, strhash(str));\n> +\t\tentry->item.string = strdup(str);\n> +\t\tentry->item.util = data;\n> +\t\thashmap_add(&map->map, &entry->ent);\n> +\t}\n\nAnd in a flex-alloc world, this second block is:\n\n FLEX_ALLOC_STR(entry, key, str);\n hashmap_entry_init(&entry->ent, strhash(str));\n entry->value = data;\n hashmap_add(&map->map, &entry->ent);\n\n> +void *strmap_get(struct strmap *map, const char *str)\n> +{\n> +\tstruct str_entry *entry = find_str_entry(map, str);\n> +\treturn entry ? entry->item.util : NULL;\n> +}\n\nIn a lazy world, this is:\n\n if (!map->map.table)\n return NULL;\n\n> +int strmap_contains(struct strmap *map, const char *str)\n> +{\n> +\treturn find_str_entry(map, str) != NULL;\n> +}\n\nAnd likewise:\n\n if (!map->map.table)\n return NULL;\n\nIt might actually be easier to stick that in find_str_entry().\n\nThe rest of it all looked good to me.\n\n-Peff\n"},{"id":"404199","messageId":"20200821195822.GE1165@coredump.intra.peff.net","threadId":"54087","inReplyTo":"5bda171d0c1562573800d4bcbfac4799f01d9c20.1598035949.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/5] strmap: add more utility functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T19:58:22Z","receivedAt":"2020-08-21T19:58:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 06:52:27PM +0000, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n> \n> This adds a number of additional convienence functions I want/need:\n> * strmap_empty()\n> * strmap_get_size()\n> * strmap_remove()\n> * strmap_for_each_entry()\n> * strmap_free()\n> * strmap_get_item()\n> \n> I suspect the first four are self-explanatory.\n\nYup, all make sense. We might also want real iterators rather than\nstrmap_for_each_entry(), which can be a bit more convenient given the\nlack of lambdas in C. But I'd be happy to wait until a caller arises.\n\n> strmap_free() differs from strmap_clear() in that the data structure is\n> not reusable after it is called; strmap_clear() is not sufficient for\n> the API because without strmap_free() we will leak memory.\n\nHmm, I missed in the previous function that strmap_clear() is actually\nleaving allocated memory. I think this is bad, because it's unlike most\nof our other data structure clear() functions.\n\nWe could work around it with the lazy-init stuff I mentioned in my last\nemail (i.e., _don't_ strmap_init() at the end of strmap_clear(), and\njust let strmap_put() take care of initializing if somebody actually\nadds something again).\n\nBut IMHO this is a sign that we should be fixing hashmap() to work like\nthat, too.\n\n> strmap_get_item() is similar to strmap_get() except that instead of just\n> returning the void* value that the string maps to, it returns the\n> string_list_item that contains both the string and the void* value (or\n> NULL if the string isn't in the map). This is helpful because it avoids\n> multiple lookups, e.g. in some cases a caller would need to call:\n> * strmap_contains() to check that the map has an entry for the string\n> * strmap_get() to get the void* value\n> * \n> * strmap_put() to update/overwrite the value\n\nThat makes sense. If you follow my suggestion to drop string_list_item,\nthen it would be OK to return the whole str_entry. (I forgot to mention\nin the last patch, but perhaps strmap_entry would be a more distinctive\nname).\n\n> diff --git a/strmap.h b/strmap.h\n> index eb5807f6fa..45d0a4f714 100644\n> --- a/strmap.h\n> +++ b/strmap.h\n> @@ -21,6 +21,11 @@ void strmap_init(struct strmap *map);\n> /*\n> * Remove all entries from the map, releasing any allocated resources.\n> */\n> +void strmap_free(struct strmap *map, int free_values);\n> +\n> +/*\n> + * Same as calling strmap_free() followed by strmap_init().\n> + */\n> void strmap_clear(struct strmap *map, int free_values);\n\nI guess the docstring was a bit inaccurate in the previous patch, then. :)\n\n-Peff\n"},{"id":"404200","messageId":"20200821200121.GF1165@coredump.intra.peff.net","threadId":"54087","inReplyTo":"b3095d97d8ee9d6576292731cc100492e7c64f13.1598035949.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 4/5] strmap: add strdup_strings option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T20:01:21Z","receivedAt":"2020-08-21T20:01:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 06:52:28PM +0000, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n> \n> Just as it is sometimes useful for string_list to duplicate and take\n> ownership of memory management of the strings it contains, the same is\n> sometimes true for strmaps as well. Add the same flag from string_list\n> to strmap.\n\nThis is actually one of the ugliest parts of string_list, IMHO, and I'd\nprefer if we can avoid duplicating it. Yes, sometimes we can manage to\navoid an extra copy of a string. But the resulting ownership and\nlifetime questions are often very error-prone. In other data structures\nwe've moved towards just having the structure own its data (e.g.,\nstrvec does so, and things like oidmap store their own oids). I've been\nhappy with the simplicity of it.\n\nIt also works if you use a flex-array for the key storage in the\nstrmap_entry. :)\n\n-Peff\n"},{"id":"404201","messageId":"20200821201034.GG1165@coredump.intra.peff.net","threadId":"54087","inReplyTo":"418975b46039f63476852a868ca6221244b5d88e.1598035949.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 5/5] strmap: add functions facilitating use as a string->int map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T20:10:34Z","receivedAt":"2020-08-21T20:10:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 06:52:29PM +0000, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n> \n> Although strmap could be used as a string->int map, one either had to\n> allocate an int for every entry and then deallocate later, or one had to\n> do a bunch of casting between (void*) and (intptr_t).\n> \n> Add some special functions that do the casting. Also, rename put->set\n> for such wrapper functions since 'put' implied there may be some\n> deallocation needed if the string was already found in the map, which\n> isn't the case when we're storing an int value directly in the void*\n> slot instead of using the void* slot as a pointer to data.\n\nI think wrapping this kind of hackery is worth doing.\n\nYou'd be able to use put() as usual, wouldn't you? It never deallocates\nthe util field, but just returns the old one. And the caller knows that\nit's really an int, and shouldn't be deallocated.\n\n> A note on the name: strintmap looks and sounds pretty lame to me, but\n> after trying to come up with something better and having no luck, I\n> figured I'd just go with it for a while and then at some point some\n> better and obvious name would strike me and I could replace it. Several\n> months later, I still don't have a better name. Hopefully someone else\n> has one.\n\nstrnummap? That's pretty bad, too.\n\nSince the functions all take a raw strmap, you _could_ just do\n\"strmap_getint()\", etc. But I think you could actually get some\nadditional safety by defining a wrapper type:\n\n struct strintmap {\n struct strmap strmap;\n };\n\nIt's a bit annoying because you a bunch of pass-through boilerplate for\nstuff like:\n\n static inline int strintmap_empty(struct strintmap *map)\n {\n return strmap_empty(&map->map);\n }\n\nbut it would prevent mistakes like:\n\n strintmap_incr(&map, \"foo\", 10);\n strmap_clear(&map, 1);\n\nwhich would try to free (void *)10. I'm not sure if that's worth it or\nnot. You'd almost have to be trying to fail to pass \"1\" for free_util\nthere. But I've seen stranger things. :)\n\n-Peff\n"},{"id":"404202","messageId":"20200821201648.GH1165@coredump.intra.peff.net","threadId":"54087","inReplyTo":"pull.835.git.git.1598035949.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/5] Add struct strmap and associated utility functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T20:16:48Z","receivedAt":"2020-08-21T20:16:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 06:52:24PM +0000, Elijah Newren via GitGitGadget wrote:\n\n> Here I introduce a new strmap type, which my new merge backed, merge-ort,\n> uses heavily. (I also made significant use of it in my changes to\n> diffcore-rename). This strmap type was based on Peff's proposal from a\n> couple years ago[1], but has additions that I made as I used it. I also\n> start the series off with a quick documentation improvement to hashmap.c to\n> differentiate between hashmap_free() and hashmap_free_entries(), since I\n> personally had difficulty understanding them and it affects how\n> strmap_clear()/strmap_free() are written.\n\nI like the direction overall (unsurprisingly), but left a bunch of\ncomments. I do think if we're going to do this that it may be worth\ncleaning up hashmap a bit first, especially around its clear/free\nsemantics, and its ability to lazy-allocate the table.\n\nI'm happy to work on that, but don't want to step on your toes.\n\nI also wonder if you looked at the khash stuff at all. Especially for\nstoring integers, it makes things much more natural. You'd do something\nlike:\n\n /* you might even be able to just write !strcmp in the macro below */\n static inline int streq(const char *a, const char *b)\n {\n return !strcmp(a, b);\n }\n\n KHASH_INIT(strint_map, char *, int, 1, strhash, streq);\n\nand then you'd probably want a \"put\" wrapper that makes a copy of the\nstring. khash has its own charming awkwardness, but I'm just curious if you\nlooked at it and found it more awkward than hashmap.c, or if you just\ndidn't look at it.\n\n-Peff\n"},{"id":"404204","messageId":"CABPp-BGJK4C7U+-MB-+TUgFAuuFJKE-E7y17FFJDRTyFydVX2A@mail.gmail.com","threadId":"54087","inReplyTo":"20200821200121.GF1165@coredump.intra.peff.net","subject":"Re: [PATCH 4/5] strmap: add strdup_strings option","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-21T20:41:44Z","receivedAt":"2020-08-21T20:42:00Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 21, 2020 at 1:01 PM Jeff King wrote:\n>\n> On Fri, Aug 21, 2020 at 06:52:28PM +0000, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n> > Just as it is sometimes useful for string_list to duplicate and take\n> > ownership of memory management of the strings it contains, the same is\n> > sometimes true for strmaps as well. Add the same flag from string_list\n> > to strmap.\n>\n> This is actually one of the ugliest parts of string_list, IMHO, and I'd\n> prefer if we can avoid duplicating it. Yes, sometimes we can manage to\n> avoid an extra copy of a string. But the resulting ownership and\n> lifetime questions are often very error-prone. In other data structures\n> we've moved towards just having the structure own its data (e.g.,\n> strvec does so, and things like oidmap store their own oids). I've been\n> happy with the simplicity of it.\n>\n> It also works if you use a flex-array for the key storage in the\n> strmap_entry. :)\n\nI can see how it's easier, but that worries me about the number of\nextra copies for my usecase. In order to minimize actual computation,\nI track an awful lot of auxiliary data in merge-ort so that I know\nwhen I can safely perform many different case-specific optimizations.\nAmong other things, this means 15 strmaps. 1 of those stores a\nmapping from all paths that traverse_trees() walks over (file or\ndirectory) to metadata about the content on the three different sides.\n9 of the remaining 14 simply share the strings in the main strmap,\nbecause I don't need extra copies of the paths in the repository. I\ncould (and maybe should) extend that to 11 of the 14. Only 3 actually\ndo need to store a copy of the paths (because they store data used\nbeyond the end of an inner recursive merge or can be used to\naccelerate subsequent commits in a rebase or cherry-pick sequence).\n\nSo, in most my cases, I don't want to duplicate strings. I actually\nstarted my implementation using FLEX_ALLOC_STR(), as you suggested\nearlier in this thread, but tossed it because of this same desire to\nnot duplicate strings but just share them between the strmaps.\n\nGranted, I made that decision before I had a complete implementation,\nso I didn't measure the actual costs. It's possible that was a\npremature optimization.\n"},{"id":"404205","messageId":"CABPp-BFi7JSkkVSLkS9Kb5fMJ3xM3CjM7_ZsvJZMv=XgQgb6Lw@mail.gmail.com","threadId":"54087","inReplyTo":"20200821201034.GG1165@coredump.intra.peff.net","subject":"Re: [PATCH 5/5] strmap: add functions facilitating use as a string->int map","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-21T20:51:57Z","receivedAt":"2020-08-21T20:52:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 21, 2020 at 1:10 PM Jeff King wrote:\n>\n> On Fri, Aug 21, 2020 at 06:52:29PM +0000, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n> > Although strmap could be used as a string->int map, one either had to\n> > allocate an int for every entry and then deallocate later, or one had to\n> > do a bunch of casting between (void*) and (intptr_t).\n> >\n> > Add some special functions that do the casting. Also, rename put->set\n> > for such wrapper functions since 'put' implied there may be some\n> > deallocation needed if the string was already found in the map, which\n> > isn't the case when we're storing an int value directly in the void*\n> > slot instead of using the void* slot as a pointer to data.\n>\n> I think wrapping this kind of hackery is worth doing.\n>\n> You'd be able to use put() as usual, wouldn't you? It never deallocates\n> the util field, but just returns the old one. And the caller knows that\n> it's really an int, and shouldn't be deallocated.\n\nYou can use put() as normal, if you don't mind the need to explicitly\nthrow in a typecast when you use it. In fact, strintmap_set() does no\nmore than typecasting the int to void* and otherwise calling\nstrmap_put().\n\nI initially called that strintmap_put(), but got confused once or\ntwice and looked up the function definition to make sure there wasn't\nsome deallocation I needed to handle. After that, I decided to just\nrename to _set() because I thought it'd reduce the chance of myself or\nothers wondering about that in the future.\n\n>\n> > A note on the name: strintmap looks and sounds pretty lame to me, but\n> > after trying to come up with something better and having no luck, I\n> > figured I'd just go with it for a while and then at some point some\n> > better and obvious name would strike me and I could replace it. Several\n> > months later, I still don't have a better name. Hopefully someone else\n> > has one.\n>\n> strnummap? That's pretty bad, too.\n>\n> Since the functions all take a raw strmap, you _could_ just do\n> \"strmap_getint()\", etc. But I think you could actually get some\n> additional safety by defining a wrapper type:\n>\n> struct strintmap {\n> struct strmap strmap;\n> };\n>\n> It's a bit annoying because you a bunch of pass-through boilerplate for\n> stuff like:\n>\n> static inline int strintmap_empty(struct strintmap *map)\n> {\n> return strmap_empty(&map->map);\n> }\n>\n> but it would prevent mistakes like:\n>\n> strintmap_incr(&map, \"foo\", 10);\n> strmap_clear(&map, 1);\n>\n> which would try to free (void *)10. I'm not sure if that's worth it or\n> not. You'd almost have to be trying to fail to pass \"1\" for free_util\n> there. But I've seen stranger things. :)\n\nI like this idea and the extra safety it provides. Most of strintmap\nis static inline functions anyway, adding a few more wouldn't hurt.\n"},{"id":"404207","messageId":"20200821210301.GA11806@coredump.intra.peff.net","threadId":"54087","inReplyTo":"CABPp-BGJK4C7U+-MB-+TUgFAuuFJKE-E7y17FFJDRTyFydVX2A@mail.gmail.com","subject":"Re: [PATCH 4/5] strmap: add strdup_strings option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T21:03:01Z","receivedAt":"2020-08-21T21:03:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 01:41:44PM -0700, Elijah Newren wrote:\n\n> > This is actually one of the ugliest parts of string_list, IMHO, and I'd\n> > prefer if we can avoid duplicating it. Yes, sometimes we can manage to\n> > avoid an extra copy of a string. But the resulting ownership and\n> > lifetime questions are often very error-prone. In other data structures\n> > we've moved towards just having the structure own its data (e.g.,\n> > strvec does so, and things like oidmap store their own oids). I've been\n> > happy with the simplicity of it.\n> >\n> > It also works if you use a flex-array for the key storage in the\n> > strmap_entry. :)\n> \n> I can see how it's easier, but that worries me about the number of\n> extra copies for my usecase. In order to minimize actual computation,\n> I track an awful lot of auxiliary data in merge-ort so that I know\n> when I can safely perform many different case-specific optimizations.\n> Among other things, this means 15 strmaps. 1 of those stores a\n> mapping from all paths that traverse_trees() walks over (file or\n> directory) to metadata about the content on the three different sides.\n> 9 of the remaining 14 simply share the strings in the main strmap,\n> because I don't need extra copies of the paths in the repository. I\n> could (and maybe should) extend that to 11 of the 14. Only 3 actually\n> do need to store a copy of the paths (because they store data used\n> beyond the end of an inner recursive merge or can be used to\n> accelerate subsequent commits in a rebase or cherry-pick sequence).\n\nI'd have to see the code, of course, but:\n\n - keep in mind you're allocating 8 bytes for a pointer (plus 24 for\n the rest of the strmap entry). If you use a flex-array you get those\n 8 bytes back. Full paths do tend to be longer than that, so it's\n probably net worse than a pointer to an existing string. But how\n much worse, and does it matter?\n\n - That sounds like a lot of maps. :) I guess you've looked at\n compacting some of them into a single map-to-struct?\n\n> So, in most my cases, I don't want to duplicate strings. I actually\n> started my implementation using FLEX_ALLOC_STR(), as you suggested\n> earlier in this thread, but tossed it because of this same desire to\n> not duplicate strings but just share them between the strmaps.\n> \n> Granted, I made that decision before I had a complete implementation,\n> so I didn't measure the actual costs. It's possible that was a\n> premature optimization.\n\nI'm just really concerned that it poisons the data structure with\ncomplexity that many of the other callers will have to deal with. We've\nhad several \"oops, strdup_strings wasn't what I expected it to be\" bugs\nwith string-list (in both directions: leaks and use-after-free). It\nwould be nice to have actual numbers and see if it's worth the cost.\n\n-Peff\n"},{"id":"404208","messageId":"20200821210505.GB11806@coredump.intra.peff.net","threadId":"54087","inReplyTo":"CABPp-BFi7JSkkVSLkS9Kb5fMJ3xM3CjM7_ZsvJZMv=XgQgb6Lw@mail.gmail.com","subject":"Re: [PATCH 5/5] strmap: add functions facilitating use as a string->int map","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-21T21:05:05Z","receivedAt":"2020-08-21T21:05:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 01:51:57PM -0700, Elijah Newren wrote:\n\n> > I think wrapping this kind of hackery is worth doing.\n> >\n> > You'd be able to use put() as usual, wouldn't you? It never deallocates\n> > the util field, but just returns the old one. And the caller knows that\n> > it's really an int, and shouldn't be deallocated.\n> \n> You can use put() as normal, if you don't mind the need to explicitly\n> throw in a typecast when you use it. In fact, strintmap_set() does no\n> more than typecasting the int to void* and otherwise calling\n> strmap_put().\n\nYeah, I think hiding the type-casting is worth it alone. I was just\nconfused by your remark.\n\n> I initially called that strintmap_put(), but got confused once or\n> twice and looked up the function definition to make sure there wasn't\n> some deallocation I needed to handle. After that, I decided to just\n> rename to _set() because I thought it'd reduce the chance of myself or\n> others wondering about that in the future.\n\nYeah, I'd agree that is a much better name. Since there's an \"incr\",\nhaving a specific \"set\" makes it clear that we're overwriting.\n\n> > struct strintmap {\n> > struct strmap strmap;\n> > };\n> [...]\n> I like this idea and the extra safety it provides. Most of strintmap\n> is static inline functions anyway, adding a few more wouldn't hurt.\n\nOK. Then I guess we can't cheat our way out of picking a name with\nstrmap_getint(). :)\n\n-Peff\n"},{"id":"404219","messageId":"CABPp-BGYiphp-93Bf=2z-ZLd-Y=buTA0BCp6zuTJF39n1x3Rfw@mail.gmail.com","threadId":"54087","inReplyTo":"20200821201648.GH1165@coredump.intra.peff.net","subject":"Re: [PATCH 0/5] Add struct strmap and associated utility functions","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-21T21:33:54Z","receivedAt":"2020-08-21T21:34:13Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 21, 2020 at 1:16 PM Jeff King wrote:\n>\n> On Fri, Aug 21, 2020 at 06:52:24PM +0000, Elijah Newren via GitGitGadget wrote:\n>\n> > Here I introduce a new strmap type, which my new merge backed, merge-ort,\n> > uses heavily. (I also made significant use of it in my changes to\n> > diffcore-rename). This strmap type was based on Peff's proposal from a\n> > couple years ago[1], but has additions that I made as I used it. I also\n> > start the series off with a quick documentation improvement to hashmap.c to\n> > differentiate between hashmap_free() and hashmap_free_entries(), since I\n> > personally had difficulty understanding them and it affects how\n> > strmap_clear()/strmap_free() are written.\n>\n> I like the direction overall (unsurprisingly), but left a bunch of\n> comments. I do think if we're going to do this that it may be worth\n> cleaning up hashmap a bit first, especially around its clear/free\n> semantics, and its ability to lazy-allocate the table.\n>\n> I'm happy to work on that, but don't want to step on your toes.\n\nI have patches which introduce hashmap_clear() and\nhashmap_clear_entries() to hashmap.[ch], which allowed me to simplify\nstrmap_clear(); instead of needing to call both\nhashmap_free[_entries]() && strmap_init(), I could just call\nhashmap_clear[_entries](). Doing that surprised me with a significant\nperformance impact (in a good direction), at which point I started\nadding mem-pool integration into hashmap for storing the entries that\nhashmap.c allocates and got further good speedups.\n\nI thought those were better explained when I got to the performance\nstuff, so I had held off on those patches. I could pull them out and\nsubmit them first.\n\nHowever, there's an important difference here between what I've done\nand what you've suggested for hashmap: my method did not deallocate\nhashmap->table in hashmap_clear() and then use lazy initialization.\nIn fact, I think not deallocating the table was part of the charm --\nthe table had already naturally grown to the right size, and because\nthe repository has approximately the same number of paths in various\ncommits, this provided me a way of getting a table preallocated to a\nreasonable size for all merges after the first (and there are multiple\nmerges either when recursiveness is needed due to multiple merge\nbases, OR when rebasing or cherry-picking a sequence of commits).\nThis prevented, as hashmap.h puts it, \"expensive resizing\".\n\nSo, once again, my performance ideas might be clashing with some of\nyour desires for the API. Any clever ideas for resolving that?\n\nAlso, since you want to see hashmap cleanup first, should I submit\njust the hashmap_clear[_entries()] stuff, or should I also submit the\nAPI additions to allow mem-pool integration in hashmap (it's pretty\nsmall and self-contained, but it'll be a while before I submit the\npatches that use it...)?\n\n> I also wonder if you looked at the khash stuff at all. Especially for\n> storing integers, it makes things much more natural. You'd do something\n> like:\n>\n> /* you might even be able to just write !strcmp in the macro below */\n> static inline int streq(const char *a, const char *b)\n> {\n> return !strcmp(a, b);\n> }\n>\n> KHASH_INIT(strint_map, char *, int, 1, strhash, streq);\n>\n> and then you'd probably want a \"put\" wrapper that makes a copy of the\n> string. khash has its own charming awkwardness, but I'm just curious if you\n> looked at it and found it more awkward than hashmap.c, or if you just\n> didn't look at it.\n\nI did look at it, but only briefly. I had a further investigation on\nmy TODO list for months, along with several other improvement ideas.\nBut it seemed like my TODO list was really long, and my new merge\nbackend hasn't benefited anyone yet. At some point, I decided to punt\non it and other ideas and start cleaning up my code and submitting. I\nbelieve merge-ort is more accurate than merge-recursive (it fixes\nseveral test_expect_failures) and is a lot faster as well for the\ncases I'm looking at. So, for now, I've pulled it off my radar.\n\nBut I'd be really happy if someone else wanted to jump in and try\nswitching out hashmap for khash in the strmap API and see if it helps\nmerge-ort performance. :-)\n"},{"id":"404241","messageId":"CABPp-BE8tdpjx2RBGyZOYV4hsfjm5HF_dmehvX792x7TtWkLcA@mail.gmail.com","threadId":"54087","inReplyTo":"20200821210301.GA11806@coredump.intra.peff.net","subject":"Re: [PATCH 4/5] strmap: add strdup_strings option","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-21T22:25:44Z","receivedAt":"2020-08-21T22:26:01Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 21, 2020 at 2:03 PM Jeff King wrote:\n>\n> On Fri, Aug 21, 2020 at 01:41:44PM -0700, Elijah Newren wrote:\n>\n> > > This is actually one of the ugliest parts of string_list, IMHO, and I'd\n> > > prefer if we can avoid duplicating it. Yes, sometimes we can manage to\n> > > avoid an extra copy of a string. But the resulting ownership and\n> > > lifetime questions are often very error-prone. In other data structures\n> > > we've moved towards just having the structure own its data (e.g.,\n> > > strvec does so, and things like oidmap store their own oids). I've been\n> > > happy with the simplicity of it.\n> > >\n> > > It also works if you use a flex-array for the key storage in the\n> > > strmap_entry. :)\n> >\n> > I can see how it's easier, but that worries me about the number of\n> > extra copies for my usecase. In order to minimize actual computation,\n> > I track an awful lot of auxiliary data in merge-ort so that I know\n> > when I can safely perform many different case-specific optimizations.\n> > Among other things, this means 15 strmaps. 1 of those stores a\n> > mapping from all paths that traverse_trees() walks over (file or\n> > directory) to metadata about the content on the three different sides.\n> > 9 of the remaining 14 simply share the strings in the main strmap,\n> > because I don't need extra copies of the paths in the repository. I\n> > could (and maybe should) extend that to 11 of the 14. Only 3 actually\n> > do need to store a copy of the paths (because they store data used\n> > beyond the end of an inner recursive merge or can be used to\n> > accelerate subsequent commits in a rebase or cherry-pick sequence).\n>\n> I'd have to see the code, of course, but:\n\n> - keep in mind you're allocating 8 bytes for a pointer (plus 24 for\n> the rest of the strmap entry). If you use a flex-array you get those\n> 8 bytes back. Full paths do tend to be longer than that, so it's\n> probably net worse than a pointer to an existing string. But how\n> much worse, and does it matter?\n\nI'll investigate; it may take a while...\n\n> - That sounds like a lot of maps. :) I guess you've looked at\n> compacting some of them into a single map-to-struct?\n\nOh, map-to-struct is the primary use. But compacting them won't work,\nbecause the reason for the additional maps is that they have different\nsets of keys (this set of paths meet a certain condition...). Only\none map contains all the paths involved in the merge.\n\nAlso, several of those maps don't even store a value; and are really\njust a set implemented via strmap (thus meaning the only bit of data I\nneed for some conditions is whether any given path meets it). It\nseems slightly ugly to have to call strmap_put(map, string, NULL) for\nthose. I wonder if I should have another strset type much like your\nsuggesting for strintmap. Hmm...\n\nAlso, one thing that inflates the number of strmaps I use is that\nseveral of those conditions are specific to a certain side of the\nmerge, thus requiring two strmaps for each of those special\nconditions.\n\n> > So, in most my cases, I don't want to duplicate strings. I actually\n> > started my implementation using FLEX_ALLOC_STR(), as you suggested\n> > earlier in this thread, but tossed it because of this same desire to\n> > not duplicate strings but just share them between the strmaps.\n> >\n> > Granted, I made that decision before I had a complete implementation,\n> > so I didn't measure the actual costs. It's possible that was a\n> > premature optimization.\n>\n> I'm just really concerned that it poisons the data structure with\n> complexity that many of the other callers will have to deal with. We've\n> had several \"oops, strdup_strings wasn't what I expected it to be\" bugs\n> with string-list (in both directions: leaks and use-after-free). It\n> would be nice to have actual numbers and see if it's worth the cost.\n\nI'll go get some and find out what the impact is.\n"},{"id":"404242","messageId":"CABPp-BFFOKcBsPEu+zueCKwPGMh9RgOE8QJonKxkNNE3-Ym7Gw@mail.gmail.com","threadId":"54087","inReplyTo":"CABPp-BGYiphp-93Bf=2z-ZLd-Y=buTA0BCp6zuTJF39n1x3Rfw@mail.gmail.com","subject":"Re: [PATCH 0/5] Add struct strmap and associated utility functions","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-21T22:28:07Z","receivedAt":"2020-08-21T22:28:25Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 21, 2020 at 2:33 PM Elijah Newren wrote:\n>\n> On Fri, Aug 21, 2020 at 1:16 PM Jeff King wrote:\n> >\n> > On Fri, Aug 21, 2020 at 06:52:24PM +0000, Elijah Newren via GitGitGadget wrote:\n> >\n> > > Here I introduce a new strmap type, which my new merge backed, merge-ort,\n> > > uses heavily. (I also made significant use of it in my changes to\n> > > diffcore-rename). This strmap type was based on Peff's proposal from a\n> > > couple years ago[1], but has additions that I made as I used it. I also\n> > > start the series off with a quick documentation improvement to hashmap.c to\n> > > differentiate between hashmap_free() and hashmap_free_entries(), since I\n> > > personally had difficulty understanding them and it affects how\n> > > strmap_clear()/strmap_free() are written.\n> >\n> > I like the direction overall (unsurprisingly), but left a bunch of\n> > comments. I do think if we're going to do this that it may be worth\n> > cleaning up hashmap a bit first, especially around its clear/free\n> > semantics, and its ability to lazy-allocate the table.\n> >\n> > I'm happy to work on that, but don't want to step on your toes.\n>\n> I have patches which introduce hashmap_clear() and\n> hashmap_clear_entries() to hashmap.[ch], which allowed me to simplify\n> strmap_clear(); instead of needing to call both\n> hashmap_free[_entries]() && strmap_init(), I could just call\n> hashmap_clear[_entries](). Doing that surprised me with a significant\n> performance impact (in a good direction), at which point I started\n> adding mem-pool integration into hashmap for storing the entries that\n> hashmap.c allocates and got further good speedups.\n>\n> I thought those were better explained when I got to the performance\n> stuff, so I had held off on those patches. I could pull them out and\n> submit them first.\n>\n> However, there's an important difference here between what I've done\n> and what you've suggested for hashmap: my method did not deallocate\n> hashmap->table in hashmap_clear() and then use lazy initialization.\n> In fact, I think not deallocating the table was part of the charm --\n> the table had already naturally grown to the right size, and because\n> the repository has approximately the same number of paths in various\n> commits, this provided me a way of getting a table preallocated to a\n> reasonable size for all merges after the first (and there are multiple\n> merges either when recursiveness is needed due to multiple merge\n> bases, OR when rebasing or cherry-picking a sequence of commits).\n> This prevented, as hashmap.h puts it, \"expensive resizing\".\n>\n> So, once again, my performance ideas might be clashing with some of\n> your desires for the API. Any clever ideas for resolving that?\n>\n> Also, since you want to see hashmap cleanup first, should I submit\n> just the hashmap_clear[_entries()] stuff, or should I also submit the\n> API additions to allow mem-pool integration in hashmap (it's pretty\n> small and self-contained, but it'll be a while before I submit the\n> patches that use it...)?\n\nNevermind, I mis-remembered. The mempool integration was added\nspecifically to strmap, not to hashmap, because strmap_put() does the\nallocation of the str_entry. So I'll just pull out the\nhashmap_clear[_entries]() stuff and send it up.\n\n>\n> > I also wonder if you looked at the khash stuff at all. Especially for\n> > storing integers, it makes things much more natural. You'd do something\n> > like:\n> >\n> > /* you might even be able to just write !strcmp in the macro below */\n> > static inline int streq(const char *a, const char *b)\n> > {\n> > return !strcmp(a, b);\n> > }\n> >\n> > KHASH_INIT(strint_map, char *, int, 1, strhash, streq);\n> >\n> > and then you'd probably want a \"put\" wrapper that makes a copy of the\n> > string. khash has its own charming awkwardness, but I'm just curious if you\n> > looked at it and found it more awkward than hashmap.c, or if you just\n> > didn't look at it.\n>\n> I did look at it, but only briefly. I had a further investigation on\n> my TODO list for months, along with several other improvement ideas.\n> But it seemed like my TODO list was really long, and my new merge\n> backend hasn't benefited anyone yet. At some point, I decided to punt\n> on it and other ideas and start cleaning up my code and submitting. I\n> believe merge-ort is more accurate than merge-recursive (it fixes\n> several test_expect_failures) and is a lot faster as well for the\n> cases I'm looking at. So, for now, I've pulled it off my radar.\n>\n> But I'd be really happy if someone else wanted to jump in and try\n> switching out hashmap for khash in the strmap API and see if it helps\n> merge-ort performance. :-)\n"},{"id":"404676","messageId":"20200828070335.GB2105050@coredump.intra.peff.net","threadId":"54087","inReplyTo":"CABPp-BGYiphp-93Bf=2z-ZLd-Y=buTA0BCp6zuTJF39n1x3Rfw@mail.gmail.com","subject":"Re: [PATCH 0/5] Add struct strmap and associated utility functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-28T07:03:35Z","receivedAt":"2020-08-28T07:03:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 02:33:54PM -0700, Elijah Newren wrote:\n\n> However, there's an important difference here between what I've done\n> and what you've suggested for hashmap: my method did not deallocate\n> hashmap->table in hashmap_clear() and then use lazy initialization.\n> In fact, I think not deallocating the table was part of the charm --\n> the table had already naturally grown to the right size, and because\n> the repository has approximately the same number of paths in various\n> commits, this provided me a way of getting a table preallocated to a\n> reasonable size for all merges after the first (and there are multiple\n> merges either when recursiveness is needed due to multiple merge\n> bases, OR when rebasing or cherry-picking a sequence of commits).\n> This prevented, as hashmap.h puts it, \"expensive resizing\".\n> \n> So, once again, my performance ideas might be clashing with some of\n> your desires for the API. Any clever ideas for resolving that?\n\nIf the magic is in pre-sizing the hash, then it seems like the callers\nought to be feeding the size hint. That does make a little more work for\nthem, but I think there's real value in having consistent semantics for\n\"clear\" across our data structures.\n\nHowever, one cheat would be to free the memory but retain the size hint\nafter a clear. And then if we lazy-init, grow immediately to the hint\nsize. That's more expensive than a true reuse, because we do reallocate\nthe memory. But it avoids the repeated re-allocation during growth.\n\nIt may also be a sign that we should be growing the hash more\naggressively in the first place. Of course all of this is predicated\nhaving some benchmarks. It would be useful to know which part actually\nprovided the speedup.\n\n-Peff\n"},{"id":"404677","messageId":"20200828070802.GC2105050@coredump.intra.peff.net","threadId":"54087","inReplyTo":"CABPp-BE8tdpjx2RBGyZOYV4hsfjm5HF_dmehvX792x7TtWkLcA@mail.gmail.com","subject":"Re: [PATCH 4/5] strmap: add strdup_strings option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-28T07:08:02Z","receivedAt":"2020-08-28T07:08:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 21, 2020 at 03:25:44PM -0700, Elijah Newren wrote:\n\n> > - That sounds like a lot of maps. :) I guess you've looked at\n> > compacting some of them into a single map-to-struct?\n> \n> Oh, map-to-struct is the primary use. But compacting them won't work,\n> because the reason for the additional maps is that they have different\n> sets of keys (this set of paths meet a certain condition...). Only\n> one map contains all the paths involved in the merge.\n\nOK, I guess I'm not surprised that you would not have missed such an\nobvious optimization. :)\n\n> Also, several of those maps don't even store a value; and are really\n> just a set implemented via strmap (thus meaning the only bit of data I\n> need for some conditions is whether any given path meets it). It\n> seems slightly ugly to have to call strmap_put(map, string, NULL) for\n> those. I wonder if I should have another strset type much like your\n> suggesting for strintmap. Hmm...\n\nFWIW, khash does have a \"set\" mode where it avoids allocating the value\narray at all.\n\nWhat's the easiest way to benchmark merge-ort? I suspect I could swap\nout hashmap for khash (messily) in an hour or less.\n\n-Peff\n"},{"id":"404701","messageId":"CABPp-BGQB8rD8KyzccTQQ_X3Puyy3g5OOSEQES8Lv8Qtb-zRPg@mail.gmail.com","threadId":"54087","inReplyTo":"20200828070335.GB2105050@coredump.intra.peff.net","subject":"Re: [PATCH 0/5] Add struct strmap and associated utility functions","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-28T15:29:44Z","receivedAt":"2020-08-28T15:30:00Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 28, 2020 at 12:03 AM Jeff King wrote:\n>\n> On Fri, Aug 21, 2020 at 02:33:54PM -0700, Elijah Newren wrote:\n>\n> > However, there's an important difference here between what I've done\n> > and what you've suggested for hashmap: my method did not deallocate\n> > hashmap->table in hashmap_clear() and then use lazy initialization.\n> > In fact, I think not deallocating the table was part of the charm --\n> > the table had already naturally grown to the right size, and because\n> > the repository has approximately the same number of paths in various\n> > commits, this provided me a way of getting a table preallocated to a\n> > reasonable size for all merges after the first (and there are multiple\n> > merges either when recursiveness is needed due to multiple merge\n> > bases, OR when rebasing or cherry-picking a sequence of commits).\n> > This prevented, as hashmap.h puts it, \"expensive resizing\".\n> >\n> > So, once again, my performance ideas might be clashing with some of\n> > your desires for the API. Any clever ideas for resolving that?\n>\n> If the magic is in pre-sizing the hash, then it seems like the callers\n> ought to be feeding the size hint. That does make a little more work for\n> them, but I think there's real value in having consistent semantics for\n> \"clear\" across our data structures.\n\nI thought about adding a size hint from the callers, but the thing is\nI don't know how to get a good one short of running a merge and\nquerying how big things were sized in that merge. (In some common\ncases I can get an upper bound, but I can't get it in all cases and\nthat upper bound might be a couple orders of magnitude too big.)\nThus, it's really a case where I just punt on pre-sizing for the first\nmerge, and use the size from the previous merge for subsequent ones.\nIf you have a non-recursive merge or are cherry-picking only a single\ncommit, then no sizing hint is used.\n\n> However, one cheat would be to free the memory but retain the size hint\n> after a clear. And then if we lazy-init, grow immediately to the hint\n> size. That's more expensive than a true reuse, because we do reallocate\n> the memory. But it avoids the repeated re-allocation during growth.\n>\n> It may also be a sign that we should be growing the hash more\n> aggressively in the first place. Of course all of this is predicated\n> having some benchmarks. It would be useful to know which part actually\n> provided the speedup.\n\nYour thoughts here are great; I also had another one this past week --\nI could introduce a hashmap_partial_clear() (in addition to\nhashmap_clear()) for the special usecase I have of leaving the table\nallocated and pre-sized. It'd prevent people from accidentally using\nit and forgetting to free stuff, while still allowing me to take\nadvantage. But, as you say, more benchmarks would be useful to find\nwhich parts provided the speedup before taking any of these steps.\n"},{"id":"404713","messageId":"CABPp-BFL_f4ee=NrfKwVEcLzuCZy7pfXOTLimp5Qn3P89RYfpA@mail.gmail.com","threadId":"54087","inReplyTo":"20200828070802.GC2105050@coredump.intra.peff.net","subject":"Re: [PATCH 4/5] strmap: add strdup_strings option","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-08-28T17:20:40Z","receivedAt":"2020-08-28T17:21:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 28, 2020 at 12:08 AM Jeff King wrote:\n>\n> On Fri, Aug 21, 2020 at 03:25:44PM -0700, Elijah Newren wrote:\n>\n> > > - That sounds like a lot of maps. :) I guess you've looked at\n> > > compacting some of them into a single map-to-struct?\n> >\n> > Oh, map-to-struct is the primary use. But compacting them won't work,\n> > because the reason for the additional maps is that they have different\n> > sets of keys (this set of paths meet a certain condition...). Only\n> > one map contains all the paths involved in the merge.\n>\n> OK, I guess I'm not surprised that you would not have missed such an\n> obvious optimization. :)\n>\n> > Also, several of those maps don't even store a value; and are really\n> > just a set implemented via strmap (thus meaning the only bit of data I\n> > need for some conditions is whether any given path meets it). It\n> > seems slightly ugly to have to call strmap_put(map, string, NULL) for\n> > those. I wonder if I should have another strset type much like your\n> > suggesting for strintmap. Hmm...\n>\n> FWIW, khash does have a \"set\" mode where it avoids allocating the value\n> array at all.\n\nCool.\n\n> What's the easiest way to benchmark merge-ort?\n\nNote that I discovered another optimization that I'm working on\nimplementing; when finished, it should cut down a little more on the\ntime spent on inexact rename detection. That should have the side\neffect of having the time spent on strmaps stick out some more in the\noverall timings (as a percentage of overall time anyway). So, I'm\nfocused on that before I do other benchmarking work (which is part of\nthe reason I mentioned my strmap/hashmap benchmarking last week might\ntake a while).\n\nAnyway, on to your question:\n\n=== If you just want to be able to run the ort merge algorithm ===\n\nClone git@github.com:newren/git and checkout the 'ort' branch and\nbuild it. It currently changes the default merge algorithm to 'ort'\nand even ignores '-s recursive' by remapping it to '-s ort' (because I\nwanted to see how regression tests fared with ort as a replacement for\nrecrusive). It should pass the regression tests if you want to run\nthose first. But note that if you want to compare 'ort' to\n'recursive', then currently you need to have two different git builds,\none of my branch and one with a different checkout of something else\n(e.g. 2.28.0 or 'master' or whatever).\n\n=== Decide the granularity of your timing ===\n\nI suspect you know more than me here, but maybe my pointers are useful anyway...\n\nDecide if you want to measure overall program runtime, or dive into\ndetails. I used both a simple 'time' and the better 'hyperfine' for\nthe former, and used both 'perf' and GIT_TRACE2_PERF for the latter.\nOne nice thing about GIT_TRACE2_PERF was I wrote a simple program to\naggregate the times per region and provide percentages, in a script at\nthe toplevel named 'summarize-perf' that I can use to prefix commands.\nThus, I could for example run from my linux clone:\n $ ../git/summarize-perf git fast-rebase --onto HEAD base hwmon-updates\nand I'd get output that looks something like (note that this is a\nsubset of the real output):\n 1.400 : 35 : label:inmemory_nonrecursive\n 0.827 : 41 : ..label:renames\n 0.019 : ( 2.2%)\n 0.803 : 37 : ....label:regular renames\n 0.004 : 31 : ....label:directory renames\n 0.001 : 31 : ....label:process renames\n 0.513 : 41 : ..label:collect_merge_info\n 0.048 : 35 : ..label:process_entries\n 0.117 : 1 : label:checkout\n 0.000 : 1 : label:record_unmerged\nand where those fields are