From patchwork Wed Feb 14 07:45:41 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556039 Received: from wfout3-smtp.messagingengine.com (wfout3-smtp.messagingengine.com [64.147.123.146]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A1D09125A4 for ; Wed, 14 Feb 2024 07:45:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.146 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896747; cv=none; b=DzsssYVlsA0KFXdv9ouiRhXWTdT4SExN2h6yovg8ndo0mEIVTJSmCjk+TVrXo8AqR/3WXkw0iEvU9OgWiSxxkUBIXa/vV7QcoSAnYySHE0CjCmaarwn/nruUkUfxpPky3SVXRVVJYn/pjeo7coczt7qnVH231Y26eX9jsBRCAUY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896747; c=relaxed/simple; bh=HdRmAI7kUhFZKc0IFBGMbcSSo9lvlfNQ5/fsbkRU6o8=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=CNv/bkSvD/NA8OIdMYCzBsvcg0BP7gpJUBVSUyIAwbMKkP1Y4o4mJPfZNyPqQaGy2Oj9wBKghrosqhkOTMr0TCV/IJkzw4NaVBdVXMHsArG2UGhK/OJ0YNZPuUMiijngZdqM9vVNWB5LL93mKtCF963z4ppxzXNQAZC3kp0Fa40= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=oVFn8mhh; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=NUSg/jWn; arc=none smtp.client-ip=64.147.123.146 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="oVFn8mhh"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="NUSg/jWn" Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailfout.west.internal (Postfix) with ESMTP id 709551C000AF for ; Wed, 14 Feb 2024 02:45:44 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute3.internal (MEProxy); Wed, 14 Feb 2024 02:45:44 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896743; x=1707983143; bh=D0qUfCTQsS xupilXEVyxObeJVgUoWWw7AYNdqW0ec6o=; b=oVFn8mhhZmJSQUzpUQNyz3okb9 hEE+XSkpA/Wy0MFv8pQBFHQ+LZHfcl2AW4WdDucVrAwcaacfAD8lYttpfeNIja1e Hp20ta5WXqWFkTolh+uqXUXtUgFxrXkylkCMQYF/9+VGSenIO2mT2uaVl8VvVdgL RO4HO/Sml0RjMdKjKUnFvtleAkkod95653ONjQcUg0/7ss+gRv/hZgj3SH0Cf0NP OCFB0CDLLBArPTSAMmFlvfrI6bXNTiflwpe31xJaxKnRdVephVq1MyRamV3LdqPK Nm8M/T3auHUde/LPolBgr0XaOdQsNdpXcClr3N8ATTrjyAiVqMMgR72dSh+Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896743; x=1707983143; bh=D0qUfCTQsSxupilXEVyxObeJVgUo WWw7AYNdqW0ec6o=; b=NUSg/jWnE2tb0wWM7LupQrvdGk1djDLM0mAJ+ftGRIyZ TbtBJGjsgtecs88L38bifKO/EWzMFnt82HOXTFNqyCkpKR8U+uI4XHa75GvewGc/ pzL9a54sORtFfUvbOM87QxNwdb78EV9KTbBMl9FIu0ro6v/xpo9MYavkaeAbzGev VUwpEfYTbO+4r+9qE6iYPxMsBUx17yD2jPgxS5mebe9xHjIchvoG/AY14Ym7OcKR queyRL6c3TQlv2wD83MJ86L9GtUy3jIWflBgg40WKzpRfERMHinu17L98yrixOqD Yo7TTDO3utDdJvSB2CrkJvVLfViriUlZdekFCfgLMA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtvdenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhepheeghfdtfeeuffehkefgffduleffjedthf dvjeektdfhhedvlefgtefgvdettdfhnecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:45:43 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 1290adf9 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:41:53 +0000 (UTC) Date: Wed, 14 Feb 2024 08:45:41 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 01/12] reftable/pq: use `size_t` to track iterator index Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The reftable priority queue is used by the merged iterator to yield records from its sub-iterators in the expected order. Each entry has a record corresponding to such a sub-iterator as well as an index that indicates which sub-iterator the record belongs to. But while the sub-iterators are tracked with a `size_t`, we store the index as an `int` in the entry. Fix this and use `size_t` consistently. Signed-off-by: Patrick Steinhardt --- reftable/pq.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/reftable/pq.h b/reftable/pq.h index e85bac9b52..9e25a43a36 100644 --- a/reftable/pq.h +++ b/reftable/pq.h @@ -12,7 +12,7 @@ license that can be found in the LICENSE file or at #include "record.h" struct pq_entry { - int index; + size_t index; struct reftable_record rec; }; From patchwork Wed Feb 14 07:45:45 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556040 Received: from wout1-smtp.messagingengine.com (wout1-smtp.messagingengine.com [64.147.123.24]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0FCF8125A1 for ; Wed, 14 Feb 2024 07:45:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.24 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896751; cv=none; b=d/a4FVWq+PPr4GVe0z8FFZkhysRGlpomKlXayCP/sCoNYgN5o87VuSTh7rEFuuZRIg6/FwdLbC9lV16GC+6bts0Euds1JMEN2VgXSYByLxVwXiRKm9m66nrFbTCUZux23+qcxCZ+GZ+4vupHx6cXdyt2TsKzXnbO9t3/49TvfPc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896751; c=relaxed/simple; bh=Ohb9lbSQnxDqK54O0+tczJBYlwBPpKv2cMqGpDePDmM=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Y4leR2/EwayDIg3SDbv8fop8Wp4TnFJlqqW64Iw88PQoJBSAr0T1qgYGwl7yt2mNXcs0dx8/TpfcPMo+9ZlNXy/LFLNww0plSAQcigq2q3lmMEeaIftKT/OAwnp4VyGy2ZCO2QeShsQIJoIlJzcZab76uuh3G9do2Ev781RaWmk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=X/XJ4JJ1; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=XzUWeL6z; arc=none smtp.client-ip=64.147.123.24 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="X/XJ4JJ1"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="XzUWeL6z" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id 1C7B232002D8 for ; Wed, 14 Feb 2024 02:45:49 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute1.internal (MEProxy); Wed, 14 Feb 2024 02:45:49 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896748; x=1707983148; bh=TBy9wXlLQc MBXmYfYPhKBB5IdG2xQSK9OT9MXeTw59M=; b=X/XJ4JJ1DX2OVdgQTVwoLK9s/J jtJ30vJEeoIuVqY0dJ8hUtLnot32cs5U6x/t22Q+4O78TTyQ164vK4hm/+v0nk5E 8qtST2IHDNvAoNBEgmvOtOC1zF4b27XhqctQcTqkh5D/yaabdBv4bPOK4VU65xxg UDh3Bwt2Itr6tqV+JC1vm0KpSvh3w5EmlZStokyJlJWoHKzoQlYLs7kyuptOiR6b 3GwKSqvfKUjv3VqCyy3G8hPSzhe3KgjT8DiMgRnmooSfKRuRwEEHmHz3qNaLs22e Q9d8dQUjXmzv3+c0YlF4k8j64SA78GLJNBPF7rMobdnZcUt7Dbd7MxZRn00A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896748; x=1707983148; bh=TBy9wXlLQcMBXmYfYPhKBB5IdG2x QSK9OT9MXeTw59M=; b=XzUWeL6zl9SQ6YGYkXGRlcBeC2waFkW4Br3eFw7iw16m Tm1PIIo+jHnB2B7Rkq+yrWiakaFnTcfLtuBlKX5qZkPn5+vQpznrJo9eCLWVqPbk v+r7Fov26h5TY44tjOz6UlUc0AWJZiKHPkKOGh4JcMjgkhz2mvUgcElEweX+ouOh M3QAJjOGxnqcbGAEy1ZQmt3T+ckG2z4H7GzKM4saqI5bQwhr+7NINZnWjA34iwMR VdPByCWG+W2Q6pCYB5x+GLu+Kok0jy6g9HmVbv09hABvo94kx+ss2hScLyv6LBF2 FrrPxe+STk/p5ljzT1CGODnp3Luv1BX3Jm7rCCxuAg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtvdenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhepheeghfdtfeeuffehkefgffduleffjedthf dvjeektdfhhedvlefgtefgvdettdfhnecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:45:47 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id bf0a18e1 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:41:57 +0000 (UTC) Date: Wed, 14 Feb 2024 08:45:45 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 02/12] reftable/merged: make `merged_iter` structure private Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The `merged_iter` structure is not used anywhere outside of "merged.c", but is declared in its header. Move it into the code file so that it is clear that its implementation details are never exposed to anything. Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 9 +++++++++ reftable/merged.h | 9 --------- 2 files changed, 9 insertions(+), 9 deletions(-) diff --git a/reftable/merged.c b/reftable/merged.c index 1aa6cd31b7..12ebd732e8 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -17,6 +17,15 @@ license that can be found in the LICENSE file or at #include "reftable-error.h" #include "system.h" +struct merged_iter { + struct reftable_iterator *stack; + uint32_t hash_id; + size_t stack_len; + uint8_t typ; + int suppress_deletions; + struct merged_iter_pqueue pq; +}; + static int merged_iter_init(struct merged_iter *mi) { for (size_t i = 0; i < mi->stack_len; i++) { diff --git a/reftable/merged.h b/reftable/merged.h index 7d9f95d27e..288ad66656 100644 --- a/reftable/merged.h +++ b/reftable/merged.h @@ -24,15 +24,6 @@ struct reftable_merged_table { uint64_t max; }; -struct merged_iter { - struct reftable_iterator *stack; - uint32_t hash_id; - size_t stack_len; - uint8_t typ; - int suppress_deletions; - struct merged_iter_pqueue pq; -}; - void merged_table_release(struct reftable_merged_table *mt); #endif From patchwork Wed Feb 14 07:45:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556041 Received: from wfout3-smtp.messagingengine.com (wfout3-smtp.messagingengine.com [64.147.123.146]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 989F512B61 for ; Wed, 14 Feb 2024 07:45:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.146 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896756; cv=none; b=lxViF3vI3c60dsfcsDlXo2tsEaM1DMmVmVLdg0GUjoBid8C0IxUpv95p/XRBTqipBbc2Yvvu7XgcnpClGXVJ2Wx9sis8aSyt7ydX1mTJFb8i0CyLn38RRVUPVlA9YPKz5PQk0FOYlND8pPedm6qovluBMA+23jjNfT6JFdRMGyE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896756; c=relaxed/simple; bh=b5kOUuyLjTa0ZyujA5rBDHGroVF6bTBRrEH6qcJ7Tp0=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=YofaimuKXp8kqhzqE7zuMw52RBTTg2awAc0Nde8l4wwfeSZUcqte97n1ElqC2+GRL7KExodxmklH/c8owxwYZXO0jFpx7yeOHjAFVZmIzhpT+yDgOiLJuvTCOfutJiM0mTtJ9JCKRmqbJTXtuxZi+WVOrc372jBJ7myRlt8uCmM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=VwiNEMeb; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=N75O3PFv; arc=none smtp.client-ip=64.147.123.146 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="VwiNEMeb"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="N75O3PFv" Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailfout.west.internal (Postfix) with ESMTP id A3F2E1C000B1 for ; Wed, 14 Feb 2024 02:45:53 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute2.internal (MEProxy); Wed, 14 Feb 2024 02:45:53 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896753; x=1707983153; bh=MTUGI0IVCz rddG8oxnE2TQQ5ClezQoBl9a21+C43m3E=; b=VwiNEMebpi5u2c8123poLh2ULZ 20ZHbt7IhrhQHbrbI69yYuxKog1KoioVuRXVdRd5Z/gZAihSpTEiyjBTHDIFVufT l7KZ2okrZP5MAWy6jQktRRWcJ1rGp4hxf05IwvGmiQpqM8IViLGcp8gj08U3DPNu uW7ctzblESnnsujJdFc/RctdhfkCYWkl3cWAtxj1lY4W5pekmAVUD/vK8NuUsJbo Dg7M2DeI8INQY2/QnrNsZZXP0+OBd4SFUmHP4YxII5JhgJHcuvjsjASHHrTdJNTY vJl0uc59nxCR+USs7YHdr8xYVSQskXVN4XNEWKX6LSXPuTFrC4Nx/tepJD1g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896753; x=1707983153; bh=MTUGI0IVCzrddG8oxnE2TQQ5Clez QoBl9a21+C43m3E=; b=N75O3PFvcKCrDo+DSv4GR6sLOkJeA8C3nY8VLf0p+/v8 nVug6C3rlbO26cXE5r1VeeokRYQliFTurTVJQigWXCGmUz9VWQN1GFFPWJ1LtInL 0OhiiOIsJQGXS3CODWlpto0oz5gXnaFGAkMFeByDA3NbTps0HBsUGGKxZv+9Hrhf fxyFE/I/2NAGiWqP3bBQaB6NbrO1UZ58OInlxmOvhdKhT2b7TAABkZDrYONe21qw R1MpaI+STAPHdkKLJawm5CIitb5K5mhkIGCelHKppLcpgcOPsfwjydp4vpUlk/Bu mKgEb3FjH+nFsKdnj5xD0/oR9dP3cilXEGS9E8/vqA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudegucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:45:52 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 50a4df57 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:02 +0000 (UTC) Date: Wed, 14 Feb 2024 08:45:50 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 03/12] reftable/merged: advance subiter on subsequent iteration Message-ID: <38d45995662ba92f4b985b82deac298446274511.1707895758.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When advancing the merged iterator, we pop the top-most entry from its priority queue and then advance the sub-iterator that the entry belongs to, adding the result as a new entry. This is quite sensible in the case where the merged iterator is used to actual iterate through records. But the merged iterator is also used when we look up a single record, only, so advancing the sub-iterator is wasted effort because we would never even look at the result. Instead of immediately advancing the sub-iterator, we can also defer this to the next iteration of the merged iterator by storing the intent-to-advance. This results in a small speedup when reading many records. The following benchmark creates 10000 refs, which will also end up with many ref lookups: Benchmark 1: update-ref: create many refs (revision = HEAD~) Time (mean ± σ): 337.2 ms ± 7.3 ms [User: 200.1 ms, System: 136.9 ms] Range (min … max): 329.3 ms … 373.2 ms 100 runs Benchmark 2: update-ref: create many refs (revision = HEAD) Time (mean ± σ): 332.5 ms ± 5.9 ms [User: 197.2 ms, System: 135.1 ms] Range (min … max): 327.6 ms … 359.8 ms 100 runs Summary update-ref: create many refs (revision = HEAD) ran 1.01 ± 0.03 times faster than update-ref: create many refs (revision = HEAD~) While this speedup alone isn't really worth it, this refactoring will also allow two additional optimizations in subsequent patches. First, it will allow us to special-case when there is only a single sub-iter left to circumvent the priority queue altogether. And second, it makes it easier to avoid copying records to the caller. Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 26 ++++++++++++-------------- 1 file changed, 12 insertions(+), 14 deletions(-) diff --git a/reftable/merged.c b/reftable/merged.c index 12ebd732e8..9b1ccfff00 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -19,11 +19,12 @@ license that can be found in the LICENSE file or at struct merged_iter { struct reftable_iterator *stack; + struct merged_iter_pqueue pq; uint32_t hash_id; size_t stack_len; uint8_t typ; int suppress_deletions; - struct merged_iter_pqueue pq; + ssize_t advance_index; }; static int merged_iter_init(struct merged_iter *mi) @@ -96,13 +97,17 @@ static int merged_iter_next_entry(struct merged_iter *mi, struct pq_entry entry = { 0 }; int err = 0; + if (mi->advance_index >= 0) { + err = merged_iter_advance_subiter(mi, mi->advance_index); + if (err < 0) + return err; + mi->advance_index = -1; + } + if (merged_iter_pqueue_is_empty(mi->pq)) return 1; entry = merged_iter_pqueue_remove(&mi->pq); - err = merged_iter_advance_subiter(mi, entry.index); - if (err < 0) - return err; /* One can also use reftable as datacenter-local storage, where the ref @@ -116,14 +121,6 @@ static int merged_iter_next_entry(struct merged_iter *mi, struct pq_entry top = merged_iter_pqueue_top(mi->pq); int cmp; - /* - * When the next entry comes from the same queue as the current - * entry then it must by definition be larger. This avoids a - * comparison in the most common case. - */ - if (top.index == entry.index) - break; - cmp = reftable_record_cmp(&top.rec, &entry.rec); if (cmp > 0) break; @@ -137,6 +134,7 @@ static int merged_iter_next_entry(struct merged_iter *mi, reftable_record_release(rec); *rec = entry.rec; + mi->advance_index = entry.index; done: if (err) @@ -160,9 +158,8 @@ static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec) static int merged_iter_next_void(void *p, struct reftable_record *rec) { struct merged_iter *mi = p; - if (merged_iter_pqueue_is_empty(mi->pq)) + if (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0) return 1; - return merged_iter_next(mi, rec); } @@ -255,6 +252,7 @@ static int merged_table_seek_record(struct reftable_merged_table *mt, .typ = reftable_record_type(rec), .hash_id = mt->hash_id, .suppress_deletions = mt->suppress_deletions, + .advance_index = -1, }; struct merged_iter *p; int err; From patchwork Wed Feb 14 07:45:54 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556042 Received: from wout1-smtp.messagingengine.com (wout1-smtp.messagingengine.com [64.147.123.24]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1915312B8A for ; Wed, 14 Feb 2024 07:45:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.24 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896760; cv=none; b=t4cXrjdZnRKt1pfWo/oB6K0IEdHES903uPD8q1G/RDqCfAuHqT/DGWPV0lEKUlXd7dWCCzsfajvzEhueYPtczIJddc79DjEEIRmDeUA6Gu83COFczg9jo9J5IagJMod/OfSzLYE2/tmn27/aV+gTvzqoIlhmmNjqBWZyEvTd6u8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896760; c=relaxed/simple; bh=OCPPRx0nBlbxQNz35my3h5Ls+3QdZOXu20q5fV7zCg0=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=gSMtTS71hyFsmGq7apP8jn/H3B7NBBGtlsV+gK+OS2Y5UqF+Dyu6uWqGQJimWDxbiZqifY4NyqRTgBmM7RP5z6AKe7MFCVzuiMWPuoj0Ut2XsoIeVOd5teDudYl7bFnHZoGzvp1kPc/bv+b4AKVMMqgh2mJ4NJf3gJGUQY0GSXw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=KXhZlcWz; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=ajOATwk4; arc=none smtp.client-ip=64.147.123.24 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="KXhZlcWz"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="ajOATwk4" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id 3935532009B5 for ; Wed, 14 Feb 2024 02:45:57 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute1.internal (MEProxy); Wed, 14 Feb 2024 02:45:57 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896756; x=1707983156; bh=UuarB80NsG bbbRjpH9TeJXYRHgWU/EujF9icdvH0mdY=; b=KXhZlcWzLLECHYJk2ZAzjASkAG uaDTiiMO9XW4O9WLJwWe7TtO3Pjxz09YBRDILuhHmrfslPfE37NI88NVglbjHpkf 8gw0u5tdRQgw14EQaVBfGJ0+/WMbsD0WBJGaQoZ3HRt49r8+oNrM93u1mWV8umig HFf+T/JS8K/8FkSkY/3q3MareXZLDrwSplDw/RGyC96lxjxVZNcDgWCpl8yRdSO3 +0+oEmlPkYG0waRKVL+8SiRs74kODWcdBWfku/iQU4CkNhCbtvaEELj6Hxm5rVOd nfRxYZ/3BCQszC87hSYiZd/VB+2JEjJPJ43q+RCBggyb0nI7Mu5TrIl9/0pw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896756; x=1707983156; bh=UuarB80NsGbbbRjpH9TeJXYRHgWU /EujF9icdvH0mdY=; b=ajOATwk4Q4caqN3rYgLc/tJEBnjm8QD2wVJ7Ai2Yfxr6 Ohdom/08daSGrDweJh8ljvGYcVWyOOCQN2Y2DYdYiScWjtZvKF9OhdRlaEuh3xAx 9A+smyN+lOCmvuDuVCgWQrsbKvQy2PTNsqJ6N3PfLb4pxDdyrBTiLIOmwxI20LwU TF+HqTSSu05wuRnNKirTfdoXB6aRNcvDKFGp93edZsGoB0QHe2R7iodd69iffInj tmdmlZWxIzqhTaeGBDIR+B3ydQySarNx6Z/wn614xyS+Y6CnXXOFiPtetp0ssrjp Q33CEhtozF+mxO9xMgXqLSmGMKcgL0aBp7gr3u55Yg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:45:56 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 36ba47a5 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:06 +0000 (UTC) Date: Wed, 14 Feb 2024 08:45:54 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 04/12] reftable/merged: make subiters own their records Message-ID: <2c51c60d165f5bb4e998c8b5dbb33be72e54d8a8.1707895758.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: For each subiterator, the merged table needs to track their current record. This record is owned by the priority queue though instead of by the merged iterator. This is not optimal performance-wise. For one, we need to move around records whenever we add or remove a record from the priority queue. Thus, the bigger the entries the more bytes we need to copy around. And compared to pointers, a reftable record is rather on the bigger side. The other issue is that this makes it harder to reuse the records. Refactor the code so that the merged iterator tracks ownership of the records per-subiter. Instead of having records in the priority queue, we can now use mere pointers to the per-subiter records. This also allows us to swap records between the caller and the per-subiter record instead of doing an actual copy via `reftable_record_copy_from()`, which removes the need to release the caller-provided record. This results in a noticeable speedup when iterating through many refs. The following benchmark iterates through 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 145.5 ms ± 4.5 ms [User: 142.5 ms, System: 2.8 ms] Range (min … max): 141.3 ms … 177.0 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 139.0 ms ± 4.7 ms [User: 136.1 ms, System: 2.8 ms] Range (min … max): 134.2 ms … 182.2 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) This refactoring also allows a subsequent refactoring where we start reusing memory allocated by the reftable records because we do not need to release the caller-provided record anymore. Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 54 ++++++++++++++++++++++++---------------------- reftable/pq.c | 8 ++----- reftable/pq.h | 2 +- reftable/pq_test.c | 41 ++++++++++++++++------------------- 4 files changed, 49 insertions(+), 56 deletions(-) diff --git a/reftable/merged.c b/reftable/merged.c index 9b1ccfff00..ae74234472 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -17,8 +17,13 @@ license that can be found in the LICENSE file or at #include "reftable-error.h" #include "system.h" +struct merged_subiter { + struct reftable_iterator iter; + struct reftable_record rec; +}; + struct merged_iter { - struct reftable_iterator *stack; + struct merged_subiter *subiters; struct merged_iter_pqueue pq; uint32_t hash_id; size_t stack_len; @@ -32,16 +37,18 @@ static int merged_iter_init(struct merged_iter *mi) for (size_t i = 0; i < mi->stack_len; i++) { struct pq_entry e = { .index = i, + .rec = &mi->subiters[i].rec, }; int err; - reftable_record_init(&e.rec, mi->typ); - err = iterator_next(&mi->stack[i], &e.rec); + reftable_record_init(&mi->subiters[i].rec, mi->typ); + err = iterator_next(&mi->subiters[i].iter, + &mi->subiters[i].rec); if (err < 0) return err; if (err > 0) { - reftable_iterator_destroy(&mi->stack[i]); - reftable_record_release(&e.rec); + reftable_iterator_destroy(&mi->subiters[i].iter); + reftable_record_release(&mi->subiters[i].rec); continue; } @@ -56,9 +63,11 @@ static void merged_iter_close(void *p) struct merged_iter *mi = p; merged_iter_pqueue_release(&mi->pq); - for (size_t i = 0; i < mi->stack_len; i++) - reftable_iterator_destroy(&mi->stack[i]); - reftable_free(mi->stack); + for (size_t i = 0; i < mi->stack_len; i++) { + reftable_iterator_destroy(&mi->subiters[i].iter); + reftable_record_release(&mi->subiters[i].rec); + } + reftable_free(mi->subiters); } static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi, @@ -66,17 +75,16 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi, { struct pq_entry e = { .index = idx, + .rec = &mi->subiters[idx].rec, }; int err; - reftable_record_init(&e.rec, mi->typ); - err = iterator_next(&mi->stack[idx], &e.rec); + err = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec); if (err < 0) return err; - if (err > 0) { - reftable_iterator_destroy(&mi->stack[idx]); - reftable_record_release(&e.rec); + reftable_iterator_destroy(&mi->subiters[idx].iter); + reftable_record_release(&mi->subiters[idx].rec); return 0; } @@ -86,7 +94,7 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi, static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx) { - if (iterator_is_null(&mi->stack[idx])) + if (iterator_is_null(&mi->subiters[idx].iter)) return 0; return merged_iter_advance_nonnull_subiter(mi, idx); } @@ -121,25 +129,19 @@ static int merged_iter_next_entry(struct merged_iter *mi, struct pq_entry top = merged_iter_pqueue_top(mi->pq); int cmp; - cmp = reftable_record_cmp(&top.rec, &entry.rec); + cmp = reftable_record_cmp(top.rec, entry.rec); if (cmp > 0) break; merged_iter_pqueue_remove(&mi->pq); err = merged_iter_advance_subiter(mi, top.index); if (err < 0) - goto done; - reftable_record_release(&top.rec); + return err; } - reftable_record_release(rec); - *rec = entry.rec; mi->advance_index = entry.index; - -done: - if (err) - reftable_record_release(&entry.rec); - return err; + SWAP(*rec, *entry.rec); + return 0; } static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec) @@ -257,10 +259,10 @@ static int merged_table_seek_record(struct reftable_merged_table *mt, struct merged_iter *p; int err; - REFTABLE_CALLOC_ARRAY(merged.stack, mt->stack_len); + REFTABLE_CALLOC_ARRAY(merged.subiters, mt->stack_len); for (size_t i = 0; i < mt->stack_len; i++) { err = reftable_table_seek_record(&mt->stack[i], - &merged.stack[merged.stack_len], rec); + &merged.subiters[merged.stack_len].iter, rec); if (err < 0) goto out; if (!err) diff --git a/reftable/pq.c b/reftable/pq.c index e0ccce2b97..0074d6bc43 100644 --- a/reftable/pq.c +++ b/reftable/pq.c @@ -14,7 +14,7 @@ license that can be found in the LICENSE file or at int pq_less(struct pq_entry *a, struct pq_entry *b) { - int cmp = reftable_record_cmp(&a->rec, &b->rec); + int cmp = reftable_record_cmp(a->rec, b->rec); if (cmp == 0) return a->index > b->index; return cmp < 0; @@ -82,10 +82,6 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry void merged_iter_pqueue_release(struct merged_iter_pqueue *pq) { - int i = 0; - for (i = 0; i < pq->len; i++) { - reftable_record_release(&pq->heap[i].rec); - } FREE_AND_NULL(pq->heap); - pq->len = pq->cap = 0; + memset(pq, 0, sizeof(*pq)); } diff --git a/reftable/pq.h b/reftable/pq.h index 9e25a43a36..ce23972c16 100644 --- a/reftable/pq.h +++ b/reftable/pq.h @@ -13,7 +13,7 @@ license that can be found in the LICENSE file or at struct pq_entry { size_t index; - struct reftable_record rec; + struct reftable_record *rec; }; struct merged_iter_pqueue { diff --git a/reftable/pq_test.c b/reftable/pq_test.c index c202eff848..b7d3c80cc7 100644 --- a/reftable/pq_test.c +++ b/reftable/pq_test.c @@ -27,48 +27,43 @@ void merged_iter_pqueue_check(struct merged_iter_pqueue pq) static void test_pq(void) { - char *names[54] = { NULL }; - int N = ARRAY_SIZE(names) - 1; - struct merged_iter_pqueue pq = { NULL }; + struct reftable_record recs[54]; + int N = ARRAY_SIZE(recs) - 1, i; char *last = NULL; - int i = 0; for (i = 0; i < N; i++) { - char name[100]; - snprintf(name, sizeof(name), "%02d", i); - names[i] = xstrdup(name); + struct strbuf refname = STRBUF_INIT; + strbuf_addf(&refname, "%02d", i); + + reftable_record_init(&recs[i], BLOCK_TYPE_REF); + recs[i].u.ref.refname = strbuf_detach(&refname, NULL); } i = 1; do { - struct pq_entry e = { .rec = { .type = BLOCK_TYPE_REF, - .u.ref = { - .refname = names[i], - } } }; + struct pq_entry e = { + .rec = &recs[i], + }; + merged_iter_pqueue_add(&pq, &e); merged_iter_pqueue_check(pq); + i = (i * 7) % N; } while (i != 1); while (!merged_iter_pqueue_is_empty(pq)) { struct pq_entry e = merged_iter_pqueue_remove(&pq); - struct reftable_record *rec = &e.rec; merged_iter_pqueue_check(pq); - EXPECT(reftable_record_type(rec) == BLOCK_TYPE_REF); - if (last) { - EXPECT(strcmp(last, rec->u.ref.refname) < 0); - } - /* this is names[i], so don't dealloc. */ - last = rec->u.ref.refname; - rec->u.ref.refname = NULL; - reftable_record_release(rec); - } - for (i = 0; i < N; i++) { - reftable_free(names[i]); + EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF); + if (last) + EXPECT(strcmp(last, e.rec->u.ref.refname) < 0); + last = e.rec->u.ref.refname; } + for (i = 0; i < N; i++) + reftable_record_release(&recs[i]); merged_iter_pqueue_release(&pq); } From patchwork Wed Feb 14 07:45:59 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556043 Received: from wfhigh4-smtp.messagingengine.com (wfhigh4-smtp.messagingengine.com [64.147.123.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B089312E4E for ; Wed, 14 Feb 2024 07:46:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896768; cv=none; b=fo4EVjBylCspaW9Gc4hoIPUAZre/NYREBxO2mPPzC6BuEeOGFMkFggFxU0OHTYKIG8WNGXHDLU8wq1h//5GFp0kaW+jJuJcBMrddjsRbSYnXSYjrzm7/Saste+k4fBF+z+8wg2CXE36TzN3D2d6x9Q87u6kf1sas5tn/RJDIWhY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896768; c=relaxed/simple; bh=Y290ijkN9Bc0qwetvK+wIfYsTn02NVFMmyKM7F446VE=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=fki31JgZDUr/+FVon6D7pfBb1gKsmy3+w9Bp3WEf/lVyi8w1sdymkcsQbXQz7lPUsIGo+CmJP5gm1sP3m8n6sE/O/anKJabnjsRrfQtxcLh7YuEZkPDmmQJohgxTzvvDhu40KEU85OBtBS7EcjsE6l5AvX9kWWqEkxvKVPfIl+c= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=kxI8FhxF; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=xzO6sHxr; arc=none smtp.client-ip=64.147.123.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="kxI8FhxF"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="xzO6sHxr" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailfhigh.west.internal (Postfix) with ESMTP id CBD84180008A for ; Wed, 14 Feb 2024 02:46:01 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Wed, 14 Feb 2024 02:46:01 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896761; x=1707983161; bh=3xsv1JJJY5 Azj8zuYFWG0QjCyygIAZ/MY6k2HLFXyEg=; b=kxI8FhxFjGm0STJnbYg2OPkP7a m8XUdCIU4qcf7MdDOVlR9Lv0xchgLlpCFt45t6CnaSxf1wVqZNLRyurI0Q2UCiuP YTA/BJKYBdOp2VlZ2oirGHyFwoGeh2M2d6U/W2LREW8R+TABs8F1WHxqy2xNpkkz 3DKa5AFXP9AIBY+tWodaKvxnh/V9ssCErkQun08g4YKpb+GW4IVySGEx8mxRoA9O SYuEkKnPHzd0PTfWCJGO2nudBw5UeDeiK/YdldfoAGJZ+iJ8LDmiu+9vhOUPA8K8 vWUuRnmIR9LroY5aPQpWFS1ETr0iULNuBtlfVdDwfjy9jtfAkrI6nQjTVx5g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896761; x=1707983161; bh=3xsv1JJJY5Azj8zuYFWG0QjCyygI AZ/MY6k2HLFXyEg=; b=xzO6sHxrrpQBr0ztriLFGsVYj1kfBGqt33rjjVZpsi5R jlyzZE+JEYOyfBq3MB7EBLFHQc1HD9QTP0zQKF/0/Q5mwrJrerfhvKkajQUHJWh+ ZKj+A3MrD/SzN/UWUXDE2y7SS4VJY4MqQGpqkoaAGaVoHEzde72/Ah/iFdToA+un UTTrrwQh/HiteRLfMf1WLlnXf91UwAlKk4NHX1kQmr7DLyOBaC2WAYLaFX9kQV9R za5Ek/FO2MLNudUkf5T1ETqBDV7OHyvYwm9TZj+piIkYPwzr8gCyGCm2odNw91E+ EExwAAZUHCFib49wXhziBI0IJX6NzgY5ka5WK1DEsg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudegucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:00 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 63fa9964 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:11 +0000 (UTC) Date: Wed, 14 Feb 2024 08:45:59 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 05/12] reftable/merged: remove unnecessary null check for subiters Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Whenever we advance a subiter we first call `iterator_is_null()`. This is not needed though because we only ever advance subiters which have entries in the priority queue, and we do not end entries to the priority queue when the subiter has been exhausted. Drop the check as well as the now-unused function. This results in a surprisingly big speedup: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 138.1 ms ± 4.4 ms [User: 135.1 ms, System: 2.8 ms] Range (min … max): 133.4 ms … 167.3 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 134.4 ms ± 4.2 ms [User: 131.5 ms, System: 2.8 ms] Range (min … max): 130.0 ms … 164.0 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.03 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/iter.c | 5 ----- reftable/iter.h | 4 ---- reftable/merged.c | 10 +--------- 3 files changed, 1 insertion(+), 18 deletions(-) diff --git a/reftable/iter.c b/reftable/iter.c index 8b5ebf6183..7aa30c4a51 100644 --- a/reftable/iter.c +++ b/reftable/iter.c @@ -16,11 +16,6 @@ license that can be found in the LICENSE file or at #include "reader.h" #include "reftable-error.h" -int iterator_is_null(struct reftable_iterator *it) -{ - return !it->ops; -} - static void filtering_ref_iterator_close(void *iter_arg) { struct filtering_ref_iterator *fri = iter_arg; diff --git a/reftable/iter.h b/reftable/iter.h index 47d67d84df..537431baba 100644 --- a/reftable/iter.h +++ b/reftable/iter.h @@ -16,10 +16,6 @@ license that can be found in the LICENSE file or at #include "reftable-iterator.h" #include "reftable-generic.h" -/* Returns true for a zeroed out iterator, such as the one returned from - * iterator_destroy. */ -int iterator_is_null(struct reftable_iterator *it); - /* iterator that produces only ref records that point to `oid` */ struct filtering_ref_iterator { int double_check; diff --git a/reftable/merged.c b/reftable/merged.c index ae74234472..29ad09f3d8 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -70,8 +70,7 @@ static void merged_iter_close(void *p) reftable_free(mi->subiters); } -static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi, - size_t idx) +static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx) { struct pq_entry e = { .index = idx, @@ -92,13 +91,6 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi, return 0; } -static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx) -{ - if (iterator_is_null(&mi->subiters[idx].iter)) - return 0; - return merged_iter_advance_nonnull_subiter(mi, idx); -} - static int merged_iter_next_entry(struct merged_iter *mi, struct reftable_record *rec) { From patchwork Wed Feb 14 07:46:03 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556044 Received: from wfhigh4-smtp.messagingengine.com (wfhigh4-smtp.messagingengine.com [64.147.123.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4BEA212E50 for ; Wed, 14 Feb 2024 07:46:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896768; cv=none; b=PQdfPSVo6MY/QQI8MDESzJ/RQTv+GUJ/KVp+w73LiY7Hp1vsW5OrK3UwLbv6fdQZGih0vrFOyD3KFMoGvlomKloqQU6Zm89aovP5jocnBXRXpTRzPkTUVE4XgJv8geX8l8SE59zzzyj7CgF+H4G1dGH0n+zKljr0GwWvXNhi8QE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896768; c=relaxed/simple; bh=mJkPpMIYAuBU1ZyIxtCPyVrvPjKQIesCgXC15nrN1Ro=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=HfsCxZlw51PvUS3V9OL2OrnS1Op+P2esfSddY0fhIQfLqY2Lw7M3p3Wv6aPyFK3sxcmU6Dwo3dLsyaNiS4rtUBxsWrBL3bX5WaBKIIdrIPF5ZfOtIDx/rtYhm7YzS99NlQc3QooAmWpHiLiwZy4RQdOJyihST4EO3l4522oOltQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=RIy4VDym; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=W+gGujwT; arc=none smtp.client-ip=64.147.123.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="RIy4VDym"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="W+gGujwT" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailfhigh.west.internal (Postfix) with ESMTP id 689A918000B6 for ; Wed, 14 Feb 2024 02:46:06 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute1.internal (MEProxy); Wed, 14 Feb 2024 02:46:06 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896765; x=1707983165; bh=TNkvZ3MKBq 5ux9qI69ZzlOVt3vR+Ps6mJQCLj0g1JS0=; b=RIy4VDymVgCYrVOzsJwf0mLCVx J7tlhfJP9YDjQI1uAaiwyT/lzZTPswUaneBAiwRxCMPufIPZaq/B55WM9Ebbf+iz Y8b+RqSDVDr+3utUyi7fK5JJIQHLqNy6OMYCAqqFh4u/kDcSclIAZmihG2a/rJp1 psZuDj85y18AQED/BE5wUMb3Z15b2fL0BVUx0wDHBPUtDrZVNhH+o5j7Np6U4Z3J M/uy11nqxFa4iBa5JeUAju4dVTGCPrHs77jCHANV1yMLkP0pQGVZYT+5Kyc1XKCc 9NGTLLqaQm3I637GYY8S+QbVTOSBpHq9Z0f0hoNPPzGJkOIVGiaym3XxzLaQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896765; x=1707983165; bh=TNkvZ3MKBq5ux9qI69ZzlOVt3vR+ Ps6mJQCLj0g1JS0=; b=W+gGujwTuQgVwfqaf5mPBP8jeugZkkF5AMOftgbreiLi qDI9RSUX/9XXQvkNrDNVCpRjp9b4O6SaXpQddef21NyAUB3FDBjDlj1T6re4UFqa u6t8GLREveABvxuVEXTLTREfsBdm3WqJpElg9gmlo5Irx1rTjXIQAu222AbGR8Pm gh2FKFNKqVkZJ8NIE26dc4XasDLrYEg8J1P0CBmTlYUE3ha5abVmtDOf9XJSqUDk X3PHAOi5UZqzNdiTcm7V5VSiG8tp3t2c/qf43LSEnoGV5YiZagoM7kUeo/4Ml3Vt ZlazptfpGJCT0NbNh3vkfmFA8okJCOs7CniwB6jh6g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtvdenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhepheeghfdtfeeuffehkefgffduleffjedthf dvjeektdfhhedvlefgtefgvdettdfhnecuvehluhhsthgvrhfuihiivgepudenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:05 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id bb2c42f5 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:15 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:03 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 06/12] reftable/merged: handle subiter cleanup on close only Message-ID: <4e50ac655064481691b71f70a9265185976ccbeb.1707895758.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When advancing one of the subiters fails we immediately release resources associated with that subiter. This is not necessary though as we will release these resources when closing the merged iterator anyway. Drop the logic and only release resources when the merged iterator is done. This is a mere cleanup that should help reduce the cognitive load when reading through the code. Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) diff --git a/reftable/merged.c b/reftable/merged.c index 29ad09f3d8..d9ed4a19dd 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -46,11 +46,8 @@ static int merged_iter_init(struct merged_iter *mi) &mi->subiters[i].rec); if (err < 0) return err; - if (err > 0) { - reftable_iterator_destroy(&mi->subiters[i].iter); - reftable_record_release(&mi->subiters[i].rec); + if (err > 0) continue; - } merged_iter_pqueue_add(&mi->pq, &e); } @@ -79,13 +76,8 @@ static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx) int err; err = iterator_next(&mi->subiters[idx].iter, &mi->subiters[idx].rec); - if (err < 0) + if (err) return err; - if (err > 0) { - reftable_iterator_destroy(&mi->subiters[idx].iter); - reftable_record_release(&mi->subiters[idx].rec); - return 0; - } merged_iter_pqueue_add(&mi->pq, &e); return 0; From patchwork Wed Feb 14 07:46:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556045 Received: from wfhigh4-smtp.messagingengine.com (wfhigh4-smtp.messagingengine.com [64.147.123.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B1FB1168CC for ; Wed, 14 Feb 2024 07:46:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896773; cv=none; b=OWo0q6X2U1ldeMArql4Cfrrf3TsUWOvObR+2LMI9AVEobJfgqXVE5Jk8OMwo3L2o2uYtIK1Tml/bDWY7hMFjyxN6bLCYba0OlgSjr4i+PZ48+lDeOqgBi1I2IjLh/248+Ofn9o/tvhGXPiTPZUQkr947Ck26cG2e3uH1MOJU+VI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896773; c=relaxed/simple; bh=ANFbczuAsCzg3JpM40ngEaTDRSFc5RBYMWnTVXL1/VY=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=kmKDVXe8EThgu14xqaDZt/TLeqPW5EbKXSULb/B9WVFjCp/cJTeyrepjn2dSezfMglrghy4ht0eFT66zKHXIRwM/QK9uOYLW3DMexQHf+NsE607C9hc03oJqCfDKBYF7LVGfQerocgC8x2wz2pSn40untTfPeqyCa3JtA+p8arE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=Qjxz9Zyu; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=NPncGkl/; arc=none smtp.client-ip=64.147.123.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="Qjxz9Zyu"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="NPncGkl/" Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailfhigh.west.internal (Postfix) with ESMTP id EEFDD180008A for ; Wed, 14 Feb 2024 02:46:10 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute4.internal (MEProxy); Wed, 14 Feb 2024 02:46:11 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896770; x=1707983170; bh=6DNwQUAe0G bsWIc89OIwzmdkzQv9bPfw1VVZk+fdVNI=; b=Qjxz9Zyuc5ZYclRIBNmsjGvA6B UCGs7RaMzj1vW7zpe51FpevC916w6oFUKsDINWNBkqjNNrD5oGRgt218+Koy2ZB7 +1B83md+rTYkysTIRtpo1dpvhgUWnjkzegsn9QvCs3sSeBdms4NGoM9PQDJ1GUFd b19x8z8v6gFFGEE2rUxXSuBRqILSh8xZD+ak1SrIY+9mOVKG/jo52YncT0gjjVA6 0WQaqtpwr10nviBmK5j60RAKzKYAmdNINkXjaUsNbpLzNaFwp7TN4ubHeTGIybqm KyNyGAEsEVKQgZUObGj8zhuPOhk3I1hYZO8EM3d7hkWvJ2Dv5/1hKMyEIz+w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896770; x=1707983170; bh=6DNwQUAe0GbsWIc89OIwzmdkzQv9 bPfw1VVZk+fdVNI=; b=NPncGkl/5NxXHIw9RqRfIS/k86elg5UoE6ccKdYSGRku 5VOvL3WNO96rMhr/vGM+X55uh/+3POuKLmVjPo/3QBUg6dQ0Cvc3vSXSWo7CU9pP eeIGzO1woVY1vRASFWw6Z14hAJWzAGbBmC577Sh/b8s3rO6R+F5kcutiIMmFI2Z2 f9a5CGLO+MG8+Gb88Z01gwQi7qfW62g47+WCzZpI40cxYG5lqe/gLqt8xzni2BXs Wx3RPovgypIzilylFcHf40XV6imKzrwKTV+JL2JOqfVS9i1K1TFYSH1pLekd6zGx Lscb+Rk/qk58JHFdKSzKLhhEBUjbL9cHbEdXNgdLWg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:09 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 761a623e (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:20 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:08 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 07/12] reftable/merged: circumvent pqueue with single subiter Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The merged iterator uses a priority queue to order records so that we can yielid them in the expected order. This priority queue of course comes with some overhead as we need to add, compare and remove entries in that priority queue. In the general case, that overhead cannot really be avoided. But when we have a single subiter left then there is no need to use the priority queue anymore because the order is exactly the same as what that subiter would return. While having a single subiter may sound like an edge case, it happens more frequently than one might think. In the most common scenario, you can expect a repository to have a single large table that contains most of the records and then a set of smaller tables which contain later additions to the reftable stack. In this case it is quite likely that we exhaust subiters of those smaller stacks before exhausting the large table. Special-case this and return records directly from the remaining subiter. This results in a sizeable speedup when iterating over 1m refs in a repository with a single table: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 135.4 ms ± 4.4 ms [User: 132.5 ms, System: 2.8 ms] Range (min … max): 131.0 ms … 166.3 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 126.3 ms ± 3.9 ms [User: 123.3 ms, System: 2.8 ms] Range (min … max): 122.7 ms … 157.0 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.07 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 24 ++++++++++++++++++++++-- 1 file changed, 22 insertions(+), 2 deletions(-) diff --git a/reftable/merged.c b/reftable/merged.c index d9ed4a19dd..29161a32cf 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -87,16 +87,36 @@ static int merged_iter_next_entry(struct merged_iter *mi, struct reftable_record *rec) { struct pq_entry entry = { 0 }; - int err = 0; + int err = 0, empty; + + empty = merged_iter_pqueue_is_empty(mi->pq); if (mi->advance_index >= 0) { + /* + * When there are no pqueue entries then we only have a single + * subiter left. There is no need to use the pqueue in that + * case anymore as we know that the subiter will return entries + * in the correct order already. + * + * While this may sound like a very specific edge case, it may + * happen more frequently than you think. Most repositories + * will end up having a single large base table that contains + * most of the refs. It's thus likely that we exhaust all + * subiters but the one from that base ref. + */ + if (empty) + return iterator_next(&mi->subiters[mi->advance_index].iter, + rec); + err = merged_iter_advance_subiter(mi, mi->advance_index); if (err < 0) return err; + if (!err) + empty = 0; mi->advance_index = -1; } - if (merged_iter_pqueue_is_empty(mi->pq)) + if (empty) return 1; entry = merged_iter_pqueue_remove(&mi->pq); From patchwork Wed Feb 14 07:46:13 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556046 Received: from wfout3-smtp.messagingengine.com (wfout3-smtp.messagingengine.com [64.147.123.146]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2548B171C1 for ; Wed, 14 Feb 2024 07:46:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.146 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896778; cv=none; b=fp6AQh7J3rkc6bA2YFbvfijcRu6USOLrV2Ro0GiNDu74TGp7vqYIlY2heKRNeH5MI+TT0CAt2scEvIt0FOUBUlEE8UJz1ZU0HZD+SitpqQm7PcPp10ePPiodspG8IOpPTf7u6EokVHqSSzXb3jTNioqo0E7BvDypYFex2aGS0Sg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896778; c=relaxed/simple; bh=BkriRgWFHhuRf6k9Qr6wYGWAzSySTdkHtu1uYYhMeY4=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=RDtDz5KJHQLoKEg7bPCNKuBEZYyBcdy5HbojJ7+vZ3NkkA+NwrBt4oyAN2obDuJ+yKv1+XHxkXKNF0k6O6yMgGoPfwf3C1SN2uXVjAx7S2HrAZcQispuPwgJZT79qRf0qh5QuVqjDOdirbwKagwdivge4sMnbxw8F4R+3/Okd3o= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=OFGWXQzo; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=HO86E0aZ; arc=none smtp.client-ip=64.147.123.146 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="OFGWXQzo"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="HO86E0aZ" Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailfout.west.internal (Postfix) with ESMTP id 84EEF1C0007A for ; Wed, 14 Feb 2024 02:46:16 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute7.internal (MEProxy); Wed, 14 Feb 2024 02:46:16 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896776; x=1707983176; bh=HFjvEVaHsu ydKXrQ0rx4LbNOMFNLcqCmGAFSIvvVGH4=; b=OFGWXQzorY1evhMLGl0dfbKewt kmpo3cofJuZEE1zhaXEJKyOit3/z/bj/OZgS5X9WYy700Gk0FWAwlX0omFjIrQpl kqInNUgT3dIwAITjAILrEpcaNdyBmxX+5OmikFboNCQ0hS72IQW+0udCY9dwWeMC Xml9ayi1hab52Be0JxVEaMbKfxMuAtlZkYoG0VyjAT63NV0R3WyRER0T3zYM8wmN n3y5nAxSaoDweJAOZlugITO8Bg8wjjwVdXrIgifjKJqejMWHz1SW1yZHji8NFUHP M91l5ahvn1w2M73WRMQqXpI6cK27XlB7uW5D9XNaLRmBCDM24nwBZRFc+EMg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896776; x=1707983176; bh=HFjvEVaHsuydKXrQ0rx4LbNOMFNL cqCmGAFSIvvVGH4=; b=HO86E0aZ/5HqXcRgU9uwy7TRgOR0q5VvOFwAiUzoG0WH gK+sTzz3cbIAMBWAe1sDdwdAtO0EqeHZx8hbvpqVIp19QfYTJqzrJFdll+lKNSW4 kUDPV971GV+RCdfEDx3e3Gu1Gzn1tVSw32YOh0Zxto/jD+Cl8EfmMGSPPC6de8oE nq8l3rzKUJ4c6pqWsmcqY4zo3djDiRcJ4BHEDLfodNUVDgVP4RJVniJxZfPYEfva qp8mCyFcLdbZ1l8ExIcH+0lVEt55SC7hGOiwg6M1K8D1Q7zb7dHM5MMMMzMwQCxa tLA7BTINHENMWuvD4+tEX2mMTJgvbclxUZ6o29GaCQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:15 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 09c62488 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:25 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:13 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 08/12] reftable/merged: avoid duplicate pqueue emptiness check Message-ID: <68bd6871132bac3ff8d67e908dd31647feab6bc3.1707895758.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When calling `merged_iter_next_void()` we first check whether the iter has been exhausted already. We already perform this check two levels down the stack in `merged_iter_next_entry()` though, which makes this check redundant. Now if this check was there to accellerate the common case it might have made sense to keep it. But the iterator being exhausted is rather the uncommon case because you can expect most reftable stacks to contain more than two refs. Simplify the code by removing the check. As `merged_iter_next_void()` is basically empty except for calling `merged_iter_next()` now, merge these two functions. This also results in a tiny speedup when iterating over many refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 125.6 ms ± 3.8 ms [User: 122.7 ms, System: 2.8 ms] Range (min … max): 122.4 ms … 153.4 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 124.0 ms ± 3.9 ms [User: 121.1 ms, System: 2.8 ms] Range (min … max): 120.1 ms … 156.4 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.01 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 20 ++++++-------------- 1 file changed, 6 insertions(+), 14 deletions(-) diff --git a/reftable/merged.c b/reftable/merged.c index 29161a32cf..f85a24c678 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -148,27 +148,19 @@ static int merged_iter_next_entry(struct merged_iter *mi, return 0; } -static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec) +static int merged_iter_next_void(void *p, struct reftable_record *rec) { + struct merged_iter *mi = p; while (1) { int err = merged_iter_next_entry(mi, rec); - if (err == 0 && mi->suppress_deletions && - reftable_record_is_deletion(rec)) { + if (err) + return err; + if (mi->suppress_deletions && reftable_record_is_deletion(rec)) continue; - } - - return err; + return 0; } } -static int merged_iter_next_void(void *p, struct reftable_record *rec) -{ - struct merged_iter *mi = p; - if (merged_iter_pqueue_is_empty(mi->pq) && mi->advance_index < 0) - return 1; - return merged_iter_next(mi, rec); -} - static struct reftable_iterator_vtable merged_iter_vtable = { .next = &merged_iter_next_void, .close = &merged_iter_close, From patchwork Wed Feb 14 07:46:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556047 Received: from wfhigh4-smtp.messagingengine.com (wfhigh4-smtp.messagingengine.com [64.147.123.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CA60A17571 for ; Wed, 14 Feb 2024 07:46:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896784; cv=none; b=DzPNoyZGbbLYmIUaFZBws4fJylT33C1eiIE9WYOEq9EKLHkTXj7GM5VJIvyNYiQdbYZMosof+sI5uUjEixUPT7jk7WWcXJTepEgjjnrpn5qA/78WRd8115PgM6AJAfNQz/ruRxgixWvdYkcNaBgOebquJqpFJBKKvpdxMRCmv1w= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896784; c=relaxed/simple; bh=G2NUbDP2gqkH3v3UKakEsuin5QfvJpKGTxxEH9+ueHs=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Fe/Hd2qdbbQ5HJEoIrM1cVyYbFf+cxgOjZM8idbnPxSN/zgLVacnjcHJSmhhFT8fgfXyPyr7vt+dQb8rfJIxpoRQ+rRELnt9SS0ui6x37NZKY+2KAP2KF0VcjuPun2ZZjEGiMaeI0Sby9cc7KNy9hnbdwDFO41T/Nszof9W48O0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=XeoYQiJT; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=mkb+gsyJ; arc=none smtp.client-ip=64.147.123.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="XeoYQiJT"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="mkb+gsyJ" Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailfhigh.west.internal (Postfix) with ESMTP id 188C41800096 for ; Wed, 14 Feb 2024 02:46:22 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute3.internal (MEProxy); Wed, 14 Feb 2024 02:46:22 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896781; x=1707983181; bh=dJgMVSOI73 4rvMz+y6cllQKTHGvA+mRWKxx90rhlWqo=; b=XeoYQiJTdQfizH1OAztqG7qZRC vn+Klmb12LsmvZRToDhN1WSSuA4yhdAzoiQoNURRaMieMK2ZNSM/sS60roYB5RRe T5EpZFeV4NuhtvxupkfovCCubinBjtqgNV49JRWn4lyCfZpYasEi60UpHc5b6n3a CLfLN7/fvHM8lWO6Womw2eB/ZQvWk87RLt6HG7RbZw0wjE9MsvpwKicVr+GciCi3 Ew18OkzwXB+vOLAAth2o5Dk024qH25WKR/olQiLE0komv+ICdhSZv+gFqnzeqQMm 7bWPboqkwwgk6drTSZSwAt0Ic9SSG6WEj0297yEijh8Lpkelou5tBUOM983A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896781; x=1707983181; bh=dJgMVSOI734rvMz+y6cllQKTHGvA +mRWKxx90rhlWqo=; b=mkb+gsyJ9RJYFoBZiCPD7Y1AZueklCSIwUXw0ddaj1Dr Y2tUWo3Z6pBQPl3wyM4VKTj+QI3dLFuLDX8hXXyASpQV+jqfZxEHgY+BvMVQU8+/ z1Q+BclXj8FLl27OyzGdmuejngQW36O6Tb9fw4cUFwRAjtzkfKKl+D0w22kPXy02 GYgo/ZUz1g0TxiqGZEbXhRpLmDmQazFbrdgAwCt7wpwAU3wwyMr0FmgnL3gP/nkH j7THLFeE8o28qFsPSK/OZScfumSv7Ka2Lsk16cc8XA2hj9vLaIdbKEJJKNEztJeH /UjDddOnTGFatn5eY+N6Yy3id/5SQG2E6n9IPfY+kw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgeptdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:20 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 80a83c27 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:31 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:19 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 09/12] reftable/record: reuse refname when decoding Message-ID: <3ba697036c1db3837f46775823a7bd55602b4bac.1707895758.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When decoding a reftable record we will first release the user-provided record and then decode the new record into it. This is quite inefficient as we basically need to reallocate at least the refname every time. Refactor the function to start tracking the refname capacity. Like this, we can stow away the refname, release, restore and then grow the refname to the required number of bytes via `REFTABLE_ALLOC_GROW()`. This refactoring is safe to do because all functions that assigning to the refname will first call `release_reftable_record()`, which will zero out the complete record after releasing memory. This change results in a nice speedup when iterating over 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 124.0 ms ± 3.9 ms [User: 121.1 ms, System: 2.7 ms] Range (min … max): 120.4 ms … 152.7 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 114.4 ms ± 3.7 ms [User: 111.5 ms, System: 2.7 ms] Range (min … max): 111.0 ms … 152.1 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.08 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Furthermore, with this change we now perform a mostly constant number of allocations when iterating. Before this change: HEAP SUMMARY: in use at exit: 13,603 bytes in 125 blocks total heap usage: 1,006,620 allocs, 1,006,495 frees, 25,398,363 bytes allocated After this change: HEAP SUMMARY: in use at exit: 13,603 bytes in 125 blocks total heap usage: 6,623 allocs, 6,498 frees, 509,592 bytes allocated Signed-off-by: Patrick Steinhardt --- reftable/record.c | 16 ++++++++++++---- reftable/reftable-record.h | 1 + 2 files changed, 13 insertions(+), 4 deletions(-) diff --git a/reftable/record.c b/reftable/record.c index d6bb42e887..e800cfef00 100644 --- a/reftable/record.c +++ b/reftable/record.c @@ -368,16 +368,24 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key, struct reftable_ref_record *r = rec; struct string_view start = in; uint64_t update_index = 0; - int n = get_var_int(&update_index, &in); + const char *refname = NULL; + size_t refname_cap = 0; + int n; + + assert(hash_size > 0); + + n = get_var_int(&update_index, &in); if (n < 0) return n; string_view_consume(&in, n); + SWAP(refname, r->refname); + SWAP(refname_cap, r->refname_cap); reftable_ref_record_release(r); + SWAP(refname, r->refname); + SWAP(refname_cap, r->refname_cap); - assert(hash_size > 0); - - r->refname = reftable_malloc(key.len + 1); + REFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap); memcpy(r->refname, key.buf, key.len); r->refname[key.len] = 0; diff --git a/reftable/reftable-record.h b/reftable/reftable-record.h index bb6e99acd3..e657001d42 100644 --- a/reftable/reftable-record.h +++ b/reftable/reftable-record.h @@ -22,6 +22,7 @@ license that can be found in the LICENSE file or at /* reftable_ref_record holds a ref database entry target_value */ struct reftable_ref_record { char *refname; /* Name of the ref, malloced. */ + size_t refname_cap; uint64_t update_index; /* Logical timestamp at which this value is * written */ From patchwork Wed Feb 14 07:46:24 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556048 Received: from wfout3-smtp.messagingengine.com (wfout3-smtp.messagingengine.com [64.147.123.146]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 37E2D1759F for ; Wed, 14 Feb 2024 07:46:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.146 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896788; cv=none; b=m7F5qosZyTaQqDWXb6kA/34FSL3hY/tki7T0IzHcsCst1h0rCWFOrGkjLH7H4tPSOkCJlp39k4yBS77+efSYyd+ga2kYa3r3DbBgNKhoaoQgLaMVwQp3GH/+fE3ZSZmxLwlgiA9gLZUycwHZQ2IHpOzPR6+tWyOElq3E2PG77/U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896788; c=relaxed/simple; bh=tBJoI8TBqmqvIxgRX7ufSW1+m71jPbaJHs3w56kYuZc=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=PezI+VviyWhLXU+kqWKE5jaY9AV8vxYNCyHSL8eQgueqy67c3694qdqr1d4WQ1XZmOLTwls4+J4Wyu5+8He2K1aGgP/t97sJayUNDQh6Na5Aaq/1BI6gTS399WNrGR6EFfo9jXXRgAl9HQyi/YDp3noohH6r15ss2rbMhw0ovms= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=f0NSfjwj; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=ok2SFBUO; arc=none smtp.client-ip=64.147.123.146 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="f0NSfjwj"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="ok2SFBUO" Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailfout.west.internal (Postfix) with ESMTP id 9B45B1C00077 for ; Wed, 14 Feb 2024 02:46:26 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute2.internal (MEProxy); Wed, 14 Feb 2024 02:46:26 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896786; x=1707983186; bh=VXZ+dYIkAD 6Emn9akeQuJcCgj3wNJGheR+4+iQ71GLg=; b=f0NSfjwjj/lyY6OpTUjps98TW8 1IhnH/JNbLM7Caw8MBhXXvTNjPgduwe+R91NMQa7ywQyRlqZ2lk8Xh3/nGwHQ+G8 i+/b1JLQtSbTAReAZZ2HKvfQg/iK+Ie3bRyx2zlPwYVihAgftPEoHrRPXecOsvKu An4U4R+DrqmVqVraw7EhuMY6AL/CcRLyF/Hx9rarTOA3ABhqrnqhIuiN+JcAMHdd qNfiCcrMS7gx/Zka3xQ5zsGdDwcdhVu3fhzp7S57C5g4gX0GjanINKPAI80KL9l2 2k5M7i4OnN+e+vImRxWLlGSBzXQ1C1WuQAY6LfEzKNel9jS4SJQ/GLcPQ4Mw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896786; x=1707983186; bh=VXZ+dYIkAD6Emn9akeQuJcCgj3wN JGheR+4+iQ71GLg=; b=ok2SFBUO750eUUoF6jshejjWt7RWQF5HmiamGPBgWj1e wCCBC6KKhpEdSNKVkjP/cZ+JDPIBCOFIxQgfNLr2aA7dkImdf6rEMwtarhaIeZ6P hIZKslgMFlCDlH2rjl8yKjdf/bqS6bT5FXzssgakZ7KL6EZ1AnpfEFSV6qAWfv+/ TABHY0xFaI1XWFn608VcLP+FULKqAdF2GFQIETVGWTu8NId8pcDB2VqzTyc1JtHv 2zpbxdZrhzivGFqoanyNxEwOSRSmIEx/UMOcPnk2K3mpn4tPKFIItF+bApxyf/tT DRu8pv/difE3IrA3QRt1QXipdgPElpDX5mk0ep7Sbg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudegucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgepudenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:25 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 1b283d2f (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:35 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:24 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 10/12] reftable/record: reuse refname when copying Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Do the same optimization as in the preceding commit, but this time for `reftable_record_copy()`. While not as noticeable, it still results in a small speedup when iterating over 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 114.0 ms ± 3.8 ms [User: 111.1 ms, System: 2.7 ms] Range (min … max): 110.9 ms … 144.3 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 112.5 ms ± 3.7 ms [User: 109.5 ms, System: 2.8 ms] Range (min … max): 109.2 ms … 140.7 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.01 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/record.c | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/reftable/record.c b/reftable/record.c index e800cfef00..3f2a639036 100644 --- a/reftable/record.c +++ b/reftable/record.c @@ -205,14 +205,26 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec, { struct reftable_ref_record *ref = rec; const struct reftable_ref_record *src = src_rec; + char *refname = NULL; + size_t refname_cap = 0; + assert(hash_size > 0); - /* This is simple and correct, but we could probably reuse the hash - * fields. */ + SWAP(refname, ref->refname); + SWAP(refname_cap, ref->refname_cap); reftable_ref_record_release(ref); + SWAP(refname, ref->refname); + SWAP(refname_cap, ref->refname_cap); + if (src->refname) { - ref->refname = xstrdup(src->refname); + size_t refname_len = strlen(src->refname); + + REFTABLE_ALLOC_GROW(ref->refname, refname_len + 1, + ref->refname_cap); + memcpy(ref->refname, src->refname, refname_len); + ref->refname[refname_len] = 0; } + ref->update_index = src->update_index; ref->value_type = src->value_type; switch (src->value_type) { From patchwork Wed Feb 14 07:46:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556049 Received: from wfhigh4-smtp.messagingengine.com (wfhigh4-smtp.messagingengine.com [64.147.123.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E1E4C17C98 for ; Wed, 14 Feb 2024 07:46:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896793; cv=none; b=RKKCobkljHsyCp5IWie1qU6q6e/ckKNbtTyH5txpVznXsvbillV6dL8PlyvwUue64K4wl7RW09R4pm+tuAMUf7/lR2ijiiIahpmX1qimxfzQmrKVCeKDP+jQi8OgVrwkAUQFunsokv3w9OcTRLcv9i5/p6LBPbFZYjn13i9Fsno= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896793; c=relaxed/simple; bh=5TD8+uj6sEL+WXfnhOcB7/4mwG2t2HyplzoLoaqpnY0=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=YPwTlRoFWDTn8fRwPmYAdme1H/JpDiMsfz8v1C1m2V/N5gakayJw9DJcqGcEch5Gjj8cxLTGlDkxf0vQSxnrqcxi58gGsfXmXdqqXakRSQhkLg66DvLFMOjgcSXHPihHu7/eUgvmZzogz0LkUmyfgCx0XDiDSikl00cWCzPrfC4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=mEXJ5G5c; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=oSvdH/oa; arc=none smtp.client-ip=64.147.123.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="mEXJ5G5c"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="oSvdH/oa" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailfhigh.west.internal (Postfix) with ESMTP id 2FE8C18000B5 for ; Wed, 14 Feb 2024 02:46:31 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Wed, 14 Feb 2024 02:46:31 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896790; x=1707983190; bh=GdJ8OdPv7V VLuipkGUIJ2qtYMm5n9XB0c1BjPq59wn8=; b=mEXJ5G5c/Gh1DfCb4MiqKIWEYx 1ic4l3OOPL19RKJVoqdkE4lakuM0ulosxO8oQB+htp4+XLaiLoCckbcQVjDxedMf gbEtwO3TFdU2FK0xIlI+HTjPaZHRcGszMXFxwiRqgremoviIpfkgL9fzOUideet/ ovwe/55fllS0oUv3zXrh867qPXeh6RDIQFHe/6O7uOuUXZBjhzOji3rSyhFd5bj0 qGXV3ldD1M2iLENWSLa4H1h1ATIkSHXZTXtmIMhDT1wsu+kGy9Bgv8C+Prlw/x4f 13bljszjx0jkR+dKBU3ZFrSGPpz7yQFT1RfZrfL3cialqEUvozxWsRxQWg9Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896790; x=1707983190; bh=GdJ8OdPv7VVLuipkGUIJ2qtYMm5n 9XB0c1BjPq59wn8=; b=oSvdH/oa3jwQmmsXGHLySs4Fe03Ho55pf5mJQQe6YOk/ YAx75or6FDrFA1dof0aW5Gyf7xBaK2gIOn3wKlvWq+tAvirqNA/yfrsrbtgS2ZXJ n2THWwCYKNa+IclFv5LN4iIfoujoFhfe0KwiP8kwK5iOxIsWIMq6nxXg2TdwTRQK 6RViEdfUiotSAzwA2rPORsFedE7FtRDGZLtOTjJuvwQWQn5ddMM8oM6FiQNuWiYe +xCCfna/A2Wzi1PspEiud3kE0TJqE1czeQoi63lh1joInG8Pjv9Fxd0AiFicBKZs XBATnMIFYfo2+sotVB7vkuUtk6Gb1IIDkYy+cVHPNw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudegucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgepudenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:30 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id dc786235 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:40 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:28 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 11/12] reftable/record: decode keys in place Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When reading a record from a block, we need to decode the record's key. As reftable keys are prefix-compressed, meaning they reuse a prefix from the preceding record's key, this is a bit more involved than just having to copy the relevant bytes: we need to figure out the prefix and suffix lengths, copy the prefix from the preceding record and finally copy the suffix from the current record. This is done by passing three buffers to `reftable_decode_key()`: one buffer that holds the result, one buffer that holds the last key, and one buffer that points to the current record. The final key is then assembled by calling `strbuf_add()` twice to copy over the prefix and suffix. Performing two memory copies is inefficient though. And we can indeed do better by decoding keys in place. Instead of providing two buffers, the caller may only call a single buffer that is already pre-populated with the last key. Like this, we only have to call `strbuf_setlen()` to trim the record to its prefix and then `strbuf_add()` to add the suffix. This refactoring leads to a noticeable performance bump when iterating over 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 112.2 ms ± 3.9 ms [User: 109.3 ms, System: 2.8 ms] Range (min … max): 109.2 ms … 149.6 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 106.0 ms ± 3.5 ms [User: 103.2 ms, System: 2.7 ms] Range (min … max): 103.2 ms … 133.7 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.06 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/block.c | 25 +++++++++++-------------- reftable/block.h | 2 -- reftable/record.c | 19 +++++++++---------- reftable/record.h | 9 ++++++--- reftable/record_test.c | 3 ++- 5 files changed, 28 insertions(+), 30 deletions(-) diff --git a/reftable/block.c b/reftable/block.c index 72eb73b380..ad9074dba6 100644 --- a/reftable/block.c +++ b/reftable/block.c @@ -291,9 +291,8 @@ static int restart_key_less(size_t idx, void *args) /* the restart key is verbatim in the block, so this could avoid the alloc for decoding the key */ struct strbuf rkey = STRBUF_INIT; - struct strbuf last_key = STRBUF_INIT; uint8_t unused_extra; - int n = reftable_decode_key(&rkey, &unused_extra, last_key, in); + int n = reftable_decode_key(&rkey, &unused_extra, in); int result; if (n < 0) { a->error = 1; @@ -326,35 +325,34 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec) if (it->next_off >= it->br->block_len) return 1; - n = reftable_decode_key(&it->key, &extra, it->last_key, in); + n = reftable_decode_key(&it->last_key, &extra, in); if (n < 0) return -1; - - if (!it->key.len) + if (!it->last_key.len) return REFTABLE_FORMAT_ERROR; string_view_consume(&in, n); - n = reftable_record_decode(rec, it->key, extra, in, it->br->hash_size); + n = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size); if (n < 0) return -1; string_view_consume(&in, n); - strbuf_swap(&it->last_key, &it->key); it->next_off += start.len - in.len; return 0; } int block_reader_first_key(struct block_reader *br, struct strbuf *key) { - struct strbuf empty = STRBUF_INIT; - int off = br->header_off + 4; + int off = br->header_off + 4, n; struct string_view in = { .buf = br->block.data + off, .len = br->block_len - off, }; - uint8_t extra = 0; - int n = reftable_decode_key(key, &extra, empty, in); + + strbuf_reset(key); + + n = reftable_decode_key(key, &extra, in); if (n < 0) return n; if (!key->len) @@ -371,7 +369,6 @@ int block_iter_seek(struct block_iter *it, struct strbuf *want) void block_iter_close(struct block_iter *it) { strbuf_release(&it->last_key); - strbuf_release(&it->key); } int block_reader_seek(struct block_reader *br, struct block_iter *it, @@ -408,8 +405,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it, if (err < 0) goto done; - reftable_record_key(&rec, &it->key); - if (err > 0 || strbuf_cmp(&it->key, want) >= 0) { + reftable_record_key(&rec, &it->last_key); + if (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) { err = 0; goto done; } diff --git a/reftable/block.h b/reftable/block.h index 17481e6331..51699af233 100644 --- a/reftable/block.h +++ b/reftable/block.h @@ -84,12 +84,10 @@ struct block_iter { /* key for last entry we read. */ struct strbuf last_key; - struct strbuf key; }; #define BLOCK_ITER_INIT { \ .last_key = STRBUF_INIT, \ - .key = STRBUF_INIT, \ } /* initializes a block reader. */ diff --git a/reftable/record.c b/reftable/record.c index 3f2a639036..37682cc7d0 100644 --- a/reftable/record.c +++ b/reftable/record.c @@ -159,20 +159,19 @@ int reftable_encode_key(int *restart, struct string_view dest, return start.len - dest.len; } -int reftable_decode_key(struct strbuf *key, uint8_t *extra, - struct strbuf last_key, struct string_view in) +int reftable_decode_key(struct strbuf *last_key, uint8_t *extra, + struct string_view in) { int start_len = in.len; uint64_t prefix_len = 0; uint64_t suffix_len = 0; - int n = get_var_int(&prefix_len, &in); + int n; + + n = get_var_int(&prefix_len, &in); if (n < 0) return -1; string_view_consume(&in, n); - if (prefix_len > last_key.len) - return -1; - n = get_var_int(&suffix_len, &in); if (n <= 0) return -1; @@ -181,12 +180,12 @@ int reftable_decode_key(struct strbuf *key, uint8_t *extra, *extra = (uint8_t)(suffix_len & 0x7); suffix_len >>= 3; - if (in.len < suffix_len) + if (in.len < suffix_len || + prefix_len > last_key->len) return -1; - strbuf_reset(key); - strbuf_add(key, last_key.buf, prefix_len); - strbuf_add(key, in.buf, suffix_len); + strbuf_setlen(last_key, prefix_len); + strbuf_add(last_key, in.buf, suffix_len); string_view_consume(&in, suffix_len); return start_len - in.len; diff --git a/reftable/record.h b/reftable/record.h index a05e2be179..91c9c6ebfd 100644 --- a/reftable/record.h +++ b/reftable/record.h @@ -81,9 +81,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest, struct strbuf prev_key, struct strbuf key, uint8_t extra); -/* Decode into `key` and `extra` from `in` */ -int reftable_decode_key(struct strbuf *key, uint8_t *extra, - struct strbuf last_key, struct string_view in); +/* + * Decode into `last_key` and `extra` from `in`. `last_key` is expected to + * contain the decoded key of the preceding record, if any. + */ +int reftable_decode_key(struct strbuf *last_key, uint8_t *extra, + struct string_view in); /* reftable_index_record are used internally to speed up lookups. */ struct reftable_index_record { diff --git a/reftable/record_test.c b/reftable/record_test.c index a86cff5526..89209894d8 100644 --- a/reftable/record_test.c +++ b/reftable/record_test.c @@ -295,7 +295,8 @@ static void test_key_roundtrip(void) EXPECT(!restart); EXPECT(n > 0); - m = reftable_decode_key(&roundtrip, &rt_extra, last_key, dest); + strbuf_addstr(&roundtrip, "refs/heads/master"); + m = reftable_decode_key(&roundtrip, &rt_extra, dest); EXPECT(n == m); EXPECT(0 == strbuf_cmp(&key, &roundtrip)); EXPECT(rt_extra == extra); From patchwork Wed Feb 14 07:46:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13556050 Received: from wfhigh4-smtp.messagingengine.com (wfhigh4-smtp.messagingengine.com [64.147.123.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4A465182B5 for ; Wed, 14 Feb 2024 07:46:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896800; cv=none; b=jL6Ptd7Fr4k9mi3ENG/cmXMi4OoBUt8kHmgi+jIgt6dhuINyEFxKjM1lMB32b3okmjXIVKtvZ5TTAQC1K5jB/KAFnmR36vRrulx/QIK/25qDEBG0PUvlX6W/h0r17E7y1qGBD/FQZXVtcU6/zzt+uXE7eKlkrKAn2EDxuhhegHk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707896800; c=relaxed/simple; bh=663k2VAlLJmdXrzi0dG+UZBNaFO9JZI5q/HcImxvzwE=; h=Date:From:To:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=WINkT2hYVZCfE9WJMcBanFLUAm5voLarXnYBiaIfhWX4voXrZcJMQsNA1ysLZe4Vtzx84BRJ4vvEcJGm2XapZRIjoQU3IeUolIVzFYYrNJ3+N8rU76BPoeoI7XoyuNZ+qDJANWc9Iidqm3Hqc8bUks8927xwV6XLy2zRdCSmQQY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=GT5V8hVn; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=NBEKhNwt; arc=none smtp.client-ip=64.147.123.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="GT5V8hVn"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="NBEKhNwt" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailfhigh.west.internal (Postfix) with ESMTP id B4F9C18000B6 for ; Wed, 14 Feb 2024 02:46:37 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Wed, 14 Feb 2024 02:46:37 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1707896797; x=1707983197; bh=mvxIMSRVBQ l3HPKdWUjVQP5XHUxlJVA2gjR4UJ/mn7g=; b=GT5V8hVnXXcIk93k0o3eIrzfYC 0IbEBu6AchURk/SrOPVm+uUYKMhyny9WPGGV9c0pHYKE+WU0/lCZCyHG0pWacZJw jIf+ZuAVZgYQ9la+laudzHh3SdXRTcZXqAjo/JJQX2yPg+TctsmynMu3dTNDR1dJ zed2rqj/DUwuxatO7CHORiAB6gFzGMtgfpyUDvZ98qO4iJnM2ipApdNlWKYQgiBt w9fx4vIIeN12OAhjcPpC+HtrLskiGpKek29Zv56G+lOPgHx0Pc6RrfcVw8TQoya6 Or1i8C+OcGrpyoidwnXhnLebbBnu1VOykd6skWNUuf6sO5hSBNyHASwpDvzg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1707896797; x=1707983197; bh=mvxIMSRVBQl3HPKdWUjVQP5XHUxl JVA2gjR4UJ/mn7g=; b=NBEKhNwt9bAn54zhFwf/tsy9Ivxx6HNabVCQdOlh0D6L igE12zWHx7LoBOM+vwWboNQII1YiWEttaNxeS1Ybxb1qtaPswuFyT+VVhJ50Kxbc RUouR/oPckfSDBIaxzO8ss6T4vRgtVOOFv5kdgBJ5XXhanb1Oad1kuHx1IxK0T4k S2lBdCmBhCwOGoWiJ7txxxCxI1z59UBD8w+1No3BV+43gzehN7akDBSgbpgP3yxP l9JTYgtal20pmWOmUaplphRHkxiraiMLQbJIPjDS4NRvY1rnoJhKMwF8IDlAh1Vq UOd3/H2QwCbeqwmPOuJnBihW6NCRhuAzNSsA3n1JtQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudeigdduudegucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkfhggtggujgesghdtre ertddtjeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehp khhsrdhimheqnecuggftrfgrthhtvghrnhephefgjeeuveejteduhefgffefffdvjeefje eivdekfffgkeeugfehveetueefleeknecuvehluhhsthgvrhfuihiivgepvdenucfrrghr rghmpehmrghilhhfrhhomhepphhssehpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA for ; Wed, 14 Feb 2024 02:46:36 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id d8e0bb08 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Wed, 14 Feb 2024 07:42:47 +0000 (UTC) Date: Wed, 14 Feb 2024 08:46:35 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Subject: [PATCH 12/12] reftable: allow inlining of a few functions Message-ID: <56ec6549326e52d88e6d063ce1a9f26b2a805d09.1707895758.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: We have a few functions which are basically just accessors to structures. As those functions are executed inside the hot loop when iterating through many refs, the fact that they cannot be inlined is costing us some performance. Move the function definitions into their respective headers so that they can be inlined. This results in a performance improvement when iterating over 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 102.4 ms ± 3.7 ms [User: 99.6 ms, System: 2.7 ms] Range (min … max): 99.1 ms … 129.1 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 98.3 ms ± 3.7 ms [User: 95.4 ms, System: 2.7 ms] Range (min … max): 94.9 ms … 126.2 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.04 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/pq.c | 10 ---------- reftable/pq.h | 12 ++++++++++-- reftable/record.c | 11 ----------- reftable/record.h | 12 ++++++++++-- 4 files changed, 20 insertions(+), 25 deletions(-) diff --git a/reftable/pq.c b/reftable/pq.c index 0074d6bc43..7fb45d8c60 100644 --- a/reftable/pq.c +++ b/reftable/pq.c @@ -20,16 +20,6 @@ int pq_less(struct pq_entry *a, struct pq_entry *b) return cmp < 0; } -struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq) -{ - return pq.heap[0]; -} - -int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq) -{ - return pq.len == 0; -} - struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) { int i = 0; diff --git a/reftable/pq.h b/reftable/pq.h index ce23972c16..f796c23179 100644 --- a/reftable/pq.h +++ b/reftable/pq.h @@ -22,12 +22,20 @@ struct merged_iter_pqueue { size_t cap; }; -struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq); -int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq); void merged_iter_pqueue_check(struct merged_iter_pqueue pq); struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq); void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e); void merged_iter_pqueue_release(struct merged_iter_pqueue *pq); int pq_less(struct pq_entry *a, struct pq_entry *b); +static inline struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq) +{ + return pq.heap[0]; +} + +static inline int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq) +{ + return pq.len == 0; +} + #endif diff --git a/reftable/record.c b/reftable/record.c index 37682cc7d0..fdda28645c 100644 --- a/reftable/record.c +++ b/reftable/record.c @@ -1176,11 +1176,6 @@ void reftable_record_key(struct reftable_record *rec, struct strbuf *dest) reftable_record_vtable(rec)->key(reftable_record_data(rec), dest); } -uint8_t reftable_record_type(struct reftable_record *rec) -{ - return rec->type; -} - int reftable_record_encode(struct reftable_record *rec, struct string_view dest, int hash_size) { @@ -1302,12 +1297,6 @@ int reftable_log_record_is_deletion(const struct reftable_log_record *log) return (log->value_type == REFTABLE_LOG_DELETION); } -void string_view_consume(struct string_view *s, int n) -{ - s->buf += n; - s->len -= n; -} - static void *reftable_record_data(struct reftable_record *rec) { switch (rec->type) { diff --git a/reftable/record.h b/reftable/record.h index 91c9c6ebfd..5e8304e052 100644 --- a/reftable/record.h +++ b/reftable/record.h @@ -25,7 +25,11 @@ struct string_view { }; /* Advance `s.buf` by `n`, and decrease length. */ -void string_view_consume(struct string_view *s, int n); +static inline void string_view_consume(struct string_view *s, int n) +{ + s->buf += n; + s->len -= n; +} /* utilities for de/encoding varints */ @@ -127,7 +131,6 @@ int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b); int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size); void reftable_record_print(struct reftable_record *rec, int hash_size); void reftable_record_key(struct reftable_record *rec, struct strbuf *dest); -uint8_t reftable_record_type(struct reftable_record *rec); void reftable_record_copy_from(struct reftable_record *rec, struct reftable_record *src, int hash_size); uint8_t reftable_record_val_type(struct reftable_record *rec); @@ -138,6 +141,11 @@ int reftable_record_decode(struct reftable_record *rec, struct strbuf key, int hash_size); int reftable_record_is_deletion(struct reftable_record *rec); +static inline uint8_t reftable_record_type(struct reftable_record *rec) +{ + return rec->type; +} + /* frees and zeroes out the embedded record */ void reftable_record_release(struct reftable_record *rec);