Taylor Blau <me@xxxxxxxxxxxx> writes:
> From: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
>
> The fill_bitmap_commit() method assumes that every parent of the given
> commit is already part of the current bitmap. Instead of making that
> assumption, let's walk parents until we reach commits already part of
> the bitmap. Set the value for that parent immediately after querying to
> save time doing double calls to find_object_pos() and to avoid inserting
> the parent into the queue multiple times.
Is it because somebody found a case where the assumption does not
hold and the code with the assumption produces a wrong result? Is
it because we can get a better result without making the assumption
the current code does?
In other words, can we explain why we are making the change in the
proposed log message?
> Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
> Signed-off-by: Taylor Blau <me@xxxxxxxxxxxx>
> ---
> pack-bitmap-write.c | 30 +++++++++++++++++++++++-------
> 1 file changed, 23 insertions(+), 7 deletions(-)
>
> diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
> index d2d46ff5f4..361f3305a2 100644
> --- a/pack-bitmap-write.c
> +++ b/pack-bitmap-write.c
> @@ -12,6 +12,7 @@
> #include "sha1-lookup.h"
> #include "pack-objects.h"
> #include "commit-reach.h"
> +#include "prio-queue.h"
>
> struct bitmapped_commit {
> struct commit *commit;
> @@ -279,17 +280,30 @@ static void fill_bitmap_tree(struct bitmap *bitmap,
> }
>
> static void fill_bitmap_commit(struct bb_commit *ent,
> - struct commit *commit)
> + struct commit *commit,
> + struct prio_queue *queue)
> {
> if (!ent->bitmap)
> ent->bitmap = bitmap_new();
>
> - /*
> - * mark ourselves, but do not bother with parents; their values
> - * will already have been propagated to us
> - */
> bitmap_set(ent->bitmap, find_object_pos(&commit->object.oid));
> - fill_bitmap_tree(ent->bitmap, get_commit_tree(commit));
> + prio_queue_put(queue, commit);
> +
> + while (queue->nr) {
> + struct commit_list *p;
> + struct commit *c = prio_queue_get(queue);
> +
> + bitmap_set(ent->bitmap, find_object_pos(&c->object.oid));
> + fill_bitmap_tree(ent->bitmap, get_commit_tree(c));
> +
> + for (p = c->parents; p; p = p->next) {
> + int pos = find_object_pos(&p->item->object.oid);
> + if (!bitmap_get(ent->bitmap, pos)) {
> + bitmap_set(ent->bitmap, pos);
> + prio_queue_put(queue, p->item);
> + }
> + }
> + }
> }
>
> static void store_selected(struct bb_commit *ent, struct commit *commit)
> @@ -319,6 +333,7 @@ void bitmap_writer_build(struct packing_data *to_pack)
> struct bitmap_builder bb;
> size_t i;
> int nr_stored = 0; /* for progress */
> + struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>
> writer.bitmaps = kh_init_oid_map();
> writer.to_pack = to_pack;
> @@ -335,7 +350,7 @@ void bitmap_writer_build(struct packing_data *to_pack)
> struct commit *child;
> int reused = 0;
>
> - fill_bitmap_commit(ent, commit);
> + fill_bitmap_commit(ent, commit, &queue);
>
> if (ent->selected) {
> store_selected(ent, commit);
> @@ -360,6 +375,7 @@ void bitmap_writer_build(struct packing_data *to_pack)
> bitmap_free(ent->bitmap);
> ent->bitmap = NULL;
> }
> + clear_prio_queue(&queue);
> bitmap_builder_clear(&bb);
>
> stop_progress(&writer.progress);
