From patchwork Tue Feb 27 15:06:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573987 Received: from wfout2-smtp.messagingengine.com (wfout2-smtp.messagingengine.com [64.147.123.145]) (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 AEDEC13B2B3 for ; Tue, 27 Feb 2024 15:06:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.145 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046383; cv=none; b=WJUhnbWIykiq2e4b8SglUmhI8GAC0tpXZq4lTlclaLK2MBRWP2C2lsDJo1fo6rDyXXDgYmreAVdgqIeH52f1VYJhYzUsFD40Y51OJ2LPYWy1LEpMl2SZTeqHoDmM/c3axn8N0RmUELWe2BAaz3wU3cSxUdiC96cmDSQ2t8xDyGM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046383; c=relaxed/simple; bh=o1x3di21jZSSV3O6HGNFTA6NGS5uGU0yhTw+vDTdEKw=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=gqEphVjUC782XmwQ3p6zFO3SpKLZK6A6zrVADoPZg55WjuXso2lS69TDOQujIY+AVb1Urnd1Ew2+mn6FhZMPiNWn1OiAhs3JV8ZE7Cq1yQPPOQMqv3fHz7aOPOR6MsKp07z9vCBPVTEBwxs+t7yRr/FORBV7cJY6r/PcR9rDZsY= 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=qac0YOWn; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=nHyMYqCC; arc=none smtp.client-ip=64.147.123.145 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="qac0YOWn"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="nHyMYqCC" Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailfout.west.internal (Postfix) with ESMTP id B82581C00076; Tue, 27 Feb 2024 10:06:20 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute2.internal (MEProxy); Tue, 27 Feb 2024 10:06:20 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046380; x=1709132780; bh=kNljyxlGd4 z8pd1D93eCcRfgr/ks1BPuuqe0Wlql4NU=; b=qac0YOWnYTxHrdRwgrdRmWYXg1 OJPQz2gaPA/BPOAbEvf7mP3Y675g/wMofjDwtpcuu9SeMGy2552mMZLq15KEqzam IPEh7ZTLg4kk/hcSYOBWgaWjFepf/Q1dokBUuEOyeznv8kJKjLJ4QAkVV1cyD/PC W4mOlTf7G7SJmYxTD+5ZpLiRVzdz1PjsI1HYAGtM0oGkISYMCme4C+ZZPQydHyCy GdDpHCDfaShrcRBJjyLYEbDYD7NjndA92iCXqRW4D/IiJ/wd5YfEDhPBxV/VhYf6 G4ScWlwlMv/fBIH00x/BWnj7eUQwDiYH/ColytnpLAoYazYnm70wwIGas00g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046380; x=1709132780; bh=kNljyxlGd4z8pd1D93eCcRfgr/ks 1BPuuqe0Wlql4NU=; b=nHyMYqCCIDNNZezv7gfWJSqoUloy24qCW+W8SuvfrLnA jkOCo/zytiOC5db+pu/I8J0bjtdzegREoqhZcWnJdeTkl9g3PtRwk5xpYvvn4MT+ vOdI6hpXPObnD4Fm+NppLHJXLn++UCBq9oa6ohkDmhs/eoBXQtIWYwwTMDaNwrQE gUQ5/mrlEUvJ6qmFjZIpL60DRpkY4kXWup2nMp1kt4sYA8JAveKmVGkDFrgtEi9Y 08xd+JTbotYOMI9av7zFV5vRq1jWBMMzSccuT0zLtf1EAbiPxPZXOf3XFEZ3+6Bh R/41RG27F568UmtqV3C8Df38GCyiuCjmLXpCag2fEw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleffteen ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:19 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 0be84a19 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:02 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:17 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 01/13] reftable/pq: use `size_t` to track iterator index Message-ID: <292e5f88889142eb29ced96010b02025b134e3ae.1709045927.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: 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 Tue Feb 27 15:06:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573988 Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (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 29420145B0D for ; Tue, 27 Feb 2024 15:06:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.25 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046388; cv=none; b=YFQ5jLOxiU9Vgu9In1bmSH9jBhO3JvljXcol6T5zYPCdxp6EMuZHdP1k2DaMdoipXa/ZfyTZmIEbShKuul6cnBA5OgOvzXNaE1LhcrngMw4kRcbVf75gjFR4DKKDr9/hIgzMkWlInHH2gaZfvvNvpjNvwZ52uMsGvIdwCOvuWk8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046388; c=relaxed/simple; bh=dXRwxPvX3ZtKz36jf/hOavFjwaqKjuDBqE+tP3ykPHQ=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=ucYuacLW6zlZQSvizp7onL/3nNWcJnIyqP/WZfB/xaUMyQkseJHdKxAcGraJgpeBDtD5g6zaEM60MgKOreT266lktKpJbW5QL2jAFAMzlohK4iTHuJWSsd/9NQTKrbnuAxYT2HnF19IA8aq1Fsxn0mfmwx3XAwgfZr/nyYh4ABA= 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=pRsCWE0N; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=OnW8E6ed; arc=none smtp.client-ip=64.147.123.25 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="pRsCWE0N"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="OnW8E6ed" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailout.west.internal (Postfix) with ESMTP id 20DC43200B8E; Tue, 27 Feb 2024 10:06:26 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Tue, 27 Feb 2024 10:06:26 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046385; x=1709132785; bh=j48CfC6/L1 wHmtjYYg57/946aqhtrahRWpXqh4yFD2Y=; b=pRsCWE0NjO0Z/m0KYYsoKi73Up ooRASAgb8Fz3XHtcclie4x/DRvdxB3m8wf9wUg6uuZNMs9TO7BVGN9oyXE2zJNBh x2bbaW3y78tTJqznJ2eOc0cxZkk+0c/ZhDGBHtcUJZpKrx4D01Np/J4xBdAxvlxd PxoJCeM1X5B3PolPmW6pMbdGaXG0HtxMIh0sK7WdoPSvYnNgQbYGMLaw40ZazhSe irMOCLkkdv+NBPANbTJnPZxbqWP4KHnm16LUfuC/k+4V7PR0NJM+U4VrxVSKTRXf IsCkkoFoE6VuVazBsiFznTgMOmy5+2k/OokLs8BUGAcbyADPLbJQI00CusYw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046385; x=1709132785; bh=j48CfC6/L1wHmtjYYg57/946aqht rahRWpXqh4yFD2Y=; b=OnW8E6edC3vlwSMxo93kVUXAqkAxibHu/r9+2pbvzW2e GGc0OET6VeTtlz/xJwzOndjakv2q8ve2JwukpCzMjcX1txwXsg/AOQi6sMhjIIoj GN9Va/ST/ljtvV4Wr2HyVtO129fBbJ4bLztC3d0mId0QSEs26VqwaAKQN0LUoI4q 9u5UaGZbtX97r2OtJgrDYJffvE1AO0G9U33usIKURQpLpHCiXp8ORuq+eHP5c/Rg 5dk3fZdyBuQq6UC1vBhsBXKSIOeivM1+a+/CFgmRMqMGY26BdqVDVBU6G0iCsUDL 15hcUfHY9bQaUpkoQ0gBEWm7QbSdfPaTaoPRpWqMSA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleffteen ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:24 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 6ede55dc (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:07 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:22 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 02/13] reftable/merged: make `merged_iter` structure private Message-ID: <95e1ccafc42aef324b5d44580d16d9463d18d371.1709045927.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: 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 | 11 +---------- 2 files changed, 10 insertions(+), 10 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..a2571dbc99 100644 --- a/reftable/merged.h +++ b/reftable/merged.h @@ -9,7 +9,7 @@ license that can be found in the LICENSE file or at #ifndef MERGED_H #define MERGED_H -#include "pq.h" +#include "system.h" struct reftable_merged_table { struct reftable_table *stack; @@ -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 Tue Feb 27 15:06:26 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573989 Received: from wfhigh2-smtp.messagingengine.com (wfhigh2-smtp.messagingengine.com [64.147.123.153]) (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 18840145B0D for ; Tue, 27 Feb 2024 15:06:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.153 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046393; cv=none; b=pvleiBc0QYf86K1n4UosDTg2LWKOVqh+A961sXCL8eQZbZ0VcXn2HY9NdEnflXZTT4CmbnJZqX6W/juKmkYaExHQuwBDmskgivzG6RBid4TBHpPeCSacXtaagiXvaskiavd+jzYVMBnHoISTNuQvtMuePHbhWrutdEhwZWzy+Ks= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046393; c=relaxed/simple; bh=wJoBN961lcxswmi/ceQBsLpu4GFYvh0D4mtPYOMo98o=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=FL7PD4ImAOA++YS4hfQB1QTIKSjcoijF3qO+x1WcZrZN9U5ZCXkRLuz1mqHQV1GVKA/PFBTKRASy53OhKvAsIJFLWHa8rWoHYo1awvhDjULFLXgVqV8QpqGebmYIkysxNWdHk+21VX7VXPddGVH3+ZDwO6aG/5Cf6FoZr2cix54= 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=awzQ88gm; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=XRNyZlKF; arc=none smtp.client-ip=64.147.123.153 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="awzQ88gm"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="XRNyZlKF" Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailfhigh.west.internal (Postfix) with ESMTP id 1326618000B4; Tue, 27 Feb 2024 10:06:29 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute7.internal (MEProxy); Tue, 27 Feb 2024 10:06:30 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046389; x=1709132789; bh=UkXWnT48tL JPGrkW3f2G9afzcV3NwBACLd8XL1v07fU=; b=awzQ88gmikUx72LEkrQoXaqbF0 OdPdKeL+ybe77hY6AVTSwIrQuCQG9/GFvPGE1vQr2RSaJYPBRwZKdCTY5b7MB0YS NiSAbYoePkY8rM1nGfFehTaaHQSN1zeLvaZs6JJQv3mLc8zq4NNGCpgyLLBX8BYy NsCvIK3HksgK2AfTlVRsX2NcQzRhwaRWajm2cu1twBs0tMPvyN2HQovmQ/fVrJSD NiRoksj1Q3IZQjlPrPcZr0+DxzgITEbECXYUicbFMrqG9FG8Z/djxr8CqPkxLxhk q6+YuKH0UZ4/L8NP8RusmfefhVbEkvOzlVpEfev7s52lOovXWt5nbkr6jXTQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046389; x=1709132789; bh=UkXWnT48tLJPGrkW3f2G9afzcV3N wBACLd8XL1v07fU=; b=XRNyZlKFqaiN13k/iq/J0ydiP40qkcmQA15/0BUXuzpX /i2TMKvQKxiHsifohMPA9vXU1E9IU1O6qotd8OrI2QlFosSMyEzkZXHVU/dowDri /PbrLuCqLotY0KIgQ9MK7j6L4LIx6NX36/CCS/SosH5U2a7yTZS5vAQVMvoxRhZp KGb38/T2Db402q4l/v5kg6NchotRFxGnwoxKI3VWUw/8qdkWmOPAhtmy9ICa7G7L DQ17OrP9h3ISTv0c6Br6mSY0RdPxuVpC/cdgT7QV9sAQlDYKMGH/Kbs83HHq4HOi c/tHIvklW7uu71DdC0FJLb+vvRf6deEs8PxRJNtcNA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:28 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 201f2797 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:11 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:26 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 03/13] reftable/merged: advance subiter on subsequent iteration Message-ID: <0e327e5fe360560b4de8c5098879581bbde2baa9.1709045927.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 topmost 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 actually 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 Tue Feb 27 15:06:30 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573990 Received: from wfhigh2-smtp.messagingengine.com (wfhigh2-smtp.messagingengine.com [64.147.123.153]) (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 B733C13DBA4 for ; Tue, 27 Feb 2024 15:06:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.153 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046396; cv=none; b=GPwtTtvstEIKBvECPSYc6CWLqTrcJwWQOHmP0kEVGwcBMMBB7Ou5e9gtgV91RxZWWBnTV9NRv/DHlHhQNYU+uFH/vTsE6xap2gCYtY2udiGIm/tcVepekO+VwLcmfH9Vc/5dfjsNS7W6ePFAx4rQzPcjhWF1NkVBVuDkIQcrxEg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046396; c=relaxed/simple; bh=CfQkbiHkB6hgWmOA5iFICoi8TGCMW/4YHwJD9UTxP6c=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=KdaB1kwZepOXONub+Uibxif21jmULKVJlze3lvjTvILdI35+rOoj5hPrfC47E9OAe6jVdOi5N1JVVQaCZMkPWr1AgdKT/lkfQTNB+LLVw1JaRsWtOTixQbZRGYlOn+AOIElJlxMISvXo3JtOgZjsOdFUQ57hGPYkrf1/QjG8tlg= 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=YuePP/c3; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=WO6gFY5E; arc=none smtp.client-ip=64.147.123.153 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="YuePP/c3"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="WO6gFY5E" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailfhigh.west.internal (Postfix) with ESMTP id 09ECD18000B4; Tue, 27 Feb 2024 10:06:33 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Tue, 27 Feb 2024 10:06:34 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046393; x=1709132793; bh=E0mIhroanH 1ECWqPiT972MS1bImEnKHQoRIJx3I8kNU=; b=YuePP/c3Pzd4yhniXsLPNv1Fvk erC+jufpdN99wLHySSKzScvudVPBbxq4xhfjd7sSvCMBa72jgkLjG/CFvNmwX4f9 UKclB/tUXAiWa53bwA3uwaPNAZFjFWgYKsXN9tg+FtTlKUblIdtA6/TywVLWjaRk +DJ3ZXpCq0kCZ5bSIc3F1UsbZO47JWTCxfuizX2pcQDg/hWg8cPZgvIlX17Zwb09 AM7B2UaDzW4mxSaiDMbTvjtoYYYstNhyrTJ8JlMYiSzKq13DLXRlf3OpAFYjjF8J M4cKuHOTPz2AkXgynu/dPtkgryKHWz8icHor5TCj9pMiVZauf19eJ3Ur+Djw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046393; x=1709132793; bh=E0mIhroanH1ECWqPiT972MS1bImE nKHQoRIJx3I8kNU=; b=WO6gFY5EfJL22hbl8IBbneVSs1sKDv2+EwB3cXeG0d9V ceVke4wEJn0r1QKeb4KGnAxkYxEr3+h4sH5gcaq+urC8hvBZkV9RYjxYjjGLPpSg 9PI2+JYPzVpYWbAsh8f0fxGWBce1aZZwqFaXXWtUMBkmhiTyE2/ZAB1GeXw+kINe ppSdcM6SD5Osa0VDE3CWIVh4Yijt3A1XULLz+evThZwR6X4yENS8nJ5Zw5JncWll u9J2+y/StYuWvuuHECLUDswKrBBijCfkum3IN6WI8isdCDW+pFSkB3RW0rFNkeLz ZEaaWaDiFqcZF9ywFJtVovbRnpAnhD+MLSaWNzFgZQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:32 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 95210f4c (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:15 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:30 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 04/13] reftable/merged: make subiters own their records Message-ID: <494d74deffcc9d473431c238b713d65015305fa4.1709045927.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 Tue Feb 27 15:06:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573991 Received: from wfhigh2-smtp.messagingengine.com (wfhigh2-smtp.messagingengine.com [64.147.123.153]) (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 E3537146915 for ; Tue, 27 Feb 2024 15:06:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.153 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046400; cv=none; b=RZVVVHU+r055bDnQjGLLvYgTAYuTR6r/mVfUdY/o4Fm4vwxx7jLdXmhoxts2qcn9mWZpCA0MQrLBnueEOoa9hNKoNw6Z4orFhFl6n0rlEBL1Xm4WmGJIabjmyl3pIE2HL9VlHYtZLhvEZ8cliZlQgeYxsMTtIY3PzqbMoxYq+Nc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046400; c=relaxed/simple; bh=XKTgLLRynHauvOvCOQt5ofGZEWbh5QOkMUd6sNmJEbo=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Aynsyxmw3uZtqMo8xD+vzXnyDntIRsiBtuD/5bEtngj/H4/aH85ss00QfK99iOHiS65ROQtD8wyzNpeB9J4QOdZnY/kQVrCizrZKMMq/ia2HYBhxtZtanZpeZQIqMpHncW22S7a2Ov3tZnHyE0JnoGSiz+gBOfYChudF/VrrKyg= 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=gPoyKPPx; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=H7cAdjC7; arc=none smtp.client-ip=64.147.123.153 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="gPoyKPPx"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="H7cAdjC7" Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailfhigh.west.internal (Postfix) with ESMTP id 0AC0118000B0; Tue, 27 Feb 2024 10:06:37 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute5.internal (MEProxy); Tue, 27 Feb 2024 10:06:38 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046397; x=1709132797; bh=6T1Y6gnsBv insKQG4NYwBa0K4fuBqtL3WwO7sIA0WKA=; b=gPoyKPPxGV8/5m2tSS+SqaVCuY a9biL0Z8u9Yw4BcHeIVT2ttoXBu8uHFn6XAv3IVbORBzLMgUP8jiWWhPNsECm1Qg fUiCO3tVAhd5ZtMHTp2HZR7QTI7MKgN+I4LYDN5Nqa/90OKOila3Aq3ePyovO+De V5RmjTB/PTC38rG0ZcHDD27E60nvmERSLH+QnSagDzJ8EdI5O5a9+lr6H8Kkkir2 0yJDIw4rPQcH87mptX3RehJXYzmKtsrSlgz0+xEou9e0gu/lOsIXHgjROQx68dfF DlL/4s3M5oWfLXFq9tfp760iLaaBe1qIpXwQLjwpwKBAjuwTa9KYha07EYHg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046397; x=1709132797; bh=6T1Y6gnsBvinsKQG4NYwBa0K4fuB qtL3WwO7sIA0WKA=; b=H7cAdjC7A8Uof2SUEqM5O6GbUj4CLm2c4GRqQse0WCE0 ffcrckplHX/JcXfngoS1N0id1QPBMrfhsTU1wDGCc/s8m2R8SdaWYN1C4w0C+qTn lHoQ0ITdXgHQmzfbh0bZIsuLjMhOZjbCS+s9vJOOv74Iy35flX2oJOTuxTvsVaEo 2Jx+gzUDQDjANEAmFoDUGoVu1hcOz3n+24mFG4xAEgt9jyGQ/UAeSsZaVfza/XUc BMKUw9zATuTCnAFltBbTzD63WMrqCWl+dY50wXNDrt5ItE/sii76MwnYhfJn863u YXLLe6rMZeeSBsmLS96nA21t7/ssg6PbPBXeM7QVqg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:36 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id e8f4b0ea (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:19 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:34 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 05/13] reftable/merged: remove unnecessary null check for subiters Message-ID: <0adf34d08b781c384d878d7d5f651efcefa7d7ab.1709045927.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: 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 Tue Feb 27 15:06:38 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573992 Received: from wfout2-smtp.messagingengine.com (wfout2-smtp.messagingengine.com [64.147.123.145]) (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 F3540146E87 for ; Tue, 27 Feb 2024 15:06:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.145 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046404; cv=none; b=Rv+R0ypUvCcsnisveiNbgjVvh3yGP69AXChZPqVv38tmZutVufUwXEtkuz+omSqyBbwLy9pCNk1PKJNp1yraLUc16VAY/1B4Pio4acYrdq8xKjFeBBU8ibL8iA3VTZf9rWczm/Sd6MQztPUYXgBNxjx4ePSeWWVN5UDlwLlynP8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046404; c=relaxed/simple; bh=ASP4TYQKH0mJ8g4+WQ/sG1YvJXp3/6uiHqO4cgqsC1A=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=oHu91Q3Jz4gJzV6ilKeV/wRPJE7X+fYj4aUwMHE4tJ4z2mg7rOVfaYtfWqMSOhiCoXRSjMd0Ktvma3XFEAqERJgdT9zv1cQV7ugy8FAljvGbuysmkpcKinbfb+WsZcvezM6OVoqCZDDzFi+liHCc3qceEuzvaZDx0oW4tdaHZ6o= 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=rXyOf8AJ; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=n77gEkgv; arc=none smtp.client-ip=64.147.123.145 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="rXyOf8AJ"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="n77gEkgv" Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailfout.west.internal (Postfix) with ESMTP id 06DFB1C00084; Tue, 27 Feb 2024 10:06:41 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute7.internal (MEProxy); Tue, 27 Feb 2024 10:06:42 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046401; x=1709132801; bh=T3nibIFt5b VkRcuAdxfkC3JyyyQLlrrg8LYmGyM9E7o=; b=rXyOf8AJbDAkWNuKpWXDkT4JU1 X2iVw0BYDgHxEfwtnyEFm2WiavYze3cJU46zbYXpqlctjlgf3mepTRuFb1TQSte1 MLrxs5hIlPR2iCHlfRC4+sgVmggaqRytwS6L68HGqJnGwxAGfPAKf1qN8ZBdaswS 6SY8WdkS4Ff2xD5bOvA5Ug3bkx0ZnqaiVERU+PXMHitIfk783D0B37IBice79Tnp NRAOTTmY0XGCxM5DmKhzNLbbImEHqHElnsXbCqjLo00PlZDX++doh/TL1qkBvPwf xvd2rR6cfz2TLyVzzWCxxwT+raI0W/YWeeICEhoMkma+F3GRzc5lSzG0L4Zg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046401; x=1709132801; bh=T3nibIFt5bVkRcuAdxfkC3JyyyQL lrrg8LYmGyM9E7o=; b=n77gEkgv2MtvWt1PoX6VD2/Coj+o67V62Ojv4/ZHRVVz VB7rcTAK7CL1GEICFIDQ2gfGV4jKG0csyOzAAG46Zgy0GIqPyPmTvFv/PPkzJXCL 6AJERRvv9eQxg+76pNIy492qsx0erlksW0+2YHjWi6DDmdci4AZjwLtVZSwsK9/L M5IKNy36tu/8gl1G6C9MzHzo7098AihzXiAmeCHXNHRIiMBiNp0Kjvxij0hu7uKC nCz9GmIf0O4Sf87VJwxogJKNPN82+dJW+cmb2p5DEtPz+zcEu6t/VZuE2XrroUg3 5TF7oLMs0I6Jph06TUPeqrMmqAToGRyGJZyajxkPUA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleffteen ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:40 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id e90875b1 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:23 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:38 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 06/13] reftable/merged: handle subiter cleanup on close only Message-ID: <01152ce13072429f2047cc874b182c2938ab49fd.1709045927.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 Tue Feb 27 15:06:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573993 Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (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 116F71482F1 for ; Tue, 27 Feb 2024 15:06:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.25 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046408; cv=none; b=uZVQCX5Og2+qA24MBB+5L2tDnhU7Y+S2CXZVOexCMleyj8KijmxpI1xvEY+aOSXefVa5sPfXLGyhzt4zEr8RbbFsa52U0VaIqUySHsPvnR6JHv5AxpafBlB6Rzv+gXktHkwg80pmKVXSgIEI8alcn00DxX8doPYGRg32X4eEdTg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046408; c=relaxed/simple; bh=AxAvG4XSp/AiugBMO6zPZSQKdR7KeGHGTRCG1ftmIHo=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=HPuBLc6QmRGiUw3d5iX8XL0UHM3Ztcwhxm3WfSPuKjV6sSUZtxhPE4Iwne4Tx3+qWudTHKDvHDxf8LqMBs5+WWkThMjuaKjpvrwZ3DqwquFNSBijZqXEvsh5rmHewP/eK23B7QuNQ+CeOUGHdtzUkB51+OL95IiTgeU1z9U/sx0= 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=S31HVaS+; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=Th+cAxJJ; arc=none smtp.client-ip=64.147.123.25 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="S31HVaS+"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="Th+cAxJJ" Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailout.west.internal (Postfix) with ESMTP id E737A3200922; Tue, 27 Feb 2024 10:06:45 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute7.internal (MEProxy); Tue, 27 Feb 2024 10:06:46 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046405; x=1709132805; bh=dUFuFu1stf tnqvcK7jkX5GKZmiMvvRiIImhStLxn46c=; b=S31HVaS+uietR7CilwlHHhl0hs AomU8q1kUjlKLKLCFuo9dL5FRgM3dU3UcdAo4ZZLqNKUuikXjM+zTbgMvaX0HtUW xAB64C14qPiowM7naqZui09QdUJ2rPFyzn3VkwW5DG+eEmy3oA0v/fXgDfeWAdML oTIlR9SvXy74rPrOI/sHoslBBk+GaaGyO+Ym/YO1SHrXBYxyd/IhqFc1dkAbZQnL zfY1hoImr27TA73VqD3rO9bHUrbMLV8o5bcHXmisdOcxW6CP/MBsHSK4n5NXr+gD jnyn9FM1FBikl7qJ0zi4ZrN8pYq6iXZYJnA1SDBfb1GVD1+fGdX2/EkBGYGg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046405; x=1709132805; bh=dUFuFu1stftnqvcK7jkX5GKZmiMv vRiIImhStLxn46c=; b=Th+cAxJJRPsPiXDg0rs/wFun9wlIZ6qSL1pjMZSFVvFc ZBcHBkKDcQXQ7vdo5Ry4AtYyLOnLdKbSQIfVqli5FPWCSpSROu+IQzk4/lA0bOC9 b+JOnGHK4+BujzY2xmDAqBD8xS0khM4iDLSl0D4T1u/liJKJsCmrfdE8plKxBm09 pd/7OCqf7oRt8xccj8d3iKdb26fGa3pR62r0zarWQlFb37VDtx2KOf9U0X70iStC nFiFDIsdPfIeAJNkIdqJjj8ydceyFqxORQTIH3+/tdYK4TEvFyWrxJBvbQo1qMUk 2Dvefj+AKs8aATrBPiSNOI3G5hct3kNXZgeaaBOrKQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:44 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 0e7453a2 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:27 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:42 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 07/13] reftable/merged: circumvent pqueue with single subiter Message-ID: <370b6cfc6cfe8a81684fe4d9c72138cb467fa268.1709045927.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: 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 Tue Feb 27 15:06:46 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573994 Received: from wfout2-smtp.messagingengine.com (wfout2-smtp.messagingengine.com [64.147.123.145]) (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 DC0FF14830A for ; Tue, 27 Feb 2024 15:06:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.145 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046412; cv=none; b=UZYGQKC+jhU2AYRwTCYs1CtlUrafi9GSqhyVtxuO3Jsu4DYnzSnu2T9SRnKZrmtc/zuBrY7Z+PqhMeQ4yt6WO7g2swb9g8K30GWFJj5Chderg8NHeEYpP4ET848lvSFX36IiuZDe0NTx613/0PiQm750NCwC9XtPu3+bbsYfjU8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046412; c=relaxed/simple; bh=pNVd3O7/FQKDAPNf2SsDT4MCBoF2Ma/xfsXLHZNX7f0=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=KIOpFFE5JscyTWcRSnHyDUuy1Ywk402biFn9+tLaXADcZl+N6+tnNoyj+xQ3zOey4OLdwIuqj61JqwA59PnGWOz+TF+hGEA5Pcgp/4bPftfr+M1CTnWAB2JuiXEUu+T3JkcN5NiKHV2cexAoe3AT8hBPkgrUC27HLPgjFCPR3/A= 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=lBdDsaGv; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=LqpInepo; arc=none smtp.client-ip=64.147.123.145 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="lBdDsaGv"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="LqpInepo" Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailfout.west.internal (Postfix) with ESMTP id E207D1C00084; Tue, 27 Feb 2024 10:06:49 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute3.internal (MEProxy); Tue, 27 Feb 2024 10:06:50 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046409; x=1709132809; bh=LfOgqeANsG qH3NddLTVOFmK5symbnIxnjHwt00f5JmE=; b=lBdDsaGvnEUbdI7O04MCw10E4o 36UX1w/aXQO2tzujbBBq72C328zS5CjqCZ/a/JgK7p+mXPnpARwqH1ck1qskacik 7WUV68mj1pq+vgvfvoKOzq/WhsLf8oUGuuwnjuCQ4I3GZVeWxL+tgmblBZ8k6X3E P5R+aEr8TKK1FRNUKw/p2sQ6l8ejWzTfDG8gcxK2cGhJ9NoaRvB1dxNUln4OfCTH 0RMpOiMnskJxjvxjZ/m0hXWwF/wFoaCLmUBSuUWzD1RG1lFTrgp2uSE/Y4pypB6t ftjEIGSMi688/Z+I04ODgqmeOuCNqC7UlWvtXMYZtx78ubriFuyvslZrz68Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046409; x=1709132809; bh=LfOgqeANsGqH3NddLTVOFmK5symb nIxnjHwt00f5JmE=; b=LqpInepod4Q4NVJjdJwVmglN7u2eLKq97IT1W+1GuuwL nl2qLZPX0BQwcF7B0AC94OhKDGyqaeec2NCuGmpFgZ6IZogz1mwwzQ0DILhl/rbV eZ63hfj9eNVeoyp/C5mL9wP0vgGvf/i4Vc6t0hDLBgf3pV/9a1UNqHHbg7sJUgx+ T4n49IyyOaPjvpa9+i1gmp0n4zIVllTfMq9dqcEYhDlYMFBZlKxFfjezWaZzlziJ asaqDmNp8LwDRIn5e4M1+sYQF1WRDfAZ3CuFvU2My40ScPD8SAGBRxJSpIxFXGJZ H+n0eNEp5pC0Vy5OuVrJMnmX4op51/hHQvWr7cf50A== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegjecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:48 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 26610aef (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:31 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:46 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 08/13] reftable/merged: avoid duplicate pqueue emptiness check Message-ID: <1e279f21e6b79d8628d5407881cee0d5032d7297.1709045927.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 Tue Feb 27 15:06: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: 13573995 Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (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 CD1BC145351 for ; Tue, 27 Feb 2024 15:06:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.25 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046416; cv=none; b=TE2EwrMbN+Nkn600DZwNcTeHZtTildxkM9seBPp1Ru2tFXO+Rd7wJxDp7G+QNrDp99+0hIeG2x5P3OwGoLspG1SyW6PtQKhjHaDrX9Vm7U77IhlckTCEe63vgsTv1vvTI6NB01cThAmGazBUqyUPGROBBlKhnJARdmsUCyx7M9c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046416; c=relaxed/simple; bh=O0i7cl+pVMocHj5q+texKRkpgE9VD3MP7b2knz32f8U=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=EpipxFwBdGnpxaf2rVJQbG9LEsDvmiXKw1OxyYh2i9Vj0yXMJPqzXVfTKpT/n9cXwMrTY1meE3Jxcn/iBeW4lMp46IXFEraqBuXzMoIeKgXFkMYwfPf4mvthz3k1rB7K2EkAdwIX+Wlv87lyn3h53DAuVK9mjaW5UpBBK6o/T0s= 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=ph1G8CUW; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=RR8ZFfz1; arc=none smtp.client-ip=64.147.123.25 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="ph1G8CUW"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="RR8ZFfz1" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id E69543200922; Tue, 27 Feb 2024 10:06:53 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute1.internal (MEProxy); Tue, 27 Feb 2024 10:06:54 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046413; x=1709132813; bh=8XzelIHsNo RAKSB3XmYer3QVUYsgA1uiTOpSAxTXoPw=; b=ph1G8CUWvB29EAbS2QUoKqZrCo 6GiO+2hOLP93GRqCUN6+o7xCLj9P+xJ8OKEMjWUyHK3dDw30rba78VVTl5u8gXUN v6GKl48IzGbX3lJrugt4UVChjFH0k+V3XcZTilsdR3HEfhJem9aIvoWNv9ZJvhJy LmMuc7CO0wEy62gAPa+Jrapuj2EBI5zRNKUXyJiDBsXMGAARU4XXBazcjxdQfvqS Q+Q+JEUs/okOk5t4l1CuvH+A632A5WuYRh+65+kJm9j7upkVdDjs/Ljgec3dffZ3 OKrH3iI/5F9uwmiT/tyhnEjqyMfHdKFQxqYHaEuwZAVxMwCjghr2GAIL/XIg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046413; x=1709132813; bh=8XzelIHsNoRAKSB3XmYer3QVUYsg A1uiTOpSAxTXoPw=; b=RR8ZFfz1u732fiWzJTM0npW3tW+/eP8V+CbKhQQfR1He /QK1Dzo55RZ68LOpbWF5uSRLM8kEWsU/J/9oumJHdUvwM2Qc4VRRbz0B7gJrmo2o 6TaSk7NIDxm2k7yh/yCpLZuU3usEWw7gJLG2BKLGcU0wcAGnWA2NeD+ocqaQ3/uT C8bN49vSaH/VdZ7tjbTzDli22/l6nCAztH95u2nqLFBlz+Tdm5BLsPGKkbvPVdVT HlbONmo1aYqhU1pqj3dK3FMLEqW3MBewRmth8w9v/CvKGplHpkQdZnS99LVt7Fe6 DaaB2lcVDZzsmntwQ7/VFk03EZPwZftFHSDJ8LzygQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:52 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id a950e687 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:35 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:50 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 09/13] reftable/record: reuse refname when decoding Message-ID: <15a8cbf6782653f4d57ef351e2d7894835813d88.1709045927.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 Tue Feb 27 15:06:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573996 Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (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 BD02B1487D5 for ; Tue, 27 Feb 2024 15:06:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.25 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046420; cv=none; b=mVqd8KsHr/3371QwMZr+LugXjyVhfoT1ZbzS+XdamiyvksPaK2M8JvelDwzFkW2alKK+51QY3qozWoew0Nz1dhetX865IukqdA6sxKqlZoVEaejyyCbzOpd/skMhb5nyU9Vj+vM94JqZRdeqcCvj44M8dLgt//Cbi/6S3oyFAq0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046420; c=relaxed/simple; bh=1fNfgntGirVyJUjKcEVOw/Yoyf7ld8XeUgPTYFbGbHg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=eafGmwIfU6fHjVYzawZlRytco1PMuXLlDIozflIuUEErizto20O0ZHFR83qc8jymbHaW5RH2Y+Yrw3biMHm0Ywlwu3Fg13xMzSzR6G7VZpYlWCVwo9a5mllATuWRtevapy6kSNkcZzP65JPbyfH+mUyLE16wUeqTHykNUitUDs4= 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=LzJv6UJL; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=rxrmXYAf; arc=none smtp.client-ip=64.147.123.25 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="LzJv6UJL"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="rxrmXYAf" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id D7C143200922; Tue, 27 Feb 2024 10:06:57 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute1.internal (MEProxy); Tue, 27 Feb 2024 10:06:58 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046417; x=1709132817; bh=Ji/jbGu0ZO qX54dJV1fXdrNeYX6FgHCVECLnqzJKhjs=; b=LzJv6UJLCjQfL1EIEuvvYnpmEj k2QtfO0QOucgwSvH3VgkhI6wf+LhhrC9idJ52Vk54M6AxasLw5GTqnpyGXfQTACK CpBtEY7T5pZO68KPbnRUeeWFnFoiQgfcbjNZiRkmM0xiOHmT1S/1/pAlkK3kZvdy SYkZrXRuWxyj/Jv98FUCHUuHukC/Z31NeoLzIZZj/ZhwzGW+Mc9FtAQUqL9lCFNW mOjSWTfEfi7tG0GrIw307gbVBlFO/6gTmF8qB+tszIebCnrMPmWhrN9PBGtEMhhi 0czFUfXKTvH8jAIImSnXJXBwgiMYavyqFn0rsQQJu8yJRDsTfeylt3i9fKfw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046417; x=1709132817; bh=Ji/jbGu0ZOqX54dJV1fXdrNeYX6F gHCVECLnqzJKhjs=; b=rxrmXYAfrqkyRowL3qmjCFpVzKBmOc8A32FHZ0kvhMZ2 S9pq+8zjI3GSoyDZzvC5rkTCylWia0NNNOCh9BSpP3iSzaaWHGU667hrq04PqDJ3 K9Js+2Zq2V3V3UIMMe3mhdEWhHFXQIk8q47yfxCAf9exueISRWZv4D/gzJAatWbt RL7OjkIVwvX5pXbFnKi19LbUyAXIZ2UFgo2zghAgQgrHJOEgIkM8MdquFaDzXm7S d9qY6jOQ+1O9x4lc9D6rd0yIiKXNLCclxtBk1EP1J8kQPK/c68ft49EOIAN0gVOO quknFsHfHajOQItXtQQlvSSunDkAzTlBQy0Y2j6pgg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:06:56 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 9c37f06f (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:39 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:55 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 10/13] reftable/record: reuse refname when copying Message-ID: <35b1af2f0612e51bc0cf87afe9c44197b2b8ccaf.1709045927.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: 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 Tue Feb 27 15:06: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: 13573997 Received: from wfhigh2-smtp.messagingengine.com (wfhigh2-smtp.messagingengine.com [64.147.123.153]) (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 1FCE01487DF for ; Tue, 27 Feb 2024 15:07:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.153 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046424; cv=none; b=VItoEsB+4ZznDirtbux8U5dSb6qc/notCRTtv/J/blCcRRH6jl9TTd8H8+Tc33TN/mIlbxkKXqcq9dcJzMr0s15YQCCJRglGleoBgTcWeRjkVxceafMMO2c4CxzMfyfP5CiY+W9dgzFLICyV8EAhA/7ZcB1ybXldbFdC1eIfOVY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046424; c=relaxed/simple; bh=bwxy3NdcIreWWmerl7X5jwA6Uv97oCQeHhUpLFiUpew=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=RVw/7zsS0HqNJJUIx4W0EJuTd9ydbUtJCrzyS2wZCarX8ARBpWTsn5sgVBQjnIZ7RWciTibGLlvcGVFZwLeBYCnZrVSDTtEPPuy7KncGk6Fwpdx/i9Du9GQdFqTn2OQVRRsCvI+PpzNcto56qFraSeWcsme8tMUo0wfbmhJt+KU= 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=MrBcw///; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=kwCmgCIf; arc=none smtp.client-ip=64.147.123.153 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="MrBcw///"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="kwCmgCIf" Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailfhigh.west.internal (Postfix) with ESMTP id 1E43318000B0; Tue, 27 Feb 2024 10:07:02 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute5.internal (MEProxy); Tue, 27 Feb 2024 10:07:02 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046421; x=1709132821; bh=JQ6Pf1c2wY Hysh3NOP66HAv0d4sUnT0xw/at/bnxjKc=; b=MrBcw///dSkVKt4nz43aGpM/2q Qsgj4HpS1B44JKEVI4Jbt1OIkBe9KyZ4csqgby/6jWZ8fUEi8hVQloVqwvyGseLd DVe3XBvBpEjzs5tpoUG+CSTBWzBnx5fbcbNmQO/hizBbTtxDJi0gd38HQzueX1Rh o+911Z2P89Fk5WMJG2gdOe+1V5omAixSqLmE3vIBR91ks73FGDGn+ibwQASGBtl4 qY2HGTm22cB2ZTtKD82AkrY//t3yHZzN71ooXxwTpSeRRFypiuXhvw4vii7lmTiY 2WO7LUsd1/LvQHUPVGYsK8XcMBObnXorr3rM2WpxAq5D8VMagMcULnKj7ZGQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046421; x=1709132821; bh=JQ6Pf1c2wYHysh3NOP66HAv0d4sU nT0xw/at/bnxjKc=; b=kwCmgCIf54YHL3F63vaDPn38WQUcDQK4/jwwlrBkV3LS MCy81zGrEDGHd0Iep19FbOtZZ0356tKhJ8+j1Edd7ALmqFojewusrHTVONmJLxG7 G+s+MX4C3nnj+N/stlRwuoC8oycFapMqO+pDCJMZStt8uNMC3dUWD4qm5fK5425f j5Eod3daRsEaNxQCK5s2VCaB9/pOA09LITMO93OM2SA3ELCI2ODLKx7oHwjKemY+ RBF5Yg0GbnzjOU5p76aHlH2DJDuBTJHyc7Fj0wmSU6jPyeFoQZYQKzToVeHfX9kC NAOFQRuLrWe8knuIzM1Nxx2fV0MUJ4bQqNGa8dxMBg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:07:00 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id ddfef1fd (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:43 +0000 (UTC) Date: Tue, 27 Feb 2024 16:06:59 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 11/13] 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 Tue Feb 27 15:07:03 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573998 Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (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 23E23149DF6 for ; Tue, 27 Feb 2024 15:07:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.25 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046429; cv=none; b=krBJncb8iJARtVvtXNn+/eibkxHzV6b7X4dQS33BYTjRTk06/dMCyeiATjyfS7uIb3ei6DrF7R42UGNa6HwGOBxamIJdsEtIE3G8LfxwMeH5TQOyTLQ3L7zqAgXYMDuCyJ4rY4WAOyr7kXYTMpHor4kz7HrcZ2FxGxZnS0H/FVo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046429; c=relaxed/simple; bh=bUYldofM5/5KVrLq2XzXxbCi3HafCy/fYOFC9EE0hd4=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=sQS98a08ZFNlfBD2zbdtEwB4g4cpQ2+4VJynclUjnzky8htfc17/FtztmCKGt8mfZvGJHchBgq1i3RL9F4uHNJeA8Wj8dKE4rsE3EvypP/5UuUipbKrbhF8X0nmJUQanHukDpQT/Uyd1UL/2mVhPdDglBceRq+g/CKADQHSfoTw= 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=sGTL/q1a; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=SVb9zaS5; arc=none smtp.client-ip=64.147.123.25 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="sGTL/q1a"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="SVb9zaS5" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailout.west.internal (Postfix) with ESMTP id 1E1493200B8F; Tue, 27 Feb 2024 10:07:07 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Tue, 27 Feb 2024 10:07:07 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046426; x=1709132826; bh=OSEMD5nyMN JDKrQ02d15AEKiDvHwVYz5pQKSPv1ZAFY=; b=sGTL/q1aqA6DKJ4LkvmQcc47M7 MsnYUQ4P1TDT3soz9Vsn5992U3TI9JjzFS5hbcDGDw+2wO3QP2DltERgDw6yp2HS DJ3ZXDdBlisqNUbp2bs64/DcECe1Z2PZedN4A90Lwi8Z3Lme8Uq10JpNFsS/hn8N Wny4qtb0IOirlprjAnek5NWJ9ckIsTiYsHS/pCdEmoG4G7TBBIyoyxJThqH4nvVr JxN+U4GRvCi5/MGWJQ+6Ja3R1c1y/2BordFQNZAWhhbk/uV8Jb4u2DR90F3h0pcN /OqLRDVNsIXPmK1Rdce19yKPYlps9rl6gwT5gRMztdLeNmk8TT9+e/5bxwvQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046426; x=1709132826; bh=OSEMD5nyMNJDKrQ02d15AEKiDvHw VYz5pQKSPv1ZAFY=; b=SVb9zaS5QF3nXlLAopdQmUhYvDVOq36RLz6kTtls9fWW dhH4x8xEh4uxSGbUGLOU6VlWKpKj6ng3BOT5shbQyyKtWhMDcsmpEaD7Ow4c5Suj 31eDii/n/Ew193XIqBSFz5wux7kiF3A8QhE7/G+DQZMYfDuznnrDvcezlaXk6tH9 nfRH+lyCQVDRgoGKMhpIAgiugyqQrbuk4kSge/5OUc8XsfDRPZIWsmECuQe3em7y HrTKFsvCQ/6gSyywz8hNLx4qXJlSK8lcYFuD/RvmVwSJZ7UbGiU1+ESaIBfM7E/8 wHBybGJ97D9Gg0RJq19aaQb2fOJoBeZTLWTwyuPihA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:07:05 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 50bdf740 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:48 +0000 (UTC) Date: Tue, 27 Feb 2024 16:07:03 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 12/13] reftable: allow inlining of a few functions Message-ID: <99b238a40da1837013c45112aa5dea38bba54df9.1709045927.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 ± σ): 105.9 ms ± 3.6 ms [User: 103.0 ms, System: 2.8 ms] Range (min … max): 103.1 ms … 133.4 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 100.7 ms ± 3.4 ms [User: 97.8 ms, System: 2.8 ms] Range (min … max): 97.8 ms … 124.0 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~) 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); From patchwork Tue Feb 27 15:07:07 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13573999 Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (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 131FA149DF6 for ; Tue, 27 Feb 2024 15:07:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.25 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046433; cv=none; b=vBBNr11A6N6J/oD7uXLaJBYzSRADcyUQiDBvP8MIOpgvAXqBB98ZUu0wPrF/fINcLdr1d3F4T70tzjOth12g4GLkpNDdDICu0Bdj+CYTLyXG5EJfa7RDbNFUaQpoUYrIf5aU4IY0wSE9ZNPOKTRKxS99C4sylXLVTX9dVyxj/XA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709046433; c=relaxed/simple; bh=OktEPnKBx7ZbzNth0zv9JV6n0MBuUSjKcoETOE7/xxw=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=qitsSsaWFMBGGAnXnYhKmYWG4Nwhdbfn3PQfcuY1RN2KR4BwysEN+W/b/NBDH2GHRvLSWK++Hsk5ByxfyEzNg8WiTJuXELhwrtCp6Pgt83BI2NMD5tqiWOqtxoAVWYls1DATQe+Ze1aQcGhXc+0DvjFWyyB6+SxIl3k622saCvs= 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=oEAdH7Qg; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=m2JHu7zP; arc=none smtp.client-ip=64.147.123.25 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="oEAdH7Qg"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="m2JHu7zP" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id 2C6823200B90; Tue, 27 Feb 2024 10:07:11 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute1.internal (MEProxy); Tue, 27 Feb 2024 10:07:11 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc: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=fm1; t=1709046430; x=1709132830; bh=DVrWmMXGuC cpTMW+tHYF+EqntUr7mX4DD/lpAb/mE4I=; b=oEAdH7QgPn3XL2orW+f0WlFB8n TOC+Yzav3jF832e8O6cIPcY++iimX5bEaHC/sedh4qqvogGl4xKloOXsHlo7t30q XA7x23PMuT8OPN0AKCdSYuJR5gqPw8CfzdsPRNA6CkBJ96q8DbhhlMGl9K1cQO3/ +rA4+fjFed3WJtnEnsORRWmxcZhSu9op3YVpFCA9zCzBWFd8VOAWh+wu8YaNyJ0r QlQLSEUs+CxwOc+1tIsQNuH1rcgWBc9fIp0f1Dh6sNxkD3l2c/wywrTB5qwz6CQM WRbhTIxo0wKDNcby6o4byfEUaTG1ER53EtD3ARjrq7+iFzUWKCFdB642/YjQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc: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= fm1; t=1709046430; x=1709132830; bh=DVrWmMXGuCcpTMW+tHYF+EqntUr7 mX4DD/lpAb/mE4I=; b=m2JHu7zPfo5l3ZBeNzM7jsu6grK/4Z0DmGcYWtcHYwgC MF4w/6asWYtFurcmlpKGFWbtzg+Xm+RZHxCOlVCodQdKAT5C9Brzyf1dafbg307D Kst0O20/D97swRYJ3xDVInUAQFT9K0YCVwizdgc8DiNb+WlG5qQrjyDWBJAdwCtc 4+t7mJB/WxDxaj4ywxUjTEypks6jAj7NFLAHvgeL/g1dVqETIPntJr3QmPAsnQ5I 9u7KR4E6DtOV0U1eF4z+hN+QsJtvXol1p6m8wHZhOzf0jhhnI+VEsBS71QRNRyVr Z53Bzg39lKc52evcKGwaw0Ys6Ogw63vaqHQSAbcHww== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrgeehgdegkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedvnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 27 Feb 2024 10:07:09 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id ad171441 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Tue, 27 Feb 2024 15:02:52 +0000 (UTC) Date: Tue, 27 Feb 2024 16:07:07 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler Subject: [PATCH v2 13/13] refs/reftable: precompute prefix length Message-ID: <627bd1f5f784a2a34d7dabf95c3adf279c3a81a9.1709045927.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're recomputing the prefix length on every iteration of the ref iterator. Precompute it for another speedup when iterating over 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 100.3 ms ± 3.7 ms [User: 97.3 ms, System: 2.8 ms] Range (min … max): 97.5 ms … 139.7 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 95.8 ms ± 3.4 ms [User: 92.9 ms, System: 2.8 ms] Range (min … max): 93.0 ms … 121.9 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~) Signed-off-by: Patrick Steinhardt --- refs/reftable-backend.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index a14f2ad7f4..4d27fdde54 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -346,6 +346,7 @@ struct reftable_ref_iterator { struct object_id oid; const char *prefix; + size_t prefix_len; unsigned int flags; int err; }; @@ -371,8 +372,8 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) if (!starts_with(iter->ref.refname, "refs/")) continue; - if (iter->prefix && - strncmp(iter->prefix, iter->ref.refname, strlen(iter->prefix))) { + if (iter->prefix_len && + strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) { iter->err = 1; break; } @@ -481,6 +482,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ iter = xcalloc(1, sizeof(*iter)); base_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable, 1); iter->prefix = prefix; + iter->prefix_len = prefix ? strlen(prefix) : 0; iter->base.oid = &iter->oid; iter->flags = flags; iter->refs = refs;