Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Junio C Hamano]

Jeff King  writes:

> So I think on the generating side we are better off creating a slightly
> longer abbreviation that is unambiguous no matter what context it is
> used in. I.e., I'd argue that it's actually more _correct_ to ignore
> the disambiguation code entirely on the generating side.

OK.  Thanks for sanity checking.

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Jeff King]

On Wed, Oct 04, 2017 at 03:07:25PM +0900, Junio C Hamano wrote:

> > -   exists = has_sha1_file(sha1);
> > -   while (len < GIT_SHA1_HEXSZ) {
> > -   struct object_id oid_ret;
> > -   status = get_short_oid(hex, len, _ret, GET_OID_QUIETLY);
> > -   if (exists
> > -   ? !status
> > -   : status == SHORT_NAME_NOT_FOUND) {
> > -   hex[len] = 0;
> > -   return len;
> > -   }
> > -   len++;
> > -   }
> > -   return len;
> 
> The "always_call_fn" thing is a big sledgehammer that overrides
> everything else in update_candidates().  It bypasses the careful
> machinery set up to avoid having to open ambiguous object to learn
> their types as much as possible.  One narrow exception when it is OK
> to use is if we never limit our candidates with type.
> 
> And it might appear that the conversion is safe (if only because we
> do not see any type limitation in the get_short_oid() call above),
> but I think there is one case where this patch changes the
> behaviour: what happens if core.disambiguate was set to anything
> other than "none"?  The new code does not know anything about type
> based filtering, so it can end up reporting longer abbreviation than
> it was asked to produce.  It may not be a problem in practice, though.
> 
> I am not sure if setting core.disambiguate is generally a good idea
> in the first place, and if it is OK to break find_unique_abbrev()
> with respect to the configuration variable like this patch does.
> 
> I'd feel safe if we get extra input from Peff, who introduced the
> feature in 5b33cb1f ("get_short_sha1: make default disambiguation
> configurable", 2016-09-27).

Regarding core.disambiguate, I _do_ think it's reasonable to set it to
"commit" or "committish". And in fact I have meant to revisit the idea
of doing so by default (the reason it was made into config at all was to
let people play around with it and gain experience).

That said, I think it's entirely reasonable for find_unique_abbrev() to
ignore type-based disambiguation entirely.

The type disambiguation is really a property of the context in which we
do a lookup. And that context is not necessarily known to the generating
side. Even core.disambiguate is not universal, as command-specific
context overrides it.

So I think on the generating side we are better off creating a slightly
longer abbreviation that is unambiguous no matter what context it is
used in. I.e., I'd argue that it's actually more _correct_ to ignore
the disambiguation code entirely on the generating side.

And it should also be faster, because it turns the abbreviation search
into a purely textual one that never has to look at extra objects. And
that speed matters a lot more on the generating side, where we tend to
output long lists of abbreviated sha1s in commands like "git log" (as
opposed to the lookup side, where we're asked to find some particular
item of interest).

-Peff

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Junio C Hamano]

Derrick Stolee  writes:

> On 10/4/2017 2:07 AM, Junio C Hamano wrote:
>> Derrick Stolee  writes:
>>
>>> -   exists = has_sha1_file(sha1);
>>> -   while (len < GIT_SHA1_HEXSZ) {
>>> -   struct object_id oid_ret;
>>> -   status = get_short_oid(hex, len, _ret, GET_OID_QUIETLY);
>>> -   if (exists
>>> -   ? !status
>>> -   : status == SHORT_NAME_NOT_FOUND) {
>>> -   hex[len] = 0;
>>> -   return len;
>>> -   }
>>> -   len++;
>>> -   }
>>> -   return len;
>> The "always_call_fn" thing is a big sledgehammer that overrides
>> everything else in update_candidates().  It bypasses the careful
>> machinery set up to avoid having to open ambiguous object to learn
>> their types as much as possible.  One narrow exception when it is OK
>> to use is if we never limit our candidates with type.
>
> I do not modify get_short_oid, which uses these advanced options,
> depending on the flags given. find_unique_abbrev_r() does not use
> these advanced options.

It is true that the function no longer even calls get_short_oid().

When it called get_short_oid() before this patch, it not pass "I
want to favor committish" in the old code, as we can see in the
above removed code.  In get_short_oid(), ds.fn would have been set
to default_disambigutate_hint, and that would have been used in the
update_candidates() function.

Now, unless the user has core.disambiguate configuration set, this
"default" thing becomes NULL, so overriding ds.fn like this patch
does and bypass major parts of update_candidates() is probably fine.
After all, update_candidates() wouldn't have inspected the object
types and made the candidate management anyway with ds.fn set to
NULL.

But having the configuration set would mean that the user wants to
set default_disambigutate_hint to some non-default value, e.g.
telling us to find disambiguation only among committishes; the patch
however overrides ds.fn and essentially makes the code ignore it
altogether, no?  That change in behaviour was what I was wondering
about.

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Derrick Stolee]

On 10/4/2017 2:07 AM, Junio C Hamano wrote:

Derrick Stolee  writes:


-   exists = has_sha1_file(sha1);
-   while (len < GIT_SHA1_HEXSZ) {
-   struct object_id oid_ret;
-   status = get_short_oid(hex, len, _ret, GET_OID_QUIETLY);
-   if (exists
-   ? !status
-   : status == SHORT_NAME_NOT_FOUND) {
-   hex[len] = 0;
-   return len;
-   }
-   len++;
-   }
-   return len;

The "always_call_fn" thing is a big sledgehammer that overrides
everything else in update_candidates().  It bypasses the careful
machinery set up to avoid having to open ambiguous object to learn
their types as much as possible.  One narrow exception when it is OK
to use is if we never limit our candidates with type.


I do not modify get_short_oid, which uses these advanced options, 
depending on the flags given. find_unique_abbrev_r() does not use these 
advanced options.



And it might appear that the conversion is safe (if only because we
do not see any type limitation in the get_short_oid() call above),
but I think there is one case where this patch changes the
behaviour: what happens if core.disambiguate was set to anything
other than "none"?  The new code does not know anything about type
based filtering, so it can end up reporting longer abbreviation than
it was asked to produce.  It may not be a problem in practice, though.

I am not sure if setting core.disambiguate is generally a good idea
in the first place, and if it is OK to break find_unique_abbrev()
with respect to the configuration variable like this patch does.


I do not think that type-aware disambiguation goes through this code 
path, since it requires giving different parameters to get_short_oid(). 
Test t1512-rev-parse-disambituagion.sh has a test 'core.disambiguate 
config can prefer types' that verifies this behavior.



I'd feel safe if we get extra input from Peff, who introduced the
feature in 5b33cb1f ("get_short_sha1: make default disambiguation
configurable", 2016-09-27).


I look forward to more feedback. Thanks for taking the time to look at 
my patch series.


Thanks,
-Stolee

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Derrick Stolee]

On 10/4/2017 2:10 AM, Junio C Hamano wrote:

Derrick Stolee  writes:
...

I understand that this patch on its own does not have good numbers. I
split the
patches 3 and 4 specifically to highlight two distinct changes:

Patch 3: Unroll the len loop that may inspect all files multiple times.
Patch 4: Parse less while disambiguating.

Patch 4 more than makes up for the performance hits in this patch.

Now you confused me even more.  When we read the similar table that
appears in [Patch 4/5], what does the "Base Time" column mean?
Vanilla Git with [Patch 3/5] applied?  Vanillay Git with [Patch 4/5]
alone applied?  Something else?
In PATCH 3, 4, and 5, I used the commit-by-commit diff for the perf 
numbers, so the "Base Time" for PATCH 4 is the time calculated when 
PATCH 3 is applied. The table in the [PATCH 0/5] message includes the 
relative change for all commits.


I recalculated the relative change for each patch related to the 
baseline (PATCH 2). Looking again, it appears I misspoke and PATCH 4 
does include a +8% change for a fully-repacked Linux repo relative to 
PATCH 2. Since PATCH 5 includes an optimization targeted directly at 
large packfiles, the final performance gain is significant in the 
fully-packed cases.


It is also worth looking at the absolute times for these cases, since 
the fully-packed case is significantly faster than the multiple-packfile 
case, so the relative change impacts users less.


One final note: the improvement was clearer in test p0008.1 when the 
test included "sort -R" to shuffle the known OIDs. Providing OIDs in 
lexicographic order has had a significant effect on the performance, 
which does not reflect real-world usage. I removed the "sort -R" because 
it is a GNU-ism, but if there is a good cross-platform alternative I 
would be happy to replace it.


p0008.1: find_unique_abbrev() for existing objects
--

For 10 repeated tests, each checking 100,000 known objects, we find the
following results when running in a Linux VM:

| Repo  | Baseline | Patch 3 | Rel % | Patch 4 | Rel % | Patch 5 | Rel % |
|---|--|-|---|-|---|-|---|
| Git   | 0.09 | 0.06    | -33%  | 0.05    | -44%  | 0.05    | -44%  |
| Git   | 0.11 | 0.08    | -27%  | 0.08    | -27%  | 0.08    | -27%  |
| Git   | 0.09 | 0.07    | -22%  | 0.06    | -33%  | 0.06    | -33%  |
| Linux | 0.13 | 0.32    | 146%  | 0.14    | + 8%  | 0.05    | -62%  |
| Linux | 1.13 | 1.12    | - 1%  | 0.94    | -17%  | 0.88    | -22%  |
| Linux | 1.08 | 1.05    | - 3%  | 0.86    | -20%  | 0.80    | -26%  |
| VSTS  | 0.12 | 0.23    | +92%  | 0.11    | - 8%  | 0.05    | -58%  |
| VSTS  | 1.02 | 1.08    | + 6%  | 0.95    | - 7%  | 0.95    | - 7%  |
| VSTS  | 2.25 | 2.08    | - 8%  | 1.82    | -19%  | 1.93    | -14%  |

(Each repo has three versions, in order: 1 packfile, multiple packfiles, 
and multiple packfiles and loose objects.)


Thanks,
-Stolee

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Junio C Hamano]

Derrick Stolee  writes:

> On 10/3/2017 6:49 AM, Junio C Hamano wrote:
>> Derrick Stolee  writes:
>>
>>> p0008.1: find_unique_abbrev() for existing objects
>>> --
>>>
>>> For 10 repeated tests, each checking 100,000 known objects, we find the
>>> following results when running in a Linux VM:
>>>
>>> |   | Pack  | Packed  | Loose  | Base   | New| |
>>> | Repo  | Files | Objects | Objects| Time   | Time   | Rel%|
>>> |---|---|-||||-|
>>> | Git   | 1 |  230078 |  0 | 0.09 s | 0.06 s | - 33.3% |
>>> | Git   | 5 |  230162 |  0 | 0.11 s | 0.08 s | - 27.3% |
>>> | Git   | 4 |  154310 |  75852 | 0.09 s | 0.07 s | - 22.2% |
>>> | Linux | 1 | 5606645 |  0 | 0.12 s | 0.32 s | +146.2% |
>>> | Linux |24 | 5606645 |  0 | 1.12 s | 1.12 s | -  0.9% |
>>> | Linux |23 | 5283204 | 323441 | 1.08 s | 1.05 s | -  2.8% |
>>> | VSTS  | 1 | 4355923 |  0 | 0.12 s | 0.23 s | + 91.7% |
>>> | VSTS  |32 | 4355923 |  0 | 1.02 s | 1.08 s | +  5.9% |
>>> | VSTS  |31 | 4276829 |  79094 | 2.25 s | 2.08 s | -  7.6% |
>>
>> The above does not look so good, especially in cases where a
>> repository is well maintained by packing into smaller number of
>> packs, we get much worse result?
>
> I understand that this patch on its own does not have good numbers. I
> split the
> patches 3 and 4 specifically to highlight two distinct changes:
>
> Patch 3: Unroll the len loop that may inspect all files multiple times.
> Patch 4: Parse less while disambiguating.
>
> Patch 4 more than makes up for the performance hits in this patch.

Now you confused me even more.  When we read the similar table that
appears in [Patch 4/5], what does the "Base Time" column mean?
Vanilla Git with [Patch 3/5] applied?  Vanillay Git with [Patch 4/5]
alone applied?  Something else?

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Junio C Hamano]

Derrick Stolee  writes:

> -int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
> +struct min_abbrev_data {
> + unsigned int init_len;
> + unsigned int cur_len;
> + char *hex;
> +};
> +
> +static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
>  {
> - int status, exists;
> + struct min_abbrev_data *mad = cb_data;
> +
> + char *hex = oid_to_hex(oid);
> + unsigned int i = mad->init_len;
> + while (mad->hex[i] && mad->hex[i] == hex[i])
> + i++;
> +
> + if (i < GIT_MAX_RAWSZ && i >= mad->cur_len)
> + mad->cur_len = i + 1;
> +
> + return 0;
> +}

The idea is to keep the target to be abbreviated in mad->hex[], and
as the two functions find_short_{object_filename,packed_object}
discover objects whose first 'len' letters of hexname are the same
as the target, they'd call into the "always_call_fn" callback, which
is this function, and it keeps track of the maximum of the common
prefix it has seen.  Which makes sense.  Well, sort of.

> - exists = has_sha1_file(sha1);
> - while (len < GIT_SHA1_HEXSZ) {
> - struct object_id oid_ret;
> - status = get_short_oid(hex, len, _ret, GET_OID_QUIETLY);
> - if (exists
> - ? !status
> - : status == SHORT_NAME_NOT_FOUND) {
> - hex[len] = 0;
> - return len;
> - }
> - len++;
> - }
> - return len;

The "always_call_fn" thing is a big sledgehammer that overrides
everything else in update_candidates().  It bypasses the careful
machinery set up to avoid having to open ambiguous object to learn
their types as much as possible.  One narrow exception when it is OK
to use is if we never limit our candidates with type.

And it might appear that the conversion is safe (if only because we
do not see any type limitation in the get_short_oid() call above),
but I think there is one case where this patch changes the
behaviour: what happens if core.disambiguate was set to anything
other than "none"?  The new code does not know anything about type
based filtering, so it can end up reporting longer abbreviation than
it was asked to produce.  It may not be a problem in practice, though.

I am not sure if setting core.disambiguate is generally a good idea
in the first place, and if it is OK to break find_unique_abbrev()
with respect to the configuration variable like this patch does.

I'd feel safe if we get extra input from Peff, who introduced the
feature in 5b33cb1f ("get_short_sha1: make default disambiguation
configurable", 2016-09-27).

> +
> + if (init_object_disambiguation(hex, len, ) < 0)
> + return -1;
> +
> + mad.init_len = len;
> + mad.cur_len = len;
> + mad.hex = hex;
> +
> + ds.fn = extend_abbrev_len;
> + ds.always_call_fn = 1;
> + ds.cb_data = (void*)
> +
> + find_short_object_filename();
> + find_short_packed_object();
> + (void)finish_object_disambiguation(, _ret);
> +
> + hex[mad.cur_len] = 0;
> + return mad.cur_len;
>  }
>  
>  const char *find_unique_abbrev(const unsigned char *sha1, int len)

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Derrick Stolee]

On 10/3/2017 6:49 AM, Junio C Hamano wrote:

Derrick Stolee  writes:


p0008.1: find_unique_abbrev() for existing objects
--

For 10 repeated tests, each checking 100,000 known objects, we find the
following results when running in a Linux VM:

|   | Pack  | Packed  | Loose  | Base   | New| |
| Repo  | Files | Objects | Objects| Time   | Time   | Rel%|
|---|---|-||||-|
| Git   | 1 |  230078 |  0 | 0.09 s | 0.06 s | - 33.3% |
| Git   | 5 |  230162 |  0 | 0.11 s | 0.08 s | - 27.3% |
| Git   | 4 |  154310 |  75852 | 0.09 s | 0.07 s | - 22.2% |
| Linux | 1 | 5606645 |  0 | 0.12 s | 0.32 s | +146.2% |
| Linux |24 | 5606645 |  0 | 1.12 s | 1.12 s | -  0.9% |
| Linux |23 | 5283204 | 323441 | 1.08 s | 1.05 s | -  2.8% |
| VSTS  | 1 | 4355923 |  0 | 0.12 s | 0.23 s | + 91.7% |
| VSTS  |32 | 4355923 |  0 | 1.02 s | 1.08 s | +  5.9% |
| VSTS  |31 | 4276829 |  79094 | 2.25 s | 2.08 s | -  7.6% |

The above does not look so good, especially in cases where a
repository is well maintained by packing into smaller number of
packs, we get much worse result?
I understand that this patch on its own does not have good numbers. I 
split the

patches 3 and 4 specifically to highlight two distinct changes:

Patch 3: Unroll the len loop that may inspect all files multiple times.
Patch 4: Parse less while disambiguating.

Patch 4 more than makes up for the performance hits in this patch.



p0008.2: find_unique_abbrev() for missing objects
-

For 10 repeated tests, each checking 100,000 missing objects, we find
the following results when running in a Linux VM:

|   | Pack  | Packed  | Loose  | Base   | New||
| Repo  | Files | Objects | Objects| Time   | Time   | Rel%   |
|---|---|-|||||
| Git   | 1 |  230078 |  0 | 0.66 s | 0.08 s | -87.9% |
| Git   | 5 |  230162 |  0 | 0.90 s | 0.13 s | -85.6% |
| Git   | 4 |  154310 |  75852 | 0.79 s | 0.10 s | -87.3% |
| Linux | 1 | 5606645 |  0 | 0.48 s | 0.32 s | -33.3% |
| Linux |24 | 5606645 |  0 | 4.41 s | 1.09 s | -75.3% |
| Linux |23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% |
| VSTS  | 1 | 4355923 |  0 | 0.46 s | 0.25 s | -45.7% |
| VSTS  |32 | 4355923 |  0 | 5.40 s | 1.15 s | -78.7% |
| VSTS  |31 | 4276829 |  79094 | 5.88 s | 1.18 s | -79.9% |

The question is if this is even measuring a relevant workload.  How
often would we have a full 40-hex object name for which we actually
do not have the object, and ask its name to be abbreviated?

Compared to it, the result from p0008.1 feels a lot more important.
We know we make tons of "abbreviate the object name for this object
we have" and we see them every day in our "git log -p" output.

Seeing a lot more impressive result from p0008.2 than p0008.1 makes
me unsure if this patch is optimizing for the right case.

I'll have to see the code a bit deeper before I can comment on it.

Thanks.
I agree that p0008.1 is more important. p0008.2 covers an important case 
of the

previous implementation. The line

    exists = has_sha1_file(sha1);

will inspect all packfiles and scan the full loose-object directory that 
would contain
the object. The only reason for this call is to determine how to inspect 
the result of
get_short_oid(), but is a significant portion of the time that is gained 
here.


Thanks,
-Stolee

Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Junio C Hamano]

Derrick Stolee  writes:

> p0008.1: find_unique_abbrev() for existing objects
> --
>
> For 10 repeated tests, each checking 100,000 known objects, we find the
> following results when running in a Linux VM:
>
> |   | Pack  | Packed  | Loose  | Base   | New| |
> | Repo  | Files | Objects | Objects| Time   | Time   | Rel%|
> |---|---|-||||-|
> | Git   | 1 |  230078 |  0 | 0.09 s | 0.06 s | - 33.3% |
> | Git   | 5 |  230162 |  0 | 0.11 s | 0.08 s | - 27.3% |
> | Git   | 4 |  154310 |  75852 | 0.09 s | 0.07 s | - 22.2% |
> | Linux | 1 | 5606645 |  0 | 0.12 s | 0.32 s | +146.2% |
> | Linux |24 | 5606645 |  0 | 1.12 s | 1.12 s | -  0.9% |
> | Linux |23 | 5283204 | 323441 | 1.08 s | 1.05 s | -  2.8% |
> | VSTS  | 1 | 4355923 |  0 | 0.12 s | 0.23 s | + 91.7% |
> | VSTS  |32 | 4355923 |  0 | 1.02 s | 1.08 s | +  5.9% |
> | VSTS  |31 | 4276829 |  79094 | 2.25 s | 2.08 s | -  7.6% |

The above does not look so good, especially in cases where a
repository is well maintained by packing into smaller number of
packs, we get much worse result?

> p0008.2: find_unique_abbrev() for missing objects
> -
>
> For 10 repeated tests, each checking 100,000 missing objects, we find
> the following results when running in a Linux VM:
>
> |   | Pack  | Packed  | Loose  | Base   | New||
> | Repo  | Files | Objects | Objects| Time   | Time   | Rel%   |
> |---|---|-|||||
> | Git   | 1 |  230078 |  0 | 0.66 s | 0.08 s | -87.9% |
> | Git   | 5 |  230162 |  0 | 0.90 s | 0.13 s | -85.6% |
> | Git   | 4 |  154310 |  75852 | 0.79 s | 0.10 s | -87.3% |
> | Linux | 1 | 5606645 |  0 | 0.48 s | 0.32 s | -33.3% |
> | Linux |24 | 5606645 |  0 | 4.41 s | 1.09 s | -75.3% |
> | Linux |23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% |
> | VSTS  | 1 | 4355923 |  0 | 0.46 s | 0.25 s | -45.7% |
> | VSTS  |32 | 4355923 |  0 | 5.40 s | 1.15 s | -78.7% |
> | VSTS  |31 | 4276829 |  79094 | 5.88 s | 1.18 s | -79.9% |

The question is if this is even measuring a relevant workload.  How
often would we have a full 40-hex object name for which we actually
do not have the object, and ask its name to be abbreviated?

Compared to it, the result from p0008.1 feels a lot more important.
We know we make tons of "abbreviate the object name for this object
we have" and we see them every day in our "git log -p" output.

Seeing a lot more impressive result from p0008.2 than p0008.1 makes
me unsure if this patch is optimizing for the right case.

I'll have to see the code a bit deeper before I can comment on it.

Thanks.

[PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r

[Derrick Stolee]

Unroll the while loop inside find_unique_abbrev_r to avoid iterating
through all loose objects and packfiles multiple times when the short
name is longer than the predicted length.

Instead, inspect each object that collides with the estimated
abbreviation to find the longest common prefix.

p0008.1: find_unique_abbrev() for existing objects
--

For 10 repeated tests, each checking 100,000 known objects, we find the
following results when running in a Linux VM:

|   | Pack  | Packed  | Loose  | Base   | New| |
| Repo  | Files | Objects | Objects| Time   | Time   | Rel%|
|---|---|-||||-|
| Git   | 1 |  230078 |  0 | 0.09 s | 0.06 s | - 33.3% |
| Git   | 5 |  230162 |  0 | 0.11 s | 0.08 s | - 27.3% |
| Git   | 4 |  154310 |  75852 | 0.09 s | 0.07 s | - 22.2% |
| Linux | 1 | 5606645 |  0 | 0.12 s | 0.32 s | +146.2% |
| Linux |24 | 5606645 |  0 | 1.12 s | 1.12 s | -  0.9% |
| Linux |23 | 5283204 | 323441 | 1.08 s | 1.05 s | -  2.8% |
| VSTS  | 1 | 4355923 |  0 | 0.12 s | 0.23 s | + 91.7% |
| VSTS  |32 | 4355923 |  0 | 1.02 s | 1.08 s | +  5.9% |
| VSTS  |31 | 4276829 |  79094 | 2.25 s | 2.08 s | -  7.6% |

For the Windows repo running in Windows Subsystem for Linux:

Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
 Base Time: 5.69 s
  New Time: 4.62 s
 Rel %: -18.9%

p0008.2: find_unique_abbrev() for missing objects
-

For 10 repeated tests, each checking 100,000 missing objects, we find
the following results when running in a Linux VM:

|   | Pack  | Packed  | Loose  | Base   | New||
| Repo  | Files | Objects | Objects| Time   | Time   | Rel%   |
|---|---|-|||||
| Git   | 1 |  230078 |  0 | 0.66 s | 0.08 s | -87.9% |
| Git   | 5 |  230162 |  0 | 0.90 s | 0.13 s | -85.6% |
| Git   | 4 |  154310 |  75852 | 0.79 s | 0.10 s | -87.3% |
| Linux | 1 | 5606645 |  0 | 0.48 s | 0.32 s | -33.3% |
| Linux |24 | 5606645 |  0 | 4.41 s | 1.09 s | -75.3% |
| Linux |23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% |
| VSTS  | 1 | 4355923 |  0 | 0.46 s | 0.25 s | -45.7% |
| VSTS  |32 | 4355923 |  0 | 5.40 s | 1.15 s | -78.7% |
| VSTS  |31 | 4276829 |  79094 | 5.88 s | 1.18 s | -79.9% |

For the Windows repo running in Windows Subsystem for Linux:

Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
 Base Time: 39.0 s
  New Time:  3.9 s
 Rel %: -90.0%

Signed-off-by: Derrick Stolee 
---
 sha1_name.c | 57 ++---
 1 file changed, 42 insertions(+), 15 deletions(-)

diff --git a/sha1_name.c b/sha1_name.c
index 134ac9742..f2a1ebe49 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -474,10 +474,32 @@ static unsigned msb(unsigned long val)
return r;
 }
 
-int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
+struct min_abbrev_data {
+   unsigned int init_len;
+   unsigned int cur_len;
+   char *hex;
+};
+
+static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 {
-   int status, exists;
+   struct min_abbrev_data *mad = cb_data;
+
+   char *hex = oid_to_hex(oid);
+   unsigned int i = mad->init_len;
+   while (mad->hex[i] && mad->hex[i] == hex[i])
+   i++;
+
+   if (i < GIT_MAX_RAWSZ && i >= mad->cur_len)
+   mad->cur_len = i + 1;
+
+   return 0;
+}
 
+int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
+{
+   struct disambiguate_state ds;
+   struct min_abbrev_data mad;
+   struct object_id oid_ret;
if (len < 0) {
unsigned long count = approximate_object_count();
/*
@@ -503,19 +525,24 @@ int find_unique_abbrev_r(char *hex, const unsigned char 
*sha1, int len)
sha1_to_hex_r(hex, sha1);
if (len == GIT_SHA1_HEXSZ || !len)
return GIT_SHA1_HEXSZ;
-   exists = has_sha1_file(sha1);
-   while (len < GIT_SHA1_HEXSZ) {
-   struct object_id oid_ret;
-   status = get_short_oid(hex, len, _ret, GET_OID_QUIETLY);
-   if (exists
-   ? !status
-   : status == SHORT_NAME_NOT_FOUND) {
-   hex[len] = 0;
-   return len;
-   }
-   len++;
-   }
-   return len;
+
+   if (init_object_disambiguation(hex, len, ) < 0)
+   return -1;
+
+   mad.init_len = len;
+   mad.cur_len = len;
+   mad.hex = hex;
+
+   ds.fn = extend_abbrev_len;
+   ds.always_call_fn = 1;
+   ds.cb_data = (void*)
+
+   find_short_object_filename();
+   find_short_packed_object();
+