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

From: Toon Claes <toon@iotcl.com>
Date: Oct 27, 2025, 15:48 UTC
Message-ID: <87ms5cpcpu.fsf@iotcl.com>
In-Reply-To: <aPrAyJYvWtlvmiEx@nand.local>

Taylor Blau <me@ttaylorr.com> writes:

Show 9 quoted lines

>> Ahha, that might be a good idea. This might allow us to get rid of the
>> hashmap, which stops us from storing the paths twice. Not sure what the
>> impact on the performance would be, because the hashmap now is valuable
>> for path_idx() lookups.
>
> Looking at this a little further, I don't think I consider this worth
> doing. Using a strvec here is awkward since last_modified_init() really
> wants to assign lm->all_paths based on each entry's diff_idx, which is
> not what strvec.h is designed for.

Yeah, I decided to leave it as is for now.

> You *could* use a string_list, and shove a pointer to the
> last_modified_entry struct in the ->util field, but that is also
> inefficient since we remove paths from our hashmap as we mark them, and
> repeating that in a string_list would be wasteful.

There was another idea I had. Instead of giving each commit a bitmap, give each commit a hashmap, and pass the hashmap entries across commits. This allows us to store paths only in once place and removes the need to allocate a fixed array `all_paths` again.

But in my measurements, this was about 30% slower than the solution I've submitted in v3. And it also complicates the memory management. So I've abandonned this idea.

-- 
Cheers,
Toon