Re: [PATCH v2 19/21] bisect: use a bottom-up traversal to find relevant weights

From: Christian Couder <christian.couder@gmail.com>
Date: Apr 13, 2016, 14:11 UTC
Message-ID: <CAP8UFD2_3jwGVJaoOzrKESi8qBN=4D49kiZes+bJARxMvAi3tg@mail.gmail.com>
In-Reply-To: <1460294354-7031-20-git-send-email-s-beyer@gmx.net>

On Sun, Apr 10, 2016 at 3:19 PM, Stephan Beyer <s-beyer@gmx.net> wrote:

Show 9 quoted lines

> The idea is to reverse the DAG and perform a traversal
> starting on all sources of the reversed DAG.
>
> We walk from the bottom commits, incrementing the weight while
> walking on a part of the graph that is single strand of pearls,
> or doing the "count the reachable ones the hard way" using
> compute_weight() when we hit a merge commit.
>
> A traversal ends when the computed weight is falling or halfway.

Yeah, it looks like it could be a good optimization to end a traversal looking for "relevant" commits when the weight is falling.

Show 14 quoted lines

> This way, commits with too high weight to be relevant are never
> visited (and their weights are never computed).
>
> Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
> ---
>
> Notes:
>     I rephrased the commit message.
>
>     I renamed the functions such that they don't talk about "BFS"
>     because that is irrelevant. Also use a DFS now because it is
>     less code (and a little more efficient).
>
>     I plugged some leaks.

That's a lot of things in just one commit.

>  bisect.c | 250 +++++++++++++++++++++++++++++++++++++++++----------------------
>  1 file changed, 162 insertions(+), 88 deletions(-)

Also from the diff stats it looks like you add a lot of code in this commit and the previous one. I wonder why you are saying that a DFS is less code above then.

The previous patch (18/21) has the following diff stat:

> bisect.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
> 1 file changed, 97 insertions(+), 19 deletions(-)

And the subsequent patches don't reduce code size overall. Diff stat for 20/21 is:

> bisect.c | 44 +++++++++++++++++++-------------------------
> 1 file changed, 19 insertions(+), 25 deletions(-)

And diff stat for 21/21 is:

> bisect.c | 18 +++++++++++++-----
> 1 file changed, 13 insertions(+), 5 deletions(-)

So after your patches from 18/21 to 21/21 there are around 150 more lines of code. Maybe this is worth it, but I wonder if at least some optimizations, like for example ending a traversal looking for "relevant" commits when the weight is falling, could be implemented without changing the code so much and adding so many lines.