Re: [PATCH v2 4/5] get_sha1: speed up ambiguous 40-hex test

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Jan 14, 2014, 11:34 UTC
Message-ID: <52D520CD.7070902@alum.mit.edu>
In-Reply-To: <20140114095002.GA32258@sigill.intra.peff.net>

On 01/14/2014 10:50 AM, Jeff King wrote:

Show 23 quoted lines

> On Fri, Jan 10, 2014 at 04:41:20AM -0500, Jeff King wrote:
> 
>> That being said, we could further optimize this by not opening the files
>> at all (and make that the responsibility of do_one_ref, which we are
>> avoiding here). I am slightly worried about the open() cost of my
>> solution. It's amortized away in a big call, but it is probably
>> noticeable for something like `git rev-parse <40-hex>`.
> 
> I took a look at this. It gets a bit hairy. My strategy is to add a flag
> to ask read_loose_refs to create REF_INCOMPLETE values. We currently use
> this flag for loose REF_DIRs to mean "we haven't opendir()'d the
> subdirectory yet". This would extend it to the non-REF_DIR case to mean
> "we haven't opened the loose ref file yet". We'd check REF_INCOMPLETE
> before handing the ref_entry to a callback, and complete it if
> necessary.
> 
> It gets ugly, though, because we need to pass that flag through quite a
> bit of callstack. get_ref_dir() needs to know it, which means all of
> find_containing_dir, etc need it, meaning it pollutes all of the
> packed-refs code paths too.
> 
> I have a half-done patch in this direction if that doesn't sound too
> nasty.

A long time ago I write a patch series to allow incomplete reading of references, but my version *always* read them lazily, so it was much simpler (no need to pass a new option down the call stack). It didn't seem to speed things up in general, so I never submitted it.

Reading lazily only from particular callers is more complicated, and I can see how it would get messy.

Given the race avoidance needed between packed/loose references, lazy reading would mean that after each reference is read, the packed-refs file would need to be stat()ted again to make sure that it hasn't been changed since the last check. I know this isn't an issue for your use case, because you plan *never* to read the file contents. But it does increase the price of lazy reference reading to most callers.

On the other hand, if we ever go in the direction of routing *all* reference lookups--including lookups of single references--through the cache, then lazy reading of references probably becomes essential to avoid populating more of the cache than necessary.

Show 17 quoted lines

>>> This doesn't correctly handle the rule
>>>
>>> 	"refs/remotes/%.*s/HEAD"
>> [...]
> 
>> I'll see how painful it is to make it work.
> 
> It's actually reasonably painful. I thought at first we could get away
> with more cleverly parsing the rule, find the prefix (up to the
> placeholder), and then look for the suffix ("/HEAD") inside there. But
> it can never work with the current do_for_each_* code. That code only
> triggers a callback when we see a concrete ref. It _never_ lets the
> callbacks see an intermediate directory.
> 
> So a NO_RECURSE flag is not sufficient to handle this case. I'd need to
> teach do_for_each_ref to recurse based on pathspecs, or a custom
> callback function. And that is getting quite complicated.

Another possibility would be to have an "int recurse" parameter rather than "bool recurse", telling how many levels to recurse. Then one could do a

    do_for_each_ref(..., "refs/remotes", ..., recurse=2)

to get all of the refs/remotes/*/HEAD references. Though since all of the heads for a remote are also siblings of "refs/remotes/foo/HEAD", it could still involve a lot of superfluous file reading. And the integer wouldn't fit conveniently in the flags parameter.

Show 5 quoted lines

> I think it might be simpler to just do my own custom traversal. What I
> need is much simpler than what do_for_each_entry provides. I don't need
> recursion, and I don't actually need to look at the loose and packed
> refs together. It's OK for me to do them one at a time because I don't
> care about the actual value; I just want to know about which refs exist.

Yes. Still, the code is really piling up for this one warning for the contrived eventuality that somebody wants to pass SHA-1s and branch names together in a single cat-file invocation *and* wants to pass lots of inputs at once and so is worried about performance *and* has reference names that look like SHA-1s. Otherwise we could just leave the warning disabled in this case, as now. Or we could add a new "--hashes-only" option that tells cat-file to treat all of its arguments/inputs as SHA-1s; such an option would permit an even faster code path for bulk callers.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/