From: Karthik Nayak <karthik.188@gmail.com>
To: Justin Tobler via GitGitGadget <gitgitgadget@gmail.com>,
git@vger.kernel.org
Cc: Patrick Steinhardt <ps@pks.im>, Justin Tobler <jltobler@gmail.com>
Subject: Re: [PATCH v2 2/3] reftable/stack: use geometric table compaction
Date: Wed, 27 Mar 2024 06:24:23 -0700 [thread overview]
Message-ID: <CAOLa=ZQFiBKWs1qT=MyJhBKgn8MJBL-5G6X7EjeXkKwNOaCC4w@mail.gmail.com> (raw)
In-Reply-To: <def7008452303f71c1fa469609bc199c629a19ec.1711060820.git.gitgitgadget@gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2431 bytes --]
"Justin Tobler via GitGitGadget" <gitgitgadget@gmail.com> writes:
> From: Justin Tobler <jltobler@gmail.com>
>
> To reduce the number of on-disk reftables, compaction is performed.
> Contiguous tables with the same binary log value of size are grouped
> into segments. The segment that has both the lowest binary log value and
> contains more than one table is set as the starting point when
> identifying the compaction segment.
>
> Since segments containing a single table are not initially considered
> for compaction, if the table appended to the list does not match the
> previous table log value, no compaction occurs for the new table. It is
> therefore possible for unbounded growth of the table list. This can be
> demonstrated by repeating the following sequence:
>
Nit: A numerical example would really help make this simpler to understand.
> + /*
> + * Find the ending table of the compaction segment needed to restore the
> + * geometric sequence.
> + *
> + * To do so, we iterate backwards starting from the most recent table
> + * until a valid segment end is found. If the preceding table is smaller
> + * than the current table multiplied by the geometric factor (2), the
> + * current table is set as the compaction segment end.
> + *
> + * Tables after the ending point are not added to the byte count because
> + * they are already valid members of the geometric sequence. Due to the
> + * properties of a geometric sequence, it is not possible for the sum of
> + * these tables to exceed the value of the ending point table.
> + */
> + for (i = n - 1; i > 0; i--) {
> + if (sizes[i - 1] < sizes[i] * 2) {
> + seg.end = i + 1;
> + bytes = sizes[i];
> break;
> + }
> + }
> +
> + /*
> + * Find the starting table of the compaction segment by iterating
> + * through the remaining tables and keeping track of the accumulated
> + * size of all tables seen from the segment end table.
> + *
Nit: we need the accumulated sum because the tables from the end of the
segment will be recursively merged backwards. This might be worthwhile
to add here.
> static void test_suggest_compaction_segment(void)
> {
> - uint64_t sizes[] = { 128, 64, 17, 16, 9, 9, 9, 16, 16 };
> + uint64_t sizes[] = { 512, 64, 17, 16, 9, 9, 9, 16, 2, 16 };
> /* .................0 1 2 3 4 5 6 */
Nit: since we're here, maybe worthwhile cleaning up this comment. Not
sure what it actually is for.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 690 bytes --]
next prev parent reply other threads:[~2024-03-27 13:24 UTC|newest]
Thread overview: 52+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-05 20:03 [PATCH] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-03-06 12:30 ` Patrick Steinhardt
2024-03-06 12:37 ` Patrick Steinhardt
2024-03-21 22:48 ` Justin Tobler
2024-03-21 22:40 ` [PATCH v2 0/3] " Justin Tobler via GitGitGadget
2024-03-21 22:40 ` [PATCH v2 1/3] reftable/stack: add env to disable autocompaction Justin Tobler via GitGitGadget
2024-03-22 1:25 ` Patrick Steinhardt
2024-03-21 22:40 ` [PATCH v2 2/3] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-03-22 1:25 ` Patrick Steinhardt
2024-03-27 13:24 ` Karthik Nayak [this message]
2024-03-21 22:40 ` [PATCH v2 3/3] reftable/segment: make segment end inclusive Justin Tobler via GitGitGadget
2024-03-22 1:25 ` [PATCH v2 0/3] reftable/stack: use geometric table compaction Patrick Steinhardt
2024-04-03 10:13 ` Han-Wen Nienhuys
2024-04-03 10:18 ` Patrick Steinhardt
2024-04-03 15:14 ` Justin Tobler
2024-04-03 16:40 ` Junio C Hamano
2024-03-29 4:16 ` [PATCH v3 " Justin Tobler via GitGitGadget
2024-03-29 4:16 ` [PATCH v3 1/3] reftable/stack: add env to disable autocompaction Justin Tobler via GitGitGadget
2024-03-29 18:25 ` Junio C Hamano
2024-03-29 21:56 ` Junio C Hamano
2024-04-02 7:23 ` Patrick Steinhardt
2024-04-02 17:23 ` Junio C Hamano
2024-03-29 4:16 ` [PATCH v3 2/3] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-04-02 7:23 ` Patrick Steinhardt
2024-03-29 4:16 ` [PATCH v3 3/3] reftable/stack: make segment end inclusive Justin Tobler via GitGitGadget
2024-03-29 18:36 ` Junio C Hamano
2024-04-02 7:23 ` Patrick Steinhardt
2024-04-03 0:20 ` [PATCH v4 0/2] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-04-03 0:20 ` [PATCH v4 1/2] reftable/stack: add env to disable autocompaction Justin Tobler via GitGitGadget
2024-04-03 0:20 ` [PATCH v4 2/2] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-04-03 4:47 ` [PATCH v4 0/2] " Patrick Steinhardt
2024-04-03 11:12 ` Karthik Nayak
2024-04-03 16:56 ` Junio C Hamano
2024-04-04 18:29 ` [PATCH v5 0/3] " Justin Tobler via GitGitGadget
2024-04-04 18:29 ` [PATCH v5 1/3] reftable/stack: allow disabling of auto-compaction Justin Tobler via GitGitGadget
2024-04-08 6:12 ` Patrick Steinhardt
2024-04-04 18:29 ` [PATCH v5 2/3] reftable/stack: add env to disable autocompaction Justin Tobler via GitGitGadget
2024-04-08 6:12 ` Patrick Steinhardt
2024-04-08 16:18 ` Junio C Hamano
2024-04-04 18:29 ` [PATCH v5 3/3] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-04-08 6:12 ` [PATCH v5 0/3] " Patrick Steinhardt
2024-04-08 16:17 ` Justin Tobler
2024-04-08 16:16 ` [PATCH v6 " Justin Tobler via GitGitGadget
2024-04-08 16:16 ` [PATCH v6 1/3] reftable/stack: expose option to disable auto-compaction Justin Tobler via GitGitGadget
2024-04-08 16:16 ` [PATCH v6 2/3] reftable/stack: add env to disable autocompaction Justin Tobler via GitGitGadget
2024-04-08 16:16 ` [PATCH v6 3/3] reftable/stack: use geometric table compaction Justin Tobler via GitGitGadget
2024-04-08 16:20 ` [PATCH v6 0/3] " Patrick Steinhardt
2024-04-08 19:12 ` Junio C Hamano
2024-04-03 19:12 ` [PATCH v2 " Junio C Hamano
2024-04-03 19:30 ` Patrick Steinhardt
2024-04-04 5:34 ` Patrick Steinhardt
2024-04-04 18:28 ` Justin Tobler
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='CAOLa=ZQFiBKWs1qT=MyJhBKgn8MJBL-5G6X7EjeXkKwNOaCC4w@mail.gmail.com' \
--to=karthik.188@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitgitgadget@gmail.com \
--cc=jltobler@gmail.com \
--cc=ps@pks.im \
/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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).