[PATCH 0/3] Improve abbreviation disambiguation

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