[PATCH v2 0/5] Improve abbreviation disambiguation

[PATCH v2 0/5] Improve abbreviation disambiguation

[Derrick Stolee]

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

-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v2 1/5] test-list-objects: List a subset of object ids

[Derrick Stolee]

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

diff --git a/Makefile b/Makefile
index f2bb7f2f6..af94b655a 100644
--- a/Makefile
+++ b/Makefile
@@ -647,6 +647,7 @@ TEST_PROGRAMS_NEED_X += test-hashmap
 TEST_PROGRAMS_NEED_X += test-index-version
 TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash
 TEST_PROGRAMS_NEED_X += test-line-buffer
+TEST_PROGRAMS_NEED_X += test-list-objects
 TEST_PROGRAMS_NEED_X += test-match-trees
 TEST_PROGRAMS_NEED_X += test-mergesort
 TEST_PROGRAMS_NEED_X += test-mktemp
diff --git a/t/helper/.gitignore b/t/helper/.gitignore
index 721650256..9dd1c9f3c 100644
--- a/t/helper/.gitignore
+++ b/t/helper/.gitignore
@@ -13,6 +13,7 @@
 /test-index-version
 /test-lazy-init-name-hash
 /test-line-buffer
+/test-list-objects
 /test-match-trees
 /test-mergesort
 /test-mktemp
diff --git a/t/helper/test-list-objects.c b/t/helper/test-list-objects.c
new file mode 100644
index 000000000..83b1250fe
--- /dev/null
+++ b/t/helper/test-list-objects.c
@@ -0,0 +1,85 @@
+#include "cache.h"
+#include "packfile.h"
+#include <stdio.h>
+
+struct count {
+	int total;
+	int select_mod;
+};
+
+int count_loose(const struct object_id *oid,
+		const char *path,
+		void *data)
+{
+	((struct count*)data)->total++;
+	return 0;
+}
+
+int count_packed(const struct object_id *oid,
+		 struct packed_git *pack,
+		 uint32_t pos,
+		 void* data)
+{
+	((struct count*)data)->total++;
+	return 0;
+}
+
+void output(const struct object_id *oid,
+	    struct count *c)
+{
+	if (!(c->total % c->select_mod))
+		printf("%s\n", oid_to_hex(oid));
+	c->total--;
+}
+
+int output_loose(const struct object_id *oid,
+		 const char *path,
+		 void *data)
+{
+	output(oid, (struct count*)data);
+	return 0;
+}
+
+int output_packed(const struct object_id *oid,
+		  struct packed_git *pack,
+		  uint32_t pos,
+		  void* data)
+{
+	output(oid, (struct count*)data);
+	return 0;
+}
+
+int cmd_main(int ac, const char **av)
+{
+	unsigned int hash_delt = 0xFDB97531;
+	unsigned int hash_base = 0x01020304;
+	int i, n = 0;
+	struct count c;
+	const int u_per_oid = sizeof(struct object_id) / sizeof(unsigned int);
+
+	c.total = 0;
+	if (ac > 1)
+		n = atoi(av[1]);
+
+	if (ac > 2 && !strcmp(av[2], "--missing")) {
+		while (c.total++ < n) {
+			for (i = 0; i < u_per_oid; i++) {
+				printf("%08x", hash_base);
+				hash_base += hash_delt;
+			}
+			printf("\n");
+		}
+	} else {
+		setup_git_directory();
+
+		for_each_loose_object(count_loose, &c, 0);
+		for_each_packed_object(count_packed, &c, 0);
+
+		c.select_mod = 1 + c.total / n;
+
+		for_each_loose_object(output_loose, &c, 0);
+		for_each_packed_object(output_packed, &c, 0);
+	}
+
+	exit(0);
+}
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf

[Derrick Stolee]

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

diff --git a/Makefile b/Makefile
index af94b655a..75835c7c0 100644
--- a/Makefile
+++ b/Makefile
@@ -633,6 +633,7 @@ X =
 
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
+TEST_PROGRAMS_NEED_X += test-abbrev
 TEST_PROGRAMS_NEED_X += test-chmtime
 TEST_PROGRAMS_NEED_X += test-ctype
 TEST_PROGRAMS_NEED_X += test-config
diff --git a/t/helper/.gitignore b/t/helper/.gitignore
index 9dd1c9f3c..ab9df8369 100644
--- a/t/helper/.gitignore
+++ b/t/helper/.gitignore
@@ -1,3 +1,4 @@
+/test-abbrev
 /test-chmtime
 /test-ctype
 /test-config
diff --git a/t/helper/test-abbrev.c b/t/helper/test-abbrev.c
new file mode 100644
index 000000000..6866896eb
--- /dev/null
+++ b/t/helper/test-abbrev.c
@@ -0,0 +1,19 @@
+#include "cache.h"
+#include <stdio.h>
+
+int cmd_main(int ac, const char **av)
+{
+	struct object_id oid;
+	char hex[GIT_MAX_HEXSZ + 2];
+	const char *end;
+
+	setup_git_directory();
+
+	while (fgets(hex, GIT_MAX_HEXSZ + 2, stdin)) {
+		hex[GIT_MAX_HEXSZ] = 0;
+		if (!parse_oid_hex(hex, &oid, &end))
+			find_unique_abbrev(oid.hash, MINIMUM_ABBREV);
+	}
+
+	exit(0);
+}
diff --git a/t/perf/p0008-abbrev.sh b/t/perf/p0008-abbrev.sh
new file mode 100755
index 000000000..ba25e7824
--- /dev/null
+++ b/t/perf/p0008-abbrev.sh
@@ -0,0 +1,22 @@
+#!/bin/bash
+
+test_description='Test object disambiguation through abbreviations'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test-list-objects 100000 | sort -R > objs.txt
+
+test_perf 'find_unique_abbrev() for existing objects' '
+	test-abbrev < objs.txt
+'
+
+test-list-objects 100000 --missing | sort -R > objs.txt
+
+test_perf 'find_unique_abbrev() for missing objects' '
+	test-abbrev < objs.txt
+'
+
+rm objs.txt
+
+test_done
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v2 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.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(-)

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, &oid_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, &ds) < 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*)&mad;
+
+	find_short_object_filename(&ds);
+	find_short_packed_object(&ds);
+	(void)finish_object_disambiguation(&ds, &oid_ret);
+
+	hex[mad.cur_len] = 0;
+	return mad.cur_len;
 }
 
 const char *find_unique_abbrev(const unsigned char *sha1, int len)
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v2 4/5] sha1_name: Parse less while finding common prefix

[Derrick Stolee]

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

diff --git a/sha1_name.c b/sha1_name.c
index f2a1ebe49..bb47b6702 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -480,13 +480,22 @@ struct min_abbrev_data {
 	char *hex;
 };
 
+static inline char get_hex_char_from_oid(const struct object_id *oid, int i)
+{
+	static const char hex[] = "0123456789abcdef";
+
+	if ((i & 1) == 0)
+		return hex[oid->hash[i >> 1] >> 4];
+	else
+		return hex[oid->hash[i >> 1] & 0xf];
+}
+
 static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 {
 	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])
+	while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))
 		i++;
 
 	if (i < GIT_MAX_RAWSZ && i >= mad->cur_len)
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v2 5/5] sha1_name: Minimize OID comparisons during disambiguation

[Derrick Stolee]

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

diff --git a/sha1_name.c b/sha1_name.c
index bb47b6702..1566cd4fc 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -478,6 +478,7 @@ struct min_abbrev_data {
 	unsigned int init_len;
 	unsigned int cur_len;
 	char *hex;
+	const unsigned char *hash;
 };
 
 static inline char get_hex_char_from_oid(const struct object_id *oid, int i)
@@ -504,6 +505,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 	return 0;
 }
 
+static void find_abbrev_len_for_pack(struct packed_git *p,
+				     struct min_abbrev_data *mad)
+{
+	int match = 0;
+	uint32_t num, last, first = 0;
+	struct object_id oid;
+
+	open_pack_index(p);
+	num = p->num_objects;
+	last = num;
+	while (first < last) {
+		uint32_t mid = (first + last) / 2;
+		const unsigned char *current;
+		int cmp;
+
+		current = nth_packed_object_sha1(p, mid);
+		cmp = hashcmp(mad->hash, current);
+		if (!cmp) {
+			match = 1;
+			first = mid;
+			break;
+		}
+		if (cmp > 0) {
+			first = mid + 1;
+			continue;
+		}
+		last = mid;
+	}
+
+	/*
+	 * first is now the position in the packfile where we would insert
+	 * mad->hash if it does not exist (or the position of mad->hash if
+	 * it does exist). Hence, we consider a maximum of three objects
+	 * nearby for the abbreviation length.
+	 */
+	mad->init_len = 0;
+	if (!match) {
+		nth_packed_object_oid(&oid, p, first);
+		extend_abbrev_len(&oid, mad);
+	} else if (first < num - 1) {
+		nth_packed_object_oid(&oid, p, first + 1);
+		extend_abbrev_len(&oid, mad);
+	}
+	if (first > 0) {
+		nth_packed_object_oid(&oid, p, first - 1);
+		extend_abbrev_len(&oid, mad);
+	}
+	mad->init_len = mad->cur_len;
+}
+
+static void find_abbrev_len_packed(struct min_abbrev_data *mad)
+{
+	struct packed_git *p;
+
+	prepare_packed_git();
+	for (p = packed_git; p; p = p->next)
+		find_abbrev_len_for_pack(p, mad);
+}
+
 int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 {
 	struct disambiguate_state ds;
@@ -535,19 +595,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 	if (len == GIT_SHA1_HEXSZ || !len)
 		return GIT_SHA1_HEXSZ;
 
-	if (init_object_disambiguation(hex, len, &ds) < 0)
-		return -1;
-
 	mad.init_len = len;
 	mad.cur_len = len;
 	mad.hex = hex;
+	mad.hash = sha1;
+
+	find_abbrev_len_packed(&mad);
+
+	if (init_object_disambiguation(hex, mad.cur_len, &ds) < 0)
+		return -1;
 
 	ds.fn = extend_abbrev_len;
 	ds.always_call_fn = 1;
 	ds.cb_data = (void*)&mad;
 
 	find_short_object_filename(&ds);
-	find_short_packed_object(&ds);
 	(void)finish_object_disambiguation(&ds, &oid_ret);
 
 	hex[mad.cur_len] = 0;
-- 
2.14.1.538.g56ec8fc98.dirty

Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix

[Stefan Beller]

On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stolee <dstolee@microsoft.com> wrote:
> 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%
>

These number look pretty cool!

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

double signoff?

> ---
>  sha1_name.c | 13 +++++++++++--
>  1 file changed, 11 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index f2a1ebe49..bb47b6702 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -480,13 +480,22 @@ struct min_abbrev_data {
>         char *hex;
>  };
>
> +static inline char get_hex_char_from_oid(const struct object_id *oid, int i)

'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?

> +{
> +       static const char hex[] = "0123456789abcdef";
> +
> +       if ((i & 1) == 0)
> +               return hex[oid->hash[i >> 1] >> 4];
> +       else
> +               return hex[oid->hash[i >> 1] & 0xf];
> +}

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.

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Junio C Hamano]

Derrick Stolee <dstolee@microsoft.com> writes:

> diff --git a/t/helper/test-list-objects.c b/t/helper/test-list-objects.c
> new file mode 100644
> index 000000000..83b1250fe
> --- /dev/null
> +++ b/t/helper/test-list-objects.c
> @@ -0,0 +1,85 @@
> +#include "cache.h"
> +#include "packfile.h"
> +#include <stdio.h>

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

> +int cmd_main(int ac, const char **av)
> +{
> +	unsigned int hash_delt = 0xFDB97531;
> +	unsigned int hash_base = 0x01020304;
> +...
> +	const int u_per_oid = sizeof(struct object_id) / sizeof(unsigned int);

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.

> +	c.total = 0;
> +	if (ac > 1)
> +		n = atoi(av[1]);

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.

> +
> +	if (ac > 2 && !strcmp(av[2], "--missing")) {
> +		while (c.total++ < n) {

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"?

> +			for (i = 0; i < u_per_oid; i++) {
> +				printf("%08x", hash_base);
> +				hash_base += hash_delt;
> +			}
> +			printf("\n");
> +		}
> +	} else {
> +		setup_git_directory();
> +
> +		for_each_loose_object(count_loose, &c, 0);
> +		for_each_packed_object(count_packed, &c, 0);
> +
> +		c.select_mod = 1 + c.total / n;

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?

> +		for_each_loose_object(output_loose, &c, 0);
> +		for_each_packed_object(output_packed, &c, 0);
> +	}
> +
> +	exit(0);
> +}

Thanks.

Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf

[Junio C Hamano]

Derrick Stolee <dstolee@microsoft.com> writes:

> diff --git a/t/helper/test-abbrev.c b/t/helper/test-abbrev.c
> new file mode 100644
> index 000000000..6866896eb
> --- /dev/null
> +++ b/t/helper/test-abbrev.c
> @@ -0,0 +1,19 @@
> +#include "cache.h"
> +#include <stdio.h>

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

> +
> +int cmd_main(int ac, const char **av)
> +{
> +	struct object_id oid;
> +	char hex[GIT_MAX_HEXSZ + 2];

Why +2 (as opposed to +1)?

> +	const char *end;
> +
> +	setup_git_directory();
> +
> +	while (fgets(hex, GIT_MAX_HEXSZ + 2, stdin)) {
> +		hex[GIT_MAX_HEXSZ] = 0;
> +		if (!parse_oid_hex(hex, &oid, &end))
> +			find_unique_abbrev(oid.hash, MINIMUM_ABBREV);
> +	}
> +
> +	exit(0);
> +}
> diff --git a/t/perf/p0008-abbrev.sh b/t/perf/p0008-abbrev.sh
> new file mode 100755
> index 000000000..ba25e7824
> --- /dev/null
> +++ b/t/perf/p0008-abbrev.sh
> @@ -0,0 +1,22 @@
> +#!/bin/bash
> +
> +test_description='Test object disambiguation through abbreviations'
> +. ./perf-lib.sh
> +
> +test_perf_large_repo
> +
> +test-list-objects 100000 | sort -R > objs.txt

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

> +
> +test_perf 'find_unique_abbrev() for existing objects' '
> +	test-abbrev < objs.txt
> +'
> +
> +test-list-objects 100000 --missing | sort -R > objs.txt
> +
> +test_perf 'find_unique_abbrev() for missing objects' '
> +	test-abbrev < objs.txt
> +'
> +
> +rm objs.txt
> +
> +test_done

Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix

[Derrick Stolee]

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

On 9/25/2017 7:42 PM, Stefan Beller wrote:
> On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stolee <dstolee@microsoft.com> wrote:
>> 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%
>>
> These number look pretty cool!
>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> double signoff?

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

>
>> ---
>>   sha1_name.c | 13 +++++++++++--
>>   1 file changed, 11 insertions(+), 2 deletions(-)
>>
>> diff --git a/sha1_name.c b/sha1_name.c
>> index f2a1ebe49..bb47b6702 100644
>> --- a/sha1_name.c
>> +++ b/sha1_name.c
>> @@ -480,13 +480,22 @@ struct min_abbrev_data {
>>          char *hex;
>>   };
>>
>> +static inline char get_hex_char_from_oid(const struct object_id *oid, int i)
> 'i' is not very descriptive, maybe add a comment?
> (I realize it is just walking through the char*s one by one)
I renamed 'i' to 'pos' in my v3.

>
> 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?
>
>> +{
>> +       static const char hex[] = "0123456789abcdef";
>> +
>> +       if ((i & 1) == 0)
>> +               return hex[oid->hash[i >> 1] >> 4];
>> +       else
>> +               return hex[oid->hash[i >> 1] & 0xf];
>> +}
> 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.

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

[PATCH v3 0/5] Improve abbreviation disambituation

[Derrick Stolee]

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

[PATCH v3 1/5] test-list-objects: List a subset of object ids

[Derrick Stolee]

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

diff --git a/Makefile b/Makefile
index ed4ca438b..50a2eab80 100644
--- a/Makefile
+++ b/Makefile
@@ -652,6 +652,7 @@ TEST_PROGRAMS_NEED_X += test-hashmap
 TEST_PROGRAMS_NEED_X += test-index-version
 TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash
 TEST_PROGRAMS_NEED_X += test-line-buffer
+TEST_PROGRAMS_NEED_X += test-list-objects
 TEST_PROGRAMS_NEED_X += test-match-trees
 TEST_PROGRAMS_NEED_X += test-mergesort
 TEST_PROGRAMS_NEED_X += test-mktemp
diff --git a/t/helper/.gitignore b/t/helper/.gitignore
index 7c9d28a83..9696f54bb 100644
--- a/t/helper/.gitignore
+++ b/t/helper/.gitignore
@@ -13,6 +13,7 @@
 /test-index-version
 /test-lazy-init-name-hash
 /test-line-buffer
+/test-list-objects
 /test-match-trees
 /test-mergesort
 /test-mktemp
diff --git a/t/helper/test-list-objects.c b/t/helper/test-list-objects.c
new file mode 100644
index 000000000..22bc9b4e6
--- /dev/null
+++ b/t/helper/test-list-objects.c
@@ -0,0 +1,87 @@
+#include "cache.h"
+#include "packfile.h"
+
+struct count {
+	int total;
+	int select_mod;
+};
+
+int count_loose(const struct object_id *oid,
+		const char *path,
+		void *data)
+{
+	((struct count*)data)->total++;
+	return 0;
+}
+
+int count_packed(const struct object_id *oid,
+		 struct packed_git *pack,
+		 uint32_t pos,
+		 void* data)
+{
+	((struct count*)data)->total++;
+	return 0;
+}
+
+void output(const struct object_id *oid,
+	    struct count *c)
+{
+	if (!(c->total % c->select_mod))
+		printf("%s\n", oid_to_hex(oid));
+	c->total--;
+}
+
+int output_loose(const struct object_id *oid,
+		 const char *path,
+		 void *data)
+{
+	output(oid, (struct count*)data);
+	return 0;
+}
+
+int output_packed(const struct object_id *oid,
+		  struct packed_git *pack,
+		  uint32_t pos,
+		  void* data)
+{
+	output(oid, (struct count*)data);
+	return 0;
+}
+
+int cmd_main(int ac, const char **av)
+{
+	uint32_t hash_delt = 0xFDB97531;
+	uint32_t hash_base = 0x01020304;
+	int i, n = -1;
+	struct count c;
+	const int u_per_oid = sizeof(struct object_id) / sizeof(uint32_t);
+
+	c.total = 0;
+	if (ac > 1)
+		n = atoi(av[ac - 1]);
+
+	if (ac > 2 && !strcmp(av[1], "--missing")) {
+		while (c.total++ < n) {
+			for (i = 0; i < u_per_oid; i++) {
+				printf("%08x", hash_base);
+				hash_base += hash_delt;
+			}
+			printf("\n");
+		}
+	} else {
+		setup_git_directory();
+
+		if (n > 0) {
+			for_each_loose_object(count_loose, &c, 0);
+			for_each_packed_object(count_packed, &c, 0);
+			c.select_mod = 1 + c.total / n;
+		} else {
+			c.select_mod = 1;
+		}
+
+		for_each_loose_object(output_loose, &c, 0);
+		for_each_packed_object(output_packed, &c, 0);
+	}
+
+	exit(0);
+}
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v3 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf

[Derrick Stolee]

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

diff --git a/Makefile b/Makefile
index 50a2eab80..63438a44e 100644
--- a/Makefile
+++ b/Makefile
@@ -638,6 +638,7 @@ X =
 
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
+TEST_PROGRAMS_NEED_X += test-abbrev
 TEST_PROGRAMS_NEED_X += test-chmtime
 TEST_PROGRAMS_NEED_X += test-ctype
 TEST_PROGRAMS_NEED_X += test-config
diff --git a/t/helper/.gitignore b/t/helper/.gitignore
index 9696f54bb..2190781ff 100644
--- a/t/helper/.gitignore
+++ b/t/helper/.gitignore
@@ -1,3 +1,4 @@
+/test-abbrev
 /test-chmtime
 /test-ctype
 /test-config
diff --git a/t/helper/test-abbrev.c b/t/helper/test-abbrev.c
new file mode 100644
index 000000000..3ad88611a
--- /dev/null
+++ b/t/helper/test-abbrev.c
@@ -0,0 +1,18 @@
+#include "cache.h"
+
+int cmd_main(int ac, const char **av)
+{
+	struct object_id oid;
+	char hex[GIT_MAX_HEXSZ + 2];
+	const char *end;
+
+	setup_git_directory();
+
+	while (fgets(hex, GIT_MAX_HEXSZ + 2, stdin)) {
+		hex[GIT_MAX_HEXSZ] = 0;
+		if (!parse_oid_hex(hex, &oid, &end))
+			find_unique_abbrev(oid.hash, MINIMUM_ABBREV);
+	}
+
+	exit(0);
+}
diff --git a/t/perf/p0008-abbrev.sh b/t/perf/p0008-abbrev.sh
new file mode 100755
index 000000000..5cbc8a888
--- /dev/null
+++ b/t/perf/p0008-abbrev.sh
@@ -0,0 +1,22 @@
+#!/bin/bash
+
+test_description='Test object disambiguation through abbreviations'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test-list-objects 100000 > objs.txt
+
+test_perf 'find_unique_abbrev() for existing objects' '
+	test-abbrev < objs.txt
+'
+
+test-list-objects --missing 100000 > objs.txt
+
+test_perf 'find_unique_abbrev() for missing objects' '
+	test-abbrev < objs.txt
+'
+
+rm objs.txt
+
+test_done
-- 
2.14.1.538.g56ec8fc98.dirty

[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 <dstolee@microsoft.com>
---
 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, &oid_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, &ds) < 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*)&mad;
+
+	find_short_object_filename(&ds);
+	find_short_packed_object(&ds);
+	(void)finish_object_disambiguation(&ds, &oid_ret);
+
+	hex[mad.cur_len] = 0;
+	return mad.cur_len;
 }
 
 const char *find_unique_abbrev(const unsigned char *sha1, int len)
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v3 4/5] sha1_name: Parse less while finding common prefix

[Derrick Stolee]

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

diff --git a/sha1_name.c b/sha1_name.c
index f2a1ebe49..5081aeb71 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -480,13 +480,23 @@ struct min_abbrev_data {
 	char *hex;
 };
 
+static inline char get_hex_char_from_oid(const struct object_id *oid,
+					 int pos)
+{
+	static const char hex[] = "0123456789abcdef";
+
+	if ((pos & 1) == 0)
+		return hex[oid->hash[pos >> 1] >> 4];
+	else
+		return hex[oid->hash[pos >> 1] & 0xf];
+}
+
 static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 {
 	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])
+	while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))
 		i++;
 
 	if (i < GIT_MAX_RAWSZ && i >= mad->cur_len)
-- 
2.14.1.538.g56ec8fc98.dirty

[PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation

[Derrick Stolee]

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

diff --git a/sha1_name.c b/sha1_name.c
index 5081aeb71..54b3a37da 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -478,6 +478,7 @@ struct min_abbrev_data {
 	unsigned int init_len;
 	unsigned int cur_len;
 	char *hex;
+	const unsigned char *hash;
 };
 
 static inline char get_hex_char_from_oid(const struct object_id *oid,
@@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 	return 0;
 }
 
+static void find_abbrev_len_for_pack(struct packed_git *p,
+				     struct min_abbrev_data *mad)
+{
+	int match = 0;
+	uint32_t num, last, first = 0;
+	struct object_id oid;
+
+	open_pack_index(p);
+	num = p->num_objects;
+	last = num;
+	while (first < last) {
+		uint32_t mid = (first + last) / 2;
+		const unsigned char *current;
+		int cmp;
+
+		current = nth_packed_object_sha1(p, mid);
+		cmp = hashcmp(mad->hash, current);
+		if (!cmp) {
+			match = 1;
+			first = mid;
+			break;
+		}
+		if (cmp > 0) {
+			first = mid + 1;
+			continue;
+		}
+		last = mid;
+	}
+
+	/*
+	 * first is now the position in the packfile where we would insert
+	 * mad->hash if it does not exist (or the position of mad->hash if
+	 * it does exist). Hence, we consider a maximum of three objects
+	 * nearby for the abbreviation length.
+	 */
+	mad->init_len = 0;
+	if (!match) {
+		nth_packed_object_oid(&oid, p, first);
+		extend_abbrev_len(&oid, mad);
+	} else if (first < num - 1) {
+		nth_packed_object_oid(&oid, p, first + 1);
+		extend_abbrev_len(&oid, mad);
+	}
+	if (first > 0) {
+		nth_packed_object_oid(&oid, p, first - 1);
+		extend_abbrev_len(&oid, mad);
+	}
+	mad->init_len = mad->cur_len;
+}
+
+static void find_abbrev_len_packed(struct min_abbrev_data *mad)
+{
+	struct packed_git *p;
+
+	prepare_packed_git();
+	for (p = packed_git; p; p = p->next)
+		find_abbrev_len_for_pack(p, mad);
+}
+
 int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 {
 	struct disambiguate_state ds;
@@ -536,19 +596,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 	if (len == GIT_SHA1_HEXSZ || !len)
 		return GIT_SHA1_HEXSZ;
 
-	if (init_object_disambiguation(hex, len, &ds) < 0)
-		return -1;
-
 	mad.init_len = len;
 	mad.cur_len = len;
 	mad.hex = hex;
+	mad.hash = sha1;
+
+	find_abbrev_len_packed(&mad);
+
+	if (init_object_disambiguation(hex, mad.cur_len, &ds) < 0)
+		return -1;
 
 	ds.fn = extend_abbrev_len;
 	ds.always_call_fn = 1;
 	ds.cb_data = (void*)&mad;
 
 	find_short_object_filename(&ds);
-	find_short_packed_object(&ds);
 	(void)finish_object_disambiguation(&ds, &oid_ret);
 
 	hex[mad.cur_len] = 0;
-- 
2.14.1.538.g56ec8fc98.dirty

Re: [PATCH v3 1/5] test-list-objects: List a subset of object ids

[Junio C Hamano]

Derrick Stolee <dstolee@microsoft.com> writes:

> Subject: Re: [PATCH v3 1/5] test-list-objects: List a subset of object ids

Style nit: s/List/list/;

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

This should stick to the left hand side.

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

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

[Junio C Hamano]

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

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 <dstolee@microsoft.com> 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 5/5] sha1_name: Minimize OID comparisons during disambiguation

[Stefan Beller]

> @@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
>         return 0;
>  }
>
> +static void find_abbrev_len_for_pack(struct packed_git *p,
> +                                    struct min_abbrev_data *mad)
> +{
> +       int match = 0;
> +       uint32_t num, last, first = 0;
> +       struct object_id oid;
> +
> +       open_pack_index(p);

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?

Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation

[Derrick Stolee]

On 10/3/2017 11:55 AM, Stefan Beller wrote:
>> @@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
>>          return 0;
>>   }
>>
>> +static void find_abbrev_len_for_pack(struct packed_git *p,
>> +                                    struct min_abbrev_data *mad)
>> +{
>> +       int match = 0;
>> +       uint32_t num, last, first = 0;
>> +       struct object_id oid;
>> +
>> +       open_pack_index(p);
> coverity complained here with
>      Calling "open_pack_index" without checking return value
>      (as is done elsewhere 13 out of 15 times).
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.
> 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?
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

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

[Junio C Hamano]

Derrick Stolee <dstolee@microsoft.com> 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, &oid_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, &ds) < 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*)&mad;
> +
> +	find_short_object_filename(&ds);
> +	find_short_packed_object(&ds);
> +	(void)finish_object_disambiguation(&ds, &oid_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

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> On 10/3/2017 6:49 AM, Junio C Hamano wrote:
>> Derrick Stolee <dstolee@microsoft.com> 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 4/5] sha1_name: Parse less while finding common prefix

[Junio C Hamano]

Derrick Stolee <dstolee@microsoft.com> writes:

> diff --git a/sha1_name.c b/sha1_name.c
> index f2a1ebe49..5081aeb71 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -480,13 +480,23 @@ struct min_abbrev_data {
>  	char *hex;
>  };
>  
> +static inline char get_hex_char_from_oid(const struct object_id *oid,
> +					 int pos)
> +{
> +	static const char hex[] = "0123456789abcdef";
> +
> +	if ((pos & 1) == 0)
> +		return hex[oid->hash[pos >> 1] >> 4];
> +	else
> +		return hex[oid->hash[pos >> 1] & 0xf];
> +}
> +


>  static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
>  {
>  	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])
> +	while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))
>  		i++;

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.

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 <stolee@gmail.com> 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

[Derrick Stolee]

On 10/4/2017 2:07 AM, Junio C Hamano wrote:
> Derrick Stolee <dstolee@microsoft.com> writes:
>
>> -	exists = has_sha1_file(sha1);
>> -	while (len < GIT_SHA1_HEXSZ) {
>> -		struct object_id oid_ret;
>> -		status = get_short_oid(hex, len, &oid_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

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> On 10/4/2017 2:07 AM, Junio C Hamano wrote:
>> Derrick Stolee <dstolee@microsoft.com> writes:
>>
>>> -	exists = has_sha1_file(sha1);
>>> -	while (len < GIT_SHA1_HEXSZ) {
>>> -		struct object_id oid_ret;
>>> -		status = get_short_oid(hex, len, &oid_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 v2 1/5] test-list-objects: List a subset of object ids

[Jeff King]

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

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

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

Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf

[Jeff King]

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

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

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.

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

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

Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf

[Jeff King]

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

> On Mon, Sep 25, 2017 at 05:54:49AM -0400, Derrick Stolee wrote:
> 
> > Create helper program test-abbrev to compute the minimum length of a
> > disambiguating short-sha for an input list of object ids.
> 
> 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.

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

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index f5fa4fd75a..a5f911a632 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -225,6 +225,9 @@ static void expand_atom(struct strbuf *sb, const char *atom, int len,
 	if (is_atom("objectname", atom, len)) {
 		if (!data->mark_query)
 			strbuf_addstr(sb, oid_to_hex(&data->oid));
+	} else if (is_atom("objectname:short", atom, len)) {
+		if (!data->mark_query)
+			strbuf_add_unique_abbrev(sb, data->oid.hash, MINIMUM_ABBREV);
 	} else if (is_atom("objecttype", atom, len)) {
 		if (data->mark_query)
 			data->info.typep = &data->type;

-Peff

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, &oid_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 5/5] sha1_name: Minimize OID comparisons during disambiguation

[Jeff King]

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

> +static void find_abbrev_len_for_pack(struct packed_git *p,
> +				     struct min_abbrev_data *mad)
> +{
> +	int match = 0;
> +	uint32_t num, last, first = 0;
> +	struct object_id oid;
> +
> +	open_pack_index(p);
> +	num = p->num_objects;
> +	last = num;
> +	while (first < last) {
> +		uint32_t mid = (first + last) / 2;

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.

> +		const unsigned char *current;
> +		int cmp;
> +
> +		current = nth_packed_object_sha1(p, mid);

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

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

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

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.

Re: [PATCH v3 0/5] Improve abbreviation disambituation

[Jeff King]

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

> 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:

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

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

[Junio C Hamano]

Jeff King <peff@peff.net> 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 v2 1/5] test-list-objects: List a subset of object ids

[Jeff King]

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

> Jeff King <peff@peff.net> writes:
> 
> > 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).
> 
> 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.

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

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Junio C Hamano]

On Thu, Oct 5, 2017 at 7:00 PM, Jeff King <peff@peff.net> wrote:
>
>> Jeff King <peff@peff.net> writes:
>>
> 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.

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

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Derrick Stolee]

On 10/5/2017 6:00 AM, Jeff King wrote:
> On Thu, Oct 05, 2017 at 06:48:10PM +0900, Junio C Hamano wrote:
>
>> Jeff King <peff@peff.net> writes:
>>
>>> 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).
>> 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.
> 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
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

[PATCH] cleanup: fix possible overflow errors in binary search

[Derrick 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;

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

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index f2be145e1..8ec459f52 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -633,7 +633,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)
 	int first = 0, last = nr_ofs_deltas;
 
 	while (first < last) {
-		int next = (first + last) / 2;
+		int next = first + (last - first) / 2;
 		struct ofs_delta_entry *delta = &ofs_deltas[next];
 		int cmp;
 
@@ -687,7 +687,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)
 	int first = 0, last = nr_ref_deltas;
 
 	while (first < last) {
-		int next = (first + last) / 2;
+		int next = first + (last - first) / 2;
 		struct ref_delta_entry *delta = &ref_deltas[next];
 		int cmp;
 
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 5ee2c48ff..6e77dfd44 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1277,7 +1277,7 @@ static int done_pbase_path_pos(unsigned hash)
 	int lo = 0;
 	int hi = done_pbase_paths_num;
 	while (lo < hi) {
-		int mi = (hi + lo) / 2;
+		int mi = lo + (hi - lo) / 2;
 		if (done_pbase_paths[mi] == hash)
 			return mi;
 		if (done_pbase_paths[mi] < hash)
diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c
index 689a29fac..62ea264c4 100644
--- a/builtin/unpack-objects.c
+++ b/builtin/unpack-objects.c
@@ -394,7 +394,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,
 		lo = 0;
 		hi = nr;
 		while (lo < hi) {
-			mid = (lo + hi)/2;
+			mid = lo + (hi - lo) / 2;
 			if (base_offset < obj_list[mid].offset) {
 				hi = mid;
 			} else if (base_offset > obj_list[mid].offset) {
diff --git a/cache-tree.c b/cache-tree.c
index 71d092ed5..d3f740127 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -49,7 +49,7 @@ static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)
 	lo = 0;
 	hi = it->subtree_nr;
 	while (lo < hi) {
-		int mi = (lo + hi) / 2;
+		int mi = lo + (hi - lo) / 2;
 		struct cache_tree_sub *mdl = down[mi];
 		int cmp = subtree_name_cmp(path, pathlen,
 					   mdl->name, mdl->namelen);
diff --git a/packfile.c b/packfile.c
index eab754248..4a5fe7ab1 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1743,7 +1743,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 		       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);
 
 	while (lo < hi) {
-		unsigned mi = (lo + hi) / 2;
+		unsigned mi = lo + (hi - lo) / 2;
 		int cmp = hashcmp(index + mi * stride, sha1);
 
 		if (debug_lookup)
diff --git a/sha1-lookup.c b/sha1-lookup.c
index 2552b7902..df08f8355 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -95,7 +95,7 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
 			hi = mi;
 		else
 			lo = mi + 1;
-		mi = (hi + lo) / 2;
+		mi = lo + (hi - lo) / 2;
 	} while (lo < hi);
 	return -lo-1;
 }
diff --git a/sha1_name.c b/sha1_name.c
index 134ac9742..c7c5ab376 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -157,7 +157,7 @@ static void unique_in_pack(struct packed_git *p,
 	num = p->num_objects;
 	last = num;
 	while (first < last) {
-		uint32_t mid = (first + last) / 2;
+		uint32_t mid = first + (last - first) / 2;
 		const unsigned char *current;
 		int cmp;
 
diff --git a/string-list.c b/string-list.c
index 806b4c872..a0cf0cfe8 100644
--- a/string-list.c
+++ b/string-list.c
@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,
 	compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
 
 	while (left + 1 < right) {
-		int middle = (left + right) / 2;
+		int middle = left + (right - left) / 2;
 		int compare = cmp(string, list->items[middle].string);
 		if (compare < 0)
 			right = middle;
diff --git a/utf8.c b/utf8.c
index 47a42047c..2c27ce013 100644
--- a/utf8.c
+++ b/utf8.c
@@ -32,7 +32,7 @@ static int bisearch(ucs_char_t ucs, const struct interval *table, int max)
 	if (ucs < table[0].first || ucs > table[max].last)
 		return 0;
 	while (max >= min) {
-		mid = (min + max) / 2;
+		mid = min + (max - min) / 2;
 		if (ucs > table[mid].last)
 			min = mid + 1;
 		else if (ucs < table[mid].first)
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index a613efc70..9f91702de 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c
@@ -166,7 +166,7 @@ static int binary_search(struct entry **sequence, int longest,
 	int left = -1, right = longest;
 
 	while (left + 1 < right) {
-		int middle = (left + right) / 2;
+		int middle = left + (right - left) / 2;
 		/* by construction, no two entries can be equal */
 		if (sequence[middle]->line2 > entry->line2)
 			right = middle;
-- 
2.14.1.538.g56ec8fc98.dirty

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Jeff King]

On Thu, Oct 05, 2017 at 08:39:42AM -0400, Derrick Stolee 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.
> > 
> 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.

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?

> Our workaround so far has been to set core.abbrev=40.

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.

> 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!

-Peff

Re: [PATCH] cleanup: fix possible overflow errors in binary search

[Jeff King]

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

> 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;

Great, thank you for picking this up!

> The included changes were found using the following two greps:
> 
> 	grep "/ 2;" *.c
> 	grep "/ 2;" */*.c
> 	grep "/2;" */*.c

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

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

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

Re: [PATCH] cleanup: fix possible overflow errors in binary search

[Derrick Stolee]

On 10/6/2017 10:18 AM, Jeff King wrote:
> On Fri, Oct 06, 2017 at 09:52:31AM -0400, Derrick Stolee wrote:
>
>> 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;
> Great, thank you for picking this up!
>
>> The included changes were found using the following two greps:
>>
>> 	grep "/ 2;" *.c
>> 	grep "/ 2;" */*.c
>> 	grep "/2;" */*.c
> 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. :)

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

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

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Derrick Stolee]

On 10/6/2017 10:11 AM, Jeff King wrote:
> On Thu, Oct 05, 2017 at 08:39:42AM -0400, Derrick Stolee wrote:
>> 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!
> 
> -Peff
> 

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

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Jeff King]

On Sat, Oct 07, 2017 at 03:12:08PM -0400, Derrick Stolee 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.

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

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

That all sounds reasonable to me.

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

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

Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Sat, Oct 07, 2017 at 03:12:08PM -0400, Derrick Stolee 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.
>
> 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).

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.

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

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.

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

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.

[PATCH v2] cleanup: fix possible overflow errors in binary search

[Derrick 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(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index f2be145e1..8ec459f52 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -633,7 +633,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)
 	int first = 0, last = nr_ofs_deltas;
 
 	while (first < last) {
-		int next = (first + last) / 2;
+		int next = first + (last - first) / 2;
 		struct ofs_delta_entry *delta = &ofs_deltas[next];
 		int cmp;
 
@@ -687,7 +687,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)
 	int first = 0, last = nr_ref_deltas;
 
 	while (first < last) {
-		int next = (first + last) / 2;
+		int next = first + (last - first) / 2;
 		struct ref_delta_entry *delta = &ref_deltas[next];
 		int cmp;
 
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 5ee2c48ff..6e77dfd44 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1277,7 +1277,7 @@ static int done_pbase_path_pos(unsigned hash)
 	int lo = 0;
 	int hi = done_pbase_paths_num;
 	while (lo < hi) {
-		int mi = (hi + lo) / 2;
+		int mi = lo + (hi - lo) / 2;
 		if (done_pbase_paths[mi] == hash)
 			return mi;
 		if (done_pbase_paths[mi] < hash)
diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c
index 689a29fac..62ea264c4 100644
--- a/builtin/unpack-objects.c
+++ b/builtin/unpack-objects.c
@@ -394,7 +394,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,
 		lo = 0;
 		hi = nr;
 		while (lo < hi) {
-			mid = (lo + hi)/2;
+			mid = lo + (hi - lo) / 2;
 			if (base_offset < obj_list[mid].offset) {
 				hi = mid;
 			} else if (base_offset > obj_list[mid].offset) {
diff --git a/cache-tree.c b/cache-tree.c
index 71d092ed5..d3f740127 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -49,7 +49,7 @@ static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)
 	lo = 0;
 	hi = it->subtree_nr;
 	while (lo < hi) {
-		int mi = (lo + hi) / 2;
+		int mi = lo + (hi - lo) / 2;
 		struct cache_tree_sub *mdl = down[mi];
 		int cmp = subtree_name_cmp(path, pathlen,
 					   mdl->name, mdl->namelen);
diff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c
index d4121f2f4..98342b831 100644
--- a/compat/regex/regex_internal.c
+++ b/compat/regex/regex_internal.c
@@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)
 	      int low = 0, high = pstr->valid_len, mid;
 	      do
 		{
-		  mid = (high + low) / 2;
+		  mid = low + (high - low) / 2;
 		  if (pstr->offsets[mid] > offset)
 		    high = mid;
 		  else if (pstr->offsets[mid] < offset)
@@ -1394,7 +1394,7 @@ re_node_set_contains (const re_node_set *set, int elem)
   right = set->nelem - 1;
   while (idx < right)
     {
-      mid = (idx + right) / 2;
+      mid = idx + (right - idx) / 2;
       if (set->elems[mid] < elem)
 	idx = mid + 1;
       else
diff --git a/compat/regex/regexec.c b/compat/regex/regexec.c
index 0a745d9c3..6f2b48a78 100644
--- a/compat/regex/regexec.c
+++ b/compat/regex/regexec.c
@@ -4284,7 +4284,7 @@ search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx)
   last = right = mctx->nbkref_ents;
   for (left = 0; left < right;)
     {
-      mid = (left + right) / 2;
+      mid = left + (right - left) / 2;
       if (mctx->bkref_ents[mid].str_idx < str_idx)
 	left = mid + 1;
       else
diff --git a/packfile.c b/packfile.c
index eab754248..4a5fe7ab1 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1743,7 +1743,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 		       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);
 
 	while (lo < hi) {
-		unsigned mi = (lo + hi) / 2;
+		unsigned mi = lo + (hi - lo) / 2;
 		int cmp = hashcmp(index + mi * stride, sha1);
 
 		if (debug_lookup)
diff --git a/sha1-lookup.c b/sha1-lookup.c
index 2552b7902..4cf3ebd92 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -10,7 +10,7 @@ static uint32_t take2(const unsigned char *sha1)
  * Conventional binary search loop looks like this:
  *
  *      do {
- *              int mi = (lo + hi) / 2;
+ *              int mi = lo + (hi - lo) / 2;
  *              int cmp = "entry pointed at by mi" minus "target";
  *              if (!cmp)
  *                      return (mi is the wanted one)
@@ -95,7 +95,7 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
 			hi = mi;
 		else
 			lo = mi + 1;
-		mi = (hi + lo) / 2;
+		mi = lo + (hi - lo) / 2;
 	} while (lo < hi);
 	return -lo-1;
 }
diff --git a/sha1_name.c b/sha1_name.c
index 134ac9742..c7c5ab376 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -157,7 +157,7 @@ static void unique_in_pack(struct packed_git *p,
 	num = p->num_objects;
 	last = num;
 	while (first < last) {
-		uint32_t mid = (first + last) / 2;
+		uint32_t mid = first + (last - first) / 2;
 		const unsigned char *current;
 		int cmp;
 
diff --git a/string-list.c b/string-list.c
index 806b4c872..a0cf0cfe8 100644
--- a/string-list.c
+++ b/string-list.c
@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,
 	compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
 
 	while (left + 1 < right) {
-		int middle = (left + right) / 2;
+		int middle = left + (right - left) / 2;
 		int compare = cmp(string, list->items[middle].string);
 		if (compare < 0)
 			right = middle;
diff --git a/utf8.c b/utf8.c
index 47a42047c..2c27ce013 100644
--- a/utf8.c
+++ b/utf8.c
@@ -32,7 +32,7 @@ static int bisearch(ucs_char_t ucs, const struct interval *table, int max)
 	if (ucs < table[0].first || ucs > table[max].last)
 		return 0;
 	while (max >= min) {
-		mid = (min + max) / 2;
+		mid = min + (max - min) / 2;
 		if (ucs > table[mid].last)
 			min = mid + 1;
 		else if (ucs < table[mid].first)
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index a613efc70..9f91702de 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c
@@ -166,7 +166,7 @@ static int binary_search(struct entry **sequence, int longest,
 	int left = -1, right = longest;
 
 	while (left + 1 < right) {
-		int middle = (left + right) / 2;
+		int middle = left + (right - left) / 2;
 		/* by construction, no two entries can be equal */
 		if (sequence[middle]->line2 > entry->line2)
 			right = middle;
-- 
2.14.1.538.g56ec8fc98.dirty

Re: [PATCH v2] cleanup: fix possible overflow errors in binary search

[Jeff King]

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

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

Thanks, this version looks good to me.

> diff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c
> index d4121f2f4..98342b831 100644
> --- a/compat/regex/regex_internal.c
> +++ b/compat/regex/regex_internal.c
> @@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)
>  	      int low = 0, high = pstr->valid_len, mid;
>  	      do
>  		{
> -		  mid = (high + low) / 2;
> +		  mid = low + (high - low) / 2;
>  		  if (pstr->offsets[mid] > offset)
>  		    high = mid;
>  		  else if (pstr->offsets[mid] < offset)

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