Re: DEVEL: Help with feature implementation

From: Derrick Stolee <stolee@gmail.com>
Date: Jan 20, 2021, 02:21 UTC
Message-ID: <ac68007e-ca66-0229-fa8f-4ceb7d6d8f23@gmail.com>
In-Reply-To: <9fc9d752-06f4-e75d-1549-f257fd34e0c3@aerusso.net>

On 1/19/2021 9:52 AM, Antonio Russo wrote:

Show 34 quoted lines

> On 1/18/21 6:24 PM, Junio C Hamano wrote:
>> Antonio Russo <aerusso@aerusso.net> writes:
>>
>>> As a side note, would this list be willing to look at patches that remove
>>> the need to use revs->limited?  Adding new features would be much easier if
>>> we could restrict git to use streaming algorithms for these simplifications.
>>
>> Do you mean you will write new implementations of operations like
>> "--simplify-merges", "--ancestory-path" and all its friends without
>> the need for the "limited" bit?
> 
> Yes.
> 
>> Willing to look at?  I do not know about others, but sure, it would
>> make be extremely excited.
>>
>> You may be able to rewrite some other operations that implicitly
>> require the limited bit into an incremental implementation, but I am
>> skeptical that you can do "simplify-merges" in a streaming fashion
>> in such a way that we'd dig a bit but not all the way down before
>> making decisions on which commits should be included in the output
>> and how their parenthood relationship should appear etc.  I and
>> Linus tried independently and we did not get that far in our
>> attempts (note: there wasn't commit-graph back then).
> 
> Yeah, it's a big task (but, it'd be useful work, rather than doing
> another rewrite of my feature to make it work when revs->limited).
> Each of the flags (simplify-merges, ancestry-path, etc.) is its own
> little sub-project.
> 
> I haven't thought about any one flag specifically, but the fact that
> two complete code paths exist right now just seem like a nightmare.
> I'm not necessarily interested in making the implementations faster,
> but rather getting rid of the duplicated code path.

It's definitely a long shot to remove the limited flag altogether, but a good start would be to remove sort_in_topological_order(). All of its logic is already re-implemented in the streaming version (see every use of "struct topo_walk_info" in revision.c). The streaming is designed to be faster in the presence of a commit-graph file, but it should still work correctly without one. Since all commits with have "generation number infinity," each phase of the walk will do the same as the limit_list() and walk all reachable commits before returning the first result.

The only thing to ask is: what is the overhead of the streaming version over sort_in_topological_order()? Is there one? You'd need to do performance tests without a commit-graph file.

This has long been on my own TODO list, but I haven't been able to prioritize it over other things. I'd be happy to review the change. It also would be a good way to familiarize yourself with the code and how we already do some streaming things, even when "extra" information is needed to accomplish that.

Thanks, -Stolee