[PATCH v4 00/24] pack-bitmap: pseudo-merge reachability bitmaps
- From
Taylor Blau <me@ttaylorr.com>
- Date
- May 23, 2024, 21:26 UTC
- Message-ID
- <cover.1716499565.git.me@ttaylorr.com>
- In-Reply-To
- <cover.1710972293.git.me@ttaylorr.com>
Here is another reroll my topic to introduce pseudo-merge bitmaps.
The implementation is still relatively unchanged compared to last time, save for the review that Peff provided on the remaining parts of this series.
As usual, there is a range-diff below, but the significant changes since last time are as follows:
- replace git_config_float() with git_config_double() (and matching
tweaks in the callers) - add a NOTE to gitpacking(7) reflecting that the pseudo-merge bitmaps
feature is considered experimental - add a length check when reading extended pseudo merges via the
pseudo_merge_ext_at() function - replace the new `--date` option for `test_commit_bulk` with a
`--notick` option (and set the GIT_COMMITTER_DATE values
appropriately at the callers) - fix broken performance tests due to a typo on "pseudo", and include
results from a large repository.The series is still based on 'tb/pack-bitmap-write-cleanups'.
Taylor Blau (24): Documentation/gitpacking.txt: initial commit Documentation/gitpacking.txt: describe pseudo-merge bitmaps Documentation/technical: describe pseudo-merge bitmaps format ewah: implement `ewah_bitmap_is_subset()` pack-bitmap: move some initialization to `bitmap_writer_init()` pseudo-merge.ch: initial commit pack-bitmap-write: support storing pseudo-merge commits pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public config: introduce `git_config_double()` pseudo-merge: implement support for selecting pseudo-merge commits pack-bitmap-write.c: write pseudo-merge table pack-bitmap: extract `read_bitmap()` function pseudo-merge: scaffolding for reads pack-bitmap.c: read pseudo-merge extension pseudo-merge: implement support for reading pseudo-merge commits ewah: implement `ewah_bitmap_popcount()` pack-bitmap: implement test helpers for pseudo-merge t/test-lib-functions.sh: support `--notick` in `test_commit_bulk()` pack-bitmap.c: use pseudo-merges during traversal pack-bitmap: extra trace2 information ewah: `bitmap_equals_ewah()` pseudo-merge: implement support for finding existing merges t/perf: implement performance tests for pseudo-merge bitmaps
Documentation/Makefile | 1 + Documentation/config.txt | 2 + Documentation/config/bitmap-pseudo-merge.txt | 91 +++ Documentation/gitpacking.txt | 189 +++++ Documentation/technical/bitmap-format.txt | 132 ++++ Makefile | 1 + builtin/pack-objects.c | 3 +- config.c | 9 + config.h | 7 + ewah/bitmap.c | 76 ++ ewah/ewok.h | 8 + midx-write.c | 2 +- object.h | 2 +- pack-bitmap-write.c | 274 ++++++- pack-bitmap.c | 359 ++++++++- pack-bitmap.h | 19 +- parse.c | 29 + parse.h | 1 + pseudo-merge.c | 756 +++++++++++++++++++ pseudo-merge.h | 216 ++++++ t/helper/test-bitmap.c | 34 +- t/perf/p5333-pseudo-merge-bitmaps.sh | 32 + t/t5333-pseudo-merge-bitmaps.sh | 393 ++++++++++ t/test-lib-functions.sh | 9 +- 24 files changed, 2590 insertions(+), 55 deletions(-) create mode 100644 Documentation/config/bitmap-pseudo-merge.txt create mode 100644 Documentation/gitpacking.txt create mode 100644 pseudo-merge.c create mode 100644 pseudo-merge.h create mode 100755 t/perf/p5333-pseudo-merge-bitmaps.sh create mode 100755 t/t5333-pseudo-merge-bitmaps.sh
Range-diff against v3:
-: ----------- > 1: 0f20c9becf4 Documentation/gitpacking.txt: initial commit
1: 528b591bd84 ! 2: 48afaa74928 Documentation/gitpacking.txt: describe pseudo-merge bitmaps
@@ Documentation/gitpacking.txt: There are many aspects of packing in Git that are
+== Pseudo-merge bitmaps
+
++NOTE: Pseudo-merge bitmaps are considered an experimental feature, so
++the configuration and many of the ideas are subject to change.
++
+=== Background
+
+Reachability bitmaps are most efficient when we have on-disk stored
2: 12f318b3d7e = 3: 44046f83c1a Documentation/technical: describe pseudo-merge bitmaps format
3: 40eb6137618 = 4: 211d6f14128 ewah: implement `ewah_bitmap_is_subset()`
4: 487fb7c6e9c = 5: 650cac2dcf9 pack-bitmap: move some initialization to `bitmap_writer_init()`
5: 827732acf99 = 6: 6647d8832ce pseudo-merge.ch: initial commit
6: 8608dd1860f = 7: e8ef1ef5ee4 pack-bitmap-write: support storing pseudo-merge commits
7: 99d2b6872ba = 8: fe458728c8a pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()`
8: e7209c60fa5 = 9: 6bf372f4020 pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public
9: 3070135eb4b ! 10: 6c77671ae9c config: introduce git_config_float()
@@ Metadata
Author: Taylor Blau <me@ttaylorr.com>
## Commit message ##
- config: introduce git_config_float()
+ config: introduce `git_config_double()`
- Future commits will want to parse a floating point value from
- configuration, but we have no way to parse such a value prior to this
- patch.
+ Future commits will want to parse a double-precision floating point
+ value from configuration, but we have no way to parse such a value prior
+ to this patch.
- The core of the routine is implemented in git_parse_float(). Unlike
+ The core of the routine is implemented in git_parse_double(). Unlike
git_parse_unsigned() and git_parse_signed(), however, the function
- implemented here only works on type "float", and not related types like
- "double", or "long double".
+ implemented here only works on type "double", and not related types like
+ "float", or "long double".
- This is because "double" and "long double" use different functions to
- convert from ASCII strings to floating point values (strtod() and
+ This is because "float" and "long double" use different functions to
+ convert from ASCII strings to floating point values (strtof() and
strtold(), respectively). Likewise, there is no pointer type that can
assign to any of these values (except for "void *"), so the only way to
define this trio of functions would be with a macro expansion that is
parameterized over the floating point type and conversion function.
That is all doable, but likely to be overkill given our current needs,
- which is only to parse floats.
+ which is only to parse double-precision floats.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
@@ config.c: ssize_t git_config_ssize_t(const char *name, const char *value,
return ret;
}
-+float git_config_float(const char *name, const char *value,
-+ const struct key_value_info *kvi)
++double git_config_double(const char *name, const char *value,
++ const struct key_value_info *kvi)
+{
-+ float ret;
-+ if (!git_parse_float(value, &ret))
++ double ret;
++ if (!git_parse_double(value, &ret))
+ die_bad_number(name, value, kvi);
+ return ret;
+}
@@ config.h: unsigned long git_config_ulong(const char *, const char *,
const struct key_value_info *);
+/**
-+ * Identical to `git_config_int`, but for floating point values.
++ * Identically to `git_config_double`, but for double-precision floating point
++ * values.
+ */
-+float git_config_float(const char *, const char *,
-+ const struct key_value_info *);
++double git_config_double(const char *, const char *,
++ const struct key_value_info *);
+
/**
* Same as `git_config_bool`, except that integers are returned as-is, and
@@ parse.c: int git_parse_ssize_t(const char *value, ssize_t *ret)
return 1;
}
-+int git_parse_float(const char *value, float *ret)
++int git_parse_double(const char *value, double *ret)
+{
+ char *end;
-+ float val;
++ double val;
+ uintmax_t factor;
+
+ if (!value || !*value) {
@@ parse.c: int git_parse_ssize_t(const char *value, ssize_t *ret)
+ }
+
+ errno = 0;
-+ val = strtof(value, &end);
++ val = strtod(value, &end);
+ if (errno == ERANGE)
+ return 0;
+ if (end == value) {
@@ parse.h: int git_parse_ssize_t(const char *, ssize_t *);
int git_parse_ulong(const char *, unsigned long *);
int git_parse_int(const char *value, int *ret);
int git_parse_int64(const char *value, int64_t *ret);
-+int git_parse_float(const char *value, float *ret);
++int git_parse_double(const char *value, double *ret);
/**
* Same as `git_config_bool`, except that it returns -1 on error rather
10: 3029473c094 ! 11: 180072ce848 pseudo-merge: implement support for selecting pseudo-merge commits
@@ Documentation/config/bitmap-pseudo-merge.txt (new)
@@
+NOTE: The configuration options in `bitmapPseudoMerge.*` are considered
+EXPERIMENTAL and may be subject to change or be removed entirely in the
-+future.
++future. For more information about the pseudo-merge bitmap feature, see
++the "Pseudo-merge bitmaps" section of linkgit:gitpacking[7].
+
+bitmapPseudoMerge.<name>.pattern::
+ Regular expression used to match reference names. Commits
@@ pseudo-merge.c
+#include "alloc.h"
+#include "progress.h"
+
-+#define DEFAULT_PSEUDO_MERGE_DECAY 1.0f
++#define DEFAULT_PSEUDO_MERGE_DECAY 1.0
+#define DEFAULT_PSEUDO_MERGE_MAX_MERGES 64
+#define DEFAULT_PSEUDO_MERGE_SAMPLE_RATE 1
+#define DEFAULT_PSEUDO_MERGE_THRESHOLD approxidate("1.week.ago")
+#define DEFAULT_PSEUDO_MERGE_STABLE_THRESHOLD approxidate("1.month.ago")
+#define DEFAULT_PSEUDO_MERGE_STABLE_SIZE 512
+
-+static float gitexp(float base, int exp)
++static double gitexp(double base, int exp)
+{
-+ float result = 1;
++ double result = 1;
+ while (1) {
+ if (exp % 2)
+ result *= base;
@@ pseudo-merge.c
+ const struct pseudo_merge_matches *matches,
+ uint32_t i)
+{
-+ float C = 0.0f;
++ double C = 0.0f;
+ uint32_t n;
+
+ /*
@@ pseudo-merge.c
+ * { 5012, 1772, 964, 626, 448, 341, 271, 221, 186, 158 }
+ */
+ for (n = 0; n < group->max_merges; n++)
-+ C += 1.0f / gitexp(n + 1, group->decay);
++ C += 1.0 / gitexp(n + 1, group->decay);
+ C = matches->unstable_nr / C;
+
+ return (uint32_t)((C / gitexp(i + 1, group->decay)) + 0.5);
@@ pseudo-merge.c
+
+ strbuf_release(&re);
+ } else if (!strcmp(key, "decay")) {
-+ group->decay = git_config_float(var, value, ctx->kvi);
++ group->decay = git_config_double(var, value, ctx->kvi);
+ if (group->decay < 0) {
+ warning(_("%s must be non-negative, using default"), var);
+ group->decay = DEFAULT_PSEUDO_MERGE_DECAY;
+ }
+ } else if (!strcmp(key, "samplerate")) {
-+ group->sample_rate = git_config_float(var, value, ctx->kvi);
++ group->sample_rate = git_config_double(var, value, ctx->kvi);
+ if (!(0 <= group->sample_rate && group->sample_rate <= 1)) {
+ warning(_("%s must be between 0 and 1, using default"), var);
+ group->sample_rate = DEFAULT_PSEUDO_MERGE_SAMPLE_RATE;
@@ pseudo-merge.c
+ struct commit *c = matches->unstable[j];
+ struct pseudo_merge_commit_idx *pmc;
+
-+ if (j % (uint32_t)(1.0f / group->sample_rate))
++ if (j % (uint32_t)(1.0 / group->sample_rate))
+ continue;
+
+ pmc = pseudo_merge_idx(writer->pseudo_merge_commits,
@@ pseudo-merge.h
+ * Pseudo-merge grouping parameters. See git-config(1) for
+ * more information.
+ */
-+ float decay;
++ double decay;
+ int max_merges;
-+ float sample_rate;
++ double sample_rate;
+ int stable_size;
+ timestamp_t threshold;
+ timestamp_t stable_threshold;
11: 311226f65c2 = 12: 90df19e43f5 pack-bitmap-write.c: write pseudo-merge table
12: 55dd7a8023e = 13: c653a10f8e4 pack-bitmap: extract `read_bitmap()` function
13: 3cc5434e44e = 14: 435ac048003 pseudo-merge: scaffolding for reads
14: 7664f5f9648 = 15: fa7a948964c pack-bitmap.c: read pseudo-merge extension
15: 8ba0a9c5402 ! 16: 3a72e66cb69 pseudo-merge: implement support for reading pseudo-merge commits
@@ pseudo-merge.c
#include "progress.h"
+#include "hex.h"
- #define DEFAULT_PSEUDO_MERGE_DECAY 1.0f
+ #define DEFAULT_PSEUDO_MERGE_DECAY 1.0
#define DEFAULT_PSEUDO_MERGE_MAX_MERGES 64
@@ pseudo-merge.c: void free_pseudo_merge_map(struct pseudo_merge_map *pm)
}
@@ pseudo-merge.c: void free_pseudo_merge_map(struct pseudo_merge_map *pm)
+ return error(_("extended pseudo-merge read out-of-bounds "
+ "(%"PRIuMAX" >= %"PRIuMAX")"),
+ (uintmax_t)at, (uintmax_t)pm->map_size);
++ if (at + 4 >= pm->map_size)
++ return error(_("extended pseudo-merge entry is too short "
++ "(%"PRIuMAX" >= %"PRIuMAX")"),
++ (uintmax_t)(at + 4), (uintmax_t)pm->map_size);
+
+ ext->nr = get_be32(pm->map + at);
+ ext->ptr = pm->map + at + sizeof(uint32_t);
16: 2c02f303b6f = 17: 42a836fda8a ewah: implement `ewah_bitmap_popcount()`
17: 82cce72bf55 = 18: 06ba1a5bbfd pack-bitmap: implement test helpers for pseudo-merge
18: 890f6c4b9de ! 19: 936f6d1b7e3 t/test-lib-functions.sh: support `--date` in `test_commit_bulk()`
@@ Metadata
Author: Taylor Blau <me@ttaylorr.com>
## Commit message ##
- t/test-lib-functions.sh: support `--date` in `test_commit_bulk()`
+ t/test-lib-functions.sh: support `--notick` in `test_commit_bulk()`
One of the tests we'll want to add for pseudo-merge bitmaps needs to be
able to generate a large number of commits at a specific date.
- Support the `--date` option (with identical semantics to the `--date`
- option for `test_commit()`) within `test_commit_bulk` as a prerequisite
- for that.
+ Support the `--notick` option (with identical semantics to the
+ `--notick` option for `test_commit()`) within `test_commit_bulk` as a
+ prerequisite for that. Callers can then set the various _DATE variables
+ themselves.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
@@ t/test-lib-functions.sh: test_commit_bulk () {
filename="${1#--*=}-%s.t"
contents="${1#--*=} %s"
;;
-+ --date)
++ --notick)
+ notick=yes
-+ GIT_COMMITTER_DATE="$2"
-+ GIT_AUTHOR_DATE="$2"
-+ shift
+ ;;
-*)
BUG "invalid test_commit_bulk option: $1"
19: 41691824f78 ! 20: cad38608aae pack-bitmap.c: use pseudo-merges during traversal
@@ t/t5333-pseudo-merge-bitmaps.sh (new)
+ new="1672549200" && # 2023-01-01
+ old="1641013200" && # 2022-01-01
+
-+ test_commit_bulk --message="new" --date "$new +0000" 128 &&
-+ test_commit_bulk --message="old" --date "$old +0000" 128 &&
-+ test_tick &&
++ GIT_COMMITTER_DATE="$new +0000" &&
++ export GIT_COMMITTER_DATE &&
++ test_commit_bulk --message="new" --notick 128 &&
++
++ GIT_COMMITTER_DATE="$old +0000" &&
++ export GIT_COMMITTER_DATE &&
++ test_commit_bulk --message="old" --notick 128 &&
+
+ tag_everything &&
+
@@ t/t5333-pseudo-merge-bitmaps.sh (new)
+ mid="1654059600" && # 2022-06-01
+ old="1641013200" && # 2022-01-01
+
-+ test_commit_bulk --message="mid" --date "$mid +0000" 128 &&
-+ test_tick &&
++ GIT_COMMITTER_DATE="$mid +0000" &&
++ export GIT_COMMITTER_DATE &&
++ test_commit_bulk --message="mid" --notick 128 &&
+
+ git for-each-ref --format="delete %(refname)" refs/tags >in &&
+ git update-ref --stdin <in &&
20: a34a60c3ef8 = 21: 9240b06a7d8 pack-bitmap: extra trace2 information
21: da2fb5b4b48 = 22: 625596a1432 ewah: `bitmap_equals_ewah()`
22: ff21247281f ! 23: fdd506d4544 pseudo-merge: implement support for finding existing merges
@@ t/t5333-pseudo-merge-bitmaps.sh: test_expect_success 'pseudo-merge overlap stale
+ stable="1641013200" && # 2022-01-01
+ unstable="1672549200" && # 2023-01-01
+
-+ for date in $stable $unstable
-+ do
-+ test_commit_bulk --date "$date +0000" 128 &&
-+ test_tick || return 1
-+ done &&
++ GIT_COMMITTER_DATE="$stable +0000" &&
++ export GIT_COMMITTER_DATE &&
++ test_commit_bulk --notick 128 &&
++ GIT_COMMITTER_DATE="$unstable +0000" &&
++ export GIT_COMMITTER_DATE &&
++ test_commit_bulk --notick 128 &&
+
+ tag_everything &&
+
23: 6a6d88fa512 ! 24: cf0316ad0e9 t/perf: implement performace tests for pseudo-merge bitmaps
@@ Metadata
Author: Taylor Blau <me@ttaylorr.com>
## Commit message ##
- t/perf: implement performace tests for pseudo-merge bitmaps
+ t/perf: implement performance tests for pseudo-merge bitmaps
Implement a straightforward performance test demonstrating the benefit
of pseudo-merge bitmaps by measuring how long it takes to count
@@ Commit message
Test this tree
-----------------------------------------------------------------------------------
- 5333.2: git rev-list --count --all --objects (no bitmaps) 3.46(3.37+0.09)
- 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.13(0.11+0.01)
+ 5333.2: git rev-list --count --all --objects (no bitmaps) 3.54(3.45+0.08)
+ 5333.3: git rev-list --count --all --objects (no pseudo-merges) 0.43(0.40+0.03)
5333.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01)
+ On a private repository which is much larger, and has many spikey parts
+ of history that aren't merged into the 'master' branch, the results are
+ as follows:
+
+ Test this tree
+ ---------------------------------------------------------------------------------------
+ 5333.1: git rev-list --count --all --objects (no bitmaps) 122.29(121.31+0.97)
+ 5333.2: git rev-list --count --all --objects (no pseudo-merges) 21.88(21.30+0.58)
+ 5333.3: git rev-list --count --all --objects (with pseudo-merges) 5.05(4.77+0.28)
+
Signed-off-by: Taylor Blau <me@ttaylorr.com>
## t/perf/p5333-pseudo-merge-bitmaps.sh (new) ##
@@ t/perf/p5333-pseudo-merge-bitmaps.sh (new)
+'
+
+test_perf 'git rev-list --count --all --objects (no pseudo-merges)' '
-+ GIT_TEST_USE_PSEDUO_MERGES=0 \
++ GIT_TEST_USE_PSEUDO_MERGES=0 \
+ git rev-list --objects --all --use-bitmap-index
+'
+
+test_perf 'git rev-list --count --all --objects (with pseudo-merges)' '
-+ GIT_TEST_USE_PSEDUO_MERGES=1 \
++ GIT_TEST_USE_PSEUDO_MERGES=1 \
+ git rev-list --objects --all --use-bitmap-index
+'
+base-commit: bf65967764f34adc2ca00d4c8195840ad3e4e127
-- 2.45.1.175.gcf0316ad0e9