Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters

From: Derrick Stolee <stolee@gmail.com>
Date: Dec 30, 2019, 16:04 UTC
Message-ID: <6d20f568-9681-3e66-b892-8f076e20dc63@gmail.com>
In-Reply-To: <20191229062414.GC220034@coredump.intra.peff.net>

On 12/29/2019 1:24 AM, Jeff King wrote:

Show 26 quoted lines

> On Fri, Dec 27, 2019 at 11:11:37AM -0500, Derrick Stolee wrote:
> 
>>> So here are a few patches to reduce the CPU and memory usage. They could
>>> be squashed in at the appropriate spots, or perhaps taken as inspiration
>>> if there are better solutions (especially for the first one).
>>
>> I tested these patches with the Linux kernel repo and reported my results
>> on each patch. However, I wanted to also test on a larger internal repo
>> (the AzureDevOps repo), which has ~500 commits with more than 512 changes,
>> and generally has larger diffs than the Linux kernel repo.
>>
>> | Version  | Time   | Memory |
>> |----------|--------|--------|
>> | Garima   | 16m36s | 27.0gb |
>> | Peff 1   | 6m32s  | 28.0gb |
>> | Peff 2   | 6m48s  |  5.6gb |
>> | Peff 3   | 6m14s  |  4.5gb |
>> | Shortcut | 3m47s  |  4.5gb |
>>
>> For reference, I found the time and memory information using
>> "/usr/bin/time --verbose" in a bash script.
> 
> Thanks for giving it more exercise. My heap profiling was done with
> massif, which measures the heap directly. Measuring RSS would cover
> that, but will also include the mmap'd packfiles. That's probably why
> your linux.git numbers were slightly higher than mine.

That's interesting. I initially avoided massif because it is so much slower than /usr/bin/time. However, the inflated numbers could be explained by that. Also, the distinction between mem_heap and mem_heap_extra may have interesting implications. Looking online, it seems that large mem_heap_extra implies the heap is fragmented from many small allocations.

Here are my findings on the Linux repo:

| Version  | mem_heap | mem_heap_extra |
|----------|----------|----------------|
| Peff 1   |  6,500mb |          913mb |
| Peff 2   |  3,100mb |          286mb |
| Peff 3   |    781mb |          235mb |

These numbers more closely match your numbers (in sum of the two columns).

> (massif is a really great tool if you haven't used it, as it also shows
> which allocations were using the memory. But it's part of valgrind, so
> it definitely doesn't run on native Windows. It might work under WSL,
> though. I'm sure there are also other heap profilers on Windows).

I am using my Linux machine for my tests. Garima is using her Windows machine.

Show 29 quoted lines

>> By "Shortcut" in the table above, I mean the following patch on top of
>> Garima's and Peff's changes. It inserts a max_changes option into struct
>> diff_options to halt the diff early. This seemed like an easier change
>> than creating a new tree diff algorithm wholesale.
> 
> Yeah, I'm not opposed to a diff feature like this.
> 
> But be careful, because...
> 
>> diff --git a/diff.h b/diff.h
>> index 6febe7e365..9443dc1b00 100644
>> --- a/diff.h
>> +++ b/diff.h
>> @@ -285,6 +285,11 @@ struct diff_options {
>>  	/* Number of hexdigits to abbreviate raw format output to. */
>>  	int abbrev;
>>  
>> +	/* If non-zero, then stop computing after this many changes. */
>> +	int max_changes;
>> +	/* For internal use only. */
>> +	int num_changes;
> 
> This is holding internal state in diff_options, but the same
> diff_options is often used for multiple diffs (e.g., "git log --raw"
> would use the same rev_info.diffopt over and over again).
> 
> So it would need to be cleared between diffs. There's a similar feature
> in the "has_changes" flag, though it looks like it is cleared manually
> by callers. Yuck.

You're right about this. What if we initialize it in diff_tree_paths() before it calls the recursive ll_difF_tree_paths()?

Show 12 quoted lines

> This isn't a problem for commit-graph right now, but:
> 
>   - it actually could be using a single diff_options, which would be
>     slightly simpler (it doesn't seem to save much CPU, though, because
>     the initialization is relatively cheap)
> 
>   - it's a bit of a subtle bug to leave hanging around for the next
>     person who tries to use the feature
> 
> I actually wonder if this could be rolled into the has_changes and
> diff_can_quit_early() feature. This really just a generalization of that
> feature (which is like setting max_changes to "1").

I thought about this at first, but it only takes a struct diff_options right now. It does have an internally-mutated member (flags.has_changes) but it also seems a bit wrong to add a uint32_t of the count in this. Changing the prototype could be messy, too.

There are also multiple callers, and limiting everything to tree-diff.c limits the impact.

Thanks, -Stolee