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
--
2.14.1.538.g56ec8fc98.dirty
