From: Patrick Steinhardt <ps@pks.im>
To: git@vger.kernel.org
Subject: [PATCH 00/12] reftable: improve ref iteration performance (pt.2)
Date: Wed, 14 Feb 2024 08:45:37 +0100 [thread overview]
Message-ID: <cover.1707895758.git.ps@pks.im> (raw)
[-- Attachment #1: Type: text/plain, Size: 3837 bytes --]
Hi,
this is the second part of my patch series that aim to improve raw ref
iteration performance with the reftable backend. The target of this
series was to get the reftable backend performant enough to match the
files backend. This was achieved via two angles:
- Refactorings of the merged iterators that allow us to skip copying
and allocating records from the sub-iterators to the caller. This is
implemented by the first 8 patches.
- Refactorings of how we decode reftable records so that we reuse
allocated memory. Like this the number of allocations don't scale
with the number of iterated records anymore, but instead with the
number of blocks which we're iterating over.
Combined, these refactorings lead to a sizeable speedup when iterating
over 1 million refs:
```
Benchmark 1: show-ref: single matching ref (revision = HEAD~)
Time (mean ± σ): 146.1 ms ± 4.2 ms [User: 143.2 ms, System: 2.8 ms]
Range (min … max): 140.7 ms … 180.2 ms 1000 runs
Benchmark 2: show-ref: single matching ref (revision = HEAD)
Time (mean ± σ): 97.6 ms ± 3.2 ms [User: 94.8 ms, System: 2.7 ms]
Range (min … max): 94.6 ms … 122.1 ms 1000 runs
Summary
show-ref: single matching ref (revision = HEAD) ran
1.50 ± 0.07 times faster than show-ref: single matching ref (revision = HEAD~)
```
With this, the reftable backend is now on par with the files backend:
```
Benchmark 1: show-ref: single matching ref (refformat = files)
Time (mean ± σ): 97.8 ms ± 3.4 ms [User: 87.6 ms, System: 10.0 ms]
Range (min … max): 95.0 ms … 121.3 ms 1000 runs
Benchmark 2: show-ref: single matching ref (refformat = reftable)
Time (mean ± σ): 97.4 ms ± 3.2 ms [User: 94.5 ms, System: 2.7 ms]
Range (min … max): 94.1 ms … 126.3 ms 1000 runs
Summary
show-ref: single matching ref (refformat = reftable) ran
1.00 ± 0.05 times faster than show-ref: single matching ref (refformat = files)
```
There are still optimization opportunities left, but given that the
original target has been fulfilled I decided to stop so that the patch
series remains somewhat reasonably sized.
The patch series is based on `master` at 2996f11c1d (Sync with 'maint',
2024-02-12) and depends on ps/reftable-iteration-perf at c68ca7abd3
(reftable/reader: add comments to `table_iter_next()`, 2024-02-12).
Patrick
Patrick Steinhardt (12):
reftable/pq: use `size_t` to track iterator index
reftable/merged: make `merged_iter` structure private
reftable/merged: advance subiter on subsequent iteration
reftable/merged: make subiters own their records
reftable/merged: remove unnecessary null check for subiters
reftable/merged: handle subiter cleanup on close only
reftable/merged: circumvent pqueue with single subiter
reftable/merged: avoid duplicate pqueue emptiness check
reftable/record: reuse refname when decoding
reftable/record: reuse refname when copying
reftable/record: decode keys in place
reftable: allow inlining of a few functions
reftable/block.c | 25 +++----
reftable/block.h | 2 -
reftable/iter.c | 5 --
reftable/iter.h | 4 --
reftable/merged.c | 139 +++++++++++++++++++------------------
reftable/merged.h | 9 ---
reftable/pq.c | 18 +----
reftable/pq.h | 16 +++--
reftable/pq_test.c | 41 +++++------
reftable/record.c | 64 +++++++++--------
reftable/record.h | 21 ++++--
reftable/record_test.c | 3 +-
reftable/reftable-record.h | 1 +
13 files changed, 170 insertions(+), 178 deletions(-)
base-commit: 2996f11c1d11ab68823f0939b6469dedc2b9ab90
--
2.43.GIT
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
next reply other threads:[~2024-02-14 7:45 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-02-14 7:45 Patrick Steinhardt [this message]
2024-02-14 7:45 ` [PATCH 01/12] reftable/pq: use `size_t` to track iterator index Patrick Steinhardt
2024-02-14 7:45 ` [PATCH 02/12] reftable/merged: make `merged_iter` structure private Patrick Steinhardt
2024-02-20 18:15 ` Justin Tobler
2024-02-27 16:49 ` Patrick Steinhardt
2024-02-14 7:45 ` [PATCH 03/12] reftable/merged: advance subiter on subsequent iteration Patrick Steinhardt
2024-02-20 18:25 ` Justin Tobler
2024-02-27 16:50 ` Patrick Steinhardt
2024-02-14 7:45 ` [PATCH 04/12] reftable/merged: make subiters own their records Patrick Steinhardt
2024-02-14 7:45 ` [PATCH 05/12] reftable/merged: remove unnecessary null check for subiters Patrick Steinhardt
2024-02-14 7:46 ` [PATCH 06/12] reftable/merged: handle subiter cleanup on close only Patrick Steinhardt
2024-02-14 7:46 ` [PATCH 07/12] reftable/merged: circumvent pqueue with single subiter Patrick Steinhardt
2024-02-14 7:46 ` [PATCH 08/12] reftable/merged: avoid duplicate pqueue emptiness check Patrick Steinhardt
2024-02-27 23:53 ` James Liu
2024-02-14 7:46 ` [PATCH 09/12] reftable/record: reuse refname when decoding Patrick Steinhardt
2024-02-28 0:06 ` James Liu
2024-03-04 10:39 ` Patrick Steinhardt
2024-02-14 7:46 ` [PATCH 10/12] reftable/record: reuse refname when copying Patrick Steinhardt
2024-02-28 0:08 ` James Liu
2024-02-14 7:46 ` [PATCH 11/12] reftable/record: decode keys in place Patrick Steinhardt
2024-02-28 0:13 ` James Liu
2024-03-04 10:39 ` Patrick Steinhardt
2024-02-14 7:46 ` [PATCH 12/12] reftable: allow inlining of a few functions Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 00/13] reftable: improve ref iteration performance (pt.2) Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 01/13] reftable/pq: use `size_t` to track iterator index Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 02/13] reftable/merged: make `merged_iter` structure private Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 03/13] reftable/merged: advance subiter on subsequent iteration Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 04/13] reftable/merged: make subiters own their records Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 05/13] reftable/merged: remove unnecessary null check for subiters Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 06/13] reftable/merged: handle subiter cleanup on close only Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 07/13] reftable/merged: circumvent pqueue with single subiter Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 08/13] reftable/merged: avoid duplicate pqueue emptiness check Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 09/13] reftable/record: reuse refname when decoding Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 10/13] reftable/record: reuse refname when copying Patrick Steinhardt
2024-02-27 15:06 ` [PATCH v2 11/13] reftable/record: decode keys in place Patrick Steinhardt
2024-02-27 15:07 ` [PATCH v2 12/13] reftable: allow inlining of a few functions Patrick Steinhardt
2024-02-27 15:07 ` [PATCH v2 13/13] refs/reftable: precompute prefix length Patrick Steinhardt
2024-03-04 10:48 ` [PATCH v3 00/13] reftable: improve ref iteration performance (pt.2) Patrick Steinhardt
2024-03-04 10:48 ` [PATCH v3 01/13] reftable/pq: use `size_t` to track iterator index Patrick Steinhardt
2024-03-04 10:48 ` [PATCH v3 02/13] reftable/merged: make `merged_iter` structure private Patrick Steinhardt
2024-03-04 10:48 ` [PATCH v3 03/13] reftable/merged: advance subiter on subsequent iteration Patrick Steinhardt
2024-03-04 10:48 ` [PATCH v3 04/13] reftable/merged: make subiters own their records Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 05/13] reftable/merged: remove unnecessary null check for subiters Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 06/13] reftable/merged: handle subiter cleanup on close only Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 07/13] reftable/merged: circumvent pqueue with single subiter Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 08/13] reftable/merged: avoid duplicate pqueue emptiness check Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 09/13] reftable/record: reuse refname when decoding Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 10/13] reftable/record: reuse refname when copying Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 11/13] reftable/record: decode keys in place Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 12/13] reftable: allow inlining of a few functions Patrick Steinhardt
2024-03-04 10:49 ` [PATCH v3 13/13] refs/reftable: precompute prefix length Patrick Steinhardt
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=cover.1707895758.git.ps@pks.im \
--to=ps@pks.im \
--cc=git@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.