Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)

Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)

[Ted Ts'o]

On Thu, Oct 28, 2010 at 07:17:01PM +0200, Ingo Molnar wrote:
> > Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > Yes. Except for the kernel the default git commit abbreviation is
> > borderline too short. Seven hex-chars can easily alias with a few
> > more pulls from me: git will not give aliases at the time it gives
> > a shorthand, but a month or two later the abbreviated commit may
> > no longer be unique.
> > 
> > So I suggest using --abbrev=12 or similar.
> 
> ok. A helper script i use does this:
> 
>    git log --pretty=format:"%h: %s" $@
> 
> I have added --abbrev=12. Might make sense to lengthen the %h
> default in upstream Git as well?

Maybe the right thing to do is add a git config option which allows
for a configurable minimum git commit abbreviation length?

      		   	       	      - Ted

Re: Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 2132 bytes --]

On Thu, Oct 28, 2010 at 10:27 AM, Ted Ts'o <tytso@mit.edu> wrote:
> On Thu, Oct 28, 2010 at 07:17:01PM +0200, Ingo Molnar wrote:
>> > Linus Torvalds <torvalds@linux-foundation.org> wrote:
>> > Yes. Except for the kernel the default git commit abbreviation is
>> > borderline too short. Seven hex-chars can easily alias with a few
>> > more pulls from me: git will not give aliases at the time it gives
>> > a shorthand, but a month or two later the abbreviated commit may
>> > no longer be unique.
>> >
>> > So I suggest using --abbrev=12 or similar.
>>
>> ok. A helper script i use does this:
>>
>>    git log --pretty=format:"%h: %s" $@
>>
>> I have added --abbrev=12. Might make sense to lengthen the %h
>> default in upstream Git as well?
>
> Maybe the right thing to do is add a git config option which allows
> for a configurable minimum git commit abbreviation length?

Yes. The default of 7 (I think) comes from fairly early in git
development, when seven hex digits was a lot (it covers about 250+
million hash values). Back then I thought that 65k revisions was a lot
(it was what we were about to hit in BK), and each revision tends to
be about 5-10 new objects or so, so a million objects was a big
number.

These days, the kernel isn't even the largest git project, and even
the kernel has about 220k revisions (_much_ bigger than the BK tree
ever was) and we are approaching two million objects. At that point,
seven hex digits is still unique for a lot of them, but when we're
talking about just two orders of magnitude difference between number
of objects and the hash size, there _will_ be hash collisions. It's no
longer even close to unrealistic - it happens all the time.

So I suspect we should both increase the default abbrev that was
unrealistically small, _and_ add a way for people to set their own
default per-project in the git config file.

Maybe something like the attached (not necessarily well-thought-out or
well-tested: I also didn't actually change the default, although I
suspect we should up it from 7 to at least 10).

                        Linus

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 2200 bytes --]

 builtin/describe.c |    2 +-
 cache.h            |    5 +++--
 config.c           |    8 ++++++++
 environment.c      |    1 +
 4 files changed, 13 insertions(+), 3 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index 43caff2..2d98702 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -20,7 +20,7 @@ static int debug;	/* Display lots of verbose info */
 static int all;	/* Any valid ref can be used */
 static int tags;	/* Allow lightweight tags */
 static int longformat;
-static int abbrev = DEFAULT_ABBREV;
+static int abbrev = 7;	/* NOTE! Not DEFAULT_ABBREV */
 static int max_candidates = 10;
 static int found_names;
 static const char *pattern;
diff --git a/cache.h b/cache.h
index 33decd9..6c28a81 100644
--- a/cache.h
+++ b/cache.h
@@ -540,6 +540,7 @@ extern int trust_executable_bit;
 extern int trust_ctime;
 extern int quote_path_fully;
 extern int has_symlinks;
+extern int minimum_abbrev, default_abbrev;
 extern int ignore_case;
 extern int assume_unchanged;
 extern int prefer_symlink_refs;
@@ -757,8 +758,8 @@ static inline unsigned int hexval(unsigned char c)
 }
 
 /* Convert to/from hex/sha1 representation */
-#define MINIMUM_ABBREV 4
-#define DEFAULT_ABBREV 7
+#define MINIMUM_ABBREV minimum_abbrev
+#define DEFAULT_ABBREV default_abbrev
 
 struct object_context {
 	unsigned char tree[20];
diff --git a/config.c b/config.c
index 4b0a820..474361c 100644
--- a/config.c
+++ b/config.c
@@ -514,6 +514,14 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.abbrev")) {
+		int abbrev = git_config_int(var, value);
+		if (abbrev < minimum_abbrev || abbrev > 40)
+			return -1;
+		default_abbrev = abbrev;
+		return 0;
+	}
+
 	if (!strcmp(var, "core.loosecompression")) {
 		int level = git_config_int(var, value);
 		if (level == -1)
diff --git a/environment.c b/environment.c
index de5581f..b98003c 100644
--- a/environment.c
+++ b/environment.c
@@ -15,6 +15,7 @@ int user_ident_explicitly_given;
 int trust_executable_bit = 1;
 int trust_ctime = 1;
 int has_symlinks = 1;
+int minimum_abbrev = 4, default_abbrev = 7;
 int ignore_case;
 int assume_unchanged;
 int prefer_symlink_refs;

Re: Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)

[Linus Torvalds]

On Thu, Oct 28, 2010 at 11:28 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Yes. The default of 7 (I think) comes from fairly early in git
> development, when seven hex digits was a lot (it covers about 250+
> million hash values). Back then I thought that 65k revisions was a lot
> (it was what we were about to hit in BK), and each revision tends to
> be about 5-10 new objects or so, so a million objects was a big
> number.
>
> These days, the kernel isn't even the largest git project, and even
> the kernel has about 220k revisions (_much_ bigger than the BK tree
> ever was) and we are approaching two million objects. At that point,
> seven hex digits is still unique for a lot of them, but when we're
> talking about just two orders of magnitude difference between number
> of objects and the hash size, there _will_ be hash collisions. It's no
> longer even close to unrealistic - it happens all the time.

Hmm. In fact, in the kernel, we currently have about twelve thousand
objects that end up having collisions in 7 hex digits. Even in the old
historical BK kernel tree, we have over a thousand objects that
collide (each bucket in both cases gets just two objects, there are as
of yet no multiple collisions, which is what you'd expect with a good
hash). See with

  git rev-list --objects --all | cut -c1-7 | sort | uniq -dc

and in fact git itself has a few collisions (but currently just 44
objects ending up sharing 22 SHA1 buckets in 7 digits).

With each digit, you'd expect the collisions to decrease by a factor
of 16, and that is indeed exactly what happens. For my current kernel
tree I get:

 - 7 digits: 5823 buckets with duplicates (ie 11646 objects that aren't unique)
 - 8: 406
 - 9: 30
 - 10: 1
 - 11: 0

so 12 hex digits is indeed pretty safe for the kernel, and is likely
to remain so until the kernel history grows by a factor of 16.

                        Linus

Re: Minimum git commit abbrev length (Was Re: -tip: origin tree build failure

[Brandon Casey]

From: Brandon Casey <drafnel@gmail.com>

[dropped linux-kernel list from discussion]

On 10/28/2010 01:54 PM, Linus Torvalds wrote:

> and in fact git itself has a few collisions (but currently just 44
> objects ending up sharing 22 SHA1 buckets in 7 digits).
> 
> With each digit, you'd expect the collisions to decrease by a factor
> of 16, and that is indeed exactly what happens. For my current kernel
> tree I get:
> 
>  - 7 digits: 5823 buckets with duplicates (ie 11646 objects that aren't unique)
>  - 8: 406
>  - 9: 30
>  - 10: 1
>  - 11: 0
> 
> so 12 hex digits is indeed pretty safe for the kernel, and is likely
> to remain so until the kernel history grows by a factor of 16.


Perhaps we should calculate DEFAULT_ABBREV dynamically?

Something like the code down below would use 11 digits for the current
kernel repo, and would bump up to 12 digits once it hit 4M objects.

It would use 9 digits for git.git.

The digits of abbrev are bumped up for each factor of 4 objects.
This seems to produce a desirable number for the git.git and
linux-2.6.git repos.

estimate_loose_objects() quickly estimates the number of loose
objects using Junio's code extracted from gc.c.

default_abbrev() estimates the loose objects, counts the number of
packed objects, and calculates a default abbreviation width.
Subsequent calls to default_abbrev() return the previously calculated
value.

This is obviously not a patch meant for inclusion, just an example.

---
 builtin/describe.c |    4 ++-
 cache.h            |    3 +-
 sha1_name.c        |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 66 insertions(+), 2 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index 43caff2..551b491 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -20,7 +20,7 @@ static int debug;	/* Display lots of verbose info */
 static int all;	/* Any valid ref can be used */
 static int tags;	/* Allow lightweight tags */
 static int longformat;
-static int abbrev = DEFAULT_ABBREV;
+static int abbrev;
 static int max_candidates = 10;
 static int found_names;
 static const char *pattern;
@@ -386,6 +386,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 		OPT_END(),
 	};
 
+	abbrev = DEFAULT_ABBREV;
+
 	argc = parse_options(argc, argv, prefix, options, describe_usage, 0);
 	if (max_candidates < 0)
 		max_candidates = 0;
diff --git a/cache.h b/cache.h
index 33decd9..049ef2b 100644
--- a/cache.h
+++ b/cache.h
@@ -758,7 +758,7 @@ static inline unsigned int hexval(unsigned char c)
 
 /* Convert to/from hex/sha1 representation */
 #define MINIMUM_ABBREV 4
-#define DEFAULT_ABBREV 7
+#define DEFAULT_ABBREV default_abbrev()
 
 struct object_context {
 	unsigned char tree[20];
@@ -766,6 +766,7 @@ struct object_context {
 	unsigned mode;
 };
 
+extern int default_abbrev(void);
 extern int get_sha1(const char *str, unsigned char *sha1);
 extern int get_sha1_with_mode_1(const char *str, unsigned char *sha1, unsigned *mode, int gently, const char *prefix);
 static inline int get_sha1_with_mode(const char *str, unsigned char *sha1, unsigned *mode)
diff --git a/sha1_name.c b/sha1_name.c
index 484081d..8d622fe 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -7,6 +7,67 @@
 #include "refs.h"
 #include "remote.h"
 
+static unsigned long estimate_loose_objects(unsigned threshold)
+{
+	/*
+	 * Quickly estimate how many loose objects there are.
+	 * Because SHA-1 is evenly distributed, we can check
+	 * only one and get a reasonable estimate.
+	 */
+	char path[PATH_MAX];
+	const char *objdir = get_object_directory();
+	DIR *dir;
+	struct dirent *ent;
+	unsigned long num_loose = 0;
+
+	if (sizeof(path) <= snprintf(path, sizeof(path), "%s/17", objdir)) {
+		warning("insanely long object directory %.*s", 50, objdir);
+		return 0;
+	}
+
+	dir = opendir(path);
+	if (!dir)
+		return 0;
+
+	threshold = (threshold + 255) / 256;
+	while ((ent = readdir(dir)) != NULL) {
+		if (strspn(ent->d_name, "0123456789abcdef") != 38 ||
+		    ent->d_name[38] != '\0')
+			continue;
+		num_loose++;
+		if (threshold && num_loose > threshold)
+			break;
+	}
+	closedir(dir);
+	return num_loose * 256;
+}
+
+int default_abbrev(void)
+{
+	static int default_abbrev;
+	unsigned long count;
+	struct packed_git *p;
+
+	if (default_abbrev)
+		return default_abbrev;
+
+	count = estimate_loose_objects(0);
+
+	prepare_packed_git();
+	for (p = packed_git; p; p = p->next)
+		if (!open_pack_index(p))
+			count += p->num_objects;
+
+	default_abbrev = 1;
+	while ((count >>= 2))
+		default_abbrev++;
+
+	if (default_abbrev < MINIMUM_ABBREV)
+		default_abbrev = MINIMUM_ABBREV;
+
+	return default_abbrev;
+}
+
 static int find_short_object_filename(int len, const char *name, unsigned char *sha1)
 {
 	struct alternate_object_database *alt;
-- 
1.7.3.1

[PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Junio C Hamano]

The caller of this function wants to ensure that the returned string is a
unique abbreviation of the object name, and at least "len" characters
long.  When "len" is too short to ensure uniqueness with only that many
characters, it returns minimally unique prefix (i.e. if you dropped the
last character, there would be two or more objects that share that same
prefix as their names in the repository).

An earlier change introduced core.abbrevguard configuration with a
realization that a short prefix that is unique today may not stay unique
forever, as new objects are added to the repository. When "len" is shorter
than the length necessary to ensure uniqueness today, instead of returning
a string that is only one character longer than the longest ambiguous
prefix, we want to add that many extra characters (in addition to the "one
character that is absolutely needed to make it unique today") to ensure
uniqueness for longer time.

The code however forgot that the function may be called with a "len" that
is long enough.  If an object is uniquely identifiable with only 4 leading
characters today, and if the caller gives 7 as len and the guard is set to
3, it returned 10 hexdigits, which was 3 characters longer than necessary.
We should instead return 7 leading characters in such a case, as that is
in line with the original intention of using 3 characters more than
absolutely necessary to give the disambiguation we find today a better
chance to survive.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * A three-line patch, with 35 new comment lines and four paragraph commit
   log message, to fix a stupid thinko that I noticed during a separate
   discussion with Namhyung-ssi, who wanted to add an option to ensure
   uniqueness of the truncated commit name in the human-readable blame
   output.

 sha1_name.c |   38 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 38 insertions(+), 0 deletions(-)

diff --git a/sha1_name.c b/sha1_name.c
index 4a226ad..62950aa 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -191,6 +191,26 @@ static int get_short_sha1(const char *name, int len, unsigned char *sha1,
 	return status;
 }
 
+/*
+ * The caller wants a unique abbreviation of the full object name in
+ * "sha1" that is at least "len" characters long.  A string is a unique
+ * abbrevation of the full object name when:
+ *
+ * (1) there is no other object that shares the returned string as the
+ *     prefix of its name, if sha1 identifies an existing object; or
+ *
+ * (2) there is no object that has the returned string as the prefix
+ *     of its name, if sha1 does not identify any existing object.
+ *
+ * If there exist two or more objects that share the same N characters
+ * at the beginning of their object names, N+1 leading characters is
+ * sufficient to make the abbreviation unique today.  As the number of
+ * objects in the repository grows, however, such an abbreviation
+ * won't stay unique forever.  core.abbrevguard configuration variable
+ * can be used to add extra G characters when ensuring the uniqueness
+ * of the abbreviation, i.e. making N+1+G characters the minimum in
+ * order to keep the result unique a bit longer, instead of just N+1.
+ */
 const char *find_unique_abbrev(const unsigned char *sha1, int len)
 {
 	int status, exists;
@@ -200,6 +220,24 @@ const char *find_unique_abbrev(const unsigned char *sha1, int len)
 	memcpy(hex, sha1_to_hex(sha1), 40);
 	if (len == 40 || !len)
 		return hex;
+	/*
+	 * Try to see how short a prefix we can feed to get a unique
+	 * hit.  When len is sufficiently long, we may find the
+	 * absolute minimum abbreviation that is a lot shorter than
+	 * len, so we try from (len - unique_abbrev_extra_length), to
+	 * avoid the final addition of u_a_e_l to the result getting
+	 * longer than necessary.  E.g. an object that is ambiguous
+	 * today with only 3 but is unique with 4 leading characters,
+	 * it should yield 7 character result if the caller called us
+	 * with len=7 with u_a_e_l=3 (or shorter), so we start from 4
+	 * in such a case.  When len is shorter than the minimum
+	 * required to make the result unique, the loop counts up and
+	 * finds the absolute minimum (just one character longer than
+	 * ambiguous truncation) and then we add u_a_e_l to it.
+	 */
+	len -= unique_abbrev_extra_length;
+	if (len <= 0)
+		len = 1;
 	while (len < 40) {
 		unsigned char sha1_ret[20];
 		status = get_short_sha1(hex, len, sha1_ret, 1);
-- 
1.7.4.1.373.g37629

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Linus Torvalds]

On Thu, Mar 10, 2011 at 2:37 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
> The code however forgot that the function may be called with a "len" that
> is long enough.  If an object is uniquely identifiable with only 4 leading
> characters today, and if the caller gives 7 as len and the guard is set to
> 3, it returned 10 hexdigits, which was 3 characters longer than necessary.
> We should instead return 7 leading characters in such a case, as that is
> in line with the original intention of using 3 characters more than
> absolutely necessary to give the disambiguation we find today a better
> chance to survive.

The thing is, that just makes the notion of "abbrevguard" pointless.
Why have it?

When you pass in 6 as a len, and that isn't sufficient, it expands it
to (say) 10. And then you pass in 7 as a length, and now it's
sufficient, so it keeps it at 7.

That's just stupid. You gave it a bigger length suggestion, and you
got a smaller end result. That's crazy.

However, I think the _real_ problem is not whether that behavior is
really stupid or not. I think the real problem is that abbrevguard
really isn't a well-defined, and you get this kind of crazy semantics.

So I think the REAL problem is different:

 (a) DEFAULT_ABBREV is just too damn small. 7 made sense as a random
number back when we did this, but we're talking over 5 years ago. The
seven comes from commit 47dd0d595d04e. Back then, a million objects
was a really almost inconceivably big number.  Even the BK tree (that
I was going by as a target) was just 65k revisions for Linux, so with
most changes only touching a few files, "million" was "long time in
the future". Now we're close to 2 million.

It turns out 640kB isn't enough for everybody. For the kernel, we have
several objects that need 10 digits just for uniqeness right NOW.. 12
digits is a _somewhat_ reasonable safe value for the forseeable
future. But 11 would be too short. And I don't think the kernel is the
biggest repo.

 (b) You can't change DEFAULT_ABBREV except with the command line option.

 (c) Even there it's unnecessarily hard.  Want to see your commit
numbers abbreviated appropriately too? Oh, you have to use
"--abbrev=12 --abbrev-commit". We didn't think the interface through.

 (d) some places don't even take the command line option. Grep for
DEFAULT_ABBREV, and notice how often it's just used as-is.

So I would suggest ditching 'unique_abbrev_extra_length' entirely. I
doubt anybody uses it, and the whole concept is simply badly designed
with crazy semantics as per your patch.

                              Linus

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> When you pass in 6 as a len, and that isn't sufficient, it expands it
> to (say) 10. And then you pass in 7 as a length, and now it's
> sufficient, so it keeps it at 7.

Hmph, that is not the way I wanted to do things.  If len is 6 and the
result needs to be 10 to be sufficient, it should still yield 10 if the
len you give is 7 (or 8 or 9 or 10).  Of course it would be stupid if you
don't do it that way.

I thought the code should work that way already (unless of course there is
an implementation bug).

How many characters do we need to name master uniquely today?

    $ ./git -c core.abbrevguard=0 rev-parse --short=1 master
    83c3c

Ok, so there are more than one object with 83c3 and 83c3c is the absolute
minimum.  We can ask for extra for futureproofing.

    $ ./git -c core.abbrevguard=3 rev-parse --short=1 master
    83c3c622

And we get three extra and the result is 8 characters long.  What if we
give len=7 that is still short?

    $ ./git -c core.abbrevguard=3 rev-parse --short=7 master
    83c3c622

Of course we allow the limit 7 to be busted to keep the futureproofing.

    $ ./git -c core.abbrevguard=3 rev-parse --short=8 master
    83c3c622

Obeying 8 doesn't hurt the futureproofing so the output remains the same.
But if you say len=9, you get 9

    $ ./git -c core.abbrevguard=3 rev-parse --short=9 master
    83c3c6222

even though we know 8 is plenty futureproof, but you get 9 because you
asked for 9.

What am I missing to be called "just stupid" and "crazy"?

The earlier code was adding the three extra over what was asked for.  With
guard=3 and len=7, you would have got 10 for this object that only needs 5
as absolute minimum today, and giving 8 would have been enough to stay
unique with room for 3 extra characters to grow.  That is what I was
fixing.

>  (b) You can't change DEFAULT_ABBREV except with the command line option.

I would agree that would need changing, but I think that is more or less
an independent issue.

I thought I took your patch to introduce the configuration when I sent the
abbrevguard as a companion patch, but apparently I didn't.  That would fix
the "grep DEFAULT_ABBREV" issue.

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Linus Torvalds]

On Thu, Mar 10, 2011 at 4:40 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
> How many characters do we need to name master uniquely today?
>
>    $ ./git -c core.abbrevguard=0 rev-parse --short=1 master
>    83c3c
>
> Ok, so there are more than one object with 83c3 and 83c3c is the absolute
> minimum.

Actually, that's just lucky.

Do this:

  git rev-list --abbrev=4 --abbrev-commit --all --objects | grep '^.........*$'

and you'll see several commits in the git tree that need eight
characters to be unique. The fact that your current 'master' isn't one
of them, and in fact happens to be one that only needs five, is just
pure luck.

So even in the (much smaller) git repo, 7 is not a sufficient unique
minimum even today. Never mind any future guarding.

And your argument fails for exactly that reason: yes, for an
_individual_ SHA1, you may think that "five characters is sufficient",
and when you then use that random number (5) as a basis for forming
your "max 8 character" logic, it fails miserably for other cases.

Now, if the "abbrevguard" was based not one one random data-point, but
on the _whole_ current state of the repository, things would be
different.  Then it would actually become a "let's pick a good default
abbreviation length for this repo". But that's now that it does. The
abbrevguard depends on the one particular SHA1 you're looking at, so
you can actually be asking for a longer abbreviation, but still get a
_shorter_ end result than when you asked for a shorter abbreviation.

IOW, try your example thing not just with "master", but with two
extreme commits. For example, try

  git -c core.abbrevguard=2 rev-parse --short=5 83c3c622
  git -c core.abbrevguard=2 rev-parse --short=4 979f7929

and tell me what you get. I _think_ you should get 7 digits for the
first case, and 8 digits for the second one. Even though you "asked"
for a longer name in the first case, and you had the same abbrevguard.

See what I'm saying? I think that's just insane. And it comes exactly
from the fact that abbreviation ends up being a "local" thing.

                          Linus

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> IOW, try your example thing not just with "master", but with two
> extreme commits. For example, try
>
>   git -c core.abbrevguard=2 rev-parse --short=5 83c3c622
>   git -c core.abbrevguard=2 rev-parse --short=4 979f7929
>
> and tell me what you get. I _think_ you should get 7 digits for the
> first case, and 8 digits for the second one. Even though you "asked"
> for a longer name in the first case, and you had the same abbrevguard.
>
> See what I'm saying? I think that's just insane.

Hmph, why?

That 979f79 one already have enough other objects with similar names, so
compared to 83c3c that doesn't, it is natural that you would need more
digits to protect its uniqueness, no?  The result shouldn't be affected by
the value of "short" as long as it is not long enough, as that is merely
specifying "at least this many letters".

Another thing to realize is that without abbrevguard with the code before
the configuration was introduced, you would get very similar results.
With --short=5, you would get 5 letters for 83c3c622 and with --short=4,
you would still need 8 letters for 979f7929.  Because either of these
values are not long enough and it is merely a way to specify "at least
this many letters".

If we don't care about uniqueness, we can just truncate at the number of
characters specified by the "len" without doing anything else.  That would
give us an output of uniform length without the uniqueness guarantee, and
"git describe" output cannot even be fed back to git running in the same
repository immediately after it is obtained.  I don't think that is what
we want.

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Linus Torvalds]

On Thu, Mar 10, 2011 at 5:33 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
> That 979f79 one already have enough other objects with similar names, so
> compared to 83c3c that doesn't, it is natural that you would need more
> digits to protect its uniqueness, no?  The result shouldn't be affected by
> the value of "short" as long as it is not long enough, as that is merely
> specifying "at least this many letters"

Yes, uniqueness in that sense is sane and has a good definition.

But that's _not_ the case when you then randomly add extra <n> digits to it.

Why? Because that <n> is meaningless, because what <n> means depends
on what the base number was. And the base number is different for
different objects.

The case of n=0 is special, because it is the "current state". But
what does "n=1" mean?

Let me make it more explicit by making an extreme example about this.
It's extreme just because I'm going to assume that the shortest
abbreviation is 1 (in reality it's 4) but that doesn't really change
the math, it just makes the numbers smaller/easier.

So let's say that we have a repository with just 100 objects. What
does that mean? In practical terms, it means that it is not impossible
that you will have some object that is unique in a single digit (yes,
it may be a bit unlikely, but it's not unreasonable), while you'll
have other objects that need three digits. And most will be unique in
two.

Shortening the numbers that way has a _meaning_: the notion of
"unique" is clearly meaningful. Sure, different objects get different
lengths, but the different lengths have a very real reason for them.

So then (again, to make the numbers small, and the math simple), let's
assume abbrevguard=1. What does that MEAN?

And I claim that it means something totally _different_ for the
different objects, and that's the crazy thing. Because now we're
talking about possible _future_ objects, but the likely _future_
uniqueness of "unique in one digit" is TOTALLY DIFFERENT from the
future uniqueness of "unique in three digits"!

The single-digit uniqueness is going to be gone _long long_ before the
three-digit uniqueness is gone. Adding a single digit to the object
that currently happens to need only a single-digit unique id will
_not_ do a whole lot of future-proofing - if you add another one
hundred objects, that object may well need three digits to be unique.
But if you add a single digit to the one that currently already needed
three digits, you're likely to need to add an order of magnitude more
objects to need to extend the three digits to four.

See what I'm trying to say? This is why I think abbrevguard is a
broken concept, when it is relative to "how unique is the object now".

If the abbrevguard was related to the maximum number of digits
required for _any_ object in the current repository, it would be
meaningful - it would actually be about the _size_ of the current
repository, and thus indirectly about the size of a future one. But it
isn't. It's always relative to the "local uniqueness", which is only
valid for the *current* state, and has very little to do with future
growth.

Now, to put things in terms of a real repository ("git" itself), and
two extreme cases from it:

 - commit 1dae(0d38b8119de2b67f87e800c860ed958bbed6) currently unique
in four digits

 - commit 979f7929(51913d75f992f87022b75610303a614f) currently unique
in eight digits

and think about what "abbrevguard" means for those two commits.

Let's pick an abbrev-guard of two digits. For the first one, it means
that you use six digits total, and for the second one, you'd use 10
digits total.

What does that mean for future work? How many objects do we need to
add for clashes to start happening?

For the first commit, it's _almost certain_ that if you double the
size of the repository, those six digits will no longer be unique. For
the second case? I can pretty much guarantee that EVEN IF you didn't
have any abbrev-guard at all, and you doubled the size of the git
repository, the thing would still be unique in eight digits.

Why? It's simply *much*much* less likely that you'll get future
clashes from new objects in the eight digits. The likelihood of a
clash with the currently unique 4-digit object is 16^4=65536 times
higher than a clash with the currently 8-digit unique shortening.

So it's senseless to add an equal number of digits to the two objects.
They simply don't have the same likelihood of future collisions.

So what is mathematically the sensible thing? It's actually to extend
both objects to the _same_ number of digits. It's _more_ sensible to
extend the current four-digit number to eight digits, than it is to
extend the currently unique in eight digits by even a single digit. It
would future-proof things a fair amount, exactly because the
likelihood of future objects clashing with the two objects are totally
different.

That's why I said that it would be sensible to make the abbrevguard be
relative to the current worst-case uniqueness. Because THAT actually
is what is probable. If we currently have a maximum uniqueness
requirement of 8 characters, it is _probable_ that by the time the
project has grown by a factor of 4, we'll need 9 characters (I think,
I may have gotten the math wrong).

But it is somewhat expensive to calculate "max current uniqueness", so
I would suggest ditching the whole notion of "how many extra numbers
do I need for futureproofing", and go for just setting the absolute
value of DEFAULT_ABBREV.

                               Linus

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> But it is somewhat expensive to calculate "max current uniqueness", so
> I would suggest ditching the whole notion of "how many extra numbers
> do I need for futureproofing", and go for just setting the absolute
> value of DEFAULT_ABBREV.

Thanks; apparently our mails crossed...

I suspect that in a sane repository with set of reasonably packed objects,
we can cheaply get a rough estimate of the number of objects to about an
order of magnitude (e.g. "likely to have 10k to 100k objects"), and we
might able to come up with a way to automatically raise the default
length.

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Hmph, why?
>
> That 979f79 one already have enough other objects with similar names, so
> compared to 83c3c that doesn't, it is natural that you would need more
> digits to protect its uniqueness, no?

Yuck, this is showing my total non-understanding of statistics and secure
hashing.  The example does not mean the next object we will create in
git.git project somehow magically is more likely to have 979 prefix than
83c prefix.  In other words, 979f7929 is much less likely to collide with
new objects than 83c3c, simply because it has 4 more digits in it (making
the likelyhood of collision with the next one by four orders of magnitude
in base-16), the likelyhood does not depend on what other objects happen
to share the same prefix right now, and adding one digits to each would
make it 1/16 less likely to have collision relative to the likelyhood with
their current length.

In any case, if we want to protect abbreviations we generate today from
future collisions, the only sane thing to do is to give sufficiently long
"len" that is computed globally by taking the total number of objects into
account.  We should consider the loop in find_unique_abbrev that makes
sure that prefix truncated to len is unique, and increments until the
result becomes unique, merely a last-ditch thing, not contributing to
futureproofing.  Even though adding 1 to make it minimally unique as we
have always did before the abbrevguard patch has the same "that 1 extra
has different effectiveness for protecting against future collisions,
depending on how long the base string is" issue, we cannot get away by
adding less than 1 character, and adding more doesn't make it better.

So let's scrap the abbrevguard thing.  I somehow thought that I already
took your "make DEFAULT_ABBREV tweakable" patch, but apparently I didn't.
That one is the real fix to the issue of futureproofing.

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Jeff King]

On Thu, Mar 10, 2011 at 07:03:39PM -0800, Junio C Hamano wrote:

> Junio C Hamano <gitster@pobox.com> writes:
> 
> > Hmph, why?
> >
> > That 979f79 one already have enough other objects with similar names, so
> > compared to 83c3c that doesn't, it is natural that you would need more
> > digits to protect its uniqueness, no?
> 
> Yuck, this is showing my total non-understanding of statistics and secure
> hashing.  The example does not mean the next object we will create in
> git.git project somehow magically is more likely to have 979 prefix than
> 83c prefix.  In other words, 979f7929 is much less likely to collide with
> new objects than 83c3c, simply because it has 4 more digits in it (making
> the likelyhood of collision with the next one by four orders of magnitude
> in base-16), the likelyhood does not depend on what other objects happen
> to share the same prefix right now, and adding one digits to each would
> make it 1/16 less likely to have collision relative to the likelyhood with
> their current length.

This is basically the birthday problem used in hash collision analysis.
Which means that if we decide on some acceptable probability of
collision, we can figure out the hash-length required to keep the
probability of collision below that acceptable level for a repository
with objects.

You can find the formulas here:

  http://en.wikipedia.org/wiki/Birthday_problem

The closest version to what we want is:

  n(p,d) ~ sqrt(2d * ln(1/(1-p)))

where "n" is the number of objects in the repository, "p" is the
probability of a collision, and "d" is the size of the distribution
space. In our case, for sha1 subset with "l" hex characters, it is
2^(4l). And note that this is an approximation, but it should be close
enough for our purposes.

We can arrange the formula into:

  d(n,p) = n^2 / 2 / ln(1/(1-p))

and rearrange our length relationship into:

  l(d) = log2(d) / 4

Then we just pick an acceptable probability of collision. Let's say one
in a million, 10^-6.

So for a repository with 175,000 objects (close to git.git), to keep the
probability of collision at 10^-6, we get d(n,p) = 1.5e16, or 53 bits,
or 13 hex characters.

Which is obviously a lot more than we're doing now. But remember that
this is for _any_ collision. So it's not likely to be for one of the few
numbers you write down for reference later. So we could probably get by
with a much higher collision probability. At one-in-a-thousand, it's 43
bits or 10 characters.

Or we could just take it all the way down to 50%: we are likely to have
ae collision, but that's probably OK since it's unlikely to be one of
the n out of 175,000 that we actually remember and care about. That's 34
bits, or 8.5 hex characters.

For the kernel repository, there are 1.8 million objects. So to hit 50%,
we're talking about 41 bits or about 10 characters. Which, as a quick
sanity check, matches what Linus said earlier: they are seeing
collisions around the 10-character mark now in the kernel repo.

So all of this is more or less what Linus has been saying, but with
numbers and formulas to back it up.

One observation I should note are that these probabilities are what we
would guess knowing _nothing_ about what is in the repo. That is, if you
gave me an empty repo and told me you were going to populate it with N
objects, these are the probabilities I would calculate. But of course
the problem we actually have is that we already have N objects, and we
expect to have N+M at some point in the future; we already know which
collisions we have in the first N, and we want to future proof against
the next M.

So in theory we could say "we currently are unique at 8 characters; we
anticipate 50,000 new objects per year and want to future proof for 4
years (so M=200,000). What is the length we need to keep the probability
of collision for just this _one_ sha1 below some acceptable level?"

Which I think is just:

  p(M) = 1 - d^-M

but when I tried solving for d, I ended up with nonsensical numbers.
Which means I'm either wrong or I'm way too sleepy to be doing algebra.

Anyway, point being if we wanted to make a table of reasonable lengths
for repos with N objects, it would look like this (for p=0.5):

   N  | bits | hex
  ------------------
  1e2 |  13  |  3
  1e3 |  19  |  5
  1e4 |  26  |  7
  1e5 |  33  |  8
  1e6 |  39  | 10
  2e6 |  41  | 10
  5e6 |  44  | 11
  1e7 |  46  | 12

So '11' would take the kernel repo to 5 million objects, which is more
than doubling. 12 would take it to 10 million. Most smaller projects are
probably fine at 8 or 9.

But you can see that it takes quite a lot of objects to require a bump
in the hex length, meaning we don't need to re-check it very often. If
we really wanted to tweak it automatically, we could probably just set
core.defaultAbbrev (or whatever) during git-gc based on the number of
objects in the repository. We could do the formula, or even just have a
precomputed table (it would be the inverse of the table above, mapping
the switch points for hex characters to numbers of objects).

-Peff

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Jeff King]

On Fri, Mar 11, 2011 at 12:22:35AM -0500, Jeff King wrote:

> This is basically the birthday problem used in hash collision analysis.
> Which means that if we decide on some acceptable probability of
> collision, we can figure out the hash-length required to keep the
> probability of collision below that acceptable level for a repository
> with objects.

Urgh, that was supposed to be "...for a repository with _n_ objects".
But hopefully that became clear as you read on.

-Peff

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> So let's scrap the abbrevguard thing.  I somehow thought that I already
> took your "make DEFAULT_ABBREV tweakable" patch, but apparently I didn't.
> That one is the real fix to the issue of futureproofing.

In return for a free education last night, I now owe you your patch from
October last year, resurrected from the list archive, and here it is.

With a forged sign-off from you, as I know that everything you write is
supposed to be open source.

 - I do not think making minimum configurable is worth it, but I left it in
   (there is no UI to tweak it anyway).

 - I somewhat tweaked "describe" and "describe --abbrev" implementation.
   OPT__ABBREV() uses DEFAULT_ABBREV in its callback, so we need to read
   from the configuration before calling parse_options().  As it won't
   make any sense to call "git describe" outside repository where you
   cannot get to your configuration, I think it is safe to add a call to
   git_config() in this codepath. Other users of OPT__ABBREV() may need to
   be audited.

By the way, I've already reverted the abbrevguard thing away.

-- >8 --
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 28 Oct 2010 11:28:04 -0700
Subject: [PATCH] Make the default abbrev length configurable

The default of 7 comes from fairly early in git development, when
seven hex digits was a lot (it covers about 250+ million hash
values). Back then I thought that 65k revisions was a lot (it was what
we were about to hit in BK), and each revision tends to be about 5-10
new objects or so, so a million objects was a big number.

These days, the kernel isn't even the largest git project, and even
the kernel has about 220k revisions (_much_ bigger than the BK tree
ever was) and we are approaching two million objects. At that point,
seven hex digits is still unique for a lot of them, but when we're
talking about just two orders of magnitude difference between number
of objects and the hash size, there _will_ be collisions in truncated
hash values. It's no longer even close to unrealistic - it happens all
the time.

We should both increase the default abbrev that was unrealistically
small, _and_ add a way for people to set their own default per-project
in the git config file.

This is the first step to first make it configurable; the default of 7
is not raised yet.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/config.txt |    6 ++++++
 builtin/describe.c       |    6 +++++-
 cache.h                  |    5 +++--
 config.c                 |    8 ++++++++
 environment.c            |    1 +
 5 files changed, 23 insertions(+), 3 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index c5e1835..30afde9 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -567,6 +567,12 @@ core.sparseCheckout::
 	Enable "sparse checkout" feature. See section "Sparse checkout" in
 	linkgit:git-read-tree[1] for more information.
 
+core.abbrevLength::
+	Set the length object names are abbreviated to.  If unspecified,
+	many commands abbreviate to 7 hexdigits, which may not be enough
+	for abbreviated object names to stay unique for sufficiently long
+	time.
+
 add.ignore-errors::
 add.ignoreErrors::
 	Tells 'git add' to continue adding files when some files cannot be
diff --git a/builtin/describe.c b/builtin/describe.c
index 342129f..9591596 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -21,7 +21,7 @@ static int debug;	/* Display lots of verbose info */
 static int all;	/* Any valid ref can be used */
 static int tags;	/* Allow lightweight tags */
 static int longformat;
-static int abbrev = DEFAULT_ABBREV;
+static int abbrev = -1; /* unspecified */
 static int max_candidates = 10;
 static struct hash_table names;
 static int have_util;
@@ -420,7 +420,11 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 		OPT_END(),
 	};
 
+	git_config(git_default_config, NULL);
 	argc = parse_options(argc, argv, prefix, options, describe_usage, 0);
+	if (abbrev < 0)
+		abbrev = DEFAULT_ABBREV;
+
 	if (max_candidates < 0)
 		max_candidates = 0;
 	else if (max_candidates > MAX_TAGS)
diff --git a/cache.h b/cache.h
index d83d68c..8d73d88 100644
--- a/cache.h
+++ b/cache.h
@@ -540,6 +540,7 @@ extern int trust_executable_bit;
 extern int trust_ctime;
 extern int quote_path_fully;
 extern int has_symlinks;
+extern int minimum_abbrev, default_abbrev;
 extern int ignore_case;
 extern int assume_unchanged;
 extern int prefer_symlink_refs;
@@ -758,8 +759,8 @@ static inline unsigned int hexval(unsigned char c)
 }
 
 /* Convert to/from hex/sha1 representation */
-#define MINIMUM_ABBREV 4
-#define DEFAULT_ABBREV 7
+#define MINIMUM_ABBREV minimum_abbrev
+#define DEFAULT_ABBREV default_abbrev
 
 struct object_context {
 	unsigned char tree[20];
diff --git a/config.c b/config.c
index 625e051..e8a6e56 100644
--- a/config.c
+++ b/config.c
@@ -531,6 +531,14 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.abbrevlength")) {
+		int abbrev = git_config_int(var, value);
+		if (abbrev < minimum_abbrev || abbrev > 40)
+			return -1;
+		default_abbrev = abbrev;
+		return 0;
+	}
+
 	if (!strcmp(var, "core.loosecompression")) {
 		int level = git_config_int(var, value);
 		if (level == -1)
diff --git a/environment.c b/environment.c
index 9564475..f2d90a8 100644
--- a/environment.c
+++ b/environment.c
@@ -15,6 +15,7 @@ int user_ident_explicitly_given;
 int trust_executable_bit = 1;
 int trust_ctime = 1;
 int has_symlinks = 1;
+int minimum_abbrev = 4, default_abbrev = 7;
 int ignore_case;
 int assume_unchanged;
 int prefer_symlink_refs;
-- 
1.7.4.1.404.g62d316

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Namhyung Kim]

2011-03-11 (금), 14:45 -0800, Junio C Hamano:
> Junio C Hamano <gitster@pobox.com> writes:
> 
> > So let's scrap the abbrevguard thing.  I somehow thought that I already
> > took your "make DEFAULT_ABBREV tweakable" patch, but apparently I didn't.
> > That one is the real fix to the issue of futureproofing.
> 
> In return for a free education last night, I now owe you your patch from
> October last year, resurrected from the list archive, and here it is.
> 
> With a forged sign-off from you, as I know that everything you write is
> supposed to be open source.
> 
>  - I do not think making minimum configurable is worth it, but I left it in
>    (there is no UI to tweak it anyway).
> 
>  - I somewhat tweaked "describe" and "describe --abbrev" implementation.
>    OPT__ABBREV() uses DEFAULT_ABBREV in its callback, so we need to read
>    from the configuration before calling parse_options().  As it won't
>    make any sense to call "git describe" outside repository where you
>    cannot get to your configuration, I think it is safe to add a call to
>    git_config() in this codepath. Other users of OPT__ABBREV() may need to
>    be audited.
> 
> By the way, I've already reverted the abbrevguard thing away.
> 
> -- >8 --
> From: Linus Torvalds <torvalds@linux-foundation.org>
> Date: Thu, 28 Oct 2010 11:28:04 -0700
> Subject: [PATCH] Make the default abbrev length configurable
> 
> The default of 7 comes from fairly early in git development, when
> seven hex digits was a lot (it covers about 250+ million hash
> values). Back then I thought that 65k revisions was a lot (it was what
> we were about to hit in BK), and each revision tends to be about 5-10
> new objects or so, so a million objects was a big number.
> 
> These days, the kernel isn't even the largest git project, and even
> the kernel has about 220k revisions (_much_ bigger than the BK tree
> ever was) and we are approaching two million objects. At that point,
> seven hex digits is still unique for a lot of them, but when we're
> talking about just two orders of magnitude difference between number
> of objects and the hash size, there _will_ be collisions in truncated
> hash values. It's no longer even close to unrealistic - it happens all
> the time.
> 
> We should both increase the default abbrev that was unrealistically
> small, _and_ add a way for people to set their own default per-project
> in the git config file.
> 
> This is the first step to first make it configurable; the default of 7
> is not raised yet.
> 
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---

Reviewed-by: Namhyung Kim <namhyung@gmail.com>

Thanks.


-- 
Regards,
Namhyung Kim

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Jay Soffian]

On Fri, Mar 11, 2011 at 5:45 PM, Junio C Hamano <gitster@pobox.com> wrote:
> +core.abbrevLength::
> +       Set the length object names are abbreviated to.  If unspecified,
> +       many commands abbreviate to 7 hexdigits, which may not be enough
> +       for abbreviated object names to stay unique for sufficiently long
> +       time.
> +

Isn't this the minimum length though? i.e. a longer length is used as
needed for uniqueness. If so, at least the description is misleading,
and I'd argue the option name too. Perhaps core.abbrevMinLength?

j.

Re: [PATCH] find_unique_abbrev(): honor caller-supplied "len" better

[Namhyung Kim]

2011-03-18 (금), 21:22 -0400, Jay Soffian:
> On Fri, Mar 11, 2011 at 5:45 PM, Junio C Hamano <gitster@pobox.com> wrote:
> > +core.abbrevLength::
> > +       Set the length object names are abbreviated to.  If unspecified,
> > +       many commands abbreviate to 7 hexdigits, which may not be enough
> > +       for abbreviated object names to stay unique for sufficiently long
> > +       time.
> > +
> 
> Isn't this the minimum length though? i.e. a longer length is used as
> needed for uniqueness. If so, at least the description is misleading,
> and I'd argue the option name too. Perhaps core.abbrevMinLength?
> 
> j.

It could confuse what it points is the default length or the minimum.
I'd like to suggest core.defaultAbbrev or core.abbrevDefault.


-- 
Regards,
Namhyung Kim