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@xxxxxxxxx> @@ 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