21–30 of 68 posts
To clarify: the likelihood of being merely struck by lightning is ~ 1/1,000,000 per year. The likelihood of being struck and killed is 1/10,000,000 , or about 1/2^23.25
Given this, you would only have to be struck and killed by lightning 6.8 years in a row to equal a sha1 hash collision probability.
They were off by a factor of 10 with the likelihood of being struck and killed by lightning, according to the nws website. To clarify: the likelihood of being merely struck by lightning is ~ 1/1,000,000 per year. The likelihood of being struck and killed is 1/10,000,000 , or about 1/2^23.25 Given this, you would only have to be struck and killed by lightning 6.8 years in a row to equal a sha1 hash collision probabili…
They were off by a factor of 10 with the likelihood of being struck and killed by lightning, according to the nws website. To clarify: the likelihood of being merely struck by lightning is ~ 1/1,000,000 per year. The likelihood of being struck and killed is 1/10,000,000 , or about 1/2^23.25 Given this, you would only have to be struck and killed by lightning 6.8 years in a row to equal a sha1 hash collision probabili…
There are a lot of other caveats, too. Such as the idea of each year being an independent probability.
I'm curious but not motivated enough to really search for it, but for ambiguous hash abbreviations, why not select the oldest, since presumably it was unique at the time it was created? edit: I guess that information must not exist or I assume they'd be doing it.
However, there'a more complicated issue with timestamps, with is that you care about what was in the repository of the person who generated the sha1, at the time of generation. So you could merge in history that includes older commits, and invalidate your sha1s with "older" objects.
So the timestamp of interest is not the one in the objects themselves, but when they entered some particular repository (and not even some well-known repository; the local clone of whoever happened to generate the sha1). That being said, those two things correlate a lot in practice, and auto-picking the oldest commit might be a useful heuristic.
It would be a fun project to implement as an option for `core.disambiguate`.
Converting to and from base 36 (or 32) would probably do more to help the problem than any heuristics. Compare: 66c22ba6fbe0724ecce3d82611ff0ec5c2b0255f to: c04bo5604v5qsp6asgasjp9y4paxu8v That's approx a 25% gain in compactness.
That's an interesting thought, and I don't feel there's any advantage in the text being in hex. The only problem would by now probably too much code expects hex, so I'm not sure the gain is big enough to go through the pain of the switch.
Great write-up! I love the focus on performance in this release. I've put together another write-up of the Git 2.11 release that discusses some of the other new features (and goes into a little more detail on some of the 'sundries'): https://medium.com/@kannonboy/whats-new-in-git-2-11-64860aea...
I'm also curious how you came up with 19,290 for a birthday paradox on a 7-hex hash. I think it's 16,384, but probability can sometimes be tricky. :)
Hexadecimal dumps of binary data are the worst of all worlds if used as keys/references. Hard to memorize, hard to type, look ugly, aren't compact. Better alternatives: Base64 without padding: compact. Grouped decimals: slightly less compact than hexadecimal, but extremely easy to type and pronounce. E.g. 577-467-341-467
Same thing when speaking it out loud. 'B four D capital Q B capital F s thirty-one' is way more convoluted and error-prone than 'B four D Q B F S thirty-one'.
The best thing I've found that fits this criterion is Crockford's Base 32 [1], basically the extension of hex digits, removing letters ILOU.
But Base 32 (case-insensitivity by proxy) constrains us to 5 bits, which is only a 20% reduction over the 4 bits of base 16. So instead of the 20 bits `1ab2f` we could express them with something like `1qm3`.
Or we could be using words...
Hexadecimal dumps of binary data are the worst of all worlds if used as keys/references. Hard to memorize, hard to type, look ugly, aren't compact. Better alternatives: Base64 without padding: compact. Grouped decimals: slightly less compact than hexadecimal, but extremely easy to type and pronounce. E.g. 577-467-341-467
Still better is grouped alphanumeric without potentially ambiguous characters (ie. generate number-1's but not letter-I's, generate number-0's but not letter-O's). I wrote a disambiguation library based upon the checksums present in IBAN @ https://github.com/globalcitizen/php-iban .. it's surprising how accurate the mistranscription suggestions are. In general, pure-number systems are better if possible, but where yo…
git license-plate?
Great write-up! I love the focus on performance in this release. I've put together another write-up of the Git 2.11 release that discusses some of the other new features (and goes into a little more detail on some of the 'sundries'): https://medium.com/@kannonboy/whats-new-in-git-2-11-64860aea...
That is a nice writeup. One of the interesting things for me was to see which topics you decided to cover and which to omit. For instance, I noted `clone --reference --recurse-submodules` as a potential topic of interest, but I am afraid to point anybody to the `--reference` option due to its hidden dangers. I'm also curious how you came up with 19,290 for a birthday paradox on a 7-hex hash. I think it's 16,384, but…
I came up with 19,290 using the generalized birthday formula[0] (actually after double-checking it's slightly closer to 19,291).
16,384 is the value you get using the square approximation method[1] which I believe is a bit less accurate in terms of probability, but faster to calculate. I think Git's using square approximation under the hood -- which is probably a good thing since I think it'll always yield a more conservative result.
[0]: https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_col...
[1]: https://en.wikipedia.org/wiki/Birthday_problem#Square_approx...
Although it's worth noting mercurial and git use different delta formats.
Edit: This is apparently what chooses to store a delta or not in mercurial: https://www.mercurial-scm.org/repo/hg/file/9e29d4e4e08b/merc... self._maxchainlen is not set by default.