| Message ID | pull.1683.v4.git.1712103636.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | reftable/stack: use geometric table compaction | expand |
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 <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
Hello, "Justin Tobler via GitGitGadget" <gitgitgadget@gmail.com> writes: > 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 > Just a note that this doesn't merge nicely with nice because of conflicts with a2f711ade0c4816a59155d72559cbc4759cd4699.
Karthik Nayak <karthik.188@gmail.com> writes: > Just a note that this doesn't merge nicely with nice because of > conflicts with a2f711ade0c4816a59155d72559cbc4759cd4699. True. I've been resolving the conflict already, so there is not much new to see here ;-) It seems that the plan is to update the section that conflicts even further to avoid the access to the environment variable, so I'll have to update my rerere database yet another time. Thanks.
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