[PATCH v2] speeding up 40-hex ambiguity check

From: Jeff King <peff@peff.net>
Date: Jan 7, 2014, 23:56 UTC
Message-ID: <20140107235631.GA10503@sigill.intra.peff.net>
In-Reply-To: <20140107220856.GA10074@sigill.intra.peff.net>

On Tue, Jan 07, 2014 at 05:08:56PM -0500, Jeff King wrote:

Show 18 quoted lines

> > OK.  I agree with that line of thinking.  Let's take it one step at
> > a time, i.e. do c. and also use warn_on_object_refname_ambiguity in
> > "rev-list --stdin" first and leave the simplification (i.e. b.) for
> > later.
> 
> Here's a series to do that. The first three are just cleanups I noticed
> while looking at the problem.
> 
> While I was writing the commit messages, though, I had a thought. Maybe
> we could simply do the check faster for the common case that most refs
> do not look like object names? Right now we blindly call dwim_ref for
> each get_sha1 call, which is the expensive part. If we instead just
> loaded all of the refnames from the dwim_ref location (basically heads,
> tags and the top-level of "refs/"), we could build an index of all of
> the entries matching the 40-hex pattern. In 99% of cases, this would be
> zero entries, and the check would collapse to a simple integer
> comparison (and even if we did have one, it would be a simple binary
> search in memory).

That turned out very nicely, and I think we can drop the extra flag entirely. Brodie's patch still makes sense, for people who do want to turn off ambiguity warnings entirely (and I built on his patch, which matters textually for 4 and 5, but it would be easy to rebase).

I'm cc-ing Michael, since it is his ref-traversal code I am butchering in the 3rd patch. The first two are the unrelated cleanups from v1. They are not necessary, but I do not see any reason not to include them.

  [1/5]: cat-file: refactor error handling of batch_objects
  [2/5]: cat-file: fix a minor memory leak in batch_objects
  [3/5]: refs: teach for_each_ref a flag to avoid recursion
  [4/5]: get_sha1: speed up ambiguous 40-hex test
  [5/5]: get_sha1: drop object/refname ambiguity flag

-Peff