On Tue, Dec 01, 2020 at 11:28:11PM -0800, Jonathan Tan wrote:
> > However, if we walk trees
> > from top to bottom, then we might be parsing trees that are actually
> > part of a re-used bitmap.
>
> Isn't the issue that we shouldn't walk trees at all before exhausting
> our commit search, not the direction that we walk the trees in (top to
> bottom or bottom to top or whatever)?
Right, the direction that we explore trees in isn't important: what
matters is that we consider them after the commits. I've clarified the
commit message to reflect this.
> > To avoid over-walking trees, add them to a
> > LIFO queue and walk them from bottom-to-top after exploring commits
> > completely.
>
> Just to clarify - would it work just as well with a FIFO queue (not LIFO
> queue)? It seems to me that the most important part is doing this after
> exploring commits completely.
Yup, see above.
> > static void fill_bitmap_commit(struct bb_commit *ent,
> > struct commit *commit,
> > - struct prio_queue *queue)
> > + struct prio_queue *queue,
> > + struct prio_queue *tree_queue,
> > + struct bitmap_index *old_bitmap,
> > + const uint32_t *mapping)
> > {
> > if (!ent->bitmap)
> > ent->bitmap = bitmap_new();
> >
> > - bitmap_set(ent->bitmap, find_object_pos(&commit->object.oid));
> > prio_queue_put(queue, commit);
> >
> > while (queue->nr) {
> > struct commit_list *p;
> > struct commit *c = prio_queue_get(queue);
> >
> > + /*
> > + * If this commit has an old bitmap, then translate that
> > + * bitmap and add its bits to this one. No need to walk
> > + * parents or the tree for this commit.
> > + */
>
> This comment should be right before "if (old && ...", I think. Here, it
> is a bit misleading. It leads me to think that "this commit has an old
> bitmap" means old_bitmap != NULL, but it is actually old != NULL.
Yup, the comment is much more clear when placed there, thanks.
> > + if (old_bitmap && mapping) {
>
> This is defensive in that if we somehow calculate old_bitmap without
> mapping (or the other way around) (which is a bug), things just slow
> down instead of breaking. I'm OK with this, but I still wanted to call
> it out.
Right, we should never have one without the other, so in that sense this
is a defensive check. IOW, this could easily be written as `if
(old_bitmap)` or `if (mapping)`, but being extra defensive here doesn't
hurt.
Thanks,
Taylor
