From patchwork Sun Aug 28 10:34:05 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 12957228 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EEB86ECAAD2 for ; Sun, 28 Aug 2022 10:34:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229511AbiH1KeN (ORCPT ); Sun, 28 Aug 2022 06:34:13 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41884 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229379AbiH1KeM (ORCPT ); Sun, 28 Aug 2022 06:34:12 -0400 Received: from mout.web.de (mout.web.de [217.72.192.78]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B80081B792 for ; Sun, 28 Aug 2022 03:34:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1661682846; bh=E+LtwnkhWXhMdxd5XXdpJnPNzGVBFf3B7HDBILfLOaU=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=WxSzKMdU9CgPVELXdr6ZM6HLRY3wg8ZWwu0RRe5zDl0CSFTQ3QQp134+i0d18fuZx Qk1tU0kGEP0I0vkgp2J3ZwRJJopm31Co3I38yS4gVD4pu6p9Gs9AsrkNPkYFzYGorF tG8vZi7AVYOcJVAI3VRB5yHSyqsvnUzwKN2lfo2M= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.35] ([79.203.21.84]) by smtp.web.de (mrweb105 [213.165.67.124]) with ESMTPSA (Nemesis) id 1MElZB-1ocUM92u5r-00GU2g; Sun, 28 Aug 2022 12:34:06 +0200 Message-ID: <63cae51b-877e-0ca5-c61a-bf4f72d7dc8c@web.de> Date: Sun, 28 Aug 2022 12:34:05 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.2.0 Subject: [PATCH 1/2] test-mergesort: read sort input all at once From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: git@vger.kernel.org Cc: Junio C Hamano References: <128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de> In-Reply-To: <128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de> X-Provags-ID: V03:K1:Zcz91f7RdViMoJuIP20sjfuaedx0KyxVGjhk1YPKTtTaLUfIARu a3bwHapgXbqo53QJCAjuVQjhj0OCCDFH1m1l/ckYLp8MC1Fo/NzzzfCgKpG3ax5rzQzC9z9 HlETk3u4WFcAT9+Qn8YGlu8IBfDImhY1nvP0/sIOOkuXBMBjXv78uRFVUww7xfaMCvDnl9d TMO2dFZwPBpJ7JRMRypzQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:siClq0baGIg=:f+jCv8MwUP7VvSMpdeJYi4 OCYAjpajeBgOUpE2IS452l952QJKrZWubV1hv7GdDwaLda0NHxtEcPSLU1rjKwhLMQNKhoCrv OZhhLN4MyrMLpD5YFsgqNzwRL8iHcn2CjKhPYhrTmBwweaiyAeDbznGAr/M21RwlIn48gzWOX RXbUejP+1ca3Mbg1YfDnRhTvHZGVknQSlBUbrcYgiZhlZu+EdSgXiebUc5ve3/9eb1gbFXzl6 xRwj4bCrU6Pw4AuzCU8XwZjwlxTqT/zBFqvRcJaH7HHxNo92AqSge9HcjFb7Stb43xHlFE2L/ bPHgrM941Xv026VmI4JP6KI3HaBhKbgvnVdF6tzSMYuZPYBTxRKtKlxDsLicVXJ6Z2GvrKV1/ ShdvkUGRxVf+n6EwNagUIIjxOOY6H6Fg7OyFTZtyaQysBFs7lsWyUG+Tnl5NgkiKZTy56NZGJ tCf1rb2WAx9kv0hhBGVgg2/3vZUlmS+PNUi69YagIPRJfIFqYds/Vxtuv4zKizKh4kadHx9q3 ZntdiZT9cSgj4Lp7Oey/Hrv0yWApJSESsYm5DOZNeRjnKpgElOPcuVZ4IG2Quz1r9zs2uOTtH oF7A6/8sgVxlYMWb+hyoNNvvxRhgji+HnE4WyxqNM3ATILDwmBZjnueR5qFIDW6pfFUSuvizl Awrz1xd/syyE2ELPBH7iZdJXTy21VepJdwtZ752wvfQ8AGTw37+DDemrsBd/3HbmuQYqlMlIy 95oz6YOA82vajYxXEpWT31dZJvGvuNWermFaBarJO+0wvX9qee+rXx3uYgy2gHKuXwXQ0UgxK jkHpNi1lwCIcSqfQUbi4wmtHd3mPLNMoPf+/+JybovZ12deCxnMOtvjfEme/tYgCSMBEwPV6q KpwBvEWhR/s7hRajeunz1Wwg/Jn+6WItifyhiBziTOUbq8H8e6VgibunU6se0NsWhPWX5KW1t XAgPgzxAtloFATjdUgX7u3k2SNS0R1ndZLUB3naDsV81+tj3z4PCIe3aY7G9DMkXhx5bWbTsH mjPtPFt+gRqUbqHeMn7IyfTY0+QDkthZS/3c3m5dIf2JiWE9aAdAYnVegGGEO6ptEr+m60n01 etcw5HYsi9q2wC61I5RFYrg5m/90SOlGiFv Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The sort subcommand of test-mergesort is used to test the performance of sorting linked lists. It reads lines from stdin, sorts them and prints the result to stdout. Two heap allocations are done per line: One for the linked list item and one for the actual line string. That imposes a significant amount of allocation overhead. Reduce it by doing the same as the sort subcommand of test-string-list, namely to read the whole input file into a single buffer and then split it in-place. Note that t/perf/run can't be used directly to compare two versions of test-mergesort because it always runs the helpers from the checked-out version. So I hand-merged the results of separate runs before and with this patch: macOS 12.5.1 on M1: 0071.12: DEFINE_LIST_SORT unsorted 0.23(0.20+0.01) 0.22(0.20+0.01) 0071.14: DEFINE_LIST_SORT sorted 0.12(0.10+0.01) 0.10(0.08+0.01) 0071.16: DEFINE_LIST_SORT reversed 0.12(0.10+0.01) 0.10(0.08+0.01) Git SDK 64-bit on Windows 11 21H2 on Ryzen 7 5800H: 0071.12: DEFINE_LIST_SORT unsorted 0.71(0.00+0.03) 0.54(0.00+0.06) 0071.14: DEFINE_LIST_SORT sorted 0.42(0.00+0.04) 0.21(0.03+0.03) 0071.16: DEFINE_LIST_SORT reversed 0.42(0.06+0.01) 0.21(0.01+0.04) Debian bullseye on WSL2 on the same system: 0071.12: DEFINE_LIST_SORT unsorted 0.41(0.39+0.02) 0.29(0.27+0.01) 0071.14: DEFINE_LIST_SORT sorted 0.11(0.08+0.02) 0.07(0.06+0.01) 0071.16: DEFINE_LIST_SORT reversed 0.11(0.08+0.02) 0.07(0.04+0.03) Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 38 +++++++++++++++++++++++++------------- 1 file changed, 25 insertions(+), 13 deletions(-) -- 2.30.2 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 202e54a7ff..540537224f 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -22,21 +22,33 @@ static int compare_strings(const struct line *x, const struct line *y) static int sort_stdin(void) { - struct line *line, *p = NULL, *lines = NULL; + struct line *lines; + struct line **tail = &lines; struct strbuf sb = STRBUF_INIT; - - while (!strbuf_getline(&sb, stdin)) { - line = xmalloc(sizeof(struct line)); - line->text = strbuf_detach(&sb, NULL); - if (p) { - line->next = p->next; - p->next = line; - } else { - line->next = NULL; - lines = line; - } - p = line; + char *p; + + strbuf_read(&sb, 0, 0); + + /* + * Split by newline, but don't create an item + * for the empty string after the last separator. + */ + if (sb.len && sb.buf[sb.len - 1] == '\n') + strbuf_setlen(&sb, sb.len - 1); + + p = sb.buf; + for (;;) { + char *eol = strchr(p, '\n'); + struct line *line = xmalloc(sizeof(*line)); + line->text = p; + *tail = line; + tail = &line->next; + if (!eol) + break; + *eol = '\0'; + p = eol + 1; } + *tail = NULL; sort_lines(&lines, compare_strings); From patchwork Sun Aug 28 10:34:47 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 12957229 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8F3B0C0502C for ; Sun, 28 Aug 2022 10:34:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229560AbiH1Key (ORCPT ); Sun, 28 Aug 2022 06:34:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42276 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229519AbiH1Kex (ORCPT ); Sun, 28 Aug 2022 06:34:53 -0400 Received: from mout.web.de (mout.web.de [217.72.192.78]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E97D5656E for ; Sun, 28 Aug 2022 03:34:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1661682887; bh=qpxW7aS6wf77uSKbHspfa8X9tlVbuQ5SVlZP2BWE5jk=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=P7bschu95JEXyyXloYIN/cDClWU96SuVp2tMAQKvL3pA7pwmrOOrwtH2CyKMpOZH0 Y4Y9RBImqVp7x4ngoamwqceDdHwJP1pYY6MwVUP1z9H4oqv8YLpxWDwFLqxK7Cm6c9 vAHORc+C2l3YAxpmFFLDLbP8ycBCPiYeRp8vzn60= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.35] ([79.203.21.84]) by smtp.web.de (mrweb106 [213.165.67.124]) with ESMTPSA (Nemesis) id 1Mvbn2-1pJfBx2HEk-00sRwS; Sun, 28 Aug 2022 12:34:47 +0200 Message-ID: Date: Sun, 28 Aug 2022 12:34:47 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.2.0 Subject: [PATCH 2/2] test-mergesort: use mem_pool for sort input From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: git@vger.kernel.org Cc: Junio C Hamano References: <128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de> In-Reply-To: <128f0fb8-d29b-8622-0cfe-2ecadc999db5@web.de> X-Provags-ID: V03:K1:4BNmBkIiw2SfuJcKVPmHkFuHJOUDBNVgJ/G9Sex/RqfrUrp4MXr xFNOTkHas0BtLrRnpEAp3vgHgGtH7gpUofLQo3O/4UQjN996MEtEPwOAyetHo4yU7dM/Mmz 7be0hKGvArPxfylHyKcrMzKTm9RDVKwHAKMYG2PC6C2NQDIYbgM4LJPrF+JlvIuqCViQjiE uAiO9uFcqp4SyKA/z8OAQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:cScU/rWQ+Ac=:xtEvPnzWlsQ8IWzMjE4/hY tyjWi2pi2zd4tAs33/GopMZfYdVqFk7eWco2qXYY7al0UyO4qRUGKUwcncDPwRQCTXV/Ke3xg mdSyVSySZnmUtmiO6Mrn1rvwsXjZfrNqyWdbR2gFNdjZSzjlO+oGCKcjjh/N4BfonzrKxmVjS ylkkhtJ7gWYpPqJEzyxG3f4eD9feCuRXqGtFDLJ2fVyMme3Or4FXt1Wl5adahGJbVk00H/ZYk /sPNpf72FQnEotJ3qXshqzIBD++lYyKA+KPTRqh1aJh6c/GrMye39pXGfSz5rtDAG+sD0xcYP IDMLyi7D3Z1BWZUIAbxiDWb9S9n30dRlxarTrQUXaZ4qldnwYan++BJFIDEhM96Tzzu3LicP2 8I74RaPezzDHm/5+NYN7WVGGM+ZobwDL2KqLQs/0EmX2jwqFwfELJKMHG5TQxfh10G1rSirCT NFTSl6X7uTAbg1nx/Fw2rrpvi0lTYvFqC42ZmGep6oI0E0MJqbbPdaxlVNIUzOF8bq2rX4XL6 wNjkPGb6pxPifUE6IQ2ganii4nNMKmZAFB8tH5fn5OOE6xkvgXgoqobp2dYNddploVtcDCRRG aX6v4vLJcc5YHlYbdDqBXMmG1LltT5QslAkDhh/W9PuUg2wZ074v5/jYsqzU40xMzhYW4x71J p/9HWJ+VqYO0bJ4mwaBcEXV1K4SEru/J61l5LpcYRG95bPwEMZJZ5AaIC+nE29AteL9vLpYeP kECR9LjBDxaG5ChPm45p9YRBxTVk8wBo5+aXmdDgehQ1L8wl3zGSKJauu0rAV/VQLo58Q15tQ 99NwQW4UiJ6hHO7E97g/VS+zXIX60yqO6ml2O/Gv18s13DEO6va3z7LV3JsSytFF6iovPhcAb W1UYzVfTAPD06oKEHjaSEUOit0VpInd1zRy61kr1g/mDPx+Dp/Y2KxvnziewDn4dA1AdXJbv2 uRpZ6BvdPhyEqcRGtxzqL+ItKEG2Pum7JqxwChVQU5urt+DOoVsbdE0W+0FZCht997iXsAzXR LIaascWAYIdTf0B4v8BogkoA+8cD7uCDWa9lByCL8rDgVE0hfd8UgCMwJXKVFy8llvKKysX+N 4WH6eKKBPIM1d5h7TqaZTSJpl/g9yegJ1xM Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The previous patch almost halved the number of heap allocations for the sort subcommand. Reduce it further by using a mem_pool for the line objects. Note that t/perf/run can't be used directly to compare two versions of test-mergesort because it always runs the helpers from the checked-out version. So I hand-merged the results of separate runs before and with this patch: macOS 12.5.1 on M1: 0071.12: DEFINE_LIST_SORT unsorted 0.22(0.20+0.01) 0.21(0.19+0.01) 0071.14: DEFINE_LIST_SORT sorted 0.10(0.08+0.01) 0.10(0.08+0.01) 0071.16: DEFINE_LIST_SORT reversed 0.10(0.08+0.01) 0.10(0.08+0.01) Git SDK 64-bit on Windows 11 21H2 on Ryzen 7 5800H: 0071.12: DEFINE_LIST_SORT unsorted 0.54(0.00+0.06) 0.44(0.01+0.06) 0071.14: DEFINE_LIST_SORT sorted 0.21(0.03+0.03) 0.19(0.04+0.01) 0071.16: DEFINE_LIST_SORT reversed 0.21(0.01+0.04) 0.19(0.04+0.04) Debian bullseye on WSL2 on the same system: 0071.12: DEFINE_LIST_SORT unsorted 0.29(0.27+0.01) 0.22(0.19+0.02) 0071.14: DEFINE_LIST_SORT sorted 0.07(0.06+0.01) 0.06(0.04+0.02) 0071.16: DEFINE_LIST_SORT reversed 0.07(0.04+0.03) 0.06(0.04+0.02) Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) -- 2.30.2 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 540537224f..335e5bb3a9 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -25,6 +25,7 @@ static int sort_stdin(void) struct line *lines; struct line **tail = &lines; struct strbuf sb = STRBUF_INIT; + struct mem_pool lines_pool; char *p; strbuf_read(&sb, 0, 0); @@ -36,10 +37,11 @@ static int sort_stdin(void) if (sb.len && sb.buf[sb.len - 1] == '\n') strbuf_setlen(&sb, sb.len - 1); + mem_pool_init(&lines_pool, 0); p = sb.buf; for (;;) { char *eol = strchr(p, '\n'); - struct line *line = xmalloc(sizeof(*line)); + struct line *line = mem_pool_alloc(&lines_pool, sizeof(*line)); line->text = p; *tail = line; tail = &line->next;