From patchwork Fri Oct 1 09:10:09 2021 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: 12529897 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0B9F4C433EF for ; Fri, 1 Oct 2021 09:10:25 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DADC961A51 for ; Fri, 1 Oct 2021 09:10:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229874AbhJAJME (ORCPT ); Fri, 1 Oct 2021 05:12:04 -0400 Received: from mout.web.de ([212.227.17.12]:49643 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229702AbhJAJL7 (ORCPT ); Fri, 1 Oct 2021 05:11:59 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079410; bh=0JPtoY5xDq3tgkgxexgL/nQg9/XjMjc+CvhgAi0iljI=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=ZknzkCPbizIZbCwQUVrwq084dcANEc+ae6i29FWYYuzFm/Jf+auIp+RXbRD/h9e1z 15keBp3iDgeqek1V0zcDOnPASUgwC5MXE9LAQT4yyMCZ4T+joxM/38sLtXqK11A+HD nNeZAuBqUE3YyeQhAu/Tsm2q46pMYYL0xCwqrPVc= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb103 [213.165.67.124]) with ESMTPSA (Nemesis) id 0LyDlZ-1mrDwF1sft-015c5d; Fri, 01 Oct 2021 11:10:10 +0200 Subject: [PATCH 1/9] test-mergesort: use strbuf_getline() From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <928cb42c-c45b-c90a-c71b-2f6669e03251@web.de> Date: Fri, 1 Oct 2021 11:10:09 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:obHIWkUGR86Ec+d7uVtTCydtwTQwoRF7rQjmLL0jcJfGSvIUftY rws3NUrj7WRMAKop+YBZikeOmozpFnehEFiquWIYYJTcs/9mEpDJ0NAy7ea8OjOZOyPGK0l TkSfBFZzbuSP+SykKwZEu+hu6/dVcOU4KwMJ5Ef2H+F1yaFZYGgDJPIRWonZb5cR15gKgOC yoJZmY1GjmFC7Y4unYUjQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:uN/nnY+5Vyw=:Lltu63VQi6mcMm4xIXN7Yv RfbWiKG5iV2JTLg5bMUtH/0BjgAm/SenYdouxNJ3G3YzZJyP34N9BjuCjCFgy+zJkA7SJRlf5 nKCW0HVjR7+46rrRWon50KsmWy6J3j6ddtGLyjpg90mgy9yYHSJ9qelTKOERT3Wvn0QJ3wg8T EfbqX9K2BVVldEeAKfKGJBq+tSz5Z9ad//s0Mw0AgQOCotH2ZbSKgnn+D32PvBI2szBqyZR7a ByNaZrfTgRJxjkjaP7WZnuMAvRGtM1/SApIXxsdQtbhGu6yl0zpYdzKaFpmEtuPkxfwAHEPCS 9INIHgYCuwbPhCXRCdKFNazfDVoaXZk2MiV6F1G6qBAhHybbOUQWPbdE/lXhuJOeJ2wgkNEor w+EnEWW4G98RGqHFI6dcT2V+eMlOrbovI1CaJEd5OQ072HcDQxW/dLObDu/VvSokJDtwZ/4HX cIIDM0qjpMWLaktXK2Q2lfoCj6uabw2cNR6jEZ6sLzIIePKpbsveoTFgvBzMiOlZGOgSQaqac ItEvzpkLd9KgPd4xki7hWssN1tl6GDUCERkA5/70rUIgTegW4RuOvi0z+3cHxS0FwiqnL+KKl howVlq8C4ZqT4zaM4YLHtLXZf2jWQjzu4+xBQkQ+ovS1XV39l7lrNrpsu91lCQFDKPJf53+Jb i53gfEVW0SlmpCJKqn2jq3FrzUHzsrOB8CyODxDyR5Zg4URV9vbFtBmGnsTr29sLEdGQ7XyhU vkHayZhIBxjz4OxUu+E2b7ebcRc8QPHlvgZ6RDCZBntRpC9WFpCtT5JWpzwcpB3YlLJI7jmuH S7aUA7aCGYMenimWUND1jT9r7L4BIoNKZIWjeaQ4qfb3hKldANHX5eNXsqiy5oxV6RPTBv7ou GllEIwL1vl2FlC76QlYPwkHHgIJ5lrk58pPVtytZdMY4dDUORBIKy750DbiuqtqZ2JwE2/w6O E9MUjeYCkMe0+FmYHeYAaPofqmGcUZXDNBDsTbpr1gOHXlK3sZjoJY7mMbLk4S5nGDXFUpPLW z+Xvmn9qCJTCsXCVh1OyJ6r2TkO7hVcF9X8YBpy3WpEcpklrtEwxdMSrjWGmME8POw== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Strip line ending characters to make sure empty lines are sorted like sort(1) does. Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index c5cffaa4b7..621e2a5197 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -28,9 +28,7 @@ int cmd__mergesort(int argc, const char **argv) struct line *line, *p = NULL, *lines = NULL; struct strbuf sb = STRBUF_INIT; - for (;;) { - if (strbuf_getwholeline(&sb, stdin, '\n')) - break; + while (!strbuf_getline(&sb, stdin)) { line = xmalloc(sizeof(struct line)); line->text = strbuf_detach(&sb, NULL); if (p) { @@ -46,7 +44,7 @@ int cmd__mergesort(int argc, const char **argv) lines = llist_mergesort(lines, get_next, set_next, compare_strings); while (lines) { - printf("%s", lines->text); + puts(lines->text); lines = lines->next; } return 0; From patchwork Fri Oct 1 09:11:19 2021 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: 12529899 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C3398C433EF for ; Fri, 1 Oct 2021 09:11:24 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9EB5D61A84 for ; Fri, 1 Oct 2021 09:11:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230071AbhJAJNH (ORCPT ); Fri, 1 Oct 2021 05:13:07 -0400 Received: from mout.web.de ([212.227.17.12]:40023 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229702AbhJAJNH (ORCPT ); Fri, 1 Oct 2021 05:13:07 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079480; bh=LcOPzV+0bnAqp2HCpIIetJESiKvwf1IAj32T8E2f6Eo=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=Gyop/eGW6JoL/kU0oxgmf1N+52loq9GTBrcP0hBL7n5yPBFvaQzUgvOcAYKASsiIb H56lckFd+ez+VJchkfrapz//F1cEGDtKphAmJzMFm5Zqwz7YJy1IATSeCC7hGoxEft gmiSTv3no3ICAW92q4HyX9lSJ7WIig2q/C7BXcYc= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb101 [213.165.67.124]) with ESMTPSA (Nemesis) id 0Lmu2K-1n1zPw2lzg-00h6ts; Fri, 01 Oct 2021 11:11:20 +0200 Subject: [PATCH 2/9] test-mergesort: add sort subcommand From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: Date: Fri, 1 Oct 2021 11:11:19 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:UCS2Njyu/GnEbjoh/Xb+YD0IdjZV/V+9iHZnBI8MJgY8/dAtUum 5Dji5TrzeOq+MQKnHmnL/73oDFHLUB7Y+LdZ84Ix0dFwrNv0qFOXKXmaFKimbx8zZsBzTxU abQJcBpq5XIUrXI+nxUlCvAEP0YiZkWkBhe4LyuZb/g88cCtkcFI+pH/VxBK4R6YEwPmLmw 8kesLZo2Ydvob3qRC5Aag== X-UI-Out-Filterresults: notjunk:1;V03:K0:SYzfaI6Zm1E=:P/FIBBr60jhIpLibgqEZ/p +zmTThWS+zRAvuCLU1Ztn+aahSEZrKbIHrZMHqMQ0BuDTkO8iwsA+Vs72Na/kbJd4U0MHG/nR 2wK/E/Kd4zdsWPZxF+ZfbUl48jFbxTKPuyt3gwmxS8xu2olhnIGHWnYtbbO0m3B6wgp95P41I nPGDVa/PWn6QB3t0bslb8IS9PTpMYraaUrpLnLHnXTtqHQ25vM8Lv1PrAJg65/ShEZuJa7UWe zTAm6mvkoHlFWzabiSdBm8BfwZI+Aj5o98dCEXscs8Z72/DlW72pbaPwsBgv7o7ypx3FHnuim O/FA3duVfk+/9g5zALW8vEcWQ8u2OHsHB4+nBlLxBYdBnyZshp+5lP/7zN+9qOqPJdsHvzphi RxRggvLd/qwtp42Fl0ypA6BiroUMWt/H+Qn4lIATnBeXGmcaEKWl1YcKhDpmCqIPIvUr7Feqb eriJoNHRVAocL+y1M5sTe5b5Tt1PwbGUyuBX6gcLnIZb7+E3dscz8le33dbN6K46466rtujK3 l00tLdF1Ueal6V2c8S9Hid/RgDwXftY90Y+R5ivTFUKsgnXl+Y6cDRU9UX2gOMr2Xs86fM4kQ iooqd8SrCaecxI+pqRqSRBWGRNYgNDG26C7HpnGvJVc/jZbfaitplKSzy3Mb9dWMqCmXU2EEa WogIPr1HA5jMRUP/zj3YwsOHcgTWHmQKNmFUiSIY+hy+lG2gjt9z4cg2qrWt6dOMVTVX+8G/7 id5I6R7+zKy4VH1XHNTPDb4jBdsG+ou+jWgp7y1oQ+XEcGnwMCXJtBJB4zw2x99+oPPlDAwbw 19hKOjTyG4h8olaxXFJpRhtZ2lj0k5GJaEI68r+Uwm6jfQmiRqksQfVbv9mSNUvBxBsXhtOUP jGOuZ2zfl/ZKB0Cw87M3rXlW6pIni33+STNdB383jSXc+0HSGBOCxu3s/irGjKYyWVwOhl1lA VOWMrerynAbOgj9+/jVvjYRfEVhrAGTWMvNwvAiD5LIE9UuJEQ3WhkXMoEnoTUGgiCWclSKsU qq1n4HXf6OckDUXuNBrtRa9vFKv12vCIaskCOJ0zUFKVMkBBdbk+8Y/FnZyymFQV+Q== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Give the code for sorting a text file its own sub-command. This allows extending the helper, which we'll do in the following patches. Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 621e2a5197..05be0d067a 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -23,7 +23,7 @@ static int compare_strings(const void *a, const void *b) return strcmp(x->text, y->text); } -int cmd__mergesort(int argc, const char **argv) +static int sort_stdin(void) { struct line *line, *p = NULL, *lines = NULL; struct strbuf sb = STRBUF_INIT; @@ -49,3 +49,10 @@ int cmd__mergesort(int argc, const char **argv) } return 0; } + +int cmd__mergesort(int argc, const char **argv) +{ + if (argc == 2 && !strcmp(argv[1], "sort")) + return sort_stdin(); + usage("test-tool mergesort sort"); +} From patchwork Fri Oct 1 09:12:27 2021 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: 12529901 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 26236C433EF for ; Fri, 1 Oct 2021 09:12:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 06F486187D for ; Fri, 1 Oct 2021 09:12:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230143AbhJAJOP (ORCPT ); Fri, 1 Oct 2021 05:14:15 -0400 Received: from mout.web.de ([212.227.17.12]:52595 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229681AbhJAJOO (ORCPT ); Fri, 1 Oct 2021 05:14:14 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079547; bh=/zSY045fpew0AbDo5E1kzYjESun88SFZ4WyIRpG4bWU=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=rQLbfLZybPrSfN3DgNkbMontLzubZJ8femmI4JgG1ywl9lPhG7JQXTgLREi1aIJU2 EPfNWhumN8xLjss5N0uzhELE6fUvCAkPrX1FhfTu4V3iIkAfa5e9NbfoWzbsDB1EmU brKHQnRSTk7pK4uuaPlVkuQeEnNDnXC0BA4VHDWI= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb105 [213.165.67.124]) with ESMTPSA (Nemesis) id 1MAcpW-1mhHCV1qky-00BXzM; Fri, 01 Oct 2021 11:12:27 +0200 Subject: [PATCH 3/9] test-mergesort: add test subcommand From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <522fba5e-1048-3377-45c1-7107b55dc6e1@web.de> Date: Fri, 1 Oct 2021 11:12:27 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:fRqUU5KeRNGV/mN1SYWp1nZOVfXJfUwssTeej/T6xkP+8/at3Cw RZGmorVfYTwKlS0kIHYzr9jtcys5lanKo00g1ydgk/jACeh1W9g2f+hpmpbTEUplFuLN8xn urvNP0bqDrZqz6UKTVd/s4ZlmbVfvnyY2TkkRpcaviAf4ceQjSGEED/vLt7KUKXxv30Tz2i BXlD12WrlDAB224ogdwRA== X-UI-Out-Filterresults: notjunk:1;V03:K0:iEX3uASVwBU=:Dk0arxILaBqfa9D2SxijnI ljzG1fBNqTRn4cgtx8chCF8U5IzCmKd+xDjUpUUCx6fU0kxQ6VamGNGv71vnBLEfcwonDdmgB s2Eaa6xAzOvvyR5CV4Hm8ub9mTKBiPkVd2opPv2w6hd1rllvakYds8nA8wZFKR7r80XiFyd9I 86BzQlgNUTbkKROawLs4DD8urer9nClmRigJhWAqFn5IXJ8TPeXixO9cxV8t55T+katNahXN9 fK2VcTseaJ119oZYYyAG/wsgFMAxfkdEVrjo/XOEt6xQ3hi+TneR715paWoiOQtiZUcd3vlFS SVsuMd7gO8KJiuLL2QmsGh/Imh34KHmWbNaZZ1h6/MFafM6F5mj90T8iVBdC1O3kCIUuttit9 Gl1txuMWLcSu0QWM4R4CEkKCtzMGPp9qlZgaWqDf7ezH1Y2FRCVhRnHLaqUrhOzRvUb3xSnYt Co9a59wLwS+RKP+/Lc9dP/EI3B5JmnBLrPjWLFY1R/xYoJhTikv6gpJHDsfLB7cXnn1Y0DUBI zHtxEzVgN26C1O/Tfkw7rFBsScscI7XTWBhpKPMonL/swTQbBQwFdGyQLCpnsAYcJAtuOVxmA p4Ejk792keR8lbyLty7CBpzDrjxyJR3BPLMmUH3OxR3Iu4OpUeVp0Mcm1qQCbDwthXfs4kZ8i cM7W8j9ehtsZPNu9dooC3XwmK8AFI82BF5xYP8v/t9neS8MfSQ09HfqDtHZ5yyFzTn/qA7cLT dp/yXS8HozqkWgWQDmkoBbMNiLM+W6zuYudkXH3MGUe7ynldV3aU5ZNs3LjU2HggutRp6cxrQ xTthisKg/Dt/JP6lJ6mb1OMr/vq82fykGL1NS6Y/oAkm00MbGgGKDrZJcHXBL+jpIsSDH1Mqz v7Vg5wYIJR/mddJXhBe/6mbd0pzRQaBovErVc4ll4LEdJyx9BEFoSrOlxm47LIIYgofUZyukz rdaxvXEFV3YGVRVClvOGTJ5gW2H9AgAX6iGnJca7L+S05QSyZsU0bQqXosdHOBmvSe+9iZg3S 7UrjdBJa1rtwkTB4OvYKU0zpi+WII9sH57ZLwnUKN9OTl8bSoqkJP0OcsO5zGNYPTg== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Adapt the qsort certification program from "Engineering a Sort Function" by Bentley and McIlroy for testing our linked list sort function. It generates several lists with various distribution patterns and counts the number of operations llist_mergesort() needs to order them. It compares the result to the output of a trusted sort function (qsort(1)) and also checks if the sort is stable. Also add a test script that makes use of the new subcommand. Signed-off-by: René Scharfe Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 232 +++++++++++++++++++++++++++++++++++++- t/t0071-sort.sh | 11 ++ 2 files changed, 242 insertions(+), 1 deletion(-) create mode 100755 t/t0071-sort.sh -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 05be0d067a..8006be8bf8 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -50,9 +50,239 @@ static int sort_stdin(void) return 0; } +static void dist_sawtooth(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = i % m; +} + +static void dist_rand(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = rand() % m; +} + +static void dist_stagger(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = (i * m + i) % n; +} + +static void dist_plateau(int *arr, int n, int m) +{ + int i; + for (i = 0; i < n; i++) + arr[i] = (i < m) ? i : m; +} + +static void dist_shuffle(int *arr, int n, int m) +{ + int i, j, k; + for (i = j = 0, k = 1; i < n; i++) + arr[i] = (rand() % m) ? (j += 2) : (k += 2); +} + +#define DIST(name) { #name, dist_##name } + +static struct dist { + const char *name; + void (*fn)(int *arr, int n, int m); +} dist[] = { + DIST(sawtooth), + DIST(rand), + DIST(stagger), + DIST(plateau), + DIST(shuffle), +}; + +static void mode_copy(int *arr, int n) +{ + /* nothing */ +} + +static void mode_reverse(int *arr, int n) +{ + int i, j; + for (i = 0, j = n - 1; i < j; i++, j--) + SWAP(arr[i], arr[j]); +} + +static void mode_reverse_1st_half(int *arr, int n) +{ + mode_reverse(arr, n / 2); +} + +static void mode_reverse_2nd_half(int *arr, int n) +{ + int half = n / 2; + mode_reverse(arr + half, n - half); +} + +static int compare_ints(const void *av, const void *bv) +{ + const int *ap = av, *bp = bv; + int a = *ap, b = *bp; + return (a > b) - (a < b); +} + +static void mode_sort(int *arr, int n) +{ + QSORT(arr, n, compare_ints); +} + +static void mode_dither(int *arr, int n) +{ + int i; + for (i = 0; i < n; i++) + arr[i] += i % 5; +} + +#define MODE(name) { #name, mode_##name } + +static struct mode { + const char *name; + void (*fn)(int *arr, int n); +} mode[] = { + MODE(copy), + MODE(reverse), + MODE(reverse_1st_half), + MODE(reverse_2nd_half), + MODE(sort), + MODE(dither), +}; + +static struct stats { + int get_next, set_next, compare; +} stats; + +struct number { + int value, rank; + struct number *next; +}; + +static void *get_next_number(const void *a) +{ + stats.get_next++; + return ((const struct number *)a)->next; +} + +static void set_next_number(void *a, void *b) +{ + stats.set_next++; + ((struct number *)a)->next = b; +} + +static int compare_numbers(const void *av, const void *bv) +{ + const struct number *an = av, *bn = bv; + int a = an->value, b = bn->value; + stats.compare++; + return (a > b) - (a < b); +} + +static void clear_numbers(struct number *list) +{ + while (list) { + struct number *next = list->next; + free(list); + list = next; + } +} + +static int test(const struct dist *dist, const struct mode *mode, int n, int m) +{ + int *arr; + size_t i; + struct number *curr, *list, **tail; + int is_sorted = 1; + int is_stable = 1; + const char *verdict; + int result = -1; + + ALLOC_ARRAY(arr, n); + dist->fn(arr, n, m); + mode->fn(arr, n); + for (i = 0, tail = &list; i < n; i++) { + curr = xmalloc(sizeof(*curr)); + curr->value = arr[i]; + curr->rank = i; + *tail = curr; + tail = &curr->next; + } + *tail = NULL; + + stats.get_next = stats.set_next = stats.compare = 0; + list = llist_mergesort(list, get_next_number, set_next_number, + compare_numbers); + + QSORT(arr, n, compare_ints); + for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) { + if (arr[i] != curr->value) + is_sorted = 0; + if (curr->next && curr->value == curr->next->value && + curr->rank >= curr->next->rank) + is_stable = 0; + } + if (i < n) { + verdict = "too short"; + } else if (curr) { + verdict = "too long"; + } else if (!is_sorted) { + verdict = "not sorted"; + } else if (!is_stable) { + verdict = "unstable"; + } else { + verdict = "OK"; + result = 0; + } + + printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n", + dist->name, mode->name, n, m, stats.get_next, stats.set_next, + stats.compare, verdict); + + clear_numbers(list); + free(arr); + + return result; +} + +/* + * A version of the qsort certification program from "Engineering a Sort + * Function" by Bentley and McIlroy, Software—Practice and Experience, + * Volume 23, Issue 11, 1249–1265 (November 1993). + */ +static int run_tests(int argc, const char **argv) +{ + const char *argv_default[] = { "100", "1023", "1024", "1025" }; + if (!argc) + return run_tests(ARRAY_SIZE(argv_default), argv_default); + printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n", + "distribut", "mode", "n", "m", "get_next", "set_next", + "compare", "verdict"); + while (argc--) { + int i, j, m, n = strtol(*argv++, NULL, 10); + for (i = 0; i < ARRAY_SIZE(dist); i++) { + for (j = 0; j < ARRAY_SIZE(mode); j++) { + for (m = 1; m < 2 * n; m *= 2) { + if (test(&dist[i], &mode[j], n, m)) + return 1; + } + } + } + } + return 0; +} + int cmd__mergesort(int argc, const char **argv) { if (argc == 2 && !strcmp(argv[1], "sort")) return sort_stdin(); - usage("test-tool mergesort sort"); + if (argc > 1 && !strcmp(argv[1], "test")) + return run_tests(argc - 2, argv + 2); + fprintf(stderr, "usage: test-tool mergesort sort\n"); + fprintf(stderr, " or: test-tool mergesort test [...]\n"); + return 129; } diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh new file mode 100755 index 0000000000..a8ab174879 --- /dev/null +++ b/t/t0071-sort.sh @@ -0,0 +1,11 @@ +#!/bin/sh + +test_description='verify sort functions' + +. ./test-lib.sh + +test_expect_success 'llist_mergesort()' ' + test-tool mergesort test +' + +test_done From patchwork Fri Oct 1 09:14:32 2021 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: 12529903 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 775FBC433F5 for ; Fri, 1 Oct 2021 09:14:38 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5DAFF61A87 for ; Fri, 1 Oct 2021 09:14:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231240AbhJAJQV (ORCPT ); Fri, 1 Oct 2021 05:16:21 -0400 Received: from mout.web.de ([217.72.192.78]:33021 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229702AbhJAJQU (ORCPT ); Fri, 1 Oct 2021 05:16:20 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079673; bh=DZbCBUzsyeR0mESMjMiRa98oSh/aD68k+7vaFNNwk4Y=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=CalJP1WrrqNipitVYaToVB2iX2kTPsGZibx6bkSAr7Y/WMleOJRiQ6hjoJCyfMgII pjxXKncIAld+f/2FkPBTnL5RcmjYonDpXBNW5xxGCOrDgJCHm2mOHP39gWLNQIoa8s VUovfncHZwDc/Qj+DprZZ70YrxO76Th3r0OaciPY= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb103 [213.165.67.124]) with ESMTPSA (Nemesis) id 0Lal6K-1nGL0D1ItM-00kOxI; Fri, 01 Oct 2021 11:14:33 +0200 Subject: [PATCH 4/9] test-mergesort: add generate subcommand From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <1b6e34fc-b758-f6e7-39b2-e73f309591bd@web.de> Date: Fri, 1 Oct 2021 11:14:32 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:6opvJZ7N4fLOUg5g7iKzlIklxVNKVn0LvNAzhZY+Tg7kZr9aCiw HZ1S6e2K59XvErXsxHu7vrCcoNtgaAFH0GgPxi4Dtsl6w87r7EwhVx8BQGEVyVVjVhA10EV CXVCQMzH7OQKe0lnxxDx8f5MDBsqWW+I9FfZuFhfVR4dWV/T7QU1dtuJkNLd5iVkC0tiYLh sVYmTt1hDj4qYt8gqU2fw== X-UI-Out-Filterresults: notjunk:1;V03:K0:YvmNxUYI5W0=:zVb9wwgs664SLYCtLAAPqP WZ/4/VPqBgHl01xu2Klp3AS6qO7Zp8hMFs7hPtNakfDhSlPeMjpxCfpWeVQhyzZ22JeZlvBVn TlRjuwaAOAVNI3fF9PjiI5wl7rdf+Zep+AwRChmH/cvBmLCZvmmA4GSL0Qd+4OedVM1zuRINm a+qJC8YgYzXrgrxojycU9yN9mAe2zZMTgijwBFIYIi8bSE2AknIa85eFgkWjbEkMV+smC/fw1 N5eNkKxyoV9gmcJDWa/UKjOLWp7jwY1ipwjPzMrUFmX6Hkm+pPXabVD7xHMjnESjESU/I+/wm mMy5Ux/wbnQF9sNP17+I+P2K5PrU7PyyBL6ZQmy2IyC9DqQtPzxIu81ezJE4Sfkel24hxwLYW yuk1NteiYY+xYeqhMHxv2qkfTTVzxD5UIj2ExGfi+mIFuj4dUyFkfYoXXSOJDJlNhEhl1Xxae 33IEVnisbquZ8op+3oEJICnkKIitE1mdyaNRwPvQrucgztM44G1nm6KZ1p4M1xpdvC8o2ePsL OYXd09uDN0YPV/b9DooxpELetv7YdBdk0S1HvVo97N9LRs24QbpxplW/Mcctj8zDuPTUFqgId 31356qy/w5XKdioNpQcYo/EMC72bxd36raAhyPKEH1NsAHds17xmw3d+YyEongODeDk/QLM6r jVe7xKeOS8ggiR7i2l7L+2A28OoABsAy05Q7o0nhOyxmQkLqMDQO4es8/RclgyoEcEAWBzzLa fY2CVuAx8nVGIXfhSbFWcmX/j8cJJ60wYQ0uJOz8Zc/42boSoQPFH4v05S0MHcBWlLthNgKXx 959CiSO0ZSQASYwBBep0gXxCOzQSGTRnEgB4VjE0EfW131gjvMC47uuBsED6frZ20QyMtTVkH 3z4+bZdyQ5GLhJiyfNTYihOI19W3KNVnA6nl2QBnNFTGtJS7U99yO3KfstaAMvFGN4u2wAHwX 42sk4rDLFQQ/opJAH+9Be1TqwMfw80zBsgixPz7c8w5aXyi76aD8mlVSy6HhPSW1pxyo1uuyM GiZVFSzums78rBXfGKPF/qdP75OirCVwjl0h0Zoauu+RCKvGKxoKFr3QpcqsJnsr51fCkldue bA6IHzH9l1A7gA= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Add a subcommand for printing test data. It can be used to generate special test cases and feed them into the sort subcommand or sort(1) for performance measurements. It may also be useful to illustrate the effect of distributions, modes and their parameters. It generates n integers with the specified distribution and its distribution-specific parameter m. E.g. m is the maximum value for the plateau distribution and the length and height of individual teeth of the sawtooth distribution. The generated values are printed as zero-padded eight-digit hexadecimal numbers to make sure alphabetic and numeric order are the same. Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 60 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 59 insertions(+), 1 deletion(-) -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 8006be8bf8..27ba252d4a 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -98,6 +98,16 @@ static struct dist { DIST(shuffle), }; +static const struct dist *get_dist_by_name(const char *name) +{ + int i; + for (i = 0; i < ARRAY_SIZE(dist); i++) { + if (!strcmp(dist[i].name, name)) + return &dist[i]; + } + return NULL; +} + static void mode_copy(int *arr, int n) { /* nothing */ @@ -154,6 +164,41 @@ static struct mode { MODE(dither), }; +static const struct mode *get_mode_by_name(const char *name) +{ + int i; + for (i = 0; i < ARRAY_SIZE(mode); i++) { + if (!strcmp(mode[i].name, name)) + return &mode[i]; + } + return NULL; +} + +static int generate(int argc, const char **argv) +{ + const struct dist *dist = NULL; + const struct mode *mode = NULL; + int i, n, m, *arr; + + if (argc != 4) + return 1; + + dist = get_dist_by_name(argv[0]); + mode = get_mode_by_name(argv[1]); + n = strtol(argv[2], NULL, 10); + m = strtol(argv[3], NULL, 10); + if (!dist || !mode) + return 1; + + ALLOC_ARRAY(arr, n); + dist->fn(arr, n, m); + mode->fn(arr, n); + for (i = 0; i < n; i++) + printf("%08x\n", arr[i]); + free(arr); + return 0; +} + static struct stats { int get_next, set_next, compare; } stats; @@ -278,11 +323,24 @@ static int run_tests(int argc, const char **argv) int cmd__mergesort(int argc, const char **argv) { + int i; + const char *sep; + + if (argc == 6 && !strcmp(argv[1], "generate")) + return generate(argc - 2, argv + 2); if (argc == 2 && !strcmp(argv[1], "sort")) return sort_stdin(); if (argc > 1 && !strcmp(argv[1], "test")) return run_tests(argc - 2, argv + 2); - fprintf(stderr, "usage: test-tool mergesort sort\n"); + fprintf(stderr, "usage: test-tool mergesort generate \n"); + fprintf(stderr, " or: test-tool mergesort sort\n"); fprintf(stderr, " or: test-tool mergesort test [...]\n"); + fprintf(stderr, "\n"); + for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ") + fprintf(stderr, "%s%s", sep, dist[i].name); + fprintf(stderr, "\n"); + for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ") + fprintf(stderr, "%s%s", sep, mode[i].name); + fprintf(stderr, "\n"); return 129; } From patchwork Fri Oct 1 09:16:49 2021 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: 12529905 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7707CC433EF for ; Fri, 1 Oct 2021 09:16:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 565A1610C8 for ; Fri, 1 Oct 2021 09:16:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231370AbhJAJSj (ORCPT ); Fri, 1 Oct 2021 05:18:39 -0400 Received: from mout.web.de ([217.72.192.78]:60293 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230000AbhJAJSi (ORCPT ); Fri, 1 Oct 2021 05:18:38 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079810; bh=Ub489NJCdHYRn3myJlbvJbDD+oZboHmWvm7inzCe/fQ=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=L8q1TogSYRcXNp7VAXLo6mnRSNc01RlNAvQ/E0Ewg19H72zT0rwAx4pemdWOet6Nu 9NJKrT6vDqNyIpveperJSxS0F1wGyYlwLPc5fv2FWJVSVagaTp+7hjClxZveh4RK/A 8MQ1xYVdv6PcioMEOxvYzitra46BhZI6kkWnitqc= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb102 [213.165.67.124]) with ESMTPSA (Nemesis) id 0MGzXS-1ma6Hw2F4E-00Dn3j; Fri, 01 Oct 2021 11:16:50 +0200 Subject: [PATCH 5/9] test-mergesort: add unriffle mode From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: Date: Fri, 1 Oct 2021 11:16:49 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:d8AJLR5iau+yiItNsMbCN408COKsWJ55H2u0Yw6ec43+J/yt74J c/oq8rVBhaLJ+ebuL8mYuZX0f28N5Xxup8M0cT1wAYULAAENMy+MoviG/7D0/oL22q/U99Y PctWNKV+IiWYz6ZJjrkGUYVoVLVgSumLwrsTEG2TaTNQxkA3npOOq9WErXxZLQiTRa6+l8a a7H+ZMhZLEHWXJ+KCWUBg== X-UI-Out-Filterresults: notjunk:1;V03:K0:QOpB3DYJFTo=:ZsPJxDtiubsYgCjzhA6e0b lm/mnZOrY6QiSCms4azrtDbZmhuaDaXJyNHndAf55RbplgjFNi+87l4XLbA8fvg2dNIdmlW2o Q1JB2+fvLWFHwMmq2yKt3Pr08NvdWG8kUn4/1U+H9IBCB7dsVJP5kPqKoV/d9wcZ9SNV/IRDj 6DbIm8k0Q9e57kB0Bqun6IU23bwaxNvcJs8NQhYRD3i289Dy0loi32PO2Lt4D/zYS4V/cS2qk J8j6/0s/rWV1NPMwFww/PqgdSeH52wL3HhnEuWGFmsI18I82AVh2xu4OqD9aGTebftFFFJOqD 1CUNno8lWPacoD76nUKjcDbizbbO4ugQ1+Zh8a6a+Oz34UE8sP6OgnaEd78erbC+Tt5u/8aki pE693IiZZQWRXFNFpGSWoKkAE7If+Q/b3/Y5ITsRuGmpro1eMyiC2uBS/A4IJHbUj9FYyYpCe dPYNkq7PLrWWN9zbby5ea6g4b8Fol+pyXUj2o2mwsoAoyAqj6qt0mJg7XfasQk7PrtvEJvQYv Z8/WFkH65emwOuFVih5YO7aMkJjmx4ELF3TKPCJ4dyrQEbUjVrgqmow76//2Ah0bZ9dKYb+KU SdY6l8Wiuxx9zWoEFBLQJ1LM5vHWg7mBzvo/UvnMpfIXOEAnxQuvhB9XHUMV/0vG1cwj5W5uO N733Hb6ob6PrXi7AzsjFsexgO4uvQFq0YKOlUjQjT60VevSUWMfI6/YGnQN8SnTt1wtS2FS8A NH8xuahOOTyVwvXCP/OG0TA4yAgauZmZBn1Z+9xlXOgKWknUwlRZbdkHBnBvMbWtSALw+xwUe vqYS+i+GUllFCEyiAyMhb/G3vWsFBok/zcFbzSUlUttQCX79h2ShKh3FmiFChlbcVAs478/tG gR6WYvS2lBu0Kn2vqD3/AGH94NWqUpJ3BYql3GRCZzq+4zf4poIFzGzRdWYO1Jr4te5K9oP/u U1z2oJWknu2s81KGNxP+UfFRLOQqJAMZLNzfjSQ+2I/Qt2U+y2fIIUevmFQvVB1e9yFglBPNm dOkksUqslN3H8OpUU14JU2CJVtxaev/q5QSBTeLBm0t5iBN+PWE7x9/mK7lUTcNBnSJEkjg9V ovp4RfbEX2LuJM= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Add a mode that turns sorted items into adversarial input for mergesort. Do that by running mergesort in reverse and rearranging the items in such a way that each merge needs the maximum number of operations to undo it. To riffle is a card shuffling technique and involves splitting a deck into two and then to interleave them. A perfect riffle takes one card from each half in turn. That's similar to the most expensive merge, which has to take one item from each sublist in turn, which requires the maximum number of comparisons (n-1). So unriffle does that in reverse, i.e. it generates the first sublist out of the items at even indexes and the second sublist out of the items at odd indexes, without changing their order in any other way. Done recursively until we reach the trivial sublist length of one, this twists the list into an order that requires the maximum effort for mergesort to untangle. As a baseline, here are the rand distributions with the highest number of comparisons from "test-tool mergesort test": $ t/helper/test-tool mergesort test | awk ' NR > 1 && $1 != "rand" {next} $7 > max[$3] {max[$3] = $7; line[$3] = $0} END {for (n in line) print line[n]} ' distribut mode n m get_next set_next compare verdict rand copy 100 32 1184 700 569 OK rand reverse_1st_half 1023 256 16373 10230 8976 OK rand reverse_1st_half 1024 512 16384 10240 8993 OK rand dither 1025 64 18454 11275 9970 OK And here are the most expensive ones overall: $ t/helper/test-tool mergesort test | awk ' $7 > max[$3] {max[$3] = $7; line[$3] = $0} END {for (n in line) print line[n]} ' distribut mode n m get_next set_next compare verdict stagger reverse 100 64 1184 700 580 OK sawtooth unriffle 1023 1024 16373 10230 9179 OK sawtooth unriffle 1024 1024 16384 10240 9217 OK stagger unriffle 1025 2048 18454 11275 10241 OK The sawtooth distribution with m>=n generates a sorted list. The unriffle mode is designed to turn that into adversarial input for mergesort, and that checks out for n=1023 and n=1024, where it produces the list that requires the most comparisons. Item counts that are not powers of two have other winners, and that's because unriffle recursively splits lists into equal-sized halves, while llist_mergesort() splits them into the biggest power of two smaller than n and the rest, e.g. for n=1025 it sorts the first 1024 separately and finally merges them to the last item. So unriffle mode works as designed for the intended use case, but to consistently generate adversarial input for unbalanced merges we need something else. Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 27ba252d4a..d71ef568f3 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -150,6 +150,34 @@ static void mode_dither(int *arr, int n) arr[i] += i % 5; } +static void unriffle(int *arr, int n, int *tmp) +{ + int i, j; + COPY_ARRAY(tmp, arr, n); + for (i = j = 0; i < n; i += 2) + arr[j++] = tmp[i]; + for (i = 1; i < n; i += 2) + arr[j++] = tmp[i]; +} + +static void unriffle_recursively(int *arr, int n, int *tmp) +{ + if (n > 1) { + int half = n / 2; + unriffle(arr, n, tmp); + unriffle_recursively(arr, half, tmp); + unriffle_recursively(arr + half, n - half, tmp); + } +} + +static void mode_unriffle(int *arr, int n) +{ + int *tmp; + ALLOC_ARRAY(tmp, n); + unriffle_recursively(arr, n, tmp); + free(tmp); +} + #define MODE(name) { #name, mode_##name } static struct mode { @@ -162,6 +190,7 @@ static struct mode { MODE(reverse_2nd_half), MODE(sort), MODE(dither), + MODE(unriffle), }; static const struct mode *get_mode_by_name(const char *name) From patchwork Fri Oct 1 09:17:57 2021 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: 12529943 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id F32CBC433EF for ; Fri, 1 Oct 2021 09:18:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DA8ED61A51 for ; Fri, 1 Oct 2021 09:18:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1352906AbhJAJTq (ORCPT ); Fri, 1 Oct 2021 05:19:46 -0400 Received: from mout.web.de ([212.227.17.12]:47769 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229792AbhJAJTp (ORCPT ); Fri, 1 Oct 2021 05:19:45 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079878; bh=dyfeIr0gJmT8o2FBrINxKDbVaWlpxgBDcl19/sy7n58=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=bxbXL6ewBttjkyh7GqxC1DuxCgrQBSqoOb7JzZqTj26OrjWjGUIwVZ5GYIPSwJsdq Aaypt5qtmxUKuk6rc4rlSSOsZ/Z4Tfa9Xh9O5btXsgJHre4+mgvA4TKDPRdhIfvPqf CvpMaMreRaB1GEDNvV9Lc9mGJavD08GOdgvyjnrk= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb101 [213.165.67.124]) with ESMTPSA (Nemesis) id 0MMW2M-1mSNb61cIo-008K6p; Fri, 01 Oct 2021 11:17:58 +0200 Subject: [PATCH 6/9] test-mergesort: add unriffle_skewed mode From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <8763ebde-772c-500c-20fc-cbde43dcefeb@web.de> Date: Fri, 1 Oct 2021 11:17:57 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:ynsosH7KRiHwh5inIskZCv2dj64iZpdBvxPt3d7F1pUDsIE9zuq vBDM184zV9LIQqTRNV2gV3rMiYUXSp+bOp3R6H1s8nMgmZ+xWtEV44LPbYMZdip9iAPF/V7 FQBgjk3rN4zIWRezhlqQNXiHel8oHaMsG85wdWOjlMFn91pweogrrlXY0JF+sOvq0W7lZ8s yNsPhjn8F9ydMzrsGv7BQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:nO48ipw3mPQ=:Qz0bZi/lEVMkfHWkD5aQOx h41tWXyxHpKUR3YsZ8I83MHONtzcvKUhv0mbGCno2oSp3o+g2VnV3Hhuh1eywMWMpTtACgQpf uR0CI4UWvZZPyedLrTWzVTAbkRUA9VDhhtqa+aFrmKhp1KemvZOTxaWbNvPKPMwGr4Nh8WsGl FOsUzIpI4px6rkLV2OmX3huObAKwKNfrUt3Vaq4q4RDiC2CexuqVFXC9CYYd2BioYJ4JE98kR HLKcO9J7p/8hPfqNbs0vePckZBV++t7CBenj4sSHeN9JZKzOyOn3WOyJFqp2L4cMPCUI3cvbZ 5B5Xr4gvqwNPLW5EqTA54te4FN/LwVUfgRy8TzXccU4PpJp7CR1iymXB0LwOJe0s5kwc+EQgo pz44oVBRUurZJ30PP0iqdNUJ+EwkZy6amOrv1abaKZD168HstyHtB1oDnd5IqWPCiENtyQCZl 3FPT/f1DhwhPFqVAjLXEs+mLFtQ5Kxi2J1+WcROKFxx20QiiNCiVOX3TNCrwOwVo0Jc9BsPPF GbRaM0cnHTQCCA7FGlKGKozecjw83oqXtF36qER68cKxQPmJWsE09Br4w+WS0pi/LS270fkNE vK5O4CTKNAook/JvuhTrAt3BbDdEO5GUOtTFYLWo/FvMuxWo5LTbn8KSNkyqtDj7d4DRyVd7/ uDzhPRpJUKmygounaHGDHYdfsj9ejSZqQPXEyplbFH4kl8oxaIHbj2nmAJJDy6MbiSKK0kdQN OI0bTbG+hqj7Da7Npi0oFCS4xGf0cROBd2Te7BYhundHuDRPvS8j9QH4nBa0UbSzw5UVbYg70 zvjZXouiNzKYMg/NeJEot8CPDHYKxA26Tl3GGr5njdrO06vUJ40JoaQBRz5cu91RKlm1Y5PkP 6yrdb00NI95wYJmacZjI+HrYpcbEo9CI/0ZCp20LKvNMBEITVogpPNHI/8+dsDrHAwBZgCbfQ 7vD8UkNpdvaPARIgfquy4OHld5M7eh94UjJ6cES4+LI0F5k6xTDaijly3m25rYpQleJ7zKWLF 56jFwkVpdXspfQKlErrPNB/v/U4dG3kLnzUwMyhLwcwRH9RlOElqTgfVZMCyGDUB98RHmRiV4 rQF0cN4OAgZ0jg= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Add a mode that turns a sorted list into adversarial input for a bottom-up mergesort implementation that doubles the length of sorted sublists at each level -- like our llist_mergesort(). While unriffle mode splits the list in half at each recursion step, unriffle_skewed splits it into 2^l items and the rest, with 2^l being the highest power of two smaller than the number of items and thus 2^l >= rest. The rest is unriffled with the tail of the first half to require a merge to compare the maximum number of elements. It complements the unriffle mode, which targets balanced merges. If the number of elements is a power of two then both actually produce the same result, as 2^l == rest == n/2 at each recursion step in that case. Here are the results: $ t/helper/test-tool mergesort test | awk ' $7 > max[$3] {max[$3] = $7; line[$3] = $0} END {for (n in line) print line[n]} ' distribut mode n m get_next set_next compare verdict sawtooth unriffle_skewed 100 128 1184 700 589 OK sawtooth unriffle_skewed 1023 1024 16373 10230 9207 OK sawtooth unriffle 1024 1024 16384 10240 9217 OK sawtooth unriffle_skewed 1025 2048 18454 11275 10241 OK The sawtooth distribution with m>=n produces a sorted list and unriffle_skewed mode turns it into adversarial input for unbalanced merges, which it wins in all cases except for n=1024 -- the resulting list is the same, but unriffle is tested before unriffle_skewed, so its result is selected by the AWK script. Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index d71ef568f3..43ec74e2d3 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -178,6 +178,33 @@ static void mode_unriffle(int *arr, int n) free(tmp); } +static unsigned int prev_pow2(unsigned int n) +{ + unsigned int pow2 = 1; + while (pow2 * 2 < n) + pow2 *= 2; + return pow2; +} + +static void unriffle_recursively_skewed(int *arr, int n, int *tmp) +{ + if (n > 1) { + int pow2 = prev_pow2(n); + int rest = n - pow2; + unriffle(arr + pow2 - rest, rest * 2, tmp); + unriffle_recursively_skewed(arr, pow2, tmp); + unriffle_recursively_skewed(arr + pow2, rest, tmp); + } +} + +static void mode_unriffle_skewed(int *arr, int n) +{ + int *tmp; + ALLOC_ARRAY(tmp, n); + unriffle_recursively_skewed(arr, n, tmp); + free(tmp); +} + #define MODE(name) { #name, mode_##name } static struct mode { @@ -191,6 +218,7 @@ static struct mode { MODE(sort), MODE(dither), MODE(unriffle), + MODE(unriffle_skewed), }; static const struct mode *get_mode_by_name(const char *name) From patchwork Fri Oct 1 09:19:04 2021 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: 12529949 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id B5301C433F5 for ; Fri, 1 Oct 2021 09:19:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 92AF8610C8 for ; Fri, 1 Oct 2021 09:19:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1352897AbhJAJUx (ORCPT ); Fri, 1 Oct 2021 05:20:53 -0400 Received: from mout.web.de ([217.72.192.78]:36851 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229792AbhJAJUw (ORCPT ); Fri, 1 Oct 2021 05:20:52 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079945; bh=NK1d8BUqZNtz2yCWpgNz7R1A5M0Sd9cY3FfIvIlPQ0Y=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=PDXmZFA9N/Eh+/yKgL3z8jjBXKbkkLgMjRQyPbXQPKmX01ryVnMnLyw3lZ61zKAx2 EiPVjA7Pk3O3Q9U7cOzGwTl8WkjLgezOCrPr2Ae71QP3PtSSzd5NEW/19wo2+4v0jb 43KY5KK915ZXp48p/QTr+bUO98X/0oPAzr+vQlRw= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb105 [213.165.67.124]) with ESMTPSA (Nemesis) id 1MQgl2-1m8VJf0mu6-00O41I; Fri, 01 Oct 2021 11:19:05 +0200 Subject: [PATCH 7/9] p0071: measure sorting of already sorted and reversed files From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <3fa28f14-5e53-7367-b628-6eab2d5737be@web.de> Date: Fri, 1 Oct 2021 11:19:04 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:mMPo3rTo3Lx6pJp15jKk6UXxSWP0vGa6Ln+GzQxwbkSXq5sov3W rLusTQnK4mbJ/ObQf538BSOxYaXiszbH+aRDXV2K5OcsKVmEBsXSViNvQkQlnfzDC5YjKav ftU1LoQYKddY20+x5t2zHT8ILXyoiaHIL6h94jN6IV3UdH2k/Y0pGRxwwVmQTsS5m6j7xk3 0lHQQ56DXrVRbfjqr/Sqw== X-UI-Out-Filterresults: notjunk:1;V03:K0:/JfHREKQ3s8=:XcIeDSIeD1jzrzVRpme/oQ ONsqZFXQiTyA1Wa9RVnzfsS6IQVID3/QCAuxLlp+s3prsHuTRJApfF36EiQOCAt6oSxuebKM/ 9StG2SIJHlzMgT51W/v3p9y0oiGXogb5+fcZYAzRNrmqs7sY4DBdwHPYxGlLCMo7/6gQi+Uod BaK/mBJrT3kcDIV4gA1O5870jW5Gd7SHTP4KW+YxpYhHrKzR2nG2ukto+zWh3NVnYL0xN+sEh 6Di5nCuK7YV22pGteweMqozfwjiIT7mw+mFOE5wa3f1Jca2KuJkbcCwO9FJySLR1SZY8coXRM pVI+cj2onO4F1iOEjeDoV3LQRmUCZS/SxChx+NNTHpiAhf43AiV8TFBB0T42dXrYsALpjoyO+ fCOlHi7PDdu+JstpAais0uJaRr90bmcstBJHPA20v37CK5HA02dL1ZsOVitjb+RLh6sK7fXER mTZX7cnGFVHNng9hLmEubylGQGlQewH+mMbZ8PJY7pgtZRrb+Oj55DE/l97TODBy+0WppSubK ouLPJK9pdQShA4PVa3ptMyxH+j6ZbUaRqbJ+qpS9B1U3tmfSGep7j3n0S5igb/GOVP1zpRxqI o5qS0aHN0xvaBCoa2wXvGJI+gkpG/Fp6eREW3LmahUl5I01HtbDikP+eo4K1YoUCkJave14zE xV/aMVmliPIw0W3sxYuQTmtBmvH0kURIPPnFm3CtYpUPkg1tqOshC864LlxcS3/goTV5cwodU pNlW9XAZwit4qObB1VFOpdDjhr9Sca3OnbTxdnQwWmhBkha+VMYs6q+myhLPdYtkX44WAnCjq HWzyxrK2QMvT+SNilHb+rQi/O4xuAHEnaSrObzwbwq6xEmM22B0BKcOos9WXjQSWmiEngq/5G HGtVfMnbde3d4ko8bb5ZzS/CkUywwb9njjcQxBEworKiXEQFA/7YTqotj5qOgxo/u0s6xTmQq Q5fd6c3kJck2Ps/5ar2BOjc1KF6gNozYMD4CcfUkC9mm9zA4g+OBHjpINUExVTnTKSDr/U0Lo JW5yoR0JcMYYIY2W81RxsnhmILhPgUHOOZhiThnDD74VLR1rTY+eZT5cyC8UqkW3lxstwlVrP 9A2CcecixASSyI= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Check if sorting takes advantage of already sorted or reversed content, or if that corner case actually decreases performance, like it would for a simplistic quicksort implementation. Signed-off-by: René Scharfe --- t/perf/p0071-sort.sh | 29 ++++++++++++++++++++++------- 1 file changed, 22 insertions(+), 7 deletions(-) -- 2.33.0 diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh index 6e924f5fa3..5b39b68f35 100755 --- a/t/perf/p0071-sort.sh +++ b/t/perf/p0071-sort.sh @@ -11,16 +11,31 @@ test_expect_success 'setup' ' git cat-file --batch >unsorted ' -test_perf 'sort(1)' ' - sort expect +test_perf 'sort(1) unsorted' ' + sort sorted ' -test_perf 'string_list_sort()' ' - test-tool string-list sort actual +test_expect_success 'reverse' ' + sort -r reversed ' -test_expect_success 'string_list_sort() sorts like sort(1)' ' - test_cmp_bin expect actual -' +for file in sorted reversed +do + test_perf "sort(1) $file" " + sort <$file >actual + " +done + +for file in unsorted sorted reversed +do + + test_perf "string_list_sort() $file" " + test-tool string-list sort <$file >actual + " + + test_expect_success "string_list_sort() $file sorts like sort(1)" " + test_cmp_bin sorted actual + " +done test_done From patchwork Fri Oct 1 09:19:51 2021 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: 12529951 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 964FFC433EF for ; Fri, 1 Oct 2021 09:19:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7524361A05 for ; Fri, 1 Oct 2021 09:19:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1352927AbhJAJVl (ORCPT ); Fri, 1 Oct 2021 05:21:41 -0400 Received: from mout.web.de ([212.227.17.11]:55749 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229681AbhJAJVk (ORCPT ); Fri, 1 Oct 2021 05:21:40 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633079991; bh=v/OvrM/HVyePSlOY7IhwJjEDPmtLc9DUT0zljf2IDJI=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=EuWtUL2koIoYxIqwcOm7YcnuLmRKXjij7W85lEjCS+l9tF1aGt61oAVe9NE+F2FlO 7aJO1wKbRHqi4CEOqNgHx8SW1k+2V0f0Ozb2dgdNt7M5AGxHVkzSCiysokrBj2Lqj3 ow49l5hHiY8KPYKS6EnQPucYljUrHKwZBKYMA9dg= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb102 [213.165.67.124]) with ESMTPSA (Nemesis) id 0MBkLb-1mdhLc35HD-00AmHO; Fri, 01 Oct 2021 11:19:51 +0200 Subject: [PATCH 8/9] p0071: test performance of llist_mergesort() From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <9ecbd8c8-2907-7955-0b85-f9bbae8475d1@web.de> Date: Fri, 1 Oct 2021 11:19:51 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:rwHQTJ4RAfwpTnK2NncBIEJuNp1fM8F7U3Oio7QD9ywdzw+QWsr AEMzZLuFcQm9pv1/RxmS4N7c0aPPWqpJ5B1yxN4PgQZP7BGy2JY0jd5ugV5xsApbxBL0min Jx5YISalrXS1uOcpaupVCI2mPbSNVTpWweQTrkh+tDgY2FHM9HuRlKflNyvdW3PS8PsT39g PXh51af5qZWqdCn8fWfBA== X-UI-Out-Filterresults: notjunk:1;V03:K0:F2W+qKeBMHw=:zpNeRHjAQVAtkqJHaAb0z3 HgABrTlWq6CIRkuEtU/Lqar1LAEgOP6FBchDkaKNzMJT9aKBw811oeD7IPkiUvZxZTjfF/J14 2EzvwGWRHindsXmISkBHoXtYqSu7j6iePlO4kfgOnfVVSu5rh4Guf6HCBaoTysG/bQcm0bYWK qExFeAnQM3Cm8gzcqa5hAHgcmS36eXcrLHCpepSrTGTZWuk10/0noaHa8pAfi0Q1y4HW2v/vv ZhWvMlhbtJfcs2bCZMDAXh+YUVQtPEBsH8KrUVjcJFlA0h+ArNYceBaUsvJuY6V9RC6LEkWcL fY9fWEQjKSkl0DyOxJdNKHefmGnsM4xjDfAliwjRLzAP+p37XfrrTg9E2QLKt1p/jZcST4IQI 7YXJit+zjckYW5VMyg6Csm4AeC5ah70u36MMLWWIBqwcbSFexHDHmg8vGfz5cRxwzAcPP22gG aYt2lDAxboR9m6wp6jxhthccikKdGP/SDESEywTwGHYOUwC/T7Wi1CmDYreXi+8EZk5YNObQK Fr8w9iaBweP5QkHlnHNANw2JNEbCagLB+AWpGi28N8i7QgVbBI48eX/wTpbunIienQkXzlD0y WwzxO9RXeM5AWq+lg3TFY/KJNvfGd2f3/RI/iyjP5uFS3EQ3YiN3Bi4dUGkjlnpS/ky8YniKe cohWgZBZa5a6euiHi7CdzzWm46hSrDgOoeRwWPHT3tbikJgEUyC8MUPFjKQFgpPjF1E3eWZsd GzrctBJVbBfeFvFGewQ7FNXExKFjhb8UKUl4RR5is8CoBgw8Gli0hcERhAswt6md8I/74krMw OZrs/UEfDipYsgrpV4WLNRvl7w6C7nLMzqfyLmW2Fb01EJROOann4sezIIljSL7CKTwjeVvNE MRwj8GLAl6TcUKsjtKuYjfECzNaHYewTvelRodV7sx/s5+dwf2gNMX4qUNG6V4P/ldJbvrOeS Y/JNVlSZDo3SuN4F9e/b0LxiWqn1YG8M+MHBseOBLm+31dUtEZJ5QgZDO5tbXt2EN8estfWUU ubOnzJs3J9Vfa7VsyY4hFPDKLKbqiLwAmRavMYawl2cjU/KbXzAUF4amKd9oxxmKEyOvnUyBd fjrkZQFdSrH9H8= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: René Scharfe --- t/perf/p0071-sort.sh | 11 +++++++++++ 1 file changed, 11 insertions(+) -- 2.33.0 diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh index 5b39b68f35..ed366e2e12 100755 --- a/t/perf/p0071-sort.sh +++ b/t/perf/p0071-sort.sh @@ -38,4 +38,15 @@ do " done +for file in unsorted sorted reversed +do + test_perf "llist_mergesort() $file" " + test-tool mergesort sort <$file >actual + " + + test_expect_success "llist_mergesort() $file sorts like sort(1)" " + test_cmp_bin sorted actual + " +done + test_done From patchwork Fri Oct 1 09:22:39 2021 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: 12529953 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A851FC433F5 for ; Fri, 1 Oct 2021 09:22:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8DB0461A58 for ; Fri, 1 Oct 2021 09:22:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1352971AbhJAJY3 (ORCPT ); Fri, 1 Oct 2021 05:24:29 -0400 Received: from mout.web.de ([217.72.192.78]:59429 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1353029AbhJAJY2 (ORCPT ); Fri, 1 Oct 2021 05:24:28 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633080160; bh=n6w4CQLItzfHt8jF9AaXDRlMbTIUhOmaWfuK+45V/ZY=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=Gl166SaDW/8teCBMJolsQBg61BBMZXxyIz77WguyE4UB/JLzIeCXhATFHia++y5Ti 9S/lcR4ZFwTkryCEj1gMUBXVvkwhmh9KSgPMB30ODvzQwnDPHPhLzJYxRXmqO7O3br bM7fLZ9q1hSCjxcoDIaPq1QDyG+4xI4PkHxgf088= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb102 [213.165.67.124]) with ESMTPSA (Nemesis) id 0Lzb94-1mrUjN3nYA-014n1g; Fri, 01 Oct 2021 11:22:39 +0200 Subject: [PATCH 9/9] mergesort: use ranks stack From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <943b1e01-465e-5def-a766-0adf667690de@web.de> Message-ID: <636647b1-f666-f1e2-4127-ee0869b61036@web.de> Date: Fri, 1 Oct 2021 11:22:39 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <943b1e01-465e-5def-a766-0adf667690de@web.de> Content-Language: en-US X-Provags-ID: V03:K1:lG3kJnx3Irmf/74D4oFxLWoTbugUMEJcVZzJ+md1uNpeEeoz/mB Jw2Fg1Sp+9As9ktKHQc9NtccVt1uxKM6Q7neIIPFju0uXu0R2zG3yM3J6Yr8AU4FbUJgYqc Ds7kXzjVIc6NwO3q2lJdbjkf11ywtnybCpNAiX82mL9no1xI3zRPYadR/65pjlWTZjgpPSq Cpu8mQshaIunIT3wXHnQg== X-UI-Out-Filterresults: notjunk:1;V03:K0:claqsnqsrNs=:RQNoA9gwDSRRhS/MuZSpiD 4QIIqdP6fMmnEHmKLm4e4Gp1VWEZVFbFcTw0o/Kj2WdUlcgExxwoYDq+8uiZX1iA8NPrRxXI5 nJZgIJU0ZF+JTrJ0ZUS6bUktjE+Q+oN/Yl4KQEAqvxUxG/q3kJUeO5zqCvzc2uMCaWAz/cXt6 3Mxbghmo3ZWPHtKHKGhNTc4lRXGg9pFIoK7CyPCxmqLoXYTicpVKDL8AZ7iVZQ3LntBq4cT0Y GAmwrMOlAzMuhMinzLl1HBOe7ov2/XeuGCba/OOHARhyzs3ScZEGxwtLkYLYoSKDf6Md1iSnH VIqfF+7LSqsKxTs6zF5adzWPMUW+3Pa992ap45pzUkds+lcE/Jt7zrBQSNYAmgTTHOCQioQ79 uFXJPrkUGc3YSmtnYRFlJTxkaKqzVvHGwoSzIp0bR3irc9P4lZJ5FuD/YaBwPEHlcI3c3jt8U ROnyyqGCN7OfkZP6vTsvASFNRg5gNOnwBnBJBj2vcr1LwQSo2e4V/BFMF1hjepbm2ioTa+Yx0 fy6iQB+d4gZtSXtwfaFvfytQDblf2AlYqLehbHzvgJH4fKf23BY0QEr5tK5AsLDfL0MdaDddf 5ZlQbv1rXI+CTzzvEzdGUq6m8zJxql/fsIzWIOXtbYoz2lrne/4PEnCiaV4bVUQ4XPGkmQhES XH48R5Gd4z1PJPP3PfnkpS9BCo1NSFV6MBmQ8BOTyVRge/UpqJHFlQrU4O+9ZeHTKqtsR++Iy kPYZyQvqvTGCZjWoVR7B5vECztbILUeIXtOvk96kCZZhXHRY7JaYlfkdhMAnq+1nkNRim4ye/ HrHGM7UmMiZtjCEcvUGlyr/D5/loeIWlHWwam5ExagllSSKNodH7usE1XD8qlSGdo48XeaQnP NTbm4fsxY566wfUdqEujGeUDJQtVEYQb5RAt4YIgryKr0EqQ+MAkyFuhYSsfo+M6yDCJNCRcq U8iNSbO8fKwRC764QSfSCOQTpzrPrJc1z3Cz/NiKTOzxFKprvttzqwwUk2eeBiKQstHZ1vMjo yydFks+q1BMuan3NmJHbC6omYCU3c8ZIIbf3G88sE/cV7HC2QJPBV67yGymm2ITCGST5MJBE0 dxIOeDnnXEin5A= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The bottom-up mergesort implementation needs to skip through sublists a lot. A recursive version could avoid that, but would require log2(n) stack frames. Explicitly manage a stack of sorted sublists of various lengths instead to avoid fast-forwarding while also keeping a lid on memory usage. While this patch was developed independently, a ranks stack is also used in https://github.com/mono/mono/blob/master/mono/eglib/sort.frag.h by the Mono project. The idea is to keep slots for log2(n_max) sorted sublists, one for each power of 2. Such a construct can accommodate lists of any length up to n_max. Since there is a known maximum number of items (effectively SIZE_MAX), we can preallocate the whole rank stack. We add items one by one, which is akin to incrementing a binary number. Make use of that by keeping track of the number of items and check bits in it instead of checking for NULL in the rank stack when checking if a sublist of a certain rank exists, in order to avoid memory accesses. The first item can go into the empty first slot as a sublist of length 2^0. The second one needs to be merged with the previous sublist and the result goes into the empty second slot as a sublist of length 2^1. The third one goes into vacated first slot and so on. At the end we merge all the sublists to get the result. The new version still performs a stable sort by making sure to put items seen earlier first when the compare function indicates equality. That's done by preferring items from sublists with a higher rank. The new merge function also tries to minimize the number of operations. Like blame.c::blame_merge(), the function doesn't set the next pointer if it already points to the right item, and it exits when it reaches the end of one of the two sublists that it's given. The old code couldn't do the latter because it kept all items in a single list. The number of comparisons stays the same, though. Here's example output of "test-tool mergesort test" for the rand distributions with the most number of comparisons with the ranks stack: $ t/helper/test-tool mergesort test | awk ' NR > 1 && $1 != "rand" {next} $7 > max[$3] {max[$3] = $7; line[$3] = $0} END {for (n in line) print line[n]} ' distribut mode n m get_next set_next compare verdict rand copy 100 32 669 420 569 OK rand dither 1023 64 9997 5396 8974 OK rand dither 1024 512 10007 6159 8983 OK rand dither 1025 256 10993 5988 9968 OK Here are the differences to the results without this patch: distribut mode n m get_next set_next compare rand copy 100 32 -515 -280 0 rand dither 1023 64 -6376 -4834 0 rand dither 1024 512 -6377 -4081 0 rand dither 1025 256 -7461 -5287 0 The numbers of get_next and set_next calls are reduced significantly. NB: These winners are different than the ones shown in the patch that introduced the unriffle mode because the addition of the unriffle_skewed mode in between changed the consumption of rand() values. Here are the distributions with the most comparisons overall with the ranks stack: $ t/helper/test-tool mergesort test | awk ' $7 > max[$3] {max[$3] = $7; line[$3] = $0} END {for (n in line) print line[n]} ' distribut mode n m get_next set_next compare verdict sawtooth unriffle_skewed 100 128 689 632 589 OK sawtooth unriffle_skewed 1023 1024 10230 10220 9207 OK sawtooth unriffle 1024 1024 10241 10240 9217 OK sawtooth unriffle_skewed 1025 2048 11266 10242 10241 OK And here the differences to before: distribut mode n m get_next set_next compare sawtooth unriffle_skewed 100 128 -495 -68 0 sawtooth unriffle_skewed 1023 1024 -6143 -10 0 sawtooth unriffle 1024 1024 -6143 0 0 sawtooth unriffle_skewed 1025 2048 -7188 -1033 0 We get a similar reduction of get_next calls here, but only a slight reduction of set_next calls, if at all. And here are the results of p0071-sort.sh before: 0071.12: llist_mergesort() unsorted 0.36(0.33+0.01) 0071.14: llist_mergesort() sorted 0.15(0.13+0.01) 0071.16: llist_mergesort() reversed 0.16(0.14+0.01) ... and here the ones with this patch: 0071.12: llist_mergesort() unsorted 0.24(0.22+0.01) 0071.14: llist_mergesort() sorted 0.12(0.10+0.01) 0071.16: llist_mergesort() reversed 0.12(0.10+0.01) NB: We can't use t/perf/run to compare revisions in one run because it uses the test-tool from the worktree, not from the revisions being tested. Signed-off-by: René Scharfe --- mergesort.c | 121 ++++++++++++++++++++++++++++------------------------ 1 file changed, 66 insertions(+), 55 deletions(-) -- 2.33.0 diff --git a/mergesort.c b/mergesort.c index e5fdf2ee4a..6216835566 100644 --- a/mergesort.c +++ b/mergesort.c @@ -1,73 +1,84 @@ #include "cache.h" #include "mergesort.h" -struct mergesort_sublist { - void *ptr; - unsigned long len; -}; - -static void *get_nth_next(void *list, unsigned long n, - void *(*get_next_fn)(const void *)) +/* Combine two sorted lists. Take from `list` on equality. */ +static void *llist_merge(void *list, void *other, + void *(*get_next_fn)(const void *), + void (*set_next_fn)(void *, void *), + int (*compare_fn)(const void *, const void *)) { - while (n-- && list) - list = get_next_fn(list); - return list; -} + void *result = list, *tail; -static void *pop_item(struct mergesort_sublist *l, - void *(*get_next_fn)(const void *)) -{ - void *p = l->ptr; - l->ptr = get_next_fn(l->ptr); - l->len = l->ptr ? (l->len - 1) : 0; - return p; + if (compare_fn(list, other) > 0) { + result = other; + goto other; + } + for (;;) { + do { + tail = list; + list = get_next_fn(list); + if (!list) { + set_next_fn(tail, other); + return result; + } + } while (compare_fn(list, other) <= 0); + set_next_fn(tail, other); + other: + do { + tail = other; + other = get_next_fn(other); + if (!other) { + set_next_fn(tail, list); + return result; + } + } while (compare_fn(list, other) > 0); + set_next_fn(tail, list); + } } +/* + * Perform an iterative mergesort using an array of sublists. + * + * n is the number of items. + * ranks[i] is undefined if n & 2^i == 0, and assumed empty. + * ranks[i] contains a sublist of length 2^i otherwise. + * + * The number of bits in a void pointer limits the number of objects + * that can be created, and thus the number of array elements necessary + * to be able to sort any valid list. + * + * Adding an item to this array is like incrementing a binary number; + * positional values for set bits correspond to sublist lengths. + */ void *llist_mergesort(void *list, void *(*get_next_fn)(const void *), void (*set_next_fn)(void *, void *), int (*compare_fn)(const void *, const void *)) { - unsigned long l; - - if (!list) - return NULL; - for (l = 1; ; l *= 2) { - void *curr; - struct mergesort_sublist p, q; + void *ranks[bitsizeof(void *)]; + size_t n = 0; + int i; - p.ptr = list; - q.ptr = get_nth_next(p.ptr, l, get_next_fn); - if (!q.ptr) - break; - p.len = q.len = l; + while (list) { + void *next = get_next_fn(list); + if (next) + set_next_fn(list, NULL); + for (i = 0; n & (1 << i); i++) + list = llist_merge(ranks[i], list, get_next_fn, + set_next_fn, compare_fn); + n++; + ranks[i] = list; + list = next; + } - if (compare_fn(p.ptr, q.ptr) > 0) - list = curr = pop_item(&q, get_next_fn); + for (i = 0; n; i++, n >>= 1) { + if (!(n & 1)) + continue; + if (list) + list = llist_merge(ranks[i], list, get_next_fn, + set_next_fn, compare_fn); else - list = curr = pop_item(&p, get_next_fn); - - while (p.ptr) { - while (p.len || q.len) { - void *prev = curr; - - if (!p.len) - curr = pop_item(&q, get_next_fn); - else if (!q.len) - curr = pop_item(&p, get_next_fn); - else if (compare_fn(p.ptr, q.ptr) > 0) - curr = pop_item(&q, get_next_fn); - else - curr = pop_item(&p, get_next_fn); - set_next_fn(prev, curr); - } - p.ptr = q.ptr; - p.len = l; - q.ptr = get_nth_next(p.ptr, l, get_next_fn); - q.len = q.ptr ? l : 0; - - } - set_next_fn(curr, NULL); + list = ranks[i]; } return list; } From patchwork Fri Oct 8 04:04:42 2021 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: 12544193 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6CCA1C433EF for ; Fri, 8 Oct 2021 04:04:55 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4B60760EE3 for ; Fri, 8 Oct 2021 04:04:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237387AbhJHEGr (ORCPT ); Fri, 8 Oct 2021 00:06:47 -0400 Received: from mout.web.de ([212.227.15.3]:37271 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237160AbhJHEGn (ORCPT ); Fri, 8 Oct 2021 00:06:43 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1633665883; bh=NAJnOPJHM4rWarUMM3Iq3UdU8ic7qASqEnCUAZGJV3E=; h=X-UI-Sender-Class:Subject:From:To:Cc:References:Date:In-Reply-To; b=q0iPfGJ79+I+sIg7CnHRknQIvn2VHhX9CDk8KU05221/N+tQWDaTHa4rBvGE8Nxc/ lzJ50RObga1fnZwdHRKJ+8kzcehvUV1GhzpQYJ/5cpCuXkZs9Ww9OnE9zXTmxvfZUA hjbVjb3oisrPilIQa0bl7MIHrXRL7yCl8qN6461U= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from Mini-von-Rene.fritz.box ([79.203.20.171]) by smtp.web.de (mrweb004 [213.165.67.108]) with ESMTPSA (Nemesis) id 0MYq7X-1mKeLo3C1T-00ViBS; Fri, 08 Oct 2021 06:04:43 +0200 Subject: [PATCH 10/9 v2] test-mergesort: use repeatable random numbers From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Junio C Hamano Cc: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsCBCamFybWFzb24=?= , Git List References: <943b1e01-465e-5def-a766-0adf667690de@web.de> <522fba5e-1048-3377-45c1-7107b55dc6e1@web.de> <87o887q0s9.fsf@evledraar.gmail.com> <850aa059-61d9-0eba-5809-e0c27a19dfb4@web.de> Message-ID: Date: Fri, 8 Oct 2021 06:04:42 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: Content-Language: en-US X-Provags-ID: V03:K1:4X7VE5zOxB4gh+T8uaJfcTCq3SvlxuZrL621l+GsRsYB57xELoa 1GTh6k7kpZqXKZ7QTj4vNcv01n8EYYG9vRRYtxR+9cB5puZVQrFq3bSlCJSw9eVTPICvvyP dGQm248LlFTFaICgIuPNQ7lWdbvG/B+AASwP68YkDXCup1Frn8zVMgHtlcelTslZC70rmiY n+fwgrSTfvvvCdXtEhRJw== X-UI-Out-Filterresults: notjunk:1;V03:K0:PiJs9it9MXc=:+QgvUCcYsXQ1Uu0u7NyP93 im4fCPqEk6oC2SDmifBLxEqVVV9eBBhmP65/+tUKWG+/vbRQIqcUjKX+RtzTJWy5ueKw/bQfo kIxH471SNNogOEX+2+V4VucFg5qMvhTucqzYKYDgaX5wX0zE53ojH6ihFA9ZZ4ibMSNbSYBIc yTZddZ6cu1y47kj6KHhn1dKaXGQO6wjq4VzhzMtTVfgKN8rRT4/oa3A6f092AKS4JPlfnnp+c HGvvPb22y+smr83NtamCcJovdnh/bSQUe6gy5Mq67wtXYgDCTdxHTJnYYq8428ScHHEJsEZ9M ZRBCHtZe+3IbUmHoq2yRmkEt0/0/r1j9iAxYEzHuhUiFYt3MpsHyxfVyldlN01RZD8EGY5hOq XKqCbwmY7It58PLlNddgHAtR+44cqobm5KGRNgyEomjvKNcYU8VB5leVit64Pd8cJFdIWkwkY krW++rHInS7e518MEM2r8TXC/VSzmQK6ZRSNxHaf5fVa/t2lQ9lapt3HsZxKEMcZAdyJalcHU PHyZ2akxJ5mgZasCLCNyZ3ywBYJ6dnyLPuGiasVMqbGv00ieo+RbgSsiIgggc0pBBBfNs8amX 6N2BvP7SY0KlEbGOw3PUw7J9r0A3TIuVOZhj3+FYqJNSpW7CB0Gi541V1V+Q/d/exNcCmfdu3 7J38zBmL0QLo/p86IVoJFuRt45itYBFWBnesKdMRgv9xcmjuIalyN/ovEs4YCij+rp/Xln3BN BBOf7n2QyrlFf+z+ro2zXXni/2lWlea+9X6eysENQEhzmVlgBTJNgnKxHJTNXV4mAlWgIlg25 VEDDKWeXsGwCsrJaIvi+WkbylBfpOqdyOLstuM2M0iw2YVXm96V2dfBNjb1XHPKN3oafX1Tuk FZ2jgX8gzuiX6GNjy3XSBYXg0EJAUBbLkHyxx0RFcPtMMWkccmNjzaRYZaqpjxpaGrFCHrO1S TQAfeoDr77SZPd3ojw/+O0zrmvOrGtDFlRf9hg0yDWONf1lP19caicNaHin0s4UA6w8JUtUAK lhsfMppprmTRSyYsdpze9RNa6k+bOZYZV1QiHzkyvO+LqF5vrtxE4z+iqa6LrJHVYhJr+nrcW SYH0fBFsnnGlAs= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Use MINSTD to generate pseudo-random numbers consistently instead of using rand(3), whose output can vary from system to system, and reset its seed before filling in the test values. This gives repeatable results across versions and systems, which simplifies sharing and comparing of results between developers. Signed-off-by: René Scharfe --- Change: Use uint32_t to avoid relying on unsigned int being exactly 4 bytes wide. D'oh! t/helper/test-mergesort.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) -- 2.33.0 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 29758cf89b..c6fa816be3 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -2,6 +2,12 @@ #include "cache.h" #include "mergesort.h" +static uint32_t minstd_rand(uint32_t *state) +{ + *state = (uint64_t)*state * 48271 % 2147483647; + return *state; +} + struct line { char *text; struct line *next; @@ -60,8 +66,9 @@ static void dist_sawtooth(int *arr, int n, int m) static void dist_rand(int *arr, int n, int m) { int i; + uint32_t seed = 1; for (i = 0; i < n; i++) - arr[i] = rand() % m; + arr[i] = minstd_rand(&seed) % m; } static void dist_stagger(int *arr, int n, int m) @@ -81,8 +88,9 @@ static void dist_plateau(int *arr, int n, int m) static void dist_shuffle(int *arr, int n, int m) { int i, j, k; + uint32_t seed = 1; for (i = j = 0, k = 1; i < n; i++) - arr[i] = (rand() % m) ? (j += 2) : (k += 2); + arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2); } #define DIST(name) { #name, dist_##name }