Re: [PATCH] attr: do not mark queried macros as unset

From: Duy Nguyen <pclouds@gmail.com>
Date: Jan 22, 2019, 09:50 UTC
Message-ID: <CACsJy8ALL5_gHro9jZcSBnfnV01UEJLReCrqi+w727bkqnjUAA@mail.gmail.com>
In-Reply-To: <20190122071921.GC28555@sigill.intra.peff.net>

On Tue, Jan 22, 2019 at 2:19 PM Jeff King <peff@peff.net> wrote:

> Yes, that's the interesting part. I think I've convinced myself, too,
> that it doesn't do the _wrong_ thing ever. But I think it misses the
> point of the original, which is that you want common ones like "diff"
> not to trigger in_stack if nobody has actually used them.

Yes. I don't think it matters much when you don't have a lot of attributes, but if you do, the cost of lookup will be proportional to the stack's depth even whenever you look up some attribute, even though you don't use it. This makes code that uses attributes just a tiny bit slower over time because I think we still add more and more attributes.

Show 15 quoted lines

> And doing that
> really does mean marking in_stack not just when a macro mentions it
> (because clearly "binary" is going to mention it for every repo), but
> waiting to see if anybody mentions that macro.
>
> Which means we must call determine_macros(), and then propagate the
> macro's in_stack to its expansion (if it's indeed called at all).
>
> I don't think that would be _too_ hard to do. But I also wonder if
> there's much point. We are trying to avoid fill(), but I think that
> determine_macros() is of roughly the same complexity (look at all
> matches of all stacks). I guess it does avoid path_matches(), which is a
> bit more expensive. And in theory it could be cached for a particular
> stack top, so the work is amortized across many path lookups (though I
> think that gets even more tricky).

There is a comment that got eventually removed in bw/attr, especially the second to last sentence.

-/*
- * NEEDSWORK: maybe-real, maybe-macro are not property of
- * an attribute, as it depends on what .gitattributes are
- * read.  Once we introduce per git_attr_check attr_stack
- * and check_all_attr, the optimization based on them will
- * become unnecessary and can go away.  So is this variable.
- */
-static int cannot_trust_maybe_real;

The promise here is, after we have moved away from global attribute stack, we can build custom stacks containing only queried attributes. This makes attribute stacks short (in the best case, empty, which is what my optimization is for) which means fill time (I think it's path_matches() would dominate) becomes shorter in the _general_ case, so this optimization "will become unnecessary". More importantly the total number of attributes will not matter since we only look at what we are interested. This makes attribute lookup scale much better in the long run.

This part, building custom stacks, has not come true yet. But if we optimize this code again, I think this is the way forward. Perhaps this could be one of the mini projects for Matthey's students. The scope is relatively small, and optimization is always fun.

-- 
Duy