Re: [PATCH 0/4] Test name-rev with small stack
- From
Jeff King <peff@peff.net>
- Date
- Sep 11, 2017, 18:08 UTC
- Message-ID
- <20170911180824.gf6jecxpx7d3d4a7@sigill.intra.peff.net>
- In-Reply-To
- <9b3275a2-7b47-9ed8-6f1f-dac999c3b46a@grubix.eu>
On Fri, Sep 08, 2017 at 02:33:35PM +0200, Michael J Gruber wrote:
Show 7 quoted lines
> Looking at it more closely, the solution in cbc60b6720 ("git tag
> --contains: avoid stack overflow", 2014-04-24) seems to be a bit "ad
> hoc" to me:
>
> First of all, there is more than "tag --contains" that may exceed the
> stack by recursion. So I would expect the solution to be more general,
> and not localised and specialised to builtin/tag.cAt the time, tag was the only one using this depth-first contains algorithm. It's since been adapted to ref-filter.c, but of course the stack handling went with it.
Most traversals have a date-sorted queue, so are effectively doing a breadth-first iteration with no recursion.
Show 5 quoted lines
> Second, this is a walk, so I'm wondering whether our revision walk > machinery should be the place to add missing functionality (if any). > That way, everything would benefit from possible or existing > improvements there. For example, I think some of our "extra walkers" > don't heed object replacements. (I need to test more.)
It's possible that name-rev could make better use of the existing traversal machinery. It's often tough to do so, though, because that machinery gives you a linearized ordering of the commits. Whereas something like name-rev really cares about the order that it visits the commits, because it's building up the names.
It's the same for this "tag --contains" traversal. It _used_ to be a series of merge-base computations. But by doing a custom traversal, we can cache incremental results through the graph and avoid walking over the same bits multiple times. There actually is a way to do it with the regular breadth-first traversal, but you have to store one bit per ref you're checking for each commit.
I played around with that a bit a while ago, and it did seem to work. I can dig up the patches if you're interested. But one downside is that one bit per ref per commit adds up if you have a lot of refs. A large number of those bitfields will be the same, so you could probably get by with a copy-on-write scheme, but I never implemented that.
Of course somebody may have a more clever algorithm, too. I don't claim the above is a proof. ;)
-Peff