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

["Justin Tobler via GitGitGadget" <gitgitgadget@gmail.com>]

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
   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!

-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 <jltobler@gmail.com>
      
     @@ 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