Subject: Re: [PATCH v4 0/2] reftable/stack: use geometric table compaction

From: Patrick Steinhardt <[email-masked]>
Date: Wed, 3 Apr 2024 06:47:19 +0200

On Wed, Apr 03, 2024 at 12:20:34AM +0000, Justin Tobler via GitGitGadget wrote:
> Hello again,
> 
> This is the fourth version my patch series that refactors the reftable
> compaction strategy to instead follow a geometric sequence. Changes compared
> to v3:
> 
>  * Changed env name from GIT_TEST_REFTABLE_NO_AUTOCOMPACTION to
>    GIT_TEST_REFTABLE_AUTOCOMPACTION and set the default to false. This

You probably mean true here, not false :)

>    should hopefully be a bit more intuitive since it avoids the double
>    negative.
>  * Updated the corresponding env var test in t0610-reftable-basics.sh to
>    assert on the number of tables added and be overall less fragile.
>  * Folded lines that were too long.
>  * Updated some comments in stack.c to more accurately explain that table
>    segment end is exclusive.
>  * Dropped reftable/stack: make segment end inclusive commit to keep segment
>    end exclusive and better follow expectations.
> 
> Thanks for taking a look!

This version looks good to me, thanks!

Patrick

> -Justin
> 
> Justin Tobler (2):
>   reftable/stack: add env to disable autocompaction
>   reftable/stack: use geometric table compaction
> 
>  reftable/stack.c           | 126 +++++++++++++++++++------------------
>  reftable/stack.h           |   3 -
>  reftable/stack_test.c      |  66 ++++---------------
>  reftable/system.h          |   1 +
>  t/t0610-reftable-basics.sh |  65 +++++++++++++++----
>  5 files changed, 132 insertions(+), 129 deletions(-)
> 
> 
> base-commit: c75fd8d8150afdf836b63a8e0534d9b9e3e111ba
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1683%2Fjltobler%2Fjt%2Freftable-geometric-compaction-v4
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1683/jltobler/jt/reftable-geometric-compaction-v4
> Pull-Request: https://github.com/gitgitgadget/git/pull/1683
> 
> Range-diff vs v3:
> 
>  1:  2fdd8ea1133 ! 1:  2a0421e5f20 reftable/stack: add env to disable autocompaction
>      @@ Commit message
>       
>           In future tests it will be neccesary to create repositories with a set
>           number of tables. To make this easier, introduce the
>      -    `GIT_TEST_REFTABLE_NO_AUTOCOMPACTION` environment variable that, when
>      -    set, disables autocompaction of reftables.
>      +    `GIT_TEST_REFTABLE_AUTOCOMPACTION` environment variable that, when set
>      +    to false, disables autocompaction of reftables.
>       
>           Signed-off-by: Justin Tobler <[email-masked]>
>       
>      @@ reftable/stack.c: int reftable_addition_commit(struct reftable_addition *add)
>        		goto done;
>        
>       -	if (!add->stack->disable_auto_compact)
>      -+	if (!add->stack->disable_auto_compact && !git_env_bool("GIT_TEST_REFTABLE_NO_AUTOCOMPACTION", 0))
>      ++	if (!add->stack->disable_auto_compact &&
>      ++	    git_env_bool("GIT_TEST_REFTABLE_AUTOCOMPACTION", 1))
>        		err = reftable_stack_auto_compact(add->stack);
>        
>        done:
>      @@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: writes cause a
>        	test_line_count = 1 repo/.git/reftable/tables.list
>        '
>        
>      -+test_expect_success 'ref transaction: environment variable disables auto-compaction' '
>      ++test_expect_success 'ref transaction: env var disables compaction' '
>       +	test_when_finished "rm -rf repo" &&
>       +
>       +	git init repo &&
>       +	test_commit -C repo A &&
>      -+	for i in $(test_seq 20)
>      ++
>      ++	start=$(wc -l <repo/.git/reftable/tables.list) &&
>      ++	iterations=5 &&
>      ++	expected=$((start + iterations)) &&
>      ++
>      ++	for i in $(test_seq $iterations)
>       +	do
>      -+		GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C repo update-ref branch-$i HEAD || return 1
>      ++		GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
>      ++		git -C repo update-ref branch-$i HEAD || return 1
>       +	done &&
>      -+	test_line_count = 23 repo/.git/reftable/tables.list &&
>      ++	test_line_count = $expected repo/.git/reftable/tables.list &&
>       +
>       +	git -C repo update-ref foo HEAD &&
>      -+	test_line_count = 1 repo/.git/reftable/tables.list
>      ++	test_line_count -lt $expected repo/.git/reftable/tables.list
>       +'
>       +
>        check_fsync_events () {
>  2:  7e62c2286ae ! 2:  e0f4d0dbcc1 reftable/stack: use geometric table compaction
>      @@ reftable/stack.c: static int segment_size(struct segment *s)
>       -		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev]))
>       +	/*
>       +	 * Find the ending table of the compaction segment needed to restore the
>      -+	 * geometric sequence.
>      ++	 * geometric sequence. Note that the segment end is exclusive.
>       +	 *
>       +	 * 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.
>      ++	 * compaction segment end has been identified.
>       +	 *
>       +	 * 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
>      @@ reftable/stack.c: static int segment_size(struct segment *s)
>       +	 * Example table size sequence requiring no compaction:
>       +	 * 	64, 32, 16, 8, 4, 2, 1
>       +	 *
>      -+	 * Example compaction segment end set to table with size 3:
>      ++	 * Example table size sequence where compaction segment end is set to
>      ++	 * the last table. Since the segment end is exclusive, the last table is
>      ++	 * excluded during subsequent compaction and the table with size 3 is
>      ++	 * the final table included:
>       +	 * 	64, 32, 16, 8, 4, 3, 1
>       +	 */
>       +	for (i = n - 1; i > 0; i--) {
>      @@ reftable/stack_test.c: static void test_empty_add(void)
>       +	int l = 0;
>       +	if (sz == 0)
>       +		return 0;
>      -+	for (; sz; sz /= 2) {
>      ++	for (; sz; sz /= 2)
>       +		l++;
>      -+	}
>       +	return l - 1;
>       +}
>       +
>      @@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: writes cause a
>        
>        	test_commit -C repo --no-tag B &&
>        	test_line_count = 1 repo/.git/reftable/tables.list
>      -@@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: environment variable disables auto-compact
>      - 	do
>      - 		GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C repo update-ref branch-$i HEAD || return 1
>      - 	done &&
>      --	test_line_count = 23 repo/.git/reftable/tables.list &&
>      -+	test_line_count = 22 repo/.git/reftable/tables.list &&
>      - 
>      - 	git -C repo update-ref foo HEAD &&
>      - 	test_line_count = 1 repo/.git/reftable/tables.list
>      +@@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: env var disables compaction' '
>      + 	test_line_count -lt $expected repo/.git/reftable/tables.list
>        '
>        
>       +test_expect_success 'ref transaction: alternating table sizes are compacted' '
>       +	test_when_finished "rm -rf repo" &&
>      ++
>       +	git init repo &&
>       +	test_commit -C repo A &&
>      -+	for i in $(test_seq 20)
>      ++	for i in $(test_seq 5)
>       +	do
>       +		git -C repo branch -f foo &&
>       +		git -C repo branch -d foo || return 1
>      @@ t/t0610-reftable-basics.sh: test_expect_success 'worktree: pack-refs in main rep
>        	test_when_finished "rm -rf repo worktree" &&
>        	git init repo &&
>        	test_commit -C repo A &&
>      --	git -C repo worktree add ../worktree &&
>      -+	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C repo worktree add ../worktree &&
>      -+	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C worktree update-ref refs/worktree/per-worktree HEAD &&
>      ++
>      ++	GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
>      + 	git -C repo worktree add ../worktree &&
>      ++	GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
>      ++	git -C worktree update-ref refs/worktree/per-worktree HEAD &&
>        
>       -	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
>       -	test_line_count = 4 repo/.git/reftable/tables.list &&
>      @@ t/t0610-reftable-basics.sh: test_expect_success 'worktree: pack-refs in worktree
>        	test_when_finished "rm -rf repo worktree" &&
>        	git init repo &&
>        	test_commit -C repo A &&
>      --	git -C repo worktree add ../worktree &&
>      -+	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C repo worktree add ../worktree &&
>      -+	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C worktree update-ref refs/worktree/per-worktree HEAD &&
>      ++
>      ++	GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
>      + 	git -C repo worktree add ../worktree &&
>      ++	GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
>      ++	git -C worktree update-ref refs/worktree/per-worktree HEAD &&
>        
>       -	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
>       -	test_line_count = 4 repo/.git/reftable/tables.list &&
>      @@ t/t0610-reftable-basics.sh: test_expect_success 'worktree: pack-refs in worktree
>        '
>        
>        test_expect_success 'worktree: creating shared ref updates main stack' '
>      - 	test_when_finished "rm -rf repo worktree" &&
>      - 	git init repo &&
>      - 	test_commit -C repo A &&
>      -+	test_commit -C repo B &&
>      - 
>      - 	git -C repo worktree add ../worktree &&
>      - 	git -C repo pack-refs &&
>       @@ t/t0610-reftable-basics.sh: test_expect_success 'worktree: creating shared ref updates main stack' '
>        	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
>        	test_line_count = 1 repo/.git/reftable/tables.list &&
>        
>      --	git -C worktree update-ref refs/heads/shared HEAD &&
>      -+	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C worktree update-ref refs/heads/shared HEAD &&
>      ++	GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
>      + 	git -C worktree update-ref refs/heads/shared HEAD &&
>        	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
>        	test_line_count = 2 repo/.git/reftable/tables.list
>      - '
>  3:  9a33914c852 < -:  ----------- reftable/stack: make segment end inclusive
> 
> -- 
> gitgitgadget