From patchwork Sat Jul 16 16:52:31 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: 12920191 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 AA36DC433EF for ; Sat, 16 Jul 2022 16:52:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231528AbiGPQwn (ORCPT ); Sat, 16 Jul 2022 12:52:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50904 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230448AbiGPQwl (ORCPT ); Sat, 16 Jul 2022 12:52:41 -0400 Received: from mout.web.de (mout.web.de [212.227.15.4]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 89F211DA5D for ; Sat, 16 Jul 2022 09:52:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990352; bh=uOOvUnAVEgBBF3N5MP00f109ngKuXeeXmyNwxLUZc2c=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=DipfK4Uc7H7wiOpPC77CcEy1Gp44+vdS0m2A0Bri1XyVrTcKOIEGmRhCAglbsNW7A XwBlvGj+woI6ziWv3YLdHbWtigSjxHYPfbE7QJO7TIoyNz3oRnSMxQHuqz2oELj3zv ClTUbYWbLlwMKCOYRYive+pNuBv8/FT2XAi+HsCU= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb006 [213.165.67.108]) with ESMTPSA (Nemesis) id 1MdO9E-1ndQDA222C-00ZIPe; Sat, 16 Jul 2022 18:52:32 +0200 Message-ID: <50b229e9-46b7-fdd1-3f68-de8dd4acf811@web.de> Date: Sat, 16 Jul 2022 18:52:31 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 01/10] mergesort: unify ranks loops Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:Q4jYaXuZuAE3ooDURVH/AoydeeoPCL+9DxSerN0GR0tFMQ1kJIG uKaOPdfc3eygpPC+dYAjcWnLF8x7ckSnCc4HsNwiVqYRmOEOtXEF0q8GIsr6ExFxo1LYab5 VXdOxb1x4L29KVLI/bwyYZU6dcKhqyDm7CGBFZU4Qrs3OJrmYUVZFJDGQo1yjiIzxUBYnEh gxM3gVHi9SuBL6W+dCM0g== X-UI-Out-Filterresults: notjunk:1;V03:K0:u6rzjNYKl7U=:FT+T6BlMXColhTctB3CBf1 qQBONrco3CJeq8t6N2XOjrqFLopHEtVdwgmZNa9Qvz9bxSNxYFQ0mpLc9+aJS8HYXm6x3O+ff bu2kKlw1gyCWGgjIDhp56Ks6aWNLAj2XK+zOj3vef43R5190qmuDD4X4yT1S5dIKegWtH+VZ6 Ll7ywUaW36nqyS0iznbBKmACcg8CdNE0Df3DCIOqkQFh1Z8rybqJAjkDUyhNI750fKrYupSa9 fJ/Hig9YN4eKb67b+avveo3EJuxFcAdY2HiAkr/3DPdJd1K3GwFNhk63gzEWWiry7cXnMIweu Oy0geJI89H5p91fOAk4vjJy6H4mbgT34+3cLWdFDaXgSdkpmhgUAXUJFfwSV7ID8XcmR+rH4q c0J7AeVexHzwZXMi5x//4Afx0xg1Je9dv8SiQc2y5Tzo53p3RAWXuVgSJRCT9KlxeJHVdEkOx HEcE1+Qn8yaiMOgV+sqUtQnhkHoNOQL+rCA7Azxef40gsdQXCDCQ5d2m3TBhsMMpyErR03Nxl xbgwLchq250ItQXW79Zaj5BOyy9bhfR0FuLzD+wboi9BikHe9nVA5YgtpLOcVGA3w3B/1xSsj 9XZ8B177BOfvPldPbOP+tAUzj+eUpZYunxbjwfLiVnuTcqoxXtSkI0CJbSn1xQl+RW+kaXSyF A5vgKX1ZfAcKVK5WXsLeI0sDdtS+eaN1ep1UY6vKNnKLfiF/ex4LqrXHTSOqr83rKnQNwRoBr Xs293bcSG/9rDQQ0PCYDBU6kH7pP2gPSHeGYLaNuGovCM/7+K2oTb4N+wA3q/lBpqfVqy1t3U WeKkkA0P7uArC5yMvdazKy2xBOE9HDAIeCCH40c8VSIup1BH5nbXV6ZE5jSZoxZD+VxOvoSlu RKOcx+Eohrdx0jj6lK9dveBg5/vJ+DlWKEte7gEXu05QI21hXtBZhCJ8hRM0t4OO7vt0PdBPb ajykZOOlbnrPUlGIVcBVszvPwjyUK/smpBnETqj1y56SzfFFeLBzyj88V4J2Nborn07mnn23S nV+lyNSEzAIl1CzFRyZZEZgRrUiK9BneBY6RYHkOZMoTxcU9YvQYaBweNGLMT9LDXVeukOq+F s7nWtZLM1IfZwcsCYc23Xs0m4izBy2fAzr3 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org llist_mergesort() has a loop for adding a new element to the ranks array and another one for rolling up said array into a single sorted list at the end. We can merge them, so that adding the last element rolls up the whole array. Handle the empty list before the main loop now because list can't be NULL anymore inside the loop. The result is shorter code and significantly less object text: main: __TEXT __DATA __OBJC others dec hex 652 0 0 4651 5303 14b7 mergesort.o With this patch: __TEXT __DATA __OBJC others dec hex 412 0 0 3441 3853 f0d mergesort.o Why is the change so big? The reduction is amplified by llist_merge() being inlined both before and after. Performance stays basically the same: main: 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) Benchmark 1: t/helper/test-tool mergesort test Time (mean ± σ): 109.0 ms ± 0.3 ms [User: 107.4 ms, System: 1.1 ms] Range (min … max): 108.7 ms … 109.6 ms 27 runs 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) Benchmark 1: t/helper/test-tool mergesort test Time (mean ± σ): 109.2 ms ± 0.2 ms [User: 107.5 ms, System: 1.1 ms] Range (min … max): 108.9 ms … 109.6 ms 27 runs Signed-off-by: René Scharfe --- mergesort.c | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-) -- 2.37.1 diff --git a/mergesort.c b/mergesort.c index bd9c6ef8ee..92150c4101 100644 --- a/mergesort.c +++ b/mergesort.c @@ -57,28 +57,27 @@ void *llist_mergesort(void *list, { void *ranks[bitsizeof(void *)]; size_t n = 0; - int i; - while (list) { + if (!list) + return NULL; + + for (;;) { + int i; + size_t m; void *next = get_next_fn(list); if (next) set_next_fn(list, NULL); - for (i = 0; n & ((size_t)1 << i); i++) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); + for (i = 0, m = n;; i++, m >>= 1) { + if (m & 1) + list = llist_merge(ranks[i], list, get_next_fn, + set_next_fn, compare_fn); + else if (next) + break; + else if (!m) + return list; + } n++; ranks[i] = list; list = next; } - - 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 = ranks[i]; - } - return list; } From patchwork Sat Jul 16 16:53:45 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: 12920193 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 F4024C433EF for ; Sat, 16 Jul 2022 16:53:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231557AbiGPQxx (ORCPT ); Sat, 16 Jul 2022 12:53:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51684 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230448AbiGPQxw (ORCPT ); Sat, 16 Jul 2022 12:53:52 -0400 Received: from mout.web.de (mout.web.de [212.227.15.4]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 63BC764E4 for ; Sat, 16 Jul 2022 09:53:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990426; bh=LvdXq/5BE/hS/ln1un1xjC98Al1GF4eDWxuAR4BKsrk=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=nWxQ2FQk/ZkEIQWBkuPq6P/7zh07D+CCQeyOf+SuDraDsmX/YhcEZTTiaOfF1qlum gWdn1GRrfDOdAoTz3QPLisCc2sOIT7MQLTCYFeu/6OOl81eiAVwPWGf3oPpQPUrKwk /SmyYTHKlEyZc0tQX7K2M6LZ3x+OO8r83LNIVAnQ= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb005 [213.165.67.108]) with ESMTPSA (Nemesis) id 1M43GO-1oCl334Bay-0009Cb; Sat, 16 Jul 2022 18:53:46 +0200 Message-ID: Date: Sat, 16 Jul 2022 18:53:45 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 02/10] mergesort: tighten merge loop Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:5a6LGp29fjpl1k11E3DupnAgbDpZgVKzxOQtQ7C98XKgCKKYR+I mlesA+Ajwjr7DfX/n7Rm8QdJWYcjb5/sFw6jNpWSCBzTqupFvxJhch8FkliDhhqdxgx9ofB inJ6T2oFKEtpLsiBiF55fzhn0gyvmdU5dFcwAEWKfOgvm7v5D3PmZwcC7pJGrPd0fwqgMN7 wLk3X6hU06bsGyA3kOqFA== X-UI-Out-Filterresults: notjunk:1;V03:K0:jfpfFu3MYI4=:j9IqB1dsj2FgFl1eAFjyP2 PYXB4Zz3FauWTlX9FpxzX2b0JjAlQtfk0UCeqmp13YeBea0yGneQdP0P4PwBkX+A5H2RoI+hO wHND3N0WplGPuW8J2JtFYYWrJal+2l+1sCxN8ALe4aJviV+05rQb2LfDtydWsq8niOR2vPaYb hLJ/tsghsgJqq7IzMoA6j2QY/mW5goxl3z/vNOkHxBgzf715gMDM+JNHALv4G5U6ayW68KAGe rEVwIRp9aJng1FuYGsS3/FjkSSXpb0Oyxd3WW0vU3BS6bX1qvwA7EjNd/qJ2tgW9OTFlea6Jc J2lQxnp9uW7gltVxbacv+nJYH9rfjdSpB7rd7rSMnjqrPd9PQpzsIA7L35WN/DTeiKxvkMvyD /Ds6jI3i9f24Rlga1UgyJJqzyQdpCgh+yh//K0xvLT+9Yior2aOm8CgwVoD2Bt+jZ0f8m+VWf +bu1BGX/Xj6mBxf4jjAlO8vmrK2QjgdCo8iIQX/zswXNfuB7n3Vyr0YNOGbcW3Qa7hGY/FaCp X/Oxz/4MIE61e/Xd+mcNBYO7E6h+PkE6ffDlGspq22/BJmw4oNCg/fMwZQUITI7SpBotv+2I8 qMJmtOfEzqVzaPIYcYJPanrBkJ5eYZC6rad86/k7+gXs96Rdh8ro2bFn/Gkj+fzClltflks3p 1XMVxWxmAoVuAH+iXjKsR/k0EM/ZW6Si9rWJlPneABRoTPfxqkaeAy87qgYIvn0s77iRzZAOs gmgHDClmVu6a5m5+Swu81q4PwiGUCS0ZQSjdS3Yi4JIRXFdLE44UPSjqaoySDUCVCJSjWmjvB Tfq5i5m3lb2YLrgkmQ5feKEPc4L/zkxhExDCyM9Cmf6EEPNF199RezvkY2bxgucOpdKLjoY/X avTHSLhFRJK/gItAqKIv/mz1O+xtyMBsuCm4vZ7BgQ3EDliNxlF251qBoW89EgLibvBd0z8t+ ac4QJjAykzahiToI/oybGUTljR4MMVq7mIcJeq5hECK9bZHodh7wmVoapRFnvap+e065M7L05 RN7G0DDJPCcA16+NfP3PX3gkyiP5F2ktrWCHEu8cbGpk/0hKPR+LxOqEQ+ULIz46q8enhrUxk D3kaMF6qUrE0McmL1v3yiUmOlGk3TsHLBIh8W8F0ARN69/wmU52yrfwUA== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org llist_merge() has special inner loops for taking elements from either of the two lists to merge. That helps consistently preferring one over the other, for stability. Merge the loops, swap the lists when the other one has the next element for the result and keep track on which one to prefer on equality. This results in shorter code and object text: Before: __TEXT __DATA __OBJC others dec hex 412 0 0 3441 3853 f0d mergesort.o With this patch: __TEXT __DATA __OBJC others dec hex 352 0 0 3516 3868 f1c mergesort.o Performance doesn't get worse: Before: 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) Benchmark 1: t/helper/test-tool mergesort test Time (mean ± σ): 109.2 ms ± 0.2 ms [User: 107.5 ms, System: 1.1 ms] Range (min … max): 108.9 ms … 109.6 ms 27 runs 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) Benchmark 1: t/helper/test-tool mergesort test Time (mean ± σ): 108.4 ms ± 0.2 ms [User: 106.7 ms, System: 1.2 ms] Range (min … max): 108.0 ms … 108.8 ms 27 runs Signed-off-by: René Scharfe --- mergesort.c | 19 ++++++------------- 1 file changed, 6 insertions(+), 13 deletions(-) -- 2.37.1 diff --git a/mergesort.c b/mergesort.c index 92150c4101..6bda3a1c0e 100644 --- a/mergesort.c +++ b/mergesort.c @@ -8,10 +8,11 @@ static void *llist_merge(void *list, void *other, int (*compare_fn)(const void *, const void *)) { void *result = list, *tail; + int prefer_list = compare_fn(list, other) <= 0; - if (compare_fn(list, other) > 0) { + if (!prefer_list) { result = other; - goto other; + SWAP(list, other); } for (;;) { do { @@ -21,18 +22,10 @@ static void *llist_merge(void *list, void *other, set_next_fn(tail, other); return result; } - } while (compare_fn(list, other) <= 0); + } while (compare_fn(list, other) < prefer_list); 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); + prefer_list ^= 1; + SWAP(list, other); } } From patchwork Sat Jul 16 16:54:51 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: 12920194 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 AC8CDC433EF for ; Sat, 16 Jul 2022 16:54:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231613AbiGPQy7 (ORCPT ); Sat, 16 Jul 2022 12:54:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52058 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230448AbiGPQy6 (ORCPT ); Sat, 16 Jul 2022 12:54:58 -0400 Received: from mout.web.de (mout.web.de [212.227.15.3]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9C6DD1E3C7 for ; Sat, 16 Jul 2022 09:54:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990492; bh=gtW5zPZpV39jtq0lRx43ddxtGniFDkDAP4D1Ikv14+A=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=jCN+8tis788TdcoXiCQnqik8SOs4XhGa1p4t+ch+OCcGQ43LHOpCYSrZELIYHdqIO ZmPmNCXI29e3CsNzA6UdRZ33CKGSwNNrWi4Uom8iyeyk9qxsoh0AV8qeWUIEFmOBQX NdjBWuDaEb9aBrUd1l9WHZ1aqpVYzIfa1vg//NGI= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb006 [213.165.67.108]) with ESMTPSA (Nemesis) id 1MzTPQ-1nHNBU1BVg-00vCzY; Sat, 16 Jul 2022 18:54:52 +0200 Message-ID: Date: Sat, 16 Jul 2022 18:54:51 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 03/10] mergesort: add macros for typed sort of linked lists Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:CE2gmwz2kVEhSfnB9zpVwis4gHABdc2LeSYx3B/uAqQGUHR0vN7 YNUdaBUFDnBKlyL++lbBXvfCLiUx3ZvksaYpthvygNPDRwMfwRS4c3J87M+PeKaKwD4W4aj IQAprQhZrB/vErTFs6Tn52LLn4hlxdW4Sovuy+SHKqYqds+ARnNkMbfNdL0JYNJYaPqhebt PWCIY43VubsdS98oudR9w== X-UI-Out-Filterresults: notjunk:1;V03:K0:G+atJlCYoh8=:Z3VKxWUtFgawAqep70MzKy Uxqbq87vHG4egsm63pg8UuWY/s5NJOBeYUMx0d0scVF21Y7+87taWN8IMUYNlO1xhsXkcPl57 tIX8jG9VZrF6SuntzBVhNL87CJf97DnXAzpV72xHfWCim+I9QxAdFzqhaC0lCifwmiyk/pAKb XAlwdUXSYLVniaQvGRTKcKbGir4XWKUMgiMLOtQ62oTIDTOsrzxtmrzX4puModW8hRtZvdKS4 OPA2EGtFQ8Arqvbw8Z3oYJBoNXSd528EQ3xjskeIS+XdeYVIyg2C2kMLPV/yFEQn8o/Hjivln 0C9m7LL2WfYszDavlsQsE132WacRSPOaK2zLdYYHkmkXQhhlfSMYwvJc8W4sCG3ZG4Bbm6b7P BiSVVp/cJ8Gaf1cdTGwdGiLRxQ4h+1Mf/vF9eYNqFRRcPAokaASINCP+NhGq29Tbfankznuum mi+Vam/JiKiTUfUjFQFxHOMeaXrHpYvD4bzVuZxPfonTFQyXQjBEdn4AV2Yo5FKL4+NKjm4Ni 6Q4iJaTIbEO/FGwiIxgR3W3k+3Zmtagdmi180t7caqEVql6KQXFnwBe+PndUY7tpwNHxAHd+l 68Kf3vjxJG0m7t1dD+UBlbVbbkV+FDH2G30jzJbuurm/ssrYS+rFUajqCQSlSjk6RRO2nCf/R HLUuaaZpb/HIdkw/OCWCT8TdtMWVngA2fpNT7wbT5N9OkCPqtT4JtYraiAMeceJE7R/mwsc9F 8TuF47NRk/JQPdm68MVXSqzBH1nxvmeJFwo2jBZzcPQCiSI8e9h0SISkcHD6PT74BzOpLIejE xdNor0WuER1B/GbZbIGOqIL+y3GFlHA9wL1Y7TDB1qkWnbBqeugpg6VVsSEqOvhfa9VtJKN3N ihBE8ebzpzlPjCUxidlZmF2yjY3n0v2VudFHHPQhIP0J6UL493Ywcwf68yEHU/9IAF7+SmQ0d SZlzR109cIB7Rj4TscEpwJWggNkk9vEntpk7k6Fq1SpBIshcgtIQZzBg0OCY7XRRqW5s/4EBb bIFjv+o18QFpBmcfVaDkgpqTy+mGG3UjUsMsE15lH7AAOefNo0d2U2DK5JeG0yQT4XQU/KPPk M/QU/H9lqfK2jp9tF45fSNx50MUoBlFKzhv Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Add the macros DECLARE_LIST_SORT and DEFINE_LIST_SORT for building type-specific functions for sorting linked lists. The generated function expects a typed comparison function. The programmer provides full type information (no void pointers). This allows the compiler to check whether the comparison function matches the list type. It can also inline the "next" pointer accessor functions and even the comparison function to get rid of the calling overhead. Also provide a DECLARE_LIST_SORT_DEBUG macro that allows executing custom code whenever the accessor functions are used. It's intended to be used by test-mergesort, which counts these operations. Signed-off-by: René Scharfe --- mergesort.h | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 101 insertions(+) -- 2.37.1 diff --git a/mergesort.h b/mergesort.h index 644cff1f96..7b44355283 100644 --- a/mergesort.h +++ b/mergesort.h @@ -14,4 +14,105 @@ void *llist_mergesort(void *list, void (*set_next_fn)(void *, void *), int (*compare_fn)(const void *, const void *)); +/* Combine two sorted lists. Take from `list` on equality. */ +#define DEFINE_LIST_MERGE_INTERNAL(name, type) \ +static type *name##__merge(type *list, type *other, \ + int (*compare_fn)(const type *, const type *))\ +{ \ + type *result = list, *tail; \ + int prefer_list = compare_fn(list, other) <= 0; \ + \ + if (!prefer_list) { \ + result = other; \ + SWAP(list, other); \ + } \ + for (;;) { \ + do { \ + tail = list; \ + list = name##__get_next(list); \ + if (!list) { \ + name##__set_next(tail, other); \ + return result; \ + } \ + } while (compare_fn(list, other) < prefer_list); \ + name##__set_next(tail, other); \ + prefer_list ^= 1; \ + SWAP(list, other); \ + } \ +} + +/* + * 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. + */ +#define DEFINE_LIST_SORT_INTERNAL(scope, name, type) \ +scope void name(type **listp, \ + int (*compare_fn)(const type *, const type *)) \ +{ \ + type *list = *listp; \ + type *ranks[bitsizeof(type *)]; \ + size_t n = 0; \ + \ + if (!list) \ + return; \ + \ + for (;;) { \ + int i; \ + size_t m; \ + type *next = name##__get_next(list); \ + if (next) \ + name##__set_next(list, NULL); \ + for (i = 0, m = n;; i++, m >>= 1) { \ + if (m & 1) { \ + list = name##__merge(ranks[i], list, \ + compare_fn); \ + } else if (next) { \ + break; \ + } else if (!m) { \ + *listp = list; \ + return; \ + } \ + } \ + n++; \ + ranks[i] = list; \ + list = next; \ + } \ +} + +#define DECLARE_LIST_SORT(scope, name, type) \ +scope void name(type **listp, \ + int (*compare_fn)(const type *, const type *)) + +#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \ + on_get_next, on_set_next) \ + \ +static inline type *name##__get_next(const type *elem) \ +{ \ + on_get_next; \ + return elem->next_member; \ +} \ + \ +static inline void name##__set_next(type *elem, type *next) \ +{ \ + on_set_next; \ + elem->next_member = next; \ +} \ + \ +DEFINE_LIST_MERGE_INTERNAL(name, type) \ +DEFINE_LIST_SORT_INTERNAL(scope, name, type) \ +DECLARE_LIST_SORT(scope, name, type) + +#define DEFINE_LIST_SORT(scope, name, type, next_member) \ +DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0) + #endif From patchwork Sat Jul 16 16:56:32 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: 12920195 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 98DECC433EF for ; Sat, 16 Jul 2022 16:56:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231697AbiGPQ4i (ORCPT ); Sat, 16 Jul 2022 12:56:38 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52638 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230448AbiGPQ4h (ORCPT ); Sat, 16 Jul 2022 12:56:37 -0400 Received: from mout.web.de (mout.web.de [212.227.15.4]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 02F721EECB for ; Sat, 16 Jul 2022 09:56:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990592; bh=ZHs1iXbVbXaVw++047CRpV2JS/Why4c2OfaUdEZ4T+g=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=OznOkL+gRsoA3pNXiMzNu0clX5BWQ2TJtmnQ7IIT1vd22HFZkDzuy5rcf62zOWVVc leaGtEXl7XgqLQ5WSpydDV8trR5EGbnULnjHiXR08F0abOl4XEQJU7dKjXikurDXzQ c9luoKGvarYtmrkFcgjxBt7oizQYG/wmmZH+sNHY= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb006 [213.165.67.108]) with ESMTPSA (Nemesis) id 1MCGWc-1oKyZO1che-009cgG; Sat, 16 Jul 2022 18:56:32 +0200 Message-ID: Date: Sat, 16 Jul 2022 18:56:32 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 04/10] test-mergesort: use DEFINE_LIST_SORT_DEBUG Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:5zvVqOiGSj+I8UlajZWWsivRsEfT902OfOKVdeQapYx0KCV4uEh y+1FOg4lhF+74D9yDQip1yQvxu20Y3UMBeaBB//aYwz+XV4KntPT7r/ToarSVSCfHNo9UhE hQwJKxdw6zbssgr9cKFAWOy22dlyCLKn9YYBsqMuHMHeHYCFtLKHhsTQP+4urGvultK9ek3 j9JcVpHzlNkH395YCyMBw== X-UI-Out-Filterresults: notjunk:1;V03:K0:GBhaQeWRxzY=:rQix5elWVPriWcmuAr5n0x KP2N7jb/0T5LNLy4YIul1Gi9tm6JricW9NRdw0SKby0brm/u+gqNatxUqAzULOdJob11teZzU w+ai1sBEJf+J8lKXMG08fhKQCf2CV0zlhaH92EUgQ/CpMqj4zjxMtareyLIOlIyy0wqNxCTQo IW2k/BSUSXpOjH+HoeJn0KljujZsFe4nFZe9wRJQeKdbIPohTfFEuM7yum0i47+Z0JomDOqCy 6k9Q0TnjLb+ZUYGsfN3PwEhhuEnSZnoEhGtcLqtlw1G5XXlUBpENJz98vsuvh1BjnqoqkUSdd aRFA6Fcqpedjd/hqjssfplM+8g+i7J9duvOVJkyJ1tK1KVTEgR8RYMSWmvS3MRoulbivjxX8z MarDuv7dCvfXye/2pyXKZfgTKYFDoU31BoRFwVuy9xykTX41Z5+B00sZMXCaqjLvjHIBsHYUJ sZa0KQM1XVVOXcltjAjM121Kscan+PrFuPGeTfxEBpFN8N6PiRovF2Lq8lNiMUkd8mPwH+v8Y wm1NR3AJRsQNRfWQmvr0GdzBMAm61DAL1flfs/MXwX1JWyyM4ZzK4OSKB5iCPZPpRBLTp8bV5 fzHLUAVDWJQ/hy9U5impbw6Ugb1FkOs/h1GtocvFYF7y5W61SdDhITxbfhH7JjPqFMk7JYFdg 50XuK5qcst105ruDgnzmDRNDPA2wN9ZGF6GevYYG9U8ORp0MqTYEGRJ2LiZfgN20GcKEDCRXP qdzJY1jabfjeC6VPR8oITIdr6B1yhVjlnn4iyxAyD2kkGugJiC/SBXvUMYfzAgNZhx/jBDDrK /t2rHhiRAQ4mUyTQiRvh2H6GxOJvAoJ8B4cLdg9S6AeU+RMJPnqoQ0SB7BuHjPaMITb9Ny7QB FveIGjNKIFVTj8yOlNzSGtG6XexFsGXaJAtINuM+x9OI+8Q/P2gRLYf9NGbF+tRsurUtw57ap xmMgyUvjQbPuFG4w2OkD4ko14odOpPlZGzVQG07m1yMlbs867WscJPZRDYF/xvcwsC5+77yz4 UDoKTVNfsQtdHPUYfHgOCRrrpugoGsgzRTIbbhWIeqEXlsdTQEjUwkYf/LaL4An/j0J6lC9Y9 cL2zMdTpV6kN5VCRRm+sFZyf6nuyknjNAJ5osLNpzi/ZgKG9V6kh+qaJw== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Define a typed sort function using DEFINE_LIST_SORT_DEBUG for the mergesort sanity check instead of using llist_mergesort(). This gets rid of the next pointer accessor functions and improves the performance at the cost of slightly bigger object text. Before: Benchmark 1: t/helper/test-tool mergesort test Time (mean ± σ): 108.4 ms ± 0.2 ms [User: 106.7 ms, System: 1.2 ms] Range (min … max): 108.0 ms … 108.8 ms 27 runs __TEXT __DATA __OBJC others dec hex 6251 276 0 23172 29699 7403 t/helper/test-mergesort.o With this patch: Benchmark 1: t/helper/test-tool mergesort test Time (mean ± σ): 94.0 ms ± 0.2 ms [User: 92.4 ms, System: 1.1 ms] Range (min … max): 93.7 ms … 94.5 ms 31 runs __TEXT __DATA __OBJC others dec hex 6407 276 0 24701 31384 7a98 t/helper/test-mergesort.o Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 19 ++++--------------- t/t0071-sort.sh | 2 +- 2 files changed, 5 insertions(+), 16 deletions(-) -- 2.37.1 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index ebf68f7de8..93d15d59a1 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -273,21 +273,11 @@ struct number { 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; -} +DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next, + stats.get_next++, stats.set_next++); -static int compare_numbers(const void *av, const void *bv) +static int compare_numbers(const struct number *an, const struct number *bn) { - const struct number *an = av, *bn = bv; int a = an->value, b = bn->value; stats.compare++; return (a > b) - (a < b); @@ -325,8 +315,7 @@ static int test(const struct dist *dist, const struct mode *mode, int n, int m) *tail = NULL; stats.get_next = stats.set_next = stats.compare = 0; - list = llist_mergesort(list, get_next_number, set_next_number, - compare_numbers); + sort_numbers(&list, compare_numbers); QSORT(arr, n, compare_ints); for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) { diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh index 6f9a501c72..ba8ad1d1ca 100755 --- a/t/t0071-sort.sh +++ b/t/t0071-sort.sh @@ -5,7 +5,7 @@ test_description='verify sort functions' TEST_PASSES_SANITIZE_LEAK=true . ./test-lib.sh -test_expect_success 'llist_mergesort()' ' +test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' test-tool mergesort test ' From patchwork Sat Jul 16 16:57:18 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: 12920196 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 A6F87C43334 for ; Sat, 16 Jul 2022 16:57:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231738AbiGPQ5Z (ORCPT ); Sat, 16 Jul 2022 12:57:25 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52922 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229683AbiGPQ5Y (ORCPT ); Sat, 16 Jul 2022 12:57:24 -0400 Received: from mout.web.de (mout.web.de [212.227.15.3]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 47E231EEDD for ; Sat, 16 Jul 2022 09:57:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990639; bh=P0Ldh/u8BxpmuQnbuXD1I8hnP1si1Hm0NES5D0boh88=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=YlTawgs6Qc2SY9LTw7PzDghHnqkPQD7aCoHYSUkU75K+iYgA8ijWd5RdLT5q6V+Ys 3arXvmD9I8dXG/FqQf/fADRYo2BkgIOGf6ZUkDV6i7GvKhi79qkIL4QnSz3Px6HlbF kxRTvOj2Pkk6MPeVuUr+laBrLbHwekfK9eIYRFY4= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb006 [213.165.67.108]) with ESMTPSA (Nemesis) id 1Mpl0r-1nlMlX4C6v-00q4jO; Sat, 16 Jul 2022 18:57:19 +0200 Message-ID: <54b6a68e-9e2d-c3ec-d6d0-e5dd9a81d391@web.de> Date: Sat, 16 Jul 2022 18:57:18 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 05/10] test-mergesort: use DEFINE_LIST_SORT Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:YTQSZQAe/p4jr+Y7sfN0sooPLb1FTVE/DzXVZ17bzPcgQorfXSL XaAiAWyK9XuPqRuDUtBSBpvz69KU1/Bcgh+rQKaIKJZL2FiOownMvyRs5o+vbuUo/auH65v vTS6mA0hKa3yXDg9rmpVjoiWzBMyh0iZps00DN+cKtLu068hL1Fzpbx+pz0maC0bSPUs1Mq bn4jwkF7bfxLV67ofPiSg== X-UI-Out-Filterresults: notjunk:1;V03:K0:rwr/te9R23E=:dm1xb8MFODmBeEATQ/evNa cC4LMrve3X8/FPR548mdaG22cUy6IfxpSyi/NQrPqIhzH6IMBNDU+WXkmcqQdrtW6seoLJLq7 cUWjEG2BO0NNkzY3GZ7N6vswWFLPfKQ8dB0KkrGqKRPSGOv3i136LdJERQsOXefFqUvysqpkb qDbHMf2+KbBSdRyxmho/xhzoPedEPvx8dlVrMZ2uSDkUaKCaOEyzQTvPwHWTcZLzuHWu5aQzv PszpfPGRbVv4wya9TQcK3d2AUltWrNGLOx1aLfo6h12jyQjgcpjo1GP4/U2T913IO38Qjbegw eCFEGKzWFOW55zmiEkWgxlaZ441GT/P04abqd43M/kETc9M7oAPHwJ0yC3IVw7+cLJ2YhtXGZ rtuy3Cfjz+EVLnhLxV8VxiFIoiJSYa5vYtyBfejQAYIPOHeKKG2wYSyjrVXDLBvgHvHDPrGbL 78m96b9RT1LgV/V6hkck735eqwa4fqu8jp4nL5Gv6JPOU6tdYf/EjUeLQZ2VlgqgDpu4pCLa4 vFNIJxazZvAdodM33lxaVb5RFVeie3j9HCpcqQl44ZA3THthsl0Tdlvp8s9L3NewKfpEbZLUn 2q4xfdbS2/rXWpVpyflWYx+iKie6NGYNmVOYbfsHCOepjhVnJVwUMfS4KHquHWTRLCXuQLciB YIlRDA/vGtRgHuczjcQhlGNfmC9CFA0iHJ6jPgFys49eptKW1UldZ6txbpj21mHidQLiXJX7n Yms3A9cVEM0Z+3aGiumLPzu/H/RAOsqw3WI0E66PAJJLKCYu8Bg57bN5gSMNIuviN9aODQ82f 4UY0zXa7xBpaBtGigfSI8KshIrIA8HZPnoo2H5NYr9ewbmUcgJFehBjqEuO3LFbxVjLkcqewa 8YFjRE7yiFot8kzCfvrn4ksEoRXHwA6cKEYYznCFfiY951OBJM8GE+geJOsjI4tXn6nXeX2fw PZh85ts6lLOlfcW2ap8vu4XT9DkhCReDMPfP0TpwVheGh9wbjUkklZvZFBa0BXdYjQRgywmli Hbkznf3aG0gK90/yzC0b6tL3Txuv0Vztne+mzbh4gB0nSg7HtXGT1a/DvSsaPSFC6u3AI2RiD GJxHt/tqfxeLdessIHywYrz/f6TQomDuLhpjEmo2RC09pxoWdRdHDPzYQ== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Build a typed sort function for the mergesort performance test tool using DEFINE_LIST_SORT instead of calling llist_mergesort(). This gets rid of the next pointer accessor functions and improves the performance at the cost of a slightly higher object text size. Before: 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) __TEXT __DATA __OBJC others dec hex 6407 276 0 24701 31384 7a98 t/helper/test-mergesort.o With this patch: 0071.12: DEFINE_LIST_SORT unsorted 0.22(0.21+0.01) 0071.14: DEFINE_LIST_SORT sorted 0.11(0.10+0.01) 0071.16: DEFINE_LIST_SORT reversed 0.11(0.10+0.01) __TEXT __DATA __OBJC others dec hex 6615 276 0 25832 32723 7fd3 t/helper/test-mergesort.o Signed-off-by: René Scharfe --- t/helper/test-mergesort.c | 15 +++------------ t/perf/p0071-sort.sh | 4 ++-- 2 files changed, 5 insertions(+), 14 deletions(-) -- 2.37.1 diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index 93d15d59a1..202e54a7ff 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -13,19 +13,10 @@ struct line { struct line *next; }; -static void *get_next(const void *a) -{ - return ((const struct line *)a)->next; -} - -static void set_next(void *a, void *b) -{ - ((struct line *)a)->next = b; -} +DEFINE_LIST_SORT(static, sort_lines, struct line, next); -static int compare_strings(const void *a, const void *b) +static int compare_strings(const struct line *x, const struct line *y) { - const struct line *x = a, *y = b; return strcmp(x->text, y->text); } @@ -47,7 +38,7 @@ static int sort_stdin(void) p = line; } - lines = llist_mergesort(lines, get_next, set_next, compare_strings); + sort_lines(&lines, compare_strings); while (lines) { puts(lines->text); diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh index ed366e2e12..ae4ddac864 100755 --- a/t/perf/p0071-sort.sh +++ b/t/perf/p0071-sort.sh @@ -40,11 +40,11 @@ done for file in unsorted sorted reversed do - test_perf "llist_mergesort() $file" " + test_perf "DEFINE_LIST_SORT $file" " test-tool mergesort sort <$file >actual " - test_expect_success "llist_mergesort() $file sorts like sort(1)" " + test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" " test_cmp_bin sorted actual " done From patchwork Sat Jul 16 16:58:20 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: 12920205 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 7316BC43334 for ; Sat, 16 Jul 2022 16:58:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231883AbiGPQ60 (ORCPT ); Sat, 16 Jul 2022 12:58:26 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53604 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229821AbiGPQ6Z (ORCPT ); Sat, 16 Jul 2022 12:58:25 -0400 Received: from mout.web.de (mout.web.de [212.227.15.4]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A980B1EEFF for ; Sat, 16 Jul 2022 09:58:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990701; bh=YDfkxxYE6PZhiH5TAOTdSYIijUTWHjzAFeXWclhw4JQ=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=rkgwH0GZR6V8xI8pjrqRogQkdjrWSHTgqSimudzjBtvv0a9gW0WUKb1hbdp4pgmQx m/S31VVg+ZHg8OCUV4T1mFyQrgRQ68tGAknCfuizO4wXYj762Q8Y/JaFirMwQkFc01 e6UqB8IqV5DARuUFFccRLJyrF53KmvkLpwBhHmFs= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb006 [213.165.67.108]) with ESMTPSA (Nemesis) id 1MN6BN-1nwSmu1WWD-00J905; Sat, 16 Jul 2022 18:58:21 +0200 Message-ID: <11f185bd-0117-7f1f-c97c-19cfb0de1384@web.de> Date: Sat, 16 Jul 2022 18:58:20 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 06/10] blame: use DEFINE_LIST_SORT Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:XY1IRe4wQi/JGm6AxE3Fm9ntGUGreRMTKtFBhL6l3Ka+BZ4CQpK YoaM57nE8tPy4hc9fKEWFRG8GQhaeChCA3fnfkopX24OcmicdG6hDvljEPtzBozPNeaTL/J CtjxRO5suBhrdUrrWTgCAU/EhsW9YLVR8VD8COFH6JYZQISp+KuCH9fRlf7+2Q7ETBmm9u2 wQTDGNArx43nq/YA5OBCw== X-UI-Out-Filterresults: notjunk:1;V03:K0:La4eu1O1mcI=:jbr88lfGNusRa0O6eSx7j/ vD6CkUAU9Pic7nIY3XrP23/uXg+/KwfujIghCvF34KMhcKKGjYbvJQD9cjjgNmHmMIi95EliL vGMknrnh8FG92YnTGTEG4ne0EeiunIUg2zem45zTagZRhiSxGmVjV5n+DUTrDFUsyZdXBR0bL u/TkTwfui163DExgZjVjDXiILkLklpwLQupPuArp0k3Z/2WARFvF29RCDKODY5XfESKABX7Af 4Ecmc2gJI9X3ZmwCnAMLF/Cb1sZDVJRrTD9Dpy5Gkj/ct2JkPacfFfmRf59H1AUA1kTNQ7Oj/ x910exIU5vzdt/CoHVigWj+BZ2YZo6PBtDTdRI+TGvvKS2lpZ+qHu2XSbEQzRSahmySZhtvPO 2z6AdY1638QZHlJoT0JFNDzlPl4WAeIRflhflVAnxtmZwC44dTUp9mOceF8WSqs3Q0jFE2BMH nMIWWhT318lOHp55R6v27VCLIm+m/oxXxxeHXN+zAqFWizMW9yL8i1CezQPfT2KKcC0TG8UAF +KFomg9G2OG1s3HIWA/veY2iw9osWlGcEw3327schmFeoF/sE3tz1WXttcrgyKhYvSIzi8uoq 2mT74jB2PL4qYcSF+Mt0BBZJMmcNjMrMrquqebhicLofQtcDw7bwo2ZOi506bmy5ONthBRDlF Kz7bTH6WWfllueZlYMzDY0K5JM69pllK8vt3rYKc4cRZXWPK9YU2xOAXGs27spDbhfZSApX9p EH+LF9pLqDGopmQHseDaATMKs4F92F4JDiy6cMIycYr9jRftKDnjI6ulC/OoVlbOZkKplpX1l QCvtYurkxixJuxALAl5/iSqGRav27gMMiz3zHfXuWA98kjsNT6V/DZcYTd7436R4AIGKyTogU lC6voWOwJRDwlJbuHuJDGUbusuT+68G0lRC7NUuXGRYo8ngCW7SXVCQ7wnWJcpl5hB/OVJsLh O/VlamUPJZIBTodQKX81l2nm0/wj8IAxyxEcomoSNkRMICz9iTdIIs6dbPY+M6VqH1lTUqDF0 EkEp8/oeQN/6TGySbcE/xYNF1luJ+HXEeNOKhdpiMkokJzKRSx7h189VnFvohFM+j++oN5Fmv WLWivD+O1Tu3y2OZjLnduYQmeXFDTRYXtk60Qx9z4RRoPjr6WrDqEY0Cg== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Build a typed sort function for blame entries using DEFINE_LIST_SORT instead of calling llist_mergesort(). This gets rid of the next pointer accessor functions and their calling overhead at the cost of a slightly increased object text size. Before: __TEXT __DATA __OBJC others dec hex 24621 56 0 147515 172192 2a0a0 blame.o With this patch: __TEXT __DATA __OBJC others dec hex 25229 56 0 151702 176987 2b35b blame.o Signed-off-by: René Scharfe --- blame.c | 30 +++++++++--------------------- 1 file changed, 9 insertions(+), 21 deletions(-) -- 2.37.1 diff --git a/blame.c b/blame.c index da1052ac94..8bfeaa1c63 100644 --- a/blame.c +++ b/blame.c @@ -1098,30 +1098,22 @@ static struct blame_entry *blame_merge(struct blame_entry *list1, } } -static void *get_next_blame(const void *p) -{ - return ((struct blame_entry *)p)->next; -} - -static void set_next_blame(void *p1, void *p2) -{ - ((struct blame_entry *)p1)->next = p2; -} +DEFINE_LIST_SORT(static, sort_blame_entries, struct blame_entry, next); /* * Final image line numbers are all different, so we don't need a * three-way comparison here. */ -static int compare_blame_final(const void *p1, const void *p2) +static int compare_blame_final(const struct blame_entry *e1, + const struct blame_entry *e2) { - return ((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno - ? 1 : -1; + return e1->lno > e2->lno ? 1 : -1; } -static int compare_blame_suspect(const void *p1, const void *p2) +static int compare_blame_suspect(const struct blame_entry *s1, + const struct blame_entry *s2) { - const struct blame_entry *s1 = p1, *s2 = p2; /* * to allow for collating suspects, we sort according to the * respective pointer value as the primary sorting criterion. @@ -1138,8 +1130,7 @@ static int compare_blame_suspect(const void *p1, const void *p2) void blame_sort_final(struct blame_scoreboard *sb) { - sb->ent = llist_mergesort(sb->ent, get_next_blame, set_next_blame, - compare_blame_final); + sort_blame_entries(&sb->ent, compare_blame_final); } static int compare_commits_by_reverse_commit_date(const void *a, @@ -1964,9 +1955,7 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb, parent, target, 0); *d.dstq = NULL; if (ignore_diffs) - newdest = llist_mergesort(newdest, get_next_blame, - set_next_blame, - compare_blame_suspect); + sort_blame_entries(&newdest, compare_blame_suspect); queue_blames(sb, parent, newdest); return; @@ -2383,8 +2372,7 @@ static int num_scapegoats(struct rev_info *revs, struct commit *commit, int reve */ static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *blamed) { - blamed = llist_mergesort(blamed, get_next_blame, set_next_blame, - compare_blame_suspect); + sort_blame_entries(&blamed, compare_blame_suspect); while (blamed) { struct blame_origin *porigin = blamed->suspect; From patchwork Sat Jul 16 16:59: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: 12920206 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 8E7ABC433EF for ; Sat, 16 Jul 2022 16:59:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231896AbiGPQ7L (ORCPT ); Sat, 16 Jul 2022 12:59:11 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54478 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229821AbiGPQ7K (ORCPT ); Sat, 16 Jul 2022 12:59:10 -0400 Received: from mout.web.de (mout.web.de [212.227.15.4]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0AD21D11A for ; Sat, 16 Jul 2022 09:59:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990745; bh=ryiAVfB/Kx7xMQB2asycsKme0OLkizPNC8z6/stXibM=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=VRx64lr3k8+3BWkCySkqbfCBCmJ4w1jjC9Pjuthk3CUp36jiKOZE1F1JKF7IfHsol Ry7fUPSEsF1WwERxzBUFFJlCshR3APtFII9Yr1L6tApBnp5zpnjMldLIe0xCFhc+eX OsUKXY6TZjxmAP6ErQZ7Dp2PCA8eq4Y+P7wxbmlQ= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb005 [213.165.67.108]) with ESMTPSA (Nemesis) id 1Ma0PY-1o0ZNF2tuO-00WAhL; Sat, 16 Jul 2022 18:59:05 +0200 Message-ID: <396b927e-5bbd-1b7d-669e-8e22740b5295@web.de> Date: Sat, 16 Jul 2022 18:59:05 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 07/10] commit: use DEFINE_LIST_SORT Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:pMfAzpF4gVnD7DxVtK0mXlZXiaiwgxyj4CxP8VzJpRIJLXHHGti KcmMAdpmArdDD0rPdZsFkQ1476oUXf9Uv1UK4SL9a2Rxwu/VRH+qB6OMPvzGNNe+lFUSV8K GFZms8ytTGHIkfRnQqAKt8KVJ8NczxcjA7uaLeBrJRRWlqEHoSczbRAsx7NQTkjlsvY83iC bfec7mjThSnzBWcZJyKvQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:M4PZw6H3/k0=:wvV+l8c3yvVRx6llHVS5TM izFYFRuFbbh5Wyoekhcu3l0MGjo0WBhUAV6zkOotl1X2dIYtTCWg6158EbF3AZ0jd7CVJeVgN t2JFhkDOk54UwPVIvtWDiMQvy0ALqGRz7+e8uutdmR9oPdK9W+m5zwA6bQ9R19ek6AzZStNVm UilqwEvBJfNXt21VfDUckh7M4laRIVp0xi6o6MuvPqLWkUk/YLGkFBlTPhlMinMVsVm4iJlAt m+dboJ1mGkxF5hIoVDkLggbCwKH2HVYDQDcb7ok+j9RgXwqHqkbuJyi7IvnBcTQ9MiHaLpusL RzUuxqsjoVuzNE5zhsrcy0LbkRsH3UT19IkyPAsuGdL4pOqN7TBecYPGvr59a788dpo/lP/As 5wcX7dGTnmt3rlgf/90xhmz/nt50QkZMnljpARQiThWjVIuT5twtYnwXyfI3rg5tREmQdxvW5 bYNhoRYrouk6l6pKZUAVVzViCUcgiHwcLJqN96WROgjT33q0PgeGQxp+p0Zl7XY8Ggl+4et5e bOgIB6+qqxWqOEZDyN77MQrjZRvov0npqVl/Ua1Y5VktD2Mes8CC8059173qud7ryfGjS3jpq LkGrXAbGeCu1gkYR5Bb0DBLulStEFCPNCvcZGPZtzvZiiZXcCgUfsK2FIIrn++qjrlpbi8MDV I00j3lSrlt/x5FyjrVl7YrKeU6LH0oTsCTMeRhPpcLIZQQAC+Jz6Pvb7ZTEH8deL5pHVM771Y 7UmoEXzyd6RyGTi4oKCAUjI0wp0lpoeEXhhX63VgnF/5oLUHuLt6SiMUZRUdCMbXF8bdDA4aO k31LDffF/UiQbk5hM4OPoQPOMuSBto+Lq5554REaEv898TC7M0ey51kVAmuC/q4ClMKrtTQTS APCY8jyOUA36TH+tOGumnrjJvsoCIdwYFA50g3Bbavbt4dOImMxjyz9eCHrA5OP8NoUpYDqxc IMAqj5l6McFVFvATKw9OyOCbMlAgQ5PI1Db+rEMwELYlsHkfJriITplvjLhUzDMweo11AijwZ yEHzn2Jvn45O1DXeI9B+ZgZSZZNXQj5BWKLuiIz4tVxxvVh38zu6VLNn3cFjBsEBu3QenqaqC RcXuCMRfpphQ1YunxooPxEM9l/dJ3XxRtLQIy6BcInc4egztvc/NYlRIQ== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Use DEFINE_LIST_SORT to build a typed sort function for commit_list entries instead of calling llist_mergesort(). This gets rid of the next pointer accessor functions and their calling overhead at the cost of a slightly increased object text size. Before: __TEXT __DATA __OBJC others dec hex 18795 92 0 104654 123541 1e295 commit.o With this patch: __TEXT __DATA __OBJC others dec hex 18963 92 0 106094 125149 1e8dd commit.o Signed-off-by: René Scharfe --- commit.c | 20 ++++++-------------- 1 file changed, 6 insertions(+), 14 deletions(-) -- 2.37.1 diff --git a/commit.c b/commit.c index 1fb1b2ea90..0db461f973 100644 --- a/commit.c +++ b/commit.c @@ -642,10 +642,11 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm return commit_list_insert(item, pp); } -static int commit_list_compare_by_date(const void *a, const void *b) +static int commit_list_compare_by_date(const struct commit_list *a, + const struct commit_list *b) { - timestamp_t a_date = ((const struct commit_list *)a)->item->date; - timestamp_t b_date = ((const struct commit_list *)b)->item->date; + timestamp_t a_date = a->item->date; + timestamp_t b_date = b->item->date; if (a_date < b_date) return 1; if (a_date > b_date) @@ -653,20 +654,11 @@ static int commit_list_compare_by_date(const void *a, const void *b) return 0; } -static void *commit_list_get_next(const void *a) -{ - return ((const struct commit_list *)a)->next; -} - -static void commit_list_set_next(void *a, void *next) -{ - ((struct commit_list *)a)->next = next; -} +DEFINE_LIST_SORT(static, commit_list_sort, struct commit_list, next); void commit_list_sort_by_date(struct commit_list **list) { - *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next, - commit_list_compare_by_date); + commit_list_sort(list, commit_list_compare_by_date); } struct commit *pop_most_recent_commit(struct commit_list **list, From patchwork Sat Jul 16 16:59:59 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: 12920207 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 513C3C433EF for ; Sat, 16 Jul 2022 17:00:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231903AbiGPRAK (ORCPT ); Sat, 16 Jul 2022 13:00:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54914 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229821AbiGPRAK (ORCPT ); Sat, 16 Jul 2022 13:00:10 -0400 Received: from mout.web.de (mout.web.de [212.227.15.3]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1EF5D1F609 for ; Sat, 16 Jul 2022 10:00:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990800; bh=5N9DghwnJ7g7FzOLCtIxw1O4NxjWPkP5czoq8DwncWE=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=V1ZzmUji/OMPtlaokrxh/qmFS3AUp9j20LWhRswvsNxjelzN4FQ0tT04SQecfSV3M zI2eJxA86HsAVI6l+/im6X/s8n8lyJ/Q1KcXwAOCgM0ThXxHQ4eUna7Q3UqJlOXuCA skAK75ZqTPlRg2eQ/RO66K9UyHQVbRBCZ/m8tpq4= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb005 [213.165.67.108]) with ESMTPSA (Nemesis) id 1MUlDJ-1o48KP03ov-00QvFU; Sat, 16 Jul 2022 19:00:00 +0200 Message-ID: Date: Sat, 16 Jul 2022 18:59:59 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 08/10] fetch-pack: use DEFINE_LIST_SORT Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:P9eEwJkC+r1dtoT+JFbrAx4rtYT4dIkhhwo1d1oyOXwiNDcXujN UmThJAQey+gTq9Sf/svHEirtfGvxU8y6ltbFPTONmZXZdM6PDhkrNGxwSmVdOC1MY5Lo2ko CwQf2iYFpNdmudRqQiRhv+t6yNUPD3/dLOdzwd52knhWATa3log40JZXwI8/Q3smIhZLLhu bXhfitu83JGc1goamtiNQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:QI9FNULLqaQ=:TYUlQom5dZu+hubP+cENXc /AZQGM5WuHVmDePEG4blKjoGjcjutQVi7iZ0GdUF6RbzNHJjQRYq6xX4+arpWG1kpxA6a4w6W jThyc5vvV1InJd50f8K2OvPHvfPr0HL88W9+BD9xY8S5BdK7a2DJteT5Va45ixoPKQFztXUdp pRZqQtOopKmfqmCRbTTMv9vp5II3ea7r2VQdnQt/M3/0Z+rJbQjIMIZEbkitdUHCPAEreklr9 kNZh7xiPq2t1UG2Utc7WugrZE0SwI/iqNQNiv7ocf6rCwWd2fHr2L2lUwMKAKh59fNQ7Qau/O uSMidm8SnPon9Kzx9C9jlvdoum/XBge6MjISQFPUEKuDaItKlje4VLJOneaogZBGBERjkUGkP JKpPdH0Nxp5FFzQyjH6TxkHHwPvg4/lBD/PVVuS8FVhl6liNjjT5Fz9+BTRpGGwC4/FmExWhn 2VaiJDCmx5WeOPGK1CYzmEJj5mOxIc9oivLWxmSmhk7GAXOwHeFWk3e0D1l5ni0d7JaVPilfb CtpdveXG/16kKSpS/dZ9pu3GmT+3a8eVWOmK4S+8OJlAuanBOJJTsh4eWVSL8lNXDSDciE/hJ N3TiWbVMxrOISwPBox1aVDh0f5ZXu9fY/979Tjj4hk2Ht/n5u1Wis/m60Zp2AIu4JFPjoC0Lh eby2Jf2qHOFFX/QqSSx2Yjtl8rKbw93GJ6rA5lbeQeuTYJniZSifBLyqqn9EN8CxOyc9PIhyX /2F8hhBwx85P02hB5UIlhWDnRw+iI4h+aPxMfvvAoqBKp60ANeRJlz3PEvHwA7Tj0Nug9HCM1 Gub5NWYCyc6hCAQU8B605WVSDxqD0adTYXs4EQmQTDzrLokWmXWU4ZFKVFVFGXvDwMWVMs1vj bBlFcw1fvq7AnAsSCECGRpz/bBSh16ZwTNT3GXTUAOShjD7xmkb8pR9xHPPpQRJkiUJSoukEM /754MnvRTIOyk9++6s0+0EM2Qt/1WXUpeNxoSiUKlDr7s7x2lYBa6cX67+ll1c4jtrMVfR8uU mv7l2jOy5dPv+DPuDL8tGXVYvPAM3aaFABYUM+SaHMtRxH1h+hnjlmTk2eDTustoeSK0hPU0g KncMuQQxg9ysIwUnqlTNfFekvcWy9yJlr89LAeCHUGDqYTeF6puwrS2MQ== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Build a static typed ref sorting function using DEFINE_LIST_SORT along with a typed comparison function near its only two callers instead of having an exported version that calls llist_mergesort(). This gets rid of the next pointer accessor functions and their calling overhead at the cost of a slightly increased object text size. Before: __TEXT __DATA __OBJC others dec hex 23231 389 0 113689 137309 2185d fetch-pack.o 29158 80 0 146864 176102 2afe6 remote.o With this patch: __TEXT __DATA __OBJC others dec hex 23591 389 0 117759 141739 229ab fetch-pack.o 29070 80 0 145718 174868 2ab14 remote.o Signed-off-by: René Scharfe --- fetch-pack.c | 8 ++++++++ remote.c | 22 ---------------------- remote.h | 2 -- 3 files changed, 8 insertions(+), 24 deletions(-) -- 2.37.1 diff --git a/fetch-pack.c b/fetch-pack.c index cb6647d657..e4503774b5 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -26,6 +26,7 @@ #include "commit-reach.h" #include "commit-graph.h" #include "sigchain.h" +#include "mergesort.h" static int transfer_unpack_limit = -1; static int fetch_unpack_limit = -1; @@ -1025,6 +1026,13 @@ static int get_pack(struct fetch_pack_args *args, return 0; } +static int ref_compare_name(const struct ref *a, const struct ref *b) +{ + return strcmp(a->name, b->name); +} + +DEFINE_LIST_SORT(static, sort_ref_list, struct ref, next); + static int cmp_ref_by_name(const void *a_, const void *b_) { const struct ref *a = *((const struct ref **)a_); diff --git a/remote.c b/remote.c index 1ee2b145d0..e90dca1d56 100644 --- a/remote.c +++ b/remote.c @@ -11,7 +11,6 @@ #include "dir.h" #include "tag.h" #include "string-list.h" -#include "mergesort.h" #include "strvec.h" #include "commit-reach.h" #include "advice.h" @@ -1082,27 +1081,6 @@ void free_refs(struct ref *ref) } } -int ref_compare_name(const void *va, const void *vb) -{ - const struct ref *a = va, *b = vb; - return strcmp(a->name, b->name); -} - -static void *ref_list_get_next(const void *a) -{ - return ((const struct ref *)a)->next; -} - -static void ref_list_set_next(void *a, void *next) -{ - ((struct ref *)a)->next = next; -} - -void sort_ref_list(struct ref **l, int (*cmp)(const void *, const void *)) -{ - *l = llist_mergesort(*l, ref_list_get_next, ref_list_set_next, cmp); -} - int count_refspec_match(const char *pattern, struct ref *refs, struct ref **matched_ref) diff --git a/remote.h b/remote.h index 448675e112..1c4621b414 100644 --- a/remote.h +++ b/remote.h @@ -207,9 +207,7 @@ struct ref *find_ref_by_name(const struct ref *list, const char *name); struct ref *alloc_ref(const char *name); struct ref *copy_ref(const struct ref *ref); struct ref *copy_ref_list(const struct ref *ref); -void sort_ref_list(struct ref **, int (*cmp)(const void *, const void *)); int count_refspec_match(const char *, struct ref *refs, struct ref **matched_ref); -int ref_compare_name(const void *, const void *); int check_ref_type(const struct ref *ref, int flags); From patchwork Sat Jul 16 17:01:18 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: 12920208 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 82716C433EF for ; Sat, 16 Jul 2022 17:01:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232235AbiGPRBc (ORCPT ); Sat, 16 Jul 2022 13:01:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56652 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232217AbiGPRBY (ORCPT ); Sat, 16 Jul 2022 13:01:24 -0400 Received: from mout.web.de (mout.web.de [212.227.15.4]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B76B220192 for ; Sat, 16 Jul 2022 10:01:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990878; bh=2PBc5Mm97PDs6p4eVbaOqO0otjiRK9R0XgecFLIufvI=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=hJtA1IYBG+a0BKjk2ggwpdvKR9JyM+7cx9pY5unrFmU1jJwWzSFCC5l/KSphJm+IX zcUU5APuzNMTIHaVDYPYYjhUDXkZqwo7SEs8SDP1HE2L7/pGl1NbGhZUmkQJGMuirq JMnCR+BXGtfhCU6b/xR/OmiVp1LXAc3W7yhOYbCU= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb005 [213.165.67.108]) with ESMTPSA (Nemesis) id 1MJFhX-1nx0Uv2Fbf-00KpWv; Sat, 16 Jul 2022 19:01:18 +0200 Message-ID: Date: Sat, 16 Jul 2022 19:01:18 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 09/10] packfile: use DEFINE_LIST_SORT Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:c3b2zSJwD/w/2vIdfS3w53gkzn2VK8cVhNJ6gk7G04TE5UX0zzL kO0VroPiZdd+kwdVn8ak7UTOSWkOMMPDE+3KUH++7SYARvc53RhFEX5obDlG8iM9bae46L6 pIq/np0IL9pnR0uPAO6+wvINR8pAMCZwn58TWpLHYvthLwgdtTFQ9XsXbgKeEVPbcgTUoZy tqwLVVQf/3PAS5htSU0qQ== X-UI-Out-Filterresults: notjunk:1;V03:K0:tIIJFPm8NBg=:84BKTMxaiErJRcCNowDuoE bOQ2xg0M4/K9b4d/H86gID3iMnUvmSC5fhfwZNnZ42lnfWSjM32VEa3qSMaCoK2rm02ktyagt tyAYDfMbgXBDoEuWAjRp2PU+iaxiXH6G3Gq7IDCqd0hHOotmNO5CUFKSQOiAgufzrukknbF3w HHbGpgLPXaUejwOk56/E+eG6cRZV0PSUvhCRQGQB5DOF3g8It89nu4iPbRKBHOOcoYIyCdtnz E3X58LroEpuvhxLMuooOlqRMMZSxddjR6bDzUT6fsBOqR6kjabkw8oJ8ud/U2eRROmdAcA+z0 5T+sb/FsuMRx0goAuF+y7v3T5pqY76nD8t2avFvV4pSGMc+2g+fv213Ey4lnxq1X8Er1VxoqD U4+lEi1cq7FPkrG8FE3WSCycL6UA/Oxgrcw1iq2MBZnyhM1ym5UV0osTGvqWUulR2XBgLyOrp jzR1Q8s8UNJj545fQXjolbVjUvVV2wi4YrqI1FUPwT5+/Xjjk3YIIT41vsYJQsV2nGZ55JrSf sFC9bfkbY5EcaI7YubaVnkl9gm5M8/gtKvpEJcOZeap7PMDCw20LN70lhIsVki1/NsFc7wQv0 o1r433vMFzotLK9VFsh1kGX9QQx5X1CEBIfaCHUk4nufEqRp8eUWg2Dov3By4lAbEK/U+H7iA bZrS/RVHObFUm6UoQ2IVKjuOXBmgfcPK52p+mMUiIliCL34GbTohM+jzW5i4f1fNSJe26k3nH M1p6hHWYHHif85zrwCiX9HVQhQOfwUl55Iq/5r9EhoW6wQ7bhgGNlGrd5tOzRLM6agNQUoyRt TKl2/yA0+YEDcNxl+E8Z5awNZwOV34LcDv7+Tw70v315O8l4gy9kxp2lp6jlpTsOBF3HTn1yK +ipDWaB1zq24ljKwNT7erWYh8nC2brXh5/F+tEXS4WKWpcj7W096kNyBsWnTvxs5MYoOCaQyv nj4GXbS/hQjiMpC0N0NGATbn0Mtst113go75JO595E01I01Gk6GFUoEg7HDfVT9HDIYntIxUN ElRUsZxD1ya+p67QPcCY0QopgZfW5yVbakgP0BXwjUaLiCQD9IjgmItWl8lbjHysNPBnRD/pQ s5LZ3WtXnBIE6jz2xlKW8/9TmR363YLVMHESmAZv3dzG//3H/+L3O/wHg== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Build a typed sort function for packed_git lists using DEFINE_LIST_SORT instead of calling llist_mergesort(). This gets rid of the next pointer accessor functions and their calling overhead at the cost of slightly increased object text size. Before: __TEXT __DATA __OBJC others dec hex 20218 320 0 110936 131474 20192 packfile.o With this patch: __TEXT __DATA __OBJC others dec hex 20430 320 0 112619 133369 208f9 packfile.o Signed-off-by: René Scharfe --- packfile.c | 18 +++--------------- 1 file changed, 3 insertions(+), 15 deletions(-) -- 2.37.1 diff --git a/packfile.c b/packfile.c index ed69fe457b..6b0eb9048e 100644 --- a/packfile.c +++ b/packfile.c @@ -941,20 +941,10 @@ unsigned long repo_approximate_object_count(struct repository *r) return r->objects->approximate_object_count; } -static void *get_next_packed_git(const void *p) -{ - return ((const struct packed_git *)p)->next; -} - -static void set_next_packed_git(void *p, void *next) -{ - ((struct packed_git *)p)->next = next; -} +DEFINE_LIST_SORT(static, sort_packs, struct packed_git, next); -static int sort_pack(const void *a_, const void *b_) +static int sort_pack(const struct packed_git *a, const struct packed_git *b) { - const struct packed_git *a = a_; - const struct packed_git *b = b_; int st; /* @@ -981,9 +971,7 @@ static int sort_pack(const void *a_, const void *b_) static void rearrange_packed_git(struct repository *r) { - r->objects->packed_git = llist_mergesort( - r->objects->packed_git, get_next_packed_git, - set_next_packed_git, sort_pack); + sort_packs(&r->objects->packed_git, sort_pack); } static void prepare_packed_git_mru(struct repository *r) From patchwork Sat Jul 16 17:02:38 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: 12920209 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 894D6C433EF for ; Sat, 16 Jul 2022 17:02:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229802AbiGPRCr (ORCPT ); Sat, 16 Jul 2022 13:02:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58940 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229648AbiGPRCq (ORCPT ); Sat, 16 Jul 2022 13:02:46 -0400 Received: from mout.web.de (mout.web.de [212.227.15.14]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 279951F62E for ; Sat, 16 Jul 2022 10:02:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1657990958; bh=buZGKpC0RpNv9sOGu9nmHwy8/TYE97mnrVNiOTjp/S4=; h=X-UI-Sender-Class:Date:Subject:From:To:Cc:References:In-Reply-To; b=SPXH9wtgVF2N4POx45Ovj3bzrwBIyRt20GEheOc0TBuVUlN5Vqn9KAAaXw8emsRLE 0qjRpVhGz+Hbgjal0COZK4nObsW1ouk9joRo7g1aSl4bYn3QpyB6vH1vwzWTaXE0IZ a5qFrQ5mi869H4//iMpj9k21T+KJn+C/Wf0oNP18= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Received: from [192.168.178.29] ([79.203.19.130]) by smtp.web.de (mrweb005 [213.165.67.108]) with ESMTPSA (Nemesis) id 1Mx0N5-1nJHxF2ikN-00yJ8L; Sat, 16 Jul 2022 19:02:38 +0200 Message-ID: <2fd427e6-2f3c-66d1-bcc5-6bb1e0f59f08@web.de> Date: Sat, 16 Jul 2022 19:02:38 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.0.2 Subject: [PATCH 10/10] mergesort: remove llist_mergesort() Content-Language: en-US From: =?utf-8?q?Ren=C3=A9_Scharfe?= To: Git List Cc: Junio C Hamano References: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> In-Reply-To: <4d7cd286-398e-215c-f2bd-aa7e8207be4f@web.de> X-Provags-ID: V03:K1:n6Zaf3h+uHXPe6GyZwxNh2pxegFOKkL1TKnsc43Tzzu29CMT53L +9s7v+hxLYuXWXzEF9BeKhJcyq82ih+tFiapi1NgIy5Vs5Vy2bCklXWgh6Ek9mQsKIWeU3z anvbWqWp4HsPbcEOVGi9rIoZMajHBfxacC7frdhJDBRM2tXwfB3oW9Tu0SH/n4vc12b9Hl5 vHc3dLjfIqLdOIGDxArBA== X-UI-Out-Filterresults: notjunk:1;V03:K0:bHZ9ifs8JIQ=:rQ4q6jxVIlQmZZTK02FS8d TQqzgzceUZOkmOL1JgYJVoSNf356U5qya9mdatEuhghW8E/Kvk5KiTaGuBDeP7X57GBHK37Tf repCgL/o5MINL85inak919pvt7iisZ6qoQBSM31cyRx8VC5L0JZzo+bgzp4f+ynnz6/F6LLme fMkPPXW3a55CDn6RmqpHy6EdoehkNIMMsp+iLepNLpioF28T+Tygjzr019qCHrLpCG/biU543 Vtk3CF191RE/Zru9yC6msikS/yKZIIlVW1EM1ivuhRtnUPD/0t8emzNR9XDyJYO7namLrEM4b cW+XlmL+9UQlhEsbZVE2fKwDJbP9WNWJZIMLUVIVwBleUGNmB60PWsw6IDvM+6mrHeGpd6xEu M6sgJ2ZPyBQ/VQhPLbRCF9efNY6lRjA6pG584WyEuA3Bdjt2kGx/3PNZo4R3Djsjs6fST3LWe H56axXVdcdAY/g5DYGYfveEOuNdlfxGd7YzgWcoJpfgHpLxl2TEf/UU4O/KxRygOdsjhNCtM7 ESzEUUlmVD6fpa4md1ZmhyqSQFRLxGQKmbcLp0pJzlKa/rXkIB+EwoctfHHA95J8/TFJBdSlv P241mDEzdwV4Ju/PxM9q3sxjRmEKJZkyqVP+yVd9uSOSL3y68ZWZ4SmNDRLgnCr3lzIYffhwG TQsczMI05BL9RER9zeNGuHvpBWIotDFPyH05Jqc8BGJ6MeGB26BO8DBiMWNsaskgNN46XsM3j pq9ophdOIfugE3TV8ZLI3NQAQPMtLWp0+P5hvqrzEFDKPq6YTdb60ZOMWAt4RrmfgGWI5vBCZ 1fHd+cqRkCMY7CqLixzIQsBXX8yJjh+czsCpHABV7FDUlOJy/684MIUg5FlplYsOF0dGaTtBM 7pJTxllEC7HJlC0EdIMR10U3sSV1+I9qL/KzdvXe7Gi4CX6w2bBQw7xK9C9XLu4lxJGHO6Eea z+bhkmXuXdr64cfSGZzDcTSF/rQfp+komN7EmCCkF5QMYVWhkHlJ6dyZLqccIR5FkO++5eGQx MSlmNR0JU5ncb5iR9iaT/n/l4MoG63PAZ+Jk2r2g8AjLcWEFThkI7WrxGnpcsEkVjX3Foczsa OYRjFDAwL8FAk/zvexMpCbAiyDwrSo9mFk+adHdTf6sFsFG5KUSupFABQ== Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Now that all of its callers are gone, remove llist_mergesort(). Signed-off-by: René Scharfe --- Makefile | 1 - mergesort.c | 76 ----------------------------------------------------- mergesort.h | 13 --------- 3 files changed, 90 deletions(-) delete mode 100644 mergesort.c -- 2.37.1 diff --git a/Makefile b/Makefile index 04d0fd1fe6..d41705dc31 100644 --- a/Makefile +++ b/Makefile @@ -984,7 +984,6 @@ LIB_OBJS += merge-ort.o LIB_OBJS += merge-ort-wrappers.o LIB_OBJS += merge-recursive.o LIB_OBJS += merge.o -LIB_OBJS += mergesort.o LIB_OBJS += midx.o LIB_OBJS += name-hash.o LIB_OBJS += negotiator/default.o diff --git a/mergesort.c b/mergesort.c deleted file mode 100644 index 6bda3a1c0e..0000000000 --- a/mergesort.c +++ /dev/null @@ -1,76 +0,0 @@ -#include "cache.h" -#include "mergesort.h" - -/* 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 *)) -{ - void *result = list, *tail; - int prefer_list = compare_fn(list, other) <= 0; - - if (!prefer_list) { - result = other; - SWAP(list, other); - } - for (;;) { - do { - tail = list; - list = get_next_fn(list); - if (!list) { - set_next_fn(tail, other); - return result; - } - } while (compare_fn(list, other) < prefer_list); - set_next_fn(tail, other); - prefer_list ^= 1; - SWAP(list, other); - } -} - -/* - * 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 *)) -{ - void *ranks[bitsizeof(void *)]; - size_t n = 0; - - if (!list) - return NULL; - - for (;;) { - int i; - size_t m; - void *next = get_next_fn(list); - if (next) - set_next_fn(list, NULL); - for (i = 0, m = n;; i++, m >>= 1) { - if (m & 1) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); - else if (next) - break; - else if (!m) - return list; - } - n++; - ranks[i] = list; - list = next; - } -} diff --git a/mergesort.h b/mergesort.h index 7b44355283..7c36f08bd5 100644 --- a/mergesort.h +++ b/mergesort.h @@ -1,19 +1,6 @@ #ifndef MERGESORT_H #define MERGESORT_H -/* - * Sort linked list in place. - * - get_next_fn() returns the next element given an element of a linked list. - * - set_next_fn() takes two elements A and B, and makes B the "next" element - * of A on the list. - * - compare_fn() takes two elements A and B, and returns negative, 0, positive - * as the same sign as "subtracting" B from A. - */ -void *llist_mergesort(void *list, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)); - /* Combine two sorted lists. Take from `list` on equality. */ #define DEFINE_LIST_MERGE_INTERNAL(name, type) \ static type *name##__merge(type *list, type *other, \