On Sun, Apr 10, 2016 at 3:19 PM, Stephan Beyer <s-beyer@xxxxxxx> wrote: > 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. > 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@xxxxxxx> > --- > > 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. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html