From patchwork Mon Feb 12 08:32:37 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13552784 Received: from fhigh4-smtp.messagingengine.com (fhigh4-smtp.messagingengine.com [103.168.172.155]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5E50D10A05 for ; Mon, 12 Feb 2024 08:32:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.155 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707726763; cv=none; b=qzNtRHWmweVLHf41k78s2kWTbsSRLSPZZnKZjQpdo2K7Cl1n3Lo3J38u+vrCRcYNYyJYf4Kg5panMBeZyOX6HpN2uBlhSvRnCfijCOv0HYWOb6WQJqtz3X73brD00QJPBAoBrTPAW6z0/9p1dTCTnPQ7afMFRAksyfUPbJh+cLc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1707726763; c=relaxed/simple; bh=g59/EbwwpiXrVK1/mtUySWh8H6xpWpH2KPzit1t7YIQ=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=umyMRU8x+CkZzDKzplqE9pBEr6Y4NCl1/835VKKKfHZXL1SmOb0vqJ4Snk4CM6Z2a8avkTuJHWDP3E1UgCyRbYh8VrDp9S8yfWTVwRJkXzvFPhFZEs4kOTIe8Mqkx6WkDVutOftnojc7R0nCcmpucvlONy5XeBYljMdVa/iTJns= 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=ZraYAelz; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=UKeZzRNC; arc=none smtp.client-ip=103.168.172.155 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="ZraYAelz"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="UKeZzRNC" Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailfhigh.nyi.internal (Postfix) with ESMTP id 4D67B1140099; Mon, 12 Feb 2024 03:32:40 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute5.internal (MEProxy); Mon, 12 Feb 2024 03:32:40 -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=fm3; t=1707726760; x=1707813160; bh=VJzeEQIQHi q40lFoyRDy3hyPnHDudasBZ7yDj8vwh6I=; b=ZraYAelzkXgB7wDBFwx4c/tMTA xe2EBmdatjkPlIVps3xG9sOl2DJseYhdmTXdvjwHGgQGacRL8KBXM0Z5EUt/BeEu AdPmNB0oPNDsXV6Qzs12CKSo9UoFDMG+3sNMIoJEqmEiOfSFFPsQ/ffy6QSmO/rK e0UjFMhW3zRua1qc6YZ5gkAZAoa4sX/8NvxNyBaNmGHdL6S1IjbU5AVNmbJJ7FTr hvwcasYuaQBmfnieDyW3WCx72BUYLoLkhdhqbhnhhlkbkO83reRv3ht8nMmtz8Be 4SYHAPRSj9CnwsIpSrbpFU6TSX14B1dorNbtjn9MSms+faz/EYQdokwnUTNw== 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= fm3; t=1707726760; x=1707813160; bh=VJzeEQIQHiq40lFoyRDy3hyPnHDu dasBZ7yDj8vwh6I=; b=UKeZzRNC7LIIFcpOrumXQIUEqnO63SYvFR1cOMwZhClX dCj8JOm706yNAimF1ysNg4afW/Vcpj2RH9I+fwUZL1PXydSzIkPKMYrqIVDJB80u +Bo8oMqjJ+vMvqybZXxGmk9+vzQqXNpY3c0JxRuuKijNzNevmQgxX23Gpn3O3w6d V7kU9MlkK0b0ZmeZ10f2mT+7OVUyFjusgZc0bpDH3bWX+DnSraoC1JlzzisBqADq d4Ae9R7MU/oibDhPc352VmsOMpDBg8AbHz3VbplMp9Q05xdPoA5liE92LYX2d8HB 56n1eTdTYqKmQ/ZktFodqaQfvbjwGrr8g1JFg6Orjg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledruddvgdduvdefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepfffhvfevuffkfhggtggujgesghdtreertddtjeenucfhrhhomheprfgrthhr ihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrdhimheqnecuggftrfgrthhtvg hrnhepteeuvefhhfdufedvgeeiueeileegtdfhgeeftdeuveejjedtgfejhedujeeutddu necuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepphhsse hpkhhsrdhimh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 12 Feb 2024 03:32:39 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id ee8dfd64 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 12 Feb 2024 08:28:52 +0000 (UTC) Date: Mon, 12 Feb 2024 09:32:37 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Eric Sunshine , John Cai Subject: [PATCH v2 3/7] reftable/merged: skip comparison for records of the same subiter Message-ID: <205e6b488be9165d08e0fecb6197ebfc6747ba1c.1707726654.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 retrieving the next entry of a merged iterator we need to drop all records of other sub-iterators that would be shadowed by the record that we are about to return. We do this by comparing record keys, dropping all keys that are smaller or equal to the key of the record we are about to return. There is an edge case here where we can skip that comparison: when the record in the priority queue comes from the same subiterator as the record we are about to return then we know that its key must be larger than the key of the record we are about to return. This property is guaranteed by the sub-iterators, and if it didn't hold then the whole merged iterator would return records in the wrong order, too. While this may seem like a very specific edge case it's in fact quite likely to happen. For most repositories out there you can assume that we will end up with one large table and several smaller ones on top of it. Thus, it is very likely that the next entry will sort towards the top of the priority queue. Special case this and break out of the loop in that case. The following benchmark uses git-show-ref(1) to print a single ref matching a pattern out of 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 162.6 ms ± 4.5 ms [User: 159.0 ms, System: 3.5 ms] Range (min … max): 156.6 ms … 188.5 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 156.8 ms ± 4.7 ms [User: 153.0 ms, System: 3.6 ms] Range (min … max): 151.4 ms … 188.4 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.04 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- reftable/merged.c | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/reftable/merged.c b/reftable/merged.c index fb9978d798..0f74a14a77 100644 --- a/reftable/merged.c +++ b/reftable/merged.c @@ -107,6 +107,14 @@ 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;