From patchwork Thu Feb 1 07:32: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: 13540712 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 A3D0E1586C8 for ; Thu, 1 Feb 2024 07:32:55 +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=1706772777; cv=none; b=fOMJWX4VhUrnwAVPDbzeFeU1AGpXal+OGXCD1t4shk6abX9E326yZ4FuEG0Xrju9lVz1w6zVCNOntBGHZ2jNAOEQvtTsF9HK9unb5QBGRwp3GArHWzAZDwO7aJSrumlge/eCCkrvlSOqMUZ16TsgMBbLhSH3T/gSK5y4J0/1CHY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706772777; c=relaxed/simple; bh=q/iHTUOZ5gXT+hHXQ5pSCzoDuXqESveE2CcF0mwTfYQ=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=dvcaKhz9LGv9JLClY7aFinKbkkmowCwAnbZbbYVxlWzB1S5RswScfKbsMRLXt/vZZswTH4nNHKvpeH3NIcJmWeBIjz2T3XuadYZMdmqqVbQa30ofM0VZ/NSSW8NJMG05zGJzB1fGw51YZdb/VLVlYrzwlfATJzlGMjFSmgeZV4k= 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=sCHBXKOJ; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=YPHWAG3Q; 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="sCHBXKOJ"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="YPHWAG3Q" Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailfout.west.internal (Postfix) with ESMTP id 701531C0007A; Thu, 1 Feb 2024 02:32:54 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute6.internal (MEProxy); Thu, 01 Feb 2024 02:32: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=fm3; t=1706772773; x=1706859173; bh=QoyjWFHiQc CZiIuMG2/RMJPOXUwfqQx9M6HiJwNqiz0=; b=sCHBXKOJlPww452zF0dyLnvVKi z+MdIMmo444XXRbSZMHyUPguwcuE2pnocWegzX5Dw4wRyViVrNg4kKogTcaZSeZ8 SwoUYNIdHslNQN7exAokcTT9wwoGuoLDcrOCTwTT+IHRhE9OomID0y1r9Y/ess+f VSetflXvI2snEz2ib0g/a4/ebv2MI77aSsJdaAH7u8WDt3q6yXqHU/rtSb3uinef j0uzwP/biJw7bOCH2/dRnsytMpClnfJMkOwpgdad1KfYNS1OKQEbfmzbidgB6uXm nlpxK4EFzUhG16jhKQ/EFIVIg3lpERCfhm9V6i+RBgve6PvkhfhcdpqZP6Xw== 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=1706772773; x=1706859173; bh=QoyjWFHiQcCZiIuMG2/RMJPOXUwf qQx9M6HiJwNqiz0=; b=YPHWAG3QSbJgEW3/QLTy9H1GKf039G0NXCOksvqwHuAe YHwx7LtjTU84dvnCjEmKzrj0KS3jYvfYOhMIfw2LIQ36cPGnQyPY5Fh21WCREsgv Q1M2v5RDYRNUQvI4wJREexQzsD1c8iUAGVeOimub6kTGfHFZiAALoCpqb01ejDb/ GHRDlvCWAm2WhG7JyFcFJ6imGdMlB8hO7X5DoWdjit94il6bsO879ekIHmRTsfK4 GYci6UYa/oWyR5Vh35WfVHIFUEpC/yB7X+PEa/chX4QaLHdyyhxvio4xkK8gJiu4 bp5nMl8NLcyGnWeXaDFzYBa8nKGuDbDNyru+gFegxw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedutddguddtjecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedt udenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 1 Feb 2024 02:32:52 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 30857285 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 1 Feb 2024 07:29:29 +0000 (UTC) Date: Thu, 1 Feb 2024 08:32:50 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Eric Sunshine , Junio C Hamano Subject: [PATCH v2 0/9] reftable: code style improvements 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: Hi, this is the second version of my patch series that aims to improve the code style of the reftable library. The only changes compared to v1 are improvements for the commit messages. The edit for commit 1 should hopefully make it a much more compelling argument why we don't want to use the default growth factor used by our own `ALLOC_GROW()` macro. Thanks! Patrick Patrick Steinhardt (9): reftable: introduce macros to grow arrays reftable: introduce macros to allocate arrays reftable/stack: fix parameter validation when compacting range reftable/stack: index segments with `size_t` reftable/stack: use `size_t` to track stack slices during compaction reftable/stack: use `size_t` to track stack length reftable/merged: refactor seeking of records reftable/merged: refactor initialization of iterators reftable/record: improve semantics when initializing records reftable/basics.c | 15 ++-- reftable/basics.h | 17 ++++- reftable/block.c | 25 +++--- reftable/block_test.c | 2 +- reftable/blocksource.c | 4 +- reftable/iter.c | 3 +- reftable/merged.c | 100 +++++++++++------------- reftable/merged_test.c | 52 ++++++------- reftable/pq.c | 8 +- reftable/publicbasics.c | 3 +- reftable/reader.c | 12 ++- reftable/readwrite_test.c | 8 +- reftable/record.c | 43 +++-------- reftable/record.h | 10 +-- reftable/record_test.c | 8 +- reftable/refname.c | 4 +- reftable/reftable-merged.h | 2 +- reftable/stack.c | 151 +++++++++++++++++-------------------- reftable/stack.h | 6 +- reftable/stack_test.c | 7 +- reftable/tree.c | 4 +- reftable/writer.c | 21 ++---- 22 files changed, 221 insertions(+), 284 deletions(-) Range-diff against v1: 1: 0597e6944a ! 1: 12bd721ddf reftable: introduce macros to grow arrays @@ Commit message Throughout the reftable library we have many cases where we need to grow arrays. In order to avoid too many reallocations, we roughly double the capacity of the array on each iteration. The resulting code pattern is - thus duplicated across many sites. + duplicated across many sites. We have similar patterns in our main codebase, which is why we have eventually introduced an `ALLOC_GROW()` macro to abstract it away and @@ Commit message + 16) * 3 / 2`. The second change is because we know a bit more about the allocation - patterns in the reftable library. For In most cases, we end up only having a - single item in the array, so the initial capacity that our global growth - factor uses (which is 24), significantly overallocates in a lot of code - paths. This effect is indeed measurable: + patterns in the reftable library. In most cases, we end up only having a + handful of items in the array and don't end up growing them. The initial + capacity that our normal growth factor uses (which is 24) would thus end + up over-allocating in a lot of code paths. This effect is measurable: - Benchmark 1: update-ref: create many refs (growth factor = 2 * cap + 1) - Time (mean ± σ): 4.834 s ± 0.020 s [User: 2.219 s, System: 2.614 s] - Range (min … max): 4.793 s … 4.871 s 20 runs + - Before change: - Benchmark 2: update-ref: create many refs (growth factor = (cap + 16) * 3 + 2) - Time (mean ± σ): 4.933 s ± 0.021 s [User: 2.325 s, System: 2.607 s] - Range (min … max): 4.889 s … 4.962 s 20 runs + HEAP SUMMARY: + in use at exit: 671,983 bytes in 152 blocks + total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,402 bytes allocated - Summary - update-ref: create many refs (growth factor = 2 * cap + 1) ran - 1.02 ± 0.01 times faster than update-ref: create many refs (growth factor = (cap + 16) * 3 + 2) + - After change with a growth factor of `(2 * alloc + 1)`: + + HEAP SUMMARY: + in use at exit: 671,983 bytes in 152 blocks + total heap usage: 3,843,446 allocs, 3,843,294 frees, 223,761,410 bytes allocated + + - After change with a growth factor of `(alloc + 16)* 2 / 3`: + + HEAP SUMMARY: + in use at exit: 671,983 bytes in 152 blocks + total heap usage: 3,833,673 allocs, 3,833,521 frees, 4,728,251,742 bytes allocated + + While the total heap usage is roughly the same, we do end up allocating + significantly more bytes with our usual growth factor (in fact, roughly + 21 times as many). Convert the reftable library to use these new macros. 2: eee6580c84 = 2: 2dde581a02 reftable: introduce macros to allocate arrays 3: e2d05f7c38 = 3: f134702dc5 reftable/stack: fix parameter validation when compacting range 4: b8b2cce742 = 4: 50dac904e8 reftable/stack: index segments with `size_t` 5: 2f6a69aa14 = 5: a5ffbf09dd reftable/stack: use `size_t` to track stack slices during compaction 6: 1ee9a4477f = 6: 55605fb53b reftable/stack: use `size_t` to track stack length 7: 00aeaeee63 ! 7: 80cf2fd272 reftable/merged: refactor seeking of records @@ Commit message to read and does not conform to our coding style in multiple ways: - We have multiple exit paths where we release resources even though - that is not really necessary + that is not really necessary. - We use a scoped error variable `e` which is hard to reason about. This variable is not required at all. 8: 31864740e9 = 8: 8c1be2b159 reftable/merged: refactor initialization of iterators 9: fd8a1ce99d = 9: c39d7e30e7 reftable/record: improve semantics when initializing records base-commit: bc7ee2e5e16f0d1e710ef8fab3db59ab11f2bbe7