Re: [PATCH 4/4] core.abbrev: raise the default abbreviation to 12 hexdigits

Johannes Sixt [off-list ref] writes:

Am 29.09.2016 um 01:30 schrieb Junio C Hamano:

quoted

As Peff said, responding in a thread started by Linus's suggestion
to raise the default abbreviation to 12 hexdigits:

This is waayy too large for a new default. The vast majority of
repositories is smallish. For those, the long sequences of hex digits
are an uglification that is almost unbearable.

I know that kernel developers are important, but their importance has
long been outnumbered by the anonymous and silent masses of users.

Personally, I use 8 digits just because it is a "rounder" number than
7, but in all of my repositories 7 would still work just as well.

Yes, "git log --oneline" looks somewhat different and strange for
me, too ;-)

I am sure I'll get used to it if I keep using it, but I suspect that
I'd be irritated as I find myself typing 'q' more and more often to
"less -S" that is automatically invoked when I do "git log --oneline
master.." to see what commits are on my current topic branch.

On Thu, Sep 29, 2016 at 11:05 AM, Junio C Hamano [off-list ref] wrote:

Yes, "git log --oneline" looks somewhat different and strange for
me, too ;-)

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

              Linus

On Thu, Sep 29, 2016 at 11:37 AM, Linus Torvalds
[off-list ref] 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

On Thu, Sep 29, 2016 at 11:55 AM, Linus Torvalds
[off-list ref] wrote:

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.

Sorry, the git number is 9, not 8. The reason is that git has roughly
212k objects, and 9 hex digits gets expected collisions at about 256k
objects.

So the logic means that we'll see 7 hex digits for projects with less
than 16k objects, 8 hex digits if there are less than 64k objects, and
9 hex digits for projects like git that currently have fewer than 256k
objects.

But git itself might not be *that* far from going to 10 hex digits
with my patch.

The kernel uses 12 he digits because the collision math says that's
the right thing for a project with between 4M and 16M objects (with
the kernel being at 5M).

So on the whole the patch really does seem to just do the right thing
automatically.

              Linus

On Thu, Sep 29, 2016 at 11:55:46AM -0700, Linus Torvalds wrote:

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

Hmm. So at length 7, we expect collisions at 2^14, which is 16384. That
seems really low. I mean, by the birthday paradox that's where expect
a 50% chance of a collision. But that's a single collision. We
definitely don't expect them to be common at that size.

So I suspect this could be a bit looser. The real number we care about
is probably something like "there is probability 'p' of a collision when
we add a new object", but I'm not sure what that 'p' would be. Or
perhaps "we accept collisions in 'n' percent of objects". But again, I
don't know that 'n'.

I dunno. I suppose being overly conservative with this number leaves
room for growth. Repositories generally get bigger, not smaller. :)

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.

I like the general idea.

As far as the implementation, I was surprised to see it touch
get_short_sha1() at all. That's, after all, for lookups, and we would
never want to require more characters on the reading side.

I see you worked around it with a flag so that this behavior only kicks
in when called via find_unique_abbrev(). But if you look at the caller:

You can see that we're going to do more work than we would otherwise
need to. Because we start at 7, and ask get_short_sha1() "is this unique
enough?", and looping. But if we _know_ we won't accept any answer
shorter than some N based on the number of objects in the repository,
then we should start at that N.

IOW, something like:

  if (len < 0)
	len = ceil(log_base_2(repository_object_count()));

here, and then you don't have to touch get_short_sha1() at all.

I suspect you pushed it down into get_short_sha1() because it kind-of
does the repository_object_count() step for "free" as it's looking at
the object anyway. But that step is really not very expensive. And I'd
even say you could just ignore loose objects entirely, and treat them
like a rounding error (the way that duplicate objects in packs are
treated).

That leaves you with just an O(# of packs) loop over a linked list. You
could even just keep a global object count up to date in
add_packed_git(), and then it's O(1).

-Peff

On Thu, Sep 29, 2016 at 12:16 PM, Jeff King [off-list ref] wrote:

Hmm. So at length 7, we expect collisions at 2^14, which is 16384. That
seems really low. I mean, by the birthday paradox that's where expect
a 50% chance of a collision. But that's a single collision. We
definitely don't expect them to be common at that size.

So I suspect this could be a bit looser.

So I have to admit that I was surprised by how quickly it actually
decided that 7 isn't enough. In fact, the reason I initially said that
git used 8 digits was that I didn't count very closely, and just
verified that it was more than the default 7.

But quite frankly, I think the math is correct, and part of that is
that the logic is all about not just the current state, but the
"reasonably near future".

So it is indeed fairly aggressive, and the moment you have more
objects than the "we'd expect to probably see  _one_ collision" it
grows the size. But looking at the kernel situation, that really is
what we'd want, because the whole problem with the existing code is
that it only takes the *current* situation into account. That's what
we want to get away from. We want git to pick a number that is sane
from a standpoint of "this project is still growing".

And git _already_ has commits that are ambiguous in 8 hex digits and
need 9. Yes, it's rare today, but the reason I'm telling kernel
developers to use 12 is because while a size-11 collision is very rare
today, it does actually happen, and we want o pick a value where it is
rare enough that even in the near future it's not going to be a big
deal.

Don't get me wrong: collisions aren't fatal. So it's not like we have
to absolutely avoid them, and I really like your patch series exactly
because it makes collisions even less of a deal (particularly since I
expect people will not upgrade immediately, so we'll continue to see
even new 7-hex-digit short forms even in the kernel). So it's a
balance of making the hex string long enough that it's simply not a
big worry.

So I'm sure it *could* be looser, but I actually also really suspect
that git truly *should* use a 9-digit abbreviation rather than 8 (and
7 is definitely starting to be borderline, I think).

As far as the implementation, I was surprised to see it touch
get_short_sha1() at all. That's, after all, for lookups, and we would
never want to require more characters on the reading side.

Heh. The implementation is crap. It was literally a "how can I make
the smallest possible patch" implementation. I was finishing it off
while at a talk by Nicolas Pitre at Linaro Connect where I am right
now.

So I agree - it does extra work just because that's where it all
slotted in with minimal effort.

At a minimum, once it finds a good new default, it should just memoize
that. So a minimal fix to the "it's stupldly recalculating things over
rand over again" would be to just set "default_abbrev" to the value it
finds acceptable after the first time it finds something, so that it
doesn't end up looping _again_ in the future.

But you could easily also just instead have it do something like

      if (default_abbrev < 0)
            default_abbrev = initialize_abbrev();

at startup time if "abbrev_commit" is set, and just do it once and for
all rather rthan the odd loping behavior.

I really just wanted to see how well the concept worked, and I was
happy to see that it gave what I thought were the "correct" numbers.
And the loop was salready there ...

            Linus

On Thu, Sep 29, 2016 at 5:56 PM, Mike Hommey [off-list ref] wrote:

OTOH, how often does one refer to trees or blobs with abbreviated sha1s?
Most of the time, you'd use abbreviated sha1s for commits. And the number
of commits in git and the kernel repositories are much lower than the
number of overall objects.

See that whole other discussion about this. I agree. If we only ever
worried about just commits, the abbreviation length wouldn't need to
be grown nearly as aggressively. The current default would still be
wrong for the kernel, but it wouldn't be as noticeably wrong, and
updating it to 8 or 9 would be fine.

That said, people argued against that too. We *do* end up having
abbreviated SHA1's for blobs in the diff index. When I said that _I_
neer use it, somebody piped up to say that they do.

So I'd rather just keep the existing semantics (a hash is a hash is a
hash), and just abbreviate at a sufficient point that we don't have to
worry too much about disambiguating further by object type.

      Linus

On Thu, Sep 29, 2016 at 12:06:23PM -0700, Linus Torvalds wrote:

On Thu, Sep 29, 2016 at 11:55 AM, Linus Torvalds
[off-list ref] wrote:

quoted

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.

Sorry, the git number is 9, not 8. The reason is that git has roughly
212k objects, and 9 hex digits gets expected collisions at about 256k
objects.

So the logic means that we'll see 7 hex digits for projects with less
than 16k objects, 8 hex digits if there are less than 64k objects, and
9 hex digits for projects like git that currently have fewer than 256k
objects.

But git itself might not be *that* far from going to 10 hex digits
with my patch.

The kernel uses 12 he digits because the collision math says that's
the right thing for a project with between 4M and 16M objects (with
the kernel being at 5M).

OTOH, how often does one refer to trees or blobs with abbreviated sha1s?
Most of the time, you'd use abbreviated sha1s for commits. And the number
of commits in git and the kernel repositories are much lower than the
number of overall objects.

rev-list --all --count on the git repo gives me 46790. On the kernel, it
gives 618078.

Now, the interesting thing is looking at the *actual* collisions in
those spaces.

At 9 digits, there's only one commit collision in the kernel repo:
  45f014c5264f5e68ef0e51b36f4ef5ede3d18397
  45f014c52eef022873b19d6a20eb0ec9668f2b09

And two commit collisions at 8 digits in the git repo:
  1536dd9c1df0b7167b139f6666080cc4774ef63f
  1536dd9c61b5582cf079999057cb715dd6dc6620

  2e6e3e82ee36b3e1bec1db8db24817270080424e
  2e6e3e829f3759823d70e7af511bc04cd05ad0af

At 7 digits, there are 5 actual commit collisions in the git repo and
718 in the kernel repo only one of those collisions involve more than 2
commits.

Mike

On Fri, Sep 30, 2016 at 3:01 AM, Linus Torvalds
[off-list ref] wrote:

On Thu, Sep 29, 2016 at 5:56 PM, Mike Hommey [off-list ref] wrote:

quoted

OTOH, how often does one refer to trees or blobs with abbreviated sha1s?
Most of the time, you'd use abbreviated sha1s for commits. And the number
of commits in git and the kernel repositories are much lower than the
number of overall objects.

See that whole other discussion about this. I agree. If we only ever
worried about just commits, the abbreviation length wouldn't need to
be grown nearly as aggressively. The current default would still be
wrong for the kernel, but it wouldn't be as noticeably wrong, and
updating it to 8 or 9 would be fine.

That said, people argued against that too. We *do* end up having
abbreviated SHA1's for blobs in the diff index. When I said that _I_
neer use it, somebody piped up to say that they do.

So I'd rather just keep the existing semantics (a hash is a hash is a
hash), and just abbreviate at a sufficient point that we don't have to
worry too much about disambiguating further by object type.

I work on a repo that's around the size of linux.git in every way
(commits, objects etc.), and growing twice as fast.

So I also see 8 or 9 digit abbreviations on a daily basis, even with
the current defaults core.abbrev, but I still think growing it so
aggressively is the wrong thing to do.

The fact that we have a core.abbrev option at all and nobody's talking
about getting rid of it entirely means we all acknowledge the UX
convenience of short SHA1s.

I don't think it's a good idea for such UX options to have defaults
that really only make sense for repositories at the very far end of
the bell curve, which is the case with linux.git and the repo I work
on.

Either way you're going to waste somebody's time. I think it's a
better trade-off that some kernel dev occasionally has to look at
Peff's new disambiguation output, than have the wast hordes of
everyday Git users have less screen real estate, need to recite longer
sha1s over the phone during outages (people do that), and any number
of other every day use cases.

I think if anything we should be talking about making the default
shorter & then have some clever auto-scaling by repository size as has
been discussed in this thread to deal with the repositories at the far
end of the bell curve.