[PATCH 23/23] pack-bitmap-write: better reuse bitmaps
- From
Taylor Blau <me@ttaylorr.com>
- Date
- Nov 11, 2020, 19:44 UTC
- Message-ID
- <35beb4f098991bb3886bbaf74f9d2fc5561bca42.1605123653.git.me@ttaylorr.com>
- In-Reply-To
- <cover.1605123652.git.me@ttaylorr.com>
From: Derrick Stolee <dstolee@microsoft.com>
If the old bitmap file contains a bitmap for a given commit, then that commit does not need help from intermediate commits in its history to compute its final bitmap. Eject that commit from the walk and insert it as a maximal commit in the list of commits for computing bitmaps.
This helps the repeat bitmap computation task, even if the selected commits shift drastically. This helps when a previously-bitmapped commit exists in the first-parent history of a newly-selected commit. Since we stop the walk at these commits and we use a first-parent walk, it is harder to walk "around" these bitmapped commits. It's not impossible, but we can greatly reduce the computation time for many selected commits.
| runtime (sec) | peak heap (GB) |
| | |
| from | with | from | with |
| scratch | existing | scratch | existing |
-----------+---------+----------+---------+-----------
last patch | 100.641 | 35.560 | 2.152 | 2.224 |
this patch | 99.720 | 11.696 | 2.152 | 2.217 |Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Taylor Blau <me@ttaylorr.com> --- pack-bitmap-write.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c index b0493d971d..3ac90ae410 100644 --- a/pack-bitmap-write.c +++ b/pack-bitmap-write.c @@ -195,7 +195,8 @@ struct bitmap_builder { }; static void bitmap_builder_init(struct bitmap_builder *bb, - struct bitmap_writer *writer) + struct bitmap_writer *writer, + struct bitmap_index *old_bitmap) { struct rev_info revs; struct commit *commit; @@ -234,12 +235,26 @@ static void bitmap_builder_init(struct bitmap_builder *bb, c_ent = bb_data_at(&bb->data, commit); + if (old_bitmap && bitmap_for_commit(old_bitmap, commit)) { + /* + * This commit has an existing bitmap, so we can + * get its bits immediately without an object + * walk. There is no need to continue walking + * beyond this commit. + */ + c_ent->maximal = 1; + p = NULL; + } + if (c_ent->maximal) { num_maximal++; ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc); bb->commits[bb->commits_nr++] = commit; } + if (!c_ent->commit_mask) + continue; + if (p) { struct bb_commit *p_ent = bb_data_at(&bb->data, p->item); int c_not_p, p_not_c; @@ -422,7 +437,7 @@ void bitmap_writer_build(struct packing_data *to_pack) else mapping = NULL; - bitmap_builder_init(&bb, &writer); + bitmap_builder_init(&bb, &writer, old_bitmap); for (i = bb.commits_nr; i > 0; i--) { struct commit *commit = bb.commits[i-1]; struct bb_commit *ent = bb_data_at(&bb.data, commit);
-- 2.29.2.156.gc03786897f