pack-bitmap: pseudo-merge reachability bitmaps
Subsystems (2)
PATCH v3 26/30 pack-bitmap.c: use pseudo-merges during traversal
In reply to Taylor BlauNow that all of the groundwork has been laid to support reading and using pseudo-merges, make use of that work in this commit by teaching the pack-bitmap machinery to use pseudo-merge(s) when available during traversal.
The basic operation is as follows:
- When enumerating objects on either side of a reachability query, first see if any subset of the roots satisfies some pseudo-merge bitmap. If it does, apply that pseudo-merge bitmap.
- If any pseudo-merge bitmap(s) were applied in the previous step, OR them into the result[^1]. Then repeat the process over all pseudo-merge bitmaps (we'll refer to this as "cascading" pseudo-merges). Once this is done, OR in the resulting bitmap.
- If there is no fill-in traversal to be done, return the bitmap for that side of the reachability query. If there is fill-in traversal, then for each commit we encounter via show_commit(), check to see if any unsatisfied pseudo-merges containing that commit as one of its parents has been made satisfied by the presence of that commit.
If so, OR in the object set from that pseudo-merge bitmap, and then cascade. If not, continue traversal.
A similar implementation is present in the boundary-based bitmap traversal routines.
[^1]: Importantly, we cannot OR in the entire set of roots along with
the objects reachable from whatever pseudo-merge bitmaps were satisfied. This may leave some dangling bits corresponding to any unsatisfied root(s) getting OR'd into the resulting bitmap, tricking other parts of the traversal into thinking we already have a reachability closure over those commit(s) when we do not.
--- pack-bitmap.c | 112 ++++++++++- t/t5333-pseudo-merge-bitmaps.sh | 323 ++++++++++++++++++++++++++++++++ 2 files changed, 434 insertions(+), 1 deletion(-) create mode 100755 t/t5333-pseudo-merge-bitmaps.sh
pack-bitmap.c +111 -1
@@ -114,6 +114,9 @@ struct bitmap_index {unsigned int version; }; +static int pseudo_merges_satisfied_nr; +static int pseudo_merges_cascades_nr; +static struct ewah_bitmap *lookup_stored_bitmap (struct stored_bitmap *st) {struct ewah_bitmap *parent;
@@ -1006,6 +1009,22 @@ static void show_commit(struct commit *commit UNUSED, { } +static unsigned apply_pseudo_merges_for_commit_1 (struct bitmap_index *bitmap_git, +struct bitmap *result, +struct commit *commit, +uint32_t commit_pos) +{ +int ret; + + ret =apply_pseudo_merges_for_commit (&bitmap_git->pseudo_merges, + result, commit, commit_pos); + +if (ret) + pseudo_merges_satisfied_nr += ret; + +return ret; +} + static int add_to_include_set(struct bitmap_index *bitmap_git, struct include_data *data, struct commit *commit,
@@ -1026,6 +1045,10 @@ static int add_to_include_set(struct bitmap_index *bitmap_git, }bitmap_set (data->base, bitmap_pos); +if (apply_pseudo_merges_for_commit_1 (bitmap_git, data->base, commit, + bitmap_pos)) +return 0 ; +return 1 ; }
@@ -1151,6 +1174,20 @@ static void show_boundary_object(struct object *object UNUSED,BUG ("should not be called" ); } +static unsigned cascade_pseudo_merges_1 (struct bitmap_index *bitmap_git, +struct bitmap *result, +struct bitmap *roots) +{ +int ret =cascade_pseudo_merges (&bitmap_git->pseudo_merges, + result, roots); +if (ret) { + pseudo_merges_cascades_nr++; + pseudo_merges_satisfied_nr += ret; + } + +return ret; +} +static struct bitmap *find_boundary_objects (struct bitmap_index *bitmap_git,struct rev_info *revs,struct object_list *roots)
@@ -1160,6 +1197,7 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,unsigned int i;unsigned int tmp_blobs, tmp_trees, tmp_tags;int any_missing =0 ; +int existing_bitmaps =0 ; cb.bitmap_git = bitmap_git; cb.base =bitmap_new ();
@@ -1167,6 +1205,25 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, revs->ignore_missing_links =1 ; +if (bitmap_git->pseudo_merges.nr) { +struct bitmap *roots_bitmap =bitmap_new (); +struct object_list *objects =NULL ; + +for (objects = roots; objects; objects = objects->next) { +struct object *object = objects->item; +int pos; + + pos =bitmap_position (bitmap_git, &object->oid); +if (pos <0 ) +continue ; + +bitmap_set (roots_bitmap, pos); + } + +if (!cascade_pseudo_merges_1 (bitmap_git, cb.base, roots_bitmap)) +bitmap_free (roots_bitmap); + } +/* * OR in any existing reachability bitmaps among `roots` into * `cb.base`.
@@ -1178,8 +1235,10 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,continue ;if (add_commit_to_bitmap (bitmap_git, &cb.base, - (struct commit *)object)) + (struct commit *)object)) { + existing_bitmaps =1 ;continue ; + } any_missing =1 ; }
@@ -1187,6 +1246,9 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,if (!any_missing) goto cleanup; +if (existing_bitmaps) +cascade_pseudo_merges_1 (bitmap_git, cb.base,NULL ); + tmp_blobs = revs->blob_objects; tmp_trees = revs->tree_objects; tmp_tags = revs->blob_objects;
@@ -1242,6 +1304,13 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,return cb.base; } +static void unsatisfy_all_pseudo_merges (struct bitmap_index *bitmap_git) +{ +uint32_t i; +for (i =0 ; i < bitmap_git->pseudo_merges.nr; i++) + bitmap_git->pseudo_merges.v[i].satisfied =0 ; +} + static struct bitmap *find_objects(struct bitmap_index *bitmap_git, struct rev_info *revs, struct object_list *roots,
@@ -1249,9 +1318,32 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, {struct bitmap *base =NULL ;int needs_walk =0 ; +unsigned existing_bitmaps =0 ;struct object_list *not_mapped =NULL ; +unsatisfy_all_pseudo_merges (bitmap_git); + +if (bitmap_git->pseudo_merges.nr) { +struct bitmap *roots_bitmap =bitmap_new (); +struct object_list *objects =NULL ; + +for (objects = roots; objects; objects = objects->next) { +struct object *object = objects->item; +int pos; + + pos =bitmap_position (bitmap_git, &object->oid); +if (pos <0 ) +continue ; + +bitmap_set (roots_bitmap, pos); + } + + base =bitmap_new (); +if (!cascade_pseudo_merges_1 (bitmap_git, base, roots_bitmap)) +bitmap_free (roots_bitmap); + } +/* * Go through all the roots for the walk. The ones that have bitmaps * on the bitmap index will be `or`ed together to form an initial
@@ -1262,11 +1354,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,*/ while (roots) {struct object *object = roots->item; + roots = roots->next; +if (base) { +int pos =bitmap_position (bitmap_git, &object->oid); +if (pos >0 &&bitmap_get (base, pos)) { + object->flags |=SEEN ; +continue ; + } + } +if (object->type ==OBJ_COMMIT &&add_commit_to_bitmap (bitmap_git, &base, (struct commit *)object)) { object->flags |=SEEN ; + existing_bitmaps =1 ;continue ; }
@@ -1282,6 +1384,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, roots = not_mapped; +if (existing_bitmaps) +cascade_pseudo_merges_1 (bitmap_git, base,NULL ); +/* * Let's iterate through all the roots that don't have bitmaps to * check if we can determine them to be reachable from the existing
@@ -1866,6 +1971,11 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,object_list_free (&wants);object_list_free (&haves); +trace2_data_intmax ("bitmap" , the_repository,"pseudo_merges_satisfied" , + pseudo_merges_satisfied_nr); +trace2_data_intmax ("bitmap" , the_repository,"pseudo_merges_cascades" , + pseudo_merges_cascades_nr); +return bitmap_git; cleanup:
t/t5333-pseudo-merge-bitmaps.sh new file +323 -0
323 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gbea44add9db
Re: [PATCH v3 26/30] pack-bitmap.c: use pseudo-merges during traversal
Quoted 11 lines · Taylor Blau
The basic operation is as follows:
- When enumerating objects on either side of a reachability query, first see if any subset of the roots satisfies some pseudo-merge bitmap. If it does, apply that pseudo-merge bitmap.
- If any pseudo-merge bitmap(s) were applied in the previous step, OR them into the result[^1]. Then repeat the process over all pseudo-merge bitmaps (we'll refer to this as "cascading" pseudo-merges). Once this is done, OR in the resulting bitmap.
Quoted 8 lines
- If there is no fill-in traversal to be done, return the bitmap for that side of the reachability query. If there is fill-in traversal, then for each commit we encounter via
show_commit(), check to see if any unsatisfied pseudo-merges containing that commit as one of its parents has been made satisfied by the presence of that commit.If so, OR in the object set from that pseudo-merge bitmap, and then cascade. If not, continue traversal.
Ah, OK. This is the high-level overview I was looking for in the earlier commit. ;) I think it is fine here. I just hadn't gotten to it yet (and I think it is much better stated than what I wrote in my earlier response).
Quoted 6 lines
[^1]: Importantly, we cannot OR in the entire set of roots along with
the objects reachable from whatever pseudo-merge bitmaps were satisfied. This may leave some dangling bits corresponding to any unsatisfied root(s) getting OR'd into the resulting bitmap, tricking other parts of the traversal into thinking we already have a reachability closure over those commit(s) when we do not.
I think I know how you made this realization. :)
The code itself looks as I'd expect, and the entry points are nice and clean.
-Peff
Re: [PATCH v3 26/30] pack-bitmap.c: use pseudo-merges during traversal
Quoted 19 lines · Jeff King
Quoted 17 lines · Taylor Blau
The basic operation is as follows:
- When enumerating objects on either side of a reachability query, first see if any subset of the roots satisfies some pseudo-merge bitmap. If it does, apply that pseudo-merge bitmap.
- If any pseudo-merge bitmap(s) were applied in the previous step, OR them into the result[^1]. Then repeat the process over all pseudo-merge bitmaps (we'll refer to this as "cascading" pseudo-merges). Once this is done, OR in the resulting bitmap.
- If there is no fill-in traversal to be done, return the bitmap for that side of the reachability query. If there is fill-in traversal, then for each commit we encounter via
show_commit(), check to see if any unsatisfied pseudo-merges containing that commit as one of its parents has been made satisfied by the presence of that commit.
Quoted 7 lines
Quoted 2 lines
If so, OR in the object set from that pseudo-merge bitmap, and then cascade. If not, continue traversal.
Ah, OK. This is the high-level overview I was looking for in the earlier commit. ;) I think it is fine here. I just hadn't gotten to it yet (and I think it is much better stated than what I wrote in my earlier response).
Good, thanks.
Quoted 8 lines
Quoted 6 lines
[^1]: Importantly, we cannot OR in the entire set of roots along with
the objects reachable from whatever pseudo-merge bitmaps were satisfied. This may leave some dangling bits corresponding to any unsatisfied root(s) getting OR'd into the resulting bitmap, tricking other parts of the traversal into thinking we already have a reachability closure over those commit(s) when we do not.I think I know how you made this realization. :)
;-).
Thanks,
Taylor
PATCH v3 27/30 pack-bitmap: extra trace2 information
In reply to Taylor BlauAdd some extra trace2 lines to capture the number of bitmap lookups that are hits versus misses, as well as the number of reachability roots that have bitmap coverage (versus those that do not).
--- pack-bitmap.c | 26 +++++++++++++++++++++++++- 1 file changed, 25 insertions(+), 1 deletion(-)
pack-bitmap.c +25 -1
@@ -116,6 +116,10 @@ struct bitmap_index {static int pseudo_merges_satisfied_nr;static int pseudo_merges_cascades_nr; +static int existing_bitmaps_hits_nr; +static int existing_bitmaps_misses_nr; +static int roots_with_bitmaps_nr; +static int roots_without_bitmaps_nr;static struct ewah_bitmap *lookup_stored_bitmap (struct stored_bitmap *st) {
@@ -1040,10 +1044,14 @@ static int add_to_include_set(struct bitmap_index *bitmap_git, partial =bitmap_for_commit (bitmap_git, commit);if (partial) { + existing_bitmaps_hits_nr++; +bitmap_or_ewah (data->base, partial);return 0 ; } + existing_bitmaps_misses_nr++; +bitmap_set (data->base, bitmap_pos);if (apply_pseudo_merges_for_commit_1 (bitmap_git, data->base, commit, bitmap_pos))
@@ -1099,8 +1107,12 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git, {struct ewah_bitmap *or_with =bitmap_for_commit (bitmap_git, commit); -if (!or_with) +if (!or_with) { + existing_bitmaps_misses_nr++;return 0 ; + } + + existing_bitmaps_hits_nr++;if (!*base) *base =ewah_to_bitmap (or_with);
@@ -1407,8 +1419,12 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, object->flags &= ~UNINTERESTING ;add_pending_object (revs, object,"" ); needs_walk =1 ; + + roots_without_bitmaps_nr++; }else { object->flags |=SEEN ; + + roots_with_bitmaps_nr++; } }
@@ -1975,6 +1991,14 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, pseudo_merges_satisfied_nr);trace2_data_intmax ("bitmap" , the_repository,"pseudo_merges_cascades" , pseudo_merges_cascades_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/hits" , + existing_bitmaps_hits_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/misses" , + existing_bitmaps_misses_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/roots_with_bitmap" , + roots_with_bitmaps_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/roots_without_bitmap" , + roots_without_bitmaps_nr);return bitmap_git;
Signature · 1 line
2.45.1.175.gbea44add9db
PATCH v3 28/30 ewah: `bitmap_equals_ewah()`
In reply to Taylor BlauPrepare to reuse existing pseudo-merge bitmaps by implementing a bitmap_equals_ewah() helper.
This helper will be used to see if a raw bitmap (containing the set of parents for some pseudo-merge) is equal to any existing pseudo-merge's commits bitmap (which are stored as EWAH-compressed bitmaps on disk).
--- ewah/bitmap.c | 19 +++++++++++++++++++ ewah/ewok.h | 1 + 2 files changed, 20 insertions(+)
ewah/bitmap.c +19 -0
@@ -261,6 +261,25 @@ int bitmap_equals(struct bitmap *self, struct bitmap *other)return 1 ; } +int bitmap_equals_ewah (struct bitmap *self,struct ewah_bitmap *other) +{ +struct ewah_iterator it; +eword_t word; +size_t i =0 ; + +ewah_iterator_init (&it, other); + +while (ewah_iterator_next (&word, &it)) +if (word != (i < self->word_alloc ? self->words[i++] :0 )) +return 0 ; + +for (; i < self->word_alloc; i++) +if (self->words[i]) +return 0 ; + +return 1 ; +} +int bitmap_is_subset (struct bitmap *self,struct bitmap *other) {size_t common_size, i;
ewah/ewok.h +1 -0
@@ -179,6 +179,7 @@ void bitmap_unset(struct bitmap *self, size_t pos);int bitmap_get (struct bitmap *self,size_t pos);void bitmap_free (struct bitmap *self);int bitmap_equals (struct bitmap *self,struct bitmap *other); +int bitmap_equals_ewah (struct bitmap *self,struct ewah_bitmap *other);/* * Both `bitmap_is_subset()` and `ewah_bitmap_is_subset()` return 1 if the set
Signature · 1 line
2.45.1.175.gbea44add9db
PATCH v3 29/30 pseudo-merge: implement support for finding existing merges
In reply to Taylor BlauThis patch implements support for reusing existing pseudo-merge commits when writing bitmaps when there is an existing pseudo-merge bitmap which has exactly the same set of parents as one that we are about to write.
Note that unstable pseudo-merges are likely to change between consecutive repacks, and so are generally poor candidates for reuse. However, stable pseudo-merges (see the configuration option 'bitmapPseudoMerge.<name>.stableThreshold') are by definition unlikely to change between runs (as they represent long-running branches).
Because there is no index from a *set* of pseudo-merge parents to a matching pseudo-merge bitmap, we have to construct the bitmap corresponding to the set of parents for each pending pseudo-merge commit and see if a matching bitmap exists.
This is technically quadratic in the number of pseudo-merges, but is OK in practice for a couple of reasons:
- non-matching pseudo-merge bitmaps are rejected quickly as soon as they differ in a single bit
- already-matched pseudo-merge bitmaps are discarded from subsequent rounds of search
- the number of pseudo-merges is generally small, even for large repositories
In order to do this, implement (a) a function that finds a matching pseudo-merge given some uncompressed bitset describing its parents, (b) a function that computes the bitset of parents for a given pseudo-merge commit, and (c) call that function before computing the set of reachable objects for some pending pseudo-merge.
--- pack-bitmap-write.c | 15 ++++++-- pack-bitmap.c | 32 +++++++++++++++++ pack-bitmap.h | 2 ++ pseudo-merge.c | 55 ++++++++++++++++++++++++++++ pseudo-merge.h | 7 ++++ t/t5333-pseudo-merge-bitmaps.sh | 64 +++++++++++++++++++++++++++++++++ 6 files changed, 173 insertions(+), 2 deletions(-)
pack-bitmap-write.c +13 -2
@@ -19,6 +19,10 @@#include "tree-walk.h" #include "pseudo-merge.h" #include "oid-array.h" +#include "config.h" +#include "alloc.h" +#include "refs.h" +#include "strmap.h" struct bitmapped_commit {struct commit *commit;
@@ -465,6 +469,7 @@ static int fill_bitmap_tree(struct bitmap_writer *writer, }static int reused_bitmaps_nr; +static int reused_pseudo_merge_bitmaps_nr; static int fill_bitmap_commit(struct bitmap_writer *writer, struct bb_commit *ent,
@@ -490,7 +495,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,struct bitmap *remapped =bitmap_new ();if (commit->object.flags &BITMAP_PSEUDO_MERGE ) - old =NULL ; + old =pseudo_merge_bitmap_for_commit (old_bitmap, c);else old =bitmap_for_commit (old_bitmap, c);/*
@@ -501,7 +506,10 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,if (old && !rebuild_bitmap (mapping, old, remapped)) {bitmap_or (ent->bitmap, remapped);bitmap_free (remapped); - reused_bitmaps_nr++; +if (commit->object.flags &BITMAP_PSEUDO_MERGE ) + reused_pseudo_merge_bitmaps_nr++; +else + reused_bitmaps_nr++;continue ; }bitmap_free (remapped);
@@ -631,6 +639,9 @@ int bitmap_writer_build(struct bitmap_writer *writer, the_repository);trace2_data_intmax ("pack-bitmap-write" , the_repository,"building_bitmaps_reused" , reused_bitmaps_nr); +trace2_data_intmax ("pack-bitmap-write" , the_repository, +"building_bitmaps_pseudo_merge_reused" , + reused_pseudo_merge_bitmaps_nr);stop_progress (&writer->progress);
pack-bitmap.c +32 -0
@@ -1316,6 +1316,37 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,return cb.base; } +struct ewah_bitmap *pseudo_merge_bitmap_for_commit (struct bitmap_index *bitmap_git, +struct commit *commit) +{ +struct commit_list *p; +struct bitmap *parents; +struct pseudo_merge *match =NULL ; + +if (!bitmap_git->pseudo_merges.nr) +return NULL ; + + parents =bitmap_new (); + +for (p = commit->parents; p; p = p->next) { +int pos =bitmap_position (bitmap_git, &p->item->object.oid); +if (pos <0 || pos >=bitmap_num_objects (bitmap_git)) + goto done; + +bitmap_set (parents, pos); + } + + match =pseudo_merge_for_parents (&bitmap_git->pseudo_merges, + parents); + +done: +bitmap_free (parents); +if (match) +return pseudo_merge_bitmap (&bitmap_git->pseudo_merges, match); + +return NULL ; +} +static void unsatisfy_all_pseudo_merges (struct bitmap_index *bitmap_git) {uint32_t i;
@@ -2809,6 +2840,7 @@ void free_bitmap_index(struct bitmap_index *b)*/ close_midx_revindex (b->midx); } +free_pseudo_merge_map (&b->pseudo_merges);free (b); }
pack-bitmap.h +2 -0
@@ -142,6 +142,8 @@ int rebuild_bitmap(const uint32_t *reposition, struct bitmap *dest);struct ewah_bitmap *bitmap_for_commit (struct bitmap_index *bitmap_git,struct commit *commit); +struct ewah_bitmap *pseudo_merge_bitmap_for_commit (struct bitmap_index *bitmap_git, +struct commit *commit);void bitmap_writer_select_commits (struct bitmap_writer *writer,struct commit **indexed_commits,unsigned int indexed_commits_nr);
pseudo-merge.c +55 -0
58 lines not on this page · raw message
pseudo-merge.h +7 -0
@@ -206,4 +206,11 @@ int cascade_pseudo_merges(const struct pseudo_merge_map *pm,struct bitmap *result, struct bitmap *roots); +/* +* Returns a pseudo-merge which contains the exact set of commits +* listed in the "parents" bitamp, or NULL if none could be found. +*/ +struct pseudo_merge *pseudo_merge_for_parents (const struct pseudo_merge_map *pm, +struct bitmap *parents); +#endif
t/t5333-pseudo-merge-bitmaps.sh +64 -0
74 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gbea44add9db
PATCH v3 30/30 t/perf: implement performace tests for pseudo-merge bitmaps
In reply to Taylor BlauImplement a straightforward performance test demonstrating the benefit of pseudo-merge bitmaps by measuring how long it takes to count reachable objects in a few different scenarios:
- without bitmaps, to demonstrate a reasonable baseline
- with bitmaps, but without pseudo-merges
- with bitmaps and pseudo-merges
Results from running this test on git.git are as follows:
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.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01)--- t/perf/p5333-pseudo-merge-bitmaps.sh | 32 ++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100755 t/perf/p5333-pseudo-merge-bitmaps.sh
t/perf/p5333-pseudo-merge-bitmaps.sh new file +32 -0
@@ -0,0 +1,32 @@ +#!/bin/sh + +test_description='pseudo-merge bitmaps' +. ./perf-lib.sh + +test_perf_large_repo + +test_expect_success 'setup' ' + git \ + -c bitmapPseudoMerge.all.pattern="refs/" \ + -c bitmapPseudoMerge.all.threshold=now \ + -c bitmapPseudoMerge.all.stableThreshold=never \ + -c bitmapPseudoMerge.all.maxMerges=64 \ + -c pack.writeBitmapLookupTable=true \ + repack -adb +' + +test_perf 'git rev-list --count --all --objects (no bitmaps)' ' + git rev-list --objects --all +' + +test_perf 'git rev-list --count --all --objects (no pseudo-merges)' ' + GIT_TEST_USE_PSEDUO_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 rev-list --objects --all --use-bitmap-index +' + +test_done
Signature · 1 line
2.45.1.175.gbea44add9db
Re: [PATCH v3 30/30] t/perf: implement performace tests for pseudo-merge bitmaps
Quoted 8 lines · Taylor Blau
Implement a straightforward performance test demonstrating the benefit of pseudo-merge bitmaps by measuring how long it takes to count reachable objects in a few different scenarios:
- without bitmaps, to demonstrate a reasonable baseline
- with bitmaps, but without pseudo-merges
- with bitmaps and pseudo-merges
Quoted 7 lines
Results from running this test on git.git are as follows:
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.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01)
That's not a very exciting result. I have a feeling that your git.git is not a very interesting test case. We'd want a lot of refs, and ones that are old and have bushy history that is not included in the more recent branches. So something like a bunch of old unmerged pull request heads, for example. ;) Do you have more interesting numbers for something like that?
-Peff
Re: [PATCH v3 30/30] t/perf: implement performace tests for pseudo-merge bitmaps
Quoted 12 lines · Jeff King
Quoted 10 lines · Taylor Blau
Implement a straightforward performance test demonstrating the benefit of pseudo-merge bitmaps by measuring how long it takes to count reachable objects in a few different scenarios:
- without bitmaps, to demonstrate a reasonable baseline
- with bitmaps, but without pseudo-merges
- with bitmaps and pseudo-mergesResults from running this test on git.git are as follows:
Quoted 7 lines
Quoted 5 lines
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.4: git rev-list --count --all --objects (with pseudo-merges) 0.12(0.11+0.01)That's not a very exciting result.
I suspect some of it might have to do with:
--- 8< ---
t/perf/p5333-pseudo-merge-bitmaps.sh +2 -3
@@ -20,12 +20,12 @@ test_perf 'git rev-list --count --all --objects (no bitmaps)' ' ' 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 ' --- > 8---
Sure enough, that shows us a little gap between the "no pseudo-merges" and "with pseudo-merges" case:
``` Test this tree ----------------------------------------------------------------------------------- 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) ```
Quoted 5 lines
I have a feeling that your git.git is not a very interesting test case. We'd want a lot of refs, and ones that are old and have bushy history that is not included in the more recent branches. So something like a bunch of old unmerged pull request heads, for example. ;) Do you have more interesting numbers for something like that?
Indeed, here's one for a private repository which meets that criteria:
``` 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) ```
Thanks,
Taylor
Re: [PATCH v3 30/30] t/perf: implement performace tests for pseudo-merge bitmaps
t/perf/p5333-pseudo-merge-bitmaps.sh test_perf 'git rev-list --count --all --objects (no bitmaps)' ' · line 23
Quoted 2 lines · Taylor Blau
t/perf/p5333-pseudo-merge-bitmaps.sh +1
-1- GIT_TEST_USE_PSEDUO_MERGES=0 \ + GIT_TEST_USE_PSEUDO_MERGES=0 \
Whoops.
Quoted 10 lines
Sure enough, that shows us a little gap between the "no pseudo-merges" and "with pseudo-merges" case:
``` Test this tree ----------------------------------------------------------------------------------- 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) ```
OK, that seems more like it. 300ms is nice, but there's just not that much improvement to make here.
This one is much more exciting:
Quoted 7 lines
``` 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) ```
Very nice improvement.
I wonder what we spend the final 5s on. Maybe just book-keeping to assemble all the tips (and maybe even parse tip commits? I can't remember if we ever optimized that out). Anyway, that's all out of scope for your series. Getting rid of the expensive traversal would let us focus on those final bits. ;)
-Peff
Quoted 1 line · Taylor Blau
Here is another reroll my topic to introduce pseudo-merge bitmaps.
OK, I got through the whole thing. I left a few small comments, but mostly just observations. Overall, the shape of it looks pretty good. The much bigger question to me is: does it work?
The perf results you showed at the end are underwhelming, but I think that's mostly because it's not an interesting repository. I think it would be nice to see at least some point-in-time benchmarks on a single repository.
But much more interesting to me is how it performs in the real world in aggregate, over time:
- how often / how much do pseudo-merges speed up queries in the real world. Clones/fetches, but also reachability queries. Could connectivity checks use bitmaps with this?
- how often do pseudo-merge groups get invalidated by refs changing (and thus we lose the speedups from above)?
- what's the cost like to generate them initially?
- what's the cost like for subsequent repacks? Does the selection / grouping algorithm do a good job of keeping the older, larger groups stable (so that we can reuse them verbatim)?
I know you don't have those answers yet, and I know there's some chicken-and-egg with getting this integrated so that you can start to explore that. So I mostly reviewed this with an eye towards:
- does the idea make sense (I think it does, but I'm kind of biased)
- are the patches going to hurt anybody who isn't using the new feature (I think the answer is no)
- does the on-disk representation seem right, since that is hard to change later (I didn't see any issues)
- does the implementation look clean and plausibly correct (yes, but what I'm getting at is that I didn't pore over all of the new code with a microscope. Mostly I think the proof is in the pudding that it provides the same correct answers more quickly).
So to my eyes it looks good to move forward and let people start playing with it. The big "experimental" warning in the config is good. Maybe we'd want want in gitpacking(7), too?
I did wonder briefly what the backup plan is if there are problems with the on-disk format (or worst case, if it turns out to be a dead end). We've allocated a flag bit which I think we'd need to respect forever (though as an optional extension, it's OK to understand and ignore it). If we needed a "pseudo-merge bitmaps v2", how would that work? I think we'd have to allocate another bit in the flags field.
I wonder if the start of the pseudo-merge section should have a 4-byte version/flags field itself? I don't think that's something we've done before, and maybe it's overkill. I dunno. It's just a lot easier to do now than later.
-Peff
Quoted 4 lines · Jeff King
I wonder if the start of the pseudo-merge section should have a 4-byte version/flags field itself? I don't think that's something we've done before, and maybe it's overkill. I dunno. It's just a lot easier to do now than later.
I think the tricky thing here would be that the extension itself is a variable size, so every version would have to put the "extension size" field in the same place.
Otherwise, an older Git client which doesn't understand a future version of the pseudo-merge extension wouldn't know how large the extension is, and wouldn't be able to adjust the index_end field appropriately to skip over it.
Of course, we could make it a convention that says "all versions have to place the extension size field at the same relative offset", but it feels weird to read some of the extension while not understanding the whole thing.
I'm definitely not saying that I think the specification ought to be set in stone forever, but I think any changes would want to be behind a new bitmap extension, not a version within the same extension.
Thanks,
Taylor
Quoted 15 lines · Taylor Blau
Quoted 4 lines · Jeff King
I wonder if the start of the pseudo-merge section should have a 4-byte version/flags field itself? I don't think that's something we've done before, and maybe it's overkill. I dunno. It's just a lot easier to do now than later.
I think the tricky thing here would be that the extension itself is a variable size, so every version would have to put the "extension size" field in the same place.
Otherwise, an older Git client which doesn't understand a future version of the pseudo-merge extension wouldn't know how large the extension is, and wouldn't be able to adjust the
index_endfield appropriately to skip over it.
Quoted 4 lines
Of course, we could make it a convention that says "all versions have to place the extension size field at the same relative offset", but it feels weird to read some of the extension while not understanding the whole thing.
Ah, yeah, I didn't think of that. That definitely complicates things.
It certainly would be possible to have a version+size header at the start. Which is...basically reinventing the chunk format. Let's not worry about it for now, and as a long-term thing we might consider moving the bitmap format over to the chunk style.
-Peff
Quoted 7 lines · Jeff King
Quoted 1 line · Taylor Blau
Here is another reroll my topic to introduce pseudo-merge bitmaps.
OK, I got through the whole thing. I left a few small comments, but mostly just observations. Overall, the shape of it looks pretty good. The much bigger question to me is: does it work?
Thanks for working through this series, I appreciate you taking a close look, especially since it's on the longer end.
Quoted 4 lines
The perf results you showed at the end are underwhelming, but I think that's mostly because it's not an interesting repository. I think it would be nice to see at least some point-in-time benchmarks on a single repository.
I'd say it's mostly because I misspelt "pseudo" as "psuedo", but either way ;-).
Quoted 12 lines
I know you don't have those answers yet, and I know there's some chicken-and-egg with getting this integrated so that you can start to explore that. So I mostly reviewed this with an eye towards:
- does the idea make sense (I think it does, but I'm kind of biased)
- are the patches going to hurt anybody who isn't using the new feature (I think the answer is no)
- does the on-disk representation seem right, since that is hard to change later (I didn't see any issues)
Quoted 8 lines
- does the implementation look clean and plausibly correct (yes, but what I'm getting at is that I didn't pore over all of the new code with a microscope. Mostly I think the proof is in the pudding that it provides the same correct answers more quickly).
So to my eyes it looks good to move forward and let people start playing with it. The big "experimental" warning in the config is good. Maybe we'd want want in gitpacking(7), too?
I think adding a matching warning in gitpacking(7) is a good idea. Your feeling matches my own here that the burden of this series on those not using pseudo-merge bitmaps is negligible, and that this unblocks those who want to move forward with testing this out in the wild on doing so.
I'll send a v4 shortly with the minor changes that I picked up from your last read-through, and then I think we are good to go here.
Thanks,
Taylor
v4 cover pack-bitmap: pseudo-merge reachability bitmaps
In reply to Taylor BlauHere 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 <[email protected]>
## 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.
@@ 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 <[email protected]>
## 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.
@@ 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 <[email protected]>
## 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)
+
## 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
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 1/24 Documentation/gitpacking.txt: initial commit
Introduce a new manual page, gitpacking(7) to collect useful information about advanced packing concepts in Git.
In future commits in this series, this manual page will expand to describe the new pseudo-merge bitmaps feature, as well as include examples, relevant configuration bits, use-cases, and so on.
Outside of this series, this manual page may absorb similar pieces from other parts of Git's documentation about packing.
--- Documentation/Makefile | 1 + Documentation/gitpacking.txt | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 35 insertions(+) create mode 100644 Documentation/gitpacking.txt
Documentation/Makefile +1 -0
@@ -51,6 +51,7 @@ MAN7_TXT += gitdiffcore.txt MAN7_TXT += giteveryday.txt MAN7_TXT += gitfaq.txt MAN7_TXT += gitglossary.txt +MAN7_TXT += gitpacking.txt MAN7_TXT += gitnamespaces.txt MAN7_TXT += gitremote-helpers.txt MAN7_TXT += gitrevisions.txt
Documentation/gitpacking.txt new file +34 -0
@@ -0,0 +1,34 @@ +gitpacking(7) +============= + +NAME +---- +gitpacking - Advanced concepts related to packing in Git + +SYNOPSIS +-------- +gitpacking + +DESCRIPTION +----------- + +This document aims to describe some advanced concepts related to packing +in Git. + +Many concepts are currently described scattered between manual pages of +various Git commands, including linkgit:git-pack-objects[1], +linkgit:git-repack[1], and others, as well as linkgit:gitformat-pack[5], +and parts of the `Documentation/technical` tree. + +There are many aspects of packing in Git that are not covered in this +document that instead live in the aforementioned areas. Over time, those +scattered bits may coalesce into this document. + +SEE ALSO +-------- +linkgit:git-pack-objects[1] +linkgit:git-repack[1] + +GIT +--- +Part of the linkgit:git[1] suite
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 2/24 Documentation/gitpacking.txt: describe pseudo-merge bitmaps
In reply to Taylor BlauAdd some details to the gitpacking(7) manual page which motivate and describe pseudo-merge bitmaps.
The exact on-disk format and many of the configuration knobs will be described in subsequent commits.
--- Documentation/gitpacking.txt | 72 ++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+)
Documentation/gitpacking.txt +72 -0
@@ -24,6 +24,78 @@ There are many aspects of packing in Git that are not covered in this document that instead live in the aforementioned areas. Over time, those scattered bits may coalesce into this document. +== 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 +bitmaps for one or more of the starting points of a traversal. For this +reason, Git prefers storing bitmaps for commits at the tips of refs, +because traversals tend to start with those points. + +But if you have a large number of refs, it's not feasible to store a +bitmap for _every_ ref tip. It takes up space, and just OR-ing all of +those bitmaps together is expensive. + +One way we can deal with that is to create bitmaps that represent +_groups_ of refs. When a traversal asks about the entire group, then we +can use this single bitmap instead of considering each ref individually. +Because these bitmaps represent the set of objects which would be +reachable in a hypothetical merge of all of the commits, we call them +pseudo-merge bitmaps. + +=== Overview + +A "pseudo-merge bitmap" is used to refer to a pair of bitmaps, as +follows: + +Commit bitmap:: + + A bitmap whose set bits describe the set of commits included in the + pseudo-merge's "merge" bitmap (as below). + +Merge bitmap:: + + A bitmap whose set bits describe the reachability closure over the set + of commits in the pseudo-merge's "commits" bitmap (as above). An + identical bitmap would be generated for an octopus merge with the same + set of parents as described in the commits bitmap. + +Pseudo-merge bitmaps can accelerate bitmap traversals when all commits +for a given pseudo-merge are listed on either side of the traversal, +either directly (by explicitly asking for them as part of the `HAVES` +or `WANTS`) or indirectly (by encountering them during a fill-in +traversal). + +=== Use-cases + +For example, suppose there exists a pseudo-merge bitmap with a large +number of commits, all of which are listed in the `WANTS` section of +some bitmap traversal query. When pseudo-merge bitmaps are enabled, the +bitmap machinery can quickly determine there is a pseudo-merge which +satisfies some subset of the wanted objects on either side of the query. +Then, we can inflate the EWAH-compressed bitmap, and `OR` it in to the +resulting bitmap. By contrast, without pseudo-merge bitmaps, we would +have to repeat the decompression and `OR`-ing step over a potentially +large number of individual bitmaps, which can take proportionally more +time. + +Another benefit of pseudo-merges arises when there is some combination +of (a) a large number of references, with (b) poor bitmap coverage, and +(c) deep, nested trees, making fill-in traversal relatively expensive. +For example, suppose that there are a large enough number of tags where +bitmapping each of the tags individually is infeasible. Without +pseudo-merge bitmaps, computing the result of, say, `git rev-list +--use-bitmap-index --count --objects --tags` would likely require a +large amount of fill-in traversal. But when a large quantity of those +tags are stored together in a pseudo-merge bitmap, the bitmap machinery +can take advantage of the fact that we only care about the union of +objects reachable from all of those tags, and answer the query much +faster. + SEE ALSO -------- linkgit:git-pack-objects[1]
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 3/24 Documentation/technical: describe pseudo-merge bitmaps format
In reply to Taylor BlauPrepare to implement pseudo-merge bitmaps over the next several commits by first describing the serialization format which will store the new pseudo-merge bitmaps themselves.
This format is implemented as an optional extension within the bitmap v1 format, making it compatible with previous versions of Git, as well as the original .bitmap implementation within JGit.
The format is described in detail in the patch contents below, but the high-level description is as follows:
- An array of pseudo-merge bitmaps, each containing a pair of EWAH
bitmaps: one describing the set of pseudo-merge "parents", and another describing the set of object(s) reachable from those parents.
- A lookup table to determine which pseudo-merge(s) a given commit appears in. An optional extended lookup table follows when there is at least one commit which appears in multiple pseudo-merge groups.
- Trailing metadata, including the number of pseudo-merge(s), number of unique parents, the offset within the .bitmap file for the pseudo-merge commit lookup table, and the size of the optional extension itself.
--- Documentation/technical/bitmap-format.txt | 132 ++++++++++++++++++++++ 1 file changed, 132 insertions(+)
Documentation/technical/bitmap-format.txt +132 -0
@@ -255,3 +255,135 @@ triplet is - xor_row (4 byte integer, network byte order): :: The position of the triplet whose bitmap is used to compress this one, or `0xffffffff` if no such bitmap exists. + +Pseudo-merge bitmaps +-------------------- + +If the `BITMAP_OPT_PSEUDO_MERGES` flag is set, a variable number of +bytes (preceding the name-hash cache, commit lookup table, and trailing +checksum) of the `.bitmap` file is used to store pseudo-merge bitmaps. + +For more information on what pseudo-merges are, why they are useful, and +how to configure them, see the information in linkgit:gitpacking[7]. + +=== File format + +If enabled, pseudo-merge bitmaps are stored in an optional section at +the end of a `.bitmap` file. The format is as follows: + +.... ++-------------------------------------------+ +| .bitmap File | ++-------------------------------------------+ +| | +| Pseudo-merge bitmaps (Variable Length) | +| +---------------------------+ | +| | commits_bitmap (EWAH) | | +| +---------------------------+ | +| | merge_bitmap (EWAH) | | +| +---------------------------+ | +| | ++-------------------------------------------+ +| | +| Lookup Table | +| +---------------------------+ | +| | commit_pos (4 bytes) | | +| +---------------------------+ | +| | offset (8 bytes) | | +| +------------+--------------+ | +| | +| Offset Cases: | +| ------------- | +| | +| 1. MSB Unset: single pseudo-merge bitmap | +| + offset to pseudo-merge bitmap | +| | +| 2. MSB Set: multiple pseudo-merges | +| + offset to extended lookup table | +| | ++-------------------------------------------+ +| | +| Extended Lookup Table (Optional) | +| +----+----------+----------+----------+ | +| | N | Offset 1 | .... | Offset N | | +| +----+----------+----------+----------+ | +| | | 8 bytes | .... | 8 bytes | | +| +----+----------+----------+----------+ | +| | ++-------------------------------------------+ +| | +| Pseudo-merge Metadata | +| +-----------------------------------+ | +| | # pseudo-merges (4 bytes) | | +| +-----------------------------------+ | +| | # commits (4 bytes) | | +| +-----------------------------------+ | +| | Lookup offset (8 bytes) | | +| +-----------------------------------+ | +| | Extension size (8 bytes) | | +| +-----------------------------------+ | +| | ++-------------------------------------------+ +.... + +* One or more pseudo-merge bitmaps, each containing: + + ** `commits_bitmap`, an EWAH-compressed bitmap describing the set of + commits included in the this psuedo-merge. + + ** `merge_bitmap`, an EWAH-compressed bitmap describing the union of + the set of objects reachable from all commits listed in the + `commits_bitmap`. + +* A lookup table, mapping pseudo-merged commits to the pseudo-merges + they belong to. Entries appear in increasing order of each commit's + bit position. Each entry is 12 bytes wide, and is comprised of the + following: + + ** `commit_pos`, a 4-byte unsigned value (in network byte-order) + containing the bit position for this commit. + + ** `offset`, an 8-byte unsigned value (also in network byte-order) + containing either one of two possible offsets, depending on whether or + not the most-significant bit is set. + + *** If unset (i.e. `offset & ((uint64_t)1<<63) == 0`), the offset + (relative to the beginning of the `.bitmap` file) at which the + pseudo-merge bitmap for this commit can be read. This indicates + only a single pseudo-merge bitmap contains this commit. + + *** If set (i.e. `offset & ((uint64_t)1<<63) != 0`), the offset + (again relative to the beginning of the `.bitmap` file) at which + the extended offset table can be located describing the set of + pseudo-merge bitmaps which contain this commit. This indicates + that multiple pseudo-merge bitmaps contain this commit. + +* An (optional) extended lookup table (written if and only if there is + at least one commit which appears in more than one pseudo-merge). + There are as many entries as commits which appear in multiple + pseudo-merges. Each entry contains the following: + + ** `N`, a 4-byte unsigned value equal to the number of pseudo-merges + which contain a given commit. + + ** An array of `N` 8-byte unsigned values, each of which is + interpreted as an offset (relative to the beginning of the + `.bitmap` file) at which a pseudo-merge bitmap for this commit can + be read. These values occur in no particular order. + +* Positions for all pseudo-merges, each stored as an 8-byte unsigned + value (in network byte-order) containing the offset (relative to the + beginning of the `.bitmap` file) of each consecutive pseudo-merge. + +* A 4-byte unsigned value (in network byte-order) equal to the number of + pseudo-merges. + +* A 4-byte unsigned value (in network byte-order) equal to the number of + unique commits which appear in any pseudo-merge. + +* An 8-byte unsigned value (in network byte-order) equal to the number + of bytes between the start of the pseudo-merge section and the + beginning of the lookup table. + +* An 8-byte unsigned value (in network byte-order) equal to the number + of bytes in the pseudo-merge section (including this field).
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 4/24 ewah: implement `ewah_bitmap_is_subset()`
In reply to Taylor BlauIn order to know whether a given pseudo-merge (comprised of a "parents" and "objects" bitmaps) is "satisfied" and can be OR'd into the bitmap result, we need to be able to quickly determine whether the "parents" bitmap is a subset of the current set of objects reachable on either side of a traversal.
Implement a helper function to prepare for that, which determines whether an EWAH bitmap (the parents bitmap from the pseudo-merge) is a subset of a non-EWAH bitmap (in this case, the results bitmap from either side of the traversal).
This function makes use of the EWAH iterator to avoid inflating any part of the EWAH bitmap after we determine it is not a subset of the non-EWAH bitmap. This "fail-fast" allows us to avoid a potentially large amount of wasted effort.
--- ewah/bitmap.c | 43 +++++++++++++++++++++++++++++++++++++++++++ ewah/ewok.h | 6 ++++++ 2 files changed, 49 insertions(+)
ewah/bitmap.c +43 -0
@@ -138,6 +138,49 @@ void bitmap_or(struct bitmap *self, const struct bitmap *other) self->words[i] |= other->words[i]; } +int ewah_bitmap_is_subset (struct ewah_bitmap *self,struct bitmap *other) +{ +struct ewah_iterator it; +eword_t word; +size_t i; + +ewah_iterator_init (&it, self); + +for (i =0 ; i < other->word_alloc; i++) { +if (!ewah_iterator_next (&word, &it)) { +/* +* If we reached the end of `self`, and haven't +* rejected `self` as a possible subset of +* `other` yet, then we are done and `self` is +* indeed a subset of `other`. +*/ +return 1 ; + } +if (word & ~other->words[i]) { +/* +* Otherwise, compare the next two pairs of +* words. If the word from `self` has bit(s) not +* in the word from `other`, `self` is not a +* subset of `other`. +*/ +return 0 ; + } + } + +/* +* If we got to this point, there may be zero or more words +* remaining in `self`, with no remaining words left in `other`. +* If there are any bits set in the remaining word(s) in `self`, +* then `self` is not a subset of `other`. +*/ +while (ewah_iterator_next (&word, &it)) +if (word) +return 0 ; + +/* `self` is definitely a subset of `other` */ +return 1 ; +} +void bitmap_or_ewah (struct bitmap *self,struct ewah_bitmap *other) {size_t original_size = self->word_alloc;
ewah/ewok.h +6 -0
@@ -179,7 +179,13 @@ void bitmap_unset(struct bitmap *self, size_t pos);int bitmap_get (struct bitmap *self,size_t pos);void bitmap_free (struct bitmap *self);int bitmap_equals (struct bitmap *self,struct bitmap *other); + +/* +* Both `bitmap_is_subset()` and `ewah_bitmap_is_subset()` return 1 if the set +* of bits in 'self' are a subset of the bits in 'other'. Returns 0 otherwise. +*/ int bitmap_is_subset (struct bitmap *self,struct bitmap *other); +int ewah_bitmap_is_subset (struct ewah_bitmap *self,struct bitmap *other);struct ewah_bitmap *bitmap_to_ewah (struct bitmap *bitmap);struct bitmap *ewah_to_bitmap (struct ewah_bitmap *ewah);
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 5/24 pack-bitmap: move some initialization to `bitmap_writer_init()`
In reply to Taylor BlauThe pack-bitmap-writer machinery uses a oidmap (backed by khash.h) to map from commits selected for bitmaps (by OID) to a bitmapped_commit structure (containing the bitmap itself, among other things like its XOR offset, etc.)
This map was initialized at the end of bitmap_writer_build(). New entries are added in pack-bitmap-write.c::store_selected(), which is called by the bitmap_builder machinery (which is responsible for traversing history and generating the actual bitmaps).
Reorganize when this field is initialized and when entries are added to it so that we can quickly determine whether a commit is a candidate for pseudo-merge selection, or not (since it was already selected to receive a bitmap, and thus storing it in a pseudo-merge would be redundant).
The changes are as follows:
- Introduce a new bitmap_writer_init() function which initializes the writer.bitmaps field (instead of waiting until the end of bitmap_writer_build()).
- Add map entries in push_bitmapped_commit() (which is called via bitmap_writer_select_commits()) with OID keys and NULL values to track whether or not we *expect* to write a bitmap for some given commit.
- Validate that a NULL entry is found matching the given key when we store a selected bitmap.
--- builtin/pack-objects.c | 3 ++- midx-write.c | 2 +- pack-bitmap-write.c | 24 ++++++++++++++++++------ pack-bitmap.h | 2 +- 4 files changed, 22 insertions(+), 9 deletions(-)
builtin/pack-objects.c +2 -1
@@ -1340,7 +1340,8 @@ static void write_pack_file(void) hash_to_hex(hash));if (write_bitmap_index) { -bitmap_writer_init (&bitmap_writer); +bitmap_writer_init (&bitmap_writer, + the_repository);bitmap_writer_set_checksum (&bitmap_writer, hash);bitmap_writer_build_type_index (&bitmap_writer, &to_pack, written_list, nr_written);
midx-write.c +1 -1
@@ -820,7 +820,7 @@ static int write_midx_bitmap(const char *midx_name,for (i =0 ; i < pdata->nr_objects; i++) index[i] = &pdata->objects[i].idx; -bitmap_writer_init (&writer); +bitmap_writer_init (&writer, the_repository);bitmap_writer_show_progress (&writer, flags &MIDX_PROGRESS );bitmap_writer_build_type_index (&writer, pdata, index, pdata->nr_objects);
pack-bitmap-write.c +18 -6
@@ -27,9 +27,12 @@ struct bitmapped_commit {uint32_t commit_pos; }; -void bitmap_writer_init (struct bitmap_writer *writer) +void bitmap_writer_init (struct bitmap_writer *writer,struct repository *r) {memset (writer,0 ,sizeof (struct bitmap_writer )); +if (writer->bitmaps) +BUG ("bitmap writer already initialized" ); + writer->bitmaps =kh_init_oid_map (); }void bitmap_writer_free (struct bitmap_writer *writer)
@@ -128,11 +131,21 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer,static inline void push_bitmapped_commit (struct bitmap_writer *writer,struct commit *commit) { +int hash_ret; +khiter_t hash_pos; +if (writer->selected_nr >= writer->selected_alloc) { writer->selected_alloc = (writer->selected_alloc +32 ) *2 ;REALLOC_ARRAY (writer->selected, writer->selected_alloc); } + hash_pos =kh_put_oid_map (writer->bitmaps, commit->object.oid, + &hash_ret); +if (!hash_ret) +die (_ ("duplicate entry when writing bitmap index: %s" ), +oid_to_hex (&commit->object.oid)); +kh_value (writer->bitmaps, hash_pos) =NULL ; + writer->selected[writer->selected_nr].commit = commit; writer->selected[writer->selected_nr].bitmap =NULL ; writer->selected[writer->selected_nr].write_as =NULL ;
@@ -483,14 +496,14 @@ static void store_selected(struct bitmap_writer *writer, {struct bitmapped_commit *stored = &writer->selected[ent->idx];khiter_t hash_pos; -int hash_ret; stored->bitmap =bitmap_to_ewah (ent->bitmap); - hash_pos =kh_put_oid_map (writer->bitmaps, commit->object.oid, &hash_ret); -if (hash_ret ==0 ) -die ("Duplicate entry when writing index: %s" , + hash_pos =kh_get_oid_map (writer->bitmaps, commit->object.oid); +if (hash_pos ==kh_end (writer->bitmaps)) +die (_ ("attempted to store non-selected commit: '%s'" ),oid_to_hex (&commit->object.oid)); +kh_value (writer->bitmaps, hash_pos) = stored; }
@@ -506,7 +519,6 @@ int bitmap_writer_build(struct bitmap_writer *writer,uint32_t *mapping;int closed =1 ;/* until proven otherwise */ - writer->bitmaps =kh_init_oid_map (); writer->to_pack = to_pack;if (writer->show_progress)
pack-bitmap.h +1 -1
@@ -114,7 +114,7 @@ struct bitmap_writer {unsigned char pack_checksum[GIT_MAX_RAWSZ ]; }; -void bitmap_writer_init (struct bitmap_writer *writer); +void bitmap_writer_init (struct bitmap_writer *writer,struct repository *r);void bitmap_writer_show_progress (struct bitmap_writer *writer,int show);void bitmap_writer_set_checksum (struct bitmap_writer *writer,const unsigned char *sha1);
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 6/24 pseudo-merge.ch: initial commit
In reply to Taylor BlauAdd a new (empty) header file to contain the implementation for selecting, reading, and applying pseudo-merge bitmaps.
For now this header and its corresponding implementation are left empty, but they will evolve over the course of subsequent commit(s).
--- Makefile | 1 + pseudo-merge.c | 2 ++ pseudo-merge.h | 6 ++++++ 3 files changed, 9 insertions(+) create mode 100644 pseudo-merge.c create mode 100644 pseudo-merge.h
Makefile +1 -0
@@ -1105,6 +1105,7 @@ LIB_OBJS += prompt.o LIB_OBJS += protocol.o LIB_OBJS += protocol-caps.o LIB_OBJS += prune-packed.o +LIB_OBJS += pseudo-merge.o LIB_OBJS += quote.o LIB_OBJS += range-diff.o LIB_OBJS += reachable.o
pseudo-merge.c new file +2 -0
@@ -0,0 +1,2 @@ +#include "git-compat-util.h" +#include "pseudo-merge.h"
pseudo-merge.h new file +6 -0
@@ -0,0 +1,6 @@ +#ifndef PSEUDO_MERGE_H +#define PSEUDO_MERGE_H + +#include "git-compat-util.h" + +#endif
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 7/24 pack-bitmap-write: support storing pseudo-merge commits
In reply to Taylor BlauPrepare to write pseudo-merge bitmaps by annotating individual bitmapped commits (which are represented by the bitmapped_commit structure) with an extra bit indicating whether or not they are a pseudo-merge.
In subsequent commits, pseudo-merge bitmaps will be generated by allocating a fake commit node with parents covering the full set of commits represented by the pseudo-merge bitmap. These commits will be added to the set of "selected" commits as usual, but will be written specially instead of being included with the rest of the selected commits.
Mechanically speaking, there are two parts of this change:
- The bitmapped_commit struct gets a new bit indicating whether it is a pseudo-merge, or an ordinary commit selected for bitmaps.
- A handful of changes to only write out the non-pseudo-merge commits when enumerating through the selected array (see the new bitmap_writer_selected_nr() function). Pseudo-merge commits appear after all non-pseudo-merge commits, so it is safe to enumerate through the selected array like so:
for (i = 0; i < bitmap_writer_selected_nr(); i++)
if (writer.selected[i].pseudo_merge)
BUG("unexpected pseudo-merge");
without encountering the BUG().
--- object.h | 2 +- pack-bitmap-write.c | 96 +++++++++++++++++++++++++++++---------------- pack-bitmap.h | 3 ++ 3 files changed, 67 insertions(+), 34 deletions(-)
object.h +1 -1
@@ -81,7 +81,7 @@ void object_array_init(struct object_array *array);* reflog.c: 10--12 * builtin/show-branch.c: 0-------------------------------------------26 * builtin/unpack-objects.c: 2021 -* pack-bitmap.h: 22 +* pack-bitmap.h: 2122 */ #define FLAG_BITS 28
pack-bitmap-write.c +63 -33
232 lines not on this page · raw message
pack-bitmap.h +3 -0
@@ -21,6 +21,7 @@ struct bitmap_disk_header {unsigned char checksum[GIT_MAX_RAWSZ ]; }; +#define BITMAP_PSEUDO_MERGE (1u<<21)#define NEEDS_BITMAP (1u<<22)/*
@@ -109,6 +110,8 @@ struct bitmap_writer {struct bitmapped_commit *selected;unsigned int selected_nr, selected_alloc; +uint32_t pseudo_merges_nr; +struct progress *progress;int show_progress;unsigned char pack_checksum[GIT_MAX_RAWSZ ];
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 8/24 pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()`
In reply to Taylor BlauPrepare to implement pseudo-merge bitmap selection by implementing a necessary new function, bitmap_writer_has_bitmapped_object_id().
This function returns whether or not the bitmap_writer selected the given object ID for bitmapping. This will allow the pseudo-merge machinery to reject candidates for pseudo-merges if they have already been selected as an ordinary bitmap tip.
--- pack-bitmap-write.c | 6 ++++++ pack-bitmap.h | 2 ++ 2 files changed, 8 insertions(+)
pack-bitmap-write.c +6 -0
@@ -130,6 +130,12 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer, } } +int bitmap_writer_has_bitmapped_object_id (struct bitmap_writer *writer, +const struct object_id *oid) +{ +return kh_get_oid_map (writer->bitmaps, *oid) !=kh_end (writer->bitmaps); +} +/** * Compute the actual bitmaps */
pack-bitmap.h +2 -0
@@ -125,6 +125,8 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer,struct packing_data *to_pack, struct pack_idx_entry **index, uint32_t index_nr); +int bitmap_writer_has_bitmapped_object_id (struct bitmap_writer *writer, +const struct object_id *oid);uint32_t *create_bitmap_mapping (struct bitmap_index *bitmap_git,struct packing_data *mapping); int rebuild_bitmap(const uint32_t *reposition,
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 9/24 pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public
In reply to Taylor BlauThe pseudo-merge selection code will be added in a subsequent commit, and will need a way to push the allocated commit structures into the bitmap writer from a separate compilation unit.
Make the bitmap_writer_push_bitmapped_commit() function part of the pack-bitmap.h header in order to make this possible.
--- pack-bitmap-write.c | 9 ++++----- pack-bitmap.h | 2 ++ 2 files changed, 6 insertions(+), 5 deletions(-)
pack-bitmap-write.c +4 -5
@@ -140,9 +140,8 @@ int bitmap_writer_has_bitmapped_object_id(struct bitmap_writer *writer,* Compute the actual bitmaps */ -static inline void push_bitmapped_commit (struct bitmap_writer *writer, -struct commit *commit, -unsigned pseudo_merge) +void bitmap_writer_push_commit (struct bitmap_writer *writer, +struct commit *commit,unsigned pseudo_merge) {if (writer->selected_nr >= writer->selected_alloc) { writer->selected_alloc = (writer->selected_alloc +32 ) *2 ;
@@ -664,7 +663,7 @@ void bitmap_writer_select_commits(struct bitmap_writer *writer,if (indexed_commits_nr <100 ) {for (i =0 ; i < indexed_commits_nr; ++i) -push_bitmapped_commit (writer, indexed_commits[i],0 ); +bitmap_writer_push_commit (writer, indexed_commits[i],0 );return ; }
@@ -697,7 +696,7 @@ void bitmap_writer_select_commits(struct bitmap_writer *writer, } } -push_bitmapped_commit (writer, chosen,0 ); +bitmap_writer_push_commit (writer, chosen,0 ); i += next +1 ;display_progress (writer->progress, i);
pack-bitmap.h +2 -0
@@ -127,6 +127,8 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer, uint32_t index_nr);int bitmap_writer_has_bitmapped_object_id (struct bitmap_writer *writer,const struct object_id *oid); +void bitmap_writer_push_commit (struct bitmap_writer *writer, +struct commit *commit,unsigned pseudo_merge);uint32_t *create_bitmap_mapping (struct bitmap_index *bitmap_git,struct packing_data *mapping); int rebuild_bitmap(const uint32_t *reposition,
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 10/24 config: introduce `git_config_double()`
In reply to Taylor BlauFuture 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_double(). Unlike git_parse_unsigned() and git_parse_signed(), however, the function implemented here only works on type "double", and not related types like "float", or "long double".
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 double-precision floats.
--- config.c | 9 +++++++++ config.h | 7 +++++++ parse.c | 29 +++++++++++++++++++++++++++++ parse.h | 1 + 4 files changed, 46 insertions(+)
config.c +9 -0
@@ -1243,6 +1243,15 @@ ssize_t git_config_ssize_t(const char *name, const char *value,return ret; } +double git_config_double (const char *name,const char *value, +const struct key_value_info *kvi) +{ +double ret; +if (!git_parse_double (value, &ret)) +die_bad_number (name, value, kvi); +return ret; +} + static const struct fsync_component_name { const char *name; enum fsync_component component_bits;
config.h +7 -0
@@ -261,6 +261,13 @@ unsigned long git_config_ulong(const char *, const char *,ssize_t git_config_ssize_t (const char *,const char *,const struct key_value_info *); +/** +* Identically to `git_config_double`, but for double-precision floating point +* values. +*/ +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 * an `is_bool` flag is unset.
parse.c +29 -0
@@ -125,6 +125,35 @@ int git_parse_ssize_t(const char *value, ssize_t *ret)return 1 ; } +int git_parse_double (const char *value,double *ret) +{ +char *end; +double val; +uintmax_t factor; + +if (!value || !*value) { + errno =EINVAL ; +return 0 ; + } + + errno =0 ; + val =strtod (value, &end); +if (errno ==ERANGE ) +return 0 ; +if (end == value) { + errno =EINVAL ; +return 0 ; + } + factor =get_unit_factor (end); +if (!factor) { + errno =EINVAL ; +return 0 ; + } + val *= factor; + *ret = val; +return 1 ; +} +int git_parse_maybe_bool_text (const char *value) {if (!value)
parse.h +1 -0
@@ -6,6 +6,7 @@ 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_double (const char *value,double *ret);/** * Same as `git_config_bool`, except that it returns -1 on error rather
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 11/24 pseudo-merge: implement support for selecting pseudo-merge commits
In reply to Taylor BlauTeach the new pseudo-merge machinery how to select non-bitmapped commits for inclusion in different pseudo-merge group(s) based on a handful of criteria.
Note that the selected pseudo-merge commits aren't actually used or written anywhere yet. This will be done in the following commit.
--- Documentation/config.txt | 2 + Documentation/config/bitmap-pseudo-merge.txt | 91 ++++ Documentation/gitpacking.txt | 83 ++++ pack-bitmap-write.c | 21 + pack-bitmap.h | 2 + pseudo-merge.c | 454 +++++++++++++++++++ pseudo-merge.h | 94 ++++ 7 files changed, 747 insertions(+) create mode 100644 Documentation/config/bitmap-pseudo-merge.txt
Documentation/config.txt +2 -0
@@ -384,6 +384,8 @@ include::config/apply.txt[] include::config/attr.txt[] +include::config/bitmap-pseudo-merge.txt[] + include::config/blame.txt[] include::config/branch.txt[]
Documentation/config/bitmap-pseudo-merge.txt new file +91 -0
91 lines not on this page · raw message
Documentation/gitpacking.txt +83 -0
89 lines not on this page · raw message
pack-bitmap-write.c +21 -0
@@ -17,6 +17,7 @@#include "trace2.h" #include "tree.h" #include "tree-walk.h" +#include "pseudo-merge.h" struct bitmapped_commit {struct commit *commit;
@@ -39,11 +40,25 @@ void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r)if (writer->bitmaps)BUG ("bitmap writer already initialized" ); writer->bitmaps =kh_init_oid_map (); + writer->pseudo_merge_commits =kh_init_oid_map (); + +string_list_init_dup (&writer->pseudo_merge_groups); + +load_pseudo_merges_from_config (&writer->pseudo_merge_groups); +} + +static void free_pseudo_merge_commit_idx (struct pseudo_merge_commit_idx *idx) +{ +if (!idx) +return ; +free (idx->pseudo_merge); +free (idx); }void bitmap_writer_free (struct bitmap_writer *writer) {uint32_t i; +struct pseudo_merge_commit_idx *idx;if (!writer)return ;
@@ -55,6 +70,10 @@ void bitmap_writer_free(struct bitmap_writer *writer)kh_destroy_oid_map (writer->bitmaps); +kh_foreach_value (writer->pseudo_merge_commits, idx, +free_pseudo_merge_commit_idx (idx)); +kh_destroy_oid_map (writer->pseudo_merge_commits); +for (i =0 ; i < writer->selected_nr; i++) {struct bitmapped_commit *bc = &writer->selected[i];if (bc->write_as != bc->bitmap)
@@ -703,6 +722,8 @@ void bitmap_writer_select_commits(struct bitmap_writer *writer, }stop_progress (&writer->progress); + +select_pseudo_merges (writer, indexed_commits, indexed_commits_nr); }
pack-bitmap.h +2 -0
@@ -110,6 +110,8 @@ struct bitmap_writer {struct bitmapped_commit *selected;unsigned int selected_nr, selected_alloc; +struct string_list pseudo_merge_groups; +kh_oid_map_t *pseudo_merge_commits;/* oid -> pseudo merge(s) */ uint32_t pseudo_merges_nr;struct progress *progress;
pseudo-merge.c +454 -0
456 lines not on this page · raw message
pseudo-merge.h +94 -0
99 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gcf0316ad0e9
Re: [PATCH v4 11/24] pseudo-merge: implement support for selecting pseudo-merge commits
pseudo-merge.c line 39
Quoted 5 lines · Taylor Blau
pseudo-merge.c +5
-0+static uint32_t pseudo_merge_group_size (const struct pseudo_merge_group *group, +const struct pseudo_merge_matches *matches, +uint32_t i) +{ +double C =0.0f ;
This version mostly drops the "f" from floating point constants, since they're now doubles. But this one doesn't.
I don't think it really matters in practice (the number obviously fits in a float, and then it ends up as a double in the variable), so it's really just a style / readability question.
Not worth a re-roll IMHO.
-Peff
PATCH v4 12/24 pack-bitmap-write.c: write pseudo-merge table
In reply to Taylor BlauNow that the pack-bitmap writer machinery understands how to select and store pseudo-merge commits, teach it how to write the new optional pseudo-merge .bitmap extension.
No readers yet exist for this new extension to the .bitmap format. The following commits will take any preparatory step(s) necessary before then implementing the routines necessary to read this new table.
In the meantime, the new write_pseudo_merges() function implements writing this new format as described by a previous commit in Documentation/technical/bitmap-format.txt.
Writing this table is fairly straightforward and consists of a few sub-components:
- a pair of bitmaps for each pseudo-merge (one for the pseudo-merge "parents", and another for the objects reachable from those parents)
- for each commit, the offset of either (a) the pseudo-merge it belongs to, or (b) an extended lookup table if it belongs to >1 pseudo-merge groups
- if there are any commits belonging to >1 pseudo-merge group, the extended lookup tables (which each consist of the number of pseudo-merge groups a commit appears in, and then that many 4-byte unsigned )
--- pack-bitmap-write.c | 131 ++++++++++++++++++++++++++++++++++++++++++++ pack-bitmap.h | 1 + 2 files changed, 132 insertions(+)
pack-bitmap-write.c +131 -0
@@ -18,6 +18,7 @@#include "tree.h" #include "tree-walk.h" #include "pseudo-merge.h" +#include "oid-array.h" struct bitmapped_commit {struct commit *commit;
@@ -771,6 +772,130 @@ static void write_selected_commits_v1(struct bitmap_writer *writer, } } +static void write_pseudo_merges (struct bitmap_writer *writer, +struct hashfile *f) +{ +struct oid_array commits =OID_ARRAY_INIT ; +struct bitmap **commits_bitmap =NULL ; +off_t *pseudo_merge_ofs =NULL ; +off_t start, table_start, next_ext; + +uint32_t base =bitmap_writer_nr_selected_commits (writer); +size_t i, j =0 ; + +CALLOC_ARRAY (commits_bitmap, writer->pseudo_merges_nr); +CALLOC_ARRAY (pseudo_merge_ofs, writer->pseudo_merges_nr); + +for (i =0 ; i < writer->pseudo_merges_nr; i++) { +struct bitmapped_commit *merge = &writer->selected[base + i]; +struct commit_list *p; + +if (!merge->pseudo_merge) +BUG ("found non-pseudo merge commit at %" PRIuMAX, (uintmax_t )i); + + commits_bitmap[i] =bitmap_new (); + +for (p = merge->commit->parents; p; p = p->next) +bitmap_set (commits_bitmap[i], +find_object_pos (writer, &p->item->object.oid, +NULL )); + } + + start =hashfile_total (f); + +for (i =0 ; i < writer->pseudo_merges_nr; i++) { +struct ewah_bitmap *commits_ewah =bitmap_to_ewah (commits_bitmap[i]); + + pseudo_merge_ofs[i] =hashfile_total (f); + +dump_bitmap (f, commits_ewah); +dump_bitmap (f, writer->selected[base+i].write_as); + +ewah_free (commits_ewah); + } + + next_ext =st_add (hashfile_total (f), +st_mult (kh_size (writer->pseudo_merge_commits), +sizeof (uint64_t ))); + + table_start =hashfile_total (f); + + commits.alloc =kh_size (writer->pseudo_merge_commits); +CALLOC_ARRAY (commits.oid, commits.alloc); + +for (i =kh_begin (writer->pseudo_merge_commits); i !=kh_end (writer->pseudo_merge_commits); i++) { +if (!kh_exist (writer->pseudo_merge_commits, i)) +continue ; +oid_array_append (&commits, &kh_key (writer->pseudo_merge_commits, i)); + } + +oid_array_sort (&commits); + +/* write lookup table (non-extended) */ +for (i =0 ; i < commits.nr; i++) { +int hash_pos; +struct pseudo_merge_commit_idx *c; + + hash_pos =kh_get_oid_map (writer->pseudo_merge_commits, + commits.oid[i]); +if (hash_pos ==kh_end (writer->pseudo_merge_commits)) +BUG ("could not find pseudo-merge commit %s" , +oid_to_hex (&commits.oid[i])); + + c =kh_value (writer->pseudo_merge_commits, hash_pos); + +hashwrite_be32 (f,find_object_pos (writer, &commits.oid[i], +NULL )); +if (c->nr ==1 ) +hashwrite_be64 (f, pseudo_merge_ofs[c->pseudo_merge[0 ]]); +else if (c->nr >1 ) { +if (next_ext & ((uint64_t )1 <<63 )) +die (_ ("too many pseudo-merges" )); +hashwrite_be64 (f, next_ext | ((uint64_t )1 <<63 )); + next_ext =st_add3 (next_ext, +sizeof (uint32_t ), +st_mult (c->nr,sizeof (uint64_t ))); + }else +BUG ("expected commit '%s' to have at least one " +"pseudo-merge" ,oid_to_hex (&commits.oid[i])); + } + +/* write lookup table (extended) */ +for (i =0 ; i < commits.nr; i++) { +int hash_pos; +struct pseudo_merge_commit_idx *c; + + hash_pos =kh_get_oid_map (writer->pseudo_merge_commits, + commits.oid[i]); +if (hash_pos ==kh_end (writer->pseudo_merge_commits)) +BUG ("could not find pseudo-merge commit %s" , +oid_to_hex (&commits.oid[i])); + + c =kh_value (writer->pseudo_merge_commits, hash_pos); +if (c->nr ==1 ) +continue ; + +hashwrite_be32 (f, c->nr); +for (j =0 ; j < c->nr; j++) +hashwrite_be64 (f, pseudo_merge_ofs[c->pseudo_merge[j]]); + } + +/* write positions for all pseudo merges */ +for (i =0 ; i < writer->pseudo_merges_nr; i++) +hashwrite_be64 (f, pseudo_merge_ofs[i]); + +hashwrite_be32 (f, writer->pseudo_merges_nr); +hashwrite_be32 (f,kh_size (writer->pseudo_merge_commits)); +hashwrite_be64 (f, table_start - start); +hashwrite_be64 (f,hashfile_total (f) - start +sizeof (uint64_t )); + +for (i =0 ; i < writer->pseudo_merges_nr; i++) +bitmap_free (commits_bitmap[i]); + +free (pseudo_merge_ofs); +free (commits_bitmap); +} +static int table_cmp (const void *_va,const void *_vb,void *_data) {struct bitmap_writer *writer = _data;
@@ -878,6 +1003,9 @@ void bitmap_writer_finish(struct bitmap_writer *writer,int fd =odb_mkstemp (&tmp_file,"pack/tmp_bitmap_XXXXXX" ); +if (writer->pseudo_merges_nr) + options |=BITMAP_OPT_PSEUDO_MERGES ; + f =hashfd (fd, tmp_file.buf);memcpy (header.magic,BITMAP_IDX_SIGNATURE ,sizeof (BITMAP_IDX_SIGNATURE ));
@@ -907,6 +1035,9 @@ void bitmap_writer_finish(struct bitmap_writer *writer,write_selected_commits_v1 (writer, f, offsets); +if (options &BITMAP_OPT_PSEUDO_MERGES ) +write_pseudo_merges (writer, f); +if (options &BITMAP_OPT_LOOKUP_TABLE )write_lookup_table (writer, f, offsets);
pack-bitmap.h +1 -0
@@ -37,6 +37,7 @@ enum pack_bitmap_opts {BITMAP_OPT_FULL_DAG =0x1 ,BITMAP_OPT_HASH_CACHE =0x4 ,BITMAP_OPT_LOOKUP_TABLE =0x10 , + BITMAP_OPT_PSEUDO_MERGES = 0x20, }; enum pack_bitmap_flags {
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 13/24 pack-bitmap: extract `read_bitmap()` function
In reply to Taylor BlauThe pack-bitmap machinery uses the read_bitmap_1() function to read a bitmap from within the mmap'd region corresponding to the .bitmap file. As as side-effect of calling this function, read_bitmap_1() increments the index->map_pos variable to reflect the number of bytes read.
Extract the core of this routine to a separate function (that operates over a const unsigned char *, a size_t and a size_t * pointer) instead of a struct bitmap_index * pointer.
This function (called read_bitmap()) is part of the pack-bitmap.h API so that it can be used within the upcoming portion of the implementation in pseduo-merge.ch.
Rewrite the existing function, read_bitmap_1(), in terms of its more generic counterpart.
--- pack-bitmap.c | 24 +++++++++++++++--------- pack-bitmap.h | 2 ++ 2 files changed, 17 insertions(+), 9 deletions(-)
pack-bitmap.c +15 -9
@@ -129,17 +129,13 @@ static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)return composed; } -/* -* Read a bitmap from the current read position on the mmaped -* index, and increase the read position accordingly -*/ -static struct ewah_bitmap *read_bitmap_1 (struct bitmap_index *index) +struct ewah_bitmap *read_bitmap (const unsigned char *map, +size_t map_size,size_t *map_pos) {struct ewah_bitmap *b =ewah_pool_new (); -ssize_t bitmap_size =ewah_read_mmap (b, - index->map + index->map_pos, - index->map_size - index->map_pos); +ssize_t bitmap_size =ewah_read_mmap (b, map + *map_pos, + map_size - *map_pos);if (bitmap_size <0 ) {error (_ ("failed to load bitmap index (corrupted?)" ));
@@ -147,10 +143,20 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)return NULL ; } - index->map_pos += bitmap_size; + *map_pos += bitmap_size; +return b; } +/* +* Read a bitmap from the current read position on the mmaped +* index, and increase the read position accordingly +*/ +static struct ewah_bitmap *read_bitmap_1 (struct bitmap_index *index) +{ +return read_bitmap (index->map, index->map_size, &index->map_pos); +} +static uint32_t bitmap_num_objects (struct bitmap_index *index) {if (index->midx)
pack-bitmap.h +2 -0
@@ -160,4 +160,6 @@ int bitmap_is_preferred_refname(struct repository *r, const char *refname);int verify_bitmap_files (struct repository *r); +struct ewah_bitmap *read_bitmap (const unsigned char *map, +size_t map_size,size_t *map_pos);#endif
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 14/24 pseudo-merge: scaffolding for reads
In reply to Taylor BlauImplement scaffolding within the new pseudo-merge compilation unit necessary to use the pseudo-merge API from within the pack-bitmap.c machinery.
The core of this scaffolding is two-fold:
- The pseudo_merge structure itself, which represents an individual pseudo-merge bitmap. It has fields for both bitmaps, as well as metadata about its position within the memory-mapped region, and a few extra bits indicating whether or not it is satisfied, and which bitmaps(s, if any) have been read, since they are initialized lazily.
- The pseudo_merge_map structure, which holds an array of pseudo_merges, as well as a pointer to the memory-mapped region containing the pseudo-merge serialization from within a .bitmap file.
Note that the bitmap_index structure is defined statically within the pack-bitmap.o compilation unit, so we can't take in a struct bitmap_index *. Instead, wrap the primary components necessary to read the pseudo-merges in this new structure to avoid exposing the implementation details of the bitmap_index structure.
--- pseudo-merge.c | 10 ++++++++ pseudo-merge.h | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 75 insertions(+)
pseudo-merge.c +10 -0
@@ -454,3 +454,13 @@ void select_pseudo_merges(struct bitmap_writer *writer,stop_progress (&progress); } + +void free_pseudo_merge_map (struct pseudo_merge_map *pm) +{ +uint32_t i; +for (i =0 ; i < pm->nr; i++) { +ewah_pool_free (pm->v[i].commits); +ewah_pool_free (pm->v[i].bitmap); + } +free (pm->v); +}
pseudo-merge.h +65 -0
69 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 15/24 pack-bitmap.c: read pseudo-merge extension
In reply to Taylor BlauNow that the scaffolding for reading the pseudo-merge extension has been laid, teach the pack-bitmap machinery to read the pseudo-merge extension when present.
Note that pseudo-merges themselves are not yet used during traversal, this step will be taken by a future commit.
In the meantime, read the table and initialize the pseudo_merge_map structure introduced by a previous commit. When the pseudo-merge extension is present, load_bitmap_header() performs basic sanity checks to make sure that the table is well-formed.
--- pack-bitmap.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)
pack-bitmap.c +39 -0
@@ -20,6 +20,7 @@#include "list-objects-filter-options.h" #include "midx.h" #include "config.h" +#include "pseudo-merge.h" /* * An entry on the bitmap index, representing the bitmap for a given
@@ -86,6 +87,9 @@ struct bitmap_index {*/ unsigned char *table_lookup; +/* This contains the pseudo-merge cache within 'map' (if found). */ +struct pseudo_merge_map pseudo_merges; +/* * Extended index. *
@@ -205,6 +209,41 @@ static int load_bitmap_header(struct bitmap_index *index) index->table_lookup = (void *)(index_end - table_size); index_end -= table_size; } + +if (flags &BITMAP_OPT_PSEUDO_MERGES ) { +unsigned char *pseudo_merge_ofs; +size_t table_size; +uint32_t i; + +if (sizeof (table_size) > index_end - index->map - header_size) +return error (_ ("corrupted bitmap index file (too short to fit pseudo-merge table header)" )); + + table_size =get_be64 (index_end -8 ); +if (table_size > index_end - index->map - header_size) +return error (_ ("corrupted bitmap index file (too short to fit pseudo-merge table)" )); + +if (git_env_bool ("GIT_TEST_USE_PSEUDO_MERGES" ,1 )) { +const unsigned char *ext = (index_end - table_size); + + index->pseudo_merges.map = index->map; + index->pseudo_merges.map_size = index->map_size; + index->pseudo_merges.commits = ext +get_be64 (index_end -16 ); + index->pseudo_merges.commits_nr =get_be32 (index_end -20 ); + index->pseudo_merges.nr =get_be32 (index_end -24 ); + +CALLOC_ARRAY (index->pseudo_merges.v, + index->pseudo_merges.nr); + + pseudo_merge_ofs = index_end -24 - + (index->pseudo_merges.nr *sizeof (uint64_t )); +for (i =0 ; i < index->pseudo_merges.nr; i++) { + index->pseudo_merges.v[i].at =get_be64 (pseudo_merge_ofs); + pseudo_merge_ofs +=sizeof (uint64_t ); + } + } + + index_end -= table_size; + } } index->entry_count =ntohl (header->entry_count);
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 16/24 pseudo-merge: implement support for reading pseudo-merge commits
In reply to Taylor BlauImplement the basic API for reading pseudo-merge bitmaps, which consists of four basic functions:
- pseudo_merge_bitmap()
- use_pseudo_merge()
- apply_pseudo_merges_for_commit()
- cascade_pseudo_merges()
These functions are all documented in pseudo-merge.h, but their rough descriptions are as follows:
- pseudo_merge_bitmap() reads and inflates the objects EWAH bitmap for a given pseudo-merge
- use_pseudo_merge() does the same as pseudo_merge_bitmap(), but on the commits EWAH bitmap, not the objects bitmap
- apply_pseudo_merges_for_commit() applies all satisfied pseudo-merge commits for a given result set, and cascades any yet-unsatisfied pseudo-merges if any were applied in the previous step
- cascade_pseudo_merges() applies all pseudo-merges which are satisfied but have not been previously applied, repeating this process until no more pseudo-merges can be applied
The core of the API is the latter two functions, which are responsible for applying pseudo-merges during the object traversal implemented in the pack-bitmap machinery.
The other two functions (pseudo_merge_bitmap(), and use_pseudo_merge()) are low-level ways to interact with the pseudo-merge machinery, which will be useful in future commits.
--- pseudo-merge.c | 235 +++++++++++++++++++++++++++++++++++++++++++++++++ pseudo-merge.h | 44 +++++++++ 2 files changed, 279 insertions(+)
pseudo-merge.c +235 -0
@@ -10,6 +10,7 @@#include "commit.h" #include "alloc.h" #include "progress.h" +#include "hex.h" #define DEFAULT_PSEUDO_MERGE_DECAY 1.0#define DEFAULT_PSEUDO_MERGE_MAX_MERGES 64
@@ -464,3 +465,237 @@ void free_pseudo_merge_map(struct pseudo_merge_map *pm) }free (pm->v); } + +struct pseudo_merge_commit_ext { +uint32_t nr; +const unsigned char *ptr; +}; + +static int pseudo_merge_ext_at (const struct pseudo_merge_map *pm, +struct pseudo_merge_commit_ext *ext,size_t at) +{ +if (at >= pm->map_size) +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 ); + +return 0 ; +} + +struct ewah_bitmap *pseudo_merge_bitmap (const struct pseudo_merge_map *pm, +struct pseudo_merge *merge) +{ +if (!merge->loaded_commits) +BUG ("cannot use unloaded pseudo-merge bitmap" ); + +if (!merge->loaded_bitmap) { +size_t at = merge->bitmap_at; + + merge->bitmap =read_bitmap (pm->map, pm->map_size, &at); + merge->loaded_bitmap =1 ; + } + +return merge->bitmap; +} + +struct pseudo_merge *use_pseudo_merge (const struct pseudo_merge_map *pm, +struct pseudo_merge *merge) +{ +if (!merge->loaded_commits) { +size_t pos = merge->at; + + merge->commits =read_bitmap (pm->map, pm->map_size, &pos); + merge->bitmap_at = pos; + merge->loaded_commits =1 ; + } +return merge; +} + +static struct pseudo_merge *pseudo_merge_at (const struct pseudo_merge_map *pm, +struct object_id *oid, +size_t want) +{ +size_t lo =0 ; +size_t hi = pm->nr; + +while (lo < hi) { +size_t mi = lo + (hi - lo) /2 ; +size_t got = pm->v[mi].at; + +if (got == want) +return use_pseudo_merge (pm, &pm->v[mi]); +else if (got < want) + hi = mi; +else + lo = mi +1 ; + } + +warning (_ ("could not find pseudo-merge for commit %s at offset %" PRIuMAX), +oid_to_hex (oid), (uintmax_t )want); + +return NULL ; +} + +struct pseudo_merge_commit { +uint32_t commit_pos; +uint64_t pseudo_merge_ofs; +}; + +#define PSEUDO_MERGE_COMMIT_RAWSZ (sizeof(uint32_t)+sizeof(uint64_t)) + +static void read_pseudo_merge_commit_at (struct pseudo_merge_commit *merge, +const unsigned char *at) +{ + merge->commit_pos =get_be32 (at); + merge->pseudo_merge_ofs =get_be64 (at +sizeof (uint32_t )); +} + +static int nth_pseudo_merge_ext (const struct pseudo_merge_map *pm, +struct pseudo_merge_commit_ext *ext, +struct pseudo_merge_commit *merge, +uint32_t n) +{ +size_t ofs; + +if (n >= ext->nr) +return error (_ ("extended pseudo-merge lookup out-of-bounds " +"(%" PRIu32" >= %" PRIu32")" ), n, ext->nr); + + ofs =get_be64 (ext->ptr +st_mult (n,sizeof (uint64_t ))); +if (ofs >= pm->map_size) +return error (_ ("out-of-bounds read: (%" PRIuMAX" >= %" PRIuMAX")" ), + (uintmax_t )ofs, (uintmax_t )pm->map_size); + +read_pseudo_merge_commit_at (merge, pm->map + ofs); + +return 0 ; +} + +static unsigned apply_pseudo_merge (const struct pseudo_merge_map *pm, +struct pseudo_merge *merge, +struct bitmap *result, +struct bitmap *roots) +{ +if (merge->satisfied) +return 0 ; + +if (!ewah_bitmap_is_subset (merge->commits, roots ? roots : result)) +return 0 ; + +bitmap_or_ewah (result,pseudo_merge_bitmap (pm, merge)); +if (roots) +bitmap_or_ewah (roots,pseudo_merge_bitmap (pm, merge)); + merge->satisfied =1 ; + +return 1 ; +} + +static int pseudo_merge_commit_cmp (const void *va,const void *vb) +{ +struct pseudo_merge_commit merge; +uint32_t key = *(uint32_t *)va; + +read_pseudo_merge_commit_at (&merge, vb); + +if (key < merge.commit_pos) +return -1 ; +if (key > merge.commit_pos) +return 1 ; +return 0 ; +} + +static struct pseudo_merge_commit *find_pseudo_merge (const struct pseudo_merge_map *pm, +uint32_t pos) +{ +if (!pm->commits_nr) +return NULL ; + +return bsearch (&pos, pm->commits, pm->commits_nr, +PSEUDO_MERGE_COMMIT_RAWSZ , pseudo_merge_commit_cmp); +} + +int apply_pseudo_merges_for_commit (const struct pseudo_merge_map *pm, +struct bitmap *result, +struct commit *commit,uint32_t commit_pos) +{ +struct pseudo_merge *merge; +struct pseudo_merge_commit *merge_commit; +int ret =0 ; + + merge_commit =find_pseudo_merge (pm, commit_pos); +if (!merge_commit) +return 0 ; + +if (merge_commit->pseudo_merge_ofs & ((uint64_t )1 <<63 )) { +struct pseudo_merge_commit_ext ext = {0 }; +off_t ofs = merge_commit->pseudo_merge_ofs & ~((uint64_t )1 <<63 ); +uint32_t i; + +if (pseudo_merge_ext_at (pm, &ext, ofs) <-1 ) { +warning (_ ("could not read extended pseudo-merge table " +"for commit %s" ), +oid_to_hex (&commit->object.oid)); +return ret; + } + +for (i =0 ; i < ext.nr; i++) { +if (nth_pseudo_merge_ext (pm, &ext, merge_commit, i) <0 ) +return ret; + + merge =pseudo_merge_at (pm, &commit->object.oid, + merge_commit->pseudo_merge_ofs); + +if (!merge) +return ret; + +if (apply_pseudo_merge (pm, merge, result,NULL )) + ret++; + } + }else { + merge =pseudo_merge_at (pm, &commit->object.oid, + merge_commit->pseudo_merge_ofs); + +if (!merge) +return ret; + +if (apply_pseudo_merge (pm, merge, result,NULL )) + ret++; + } + +if (ret) +cascade_pseudo_merges (pm, result,NULL ); + +return ret; +} + +int cascade_pseudo_merges (const struct pseudo_merge_map *pm, +struct bitmap *result, +struct bitmap *roots) +{ +unsigned any_satisfied; +int ret =0 ; + +do { +struct pseudo_merge *merge; +uint32_t i; + + any_satisfied =0 ; + +for (i =0 ; i < pm->nr; i++) { + merge =use_pseudo_merge (pm, &pm->v[i]); +if (apply_pseudo_merge (pm, merge, result, roots)) { + any_satisfied |=1 ; + ret++; + } + } + }while (any_satisfied); + +return ret; +}
pseudo-merge.h +44 -0
48 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 17/24 ewah: implement `ewah_bitmap_popcount()`
In reply to Taylor BlauSome of the pseudo-merge test helpers (which will be introduced in the following commit) will want to indicate the total number of commits in or objects reachable from a pseudo-merge.
Implement a popcount() function that operates on EWAH bitmaps to quickly determine how many bits are set in each of the respective bitmaps.
--- ewah/bitmap.c | 14 ++++++++++++++ ewah/ewok.h | 1 + 2 files changed, 15 insertions(+)
ewah/bitmap.c +14 -0
@@ -212,6 +212,20 @@ size_t bitmap_popcount(struct bitmap *self)return count; } +size_t ewah_bitmap_popcount (struct ewah_bitmap *self) +{ +struct ewah_iterator it; +eword_t word; +size_t count =0 ; + +ewah_iterator_init (&it, self); + +while (ewah_iterator_next (&word, &it)) + count +=ewah_bit_popcount64 (word); + +return count; +} +int bitmap_is_empty (struct bitmap *self) {size_t i;
ewah/ewok.h +1 -0
@@ -195,6 +195,7 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other);void bitmap_or (struct bitmap *self,const struct bitmap *other);size_t bitmap_popcount (struct bitmap *self); +size_t ewah_bitmap_popcount (struct ewah_bitmap *self);int bitmap_is_empty (struct bitmap *self);#endif
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 18/24 pack-bitmap: implement test helpers for pseudo-merge
In reply to Taylor BlauImplement three new sub-commands for the "bitmap" test-helper:
- t/helper test-tool bitmap dump-pseudo-merges
- t/helper test-tool bitmap dump-pseudo-merge-commits <n>
- t/helper test-tool bitmap dump-pseudo-merge-objects <n>
These three helpers dump the list of pseudo merges, the "parents" of the nth pseudo-merges, and the set of objects reachable from those parents, respectively.
These helpers will be useful in subsequent patches when we add test coverage for pseudo-merge bitmaps.
--- pack-bitmap.c | 126 +++++++++++++++++++++++++++++++++++++++++ pack-bitmap.h | 3 + t/helper/test-bitmap.c | 34 ++++++++--- 3 files changed, 156 insertions(+), 7 deletions(-)
pack-bitmap.c +126 -0
@@ -2443,6 +2443,132 @@ int test_bitmap_hashes(struct repository *r)return 0 ; } +static void bit_pos_to_object_id (struct bitmap_index *bitmap_git, +uint32_t bit_pos, +struct object_id *oid) +{ +uint32_t index_pos; + +if (bitmap_is_midx (bitmap_git)) + index_pos =pack_pos_to_midx (bitmap_git->midx, bit_pos); +else + index_pos =pack_pos_to_index (bitmap_git->pack, bit_pos); + +nth_bitmap_object_oid (bitmap_git, oid, index_pos); +} + +int test_bitmap_pseudo_merges (struct repository *r) +{ +struct bitmap_index *bitmap_git; +uint32_t i; + + bitmap_git =prepare_bitmap_git (r); +if (!bitmap_git || !bitmap_git->pseudo_merges.nr) + goto cleanup; + +for (i =0 ; i < bitmap_git->pseudo_merges.nr; i++) { +struct pseudo_merge *merge; +struct ewah_bitmap *commits_bitmap, *merge_bitmap; + + merge =use_pseudo_merge (&bitmap_git->pseudo_merges, + &bitmap_git->pseudo_merges.v[i]); + commits_bitmap = merge->commits; + merge_bitmap =pseudo_merge_bitmap (&bitmap_git->pseudo_merges, + merge); + +printf ("at=%" PRIuMAX", commits=%" PRIuMAX", objects=%" PRIuMAX"\n" , + (uintmax_t )merge->at, + (uintmax_t )ewah_bitmap_popcount (commits_bitmap), + (uintmax_t )ewah_bitmap_popcount (merge_bitmap)); + } + +cleanup: +free_bitmap_index (bitmap_git); +return 0 ; +} + +static void dump_ewah_object_ids (struct bitmap_index *bitmap_git, +struct ewah_bitmap *bitmap) + +{ +struct ewah_iterator it; +eword_t word; +uint32_t pos =0 ; + +ewah_iterator_init (&it, bitmap); + +while (ewah_iterator_next (&word, &it)) { +struct object_id oid; +uint32_t offset; + +for (offset =0 ; offset <BITS_IN_EWORD ; offset++) { +if (!(word >> offset)) +break ; + + offset +=ewah_bit_ctz64 (word >> offset); + +bit_pos_to_object_id (bitmap_git, pos + offset, &oid); +printf ("%s\n" ,oid_to_hex (&oid)); + } + pos +=BITS_IN_EWORD ; + } +} + +int test_bitmap_pseudo_merge_commits (struct repository *r,uint32_t n) +{ +struct bitmap_index *bitmap_git; +struct pseudo_merge *merge; +int ret =0 ; + + bitmap_git =prepare_bitmap_git (r); +if (!bitmap_git || !bitmap_git->pseudo_merges.nr) + goto cleanup; + +if (n >= bitmap_git->pseudo_merges.nr) { + ret =error (_ ("pseudo-merge index out of range " +"(%" PRIu32" >= %" PRIuMAX")" ), + n, (uintmax_t )bitmap_git->pseudo_merges.nr); + goto cleanup; + } + + merge =use_pseudo_merge (&bitmap_git->pseudo_merges, + &bitmap_git->pseudo_merges.v[n]); +dump_ewah_object_ids (bitmap_git, merge->commits); + +cleanup: +free_bitmap_index (bitmap_git); +return ret; +} + +int test_bitmap_pseudo_merge_objects (struct repository *r,uint32_t n) +{ +struct bitmap_index *bitmap_git; +struct pseudo_merge *merge; +int ret =0 ; + + bitmap_git =prepare_bitmap_git (r); +if (!bitmap_git || !bitmap_git->pseudo_merges.nr) + goto cleanup; + +if (n >= bitmap_git->pseudo_merges.nr) { + ret =error (_ ("pseudo-merge index out of range " +"(%" PRIu32" >= %" PRIuMAX")" ), + n, (uintmax_t )bitmap_git->pseudo_merges.nr); + goto cleanup; + } + + merge =use_pseudo_merge (&bitmap_git->pseudo_merges, + &bitmap_git->pseudo_merges.v[n]); + +dump_ewah_object_ids (bitmap_git, +pseudo_merge_bitmap (&bitmap_git->pseudo_merges, + merge)); + +cleanup: +free_bitmap_index (bitmap_git); +return ret; +} +int rebuild_bitmap (const uint32_t *reposition,struct ewah_bitmap *source,struct bitmap *dest)
pack-bitmap.h +3 -0
@@ -73,6 +73,9 @@ void traverse_bitmap_commit_list(struct bitmap_index *,void test_bitmap_walk (struct rev_info *revs);int test_bitmap_commits (struct repository *r);int test_bitmap_hashes (struct repository *r); +int test_bitmap_pseudo_merges (struct repository *r); +int test_bitmap_pseudo_merge_commits (struct repository *r,uint32_t n); +int test_bitmap_pseudo_merge_objects (struct repository *r,uint32_t n);#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \ "GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL"
t/helper/test-bitmap.c +27 -7
@@ -13,21 +13,41 @@ static int bitmap_dump_hashes(void)return test_bitmap_hashes (the_repository); } +static int bitmap_dump_pseudo_merges (void ) +{ +return test_bitmap_pseudo_merges (the_repository); +} + +static int bitmap_dump_pseudo_merge_commits (uint32_t n) +{ +return test_bitmap_pseudo_merge_commits (the_repository, n); +} + +static int bitmap_dump_pseudo_merge_objects (uint32_t n) +{ +return test_bitmap_pseudo_merge_objects (the_repository, n); +} +int cmd__bitmap (int argc,const char **argv) {setup_git_directory (); -if (argc !=2 ) - goto usage; - -if (!strcmp (argv[1 ],"list-commits" )) +if (argc ==2 && !strcmp (argv[1 ],"list-commits" ))return bitmap_list_commits (); -if (!strcmp (argv[1 ],"dump-hashes" )) +if (argc ==2 && !strcmp (argv[1 ],"dump-hashes" ))return bitmap_dump_hashes (); +if (argc ==2 && !strcmp (argv[1 ],"dump-pseudo-merges" )) +return bitmap_dump_pseudo_merges (); +if (argc ==3 && !strcmp (argv[1 ],"dump-pseudo-merge-commits" )) +return bitmap_dump_pseudo_merge_commits (atoi (argv[2 ])); +if (argc ==3 && !strcmp (argv[1 ],"dump-pseudo-merge-objects" )) +return bitmap_dump_pseudo_merge_objects (atoi (argv[2 ])); -usage:usage ("\ttest-tool bitmap list-commits\n" -"\ttest-tool bitmap dump-hashes" ); +"\ttest-tool bitmap dump-hashes\n" +"\ttest-tool bitmap dump-pseudo-merges\n" +"\ttest-tool bitmap dump-pseudo-merge-commits <n>\n" +"\ttest-tool bitmap dump-pseudo-merge-objects <n>" );return -1 ; }
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 19/24 t/test-lib-functions.sh: support `--notick` in `test_commit_bulk()`
In reply to Taylor BlauOne 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 --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.
--- t/test-lib-functions.sh | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-)
t/test-lib-functions.sh +8 -1
@@ -458,6 +458,7 @@ test_commit_bulk () { indir=. ref=HEAD n=1 + notick= message='commit %s' filename='%s.t' contents='content %s'
@@ -488,6 +489,9 @@ test_commit_bulk () { filename="${1#--*=}-%s.t" contents="${1#--*=} %s" ;; + --notick) + notick=yes + ;; -*) BUG "invalid test_commit_bulk option: $1" ;;
@@ -507,7 +511,10 @@ test_commit_bulk () { while test "$total" -gt 0 do - test_tick && + if test -z "$notick" + then + test_tick + fi && echo "commit $ref" printf 'author %s <%s> %s\n' \ "$GIT_AUTHOR_NAME" \
Signature · 1 line
2.45.1.175.gcf0316ad0e9
Re: [PATCH v4 19/24] t/test-lib-functions.sh: support `--notick` in `test_commit_bulk()`
Quoted 7 lines · Taylor Blau
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
--notickoption (with identical semantics to the--notickoption fortest_commit()) withintest_commit_bulkas a prerequisite for that. Callers can then set the various_DATEvariables themselves.
Looks good. I expected to see you add "--date" _also_, but it looks like you just set $GIT_COMMITTER_DATE yourself. Which I think is fine for our purposes here.
-Peff
PATCH v4 20/24 pack-bitmap.c: use pseudo-merges during traversal
In reply to Taylor BlauNow that all of the groundwork has been laid to support reading and using pseudo-merges, make use of that work in this commit by teaching the pack-bitmap machinery to use pseudo-merge(s) when available during traversal.
The basic operation is as follows:
- When enumerating objects on either side of a reachability query, first see if any subset of the roots satisfies some pseudo-merge bitmap. If it does, apply that pseudo-merge bitmap.
- If any pseudo-merge bitmap(s) were applied in the previous step, OR them into the result[^1]. Then repeat the process over all pseudo-merge bitmaps (we'll refer to this as "cascading" pseudo-merges). Once this is done, OR in the resulting bitmap.
- If there is no fill-in traversal to be done, return the bitmap for that side of the reachability query. If there is fill-in traversal, then for each commit we encounter via show_commit(), check to see if any unsatisfied pseudo-merges containing that commit as one of its parents has been made satisfied by the presence of that commit.
If so, OR in the object set from that pseudo-merge bitmap, and then cascade. If not, continue traversal.
A similar implementation is present in the boundary-based bitmap traversal routines.
[^1]: Importantly, we cannot OR in the entire set of roots along with
the objects reachable from whatever pseudo-merge bitmaps were satisfied. This may leave some dangling bits corresponding to any unsatisfied root(s) getting OR'd into the resulting bitmap, tricking other parts of the traversal into thinking we already have a reachability closure over those commit(s) when we do not.
--- pack-bitmap.c | 112 ++++++++++- t/t5333-pseudo-merge-bitmaps.sh | 328 ++++++++++++++++++++++++++++++++ 2 files changed, 439 insertions(+), 1 deletion(-) create mode 100755 t/t5333-pseudo-merge-bitmaps.sh
pack-bitmap.c +111 -1
@@ -114,6 +114,9 @@ struct bitmap_index {unsigned int version; }; +static int pseudo_merges_satisfied_nr; +static int pseudo_merges_cascades_nr; +static struct ewah_bitmap *lookup_stored_bitmap (struct stored_bitmap *st) {struct ewah_bitmap *parent;
@@ -1006,6 +1009,22 @@ static void show_commit(struct commit *commit UNUSED, { } +static unsigned apply_pseudo_merges_for_commit_1 (struct bitmap_index *bitmap_git, +struct bitmap *result, +struct commit *commit, +uint32_t commit_pos) +{ +int ret; + + ret =apply_pseudo_merges_for_commit (&bitmap_git->pseudo_merges, + result, commit, commit_pos); + +if (ret) + pseudo_merges_satisfied_nr += ret; + +return ret; +} + static int add_to_include_set(struct bitmap_index *bitmap_git, struct include_data *data, struct commit *commit,
@@ -1026,6 +1045,10 @@ static int add_to_include_set(struct bitmap_index *bitmap_git, }bitmap_set (data->base, bitmap_pos); +if (apply_pseudo_merges_for_commit_1 (bitmap_git, data->base, commit, + bitmap_pos)) +return 0 ; +return 1 ; }
@@ -1151,6 +1174,20 @@ static void show_boundary_object(struct object *object UNUSED,BUG ("should not be called" ); } +static unsigned cascade_pseudo_merges_1 (struct bitmap_index *bitmap_git, +struct bitmap *result, +struct bitmap *roots) +{ +int ret =cascade_pseudo_merges (&bitmap_git->pseudo_merges, + result, roots); +if (ret) { + pseudo_merges_cascades_nr++; + pseudo_merges_satisfied_nr += ret; + } + +return ret; +} +static struct bitmap *find_boundary_objects (struct bitmap_index *bitmap_git,struct rev_info *revs,struct object_list *roots)
@@ -1160,6 +1197,7 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,unsigned int i;unsigned int tmp_blobs, tmp_trees, tmp_tags;int any_missing =0 ; +int existing_bitmaps =0 ; cb.bitmap_git = bitmap_git; cb.base =bitmap_new ();
@@ -1167,6 +1205,25 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, revs->ignore_missing_links =1 ; +if (bitmap_git->pseudo_merges.nr) { +struct bitmap *roots_bitmap =bitmap_new (); +struct object_list *objects =NULL ; + +for (objects = roots; objects; objects = objects->next) { +struct object *object = objects->item; +int pos; + + pos =bitmap_position (bitmap_git, &object->oid); +if (pos <0 ) +continue ; + +bitmap_set (roots_bitmap, pos); + } + +if (!cascade_pseudo_merges_1 (bitmap_git, cb.base, roots_bitmap)) +bitmap_free (roots_bitmap); + } +/* * OR in any existing reachability bitmaps among `roots` into * `cb.base`.
@@ -1178,8 +1235,10 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,continue ;if (add_commit_to_bitmap (bitmap_git, &cb.base, - (struct commit *)object)) + (struct commit *)object)) { + existing_bitmaps =1 ;continue ; + } any_missing =1 ; }
@@ -1187,6 +1246,9 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,if (!any_missing) goto cleanup; +if (existing_bitmaps) +cascade_pseudo_merges_1 (bitmap_git, cb.base,NULL ); + tmp_blobs = revs->blob_objects; tmp_trees = revs->tree_objects; tmp_tags = revs->blob_objects;
@@ -1242,6 +1304,13 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,return cb.base; } +static void unsatisfy_all_pseudo_merges (struct bitmap_index *bitmap_git) +{ +uint32_t i; +for (i =0 ; i < bitmap_git->pseudo_merges.nr; i++) + bitmap_git->pseudo_merges.v[i].satisfied =0 ; +} + static struct bitmap *find_objects(struct bitmap_index *bitmap_git, struct rev_info *revs, struct object_list *roots,
@@ -1249,9 +1318,32 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, {struct bitmap *base =NULL ;int needs_walk =0 ; +unsigned existing_bitmaps =0 ;struct object_list *not_mapped =NULL ; +unsatisfy_all_pseudo_merges (bitmap_git); + +if (bitmap_git->pseudo_merges.nr) { +struct bitmap *roots_bitmap =bitmap_new (); +struct object_list *objects =NULL ; + +for (objects = roots; objects; objects = objects->next) { +struct object *object = objects->item; +int pos; + + pos =bitmap_position (bitmap_git, &object->oid); +if (pos <0 ) +continue ; + +bitmap_set (roots_bitmap, pos); + } + + base =bitmap_new (); +if (!cascade_pseudo_merges_1 (bitmap_git, base, roots_bitmap)) +bitmap_free (roots_bitmap); + } +/* * Go through all the roots for the walk. The ones that have bitmaps * on the bitmap index will be `or`ed together to form an initial
@@ -1262,11 +1354,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,*/ while (roots) {struct object *object = roots->item; + roots = roots->next; +if (base) { +int pos =bitmap_position (bitmap_git, &object->oid); +if (pos >0 &&bitmap_get (base, pos)) { + object->flags |=SEEN ; +continue ; + } + } +if (object->type ==OBJ_COMMIT &&add_commit_to_bitmap (bitmap_git, &base, (struct commit *)object)) { object->flags |=SEEN ; + existing_bitmaps =1 ;continue ; }
@@ -1282,6 +1384,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, roots = not_mapped; +if (existing_bitmaps) +cascade_pseudo_merges_1 (bitmap_git, base,NULL ); +/* * Let's iterate through all the roots that don't have bitmaps to * check if we can determine them to be reachable from the existing
@@ -1866,6 +1971,11 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,object_list_free (&wants);object_list_free (&haves); +trace2_data_intmax ("bitmap" , the_repository,"pseudo_merges_satisfied" , + pseudo_merges_satisfied_nr); +trace2_data_intmax ("bitmap" , the_repository,"pseudo_merges_cascades" , + pseudo_merges_cascades_nr); +return bitmap_git; cleanup:
t/t5333-pseudo-merge-bitmaps.sh new file +328 -0
328 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 21/24 pack-bitmap: extra trace2 information
In reply to Taylor BlauAdd some extra trace2 lines to capture the number of bitmap lookups that are hits versus misses, as well as the number of reachability roots that have bitmap coverage (versus those that do not).
--- pack-bitmap.c | 26 +++++++++++++++++++++++++- 1 file changed, 25 insertions(+), 1 deletion(-)
pack-bitmap.c +25 -1
@@ -116,6 +116,10 @@ struct bitmap_index {static int pseudo_merges_satisfied_nr;static int pseudo_merges_cascades_nr; +static int existing_bitmaps_hits_nr; +static int existing_bitmaps_misses_nr; +static int roots_with_bitmaps_nr; +static int roots_without_bitmaps_nr;static struct ewah_bitmap *lookup_stored_bitmap (struct stored_bitmap *st) {
@@ -1040,10 +1044,14 @@ static int add_to_include_set(struct bitmap_index *bitmap_git, partial =bitmap_for_commit (bitmap_git, commit);if (partial) { + existing_bitmaps_hits_nr++; +bitmap_or_ewah (data->base, partial);return 0 ; } + existing_bitmaps_misses_nr++; +bitmap_set (data->base, bitmap_pos);if (apply_pseudo_merges_for_commit_1 (bitmap_git, data->base, commit, bitmap_pos))
@@ -1099,8 +1107,12 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git, {struct ewah_bitmap *or_with =bitmap_for_commit (bitmap_git, commit); -if (!or_with) +if (!or_with) { + existing_bitmaps_misses_nr++;return 0 ; + } + + existing_bitmaps_hits_nr++;if (!*base) *base =ewah_to_bitmap (or_with);
@@ -1407,8 +1419,12 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, object->flags &= ~UNINTERESTING ;add_pending_object (revs, object,"" ); needs_walk =1 ; + + roots_without_bitmaps_nr++; }else { object->flags |=SEEN ; + + roots_with_bitmaps_nr++; } }
@@ -1975,6 +1991,14 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, pseudo_merges_satisfied_nr);trace2_data_intmax ("bitmap" , the_repository,"pseudo_merges_cascades" , pseudo_merges_cascades_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/hits" , + existing_bitmaps_hits_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/misses" , + existing_bitmaps_misses_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/roots_with_bitmap" , + roots_with_bitmaps_nr); +trace2_data_intmax ("bitmap" , the_repository,"bitmap/roots_without_bitmap" , + roots_without_bitmaps_nr);return bitmap_git;
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 22/24 ewah: `bitmap_equals_ewah()`
In reply to Taylor BlauPrepare to reuse existing pseudo-merge bitmaps by implementing a bitmap_equals_ewah() helper.
This helper will be used to see if a raw bitmap (containing the set of parents for some pseudo-merge) is equal to any existing pseudo-merge's commits bitmap (which are stored as EWAH-compressed bitmaps on disk).
--- ewah/bitmap.c | 19 +++++++++++++++++++ ewah/ewok.h | 1 + 2 files changed, 20 insertions(+)
ewah/bitmap.c +19 -0
@@ -261,6 +261,25 @@ int bitmap_equals(struct bitmap *self, struct bitmap *other)return 1 ; } +int bitmap_equals_ewah (struct bitmap *self,struct ewah_bitmap *other) +{ +struct ewah_iterator it; +eword_t word; +size_t i =0 ; + +ewah_iterator_init (&it, other); + +while (ewah_iterator_next (&word, &it)) +if (word != (i < self->word_alloc ? self->words[i++] :0 )) +return 0 ; + +for (; i < self->word_alloc; i++) +if (self->words[i]) +return 0 ; + +return 1 ; +} +int bitmap_is_subset (struct bitmap *self,struct bitmap *other) {size_t common_size, i;
ewah/ewok.h +1 -0
@@ -179,6 +179,7 @@ void bitmap_unset(struct bitmap *self, size_t pos);int bitmap_get (struct bitmap *self,size_t pos);void bitmap_free (struct bitmap *self);int bitmap_equals (struct bitmap *self,struct bitmap *other); +int bitmap_equals_ewah (struct bitmap *self,struct ewah_bitmap *other);/* * Both `bitmap_is_subset()` and `ewah_bitmap_is_subset()` return 1 if the set
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 23/24 pseudo-merge: implement support for finding existing merges
In reply to Taylor BlauThis patch implements support for reusing existing pseudo-merge commits when writing bitmaps when there is an existing pseudo-merge bitmap which has exactly the same set of parents as one that we are about to write.
Note that unstable pseudo-merges are likely to change between consecutive repacks, and so are generally poor candidates for reuse. However, stable pseudo-merges (see the configuration option 'bitmapPseudoMerge.<name>.stableThreshold') are by definition unlikely to change between runs (as they represent long-running branches).
Because there is no index from a *set* of pseudo-merge parents to a matching pseudo-merge bitmap, we have to construct the bitmap corresponding to the set of parents for each pending pseudo-merge commit and see if a matching bitmap exists.
This is technically quadratic in the number of pseudo-merges, but is OK in practice for a couple of reasons:
- non-matching pseudo-merge bitmaps are rejected quickly as soon as they differ in a single bit
- already-matched pseudo-merge bitmaps are discarded from subsequent rounds of search
- the number of pseudo-merges is generally small, even for large repositories
In order to do this, implement (a) a function that finds a matching pseudo-merge given some uncompressed bitset describing its parents, (b) a function that computes the bitset of parents for a given pseudo-merge commit, and (c) call that function before computing the set of reachable objects for some pending pseudo-merge.
--- pack-bitmap-write.c | 15 +++++++- pack-bitmap.c | 32 ++++++++++++++++ pack-bitmap.h | 2 + pseudo-merge.c | 55 ++++++++++++++++++++++++++++ pseudo-merge.h | 7 ++++ t/t5333-pseudo-merge-bitmaps.sh | 65 +++++++++++++++++++++++++++++++++ 6 files changed, 174 insertions(+), 2 deletions(-)
pack-bitmap-write.c +13 -2
@@ -19,6 +19,10 @@#include "tree-walk.h" #include "pseudo-merge.h" #include "oid-array.h" +#include "config.h" +#include "alloc.h" +#include "refs.h" +#include "strmap.h" struct bitmapped_commit {struct commit *commit;
@@ -465,6 +469,7 @@ static int fill_bitmap_tree(struct bitmap_writer *writer, }static int reused_bitmaps_nr; +static int reused_pseudo_merge_bitmaps_nr; static int fill_bitmap_commit(struct bitmap_writer *writer, struct bb_commit *ent,
@@ -490,7 +495,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,struct bitmap *remapped =bitmap_new ();if (commit->object.flags &BITMAP_PSEUDO_MERGE ) - old =NULL ; + old =pseudo_merge_bitmap_for_commit (old_bitmap, c);else old =bitmap_for_commit (old_bitmap, c);/*
@@ -501,7 +506,10 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,if (old && !rebuild_bitmap (mapping, old, remapped)) {bitmap_or (ent->bitmap, remapped);bitmap_free (remapped); - reused_bitmaps_nr++; +if (commit->object.flags &BITMAP_PSEUDO_MERGE ) + reused_pseudo_merge_bitmaps_nr++; +else + reused_bitmaps_nr++;continue ; }bitmap_free (remapped);
@@ -631,6 +639,9 @@ int bitmap_writer_build(struct bitmap_writer *writer, the_repository);trace2_data_intmax ("pack-bitmap-write" , the_repository,"building_bitmaps_reused" , reused_bitmaps_nr); +trace2_data_intmax ("pack-bitmap-write" , the_repository, +"building_bitmaps_pseudo_merge_reused" , + reused_pseudo_merge_bitmaps_nr);stop_progress (&writer->progress);
pack-bitmap.c +32 -0
@@ -1316,6 +1316,37 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,return cb.base; } +struct ewah_bitmap *pseudo_merge_bitmap_for_commit (struct bitmap_index *bitmap_git, +struct commit *commit) +{ +struct commit_list *p; +struct bitmap *parents; +struct pseudo_merge *match =NULL ; + +if (!bitmap_git->pseudo_merges.nr) +return NULL ; + + parents =bitmap_new (); + +for (p = commit->parents; p; p = p->next) { +int pos =bitmap_position (bitmap_git, &p->item->object.oid); +if (pos <0 || pos >=bitmap_num_objects (bitmap_git)) + goto done; + +bitmap_set (parents, pos); + } + + match =pseudo_merge_for_parents (&bitmap_git->pseudo_merges, + parents); + +done: +bitmap_free (parents); +if (match) +return pseudo_merge_bitmap (&bitmap_git->pseudo_merges, match); + +return NULL ; +} +static void unsatisfy_all_pseudo_merges (struct bitmap_index *bitmap_git) {uint32_t i;
@@ -2809,6 +2840,7 @@ void free_bitmap_index(struct bitmap_index *b)*/ close_midx_revindex (b->midx); } +free_pseudo_merge_map (&b->pseudo_merges);free (b); }
pack-bitmap.h +2 -0
@@ -142,6 +142,8 @@ int rebuild_bitmap(const uint32_t *reposition, struct bitmap *dest);struct ewah_bitmap *bitmap_for_commit (struct bitmap_index *bitmap_git,struct commit *commit); +struct ewah_bitmap *pseudo_merge_bitmap_for_commit (struct bitmap_index *bitmap_git, +struct commit *commit);void bitmap_writer_select_commits (struct bitmap_writer *writer,struct commit **indexed_commits,unsigned int indexed_commits_nr);
pseudo-merge.c +55 -0
58 lines not on this page · raw message
pseudo-merge.h +7 -0
@@ -206,4 +206,11 @@ int cascade_pseudo_merges(const struct pseudo_merge_map *pm,struct bitmap *result, struct bitmap *roots); +/* +* Returns a pseudo-merge which contains the exact set of commits +* listed in the "parents" bitamp, or NULL if none could be found. +*/ +struct pseudo_merge *pseudo_merge_for_parents (const struct pseudo_merge_map *pm, +struct bitmap *parents); +#endif
t/t5333-pseudo-merge-bitmaps.sh +65 -0
75 lines not on this page · raw message
Signature · 1 line
2.45.1.175.gcf0316ad0e9
PATCH v4 24/24 t/perf: implement performance tests for pseudo-merge bitmaps
In reply to Taylor BlauImplement a straightforward performance test demonstrating the benefit of pseudo-merge bitmaps by measuring how long it takes to count reachable objects in a few different scenarios:
- without bitmaps, to demonstrate a reasonable baseline
- with bitmaps, but without pseudo-merges
- with bitmaps and pseudo-merges
Results from running this test on git.git are as follows:
Test this tree
-----------------------------------------------------------------------------------
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)--- t/perf/p5333-pseudo-merge-bitmaps.sh | 32 ++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100755 t/perf/p5333-pseudo-merge-bitmaps.sh
t/perf/p5333-pseudo-merge-bitmaps.sh new file +32 -0
@@ -0,0 +1,32 @@ +#!/bin/sh + +test_description='pseudo-merge bitmaps' +. ./perf-lib.sh + +test_perf_large_repo + +test_expect_success 'setup' ' + git \ + -c bitmapPseudoMerge.all.pattern="refs/" \ + -c bitmapPseudoMerge.all.threshold=now \ + -c bitmapPseudoMerge.all.stableThreshold=never \ + -c bitmapPseudoMerge.all.maxMerges=64 \ + -c pack.writeBitmapLookupTable=true \ + repack -adb +' + +test_perf 'git rev-list --count --all --objects (no bitmaps)' ' + git rev-list --objects --all +' + +test_perf 'git rev-list --count --all --objects (no pseudo-merges)' ' + 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_PSEUDO_MERGES=1 \ + git rev-list --objects --all --use-bitmap-index +' + +test_done
Signature · 1 line
2.45.1.175.gcf0316ad0e9
Quoted 5 lines · Taylor Blau
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.
Thanks, this version looks good to me!
-Peff