[PATCH 0/3] Improve abbreviation disambiguation

[Derrick Stolee <dstolee@microsoft.com>]

Hello,

My name is Derrick Stolee and I just switched teams at Microsoft from
the VSTS Git Server to work on performance improvements in core Git.

This is my first patch submission, and I look forward to your feedback.

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 performance helper `test-abbrev` and performance test `p0008-abbrev.sh`
are added to demonstrate this performance improvement. Here are some
performance results for the three included commits, using
GIT_PERF_REPEAT_COUNT=10 since the first test is frequently an outlier
due to the file cache being cold.

Running git on a Linux VM, we see the following gains.

| Repo    | Pack-Files | Loose Objs | Baseline | Patch 2 | Patch 3 |
|---------|------------|------------|----------|---------|---------|
| Git.git | 1          | 0          | 0.46 s   | -87.0%  | -87.0%  |
| Git.git | 5          | 0          | 1.04 s   | -84.6%  | -85.6%  |
| Git.git | 4          | 75852      | 0.88 s   | -86.4%  | -86.4%  |
| Linux   | 1          | 0          | 0.63 s   | -38.1%  | -69.8%  |
| Linux   | 24         | 0          | 5.41 s   | -69.3%  | -71.5%  |
| Linux   | 23         | 323441     | 5.41 s   | -70.6%  | -73.4%  |

Running a similar patch on Git for Windows, we see the following gains.

| Repo          | Pack-Files | Loose | Baseline | Patch 2 | Patch 3 |
|---------------|------------|-------|----------|---------|---------|
| GitForWindows | 6          | 319   | 7.19 s   | -91.1%  | -91.5%  |
| VSTS          | 3          | 38    | 7.83 s   | -88.9%  | -90.9%  |
| Linux         | 3          | 0     | 7.92 s   | -87.9%  | -90.2%  |
| Windows       | 50         | 219   | 17.8 s   | -98.6%  | -98.6%  |

Note that performance improves in all cases, but the performance gain
is larger when there are multiple, large pack-files. This gain comes
from the lack of in-memory caching of index files that have already been
inspected.


Derrick Stolee (3):
  sha1_name: Create perf test for find_unique_abbrev()
  sha1_name: Unroll len loop in find_unique_abbrev_r
  sha1_name: Parse less while finding common prefix

 Makefile               |  1 +
 sha1_name.c            | 66 ++++++++++++++++++++++++++++++++++++++------------
 t/helper/.gitignore    |  1 +
 t/helper/test-abbrev.c | 22 +++++++++++++++++
 t/perf/p0008-abbrev.sh | 12 +++++++++
 5 files changed, 87 insertions(+), 15 deletions(-)
 create mode 100644 t/helper/test-abbrev.c
 create mode 100755 t/perf/p0008-abbrev.sh

-- 
2.14.1.538.g56ec8fc98.dirty