reftable/stack: use geometric table compaction

From: Justin Tobler <[email protected]>

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:

git branch -f foo
git branch -d foo

Each operation results in a new table being written with no compaction occurring until a separate operation produces a table matching the previous table log value.

To avoid unbounded growth of the table list, walk through each table and evaluate if it needs to be included in the compaction segment to restore a geometric sequence.

Some tests in t0610-reftable-basics.sh assert the on-disk state of tables and are therefore updated to specify the correct new table count. Since compaction is more aggressive in ensuring tables maintain a geometric sequence, the expected table count is reduced in these tests. In reftable/stack_test.c tests related to sizes_to_segments() are removed because the function is no longer needed. Also, the test_suggest_compaction_segment() test is updated to better showcase and reflect the new geometric compaction behavior.

Signed-off-by Justin Tobler <[email protected]>

---
reftable/stack: use geometric table compaction

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1683%2Fjltobler%2Fjt%2Freftable-geometric-compaction-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1683/jltobler/jt/reftable-geometric-compaction-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1683

 reftable/stack.c           | 106 +++++++++++++++----------------------
 reftable/stack.h           |   3 --
 reftable/stack_test.c      |  66 +++++------------------
 t/t0610-reftable-basics.sh |  24 ++++-----
 4 files changed, 70 insertions(+), 129 deletions(-)

reftable/stack.c +15 -57

index b64e55648aa..e4ea8753977 100644
@@ -1214,75 +1214,57 @@ static int segment_size(struct segment *s)
 	return s->end - s->start;
 }
 
-int fastlog2(uint64_t sz)
-{
-	int l = 0;
-	if (sz == 0)
-		return 0;
-	for (; sz; sz /= 2) {
-		l++;
-	}
-	return l - 1;
-}
-
-struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n)
-{
-	struct segment *segs = reftable_calloc(n, sizeof(*segs));
-	struct segment cur = { 0 };
-	size_t next = 0, i;
-
-	if (n == 0) {
-		*seglen = 0;
-		return segs;
-	}
-	for (i = 0; i < n; i++) {
-		int log = fastlog2(sizes[i]);
-		if (cur.log != log && cur.bytes > 0) {
-			struct segment fresh = {
-				.start = i,
-			};
-
-			segs[next++] = cur;
-			cur = fresh;
-		}
-
-		cur.log = log;
-		cur.end = i + 1;
-		cur.bytes += sizes[i];
-	}
-	segs[next++] = cur;
-	*seglen = next;
-	return segs;
-}
-
 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
 {
-	struct segment min_seg = {
-		.log = 64,
-	};
-	struct segment *segs;
-	size_t seglen = 0, i;
-
-	segs = sizes_to_segments(&seglen, sizes, n);
-	for (i = 0; i < seglen; i++) {
-		if (segment_size(&segs[i]) == 1)
-			continue;
+	struct segment seg = { 0 };
+	uint64_t bytes;
+	size_t i;
 
-		if (segs[i].log < min_seg.log)
-			min_seg = segs[i];
-	}
+	/*
+	 * If there are no tables or only a single one then we don't have to
+	 * compact anything. The sequence is geometric by definition already.
+	 */
+	if (n <= 1)
+		return seg;
 
-	while (min_seg.start > 0) {
-		size_t prev = min_seg.start - 1;
-		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev]))
+	/*
+	 * 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

reftable/stack.c +4 -0

+	 * stack preceding that first starting point which violate the geometric
+	 * sequence.
+	 */
+	for (; i > 0; i--) {

reftable/stack.c +1 -2

-	reftable_free(segs);
-	return min_seg;
+	return seg;
 }
 
 static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)

reftable/stack.c +0 -0

 test_expect_success 'worktree: creating per-worktree ref updates worktree stack' '
 

base-commit: b387623c12f3f4a376e4d35a610fd3e55d7ea907

Signature · 1 line

gitgitgadget

Quoted 9 lines · Justin Tobler via GitGitGadget

From: Justin Tobler <[email protected]>

reftable/stack.c +1 -1

@@ -1305,7 +1287,7 @@ int reftable_stack_auto_compact(struct reftable_stack *st)
 		suggest_compaction_segment(sizes, st->merged->stack_len);
 	reftable_free(sizes);
 	if (segment_size(&seg) > 0)
-		return stack_compact_range_stats(st, seg.start, seg.end - 1,
+		return stack_compact_range_stats(st, seg.start, seg.end,
 						 NULL);
 

Review int reftable_stack_auto_compact(struct reftable_stack *st) · line 1293

Quoted 1 line

(quoted diff) +0 -0

 	return 0;

One more thing: I think it would make sense to move the refactoring where you change whether the end segment index is inclusive or exclusive into a separate patch so that it's easier to reason about. Also, the fact that no tests would require changes would further stress the point that this is a mere refactoring without unintended side effects.

From: Justin Tobler <[email protected]>

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.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c  | 2 +-
 reftable/system.h | 1 +
 2 files changed, 2 insertions(+), 1 deletion(-)

reftable/stack.c +1 -1

index b64e55648aa..2370d93d13b 100644
@@ -681,7 +681,7 @@ int reftable_addition_commit(struct reftable_addition *add)
 	if (err)
 		goto done;
 
-	if (!add->stack->disable_auto_compact)
+	if (!add->stack->disable_auto_compact && !git_env_bool("GIT_TEST_REFTABLE_NO_AUTOCOMPACTION", 0))
 		err = reftable_stack_auto_compact(add->stack);
 
 done:

reftable/system.h +1 -0

index 6b74a815143..ec08b728177 100644
@@ -15,6 +15,7 @@ license that can be found in the LICENSE file or at
 #include "strbuf.h"
 #include "hash-ll.h" /* hash ID, sizes.*/
 #include "dir.h" /* remove_dir_recursively, for tests.*/
+#include "parse.h"
 
 int hash_size(uint32_t id);
 

Signature · 1 line

gitgitgadget

From: Justin Tobler <[email protected]>

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:

git branch -f foo
git branch -d foo

Each operation results in a new table being written with no compaction occurring until a separate operation produces a table matching the previous table log value.

Instead, to avoid unbounded growth of the table list, the compaction strategy is updated to ensure tables follow a geometric sequence after each operation. This is done by walking the table list in reverse index order to identify the compaction segment start and end. The compaction segment end is found by identifying the first table which has a preceding table size less than twice the current table. Next, the compaction segment start is found iterating through the remaining tables in the list checking if the previous table size is less than twice the cumulative of tables from the segment end. This ensures the correct segment start is found and that the newly compacted table does not violate the geometric sequence.

When creating 10 thousand references, the new strategy has no performance impact:

Benchmark 1: update-ref: create refs sequentially (revision = HEAD~)
Time (mean ± σ): 26.516 s ± 0.047 s [User: 17.864 s, System: 8.491 s]
Range (min … max): 26.447 s … 26.569 s 10 runs

Benchmark 2: update-ref: create refs sequentially (revision = HEAD)
Time (mean ± σ): 26.417 s ± 0.028 s [User: 17.738 s, System: 8.500 s]
Range (min … max): 26.366 s … 26.444 s 10 runs

Summary
update-ref: create refs sequentially (revision = HEAD) ran
1.00 ± 0.00 times faster than update-ref: create refs sequentially (revision = HEAD~)

Some tests in t0610-reftable-basics.sh assert the on-disk state of tables and are therefore updated to specify the correct new table count. Since compaction is more aggressive in ensuring tables maintain a geometric sequence, the expected table count is reduced in these tests. In reftable/stack_test.c tests related to sizes_to_segments() are removed because the function is no longer needed. Also, the test_suggest_compaction_segment() test is updated to better showcase and reflect the new geometric compaction behavior.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c           | 109 ++++++++++++++++---------------------
 reftable/stack.h           |   3 -
 reftable/stack_test.c      |  66 +++++-----------------
 t/t0610-reftable-basics.sh |  43 ++++++++++-----
 4 files changed, 91 insertions(+), 130 deletions(-)

reftable/stack.c +48 -61

index 2370d93d13b..ef55dc75cde 100644
@@ -1214,75 +1214,62 @@ static int segment_size(struct segment *s)
 	return s->end - s->start;
 }
 
-int fastlog2(uint64_t sz)
-{
-	int l = 0;
-	if (sz == 0)
-		return 0;
-	for (; sz; sz /= 2) {
-		l++;
-	}
-	return l - 1;
-}
-
-struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n)
-{
-	struct segment *segs = reftable_calloc(n, sizeof(*segs));
-	struct segment cur = { 0 };
-	size_t next = 0, i;
-
-	if (n == 0) {
-		*seglen = 0;
-		return segs;
-	}
-	for (i = 0; i < n; i++) {
-		int log = fastlog2(sizes[i]);
-		if (cur.log != log && cur.bytes > 0) {
-			struct segment fresh = {
-				.start = i,
-			};
-
-			segs[next++] = cur;
-			cur = fresh;
-		}
-
-		cur.log = log;
-		cur.end = i + 1;
-		cur.bytes += sizes[i];
-	}
-	segs[next++] = cur;
-	*seglen = next;
-	return segs;
-}
-
 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
 {
-	struct segment min_seg = {
-		.log = 64,
-	};
-	struct segment *segs;
-	size_t seglen = 0, i;
-
-	segs = sizes_to_segments(&seglen, sizes, n);
-	for (i = 0; i < seglen; i++) {
-		if (segment_size(&segs[i]) == 1)
-			continue;
+	struct segment seg = { 0 };
+	uint64_t bytes;
+	size_t i;
 
-		if (segs[i].log < min_seg.log)
-			min_seg = segs[i];
-	}
+	/*
+	 * If there are no tables or only a single one then we don't have to
+	 * compact anything. The sequence is geometric by definition already.
+	 */
+	if (n <= 1)
+		return seg;
 
-	while (min_seg.start > 0) {
-		size_t prev = min_seg.start - 1;
-		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev]))
+	/*
+	 * 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.
+	 *
+	 * Note that we keep iterating even after we have found the first
+	 * starting point. This is because there may be tables in the stack
+	 * preceding that first starting point which violate the geometric
+	 * sequence.
+	 */
+	for (; i > 0; i--) {
+		uint64_t curr = bytes;
+		bytes += sizes[i - 1];
 
-		min_seg.start = prev;
-		min_seg.bytes += sizes[prev];
+		if (sizes[i - 1] < curr * 2) {
+			seg.start = i - 1;
+			seg.bytes = bytes;
+		}
 	}
 
-	reftable_free(segs);
-	return min_seg;
+	return seg;
 }
 
 static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)

reftable/stack.h +0 -3

index d919455669e..656f896cc28 100644
@@ -33,12 +33,9 @@ int read_lines(const char *filename, char ***lines);
 
 struct segment {
 	size_t start, end;
-	int log;
 	uint64_t bytes;
 };
 
-int fastlog2(uint64_t sz);
-struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n);
 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n);
 
 #endif

reftable/stack_test.c +14 -52

index 509f4866236..e5f6ff5c9e4 100644
@@ -720,59 +720,14 @@ static void test_reftable_stack_hash_id(void)
 	clear_dir(dir);
 }
 
-static void test_log2(void)
-{
-	EXPECT(1 == fastlog2(3));
-	EXPECT(2 == fastlog2(4));
-	EXPECT(2 == fastlog2(5));
-}
-
-static void test_sizes_to_segments(void)
-{
-	uint64_t sizes[] = { 2, 3, 4, 5, 7, 9 };
-	/* .................0  1  2  3  4  5 */
-
-	size_t seglen = 0;
-	struct segment *segs =
-		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
-	EXPECT(segs[2].log == 3);
-	EXPECT(segs[2].start == 5);
-	EXPECT(segs[2].end == 6);
-
-	EXPECT(segs[1].log == 2);
-	EXPECT(segs[1].start == 2);
-	EXPECT(segs[1].end == 5);
-	reftable_free(segs);
-}
-
-static void test_sizes_to_segments_empty(void)
-{
-	size_t seglen = 0;
-	struct segment *segs = sizes_to_segments(&seglen, NULL, 0);
-	EXPECT(seglen == 0);
-	reftable_free(segs);
-}
-
-static void test_sizes_to_segments_all_equal(void)
-{
-	uint64_t sizes[] = { 5, 5 };
-	size_t seglen = 0;
-	struct segment *segs =
-		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
-	EXPECT(seglen == 1);
-	EXPECT(segs[0].start == 0);
-	EXPECT(segs[0].end == 2);
-	reftable_free(segs);
-}
-
 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 */
 	struct segment min =
 		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
-	EXPECT(min.start == 2);
-	EXPECT(min.end == 7);
+	EXPECT(min.start == 1);
+	EXPECT(min.end == 10);
 }
 
 static void test_suggest_compaction_segment_nothing(void)

@@ -884,6 +839,17 @@ static void test_empty_add(void)
 	reftable_stack_destroy(st2);
 }
 
+static int fastlog2(uint64_t sz)
+{
+	int l = 0;
+	if (sz == 0)
+		return 0;
+	for (; sz; sz /= 2) {
+		l++;
+	}
+	return l - 1;
+}
+
 static void test_reftable_stack_auto_compaction(void)
 {
 	struct reftable_write_options cfg = { 0 };

@@ -1072,7 +1038,6 @@ static void test_reftable_stack_compaction_concurrent_clean(void)
 int stack_test_main(int argc, const char *argv[])
 {
 	RUN_TEST(test_empty_add);
-	RUN_TEST(test_log2);
 	RUN_TEST(test_names_equal);
 	RUN_TEST(test_parse_names);
 	RUN_TEST(test_read_file);

@@ -1092,9 +1057,6 @@ int stack_test_main(int argc, const char *argv[])
 	RUN_TEST(test_reftable_stack_update_index_check);
 	RUN_TEST(test_reftable_stack_uptodate);
 	RUN_TEST(test_reftable_stack_validate_refname);
-	RUN_TEST(test_sizes_to_segments);
-	RUN_TEST(test_sizes_to_segments_all_equal);
-	RUN_TEST(test_sizes_to_segments_empty);
 	RUN_TEST(test_suggest_compaction_segment);
 	RUN_TEST(test_suggest_compaction_segment_nothing);
 	return 0;

t/t0610-reftable-basics.sh +29 -14

index 686781192eb..e6c3f94d874 100755
@@ -293,12 +293,24 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
 	test_line_count = 1 repo/.git/reftable/tables.list &&
 
 	test_commit -C repo --no-tag A &&
-	test_line_count = 2 repo/.git/reftable/tables.list &&
+	test_line_count = 1 repo/.git/reftable/tables.list &&
 
 	test_commit -C repo --no-tag B &&
 	test_line_count = 1 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)
+	do
+		git -C repo branch -f foo &&
+		git -C repo branch -d foo || return 1
+	done &&
+	test_line_count = 2 repo/.git/reftable/tables.list
+'
+
 check_fsync_events () {
 	local trace="$1" &&
 	shift &&

@@ -324,7 +336,7 @@ test_expect_success 'ref transaction: writes are synced' '
 		git -C repo -c core.fsync=reference \
 		-c core.fsyncMethod=fsync update-ref refs/heads/branch HEAD &&
 	check_fsync_events trace2.txt <<-EOF
-	"name":"hardware-flush","count":2
+	"name":"hardware-flush","count":4
 	EOF
 '
 

@@ -346,8 +358,8 @@ test_expect_success 'pack-refs: compacts tables' '
 
 	test_commit -C repo A &&
 	ls -1 repo/.git/reftable >table-files &&
-	test_line_count = 4 table-files &&
-	test_line_count = 3 repo/.git/reftable/tables.list &&
+	test_line_count = 3 table-files &&
+	test_line_count = 2 repo/.git/reftable/tables.list &&
 
 	git -C repo pack-refs &&
 	ls -1 repo/.git/reftable >table-files &&

@@ -379,7 +391,7 @@ do
 			umask $umask &&
 			git init --shared=true repo &&
 			test_commit -C repo A &&
-			test_line_count = 3 repo/.git/reftable/tables.list
+			test_line_count = 2 repo/.git/reftable/tables.list
 		) &&
 		git -C repo pack-refs &&
 		test_expect_perms "-rw-rw-r--" repo/.git/reftable/tables.list &&

@@ -747,12 +759,13 @@ test_expect_success 'worktree: pack-refs in main repo packs main refs' '
 	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 &&
 
-	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
-	test_line_count = 4 repo/.git/reftable/tables.list &&
+	test_line_count = 4 repo/.git/worktrees/worktree/reftable/tables.list &&
+	test_line_count = 3 repo/.git/reftable/tables.list &&
 	git -C repo pack-refs &&
-	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
+	test_line_count = 4 repo/.git/worktrees/worktree/reftable/tables.list &&
 	test_line_count = 1 repo/.git/reftable/tables.list
 '
 

@@ -760,19 +773,21 @@ test_expect_success 'worktree: pack-refs in worktree packs worktree refs' '
 	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 &&
 
-	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
-	test_line_count = 4 repo/.git/reftable/tables.list &&
+	test_line_count = 4 repo/.git/worktrees/worktree/reftable/tables.list &&
+	test_line_count = 3 repo/.git/reftable/tables.list &&
 	git -C worktree pack-refs &&
 	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
-	test_line_count = 4 repo/.git/reftable/tables.list
+	test_line_count = 3 repo/.git/reftable/tables.list
 '
 
 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 &&

@@ -780,7 +795,7 @@ 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 &&
 	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
 	test_line_count = 2 repo/.git/reftable/tables.list
 '

Signature · 1 line

gitgitgadget

From: Justin Tobler <[email protected]>

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:

reftable/stack.c +17 -0

+	/*
+	 * 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;

Hello again,

This is the second version my patch series that refactors the reftable compaction strategy to instead follow a geometric sequence. Changes compared to v1:

* Added GIT_TEST_REFTABLE_NO_AUTOCOMPACTION environment variable to disable reftable compaction when testing.
* Refactored worktree tests in t0610-reftable-basics.sh to properly assert git-pack-refs(1) works as expected.
* Added test to validate that alternating table sizes are compacted.
* Added benchmark to compare compaction strategies.
* Moved change that made compaction segment end inclusive to its own commit.
* Added additional explanation in commits and comments and fixed typos.

Thanks for taking a look!

Quoted 1 line

Thanks for taking a look!

Cc'ing Han-Wen and Josh for additional input. From my point of view the new algorithm is simpler to understand and less fragile, but I do wonder whether there is anything that we're missing.

Quoted 5 lines · Patrick Steinhardt

Quoted 1 line

Thanks for taking a look!

Cc'ing Han-Wen and Josh for additional input. From my point of view the new algorithm is simpler to understand and less fragile, but I do wonder whether there is anything that we're missing.

Good spotting. I hadn't thought about alternating tables.

I have one minor criticism:

Environment variables are untyped global variables without any form of data protection, so I find them unsavoury, and have tried to avoid them throughout. (The whole reftable library only looks at $TMPDIR in tests). They're also accessible to end users, so it can become a feature that can inadvertently become a maintenance burden.

For testing, there is a stack->disable_auto_compact.

If you want to keep that style, I would elevate disable_auto_compact into reftable_write_options to make it API surface. This will let you use it in tests written in C, which can be unittests and therefore more precise and fine-grained. They also run more quickly, and are easier to instrument with asan/valgrind/etc. The test for tables with alternating sizes can be easily written in C.

If you really need it, you could initialize disable_auto_compact from the environment, but I would suggest avoiding it if possible.

Quoted 26 lines · Han-Wen Nienhuys

Quoted 5 lines · Patrick Steinhardt

Quoted 1 line

Thanks for taking a look!

Cc'ing Han-Wen and Josh for additional input. From my point of view the new algorithm is simpler to understand and less fragile, but I do wonder whether there is anything that we're missing.

Good spotting. I hadn't thought about alternating tables.

I have one minor criticism:

Environment variables are untyped global variables without any form of data protection, so I find them unsavoury, and have tried to avoid them throughout. (The whole reftable library only looks at $TMPDIR in tests). They're also accessible to end users, so it can become a feature that can inadvertently become a maintenance burden.

For testing, there is a stack->disable_auto_compact.

If you want to keep that style, I would elevate disable_auto_compact into reftable_write_options to make it API surface. This will let you use it in tests written in C, which can be unittests and therefore more precise and fine-grained. They also run more quickly, and are easier to instrument with asan/valgrind/etc. The test for tables with alternating sizes can be easily written in C.

Quoted 2 lines

If you really need it, you could initialize disable_auto_compact from the environment, but I would suggest avoiding it if possible.

That's actually a good point. I think keeping this as an environment variable isn't too bad as a stop-gap measure for now, and it should be obvious to users that it's not for general use due to the GIT_TEST prefix.

But I'm definitely supportive of lifting it out of the reftable library and into the reftable backend so that it is specific to Git, not to the reftable library.

But I'm definitely supportive of lifting it out of the reftable library and into the reftable backend so that it is specific to Git, not to the reftable library.

From: Justin Tobler <[email protected]>

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.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c           |  2 +-
 reftable/system.h          |  1 +
 t/t0610-reftable-basics.sh | 15 +++++++++++++++
 3 files changed, 17 insertions(+), 1 deletion(-)

reftable/stack.c +1 -1

index 1ecf1b9751c..07262beaaf7 100644
@@ -681,7 +681,7 @@ int reftable_addition_commit(struct reftable_addition *add)
 	if (err)
 		goto done;
 
-	if (!add->stack->disable_auto_compact)
+	if (!add->stack->disable_auto_compact && !git_env_bool("GIT_TEST_REFTABLE_NO_AUTOCOMPACTION", 0))
 		err = reftable_stack_auto_compact(add->stack);
 
 done:

reftable/system.h +1 -0

index 5d8b6dede50..05b7c8554af 100644
@@ -17,6 +17,7 @@ license that can be found in the LICENSE file or at
 #include "tempfile.h"
 #include "hash-ll.h" /* hash ID, sizes.*/
 #include "dir.h" /* remove_dir_recursively, for tests.*/
+#include "parse.h"
 
 int hash_size(uint32_t id);
 

t/t0610-reftable-basics.sh +0 -0

index 686781192eb..434044078ed 100755
@@ -299,6 +299,21 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
 	test_line_count = 1 repo/.git/reftable/tables.list
 '
 

t/t0610-reftable-basics.sh +4 -0

+	git -C repo update-ref foo HEAD &&
+	test_line_count = 1 repo/.git/reftable/tables.list
+'
+
 check_fsync_events () {
 	local trace="$1" &&
 	shift &&

reftable/system.h +1 -0

index 5d8b6dede50..05b7c8554af 100644
@@ -17,6 +17,7 @@ license that can be found in the LICENSE file or at
 #include "tempfile.h"
 #include "hash-ll.h" /* hash ID, sizes.*/
 #include "dir.h" /* remove_dir_recursively, for tests.*/
+#include "parse.h"
 
 int hash_size(uint32_t id);
 

t/t0610-reftable-basics.sh +0 -0

index 686781192eb..434044078ed 100755
@@ -299,6 +299,21 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
 	test_line_count = 1 repo/.git/reftable/tables.list

t/t0610-reftable-basics.sh +7 -0

+	done &&
+	test_line_count = 23 repo/.git/reftable/tables.list &&
+
+	git -C repo update-ref foo HEAD &&
+	test_line_count = 1 repo/.git/reftable/tables.list
+'
+
 check_fsync_events () {
 	local trace="$1" &&
 	shift &&

From: Justin Tobler <[email protected]>

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.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c           |  2 +-
 reftable/system.h          |  1 +
 t/t0610-reftable-basics.sh | 15 +++++++++++++++
 3 files changed, 17 insertions(+), 1 deletion(-)

reftable/stack.c +0 -0

index 1ecf1b9751c..07262beaaf7 100644

reftable/stack.c +0 -0

 done:

reftable/system.h +1 -0

index 5d8b6dede50..05b7c8554af 100644
@@ -17,6 +17,7 @@ license that can be found in the LICENSE file or at
 #include "tempfile.h"
 #include "hash-ll.h" /* hash ID, sizes.*/
 #include "dir.h" /* remove_dir_recursively, for tests.*/
+#include "parse.h"
 
 int hash_size(uint32_t id);
 

t/t0610-reftable-basics.sh +15 -0

index 686781192eb..434044078ed 100755
@@ -299,6 +299,21 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
 	test_line_count = 1 repo/.git/reftable/tables.list
 '
 
+test_expect_success 'ref transaction: environment variable disables auto-compaction' '
+	test_when_finished "rm -rf repo" &&
+
+	git init repo &&
+	test_commit -C repo A &&
+	for i in $(test_seq 20)
+	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 &&
+
+	git -C repo update-ref foo HEAD &&
+	test_line_count = 1 repo/.git/reftable/tables.list
+'
+
 check_fsync_events () {
 	local trace="$1" &&
 	shift &&

Signature · 1 line

gitgitgadget

reftable/stack.c int reftable_addition_commit(struct reftable_addition *add) · line 685

Quoted 3 lines

reftable/stack.c +1 -1

-	if (!add->stack->disable_auto_compact)
+	if (!add->stack->disable_auto_compact && !git_env_bool("GIT_TEST_REFTABLE_NO_AUTOCOMPACTION", 0))
 		err = reftable_stack_auto_compact(add->stack);

The double-negation in GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=false may be somewhat hard to parse. Should we rename this to GIT_TEST_REFTABLE_AUTO_COMPACTION with a default value of 1?

From: Justin Tobler <[email protected]>

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:

git branch -f foo
git branch -d foo

Each operation results in a new table being written with no compaction occurring until a separate operation produces a table matching the previous table log value.

Instead, to avoid unbounded growth of the table list, the compaction strategy is updated to ensure tables follow a geometric sequence after each operation by individually evaluating each table in reverse index order. This strategy results in a much simpler and more robust algorithm compared to the previous one while also maintaining a minimal ordered set of tables on-disk.

When creating 10 thousand references, the new strategy has no performance impact:

Benchmark 1: update-ref: create refs sequentially (revision = HEAD~)
Time (mean ± σ): 26.516 s ± 0.047 s [User: 17.864 s, System: 8.491 s]
Range (min … max): 26.447 s … 26.569 s 10 runs

Benchmark 2: update-ref: create refs sequentially (revision = HEAD)
Time (mean ± σ): 26.417 s ± 0.028 s [User: 17.738 s, System: 8.500 s]
Range (min … max): 26.366 s … 26.444 s 10 runs

Summary
update-ref: create refs sequentially (revision = HEAD) ran
1.00 ± 0.00 times faster than update-ref: create refs sequentially (revision = HEAD~)

Some tests in t0610-reftable-basics.sh assert the on-disk state of tables and are therefore updated to specify the correct new table count. Since compaction is more aggressive in ensuring tables maintain a geometric sequence, the expected table count is reduced in these tests. In reftable/stack_test.c tests related to sizes_to_segments() are removed because the function is no longer needed. Also, the test_suggest_compaction_segment() test is updated to better showcase and reflect the new geometric compaction behavior.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c           | 120 ++++++++++++++++++-------------------
 reftable/stack.h           |   3 -
 reftable/stack_test.c      |  67 +++++----------------
 t/t0610-reftable-basics.sh |  45 +++++++++-----
 4 files changed, 103 insertions(+), 132 deletions(-)

reftable/stack.c +59 -61

index 07262beaaf7..e7b9a1de5a4 100644
@@ -1202,75 +1202,73 @@ static int segment_size(struct segment *s)
 	return s->end - s->start;
 }
 
-int fastlog2(uint64_t sz)
-{
-	int l = 0;
-	if (sz == 0)
-		return 0;
-	for (; sz; sz /= 2) {
-		l++;
-	}
-	return l - 1;
-}
-
-struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n)
-{
-	struct segment *segs = reftable_calloc(n, sizeof(*segs));
-	struct segment cur = { 0 };
-	size_t next = 0, i;
-
-	if (n == 0) {
-		*seglen = 0;
-		return segs;
-	}
-	for (i = 0; i < n; i++) {
-		int log = fastlog2(sizes[i]);
-		if (cur.log != log && cur.bytes > 0) {
-			struct segment fresh = {
-				.start = i,
-			};
-
-			segs[next++] = cur;
-			cur = fresh;
-		}
-
-		cur.log = log;
-		cur.end = i + 1;
-		cur.bytes += sizes[i];
-	}
-	segs[next++] = cur;
-	*seglen = next;
-	return segs;
-}
-
 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
 {
-	struct segment min_seg = {
-		.log = 64,
-	};
-	struct segment *segs;
-	size_t seglen = 0, i;
-
-	segs = sizes_to_segments(&seglen, sizes, n);
-	for (i = 0; i < seglen; i++) {
-		if (segment_size(&segs[i]) == 1)
-			continue;
+	struct segment seg = { 0 };
+	uint64_t bytes;
+	size_t i;
 
-		if (segs[i].log < min_seg.log)
-			min_seg = segs[i];
-	}
+	/*
+	 * If there are no tables or only a single one then we don't have to
+	 * compact anything. The sequence is geometric by definition already.
+	 */
+	if (n <= 1)
+		return seg;
 
-	while (min_seg.start > 0) {
-		size_t prev = min_seg.start - 1;
-		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev]))
+	/*
+	 * 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.
+	 *
+	 * Example table size sequence requiring no compaction:
+	 * 	64, 32, 16, 8, 4, 2, 1
+	 *
+	 * Example compaction segment end set to table with size 3:
+	 * 	64, 32, 16, 8, 4, 3, 1
+	 */
+	for (i = n - 1; i > 0; i--) {
+		if (sizes[i - 1] < sizes[i] * 2) {
+			seg.end = i + 1;
+			bytes = sizes[i];
 			break;
+		}
+	}
 
-		min_seg.start = prev;
-		min_seg.bytes += sizes[prev];
+	/*
+	 * 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. The previous
+	 * table is compared to the accumulated size because the tables from the
+	 * segment end are merged backwards recursively.
+	 *
+	 * Note that we keep iterating even after we have found the first
+	 * starting point. This is because there may be tables in the stack
+	 * preceding that first starting point which violate the geometric
+	 * sequence.
+	 *
+	 * Example compaction segment start set to table with size 32:
+	 * 	128, 32, 16, 8, 4, 3, 1
+	 */
+	for (; i > 0; i--) {
+		uint64_t curr = bytes;
+		bytes += sizes[i - 1];
+
+		if (sizes[i - 1] < curr * 2) {
+			seg.start = i - 1;
+			seg.bytes = bytes;
+		}
 	}
 
-	reftable_free(segs);
-	return min_seg;
+	return seg;
 }
 
 static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)

reftable/stack.h +0 -3

index d919455669e..656f896cc28 100644
@@ -33,12 +33,9 @@ int read_lines(const char *filename, char ***lines);
 
 struct segment {
 	size_t start, end;
-	int log;
 	uint64_t bytes;
 };
 
-int fastlog2(uint64_t sz);
-struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n);
 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n);
 
 #endif

reftable/stack_test.c +3 -49

index 7336757cf53..21541742fe5 100644
@@ -717,59 +717,13 @@ static void test_reftable_stack_hash_id(void)
 	clear_dir(dir);
 }
 
-static void test_log2(void)
-{
-	EXPECT(1 == fastlog2(3));
-	EXPECT(2 == fastlog2(4));
-	EXPECT(2 == fastlog2(5));
-}
-
-static void test_sizes_to_segments(void)
-{
-	uint64_t sizes[] = { 2, 3, 4, 5, 7, 9 };
-	/* .................0  1  2  3  4  5 */
-
-	size_t seglen = 0;
-	struct segment *segs =
-		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
-	EXPECT(segs[2].log == 3);
-	EXPECT(segs[2].start == 5);
-	EXPECT(segs[2].end == 6);
-
-	EXPECT(segs[1].log == 2);
-	EXPECT(segs[1].start == 2);
-	EXPECT(segs[1].end == 5);
-	reftable_free(segs);
-}
-
-static void test_sizes_to_segments_empty(void)
-{
-	size_t seglen = 0;
-	struct segment *segs = sizes_to_segments(&seglen, NULL, 0);
-	EXPECT(seglen == 0);
-	reftable_free(segs);
-}
-
-static void test_sizes_to_segments_all_equal(void)
-{
-	uint64_t sizes[] = { 5, 5 };
-	size_t seglen = 0;
-	struct segment *segs =
-		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
-	EXPECT(seglen == 1);
-	EXPECT(segs[0].start == 0);
-	EXPECT(segs[0].end == 2);
-	reftable_free(segs);
-}
-
 static void test_suggest_compaction_segment(void)
 {
-	uint64_t sizes[] = { 128, 64, 17, 16, 9, 9, 9, 16, 16 };
-	/* .................0    1    2  3   4  5  6 */
+	uint64_t sizes[] = { 512, 64, 17, 16, 9, 9, 9, 16, 2, 16 };
 	struct segment min =
 		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
-	EXPECT(min.start == 2);
-	EXPECT(min.end == 7);
+	EXPECT(min.start == 1);
+	EXPECT(min.end == 10);
 }
 
 static void test_suggest_compaction_segment_nothing(void)

@@ -880,6 +834,17 @@ static void test_empty_add(void)
 	reftable_stack_destroy(st2);

reftable/stack_test.c +3 -4

+	return l - 1;
+}
+
 static void test_reftable_stack_auto_compaction(void)
 {
 	struct reftable_write_options cfg = { 0 };

@@ -1068,7 +1033,6 @@ static void test_reftable_stack_compaction_concurrent_clean(void)
 int stack_test_main(int argc, const char *argv[])
 {
 	RUN_TEST(test_empty_add);
-	RUN_TEST(test_log2);
 	RUN_TEST(test_names_equal);
 	RUN_TEST(test_parse_names);
 	RUN_TEST(test_read_file);

@@ -1088,9 +1052,6 @@ int stack_test_main(int argc, const char *argv[])
 	RUN_TEST(test_reftable_stack_update_index_check);
 	RUN_TEST(test_reftable_stack_uptodate);
 	RUN_TEST(test_reftable_stack_validate_refname);
-	RUN_TEST(test_sizes_to_segments);
-	RUN_TEST(test_sizes_to_segments_all_equal);
-	RUN_TEST(test_sizes_to_segments_empty);
 	RUN_TEST(test_suggest_compaction_segment);
 	RUN_TEST(test_suggest_compaction_segment_nothing);
 	return 0;

t/t0610-reftable-basics.sh +2 -2

index 434044078ed..b95626549e7 100755
@@ -293,7 +293,7 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
 	test_line_count = 1 repo/.git/reftable/tables.list &&
 
 	test_commit -C repo --no-tag A &&
-	test_line_count = 2 repo/.git/reftable/tables.list &&
+	test_line_count = 1 repo/.git/reftable/tables.list &&
 
 	test_commit -C repo --no-tag B &&
 	test_line_count = 1 repo/.git/reftable/tables.list

@@ -308,12 +308,24 @@ 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 &&

From: Justin Tobler <[email protected]>

For a reftable segment, the start of the range is inclusive and the end is exclusive. In practice we increment the end when creating the compaction segment only to decrement the segment end when using it.

Simplify by making the segment end inclusive. The corresponding test, test_suggest_compaction_segment(), is updated to show that the segment end is now inclusive.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c      | 4 ++--
 reftable/stack_test.c | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

reftable/stack.c +2 -2

index e7b9a1de5a4..0973c47dd92 100644
@@ -1237,7 +1237,7 @@ struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
 	 */
 	for (i = n - 1; i > 0; i--) {
 		if (sizes[i - 1] < sizes[i] * 2) {
-			seg.end = i + 1;
+			seg.end = i;
 			bytes = sizes[i];
 			break;
 		}

@@ -1291,7 +1291,7 @@ int reftable_stack_auto_compact(struct reftable_stack *st)
 		suggest_compaction_segment(sizes, st->merged->stack_len);
 	reftable_free(sizes);
 	if (segment_size(&seg) > 0)
-		return stack_compact_range_stats(st, seg.start, seg.end - 1,
+		return stack_compact_range_stats(st, seg.start, seg.end,
 						 NULL);
 
 	return 0;

reftable/stack_test.c +1 -1

index 21541742fe5..4d7305623a0 100644
@@ -723,7 +723,7 @@ static void test_suggest_compaction_segment(void)
 	struct segment min =
 		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
 	EXPECT(min.start == 1);
-	EXPECT(min.end == 10);
+	EXPECT(min.end == 9);
 }
 
 static void test_suggest_compaction_segment_nothing(void)

Quoted 10 lines · Justin Tobler via GitGitGadget

From: Justin Tobler <[email protected]>

For a reftable segment, the start of the range is inclusive and the end is exclusive. In practice we increment the end when creating the compaction segment only to decrement the segment end when using it.

Simplify by making the segment end inclusive. The corresponding test, test_suggest_compaction_segment(), is updated to show that the segment end is now inclusive.

Quoted 5 lines

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/stack.c      | 4 ++--
 reftable/stack_test.c | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

I'd defer it to Patrick (and Han-Wen, if he wants to comment on it), but isn't it a natural expectation shared among CS folks that it is the most usual way to express a range to use inclusive lower-end and exclusive upper-end?

After all, that is how an array works, i.e. msg[n] is NULL and beyond the end where n == strlen(msg).

So, I dunno.

Quoted 38 lines

reftable/stack.c +2 -2

index e7b9a1de5a4..0973c47dd92 100644
@@ -1237,7 +1237,7 @@ struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
 	 */
 	for (i = n - 1; i > 0; i--) {
 		if (sizes[i - 1] < sizes[i] * 2) {
-			seg.end = i + 1;
+			seg.end = i;
 			bytes = sizes[i];
 			break;
 		}

@@ -1291,7 +1291,7 @@ int reftable_stack_auto_compact(struct reftable_stack *st)
 		suggest_compaction_segment(sizes, st->merged->stack_len);
 	reftable_free(sizes);
 	if (segment_size(&seg) > 0)
-		return stack_compact_range_stats(st, seg.start, seg.end - 1,
+		return stack_compact_range_stats(st, seg.start, seg.end,
 						 NULL);
 
 	return 0;

reftable/stack_test.c +1 -1

index 21541742fe5..4d7305623a0 100644
@@ -723,7 +723,7 @@ static void test_suggest_compaction_segment(void)
 	struct segment min =
 		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
 	EXPECT(min.start == 1);
-	EXPECT(min.end == 10);
+	EXPECT(min.end == 9);
 }
 
 static void test_suggest_compaction_segment_nothing(void)

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 <[email protected]>
      
     @@ 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

Signature · 1 line

gitgitgadget

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.

From: Justin Tobler <[email protected]>

Move the disable_auto_compact option into reftable_write_options to allow a stack to be configured with auto-compaction disabled. In a subsequent commit, this is used to disable auto-compaction when a specific environment variable is set.

Signed-off-by Justin Tobler <[email protected]>

---
 reftable/reftable-writer.h |  3 +++
 reftable/stack.c           |  2 +-
 reftable/stack.h           |  1 -
 reftable/stack_test.c      | 11 ++++++-----
 4 files changed, 10 insertions(+), 7 deletions(-)

reftable/reftable-writer.h +3 -0

index 7c7cae5f99b..155bf0bbe2a 100644
@@ -46,6 +46,9 @@ struct reftable_write_options {
 	 *   is a single line, and add '\n' if missing.
 	 */
 	unsigned exact_log_message : 1;
+
+	/* boolean: Prevent auto-compaction of tables. */
+	unsigned disable_auto_compact : 1;
 };
 
 /* reftable_block_stats holds statistics for a single block type */

reftable/stack.c +1 -1

index dde50b61d69..1a7cdad12c9 100644
@@ -680,7 +680,7 @@ int reftable_addition_commit(struct reftable_addition *add)
 	if (err)
 		goto done;
 
-	if (!add->stack->disable_auto_compact) {
+	if (!add->stack->config.disable_auto_compact) {
 		/*
 		 * Auto-compact the stack to keep the number of tables in
 		 * control. It is possible that a concurrent writer is already

reftable/stack.h +0 -1

index d919455669e..c862053025f 100644
@@ -19,7 +19,6 @@ struct reftable_stack {
 	int list_fd;
 
 	char *reftable_dir;
-	int disable_auto_compact;
 
 	struct reftable_write_options config;
 

reftable/stack_test.c +6 -5

index 351e35bd86d..4fec823f14f 100644
@@ -325,7 +325,7 @@ static void test_reftable_stack_transaction_api_performs_auto_compaction(void)
 		 * we can ensure that we indeed honor this setting and have
 		 * better control over when exactly auto compaction runs.
 		 */
-		st->disable_auto_compact = i != n;
+		st->config.disable_auto_compact = i != n;
 
 		err = reftable_stack_new_addition(&add, st);
 		EXPECT_ERR(err);

@@ -497,6 +497,7 @@ static void test_reftable_stack_add(void)
 	struct reftable_write_options cfg = {
 		.exact_log_message = 1,
 		.default_permissions = 0660,
+		.disable_auto_compact = 1,
 	};
 	struct reftable_stack *st = NULL;
 	char *dir = get_tmp_dir(__LINE__);

@@ -508,7 +509,6 @@ static void test_reftable_stack_add(void)
 
 	err = reftable_new_stack(&st, dir, cfg);
 	EXPECT_ERR(err);
-	st->disable_auto_compact = 1;
 
 	for (i = 0; i < N; i++) {
 		char buf[256];

@@ -935,7 +935,9 @@ static void test_empty_add(void)
 
 static void test_reftable_stack_auto_compaction(void)
 {
-	struct reftable_write_options cfg = { 0 };
+	struct reftable_write_options cfg = {
+		.disable_auto_compact = 1,
+	};
 	struct reftable_stack *st = NULL;
 	char *dir = get_tmp_dir(__LINE__);
 

@@ -945,7 +947,6 @@ static void test_reftable_stack_auto_compaction(void)
 	err = reftable_new_stack(&st, dir, cfg);
 	EXPECT_ERR(err);
 
-	st->disable_auto_compact = 1; /* call manually below for coverage. */
 	for (i = 0; i < N; i++) {
 		char name[100];
 		struct reftable_ref_record ref = {

@@ -994,7 +995,7 @@ static void test_reftable_stack_add_performs_auto_compaction(void)
 		 * we can ensure that we indeed honor this setting and have
 		 * better control over when exactly auto compaction runs.
 		 */
-		st->disable_auto_compact = i != n;
+		st->config.disable_auto_compact = i != n;
 
 		strbuf_reset(&refname);
 		strbuf_addf(&refname, "branch-%04d", i);

Signature · 1 line

gitgitgadget

From: Justin Tobler <[email protected]>

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_AUTOCOMPACTION environment variable that, when set to false, disables autocompaction of reftables.

Signed-off-by Justin Tobler <[email protected]>

---
 refs/reftable-backend.c    |  4 ++++
 t/t0610-reftable-basics.sh | 21 +++++++++++++++++++++
 2 files changed, 25 insertions(+)

refs/reftable-backend.c +1 -0

index 0bed6d2ab48..6b6191f89dd 100644
@@ -18,6 +18,7 @@
 #include "../reftable/reftable-merged.h"
 #include "../setup.h"
 #include "../strmap.h"
+#include "parse.h"
 #include "refs-internal.h"
 
 /*

refs/reftable-backend.c +0 -0

 	/*
 	 * Set up the main reftable stack that is hosted in GIT_COMMON_DIR.
 	 * This stack contains both the shared and the main worktree refs.

t/t0610-reftable-basics.sh +21 -0

index 931d888bbbc..c9e10b34684 100755
@@ -299,6 +299,27 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
 	test_line_count = 1 repo/.git/reftable/tables.list
 '
 
+test_expect_success 'ref transaction: env var disables compaction' '
+	test_when_finished "rm -rf repo" &&
+
+	git init repo &&
+	test_commit -C repo A &&
+
+	start=$(wc -l <repo/.git/reftable/tables.list) &&
+	iterations=5 &&
+	expected=$((start + iterations)) &&
+
+	for i in $(test_seq $iterations)
+	do
+		GIT_TEST_REFTABLE_AUTOCOMPACTION=false \
+		git -C repo update-ref branch-$i HEAD || return 1
+	done &&
+	test_line_count = $expected repo/.git/reftable/tables.list &&
+
+	git -C repo update-ref foo HEAD &&
+	test_line_count -lt $expected repo/.git/reftable/tables.list
+'
+
 check_fsync_events () {
 	local trace="$1" &&
 	shift &&

Signature · 1 line

gitgitgadget

refs/reftable-backend.c static struct ref_store *reftable_be_init(struct repository *repo, · line 254

Quoted 7 lines

refs/reftable-backend.c +3 -0

@@ -248,6 +249,9 @@ static struct ref_store *reftable_be_init(struct repository *repo,
 	refs->write_options.hash_id = repo->hash_algo->format_id;
 	refs->write_options.default_permissions = calc_shared_perm(0666 & ~mask);
 
+	if (!git_env_bool("GIT_TEST_REFTABLE_AUTOCOMPACTION", 1))
+		refs->write_options.disable_auto_compact = 1;
+

This could be simplified to:

    ```
    refs->write_options.disable_auto_compact =
            !git_env_bool("GIT_TEST_REFTABLE_AUTOCOMPACTION", 1);
    ```

Hello again,

This is the fifth version my patch series that refactors the reftable compaction strategy to instead follow a geometric sequence. Changes compared to v4:

* To fix some failing tests and conflicts, this patch series now depends on the ps/pack-refs-auto series which is currently in next.
* Lifted the GIT_TEST_REFTABLE_AUTOCOMPACTION env out of the reftable library and into the reftable backend code.

Thanks for taking a look!

-Justin

Justin Tobler (3):
reftable/stack: allow disabling of auto-compaction reftable/stack: add env to disable autocompaction reftable/stack: use geometric table compaction

 refs/reftable-backend.c    |   4 ++
 reftable/reftable-writer.h |   3 +
 reftable/stack.c           | 125 +++++++++++++++++++------------------
 reftable/stack.h           |   4 --
 reftable/stack_test.c      |  77 ++++++-----------------
 t/t0610-reftable-basics.sh |  71 ++++++++++++++++-----
 6 files changed, 146 insertions(+), 138 deletions(-)

base-commit: 4b32163adf4863c6df3bb6b43540fa2ca3494e28
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1683%2Fjltobler%2Fjt%2Freftable-geometric-compaction-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1683/jltobler/jt/reftable-geometric-compaction-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/1683

Range-diff vs v4:

 -:  ----------- > 1:  a7011dbc6aa reftable/stack: allow disabling of auto-compaction
 1:  2a0421e5f20 ! 2:  7c4fe0e9ec5 reftable/stack: add env to disable autocompaction

@@ Commit message

Signed-off-by Justin Tobler <[email protected]>

- ## reftable/stack.c ##
-@@ reftable/stack.c: int reftable_addition_commit(struct reftable_addition *add)
- if (err)
- goto done;
-
-- if (!add->stack->disable_auto_compact)
-+ if (!add->stack->disable_auto_compact &&
-+ git_env_bool("GIT_TEST_REFTABLE_AUTOCOMPACTION", 1))
- err = reftable_stack_auto_compact(add->stack);
-
- done:
-
- ## reftable/system.h ##
-@@ reftable/system.h: license that can be found in the LICENSE file or at
- #include "tempfile.h"
- #include "hash-ll.h" /* hash ID, sizes.*/
- #include "dir.h" /* remove_dir_recursively, for tests.*/
+ ## refs/reftable-backend.c ##
+@@
+ #include "../reftable/reftable-merged.h"
+ #include "../setup.h"
+ #include "../strmap.h"
+#include "parse.h"
+ #include "refs-internal.h"

- int hash_size(uint32_t id);
+ /*
+@@ refs/reftable-backend.c: static struct ref_store *reftable_be_init(struct repository *repo,
+ refs->write_options.hash_id = repo->hash_algo->format_id;
+ refs->write_options.default_permissions = calc_shared_perm(0666 & ~mask);

++ if (!git_env_bool("GIT_TEST_REFTABLE_AUTOCOMPACTION", 1))
++ refs->write_options.disable_auto_compact = 1;
++
+ /*
+ * Set up the main reftable stack that is hosted in GIT_COMMON_DIR.
+ * This stack contains both the shared and the main worktree refs.

## t/t0610-reftable-basics.sh ##
@@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: writes cause auto-compaction' '
2: e0f4d0dbcc1 ! 3: 8f124acf0f8 reftable/stack: use geometric table compaction
@@ reftable/stack_test.c: static void test_empty_add(void)
+
static void test_reftable_stack_auto_compaction(void)
{
- struct reftable_write_options cfg = { 0 };
+ struct reftable_write_options cfg = {
@@ reftable/stack_test.c: static void test_reftable_stack_compaction_concurrent_clean(void)
int stack_test_main(int argc, const char *argv[])
{
@@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: writes are syn
EOF
'

+@@ t/t0610-reftable-basics.sh: test_expect_success 'ref transaction: fails gracefully when auto compaction fail
+ done ||
+ exit 1
+ done &&
+- test_line_count = 13 .git/reftable/tables.list
++ test_line_count = 10 .git/reftable/tables.list
+ )
+ '
+
@@ t/t0610-reftable-basics.sh: test_expect_success 'pack-refs: compacts tables' '

test_commit -C repo A &&
@@ t/t0610-reftable-basics.sh: test_expect_success 'pack-refs: compacts tables' '

git -C repo pack-refs &&
ls -1 repo/.git/reftable >table-files &&
+@@ t/t0610-reftable-basics.sh: test_expect_success "$command: auto compaction" '
+ # The tables should have been auto-compacted, and thus auto
+ # compaction should not have to do anything.
+ ls -1 .git/reftable >tables-expect &&
+- test_line_count = 4 tables-expect &&
++ test_line_count = 3 tables-expect &&
+ git $command --auto &&
+ ls -1 .git/reftable >tables-actual &&
+ test_cmp tables-expect tables-actual &&
+@@ t/t0610-reftable-basics.sh: test_expect_success "$command: auto compaction" '
+ git branch B &&
+ git branch C &&
+ rm .git/reftable/*.lock &&
+- test_line_count = 5 .git/reftable/tables.list &&
++ test_line_count = 4 .git/reftable/tables.list &&
+
+ git $command --auto &&
+ test_line_count = 1 .git/reftable/tables.list
@@ t/t0610-reftable-basics.sh: do
umask $umask &&
git init --shared=true repo &&

Signature · 1 line

gitgitgadget

Quoted 11 lines · Justin Tobler via GitGitGadget

Hello again,

This is the fifth version my patch series that refactors the reftable compaction strategy to instead follow a geometric sequence. Changes compared to v4:

* To fix some failing tests and conflicts, this patch series now depends on the ps/pack-refs-auto series which is currently in next.
* Lifted the GIT_TEST_REFTABLE_AUTOCOMPACTION env out of the reftable library and into the reftable backend code.

Quoted 3 lines

Thanks for taking a look!

-Justin

I've added two additional nits which you may or may not want to address. But overall this patch series looks good to me. Thanks!