{"thread":{"id":"58373","subject":"[PATCH 0/2] test-mergesort: reduce memory allocation overhead of sort subcommand","startedAt":"2022-08-28T10:32:53Z","lastAt":"2022-08-28T10:34:55Z","messageCount":3,"participants":["René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"462058","messageId":"128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de","threadId":"58373","inReplyTo":null,"subject":"[PATCH 0/2] test-mergesort: reduce memory allocation overhead of sort subcommand","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-08-28T10:32:38Z","receivedAt":"2022-08-28T10:32:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The sort subcommand of the test-mergesort helper is used by p0071 to\nmeasure the performance of the linked list sort functions built by the\nmacro DEFINE_LIST_SORT.  It spends a significant amount of time\nallocating memory for the test data.  This series reduces it to allow\nfocusing more on the actual sort performance.\n\n  test-mergesort: read sort input all at once\n  test-mergesort: use mem_pool for sort input\n\n t/helper/test-mergesort.c | 40 ++++++++++++++++++++++++++-------------\n 1 file changed, 27 insertions(+), 13 deletions(-)\n\n--\n2.30.2\n"},{"id":"462059","messageId":"63cae51b-877e-0ca5-c61a-bf4f72d7dc8c@web.de","threadId":"58373","inReplyTo":"128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de","subject":"[PATCH 1/2] test-mergesort: read sort input all at once","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-08-28T10:34:05Z","receivedAt":"2022-08-28T10:34:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The sort subcommand of test-mergesort is used to test the performance of\nsorting linked lists.  It reads lines from stdin, sorts them and prints\nthe result to stdout.  Two heap allocations are done per line: One for\nthe linked list item and one for the actual line string.  That imposes a\nsignificant amount of allocation overhead.\n\nReduce it by doing the same as the sort subcommand of test-string-list,\nnamely to read the whole input file into a single buffer and then split\nit in-place.\n\nNote that t/perf/run can't be used directly to compare two versions of\ntest-mergesort because it always runs the helpers from the checked-out\nversion.  So I hand-merged the results of separate runs before and with\nthis patch:\n\nmacOS 12.5.1 on M1:\n0071.12: DEFINE_LIST_SORT unsorted     0.23(0.20+0.01)     0.22(0.20+0.01)\n0071.14: DEFINE_LIST_SORT sorted       0.12(0.10+0.01)     0.10(0.08+0.01)\n0071.16: DEFINE_LIST_SORT reversed     0.12(0.10+0.01)     0.10(0.08+0.01)\n\nGit SDK 64-bit on Windows 11 21H2 on Ryzen 7 5800H:\n0071.12: DEFINE_LIST_SORT unsorted     0.71(0.00+0.03)     0.54(0.00+0.06)\n0071.14: DEFINE_LIST_SORT sorted       0.42(0.00+0.04)     0.21(0.03+0.03)\n0071.16: DEFINE_LIST_SORT reversed     0.42(0.06+0.01)     0.21(0.01+0.04)\n\nDebian bullseye on WSL2 on the same system:\n0071.12: DEFINE_LIST_SORT unsorted     0.41(0.39+0.02)     0.29(0.27+0.01)\n0071.14: DEFINE_LIST_SORT sorted       0.11(0.08+0.02)     0.07(0.06+0.01)\n0071.16: DEFINE_LIST_SORT reversed     0.11(0.08+0.02)     0.07(0.04+0.03)\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n t/helper/test-mergesort.c | 38 +++++++++++++++++++++++++-------------\n 1 file changed, 25 insertions(+), 13 deletions(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 202e54a7ff..540537224f 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -22,21 +22,33 @@ static int compare_strings(const struct line *x, const struct line *y)\n\n static int sort_stdin(void)\n {\n-\tstruct line *line, *p = NULL, *lines = NULL;\n+\tstruct line *lines;\n+\tstruct line **tail = &lines;\n \tstruct strbuf sb = STRBUF_INIT;\n-\n-\twhile (!strbuf_getline(&sb, stdin)) {\n-\t\tline = xmalloc(sizeof(struct line));\n-\t\tline->text = strbuf_detach(&sb, NULL);\n-\t\tif (p) {\n-\t\t\tline->next = p->next;\n-\t\t\tp->next = line;\n-\t\t} else {\n-\t\t\tline->next = NULL;\n-\t\t\tlines = line;\n-\t\t}\n-\t\tp = line;\n+\tchar *p;\n+\n+\tstrbuf_read(&sb, 0, 0);\n+\n+\t/*\n+\t * Split by newline, but don't create an item\n+\t * for the empty string after the last separator.\n+\t */\n+\tif (sb.len && sb.buf[sb.len - 1] == '\\n')\n+\t\tstrbuf_setlen(&sb, sb.len - 1);\n+\n+\tp = sb.buf;\n+\tfor (;;) {\n+\t\tchar *eol = strchr(p, '\\n');\n+\t\tstruct line *line = xmalloc(sizeof(*line));\n+\t\tline->text = p;\n+\t\t*tail = line;\n+\t\ttail = &line->next;\n+\t\tif (!eol)\n+\t\t\tbreak;\n+\t\t*eol = '\\0';\n+\t\tp = eol + 1;\n \t}\n+\t*tail = NULL;\n\n \tsort_lines(&lines, compare_strings);\n\n--\n2.30.2\n"},{"id":"462060","messageId":"a597ca34-04d7-4505-2e6b-f8f33d7e817e@web.de","threadId":"58373","inReplyTo":"128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de","subject":"[PATCH 2/2] test-mergesort: use mem_pool for sort input","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-08-28T10:34:47Z","receivedAt":"2022-08-28T10:34:55Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The previous patch almost halved the number of heap allocations for the\nsort subcommand.  Reduce it further by using a mem_pool for the line\nobjects.\n\nNote that t/perf/run can't be used directly to compare two versions of\ntest-mergesort because it always runs the helpers from the checked-out\nversion.  So I hand-merged the results of separate runs before and with\nthis patch:\n\nmacOS 12.5.1 on M1:\n0071.12: DEFINE_LIST_SORT unsorted     0.22(0.20+0.01)     0.21(0.19+0.01)\n0071.14: DEFINE_LIST_SORT sorted       0.10(0.08+0.01)     0.10(0.08+0.01)\n0071.16: DEFINE_LIST_SORT reversed     0.10(0.08+0.01)     0.10(0.08+0.01)\n\nGit SDK 64-bit on Windows 11 21H2 on Ryzen 7 5800H:\n0071.12: DEFINE_LIST_SORT unsorted     0.54(0.00+0.06)     0.44(0.01+0.06)\n0071.14: DEFINE_LIST_SORT sorted       0.21(0.03+0.03)     0.19(0.04+0.01)\n0071.16: DEFINE_LIST_SORT reversed     0.21(0.01+0.04)     0.19(0.04+0.04)\n\nDebian bullseye on WSL2 on the same system:\n0071.12: DEFINE_LIST_SORT unsorted     0.29(0.27+0.01)     0.22(0.19+0.02)\n0071.14: DEFINE_LIST_SORT sorted       0.07(0.06+0.01)     0.06(0.04+0.02)\n0071.16: DEFINE_LIST_SORT reversed     0.07(0.04+0.03)     0.06(0.04+0.02)\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n t/helper/test-mergesort.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c\nindex 540537224f..335e5bb3a9 100644\n--- a/t/helper/test-mergesort.c\n+++ b/t/helper/test-mergesort.c\n@@ -25,6 +25,7 @@ static int sort_stdin(void)\n \tstruct line *lines;\n \tstruct line **tail = &lines;\n \tstruct strbuf sb = STRBUF_INIT;\n+\tstruct mem_pool lines_pool;\n \tchar *p;\n\n \tstrbuf_read(&sb, 0, 0);\n@@ -36,10 +37,11 @@ static int sort_stdin(void)\n \tif (sb.len && sb.buf[sb.len - 1] == '\\n')\n \t\tstrbuf_setlen(&sb, sb.len - 1);\n\n+\tmem_pool_init(&lines_pool, 0);\n \tp = sb.buf;\n \tfor (;;) {\n \t\tchar *eol = strchr(p, '\\n');\n-\t\tstruct line *line = xmalloc(sizeof(*line));\n+\t\tstruct line *line = mem_pool_alloc(&lines_pool, sizeof(*line));\n \t\tline->text = p;\n \t\t*tail = line;\n \t\ttail = &line->next;\n--\n2.30.2\n"}]}