From patchwork Thu Oct 4 15:09:06 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 10626273 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BBD4A15A6 for ; Thu, 4 Oct 2018 15:09:20 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A8F51292CD for ; Thu, 4 Oct 2018 15:09:20 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 9D006292D3; Thu, 4 Oct 2018 15:09:20 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,FREEMAIL_FROM, MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 5293F292CD for ; Thu, 4 Oct 2018 15:09:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727558AbeJDWDA (ORCPT ); Thu, 4 Oct 2018 18:03:00 -0400 Received: from mout.web.de ([212.227.15.14]:37733 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727354AbeJDWC7 (ORCPT ); Thu, 4 Oct 2018 18:02:59 -0400 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb003 [213.165.67.108]) with ESMTPSA (Nemesis) id 0M4I79-1fqPyP44qx-00rlfh; Thu, 04 Oct 2018 17:09:11 +0200 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb003 [213.165.67.108]) with ESMTPSA (Nemesis) id 0M4I79-1fqPyP44qx-00rlfh; Thu, 04 Oct 2018 17:09:11 +0200 Subject: [PATCH v3 1/5] fetch-pack: factor out is_unmatched_ref() To: Git List Cc: Junio C Hamano , Jeff King , Jonathan Tan References: <64911aec-71cd-d990-5dfd-bf2c3163690c@web.de> <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> From: =?utf-8?q?Ren=C3=A9_Scharfe?= Message-ID: <9a7ab468-8d6e-c3d0-3960-b05f06534de5@web.de> Date: Thu, 4 Oct 2018 17:09:06 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.0 MIME-Version: 1.0 In-Reply-To: <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> Content-Language: en-US X-Provags-ID: V03:K1:Bkl20SCPzn9NjKOSYQun5yvuaAsst51kG9hfnX+Jnjidbf2eHrB 6gFTY823gYFw2WVLcwocFMu7ee9dE6pVGPjtePavP8YeoLCgmw+h1E3Re67cJhun4Piwiau KEYinTEt/Ta11DMleTlEVK8FW1D6UDGg4O7NBUGfYYx02qvmxieGFiNXuezrK8ef2ee2Ofu zW0Z/UywyttqRLC7ETbVg== X-UI-Out-Filterresults: notjunk:1;V01:K0:JImISu2LjhI=:Ajtv2VtudHy/+K+p9yOic0 Nl2Z9PqcnJMbsAMPPsFVWQZP2ecLaFKKdLlSv1RbMz3rBPG31KD+gySHPGc7vHt97Mj3GBWrd D6pnruKMVbA/XOcgPJZaQPWGB9EJtRNt+rek0ryTJf6FxEMw3KDnOEKd21da0o2DeUKAeI82L 4FYVcD6szH5xu+TLAiNijTXAOrN5w3kZCwrbv5wLLwZYsByOcQRAUEY87FMpZnAMB3ux+1DQJ cd3vv+rUqsNWIIHtS1J/shNftWQzp9T7DfuI9NZwKReR4+7LB/Xnw6KZ1axTS9CVUC65zir+B J6AB0bNO1Lb9qkP6QJN5qb6Iib62qp/+gamiT7Fdas3IlsN9HmDbYGOfYQUCfdUwqukYVKfeK iEkOkM6oMid+969wJk1APIpY5y7GAR4UXcCWBmoT9eRecORxWM/hdmdJYG7yOG+ybmOnmD/R6 fx46+Me6OkBp6j2eBmKjOHS14VO1ddQpewrWv47FLPgSTGJYVr9O8vPSirKYwvGMh4ITQkd/b /8y1RdpH0pyBvljfm6RvrKII/wIQ+TeyHRGRUNosFkwFl6V6AyqthB9X8eqJOPbUrQgqCirlH ens9iVmkUdgpNvBZBLjyUtxwEtIFsunSrpAKeNHF1hYvLu5W2i1ukMwQZCGdGwG5Z+P3UcCpx sQmJUlBWfAhw/RsDNyS3R1rP/e7Y/50FDAeVZx5a+ofPKfHtXo5iYsrWcg+I8B5/UUWjwhK3U Syz12nC7lSZlPfVMSGa/9j+qL/fx3fLPe1PRVVORJT4hEW4SmoKbsDEcIvHy1MA8KoQK6Y9m7 DvWpjawYQqLF61z6AAR55oAEBUjbMixXNYckp51TNHx/rEHTLM= Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Move the code to determine if a request is unmatched to its own little helper. This allows us to reuse it in a subsequent patch. Signed-off-by: Rene Scharfe --- fetch-pack.c | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) diff --git a/fetch-pack.c b/fetch-pack.c index 75047a4b2a..3b317952f0 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -543,6 +543,16 @@ static int tip_oids_contain(struct oidset *tip_oids, return oidset_contains(tip_oids, id); } +static int is_unmatched_ref(const struct ref *ref) +{ + struct object_id oid; + const char *p; + return ref->match_status == REF_NOT_MATCHED && + !parse_oid_hex(ref->name, &oid, &p) && + *p == '\0' && + oideq(&oid, &ref->old_oid); +} + static void filter_refs(struct fetch_pack_args *args, struct ref **refs, struct ref **sought, int nr_sought) @@ -591,15 +601,8 @@ static void filter_refs(struct fetch_pack_args *args, /* Append unmatched requests to the list */ for (i = 0; i < nr_sought; i++) { - struct object_id oid; - const char *p; - ref = sought[i]; - if (ref->match_status != REF_NOT_MATCHED) - continue; - if (parse_oid_hex(ref->name, &oid, &p) || - *p != '\0' || - !oideq(&oid, &ref->old_oid)) + if (!is_unmatched_ref(ref)) continue; if ((allow_unadvertised_object_request & From patchwork Thu Oct 4 15:09:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 10626275 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2F3D214BD for ; Thu, 4 Oct 2018 15:09:51 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1F12B2925C for ; Thu, 4 Oct 2018 15:09:51 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 126A0292D2; Thu, 4 Oct 2018 15:09:51 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,FREEMAIL_FROM, MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AB65D2925C for ; Thu, 4 Oct 2018 15:09:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727436AbeJDWDb (ORCPT ); Thu, 4 Oct 2018 18:03:31 -0400 Received: from mout.web.de ([212.227.15.3]:45357 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727354AbeJDWDa (ORCPT ); Thu, 4 Oct 2018 18:03:30 -0400 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb003 [213.165.67.108]) with ESMTPSA (Nemesis) id 0MNLRJ-1g6ANa4BKr-006xtw; Thu, 04 Oct 2018 17:09:44 +0200 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb003 [213.165.67.108]) with ESMTPSA (Nemesis) id 0MNLRJ-1g6ANa4BKr-006xtw; Thu, 04 Oct 2018 17:09:44 +0200 Subject: [PATCH v3 2/5] fetch-pack: load tip_oids eagerly iff needed To: Git List Cc: Junio C Hamano , Jeff King , Jonathan Tan References: <64911aec-71cd-d990-5dfd-bf2c3163690c@web.de> <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> From: =?utf-8?q?Ren=C3=A9_Scharfe?= Message-ID: <9f51ac28-73e9-2855-c650-7d695945e286@web.de> Date: Thu, 4 Oct 2018 17:09:39 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.0 MIME-Version: 1.0 In-Reply-To: <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> Content-Language: en-US X-Provags-ID: V03:K1:jtX6vYyEkBvGwyuP8hS4luFJMrxtB3Y1wfyi7MFqYO3t5pwqfws cXoFXBUOsV5zk4S8bKg2MJ59/IWvNt8joTwjwHVlUQcZBZqD1l0oIC67Bi43AsOcXfGP0eV sQJ4BX1gu1wDXNHfHP2tQd2Z+qKvNzyVuE3JUVmSAdiYsUnaiksT6TwQzdBQdlLHl3cavek jeUDr8kHo22YTvYxBeYkw== X-UI-Out-Filterresults: notjunk:1;V01:K0:EQ/nXDRTFV4=:MxTqSwUfu+R8H7OYzz3QLi Hk1ZmjbxUsKpRXIulUSGMlCciWGdSeCZGkHrRLcohTiMzonI+kIwiDoet/Hu2xZDM9HfGz54f ZHpq65bZwMuc9Zng5c0+2fWz6zG3dnjhYHaym+brK6DFrrZ2nJ6xxI2hmjpC/BCvfZiB/ADh0 NIVwD+nGEWu7UxRi9m17a5H664HUYltMBImbJ0K6E2p6fIajLLPK0ERw6PRYilrooVxPjHTvR F56+W5OhtQNc1PI47BWzgQxn4/9aQXw3LqAKXh2losTrdWQ8KOmCDPBCT5NJp9er/NOfnYcyv fXZ45im70hJ3U+Om6m6yxDB7GJ86Lv2eoNryXCuhylr2AU5a2e1iMEQxAqVZgITbqd0eTa1jU jywmuoYjyXqC2UNPCmwg8vnPBJrpoK2ek3JTpF7gdTkqoipKM90KHe/knZmuFzY1R+Qb/RgMb cMe+jg8WxE80d+EE2e//Au8tI6tICO748ybHTPyOxvZEZ7Ycj9i09Fstia3B0P+1Vfu8Yvpc3 rotI6P9S5h6GQDLYRuKqtdeQ1KKGqPdRnTk+39npdKOkjBpWS66govENPBp3xceLED5qdnUwY loG2914eBlgphTXAv+Xr7N2H2pkuqREv/3zNfVfmqszTWWCdf7xmtgIGpuY8PEX4R3xKDxG57 92i2j2iwys5g2WGeXwWzi4LxJpBOX9GZjgp6nmeZRwdvBlrtUxdUMt2q1ltFa+C5PbxN0jWn9 hpQBqaUiuPWkqH/Rbm8GMWOtsw4z2lkYyd4Z5z9MrCIPwqGiUWXU5qZWqXpnSfoFWkuq5ydXX WQbI2RNYDhsmYmakKpiX8PfPw6c6bNLHWnPqO4/fAWQ/tgFYZA= Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP tip_oids_contain() lazily loads refs into an oidset at its first call. It abuses the internal (sub)member .map.tablesize of that oidset to check if it has done that already. Determine if the oidset needs to be populated upfront and then do that instead. This duplicates a loop, but simplifies the existing one by separating concerns between the two. Signed-off-by: Rene Scharfe --- fetch-pack.c | 36 +++++++++++++++--------------------- 1 file changed, 15 insertions(+), 21 deletions(-) diff --git a/fetch-pack.c b/fetch-pack.c index 3b317952f0..53914563b5 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -526,23 +526,6 @@ static void add_refs_to_oidset(struct oidset *oids, struct ref *refs) oidset_insert(oids, &refs->old_oid); } -static int tip_oids_contain(struct oidset *tip_oids, - struct ref *unmatched, struct ref *newlist, - const struct object_id *id) -{ - /* - * Note that this only looks at the ref lists the first time it's - * called. This works out in filter_refs() because even though it may - * add to "newlist" between calls, the additions will always be for - * oids that are already in the set. - */ - if (!tip_oids->map.map.tablesize) { - add_refs_to_oidset(tip_oids, unmatched); - add_refs_to_oidset(tip_oids, newlist); - } - return oidset_contains(tip_oids, id); -} - static int is_unmatched_ref(const struct ref *ref) { struct object_id oid; @@ -563,6 +546,8 @@ static void filter_refs(struct fetch_pack_args *args, struct ref *ref, *next; struct oidset tip_oids = OIDSET_INIT; int i; + int strict = !(allow_unadvertised_object_request & + (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)); i = 0; for (ref = *refs; ref; ref = next) { @@ -599,16 +584,25 @@ static void filter_refs(struct fetch_pack_args *args, } } + if (strict) { + for (i = 0; i < nr_sought; i++) { + ref = sought[i]; + if (!is_unmatched_ref(ref)) + continue; + + add_refs_to_oidset(&tip_oids, unmatched); + add_refs_to_oidset(&tip_oids, newlist); + break; + } + } + /* Append unmatched requests to the list */ for (i = 0; i < nr_sought; i++) { ref = sought[i]; if (!is_unmatched_ref(ref)) continue; - if ((allow_unadvertised_object_request & - (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) || - tip_oids_contain(&tip_oids, unmatched, newlist, - &ref->old_oid)) { + if (!strict || oidset_contains(&tip_oids, &ref->old_oid)) { ref->match_status = REF_MATCHED; *newtail = copy_ref(ref); newtail = &(*newtail)->next; From patchwork Thu Oct 4 15:10:54 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 10626277 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id F2669184E for ; Thu, 4 Oct 2018 15:11:06 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E26BE2925C for ; Thu, 4 Oct 2018 15:11:06 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D6E7B292D1; Thu, 4 Oct 2018 15:11:06 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,FREEMAIL_FROM, MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8E795292CD for ; Thu, 4 Oct 2018 15:11:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727691AbeJDWEr (ORCPT ); Thu, 4 Oct 2018 18:04:47 -0400 Received: from mout.web.de ([212.227.15.4]:34559 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727685AbeJDWEq (ORCPT ); Thu, 4 Oct 2018 18:04:46 -0400 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb002 [213.165.67.108]) with ESMTPSA (Nemesis) id 0LvS5r-1fhaFN2v4N-010ZLG; Thu, 04 Oct 2018 17:10:58 +0200 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb002 [213.165.67.108]) with ESMTPSA (Nemesis) id 0LvS5r-1fhaFN2v4N-010ZLG; Thu, 04 Oct 2018 17:10:58 +0200 Subject: [PATCH v3 3/5] khash: factor out kh_release_* To: Git List Cc: Junio C Hamano , Jeff King , Jonathan Tan References: <64911aec-71cd-d990-5dfd-bf2c3163690c@web.de> <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> From: =?utf-8?q?Ren=C3=A9_Scharfe?= Message-ID: <46f34917-eafd-2970-17f4-c2df92a00352@web.de> Date: Thu, 4 Oct 2018 17:10:54 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.0 MIME-Version: 1.0 In-Reply-To: <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> Content-Language: en-US X-Provags-ID: V03:K1:V6gOV89ppLTSLM6Q5AUmtH54iOKlKJl3NtwQE9al7MJ+oESyllg 43Fb/0/UFi5YFE82QnsINK2w7hmohXKUxPHFDZ1gO27648Gqghn7lHHlLiX+KUG0Sqwqbk+ y0WgwtuBhbK6MHgLsJYpKhNDuukkm8QKCiaGZvmGCnBbvTwQGhwcVi6FKiWSO08RzHQAIAH CgfHUukdGYQTcj04jR+pA== X-UI-Out-Filterresults: notjunk:1;V01:K0:uYg8tJ4M7KU=:ppnSHUxAv41Us73V3tBk8j gfcm+1MxBq15QnvFVFK9XguXyC3h4BcvAQtXLsfQ3zjtjRePE7PAVhhAadsOxc9ljAsSylKAQ viKanYsQM6By09YpvAI+LABZBAJ/K4QHfwlP+LjesY0wVtKWJV1lB0acUnUIFIYoP3MnJJ4Ie LJGwnmYPj9NmfXvQGC883LIaczl/b5VXYSmChGtMtE04q5incwhOBclZ+p8xm3cYJP/cNmO+n 3tWec7OKizjzkJVDdT0vnm0+xW3CLyR7l0+SiA5lLPxXpRh2JTI4p/IiaR3fKX1SkueNRIhyo cLLDmR9JPVdws89QXqjBBoL84gWsP3oXllBvpyShJpS/kT4ekYeu9lEhJJo4GWGcdxBE4Cekb ASDNwZrRrdKaQoyFQ7Q5oryvGAKjqUM3jmzW4CSi94KLaGa5o6FVubxgHqLEXEER5qMWg2MLw FP1sS/QlLo619ytsGQVd0cXnmLURPdBs2cOgJrCrtNtUt17GwujuKwf1Zn3Zh+ltM2TAJCi4a EpZqL8m6cLt93FQN/wtuLFUcmCKcSb8D2et8Fwik9UqGeO4m4ZZNh8SeO2KikBXuin+aJqYJZ U2KUIYhAcY4jAMahwA+o6rupibRjyC73u/lkXHvQzrExin21sfIz/+y8xEKC0szyvB6FHUvQS i2uUYP6RxJD7V+NGOpvgldVPzX0JWVsLAPujES/0Gc83Utv4Aqy222wXROkhFJRgGTUUxvKZq 4uCdOyd0fQrsYQB1i5NaO1HooZ9R/CEorBiBWALoHM2Du5zw6/0fxzP2UPNYEW46QbHE7gLJv cYpOTbSQLL0IzcXo6JGTxhKMIK9WLvHHVn6syGGFFp/Y7/34rQ= Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Add a function for releasing the khash-internal allocations, but not the khash structure itself. It can be used with on-stack khash structs. Signed-off-by: Rene Scharfe --- 1 tab = 4 spaces here. khash.h | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/khash.h b/khash.h index 07b4cc2e67..d10caa0c35 100644 --- a/khash.h +++ b/khash.h @@ -82,11 +82,16 @@ static const double __ac_HASH_UPPER = 0.77; SCOPE kh_##name##_t *kh_init_##name(void) { \ return (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t)); \ } \ + SCOPE void kh_release_##name(kh_##name##_t *h) \ + { \ + free(h->flags); \ + free((void *)h->keys); \ + free((void *)h->vals); \ + } \ SCOPE void kh_destroy_##name(kh_##name##_t *h) \ { \ if (h) { \ - free((void *)h->keys); free(h->flags); \ - free((void *)h->vals); \ + kh_release_##name(h); \ free(h); \ } \ } \ From patchwork Thu Oct 4 15:13:06 2018 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: 10626279 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 154D2175A for ; Thu, 4 Oct 2018 15:13:20 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 02B56209CE for ; Thu, 4 Oct 2018 15:13:20 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E7D122624D; Thu, 4 Oct 2018 15:13:19 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,FREEMAIL_FROM, MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 60958209CE for ; Thu, 4 Oct 2018 15:13:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727732AbeJDWHA (ORCPT ); Thu, 4 Oct 2018 18:07:00 -0400 Received: from mout.web.de ([212.227.15.14]:45395 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727561AbeJDWHA (ORCPT ); Thu, 4 Oct 2018 18:07:00 -0400 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb004 [213.165.67.108]) with ESMTPSA (Nemesis) id 0M7Eb0-1fkebw3rL4-00x6DO; Thu, 04 Oct 2018 17:13:10 +0200 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb004 [213.165.67.108]) with ESMTPSA (Nemesis) id 0M7Eb0-1fkebw3rL4-00x6DO; Thu, 04 Oct 2018 17:13:10 +0200 Subject: [PATCH v3 4/5] oidset: use khash To: Git List Cc: Junio C Hamano , Jeff King , Jonathan Tan References: <64911aec-71cd-d990-5dfd-bf2c3163690c@web.de> <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> From: =?utf-8?q?Ren=C3=A9_Scharfe?= Message-ID: <3651262f-dec2-16d4-fc77-346ed74c6ffa@web.de> Date: Thu, 4 Oct 2018 17:13:06 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.0 MIME-Version: 1.0 In-Reply-To: <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> Content-Language: en-US X-Provags-ID: V03:K1:J7viYq3KWSi2PuGwqQ3cv52Yz3rs1EcJCwhbcePrW6kbts8eD2k F0iouMIC0EPrPwOqaiZIFiNc72h+ovgKXw+w4/JiHtDnBu+TrRSg7I/4aPaLH9sCZNAUd0B ajo6ScxroRpwptJTfugE8OpQVuWI1UtF506UtXWs2mLDHIbC4K8wx3HVowDQXiFJ/A3i7Rx r2I+543uHxjjpubfOJYIw== X-UI-Out-Filterresults: notjunk:1;V01:K0:Ui/KzIQQqb0=:YpUzW35P0Pe/aTgaF1oK4P d3l3phSl6Ujq+7vwUgGdfngChuRluthYcIHJtUBfiFnshAmE1PFMNJrStbjzJ1X6eN4xwdvG7 3cQN4Zcc0v01H0xi+Ohx/GuIfI09rITq0BLh4ScYj7Kh0AeKPgshpICzq/MXdKJ1vp/en3K29 g/xnSvNqEYJ9XdO97YaMI1Fmvgwii/NFv1NWcnpdDSr570q0qd/ASodEUYprZOsY6fmy2TbIU qS/9IiGgrmLnORgCFodyxU7yfZ5WP3D6+2JKuocEOOXLAjq3dQPKa6F0Y0jnREDkCoSY3JUNq pvBTfxmxqn1UiGMP5qEHaq2Nkn5Br4z5QE4HqKt97pbUT0baoGzFKV2cxg7xshdiNbptwFuS1 Vn82kYBMvzyh/d8elqJ9lWg+vgj2lE6E+2MHMrpWNWJG7qE/IAdf3CDeGidliYumeD+Bwngk6 gO6g++DJujYSvrsUKrcqz+cHxYPCllcpbtils2u/kgXqTRAV8+yQPS6EON6u8RLdm63z7/EyI iinGYOrVRWy2aDOoYr5eV8r/pxCEJmVvwbAh3bJrPhCd7qeuzScd1MjjdFex/5vOKHeb22ZWQ t5047vQOHSXmbMURq2ktmHR3oiuELQtmg2YHnIswwXr03Jsian1eXwK9rbcIAZRlKSdT3Bsnv wf8R9Ztkh1zbi2sjcSLDobstbw0LvT/BTTh30ZhxQffWwI11eWvyOxEhpUy3VEO8lGaox1qKz yKuJ/LUVhe7y/JJDudyIHUUV2XhPx184BGTxVLfHUVU2GFmyiceEdLJda9NyYdky2Wegl/D2B eAZ/wgPkG7X4kg7WRuszNm4wierGcRGE2iWu11yr3IJMjKTjiI= Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Reimplement oidset using khash.h in order to reduce its memory footprint and make it faster. Performance of a command that mainly checks for duplicate objects using an oidset, with master and Clang 6.0.1: $ cmd="./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)'" $ /usr/bin/time $cmd >/dev/null 0.22user 0.03system 0:00.25elapsed 99%CPU (0avgtext+0avgdata 48484maxresident)k 0inputs+0outputs (0major+11204minor)pagefaults 0swaps $ hyperfine "$cmd" Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)' Time (mean ± σ): 250.0 ms ± 6.0 ms [User: 225.9 ms, System: 23.6 ms] Range (min … max): 242.0 ms … 261.1 ms And with this patch: $ /usr/bin/time $cmd >/dev/null 0.14user 0.00system 0:00.15elapsed 100%CPU (0avgtext+0avgdata 41396maxresident)k 0inputs+0outputs (0major+8318minor)pagefaults 0swaps $ hyperfine "$cmd" Benchmark #1: ./git-cat-file --batch-all-objects --unordered --buffer --batch-check='%(objectname)' Time (mean ± σ): 151.9 ms ± 4.9 ms [User: 130.5 ms, System: 21.2 ms] Range (min … max): 148.2 ms … 170.4 ms Initial-patch-by: Jeff King Signed-off-by: Rene Scharfe --- oidset.c | 34 ++++++++++++---------------------- oidset.h | 36 ++++++++++++++++++++++++++++-------- 2 files changed, 40 insertions(+), 30 deletions(-) diff --git a/oidset.c b/oidset.c index 454c54f933..9836d427ef 100644 --- a/oidset.c +++ b/oidset.c @@ -3,38 +3,28 @@ int oidset_contains(const struct oidset *set, const struct object_id *oid) { - if (!set->map.map.tablesize) - return 0; - return !!oidmap_get(&set->map, oid); + khiter_t pos = kh_get_oid(&set->set, *oid); + return pos != kh_end(&set->set); } int oidset_insert(struct oidset *set, const struct object_id *oid) { - struct oidmap_entry *entry; - - if (!set->map.map.tablesize) - oidmap_init(&set->map, 0); - else if (oidset_contains(set, oid)) - return 1; - - entry = xmalloc(sizeof(*entry)); - oidcpy(&entry->oid, oid); - - oidmap_put(&set->map, entry); - return 0; + int added; + kh_put_oid(&set->set, *oid, &added); + return !added; } int oidset_remove(struct oidset *set, const struct object_id *oid) { - struct oidmap_entry *entry; - - entry = oidmap_remove(&set->map, oid); - free(entry); - - return (entry != NULL); + khiter_t pos = kh_get_oid(&set->set, *oid); + if (pos == kh_end(&set->set)) + return 0; + kh_del_oid(&set->set, pos); + return 1; } void oidset_clear(struct oidset *set) { - oidmap_free(&set->map, 1); + kh_release_oid(&set->set); + oidset_init(set, 0); } diff --git a/oidset.h b/oidset.h index 40ec5f87fe..4b90540cd4 100644 --- a/oidset.h +++ b/oidset.h @@ -1,7 +1,8 @@ #ifndef OIDSET_H #define OIDSET_H -#include "oidmap.h" +#include "hashmap.h" +#include "khash.h" /** * This API is similar to sha1-array, in that it maintains a set of object ids @@ -15,19 +16,33 @@ * table overhead. */ +static inline unsigned int oid_hash(struct object_id oid) +{ + return sha1hash(oid.hash); +} + +static inline int oid_equal(struct object_id a, struct object_id b) +{ + return oideq(&a, &b); +} + +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal) + /** * A single oidset; should be zero-initialized (or use OIDSET_INIT). */ struct oidset { - struct oidmap map; + kh_oid_t set; }; -#define OIDSET_INIT { OIDMAP_INIT } +#define OIDSET_INIT { { 0 } } static inline void oidset_init(struct oidset *set, size_t initial_size) { - oidmap_init(&set->map, initial_size); + memset(&set->set, 0, sizeof(set->set)); + if (initial_size) + kh_resize_oid(&set->set, initial_size); } /** @@ -58,19 +73,24 @@ int oidset_remove(struct oidset *set, const struct object_id *oid); void oidset_clear(struct oidset *set); struct oidset_iter { - struct oidmap_iter m_iter; + kh_oid_t *set; + khiter_t iter; }; static inline void oidset_iter_init(struct oidset *set, struct oidset_iter *iter) { - oidmap_iter_init(&set->map, &iter->m_iter); + iter->set = &set->set; + iter->iter = kh_begin(iter->set); } static inline struct object_id *oidset_iter_next(struct oidset_iter *iter) { - struct oidmap_entry *e = oidmap_iter_next(&iter->m_iter); - return e ? &e->oid : NULL; + for (; iter->iter != kh_end(iter->set); iter->iter++) { + if (kh_exist(iter->set, iter->iter)) + return &kh_key(iter->set, iter->iter++); + } + return NULL; } static inline struct object_id *oidset_iter_first(struct oidset *set, From patchwork Thu Oct 4 15:14:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 10626281 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id F3179175A for ; Thu, 4 Oct 2018 15:14:49 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DF2E929285 for ; Thu, 4 Oct 2018 15:14:49 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id CEC8229291; Thu, 4 Oct 2018 15:14:49 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,FREEMAIL_FROM, MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7438429285 for ; Thu, 4 Oct 2018 15:14:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727385AbeJDWIa (ORCPT ); Thu, 4 Oct 2018 18:08:30 -0400 Received: from mout.web.de ([212.227.15.3]:41491 "EHLO mout.web.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727354AbeJDWIa (ORCPT ); Thu, 4 Oct 2018 18:08:30 -0400 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb002 [213.165.67.108]) with ESMTPSA (Nemesis) id 0MXHoz-1gBhwq3j3V-00WCOA; Thu, 04 Oct 2018 17:14:41 +0200 Received: from [192.168.178.36] ([91.20.58.167]) by smtp.web.de (mrweb002 [213.165.67.108]) with ESMTPSA (Nemesis) id 0MXHoz-1gBhwq3j3V-00WCOA; Thu, 04 Oct 2018 17:14:41 +0200 Subject: [PATCH 5/5] oidset: uninline oidset_init() To: Git List Cc: Junio C Hamano , Jeff King , Jonathan Tan References: <64911aec-71cd-d990-5dfd-bf2c3163690c@web.de> <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> From: =?utf-8?q?Ren=C3=A9_Scharfe?= Message-ID: Date: Thu, 4 Oct 2018 17:14:37 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.0 MIME-Version: 1.0 In-Reply-To: <14e57ec8-b8a2-10bd-688d-1cb926e77675@web.de> Content-Language: en-US X-Provags-ID: V03:K1:OtImo+VZXxNyrNGCJ+uw1xzPYV+GOwu6qwQvvBoc/4EzG3m0mwk D/CucHj/i0NCM15uJcs8ZUaBbI6f4dZjj6W/TGZiKb2pY7V969sevyENaz/ZN4ba/39SA3k tbHLFt/V2PCvYb6r1aqEpOnXl6vh05YNFkbsNyMAThB+jZyqjOJFIPlZRY2qCeKh/lQQfkG K6fhSIULSXHc32PGANNEQ== X-UI-Out-Filterresults: notjunk:1;V01:K0:1eUQrpTBarI=:4G0AL8oTHGXHqInYaloLD9 oI6PaggUi6+GxZm8xsmcZ3fAeyYN7bwdsWqbWE9XgVzM0eNnOC6eES/tMBiW/pTF7u5z7O3rI b6NWMLTBu15myaVQJPkOpPi9fSEnTFO1QuI8Elx12yf1+s3U/WMTbFyMpEC36PTnEyjwe35Oi FlaR/t3uXRQ98OeqW+ZvVgjuNgEY1/GFTMUUjoQMZ/jSXYQDxu4FIhKCa/CJKg8X9WgHBE92L DMX6Yo731WHqQT04R8a5rY4wgwT22U4JgIGPru8p8CqAFWSffTtJ+bq+VrBtmnErFGCVImuhl hwaa2WDVxWaaPZCCW75vEv1kLHg8FTBbEck3s6Xl+D/Ls+ScoeeSt6XIYXz7FXnQ1uNZCsR/H lrrZaAFyQw601dmf7lxdbUiF0oLHrmyltcOoRJRZJWr1HNbcV84+BDdKJLnCbtRV4zHxVzzuN LYdXJej4qM60wabcXCC+Cc2isdLNnyMhk6qkOc6UZjIXCJ6g/z0y8H0nGL3JpGSTnijNWVT/M br5lRcFhp7i2tC5CN9QYcWEWK4h09HkRJ250x9SAsKknTEZVUZv5YE+cochl+Q9dpdnYw/DBR akt7p0l2yMUMbvVpFz1pRMUGxkNxuRgTWcjR3LLcGJvK2jhMmLh0YwMDWZh5OoIvhdcNY4fgu oeEEbEyIALIMSUACedaOv6qHt/1StZVNQ85kRwEwKYcDwPLhLzh843AHFCWICVUWmXHnSbRos BLcDR+3A38UsbTRfSzb37ltve55aBPAEI1G/+XTP2eU4RQZtfED5DdPBzBTY8ItqFt0Eb3CqF nEvyy2vj+gH7lNYnzrsgfq+eoWCF33pK/SK/ASvLOaAQcStBzk= Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP There is no need to inline oidset_init(), as it's typically only called twice in the lifetime of an oidset (once at the beginning and at the end by oidset_clear()) and kh_resize_* is quite big, so move its definition to oidset.c. Document it while we're at it. Signed-off-by: Rene Scharfe --- oidset.c | 7 +++++++ oidset.h | 13 +++++++------ 2 files changed, 14 insertions(+), 6 deletions(-) diff --git a/oidset.c b/oidset.c index 9836d427ef..fe4eb921df 100644 --- a/oidset.c +++ b/oidset.c @@ -1,6 +1,13 @@ #include "cache.h" #include "oidset.h" +void oidset_init(struct oidset *set, size_t initial_size) +{ + memset(&set->set, 0, sizeof(set->set)); + if (initial_size) + kh_resize_oid(&set->set, initial_size); +} + int oidset_contains(const struct oidset *set, const struct object_id *oid) { khiter_t pos = kh_get_oid(&set->set, *oid); diff --git a/oidset.h b/oidset.h index 4b90540cd4..c9d0f6d3cc 100644 --- a/oidset.h +++ b/oidset.h @@ -38,12 +38,13 @@ struct oidset { #define OIDSET_INIT { { 0 } } -static inline void oidset_init(struct oidset *set, size_t initial_size) -{ - memset(&set->set, 0, sizeof(set->set)); - if (initial_size) - kh_resize_oid(&set->set, initial_size); -} +/** + * Initialize the oidset structure `set`. + * + * If `initial_size` is bigger than 0 then preallocate to allow inserting + * the specified number of elements without further allocations. + */ +void oidset_init(struct oidset *set, size_t initial_size); /** * Returns true iff `set` contains `oid`.