4 ms·

Doing the math, 2 to the 28th is around 268 million.

by pronoiac 5y ago

988747 5y ago
I can imagine a big company with a monorepo (i.e. Google) reaching that number in a few years.
- wruza 5y ago
  This number may be even lower if you take the birthday problem into account. I’m not a statistics guy to confirm that or to make proper calculations, but I believe it applies to this case as well, because first few bits of a hash are like what a birthday is to an otherwise unique person. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- whatshisface 5y ago
  Generously, there are about 40,000 people at Google who might commit to the monorepo. That's only 6,000 or so commits per person, a fairly achievable number. Although since they're not purposely generating every shorthash, it would take significantly longer for the absolute last unique hash to be created.
  - charcircuit 5y ago
    Don't forget the commits made by programs.
  - yellow_lead 5y ago
    I wonder what the number of commits is before you need to start worrying about 7 character collisions. (Birthday problem anyone?)
    - sltkr 5y ago
      You answered your own question. After 2^14 = 16,384 commits, there is a 50% chance of a collision. So most large repos will have collisions. This isn't a problem for Git. It accepts arbitrary prefixes so you'll just have to type a few more characters if you want to refer to a commit whose 28-bit prefix (7 hex digits) is not unique.
  - sltkr 5y ago
    Google published some info about their repository in 2016: https://cacm.acm.org/magazines/2016/7/204032-why-google-stores-billions-of-lines-of-code-in-a-single-repository/fulltext https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... Some choice quotes: > The Google codebase includes approximately one billion files and has a history of approximately 35 million commits spanning Google's entire 18-year existence. > Google's codebase is shared by more than 25,000 Google software developers from dozens of offices in countries around the world. On a typical workday, they commit 16,000 changes to the codebase, and another 24,000 changes are committed by automated systems. Note that this was 5 years ago. If you look at the number of commits over time, it is growing exponentially, about sevenfold over the last 5 years: https://dl.acm.org/cms/attachment/c219bd10-b97a-402e-bc94-798e909c821c/f1.jpg https://dl.acm.org/cms/attachment/c219bd10-b97a-402e-bc94-79... If you assume another sevenfold increase over the past 5 years, then they should have around 250 million commits now.
    - scottlamb 5y ago
      > If you assume another sevenfold increase over the past 5 years, then they should have around 250 million commits now. Decent guess. Rate's gone up; they're at about 382 million now. [1] You can see the current number in the PiperOrigin-RevId: on several public repositories that get changes synced from Google's internal Piper. I'm not looking at that paper (as I'm about to walk out the door); one thing to check is if the number there includes just the actual commits or also the pending CL numbers (same concept as Perforce). The number I'm quoting includes both. [1] https://github.com/google/tcmalloc/commit/6f42c40d6ebcf2aeb8c4379da5d6be81bb4c1797 https://github.com/google/tcmalloc/commit/6f42c40d6ebcf2aeb8...
      - jeffbee 5y ago
        That’s going to be at least some kind of fun when it crosses 2^31.
    - ahmedfromtunis 5y ago
      A bit off topic, but does this mean that each of 25k Google developers has a copy of the entire codebase on their laptops? Or is there a way to cherrypick parts of it?
  - remram 5y ago
    If a commit touches many files, do the hashes for the blobs and trees contribute to the ambiguity? E.g. does Git choose the commit over the tree if you checkout a short hash that could be either?
  - kleton 5y ago
    Piper gets at least 10s or even 100s of CLs a second
- pronoiac 5y ago
  From the "unexpectedly useful for security research" link: > Due to the birthday problem, any repository that has at least 19291 commits is likely to have a pair of ambiguous commits somewhere.
  - ghoward 5y ago
    I can't find the link. :( Edit: nevermind; I am stupid.
  - sverhagen 5y ago
    I feel I have seen much smaller repositories than that with ambiguous commits. Case in point: looking at one here with 56 commits in the reflog, already using 8-character shorthands.
- codetrotter 5y ago
  Note that collisions in short hash are not actually a problem as such. > Git can figure out a short, unique abbreviation for your SHA-1 values. If you pass --abbrev-commit to the git log command, the output will use shorter values but keep them unique; it defaults to using seven characters but makes them longer if necessary to keep the SHA-1 unambiguous https://git-scm.com/book/en/v2/Git-Tools-Revision-Selection https://git-scm.com/book/en/v2/Git-Tools-Revision-Selection and also > Git doesn't really truncate anything, internally everything will be handled with the complete value. https://stackoverflow.com/questions/7128444/how-does-github-handle-possible-collisions-from-short-shas https://stackoverflow.com/questions/7128444/how-does-github-...
  - IgorPartola 5y ago
    I wonder how many tools out there hard code the 7 character length for a hit commit hash length and would break upon a collision.
- malkia 5y ago
  AFAIK, Google's g4 is the successor to p4 (perforce), and it uses monotonically increasing number ("CL") instead of hash. From what I can remember, it was one way to specify a build - e.g. this binary was build with CL=12345 (baseline) + cherry picks (e.g. locally checked out) CL's 123450, 123455, 123460 - hence one would always know where it's in the timeline of things based on just this number.
remram 5y ago
A good time of thumb is 10 powers of two is 3 powers of ten (2^10=1024~=10^3) So 2^28 is 1/4 of a billion (10^9)
- pronoiac 5y ago
  If we were counting bytes of memory, it would be 256MB.

Doing the math, 2 to the 28th is around 268 million.

988747 5y ago

I can imagine a big company with a monorepo (i.e. Google) reaching that number in a few years.

wruza 5y ago
This number may be even lower if you take the birthday problem into account. I’m not a statistics guy to confirm that or to make proper calculations, but I believe it applies to this case as well, because first few bits of a hash are like what a birthday is to an otherwise unique person. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
whatshisface 5y ago
Generously, there are about 40,000 people at Google who might commit to the monorepo. That's only 6,000 or so commits per person, a fairly achievable number. Although since they're not purposely generating every shorthash, it would take significantly longer for the absolute last unique hash to be created.
- charcircuit 5y ago
  Don't forget the commits made by programs.
- yellow_lead 5y ago
  I wonder what the number of commits is before you need to start worrying about 7 character collisions. (Birthday problem anyone?)
  - sltkr 5y ago
    You answered your own question. After 2^14 = 16,384 commits, there is a 50% chance of a collision. So most large repos will have collisions. This isn't a problem for Git. It accepts arbitrary prefixes so you'll just have to type a few more characters if you want to refer to a commit whose 28-bit prefix (7 hex digits) is not unique.
- sltkr 5y ago
  Google published some info about their repository in 2016: https://cacm.acm.org/magazines/2016/7/204032-why-google-stores-billions-of-lines-of-code-in-a-single-repository/fulltext https://cacm.acm.org/magazines/2016/7/204032-why-google-stor... Some choice quotes: > The Google codebase includes approximately one billion files and has a history of approximately 35 million commits spanning Google's entire 18-year existence. > Google's codebase is shared by more than 25,000 Google software developers from dozens of offices in countries around the world. On a typical workday, they commit 16,000 changes to the codebase, and another 24,000 changes are committed by automated systems. Note that this was 5 years ago. If you look at the number of commits over time, it is growing exponentially, about sevenfold over the last 5 years: https://dl.acm.org/cms/attachment/c219bd10-b97a-402e-bc94-798e909c821c/f1.jpg https://dl.acm.org/cms/attachment/c219bd10-b97a-402e-bc94-79... If you assume another sevenfold increase over the past 5 years, then they should have around 250 million commits now.
  - scottlamb 5y ago
    > If you assume another sevenfold increase over the past 5 years, then they should have around 250 million commits now. Decent guess. Rate's gone up; they're at about 382 million now. [1] You can see the current number in the PiperOrigin-RevId: on several public repositories that get changes synced from Google's internal Piper. I'm not looking at that paper (as I'm about to walk out the door); one thing to check is if the number there includes just the actual commits or also the pending CL numbers (same concept as Perforce). The number I'm quoting includes both. [1] https://github.com/google/tcmalloc/commit/6f42c40d6ebcf2aeb8c4379da5d6be81bb4c1797 https://github.com/google/tcmalloc/commit/6f42c40d6ebcf2aeb8...
    - jeffbee 5y ago
      That’s going to be at least some kind of fun when it crosses 2^31.
  - ahmedfromtunis 5y ago
    A bit off topic, but does this mean that each of 25k Google developers has a copy of the entire codebase on their laptops? Or is there a way to cherrypick parts of it?
- remram 5y ago
  If a commit touches many files, do the hashes for the blobs and trees contribute to the ambiguity? E.g. does Git choose the commit over the tree if you checkout a short hash that could be either?
- kleton 5y ago
  Piper gets at least 10s or even 100s of CLs a second
pronoiac 5y ago
From the "unexpectedly useful for security research" link: > Due to the birthday problem, any repository that has at least 19291 commits is likely to have a pair of ambiguous commits somewhere.
- ghoward 5y ago
  I can't find the link. :( Edit: nevermind; I am stupid.
- sverhagen 5y ago
  I feel I have seen much smaller repositories than that with ambiguous commits. Case in point: looking at one here with 56 commits in the reflog, already using 8-character shorthands.
codetrotter 5y ago
Note that collisions in short hash are not actually a problem as such. > Git can figure out a short, unique abbreviation for your SHA-1 values. If you pass --abbrev-commit to the git log command, the output will use shorter values but keep them unique; it defaults to using seven characters but makes them longer if necessary to keep the SHA-1 unambiguous https://git-scm.com/book/en/v2/Git-Tools-Revision-Selection https://git-scm.com/book/en/v2/Git-Tools-Revision-Selection and also > Git doesn't really truncate anything, internally everything will be handled with the complete value. https://stackoverflow.com/questions/7128444/how-does-github-handle-possible-collisions-from-short-shas https://stackoverflow.com/questions/7128444/how-does-github-...
- IgorPartola 5y ago
  I wonder how many tools out there hard code the 7 character length for a hit commit hash length and would break upon a collision.
malkia 5y ago
AFAIK, Google's g4 is the successor to p4 (perforce), and it uses monotonically increasing number ("CL") instead of hash. From what I can remember, it was one way to specify a build - e.g. this binary was build with CL=12345 (baseline) + cherry picks (e.g. locally checked out) CL's 123450, 123455, 123460 - hence one would always know where it's in the timeline of things based on just this number.

remram 5y ago

A good time of thumb is 10 powers of two is 3 powers of ten (2^10=1024~=10^3) So 2^28 is 1/4 of a billion (10^9)

pronoiac 5y ago
If we were counting bytes of memory, it would be 256MB.