{"thread":{"id":"60992","subject":"[PATCH 0/2] name-rev: use memory pool for name strings","startedAt":"2024-02-25T11:40:00Z","lastAt":"2024-03-07T09:58:42Z","messageCount":10,"participants":["René Scharfe","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"489307","messageId":"20240225113947.89357-1-l.s.r@web.de","threadId":"60992","inReplyTo":null,"subject":"[PATCH 0/2] name-rev: use memory pool for name strings","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2024-02-25T11:39:43Z","receivedAt":"2024-02-25T11:40:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Avoid awkward string buffer pre-sizing by adding and using an efficient\nmem-pool-backed string format function.\n\n  mem-pool: add mem_pool_strfmt()\n  name-rev: use mem_pool_strfmt()\n\n builtin/name-rev.c | 39 ++++++++++++++++++++-------------------\n mem-pool.c         | 39 +++++++++++++++++++++++++++++++++++++++\n mem-pool.h         |  5 +++++\n 3 files changed, 64 insertions(+), 19 deletions(-)\n\n--\n2.44.0\n\n"},{"id":"489308","messageId":"20240225113947.89357-3-l.s.r@web.de","threadId":"60992","inReplyTo":"20240225113947.89357-1-l.s.r@web.de","subject":"[PATCH 2/2] name-rev: use mem_pool_strfmt()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2024-02-25T11:39:45Z","receivedAt":"2024-02-25T11:40:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"1c56fc2084 (name-rev: pre-size buffer in get_parent_name(), 2020-02-04)\ngot a big performance boost in an unusual repository by calculating the\nname length in advance.  This is a bit awkward, as it references the\nname components twice.\n\nUse a memory pool to store the strings for the struct rev_name member\ntip_name.  Using mem_pool_strfmt() allows efficient allocation without\nexplicit size calculation.  This simplifies the formatting part of the\ncode without giving up performance:\n\nBenchmark 1: ./git_2.44.0 -C ../chromium/src name-rev --all\n  Time (mean ± σ):      1.231 s ±  0.013 s    [User: 1.082 s, System: 0.136 s]\n  Range (min … max):    1.214 s …  1.252 s    10 runs\n\nBenchmark 2: ./git -C ../chromium/src name-rev --all\n  Time (mean ± σ):      1.220 s ±  0.020 s    [User: 1.083 s, System: 0.130 s]\n  Range (min … max):    1.197 s …  1.254 s    10 runs\n\nDon't bother discarding the memory pool just before exiting.  The effort\nfor that would be very low, but actually measurable in the above\nexample, with no benefit to users.  At least UNLEAK it to calm down leak\ncheckers.  This addresses the leaks that 45a14f578e (Revert \"name-rev:\nrelease unused name strings\", 2022-04-22) brought back.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\nThis doesn't make any test script leak-free, though.\n\n builtin/name-rev.c | 39 ++++++++++++++++++++-------------------\n 1 file changed, 20 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 2dd1807c4e..ad9930c831 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -15,6 +15,7 @@\n #include \"commit-slab.h\"\n #include \"commit-graph.h\"\n #include \"wildmatch.h\"\n+#include \"mem-pool.h\"\n\n /*\n  * One day.  See the 'name a rev shortly after epoch' test in t6120 when\n@@ -155,30 +156,25 @@ static struct rev_name *create_or_update_name(struct commit *commit,\n \treturn name;\n }\n\n-static char *get_parent_name(const struct rev_name *name, int parent_number)\n+static char *get_parent_name(const struct rev_name *name, int parent_number,\n+\t\t\t     struct mem_pool *string_pool)\n {\n-\tstruct strbuf sb = STRBUF_INIT;\n \tsize_t len;\n\n \tstrip_suffix(name->tip_name, \"^0\", &len);\n \tif (name->generation > 0) {\n-\t\tstrbuf_grow(&sb, len +\n-\t\t\t    1 + decimal_width(name->generation) +\n-\t\t\t    1 + decimal_width(parent_number));\n-\t\tstrbuf_addf(&sb, \"%.*s~%d^%d\", (int)len, name->tip_name,\n-\t\t\t    name->generation, parent_number);\n+\t\treturn mem_pool_strfmt(string_pool, \"%.*s~%d^%d\",\n+\t\t\t\t       (int)len, name->tip_name,\n+\t\t\t\t       name->generation, parent_number);\n \t} else {\n-\t\tstrbuf_grow(&sb, len +\n-\t\t\t    1 + decimal_width(parent_number));\n-\t\tstrbuf_addf(&sb, \"%.*s^%d\", (int)len, name->tip_name,\n-\t\t\t    parent_number);\n+\t\treturn mem_pool_strfmt(string_pool, \"%.*s^%d\",\n+\t\t\t\t       (int)len, name->tip_name, parent_number);\n \t}\n-\treturn strbuf_detach(&sb, NULL);\n }\n\n static void name_rev(struct commit *start_commit,\n \t\tconst char *tip_name, timestamp_t taggerdate,\n-\t\tint from_tag, int deref)\n+\t\tint from_tag, int deref, struct mem_pool *string_pool)\n {\n \tstruct prio_queue queue;\n \tstruct commit *commit;\n@@ -195,9 +191,10 @@ static void name_rev(struct commit *start_commit,\n \tif (!start_name)\n \t\treturn;\n \tif (deref)\n-\t\tstart_name->tip_name = xstrfmt(\"%s^0\", tip_name);\n+\t\tstart_name->tip_name = mem_pool_strfmt(string_pool, \"%s^0\",\n+\t\t\t\t\t\t       tip_name);\n \telse\n-\t\tstart_name->tip_name = xstrdup(tip_name);\n+\t\tstart_name->tip_name = mem_pool_strdup(string_pool, tip_name);\n\n \tmemset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */\n \tprio_queue_put(&queue, start_commit);\n@@ -235,7 +232,8 @@ static void name_rev(struct commit *start_commit,\n \t\t\t\tif (parent_number > 1)\n \t\t\t\t\tparent_name->tip_name =\n \t\t\t\t\t\tget_parent_name(name,\n-\t\t\t\t\t\t\t\tparent_number);\n+\t\t\t\t\t\t\t\tparent_number,\n+\t\t\t\t\t\t\t\tstring_pool);\n \t\t\t\telse\n \t\t\t\t\tparent_name->tip_name = name->tip_name;\n \t\t\t\tALLOC_GROW(parents_to_queue,\n@@ -415,7 +413,7 @@ static int name_ref(const char *path, const struct object_id *oid,\n \treturn 0;\n }\n\n-static void name_tips(void)\n+static void name_tips(struct mem_pool *string_pool)\n {\n \tint i;\n\n@@ -428,7 +426,7 @@ static void name_tips(void)\n \t\tstruct tip_table_entry *e = &tip_table.table[i];\n \t\tif (e->commit) {\n \t\t\tname_rev(e->commit, e->refname, e->taggerdate,\n-\t\t\t\t e->from_tag, e->deref);\n+\t\t\t\t e->from_tag, e->deref, string_pool);\n \t\t}\n \t}\n }\n@@ -561,6 +559,7 @@ static void name_rev_line(char *p, struct name_ref_data *data)\n\n int cmd_name_rev(int argc, const char **argv, const char *prefix)\n {\n+\tstruct mem_pool string_pool;\n \tstruct object_array revs = OBJECT_ARRAY_INIT;\n \tint all = 0, annotate_stdin = 0, transform_stdin = 0, allow_undefined = 1, always = 0, peel_tag = 0;\n \tstruct name_ref_data data = { 0, 0, STRING_LIST_INIT_NODUP, STRING_LIST_INIT_NODUP };\n@@ -587,6 +586,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tOPT_END(),\n \t};\n\n+\tmem_pool_init(&string_pool, 0);\n \tinit_commit_rev_name(&rev_names);\n \tgit_config(git_default_config, NULL);\n \targc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);\n@@ -648,7 +648,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \tadjust_cutoff_timestamp_for_slop();\n\n \tfor_each_ref(name_ref, &data);\n-\tname_tips();\n+\tname_tips(&string_pool);\n\n \tif (annotate_stdin) {\n \t\tstruct strbuf sb = STRBUF_INIT;\n@@ -676,6 +676,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\t\t\t  always, allow_undefined, data.name_only);\n \t}\n\n+\tUNLEAK(string_pool);\n \tUNLEAK(revs);\n \treturn 0;\n }\n--\n2.44.0\n\n"},{"id":"489309","messageId":"20240225113947.89357-2-l.s.r@web.de","threadId":"60992","inReplyTo":"20240225113947.89357-1-l.s.r@web.de","subject":"[PATCH 1/2] mem-pool: add mem_pool_strfmt()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2024-02-25T11:39:44Z","receivedAt":"2024-02-25T11:40:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a function for building a string, printf style, using a memory pool.\nIt uses the free space in the current block in the first attempt.  If\nthat suffices then the result can already be used without copying or\nreformatting.\n\nFor strings that are significantly shorter on average than the block\nsize (ca. 1 MiB by default) this is the case most of the time, leading\nto a better perfomance than a solution that doesn't access mem-pool\ninternals.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n mem-pool.c | 39 +++++++++++++++++++++++++++++++++++++++\n mem-pool.h |  5 +++++\n 2 files changed, 44 insertions(+)\n\ndiff --git a/mem-pool.c b/mem-pool.c\nindex c7d6256020..2078c22b09 100644\n--- a/mem-pool.c\n+++ b/mem-pool.c\n@@ -107,6 +107,45 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n \treturn r;\n }\n\n+static char *mem_pool_strvfmt(struct mem_pool *pool, const char *fmt,\n+\t\t\t      va_list ap)\n+{\n+\tstruct mp_block *block = pool->mp_block;\n+\tchar *next_free = block ? block->next_free : NULL;\n+\tsize_t available = block ? block->end - block->next_free : 0;\n+\tva_list cp;\n+\tint len, len2;\n+\tchar *ret;\n+\n+\tva_copy(cp, ap);\n+\tlen = vsnprintf(next_free, available, fmt, cp);\n+\tva_end(cp);\n+\tif (len < 0)\n+\t\tBUG(\"your vsnprintf is broken (returned %d)\", len);\n+\n+\tret = mem_pool_alloc(pool, len + 1);  /* 1 for NUL */\n+\n+\t/* Shortcut; relies on mem_pool_alloc() not touching buffer contents. */\n+\tif (ret == next_free)\n+\t\treturn ret;\n+\n+\tlen2 = vsnprintf(ret, len + 1, fmt, ap);\n+\tif (len2 != len)\n+\t\tBUG(\"your vsnprintf is broken (returns inconsistent lengths)\");\n+\treturn ret;\n+}\n+\n+char *mem_pool_strfmt(struct mem_pool *pool, const char *fmt, ...)\n+{\n+\tva_list ap;\n+\tchar *ret;\n+\n+\tva_start(ap, fmt);\n+\tret = mem_pool_strvfmt(pool, fmt, ap);\n+\tva_end(ap);\n+\treturn ret;\n+}\n+\n void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size)\n {\n \tsize_t len = st_mult(count, size);\ndiff --git a/mem-pool.h b/mem-pool.h\nindex fe7507f022..d1c66413ec 100644\n--- a/mem-pool.h\n+++ b/mem-pool.h\n@@ -47,6 +47,11 @@ void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);\n char *mem_pool_strdup(struct mem_pool *pool, const char *str);\n char *mem_pool_strndup(struct mem_pool *pool, const char *str, size_t len);\n\n+/*\n+ * Allocate memory from the memory pool and format a string into it.\n+ */\n+char *mem_pool_strfmt(struct mem_pool *pool, const char *fmt, ...);\n+\n /*\n  * Move the memory associated with the 'src' pool to the 'dst' pool. The 'src'\n  * pool will be empty and not contain any memory. It still needs to be free'd\n--\n2.44.0\n\n"},{"id":"489340","messageId":"xmqqfrxghtef.fsf@gitster.g","threadId":"60992","inReplyTo":"20240225113947.89357-3-l.s.r@web.de","subject":"Re: [PATCH 2/2] name-rev: use mem_pool_strfmt()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-02-26T02:05:28Z","receivedAt":"2024-02-26T02:05:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> 1c56fc2084 (name-rev: pre-size buffer in get_parent_name(), 2020-02-04)\n> got a big performance boost in an unusual repository by calculating the\n> name length in advance.  This is a bit awkward, as it references the\n> name components twice.\n>\n> Use a memory pool to store the strings for the struct rev_name member\n> tip_name.  Using mem_pool_strfmt() allows efficient allocation without\n> explicit size calculation.  This simplifies the formatting part of the\n> code without giving up performance:\n>\n> Benchmark 1: ./git_2.44.0 -C ../chromium/src name-rev --all\n>   Time (mean ± σ):      1.231 s ±  0.013 s    [User: 1.082 s, System: 0.136 s]\n>   Range (min … max):    1.214 s …  1.252 s    10 runs\n>\n> Benchmark 2: ./git -C ../chromium/src name-rev --all\n>   Time (mean ± σ):      1.220 s ±  0.020 s    [User: 1.083 s, System: 0.130 s]\n>   Range (min … max):    1.197 s …  1.254 s    10 runs\n>\n> Don't bother discarding the memory pool just before exiting.  The effort\n> for that would be very low, but actually measurable in the above\n> example, with no benefit to users.  At least UNLEAK it to calm down leak\n> checkers.  This addresses the leaks that 45a14f578e (Revert \"name-rev:\n> release unused name strings\", 2022-04-22) brought back.\n>\n> Signed-off-by: René Scharfe <l.s.r@web.de>\n> ---\n> This doesn't make any test script leak-free, though.\n\nHmph, is the root cause of the leak because no sensible ownership\nrules are applied to .tip_name?  Sometimes it is allocated for the\nparitcular rev_name, but some other times the pointer is copied from\nanother rev_name.tip_name?  As the way currently the code uses the\n.tip_name member seems to be \"allocate and use without any freeing\",\nI tend to agree that throwing them into mem-pool does make sense.\n\n>  builtin/name-rev.c | 39 ++++++++++++++++++++-------------------\n>  1 file changed, 20 insertions(+), 19 deletions(-)\n>\n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index 2dd1807c4e..ad9930c831 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -15,6 +15,7 @@\n>  #include \"commit-slab.h\"\n>  #include \"commit-graph.h\"\n>  #include \"wildmatch.h\"\n> +#include \"mem-pool.h\"\n>\n>  /*\n>   * One day.  See the 'name a rev shortly after epoch' test in t6120 when\n> @@ -155,30 +156,25 @@ static struct rev_name *create_or_update_name(struct commit *commit,\n>  \treturn name;\n>  }\n>\n> -static char *get_parent_name(const struct rev_name *name, int parent_number)\n> +static char *get_parent_name(const struct rev_name *name, int parent_number,\n> +\t\t\t     struct mem_pool *string_pool)\n>  {\n> -\tstruct strbuf sb = STRBUF_INIT;\n>  \tsize_t len;\n>\n>  \tstrip_suffix(name->tip_name, \"^0\", &len);\n>  \tif (name->generation > 0) {\n> -\t\tstrbuf_grow(&sb, len +\n> -\t\t\t    1 + decimal_width(name->generation) +\n> -\t\t\t    1 + decimal_width(parent_number));\n> -\t\tstrbuf_addf(&sb, \"%.*s~%d^%d\", (int)len, name->tip_name,\n> -\t\t\t    name->generation, parent_number);\n> +\t\treturn mem_pool_strfmt(string_pool, \"%.*s~%d^%d\",\n> +\t\t\t\t       (int)len, name->tip_name,\n> +\t\t\t\t       name->generation, parent_number);\n>  \t} else {\n> -\t\tstrbuf_grow(&sb, len +\n> -\t\t\t    1 + decimal_width(parent_number));\n> -\t\tstrbuf_addf(&sb, \"%.*s^%d\", (int)len, name->tip_name,\n> -\t\t\t    parent_number);\n> +\t\treturn mem_pool_strfmt(string_pool, \"%.*s^%d\",\n> +\t\t\t\t       (int)len, name->tip_name, parent_number);\n>  \t}\n> -\treturn strbuf_detach(&sb, NULL);\n>  }\n>\n>  static void name_rev(struct commit *start_commit,\n>  \t\tconst char *tip_name, timestamp_t taggerdate,\n> -\t\tint from_tag, int deref)\n> +\t\tint from_tag, int deref, struct mem_pool *string_pool)\n>  {\n>  \tstruct prio_queue queue;\n>  \tstruct commit *commit;\n> @@ -195,9 +191,10 @@ static void name_rev(struct commit *start_commit,\n>  \tif (!start_name)\n>  \t\treturn;\n>  \tif (deref)\n> -\t\tstart_name->tip_name = xstrfmt(\"%s^0\", tip_name);\n> +\t\tstart_name->tip_name = mem_pool_strfmt(string_pool, \"%s^0\",\n> +\t\t\t\t\t\t       tip_name);\n>  \telse\n> -\t\tstart_name->tip_name = xstrdup(tip_name);\n> +\t\tstart_name->tip_name = mem_pool_strdup(string_pool, tip_name);\n>\n>  \tmemset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */\n>  \tprio_queue_put(&queue, start_commit);\n> @@ -235,7 +232,8 @@ static void name_rev(struct commit *start_commit,\n>  \t\t\t\tif (parent_number > 1)\n>  \t\t\t\t\tparent_name->tip_name =\n>  \t\t\t\t\t\tget_parent_name(name,\n> -\t\t\t\t\t\t\t\tparent_number);\n> +\t\t\t\t\t\t\t\tparent_number,\n> +\t\t\t\t\t\t\t\tstring_pool);\n>  \t\t\t\telse\n>  \t\t\t\t\tparent_name->tip_name = name->tip_name;\n>  \t\t\t\tALLOC_GROW(parents_to_queue,\n> @@ -415,7 +413,7 @@ static int name_ref(const char *path, const struct object_id *oid,\n>  \treturn 0;\n>  }\n>\n> -static void name_tips(void)\n> +static void name_tips(struct mem_pool *string_pool)\n>  {\n>  \tint i;\n>\n> @@ -428,7 +426,7 @@ static void name_tips(void)\n>  \t\tstruct tip_table_entry *e = &tip_table.table[i];\n>  \t\tif (e->commit) {\n>  \t\t\tname_rev(e->commit, e->refname, e->taggerdate,\n> -\t\t\t\t e->from_tag, e->deref);\n> +\t\t\t\t e->from_tag, e->deref, string_pool);\n>  \t\t}\n>  \t}\n>  }\n> @@ -561,6 +559,7 @@ static void name_rev_line(char *p, struct name_ref_data *data)\n>\n>  int cmd_name_rev(int argc, const char **argv, const char *prefix)\n>  {\n> +\tstruct mem_pool string_pool;\n>  \tstruct object_array revs = OBJECT_ARRAY_INIT;\n>  \tint all = 0, annotate_stdin = 0, transform_stdin = 0, allow_undefined = 1, always = 0, peel_tag = 0;\n>  \tstruct name_ref_data data = { 0, 0, STRING_LIST_INIT_NODUP, STRING_LIST_INIT_NODUP };\n> @@ -587,6 +586,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n>  \t\tOPT_END(),\n>  \t};\n>\n> +\tmem_pool_init(&string_pool, 0);\n>  \tinit_commit_rev_name(&rev_names);\n>  \tgit_config(git_default_config, NULL);\n>  \targc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);\n> @@ -648,7 +648,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n>  \tadjust_cutoff_timestamp_for_slop();\n>\n>  \tfor_each_ref(name_ref, &data);\n> -\tname_tips();\n> +\tname_tips(&string_pool);\n>\n>  \tif (annotate_stdin) {\n>  \t\tstruct strbuf sb = STRBUF_INIT;\n> @@ -676,6 +676,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n>  \t\t\t\t  always, allow_undefined, data.name_only);\n>  \t}\n>\n> +\tUNLEAK(string_pool);\n>  \tUNLEAK(revs);\n>  \treturn 0;\n>  }\n> --\n> 2.44.0\n"},{"id":"489352","messageId":"20240226070844.GB780982@coredump.intra.peff.net","threadId":"60992","inReplyTo":"20240225113947.89357-2-l.s.r@web.de","subject":"Re: [PATCH 1/2] mem-pool: add mem_pool_strfmt()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-02-26T07:08:44Z","receivedAt":"2024-02-26T07:08:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Feb 25, 2024 at 12:39:44PM +0100, René Scharfe wrote:\n\n> +static char *mem_pool_strvfmt(struct mem_pool *pool, const char *fmt,\n> +\t\t\t      va_list ap)\n> +{\n> +\tstruct mp_block *block = pool->mp_block;\n> +\tchar *next_free = block ? block->next_free : NULL;\n> +\tsize_t available = block ? block->end - block->next_free : 0;\n> +\tva_list cp;\n> +\tint len, len2;\n> +\tchar *ret;\n> +\n> +\tva_copy(cp, ap);\n> +\tlen = vsnprintf(next_free, available, fmt, cp);\n> +\tva_end(cp);\n> +\tif (len < 0)\n> +\t\tBUG(\"your vsnprintf is broken (returned %d)\", len);\n> +\n> +\tret = mem_pool_alloc(pool, len + 1);  /* 1 for NUL */\n> +\n> +\t/* Shortcut; relies on mem_pool_alloc() not touching buffer contents. */\n> +\tif (ret == next_free)\n> +\t\treturn ret;\n> +\n> +\tlen2 = vsnprintf(ret, len + 1, fmt, ap);\n> +\tif (len2 != len)\n> +\t\tBUG(\"your vsnprintf is broken (returns inconsistent lengths)\");\n> +\treturn ret;\n> +}\n\nThis is pulling heavily from strbuf_vaddf(). This might be a dumb idea,\nbut... would it be reasonable to instead push a global flag that causes\nxmalloc() to use a memory pool instead of the regular heap?\n\nThen you could do something like:\n\n  push_mem_pool(pool);\n  str = xstrfmt(\"%.*s~%d^%d\", ...etc...);\n  pop_mem_pool(pool);\n\nIt's a little more involved at the caller, but it means that it now\nworks for all allocations, not just this one string helper.\n\nObviously you'd want it to be a thread-local value to prevent races. But\nI still wonder if it could cause havoc when some sub-function makes an\nallocation that the caller does not expect.\n\n-Peff\n"},{"id":"489401","messageId":"53cfe0db-458e-4a43-b5ac-0c01cc6e79ea@web.de","threadId":"60992","inReplyTo":"xmqqfrxghtef.fsf@gitster.g","subject":"Re: [PATCH 2/2] name-rev: use mem_pool_strfmt()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2024-02-26T18:06:39Z","receivedAt":"2024-02-26T18:06:44Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 26.02.24 um 03:05 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n>\n>> 1c56fc2084 (name-rev: pre-size buffer in get_parent_name(), 2020-02-04)\n>> got a big performance boost in an unusual repository by calculating the\n>> name length in advance.  This is a bit awkward, as it references the\n>> name components twice.\n>>\n>> Use a memory pool to store the strings for the struct rev_name member\n>> tip_name.  Using mem_pool_strfmt() allows efficient allocation without\n>> explicit size calculation.  This simplifies the formatting part of the\n>> code without giving up performance:\n>>\n>> Benchmark 1: ./git_2.44.0 -C ../chromium/src name-rev --all\n>>   Time (mean ± σ):      1.231 s ±  0.013 s    [User: 1.082 s, System: 0.136 s]\n>>   Range (min … max):    1.214 s …  1.252 s    10 runs\n>>\n>> Benchmark 2: ./git -C ../chromium/src name-rev --all\n>>   Time (mean ± σ):      1.220 s ±  0.020 s    [User: 1.083 s, System: 0.130 s]\n>>   Range (min … max):    1.197 s …  1.254 s    10 runs\n>>\n>> Don't bother discarding the memory pool just before exiting.  The effort\n>> for that would be very low, but actually measurable in the above\n>> example, with no benefit to users.  At least UNLEAK it to calm down leak\n>> checkers.  This addresses the leaks that 45a14f578e (Revert \"name-rev:\n>> release unused name strings\", 2022-04-22) brought back.\n>>\n>> Signed-off-by: René Scharfe <l.s.r@web.de>\n>> ---\n>> This doesn't make any test script leak-free, though.\n>\n> Hmph, is the root cause of the leak because no sensible ownership\n> rules are applied to .tip_name?  Sometimes it is allocated for the\n> paritcular rev_name, but some other times the pointer is copied from\n> another rev_name.tip_name?  As the way currently the code uses the\n> .tip_name member seems to be \"allocate and use without any freeing\",\n> I tend to agree that throwing them into mem-pool does make sense.\n\nYes, the tip_name string is shared between child and first parent (and\nits first parent and so on, until a better name is found.  Without this\nsharing the peak memory footprint of \"git name-rev --all\" in Git's repo\ngoes from 40011328 to 46286528 for me currently.\n\nI'm not too worried about the leak, though, as we can't release the\nmemory until we're done anyway.  The ability to build strings without\nhaving to calculate their sizes in advance (either by running vsnprintf\ntwice, which is slow, or by doing format-specific calculations) is more\ninteresting to me.\n\nThe reason why none of the test scripts become leak-free is other\ncommands (i.e. not git name-rev) that are still leaking.\n\nRené\n"},{"id":"489405","messageId":"1868c502-b915-42fd-8cb2-efe90429f9b7@web.de","threadId":"60992","inReplyTo":"20240226070844.GB780982@coredump.intra.peff.net","subject":"Re: [PATCH 1/2] mem-pool: add mem_pool_strfmt()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2024-02-26T18:17:00Z","receivedAt":"2024-02-26T18:17:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 26.02.24 um 08:08 schrieb Jeff King:\n> On Sun, Feb 25, 2024 at 12:39:44PM +0100, René Scharfe wrote:\n>\n>> +static char *mem_pool_strvfmt(struct mem_pool *pool, const char *fmt,\n>> +\t\t\t      va_list ap)\n>> +{\n>> +\tstruct mp_block *block = pool->mp_block;\n>> +\tchar *next_free = block ? block->next_free : NULL;\n>> +\tsize_t available = block ? block->end - block->next_free : 0;\n>> +\tva_list cp;\n>> +\tint len, len2;\n>> +\tchar *ret;\n>> +\n>> +\tva_copy(cp, ap);\n>> +\tlen = vsnprintf(next_free, available, fmt, cp);\n>> +\tva_end(cp);\n>> +\tif (len < 0)\n>> +\t\tBUG(\"your vsnprintf is broken (returned %d)\", len);\n>> +\n>> +\tret = mem_pool_alloc(pool, len + 1);  /* 1 for NUL */\n>> +\n>> +\t/* Shortcut; relies on mem_pool_alloc() not touching buffer contents. */\n>> +\tif (ret == next_free)\n>> +\t\treturn ret;\n>> +\n>> +\tlen2 = vsnprintf(ret, len + 1, fmt, ap);\n>> +\tif (len2 != len)\n>> +\t\tBUG(\"your vsnprintf is broken (returns inconsistent lengths)\");\n>> +\treturn ret;\n>> +}\n>\n> This is pulling heavily from strbuf_vaddf(). This might be a dumb idea,\n> but... would it be reasonable to instead push a global flag that causes\n> xmalloc() to use a memory pool instead of the regular heap?\n>\n> Then you could do something like:\n>\n>   push_mem_pool(pool);\n>   str = xstrfmt(\"%.*s~%d^%d\", ...etc...);\n>   pop_mem_pool(pool);\n>\n> It's a little more involved at the caller, but it means that it now\n> works for all allocations, not just this one string helper.\n\nThat would allow to keep track of allocations that would otherwise leak.\nWe can achieve that more easily by pushing the pointer to a global array\nand never freeing it.  Hmm.\n\nIt would not allow the shortcut of using the vast pool as a scratch\nspace to format the string with a single vsnprintf call in most cases.\nOr am I missing something?\n\nRené\n"},{"id":"489466","messageId":"20240227075350.GE3263678@coredump.intra.peff.net","threadId":"60992","inReplyTo":"1868c502-b915-42fd-8cb2-efe90429f9b7@web.de","subject":"Re: [PATCH 1/2] mem-pool: add mem_pool_strfmt()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-02-27T07:53:50Z","receivedAt":"2024-02-27T07:53:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 26, 2024 at 07:17:00PM +0100, René Scharfe wrote:\n\n> > This is pulling heavily from strbuf_vaddf(). This might be a dumb idea,\n> > but... would it be reasonable to instead push a global flag that causes\n> > xmalloc() to use a memory pool instead of the regular heap?\n> >\n> > Then you could do something like:\n> >\n> >   push_mem_pool(pool);\n> >   str = xstrfmt(\"%.*s~%d^%d\", ...etc...);\n> >   pop_mem_pool(pool);\n> >\n> > It's a little more involved at the caller, but it means that it now\n> > works for all allocations, not just this one string helper.\n> \n> That would allow to keep track of allocations that would otherwise leak.\n> We can achieve that more easily by pushing the pointer to a global array\n> and never freeing it.  Hmm.\n\nI see two uses for memory pools:\n\n  1. You want to optimize allocations (either locality or per-allocation\n     overhead).\n\n  2. You want to make a bunch of allocations with the same lifetime\n     without worrying about their lifetime otherwise. And then you can\n     free them all in one swoop at the end.\n\nAnd my impression is that you were interested in (2) here. If what\nyou're saying is that another way to do that is:\n\n  str = xstrfmt(...whatever...);\n  attach_to_pool(pool, str);\n\n  ...much later...\n  free_pool(pool);\n\nthen yeah, I'd agree. And that is a lot less tricky / invasive than what\nI suggested.\n\n> It would not allow the shortcut of using the vast pool as a scratch\n> space to format the string with a single vsnprintf call in most cases.\n> Or am I missing something?\n\nSo here it sounds like you do care about some of the performance\naspects. So no, it would not allow that. You'd be using the vast pool of\nheap memory provided by malloc(), and trusting that a call to malloc()\nis not that expensive in practice. I don't know how true that is, or how\nmuch it matters for this case.\n\n-Peff\n"},{"id":"489553","messageId":"3aed87d0-4789-4e96-8c6c-31cab2d996cc@web.de","threadId":"60992","inReplyTo":"20240227075350.GE3263678@coredump.intra.peff.net","subject":"Re: [PATCH 1/2] mem-pool: add mem_pool_strfmt()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2024-02-27T17:58:26Z","receivedAt":"2024-02-27T17:58:35Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 27.02.24 um 08:53 schrieb Jeff King:\n> On Mon, Feb 26, 2024 at 07:17:00PM +0100, René Scharfe wrote:\n>\n>>> This is pulling heavily from strbuf_vaddf(). This might be a dumb idea,\n>>> but... would it be reasonable to instead push a global flag that causes\n>>> xmalloc() to use a memory pool instead of the regular heap?\n>>>\n>>> Then you could do something like:\n>>>\n>>>   push_mem_pool(pool);\n>>>   str = xstrfmt(\"%.*s~%d^%d\", ...etc...);\n>>>   pop_mem_pool(pool);\n>>>\n>>> It's a little more involved at the caller, but it means that it now\n>>> works for all allocations, not just this one string helper.\n>>\n>> That would allow to keep track of allocations that would otherwise leak.\n>> We can achieve that more easily by pushing the pointer to a global array\n>> and never freeing it.  Hmm.\n>\n> I see two uses for memory pools:\n>\n>   1. You want to optimize allocations (either locality or per-allocation\n>      overhead).\n>\n>   2. You want to make a bunch of allocations with the same lifetime\n>      without worrying about their lifetime otherwise. And then you can\n>      free them all in one swoop at the end.\n>\n> And my impression is that you were interested in (2) here. If what\n> you're saying is that another way to do that is:\n>\n>   str = xstrfmt(...whatever...);\n>   attach_to_pool(pool, str);\n>\n>   ...much later...\n>   free_pool(pool);\n>\n> then yeah, I'd agree. And that is a lot less tricky / invasive than what\n> I suggested.\n>\n>> It would not allow the shortcut of using the vast pool as a scratch\n>> space to format the string with a single vsnprintf call in most cases.\n>> Or am I missing something?\n>\n> So here it sounds like you do care about some of the performance\n> aspects. So no, it would not allow that. You'd be using the vast pool of\n> heap memory provided by malloc(), and trusting that a call to malloc()\n> is not that expensive in practice. I don't know how true that is, or how\n> much it matters for this case.\n\nIn the specific use case we can look at three cases:\n\n1. xstrfmt() [before 1c56fc2084]\n2. size calculation + pre-size + strbuf_addf() [1c56fc2084]\n3. mem_pool_strfmt() [this patch]\n\nThe performance of 2 and 3 is basically the same, 1 was worse.\n\nxstrfmt() and strbuf_addf() both wrap strbuf_vaddf(), which uses\nmalloc() and vsnprintf().  My conclusion is that malloc() is fast\nenough, but running vsnprintf() twice is slow (first time to determine\nthe allocation size, second time to actually build the string).  With a\nmemory pool we almost always only need to call it once per string, and\nthat's why I use it here.\n\nThe benefit of this patch (to me) is better code readability (no more\nmanual pre-sizing) without sacrificing performance.\n\nThe ability to clear (or UNLEAK) all these strings in one go is just a\nbonus.\n\nRené\n"},{"id":"490168","messageId":"20240307095841.GD2650063@coredump.intra.peff.net","threadId":"60992","inReplyTo":"3aed87d0-4789-4e96-8c6c-31cab2d996cc@web.de","subject":"Re: [PATCH 1/2] mem-pool: add mem_pool_strfmt()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-03-07T09:58:41Z","receivedAt":"2024-03-07T09:58:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 27, 2024 at 06:58:26PM +0100, René Scharfe wrote:\n\n> >> It would not allow the shortcut of using the vast pool as a scratch\n> >> space to format the string with a single vsnprintf call in most cases.\n> >> Or am I missing something?\n> >\n> > So here it sounds like you do care about some of the performance\n> > aspects. So no, it would not allow that. You'd be using the vast pool of\n> > heap memory provided by malloc(), and trusting that a call to malloc()\n> > is not that expensive in practice. I don't know how true that is, or how\n> > much it matters for this case.\n> \n> In the specific use case we can look at three cases:\n> \n> 1. xstrfmt() [before 1c56fc2084]\n> 2. size calculation + pre-size + strbuf_addf() [1c56fc2084]\n> 3. mem_pool_strfmt() [this patch]\n> \n> The performance of 2 and 3 is basically the same, 1 was worse.\n> \n> xstrfmt() and strbuf_addf() both wrap strbuf_vaddf(), which uses\n> malloc() and vsnprintf().  My conclusion is that malloc() is fast\n> enough, but running vsnprintf() twice is slow (first time to determine\n> the allocation size, second time to actually build the string).  With a\n> memory pool we almost always only need to call it once per string, and\n> that's why I use it here.\n> \n> The benefit of this patch (to me) is better code readability (no more\n> manual pre-sizing) without sacrificing performance.\n> \n> The ability to clear (or UNLEAK) all these strings in one go is just a\n> bonus.\n\nAh, OK. I admit I did not read the series all that carefully. Mostly I\nam just concerned about a world where there are parallel-universe\nversions of every allocating function that takes a mem-pool. If it's\nlimited to this obvious string formatting variant that may not be too\nbad, though.\n\n-Peff\n"}]}