Re: [PATCH 4/4] core.abbrev: raise the default abbreviation to 12 hexdigits
- From
Linus Torvalds <torvalds@linux-foundation.org>
- Date
- Sep 29, 2016, 18:55 UTC
- Message-ID
- <CA+55aFwbCNiF0nDppZ5SuRcZwc9kNvKYzgyd_bR8Ut8XRW_p4Q@mail.gmail.com>
- In-Reply-To
- <CA+55aFyYWWpz+9+KKf=9y3vBrEDyy-5h6J3boiitGE7Zb=uL-Q@mail.gmail.com>
On Thu, Sep 29, 2016 at 11:37 AM, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > I'm playing with an early patch to make the default more dynamic. > Let's see how well it works in practice, but it looks fairly > promising. Let me test a bit more and send out an RFC patch..
Ok, this is *very* rough, and it doesn't actuall pass all the tests, and I didn't even try to look at why. But it passes the trivial smell-test, and in particular it actually makes mathematical sense...
I think the patch can speak for itself, but the basic core is this section in get_short_sha1():
+ if (len < 16 && !status && (flags & GET_SHA1_AUTOMATIC)) {
+ unsigned int expect_collision = 1 << (len * 2);
+ if (ds.nrobjects > expect_collision)
+ return SHORT_NAME_AMBIGUOUS;
+ }basically, what it says is that we will consider a sha1 ambiguous even if it was *technically* unique (that's the '!status' part of the test) if:
- the length was 15 or less
*and*
- the number of objects we have is larger than the expected point where statistically we should start to expect to get one collision.
That "expect_collision" math is actually very simple: each hex character adds four bits of range, but since we expect collisions at the square root of the maximum number of objects, we shift by just two bits per hex digits instead.
The rest of the patch is a trivial change to just initialize the default short size to -1, and consider that to mean "enable the automatic size checking with a minimum of 7". And the trivial code to estimate the number of objects (which ignores duplicates between packs etc _entirely_).
For the kernel, just the *math* right now actually gives 12 characters. For current git it actually seems to say that 8 is the correct number. For small projects, you'll still see 7.
ANYWAY. This patch is on top of Jeff's patches in 'pu' (I think those are great regardless of this patch!), and as mentioned, it fails some tests. I suspect that the failures might be due to the abbrev_default being -1, and some other code finds that surprising now. But as mentioned, I didn't really even look at it.
What do you think? It's actually a fairly simple patch and I really do think it makes sense and it seems to just DTRT automatically.
Linus
cache.h | 1 + environment.c | 2 +- sha1_name.c | 21 ++++++++++++++++++++- 3 files changed, 22 insertions(+), 2 deletions(-)
diff --git a/cache.h b/cache.h index 6e33f2f..d2da6d1 100644 --- a/cache.h +++ b/cache.h @@ -1207,6 +1207,7 @@ struct object_context { #define GET_SHA1_TREEISH 020 #define GET_SHA1_BLOB 040 #define GET_SHA1_FOLLOW_SYMLINKS 0100 +#define GET_SHA1_AUTOMATIC 0200 #define GET_SHA1_ONLY_TO_DIE 04000 #define GET_SHA1_DISAMBIGUATORS \ diff --git a/environment.c b/environment.c index c1442df..fd6681e 100644 --- a/environment.c +++ b/environment.c @@ -16,7 +16,7 @@ int trust_executable_bit = 1; int trust_ctime = 1; int check_stat = 1; int has_symlinks = 1; -int minimum_abbrev = 4, default_abbrev = 7; +int minimum_abbrev = 4, default_abbrev = -1; int ignore_case; int assume_unchanged; int prefer_symlink_refs; diff --git a/sha1_name.c b/sha1_name.c index 3b647fd..8791ff3 100644 --- a/sha1_name.c +++ b/sha1_name.c @@ -15,6 +15,7 @@ typedef int (*disambiguate_hint_fn)(const unsigned char *, void *); struct disambiguate_state { int len; /* length of prefix in hex chars */ + unsigned int nrobjects; char hex_pfx[GIT_SHA1_HEXSZ + 1]; unsigned char bin_pfx[GIT_SHA1_RAWSZ]; @@ -118,6 +119,12 @@ static void find_short_object_filename(struct disambiguate_state *ds) if (strlen(de->d_name) != 38) continue; + + // We only look at the one subdirectory, and we assume + // each subdirectory is roughly similar, so each object + // we find probably has 255 other objects in the other + // fan-out directories + ds->nrobjects += 256; if (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2)) continue; memcpy(hex + 2, de->d_name, 38); @@ -151,6 +158,7 @@ static void unique_in_pack(struct packed_git *p, open_pack_index(p); num = p->num_objects; + ds->nrobjects += num; last = num; while (first < last) { uint32_t mid = (first + last) / 2; @@ -426,6 +434,12 @@ static int get_short_sha1(const char *name, int len, unsigned char *sha1, for_each_abbrev(ds.hex_pfx, show_ambiguous_object, &ds); } + if (len < 16 && !status && (flags & GET_SHA1_AUTOMATIC)) { + unsigned int expect_collision = 1 << (len * 2); + if (ds.nrobjects > expect_collision) + return SHORT_NAME_AMBIGUOUS; + } + return status; } @@ -458,14 +472,19 @@ int for_each_abbrev(const char *prefix, each_abbrev_fn fn, void *cb_data) int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) { int status, exists; + int flags = GET_SHA1_QUIETLY; + if (len < 0) { + flags |= GET_SHA1_AUTOMATIC; + len = 7; + } sha1_to_hex_r(hex, sha1); if (len == 40 || !len) return 40; exists = has_sha1_file(sha1); while (len < 40) { unsigned char sha1_ret[20]; - status = get_short_sha1(hex, len, sha1_ret, GET_SHA1_QUIETLY); + status = get_short_sha1(hex, len, sha1_ret, flags); if (exists ? !status : status == SHORT_NAME_NOT_FOUND) {