v2, 5 partsImprove abbreviation disambiguation

Thanks for the feedback on my v1 patch. Thanks also to Jeff Hostetler for helping me with this v2 patch, which includes an extra performance improvement in commit 5.

Changes since last version:

* Added helper program test-list-objects to construct a list of
  existing object ids.

* test-abbrev now disambiguates a list of OIDs from stdin.

* p0008-abbrev.sh now has two tests:
    * 0008.1 tests 100,000 known OIDs
    * 0008.2 tests 100,000 missing OIDs

* Added a third performance improvement that uses binary search within
  packfiles to inspect at most two object ids per packfile.

Thanks,
 Stolee

---

When displaying object ids, we frequently want to see an abbreviation for easier typing. That abbreviation must be unambiguous among all object ids.

The current implementation of find_unique_abbrev() performs a loop checking if each abbreviation length is unambiguous until finding one that works. This causes multiple round-trips to the disk when starting with the default abbreviation length (usually 7) but needing up to 12 characters for an unambiguous short-sha. For very large repos, this effect is pronounced and causes issues with several commands, from obvious consumers `status` and `log` to less obvious commands such as `fetch` and `push`.

This patch improves performance by iterating over objects matching the short abbreviation only once, inspecting each object id, and reporting the minimum length of an unambiguous abbreviation.

A helper program `test-list-objects` outputs a sampling of object ids, which we reorder using `sort -R` before using them as input to a performance test.

A performance helper `test-abbrev` and performance test `p0008-abbrev.sh` are added to demonstrate performance improvements in this area.

I include performance test numbers in the commit messages for each change, but I also include the difference between the baseline and the final change here:

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.12 s | 0.05 s | -58.3% |
| Git   |     5 |  230162 |      0 | 0.25 s | 0.15 s | -40.0% |
| Git   |     4 |  154310 |  75852 | 0.18 s | 0.11 s | -38.9% |
| Linux |     1 | 5606645 |      0 | 0.32 s | 0.10 s | -68.8% |
| Linux |    24 | 5606645 |      0 | 2.77 s | 2.00 s | -27.8% |
| Linux |    23 | 5283204 | 323441 | 2.86 s | 1.62 s | -43.4% |
| VSTS  |     1 | 4355923 |      0 | 0.27 s | 0.09 s | -66.7% |
| VSTS  |    32 | 4355923 |      0 | 2.41 s | 2.01 s | -16.6% |
| VSTS  |    31 | 4276829 |  79094 | 4.22 s | 3.02 s | -28.4% |

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.09 s
         Rel %: -28.1%

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.61 s | 0.04 s | -93.4% |
| Git   |     5 |  230162 |      0 | 1.30 s | 0.15 s | -88.5% |
| Git   |     4 |  154310 |  75852 | 1.07 s | 0.12 s | -88.8% |
| Linux |     1 | 5606645 |      0 | 0.65 s | 0.05 s | -92.3% |
| Linux |    24 | 5606645 |      0 | 7.12 s | 1.28 s | -82.0% |
| Linux |    23 | 5283204 | 323441 | 6.33 s | 0.96 s | -84.8% |
| VSTS  |     1 | 4355923 |      0 | 0.64 s | 0.05 s | -92.2% |
| VSTS  |    32 | 4355923 |      0 | 7.77 s | 1.36 s | -82.5% |
| VSTS  |    31 | 4276829 |  79094 | 7.76 s | 1.36 s | -82.5% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 38.9 s
      New Time:  2.7 s
         Rel %: -93.1%

Derrick Stolee (5):
  test-list-objects: List a subset of object ids
  p0008-abbrev.sh: Test find_unique_abbrev() perf
  sha1_name: Unroll len loop in find_unique_abbrev_r
  sha1_name: Parse less while finding common prefix
  sha1_name: Minimize OID comparisons during disambiguation

 Makefile                     |   2 +
 sha1_name.c                  | 128 ++++++++++++++++++++++++++++++++++++++-----
 t/helper/.gitignore          |   2 +
 t/helper/test-abbrev.c       |  19 +++++++
 t/helper/test-list-objects.c |  85 ++++++++++++++++++++++++++++
 t/perf/p0008-abbrev.sh       |  22 ++++++++
 6 files changed, 243 insertions(+), 15 deletions(-)
 create mode 100644 t/helper/test-abbrev.c
 create mode 100644 t/helper/test-list-objects.c
 create mode 100755 t/perf/p0008-abbrev.sh

Create helper program test-abbrev to compute the minimum length of a disambiguating short-sha for an input list of object ids.

Perf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For test 0008.1, these objects exist. For test 0008.2 these objects do not exist in the repo (with high probability). For each test, use `sort -R` to (deterministically) shuffle the sample of object ids to not check abbreviations in lexicographic order.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Makefile               |  1 +
 t/helper/.gitignore    |  1 +
 t/helper/test-abbrev.c | 19 +++++++++++++++++++
 t/perf/p0008-abbrev.sh | 22 ++++++++++++++++++++++
 4 files changed, 43 insertions(+)
 create mode 100644 t/helper/test-abbrev.c
 create mode 100755 t/perf/p0008-abbrev.sh

Derrick Stolee <dstolee@microsoft.com> writes:

Same comment on <stdio.h> as [1/5] applies.

Why +2 (as opposed to +1)?

I thought "sort randomly" was a GNUism. Does it work across platforms? I think not.

On Mon, Sep 25, 2017 at 05:54:49AM -0400, Derrick Stolee wrote:

This seems like something that Git ought to be able to do via real commands.

Using "log --stdin --no-walk --format=%h" doesn't quite work, since it only handles commits. We ought to be able to ask "cat-file" for this, though. E.g., with the patch below you can do:

  git cat-file --batch-check='%(objectsize:short)' <input

Or even just dispense with your earlier randomization helper and do:

  git cat-file --batch-all-objects --batch-check='%(objectsize:short)'

to compute the abbreviation for every object.

I know you're not the first to add a test like this, but I'm somewhat negative on these sorts of micro-benchmark perf tests. They're nice for showing off an improvement, but there's little indication of how they impact things that users actually do.

We know that this series makes finding abbreviations cheaper. But how much does it speed up "git log --oneline" on a real repository (including absurdly-sized ones)?

-Peff

On Thu, Oct 05, 2017 at 04:55:53AM -0400, Jeff King wrote:

Of course it would help if I bothered to include the patch. Here it is.

Minimize OID comparisons during disambiguatiosn of packfile OIDs.

Teach git to use binary search with the full OID to find the object's position (or insertion position, if not present) in the pack-index. The object before and immediately after (or the one at the insertion position) give the maximum common prefix. No subsequent linear search is required.

Take care of which two to inspect, in case the object id exists in the packfile.

If the input to find_unique_abbrev_r() is a partial prefix, then the OID used for the binary search is padded with zeroes so the object will not exist in the repo (with high probability) and the same logic applies.

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.08 s | 0.05 s | -37.5% |
| Git   |     5 |  230162 |      0 | 0.16 s | 0.15 s | - 6.3% |
| Git   |     4 |  154310 |  75852 | 0.12 s | 0.11 s | - 8.3% |
| Linux |     1 | 5606645 |      0 | 0.25 s | 0.10 s | -60.0% |
| Linux |    24 | 5606645 |      0 | 2.08 s | 2.00 s | - 3.8% |
| Linux |    23 | 5283204 | 323441 | 1.69 s | 1.62 s | - 4.1% |
| VSTS  |     1 | 4355923 |      0 | 0.22 s | 0.09 s | -59.1% |
| VSTS  |    32 | 4355923 |      0 | 1.99 s | 2.01 s | + 1.0% |
| VSTS  |    31 | 4276829 |  79094 | 3.20 s | 3.02 s | - 5.6% |

For the Windows repo running in Windows Subsystem for Linux:

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

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.05 s | 0.04 s | -20.0% |
| Git   |     5 |  230162 |      0 | 0.15 s | 0.15 s |   0.0% |
| Git   |     4 |  154310 |  75852 | 0.12 s | 0.12 s |   0.0% |
| Linux |     1 | 5606645 |      0 | 0.17 s | 0.05 s | -70.6% |
| Linux |    24 | 5606645 |      0 | 1.30 s | 1.28 s | - 1.5% |
| Linux |    23 | 5283204 | 323441 | 1.10 s | 0.96 s | -12.7% |
| VSTS  |     1 | 4355923 |      0 | 0.12 s | 0.05 s | -58.3% |
| VSTS  |    32 | 4355923 |      0 | 1.34 s | 1.36 s | + 1.5% |
| VSTS  |    31 | 4276829 |  79094 | 1.34 s | 1.36 s | + 1.5% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 3.08 s
      New Time: 2.72 s
         Rel %: -11.8

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 66 insertions(+), 4 deletions(-)

Create test-list-objects helper program to output a random sample of OIDs present in the repo.

If no command line arguments are provided, all OIDs are output.

The first command line argument specifies how many samples to output. Samples are collected across the entire set of available OIDs to avoid clustering and therefore quite uniformly distributed.

If a second command line argument "--missing" is given, then a list of OIDs is generated without examining the repo.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Makefile                     |  1 +
 t/helper/.gitignore          |  1 +
 t/helper/test-list-objects.c | 85 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 87 insertions(+)
 create mode 100644 t/helper/test-list-objects.c

Derrick Stolee <dstolee@microsoft.com> writes:

If you include "cache.h", like the ordinary "git" program, you should not have to include any system headers like stdio.h yourself. The whole point of "git-compat-util.h must be the first to be included (indirectly including it via cache.h and friends is also OK)" rule is to make sure that system headers are included at the right place in the include sequence (e.g. defining feature macros before including certain headers, etc.).

Because the above will not work as you expect, unless your uint is 32-bit, you would probably want to make hash_delt and hash_base explicitly uint32_t, I think.

Alternatively, because you assume that uint is at least 8-hex-digit wide in the output loop, you can keep "unsigned int" above, but change the divisor from sizeof(unsigned int) to a hardcoded 4.

Either would fix the issue.

Otherwise n will stay 0 as initialized. Not checking the result of atoi() is probably permissible, as this is merely a test helper and we can assume that the caller will not do anything silly, like passing "-3" in av[1]. But it certainly would be a good discipline to make sure av[1] is a reasonable number.

I am afraid that I may be misreading the code, but the following code seems to require that the caller must know roughly how many objects there are (so that a large-enough value can be passed to av[1] to force c.select_mod to 1) when it wants to show everything, as the "missing" loop will run 0 times showing nothing, and "listing" case will divide by zero.

"Not passing anything will show everything" the proposed log message promises is a better design than what the code actually seems to be doing.

When n==0, this does nothing. I am not sure what the desired behaviour should be for "When no count is given, we show everything" in this codepath, though.

Also, doesn't "test-list-objects 5 --missing" look very wrong? Shouldn't it be more like "test-list-objects --missing 5"?

When n==0, this would divide by zero. Perhaps

		c.select_mod = n ? (1 + c.total / n) : 1;

or something to keep the promise of showing everything?

Thanks.

On Mon, Sep 25, 2017 at 05:54:48AM -0400, Derrick Stolee wrote:

This is weirdly specific. Can we accomplish the same thing with existing tools?

E.g., could:

  git cat-file --batch-all-objects --batch-check='%(objectname)' |
  shuffle |
  head -n 100

do the same thing?

I know that "shuffle" isn't available everywhere, but I'd much rather see us fill in portability gaps in a general way, rather than introducing one-shot C code that needs to be maintained (and you wouldn't _think_ that t/helper programs need much maintenance, but try perusing "git log t/helper" output; they have to adapt to the same tree-wide changes as the rest of the code).

-Peff

Jeff King <peff@peff.net> writes:

I was thinking about this a bit more, and came to the conclusion that "sort -R" and "shuf" are wrong tools to use. We would want to measure with something close to real world workload. for example, letting

	git rev-list --all --objects

produce the listof objects in traversal order (i.e. this is very similar to the order in which "git log -p" needs to access the objects) and chomping at the number of sample objects you need in your test would give you such a list.

On Thu, Oct 05, 2017 at 06:48:10PM +0900, Junio C Hamano wrote:

Actually, I'd just as soon see timings for "git log --format=%h" or "git log --raw", as opposed to patches 1 and 2.

You won't see a 90% speedup there, but you will see the actual improvement that real-world users are going to experience, which is way more important, IMHO.

-Peff

On Thu, Oct 5, 2017 at 7:00 PM, Jeff King <peff@peff.net> wrote:

Yup, "log --raw -r" would really exercise the abbreviation machinery without spending time on the diff machinery, and it would be a good test.

On 10/5/2017 6:00 AM, Jeff King wrote:

Thanks for thinking hard about this.

For some real-user context: Some engineers using Git for the Windows repo were seeing extremely slow commands, such as 'fetch' or 'commit', and when we took a trace we saw most of the time spinning in this abbreviation code. Our workaround so far has been to set core.abbrev=40.

I'll run some perf numbers for these commands you recommend, and also see if I can replicate some of the pain points that triggered this change using the Linux repo.

Thanks, -Stolee

On Thu, Oct 05, 2017 at 08:39:42AM -0400, Derrick Stolee wrote:

That's surprising to me. I'd expect fetch to generate up to two abbreviations per fetched ref (for the status table). And for commit to generate only one for the summary. But maybe it was just so painfully slow on your repo that it was noticeable.

If there's a case where we're generating a bunch of abbreviated oids, that might be worth looking into. Do you happen to have a stack trace of one of the slow cases showing who is calling into the function?

I actually wondered about this. With the new auto-scaling, we'd typically jump straight to 12 or 13 hex-chars on a large repo, and that would be sufficient. So we'd really only need one iteration of the loop.

Thanks!

-Peff

On 10/6/2017 10:11 AM, Jeff King wrote:

In my local copy, I added a test to p4211-line-log.sh that runs "git log --raw -r" and tested it on three copies of the Linux repo. In order, they have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles (~324,000 loose).

4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6% 4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1% 4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%

We have moderate performance gains for this command, despite the command doing many more things than just checking abbreviations.

I plan to re-roll my patch on Monday including the following feedback items:

* Remove test-list-objects and test-abbrev in favor of a new "git log"
   performance test.

* Fix binary search overflow error.

* Check response from open_pack_index(p) in find_abbrev_len_for_pack().
   I plan to return without failure on non-zero result, which results in
   no failure on a bad pack and the abbreviation length will be the
   minimum required among all valid packs. (Thanks Stefan!)

I made note of a few things, but will not include them in my re-roll. I'll revisit them later if they are valuable:

- nth_packed_object_sha1() could be simplified in
   find_abbrev_len_for_pack().

- Teach 'cat-file' to --batch-check='%(objectsize:short)'. (Peff already
   included a patch, perhaps that could be reviewed separately.)

- Ramsay caught my lack of "static" in test-list-objects.c, but that
   file will be removed in the next patch. I'll make sure to use "static"
   in the future.

I'm not re-rolling immediately to allow for some extra review over the weekend, if anyone is so inclined.

Thanks, -Stolee

On Sat, Oct 07, 2017 at 03:12:08PM -0400, Derrick Stolee wrote:

Yeah, while it's less exciting than seeing the 90% numbers for a micro-benchmark, I think this represents real-world gains (and 5-7% is nothing to sneeze at).

You might also try adding "--format=%h" or --oneline to your invocation, which would compute abbreviations for each commit (making your workload more abbrev-heavy and possibly showing off the difference more).

I also think "-r" isn't doing anything. Recursive diffs are the default for the "log" porcelain (even for --raw).

That all sounds reasonable to me.

I think I'll let it lie in the list archive for now unless somebody has a real use case for it (though I'm tempted to add it purely for completionism, since it's so easy).

-Peff

Jeff King <peff@peff.net> writes:

Yes! I would even say 5-7% is much better than "nothing to sneeze at". We do prefer workload closer to the real-world usage over micro benchmarks, and consider changes that gain by a few percent as real improvements.

Again, agreed, and I would not consider it would be inflating the benchmark artificially in favor of the change. "log --oneline" is not something people use rarely---I'd think it would be quite a normal thing to do.

That's my fault writing "-r" ;-) Together with your "log --oneline" suggestion,

	git log --oneline --raw

would be a reasonable thing to measure.

Thanks, both.

Create get_hex_char_from_oid() to parse oids one hex character at a time. This prevents unnecessary copying of hex characters in extend_abbrev_len() when finding the length of a 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.08 s | 0.08 s |   0.0% |
| Git   |     5 |  230162 |      0 | 0.17 s | 0.16 s | - 5.9% |
| Git   |     4 |  154310 |  75852 | 0.14 s | 0.12 s | -14.3% |
| Linux |     1 | 5606645 |      0 | 0.50 s | 0.25 s | -50.0% |
| Linux |    24 | 5606645 |      0 | 2.41 s | 2.08 s | -13.7% |
| Linux |    23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% |
| VSTS  |     1 | 4355923 |      0 | 0.40 s | 0.22 s | -45.0% |
| VSTS  |    32 | 4355923 |      0 | 2.09 s | 1.99 s | - 4.8% |
| VSTS  |    31 | 4276829 |  79094 | 3.60 s | 3.20 s | -11.1% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 4.61 s
      New Time: 4.61 s
         Rel %: 0.0%

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.06 s | 0.05 s | -16.7% |
| Git   |     5 |  230162 |      0 | 0.14 s | 0.15 s | + 7.1% |
| Git   |     4 |  154310 |  75852 | 0.12 s | 0.12 s |   0.0% |
| Linux |     1 | 5606645 |      0 | 0.40 s | 0.17 s | -57.5% |
| Linux |    24 | 5606645 |      0 | 1.59 s | 1.30 s | -18.2% |
| Linux |    23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% |
| VSTS  |     1 | 4355923 |      0 | 0.25 s | 0.12 s | -52.0% |
| VSTS  |    32 | 4355923 |      0 | 1.45 s | 1.34 s | - 7.6% |
| VSTS  |    31 | 4276829 |  79094 | 1.59 s | 1.34 s | -15.7% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 3.91 s
      New Time: 3.08 s
         Rel %: -21.1%

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sha1_name.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stolee <dstolee@microsoft.com> wrote:

These number look pretty cool!

double signoff?

'i' is not very descriptive, maybe add a comment? (I realize it is just walking through the char*s one by one)

Maybe this function (together with the change in the while below) could go into hex.c as "int progressively_cmp_oids" that returns the position at which the given oids differ?

sha1_to_hex_r has very similar code, though it iterates less and covers both cases in the loop body.

That is the actual reason I propose moving this function (or a variant thereof) to hex.c as there we can share code.

My v3 patch is incoming, but I wanted to respond directly to this message.

On 9/25/2017 7:42 PM, Stefan Beller wrote:

Oops! I'll be more careful with my format-patch in the future.

I renamed 'i' to 'pos' in my v3.

You're right that sha1_to_hex_r is similar, in fact I based my work on it. There are a few reasons I didn't combine the two implementations:

* I wanted to be sure my patch was only touching the code for 
disambiguating short-shas. Modifying code in hex.c would touch many more 
code paths.

* I realize that the extra branch in my version is slower than the 
branchless loop body in sha1_to_hex_r, so either I would slow that 
method or make the method call more complicated by returning two chars 
at a time.

* I wanted to strongly hint that the method should be inlined, but I'm 
not sure how to guarantee that happens across a linker boundary without 
doing strange things in header files.

I'm happy to revisit this after my patch is complete, since I think there are interesting trade-offs to consider here. I'd prefer to keep this discussion separate from the focus on disambiguation.

Thanks, -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.12 s | 0.08 s | -33.3% |
| Git   |     5 |  230162 |      0 | 0.25 s | 0.17 s | -32.0% |
| Git   |     4 |  154310 |  75852 | 0.18 s | 0.14 s | -22.2% |
| Linux |     1 | 5606645 |      0 | 0.32 s | 0.50 s | +56.2% |
| Linux |    24 | 5606645 |      0 | 2.77 s | 2.41 s | -13.0% |
| Linux |    23 | 5283204 | 323441 | 2.86 s | 1.99 s | -30.4% |
| VSTS  |     1 | 4355923 |      0 | 0.27 s | 0.40 s | +48.1% |
| VSTS  |    32 | 4355923 |      0 | 2.41 s | 2.09 s | -13.3% |
| VSTS  |    31 | 4276829 |  79094 | 4.22 s | 3.60 s | -14.7% |

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.61 s | 0.06 s | -90.2% |
| Git   |     5 |  230162 |      0 | 1.30 s | 0.14 s | -89.2% |
| Git   |     4 |  154310 |  75852 | 1.07 s | 0.12 s | -88.8% |
| Linux |     1 | 5606645 |      0 | 0.65 s | 0.40 s | -38.5% |
| Linux |    24 | 5606645 |      0 | 7.12 s | 1.59 s | -77.7% |
| Linux |    23 | 5283204 | 323441 | 6.33 s | 1.23 s | -80.6% |
| VSTS  |     1 | 4355923 |      0 | 0.64 s | 0.25 s | -60.9% |
| VSTS  |    32 | 4355923 |      0 | 7.77 s | 1.45 s | -81.3% |
| VSTS  |    31 | 4276829 |  79094 | 7.76 s | 1.59 s | -79.5% |

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 <dstolee@microsoft.com>

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 42 insertions(+), 15 deletions(-)

Create test-list-objects helper program to output a random sample of OIDs present in the repo.

If no command line arguments are provided, all OIDs are output.

The last command line argument specifies how many samples to output. Samples are collected across the entire set of available OIDs to avoid clustering and therefore quite uniformly distributed.

If a command line argument "--missing" is given before the sample count, then a list of OIDs is generated without examining the repo.

    Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Makefile                     |  1 +
 t/helper/.gitignore          |  1 +
 t/helper/test-list-objects.c | 87 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 89 insertions(+)
 create mode 100644 t/helper/test-list-objects.c

Derrick Stolee <dstolee@microsoft.com> writes:

Style nit: s/List/list/;

This should stick to the left hand side.

No need to resend, only to fix these two, as I'll tweak them when queuing.

Create helper program test-abbrev to compute the minimum length of a disambiguating short-sha for an input list of object ids.

Perf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For test 0008.1, these objects exist. For test 0008.2 these objects do not exist in the repo (with high probability).

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Makefile               |  1 +
 t/helper/.gitignore    |  1 +
 t/helper/test-abbrev.c | 18 ++++++++++++++++++
 t/perf/p0008-abbrev.sh | 22 ++++++++++++++++++++++
 4 files changed, 42 insertions(+)
 create mode 100644 t/helper/test-abbrev.c
 create mode 100755 t/perf/p0008-abbrev.sh

Thanks for the feedback on my previous versions, and for patience with my inexperience on the mailing list. I tried to respond to all feedback, but decided to not apply one suggestion:

* Removed the "sort -R" from p0008-abbrev.sh, since it is a GNU-
  specific flag. The perf test now considers objects in "discovery"
  order, which improved performance all versions of the test as
  expected. New perf numbers are provided.

* get_hex_char_from_oid(): renamed `i` to `pos`. I did not unify the
  code in this method with that in hex.c:sha1_to_hex_r due to the
  extra branch in get_hex_char_from_oid and wanting to inline the
  method. If we want to make this method available for other callers,
  then I would be happy to submit a separate patch for this change
  after the current patch is accepted.

* Removed unecessary includes.

* Use uint32_t instead of unsigned int in test-list-objects.c

* Rearranged arguments in test-list-objects and fixed the n == 0 bug.

---

When displaying object ids, we frequently want to see an abbreviation for easier typing. That abbreviation must be unambiguous among all object ids.

The current implementation of find_unique_abbrev() performs a loop checking if each abbreviation length is unambiguous until finding one that works. This causes multiple round-trips to the disk when starting with the default abbreviation length (usually 7) but needing up to 12 characters for an unambiguous short-sha. For very large repos, this effect is pronounced and causes issues with several commands, from obvious consumers `status` and `log` to less obvious commands such as `fetch` and `push`.

This patch improves performance by iterating over objects matching the short abbreviation only once, inspecting each object id, and reporting the minimum length of an unambiguous abbreviation.

A helper program `test-list-objects` outputs a sampling of object ids, which we reorder using `sort -R` before using them as input to a performance test.

A performance helper `test-abbrev` and performance test `p0008-abbrev.sh` are added to demonstrate performance improvements in this area.

I include performance test numbers in the commit messages for each change, but I also include the difference between the baseline and the final change here:

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.05 s | -44.4% |
| Git   |     5 |  230162 |      0 | 0.11 s | 0.08 s | -27.3% |
| Git   |     4 |  154310 |  75852 | 0.09 s | 0.06 s | -33.3% |
| Linux |     1 | 5606645 |      0 | 0.13 s | 0.05 s | -61.5% |
| Linux |    24 | 5606645 |      0 | 1.13 s | 0.88 s | -22.1% |
| Linux |    23 | 5283204 | 323441 | 1.08 s | 0.80 s | -25.9% |
| VSTS  |     1 | 4355923 |      0 | 0.12 s | 0.05 s | -58.3% |
| VSTS  |    32 | 4355923 |      0 | 1.02 s | 0.95 s | - 6.9% |
| VSTS  |    31 | 4276829 |  79094 | 2.25 s | 1.93 s | -14.2% |

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.09 s
         Rel %: -28.1%

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.07 s | -89.4% |
| Git   |     5 |  230162 |      0 | 0.90 s | 0.12 s | -86.7% |
| Git   |     4 |  154310 |  75852 | 0.79 s | 0.09 s | -88.6% |
| Linux |     1 | 5606645 |      0 | 0.48 s | 0.04 s | -91.7% |
| Linux |    24 | 5606645 |      0 | 4.41 s | 0.85 s | -80.7% |
| Linux |    23 | 5283204 | 323441 | 4.11 s | 0.78 s | -81.0% |
| VSTS  |     1 | 4355923 |      0 | 0.46 s | 0.04 s | -91.3% |
| VSTS  |    32 | 4355923 |      0 | 5.40 s | 0.98 s | -81.9% |
| VSTS  |    31 | 4276829 |  79094 | 5.88 s | 1.04 s | -82.3% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 38.9 s
      New Time:  2.7 s
         Rel %: -93.1%

Derrick Stolee (5):
  test-list-objects: List a subset of object ids
  p0008-abbrev.sh: Test find_unique_abbrev() perf
  sha1_name: Unroll len loop in find_unique_abbrev_r
  sha1_name: Parse less while finding common prefix
  sha1_name: Minimize OID comparisons during disambiguation
 Makefile                     |   2 +
 sha1_name.c                  | 129 ++++++++++++++++++++++++++++++++++++++-----
 t/helper/.gitignore          |   2 +
 t/helper/test-abbrev.c       |  18 ++++++
 t/helper/test-list-objects.c |  87 +++++++++++++++++++++++++++++
 t/perf/p0008-abbrev.sh       |  22 ++++++++
 6 files changed, 245 insertions(+), 15 deletions(-)
 create mode 100644 t/helper/test-abbrev.c
 create mode 100644 t/helper/test-list-objects.c
 create mode 100755 t/perf/p0008-abbrev.sh

On Mon, Oct 02, 2017 at 10:56:46AM -0400, Derrick Stolee wrote:

For what it's worth, the optimizations here look sound overall. Like Junio, I was concerned at the loss of performance from patch 3 at first. After looking at your numbers, though, I think it really is just the cost of oid_to_hex() that is then eliminated in patch 4.

I had a few nits to pick on the perf-test setup, but I stupidly sent them in response to v2 (and so missed cc-ing several folks involved in review). I think they apply equally to v3, though.

-Peff

Create get_hex_char_from_oid() to parse oids one hex character at a time. This prevents unnecessary copying of hex characters in extend_abbrev_len() when finding the length of a 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.06 s | 0.05 s | -16.7% |
| Git   |     5 |  230162 |      0 | 0.08 s | 0.08 s |   0.0% |
| Git   |     4 |  154310 |  75852 | 0.07 s | 0.06 s | -14.3% |
| Linux |     1 | 5606645 |      0 | 0.32 s | 0.14 s | -56.3% |
| Linux |    24 | 5606645 |      0 | 1.12 s | 0.94 s | -16.1% |
| Linux |    23 | 5283204 | 323441 | 1.05 s | 0.86 s | -18.1% |
| VSTS  |     1 | 4355923 |      0 | 0.23 s | 0.11 s | -52.2% |
| VSTS  |    32 | 4355923 |      0 | 1.08 s | 0.95 s | -12.0% |
| VSTS  |    31 | 4276829 |  79094 | 2.08 s | 1.82 s | -12.5% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 4.61 s
      New Time: 4.61 s
         Rel %: 0.0%

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.08 s | 0.07 s | -12.5% |
| Git   |     5 |  230162 |      0 | 0.13 s | 0.12 s | - 7.7% |
| Git   |     4 |  154310 |  75852 | 0.10 s | 0.09 s | -10.0% |
| Linux |     1 | 5606645 |      0 | 0.32 s | 0.13 s | -59.4% |
| Linux |    24 | 5606645 |      0 | 1.09 s | 0.89 s | -18.3% |
| Linux |    23 | 5283204 | 323441 | 0.99 s | 0.83 s | -16.2% |
| VSTS  |     1 | 4355923 |      0 | 0.25 s | 0.11 s | -56.0% |
| VSTS  |    32 | 4355923 |      0 | 1.15 s | 0.99 s | -13.9% |
| VSTS  |    31 | 4276829 |  79094 | 1.18 s | 1.02 s | -13.6% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 3.91 s
      New Time: 3.08 s
         Rel %: -21.1%

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sha1_name.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

Derrick Stolee <dstolee@microsoft.com> writes:

Assuming that [PATCH 3/5] makes sense, it is an obvious optimization to avoid writing the whole 20-byte out before comparing, and instead to grab hex digits as they become needed.

I assume that the "Base Time" in the log message was with whatever version of Git before [PATCH 3/5] and this one were applied (i.e. not comparing to "vanilla Git plus 3/5")?

Thanks.

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 <dstolee@microsoft.com>
---
 sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 42 insertions(+), 15 deletions(-)

Derrick Stolee <dstolee@microsoft.com> writes:

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?

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.

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

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.

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

Derrick Stolee <stolee@gmail.com> writes:

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?

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

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

Derrick Stolee <dstolee@microsoft.com> writes:

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.

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).

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

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.

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 look forward to more feedback. Thanks for taking the time to look at my patch series.

Thanks, -Stolee

Derrick Stolee <stolee@gmail.com> writes:

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.

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

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

Jeff King <peff@peff.net> writes:

OK.  Thanks for sanity checking.

Minimize OID comparisons during disambiguatiosn of packfile OIDs.

Teach git to use binary search with the full OID to find the object's position (or insertion position, if not present) in the pack-index. The object before and immediately after (or the one at the insertion position) give the maximum common prefix. No subsequent linear search is required.

Take care of which two to inspect, in case the object id exists in the packfile.

If the input to find_unique_abbrev_r() is a partial prefix, then the OID used for the binary search is padded with zeroes so the object will not exist in the repo (with high probability) and the same logic applies.

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.05 s | 0.05 s |   0.0% |
| Git   |     5 |  230162 |      0 | 0.08 s | 0.08 s |   0.0% |
| Git   |     4 |  154310 |  75852 | 0.06 s | 0.06 s |   0.0% |
| Linux |     1 | 5606645 |      0 | 0.14 s | 0.05 s | -64.3% |
| Linux |    24 | 5606645 |      0 | 0.94 s | 0.88 s | - 6.4% |
| Linux |    23 | 5283204 | 323441 | 0.86 s | 0.80 s | - 7.0% |
| VSTS  |     1 | 4355923 |      0 | 0.11 s | 0.05 s | -54.5% |
| VSTS  |    32 | 4355923 |      0 | 0.95 s | 0.95 s |   0.0% |
| VSTS  |    31 | 4276829 |  79094 | 1.82 s | 1.93 s | + 6.0% |

For the Windows repo running in Windows Subsystem for Linux:

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

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.07 s | 0.07 s |   0.0% |
| Git   |     5 |  230162 |      0 | 0.12 s | 0.12 s |   0.0% |
| Git   |     4 |  154310 |  75852 | 0.09 s | 0.09 s |   0.0% |
| Linux |     1 | 5606645 |      0 | 0.13 s | 0.04 s | -69.2% |
| Linux |    24 | 5606645 |      0 | 0.89 s | 0.85 s | - 4.5% |
| Linux |    23 | 5283204 | 323441 | 0.83 s | 0.78 s | - 6.0% |
| VSTS  |     1 | 4355923 |      0 | 0.11 s | 0.04 s | -63.6% |
| VSTS  |    32 | 4355923 |      0 | 0.99 s | 0.98 s | - 1.0% |
| VSTS  |    31 | 4276829 |  79094 | 1.02 s | 1.04 s | + 2.0% |

For the Windows repo running in Windows Subsystem for Linux:

    Pack Files: 50
Packed Objects: 22,385,898
 Loose Objects: 492
     Base Time: 3.08 s
      New Time: 2.72 s
         Rel %: -11.8

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 66 insertions(+), 4 deletions(-)

coverity complained here with
    Calling "open_pack_index" without checking return value
    (as is done elsewhere 13 out of 15 times).

I think the easiest way out is just a

    if (open_pack_index(p))
        die(_("Cannot open existing pack idx file for '%s'"), p);

or is there another good approach?

On 10/3/2017 11:55 AM, Stefan Beller wrote:

Good catch! This same line is repeated in unique_in_pack() in this same file, so if this is worth fixing then we should probably fix it there, too.

You probably intended to have p->pack_name in the die();

Using `cat *.c | grep -A 2 "if (open_pack_index("` and `cat */*.c | grep -A 2 "if (open_pack_index("` I see a few places that return error codes or quietly fail. The cases that use die() are inside builtin/ so I don't think die() is the right choice here.

Since find_abbrev_len_for_pack() is intended to extend the abbreviation length when necessary, I think a silent return is best here:

     if (open_pack_index(p))
         return;

Thanks, -Stolee

On Mon, Oct 02, 2017 at 10:56:51AM -0400, Derrick Stolee wrote:

This can overflow if we are looking past 2^31. Probably not very common (things seem to get pretty painful at hundreds of millions of objects). But it can be written as:

  uint32_t mid = lo + (hi - lo) / 2;

Sadly, this overflow case seems to be present in many of our binary searches.

nth_packed_object_sha1() has to do some minor computation to come up with the correct pointer. The normal packfile lookup precomputes the initial offset and stride outside the loop. I have no idea if that micro-optimization is actually noticeable, but I thought I'd mention it as a possible avenue for investigation since you're obviously interested in squeezing out performance. ;)

-Peff

A common mistake when writing binary search is to allow possible integer overflow by using the simple average:

	mid = (min + max) / 2;

Instead, use the overflow-safe version:

	mid = min + (max - min) / 2;

The included changes were found using the following two greps:

	grep "/ 2;" *.c
	grep "/ 2;" */*.c
	grep "/2;" */*.c

Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 builtin/index-pack.c     | 4 ++--
 builtin/pack-objects.c   | 2 +-
 builtin/unpack-objects.c | 2 +-
 cache-tree.c             | 2 +-
 packfile.c               | 2 +-
 sha1-lookup.c            | 2 +-
 sha1_name.c              | 2 +-
 string-list.c            | 2 +-
 utf8.c                   | 2 +-
 xdiff/xpatience.c        | 2 +-
 10 files changed, 11 insertions(+), 11 deletions(-)

On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:

Great, thank you for picking this up!

You can use[1]:

  git grep '/ 2;' '*.c'

to have Git expand the wildcard. That catches a few extra cases in compat/regex/*.c. Even though it's imported code, it might be nice to cover those, too (since it's a possible bug, and also as a good example).

[1] I'd actually write:

      git grep '/ *2;' '*.c'

    to do it all in one grep. :)

These all look good to me (really the only way the conversion could be bad is if "min" was higher than "max", and each case is just inside a loop condition which makes sure that is not the case).

-Peff

On 10/6/2017 10:18 AM, Jeff King wrote:

Thanks for the grep lesson! I knew there would be a simpler way to do what I wanted.

I thought this should be simple enough. When we are all happy with the idea of this cleanup, I'll re-roll with the missed examples.

Thanks, -Stolee

A common mistake when writing binary search is to allow possible integer overflow by using the simple average:

	mid = (min + max) / 2;

Instead, use the overflow-safe version:

	mid = min + (max - min) / 2;

This translation is safe since the operation occurs inside a loop conditioned on "min < max". The included changes were found using the following git grep:

	git grep '/ *2;' '*.c'

Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 builtin/index-pack.c          | 4 ++--
 builtin/pack-objects.c        | 2 +-
 builtin/unpack-objects.c      | 2 +-
 cache-tree.c                  | 2 +-
 compat/regex/regex_internal.c | 4 ++--
 compat/regex/regexec.c        | 2 +-
 packfile.c                    | 2 +-
 sha1-lookup.c                 | 4 ++--
 sha1_name.c                   | 2 +-
 string-list.c                 | 2 +-
 utf8.c                        | 2 +-
 xdiff/xpatience.c             | 2 +-
 12 files changed, 15 insertions(+), 15 deletions(-)

On Sun, Oct 08, 2017 at 02:29:37PM -0400, Derrick Stolee wrote:

Thanks, this version looks good to me.

This one is a do-while, so it's less obvious that "high" is always more than "low" when entering the loop. But one assumes it is so, since the binary search wouldn't work otherwise.

-Peff