Re: [PATCH] last-modified: implement faster algorithm

From

Taylor Blau <me@ttaylorr.com>

Date

Oct 17, 2025, 14:54 UTC

Message-ID

<aPJYvYs8W6LrV+0Q@nand.local>

In-Reply-To

<20251017063039.GA3074253@coredump.intra.peff.net>

On Fri, Oct 17, 2025 at 02:30:39AM -0400, Jeff King wrote:

> On Thu, Oct 16, 2025 at 07:38:36PM -0400, Taylor Blau wrote:
>
> > Looking through the backtrace, it looks like someone is calling
> > mark_path() with a NULL oid, like so:
> >
> >     (gdb) bt
> >     #0  __memcmp_evex_movbe ()
> >         at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:132
> >     #1  0x00005555555f2c32 in oideq (oid1=0x0, oid2=0x555555a5eeb0)
> >         at ./hash.h:408
> >     #2  0x00005555555f3523 in mark_path (path=0x555555a5eee8 "a", oid=0x0,
> >         data=0x7fffffffd650) at builtin/last-modified.c:179
> >
> > , which makes sense, since at the end of the main loop we call
> > mark_path() on all remaining active paths to indicate that they were
> > modified by whatever commit we just popped off the queue.
>
> Hmm, sounds like the mark_path() discussion from:
>
>   https://lore.kernel.org/git/aHmPHcNQYlhGo8JB@nand.local/
>
> coming home to roost. I'm sure you already knew that, but there's maybe
> an interesting process observation here: in pulling a battle-tested
> implementation apart into patches to be applied in chunks, we ended up
> missing a critical part of that original implementation and getting a
> bug.

Hmm. Is that what happened in this case, though?

--- 8< ---

diff --git a/blame-tree.c b/blame-tree.c
--- a/blame-tree.c
+++ b/blame-tree.c
@@ -119,28 +142,38 @@
 static void mark_path(const char *path, const struct object_id *oid,
 		      struct blame_tree_callback_data *data)
 {
 	struct blame_tree_entry *ent;
+	struct commit_active_paths *active;

 	/* Is it even a path that we are interested in? */
 	ent = hashmap_get_entry_from_hash(data->paths, strhash(path), path,
 					  struct blame_tree_entry, hashent);
 	if (!ent)
 		return;

 	/* Have we already blamed a commit? */
 	if (ent->commit)
 		return;
+
+	/* Are we inactive on the current commit? */
+	if (data->go_faster) {
+		active = active_paths_at(&active_paths, data->commit);
+		if (active && active->active &&
+		    !active->active[ent->diff_idx])
+			return;
+	}
+
 	/*
 	 * Is it arriving at a version of interest, or is it from a side branch
 	 * which did not contribute to the final state?
 	 */
-	if (oidcmp(oid, &ent->oid))
+	if (oid && oidcmp(oid, &ent->oid))
 		return;

 	ent->commit = data->commit;
 	data->num_interesting--;
 	if (data->callback)
 		data->callback(path, data->commit, data->callback_data);
 	hashmap_remove(data->paths, &ent->hashent, path);
 }
--- >8 ---

, where the above was generated with:

    $ git log -1 --oneline 0603f6d9c3c040c914c1412fab972252c4a765c4 \
        -L:mark_path:blame-tree.c

(in this case, 0603f6d9c3 is the hash of the commit that originally
introduced these changes on the GitHub side).

So I don't think that it's the case that we somehow missed this portion
of the changes when pulling the series apart, but rather that the check
was added later on, and not correctly pulled into the version that was
submitted here.

I was wondering if perhaps I had made an error when pulling these
patches out of GitHub's fork, but even in my b0ae8b3cc0 (blame-tree:
introduce '--go-faster' mode, 2025-03-27) from my fork, you can see the
same diff in mark_path() as above.

> It's not like we didn't know that was a risk, of course, and the payoff
> was getting a fresh look at the patches (to improve them and maybe even
> fix latent bugs). So it's probably something to just live with. But I
> wonder if/how we could mitigate that risk. When I reorganize patches in
> a tricky way locally, I often eyeball the diff of the end states
> (whatever mess I had originally, versus the result of the "clean"
> version), and that might have shown the omission here.
>
> I'm not sure if that would have helped here or not. The "end state" of
> the battle-tested version is really GitHub's internal fork. But maybe
> your original patches extracted from that (tb/blame-tree in your fork, I
> think) applied on top of the same base point (e.g., the current tip of
> master) might be an interesting comparison? Or maybe not. The earlier
> rounds have may have had other adjustments which introduce a bunch of
> noise.

I share your feeling here in genreal, but I think in this particular
case the patches were pulled out correctly (at least with respect to the
changes here in mark_path()), and that check was simply dropped or not
properly carried over when the patch we're discussing here was written.

> > Nice, I am glad to see that we are using a bitmap here rather than the
> > hacky 'char *' that we had originally written. I seem to remember that
> > there was a tiny slow-down when using bitmaps, but can't find the
> > discussion anymore. (It wasn't in the internal PR that I originally
> > opened, and I no longer can read messages that far back in history.)
> >
> > It might be worth benchmarking here to see if using a 'char *' is
> > faster. Of course, that's 8x worse in terms of memory usage, but not a
> > huge deal given both the magnitude and typical number of directory
> > elements (you'd need 1024^2 entries in a single tree to occupy even a
> > single MiB of heap).
>
> I doubt the memory usage matters too much. We throw away each bitmap
> after we finish processing its associated commit, so our max memory is
> really the size of the bitmap/char array times the size of the queue (so
> effectively the width of the history graph). So yeah, I too would be
> curious if the performance is actually better with chars.
>
> I also wonder how often we pass an unchanged bitmap to our parents
> (e.g., for the common case that a commit has a single parent, and does
> not touch any of the active paths, the active set will be the same for
> both). There's probably an easy-ish optimization to avoid allocating a
> new bitmap, and to just transfer ownership via pointer.

Funny enough, while we don't have this optimization in the original
version of this code, we did handle being TREESAME at the root tree as a
special case in the original blame-tree.c code. Toon dropped that change
here which I commented on earlier, but that would be a good opportunity
to optimize this case.

I don't think we ever bothered to measure how often we were able to just
pass all active path(s) up to the parent, probably because the original
code didn't actually use the optimization you're talking about here, and
instead did:

    if (!diff_queued_diff.nr) {
        for (i = 0; i < bt->all_paths_nr; i++) {
            if (active_c->active[i])
                pass_to_parent(active_c, active_p, i);
        }

        if (!(parent->object.flags & PARENT1)) {
            parent->object.flags |= PARENT1;
            prio_queue_put(queue, parent);

            ret = 1;
            goto cleanup;
        }
    }

, so that case was just handled specially, but not optimized. But I
don't know that you can just pass the bitmap up directly, since the
parent may already have some bits set if we reached it along some
different path.

I thought that we had to AND NOT out the bits in lm->scratch here, but
those are only set for non-TREESAME paths, so lm->scratch is going to be
all zeros in that case.

I think you could reasonably do something like the following on top of
Toon's patch, though:

--- 8< ---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 40e520ba18..1a9ab3b2b0 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -303,6 +303,18 @@ static void process_parent(struct last_modified *lm,
 		diffcore_std(&lm->rev.diffopt);
 	}

+	if (!diff_queued_diff.nr) {
+		bitmap_or(active_p, active_c);
+		for (i = 0; i < active_c->word_alloc; i++)
+			active_c->words[i] = 0;
+
+		if (!(parent->object.flags & PARENT1)) {
+			parent->object.flags |= PARENT1;
+			prio_queue_put(queue, parent);
+		}
+		goto cleanup;
+	}
+
 	/*
 	 * Otherwise, test each path for TREESAME-ness against the parent. If
 	 * a path is TREESAME, pass it on to this parent.
@@ -330,6 +342,7 @@ static void process_parent(struct last_modified *lm,
 		prio_queue_put(queue, parent);
 	}

+cleanup:
 	memset(lm->scratch->words, 0x0, lm->scratch->word_alloc);
 	diff_queued_diff.nr = 0;
 	diff_queue_clear(&diff_queued_diff);
--- >8 ---

> > Likewise, I wonder if we should have elemtype here be just 'struct
> > bitmap'. Unfortunately I don't think the EWAH code has a function like:
> >
> >     void bitmap_init(struct bitmap *);
> >
> > and only has ones that allocate for us. So we may consider adding one,
> > or creating a dummy bitmap and copying its contents, or otherwise.
>
> I thought that, too, though it does change the max memory use a bit.
> Right now we are storing one pointer per commit (the "struct bitmap *")
> and that is true whether we have processed the commit or not (it is
> populated while the commit is in the queue, and then NULL after). If we
> stored the struct directly, that's twice as many bytes (the eword_t
> pointer, plus a size_t), and it's per commit.

Mmm, good point. I wrote this thinking that the commit_slab was going to
end up a little gross under this patch, with the slab itself having type
'struct bitmap ***', but I agree with everything you wrote here.

> PS I tried building tb/blame-tree from your repo because I was poking at
>    how some of it worked (having forgotten everything I ever knew about
>    it by this point). It does work, but needs this:
>
> diff --git a/blame-tree.c b/blame-tree.c
> index 6addac7b0b..2448f2caf4 100644
> --- a/blame-tree.c
> +++ b/blame-tree.c
> @@ -800,7 +800,6 @@ static int process_parent(struct blame_tree *bt,
>  		int k = diff2idx(bt, fp->two->path);
>  		if (0 <= k && active_c->active[k])
>  			scratch[k] = 1;
> -		diff_free_filepair(fp);
>  	}
>  	for (i = 0; i < bt->all_paths_nr; i++) {
>  		if (active_c->active[i] && !scratch[i])
>
>   on top, since otherwise we try to double-free the filepairs. I'd guess
>   it is a victim of rebasing across a5aecb2cdc (diff: improve lifecycle
>   management of diff queues, 2024-09-30), which swapped out
>   DIFF_QUEUE_CLEAR(), which left freeing the responsibility of the
>   caller, for diff_queue_clear() which handles that itself.

Ah, good catch. When I pulled those patches out a while ago, I think I
wrote something like, "this should more or less work, but doesn't, and
I'll leave it as an exercise to the reader to figure out why ;-)."

Thanks,
Taylor