{"thread":{"id":"7495","subject":"Distribution of longest common hash prefixes","startedAt":"2007-04-02T14:58:57Z","lastAt":"2007-04-04T21:03:02Z","messageCount":20,"participants":["Peter Eriksen","Linus Torvalds","Randal L. Schwartz","James Cloos","Shawn O. Pearce","Junio C Hamano","Nicolas Pitre","Olivier Galibert"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"38479","messageId":"20070402145857.GA13293@bohr.gbar.dtu.dk","threadId":"7495","inReplyTo":null,"subject":"Distribution of longest common hash prefixes","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2007-04-02T14:58:57Z","receivedAt":"2007-04-02T14:58:57Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"Hello,\n\nWith the recent and ongoing discussion about a more efficient .idx\nformat, I got curious about how long the longest common prefix between\ntwo hashes is in git various projects. So I did\n\n$ git rev-list --objects HEAD | cut -b1-40 | sort >proj.list\n$ lcprefix proj.list\n\nand decided to compare all neighbour hashes with each other, finding the\nlongest common prefix in bits between them. These numbers were then\ntabulated into bins on the number of bits.\n\nWhy does it look so sparse and strange?\n\nThe following is the output of the program bellow on the linux-2.6.git\narchive:\n\n\n0000d162d198a60d558ab4be3f54f608ff8b7473\n0000de01ec150d1a291564818571f719a6a6190f\nlcprefix = 20\n00038c17317a3633f176f17876e69d8e31a5c708\n00038ef0cad0a60ee7cace23ade5dfb325b7700d\nlcprefix = 22\n00108a8dd8d4d772ac6a91efde40191392ba4624\n00108ba9a78dcef5629ead0e8bea35d0c08c9ea7\nlcprefix = 23\n001c2d57248586464da570017e368e188eb4d270\n001c2d594f26b529fdabb6cf05deaa384f400e12\nlcprefix = 28\n002c9920c7bc3cbf74b4cdc03491f80f68917528\n002c9922e55255556f1bebea8772aa58c9724825\nlcprefix = 30\n15d954e50cae6e816b534bf959c49a2920bef808\n15d954e51e5b40cf4d5930708fe98076adb1063a\nlcprefix = 35\nd37bdb4d4930ddb390902c19cffe6552d93d3fcf\nd37bdb4d4c9c821e4765f10c206fa613f7781b65\nlcprefix = 37\n 0: 0\n 1: 0\n 2: 0\n 3: 0\n 4: 0\n 5: 0\n 6: 0\n 7: 0\n 8: 0\n 9: 0\n10: 0\n11: 0\n12: 0\n13: 0\n14: 0\n15: 0\n16: 0\n17: 0\n18: 0\n19: 8\n20: 19\n21: 0\n22: 87\n23: 70\n24: 0\n25: 0\n26: 0\n27: 0\n28: 116\n29: 0\n30: 36975\n31: 0\n32: 0\n33: 0\n34: 0\n35: 325071\n36: 0\n37: 76996\n38: 0\n39: 0\n40: 0\n41: 0\n42: 0\n43: 0\n44: 0\n45: 0\n46: 0\n47: 0\n48: 0\n49: 0\n50: 0\n51: 0\n52: 0\n53: 0\n54: 0\n55: 0\n56: 0\n57: 0\n58: 0\n59: 0\n60: 0\n61: 0\n62: 0\n63: 0\n\n\n======================= >8 ============================\n#include \n#include \n\n\nint h2d(char c)\n{\n\tif ('a' <= c && c <= 'f')\n\t\treturn c-'a'+10;\n\telse\n\t\treturn c-'0';\n}\n\nint lcprefix(char *a, char *b)\n{\n\tint i = 0;\n\tint j = 4;\n\twhile (a[i] == b[i])\n\t\ti++;\n\n\twhile ((h2d(a[i])< \n> Why does it look so sparse and strange?\n\nBecause your program is buggy.\n\nYou do\n\n\ttable[lcp]++;\n\neven though \"lcp\" is always that *maximum* lcp at any time, not the \ncurrent one!\n\nHere's a fixed program (although that first lcp thing is still bogus, I\njust left it as you had it), and fixed output.. \n\n\t0000d162d198a60d558ab4be3f54f608ff8b7473\n\t0000de01ec150d1a291564818571f719a6a6190f\n\tlcprefix = 20\n\t00038c17317a3633f176f17876e69d8e31a5c708\n\t00038ef0cad0a60ee7cace23ade5dfb325b7700d\n\tlcprefix = 22\n\t00108a8dd8d4d772ac6a91efde40191392ba4624\n\t00108ba9a78dcef5629ead0e8bea35d0c08c9ea7\n\tlcprefix = 23\n\t001c2d57248586464da570017e368e188eb4d270\n\t001c2d594f26b529fdabb6cf05deaa384f400e12\n\tlcprefix = 28\n\t002c9920c7bc3cbf74b4cdc03491f80f68917528\n\t002c9922e55255556f1bebea8772aa58c9724825\n\tlcprefix = 30\n\t15d954e50cae6e816b534bf959c49a2920bef808\n\t15d954e51e5b40cf4d5930708fe98076adb1063a\n\tlcprefix = 35\n\td37bdb4d4930ddb390902c19cffe6552d93d3fcf\n\td37bdb4d4c9c821e4765f10c206fa613f7781b65\n\tlcprefix = 37\n\t 0: 1\n\t 1: 2\n\t 2: 4\n\t 3: 8\n\t 4: 16\n\t 5: 32\n\t 6: 64\n\t 7: 128\n\t 8: 256\n\t 9: 512\n\t10: 1024\n\t11: 2048\n\t12: 4096\n\t13: 8192\n\t14: 16384\n\t15: 32685\n\t16: 60921\n\t17: 86511\n\t18: 84426\n\t19: 61518\n\t20: 37450\n\t21: 20728\n\t22: 11035\n\t23: 5562\n\t24: 2812\n\t25: 1467\n\t26: 738\n\t27: 355\n\t28: 191\n\t29: 83\n\t30: 49\n\t31: 27\n\t32: 10\n\t33: 3\n\t34: 1\n\t35: 2\n\t36: 0\n\t37: 1\n\t38: 0\n\t39: 0\n\t40: 0\n\t41: 0\n\t42: 0\n\t43: 0\n\t44: 0\n\t45: 0\n\t46: 0\n\t47: 0\n\t48: 0\n\t49: 0\n\t50: 0\n\t51: 0\n\t52: 0\n\t53: 0\n\t54: 0\n\t55: 0\n\t56: 0\n\t57: 0\n\t58: 0\n\t59: 0\n\t60: 0\n\t61: 0\n\t62: 0\n\t63: 0\n\nwhich looks much saner..\n\n\t\tLinus\n\n---\n#include \n#include \n\n\nint h2d(char c)\n{\n\tif ('a' <= c && c <= 'f')\n\t\treturn c-'a'+10;\n\telse\n\t\treturn c-'0';\n}\n\nint lcprefix(char *a, char *b)\n{\n\tint bits = 0;\n\tunsigned n1, n2;\n\n\twhile (*a == *b) {\n\t\tbits += 4;\n\t\ta++;\n\t\tb++;\n\t}\n\n\tn1 = h2d(*a);\n\tn2 = h2d(*b);\n\n\t/* Would make more sense to start from bit 0.. */\n\twhile ((n1 & 8) == (n2 & 8)) {\n\t\tbits++;\n\t\tn1 <<= 1;\n\t\tn2 <<= 1;\n\t}\n\t\n\treturn bits;\n}\n\nint main(int argc, char **argv)\n{\n\tFILE *fp;\n\tchar old[41];\n\tchar cur[41];\n\tint lcp = 0;\n\tint table[64];\n\tint i;\n\n\tmemset(table, 0, 64*sizeof(int));\n\tmemset(old, '0', 40);\n\told[40] = '\\0';\n\n\tfp = fopen(argv[1], \"r\");\n\tfscanf(fp, \"%s\\n\", cur);\n\n\tif (lcp < lcprefix(old, cur)) {\n\t\tlcp = lcprefix(old, cur);\n\t}\n\n\ttable[lcp]++;\n\twhile (fscanf(fp, \"%s\\n\", cur) != EOF) {\n\t\tint newlcp = lcprefix(old, cur);\n\t\ttable[newlcp]++;\n\t\tif (lcp < newlcp) {\n\t\t\tprintf(\"%s\\n%s\\n\", old, cur);\n\t\t\tlcp = newlcp;\n\t\t\tprintf(\"lcprefix = %d\\n\", newlcp);\n\t\t}\n\t\tmemcpy(old, cur, 40);\n\t}\n\n\tfor(i = 0; i < 64; i++) {\n\t\tprintf(\"%2d: %2d\\n\", i, table[i]);\n\t}\n\t\n\treturn 0;\n}\n"},{"id":"38480","messageId":"20070402152835.GB13293@bohr.gbar.dtu.dk","threadId":"7495","inReplyTo":"20070402145857.GA13293@bohr.gbar.dtu.dk","subject":"Re: Distribution of longest common hash prefixes","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2007-04-02T15:28:35Z","receivedAt":"2007-04-02T15:28:35Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Mon, Apr 02, 2007 at 04:58:57PM +0200, Peter Eriksen wrote:\n...\n> Why does it look so sparse and strange?\n\n... and here is the nonbroken version, which is neither sparse nor\nstrange. Thanks to chris on #git for the nice programming lesson.\nMore correct output and program bellow.\n\nPeter\n\n\n 0: 1\n 1: 2\n 2: 4\n 3: 8\n 4: 16\n 5: 32\n 6: 64\n 7: 128\n 8: 256\n 9: 512\n10: 1024\n11: 2048\n12: 4096\n13: 8192\n14: 16384\n15: 32685\n16: 60921\n17: 86511\n18: 84426\n19: 61518\n20: 37450\n21: 20728\n22: 11035\n23: 5562\n24: 2812\n25: 1467\n26: 738\n27: 355\n28: 191\n29: 83\n30: 49\n31: 27\n32: 10\n33: 3\n34: 1\n35: 2\n36: 0\n37: 1\n38: 0\n39: 0\n40: 0\n41: 0\n42: 0\n43: 0\n44: 0\n45: 0\n46: 0\n47: 0\n48: 0\n49: 0\n50: 0\n51: 0\n52: 0\n53: 0\n54: 0\n55: 0\n56: 0\n57: 0\n58: 0\n59: 0\n60: 0\n61: 0\n62: 0\n63: 0\n\n\n\n#include \n#include \n\n\nint h2d(char c)\n{\n\tif ('a' <= c && c <= 'f')\n\t\treturn c-'a'+10;\n\telse\n\t\treturn c-'0';\n}\n\nint lcprefix(char *a, char *b)\n{\n\tint i = 0;\n\tint j = 4;\n\twhile (a[i] == b[i])\n\t\ti++;\n\n\twhile ((h2d(a[i])<>>>> \"Linus\" == Linus Torvalds writes:\n\nLinus> On Mon, 2 Apr 2007, Peter Eriksen wrote:\n\nLinus> #include \nLinus> #include \n\n\nLinus> int h2d(char c)\nLinus> {\nLinus> \tif ('a' <= c && c <= 'f')\nLinus> \t\treturn c-'a'+10;\nLinus> \telse\nLinus> \t\treturn c-'0';\nLinus> }\n\nLinus> int lcprefix(char *a, char *b)\nLinus> {\nLinus> \tint bits = 0;\nLinus> \tunsigned n1, n2;\n\nLinus> \twhile (*a == *b) {\nLinus> \t\tbits += 4;\nLinus> \t\ta++;\nLinus> \t\tb++;\nLinus> \t}\n\nLinus> \tn1 = h2d(*a);\nLinus> \tn2 = h2d(*b);\n\nLinus> \t/* Would make more sense to start from bit 0.. */\nLinus> \twhile ((n1 & 8) == (n2 & 8)) {\nLinus> \t\tbits++;\nLinus> \t\tn1 <<= 1;\nLinus> \t\tn2 <<= 1;\nLinus> \t}\n\t\nLinus> \treturn bits;\nLinus> }\n\nLinus> int main(int argc, char **argv)\nLinus> {\nLinus> \tFILE *fp;\nLinus> \tchar old[41];\nLinus> \tchar cur[41];\nLinus> \tint lcp = 0;\nLinus> \tint table[64];\nLinus> \tint i;\n\nLinus> \tmemset(table, 0, 64*sizeof(int));\nLinus> \tmemset(old, '0', 40);\nLinus> \told[40] = '\\0';\n\nLinus> \tfp = fopen(argv[1], \"r\");\nLinus> \tfscanf(fp, \"%s\\n\", cur);\n\nLinus> \tif (lcp < lcprefix(old, cur)) {\nLinus> \t\tlcp = lcprefix(old, cur);\nLinus> \t}\n\nLinus> \ttable[lcp]++;\nLinus> \twhile (fscanf(fp, \"%s\\n\", cur) != EOF) {\nLinus> \t\tint newlcp = lcprefix(old, cur);\nLinus> \t\ttable[newlcp]++;\nLinus> \t\tif (lcp < newlcp) {\nLinus> \t\t\tprintf(\"%s\\n%s\\n\", old, cur);\nLinus> \t\t\tlcp = newlcp;\nLinus> \t\t\tprintf(\"lcprefix = %d\\n\", newlcp);\nLinus> \t\t}\nLinus> \t\tmemcpy(old, cur, 40);\nLinus> \t}\n\nLinus> \tfor(i = 0; i < 64; i++) {\nLinus> \t\tprintf(\"%2d: %2d\\n\", i, table[i]);\nLinus> \t}\n\t\nLinus> \treturn 0;\nLinus> }\n\nI don't have access to the linux-2.6 kernel, but on git.git at\nd8b6a1a10b93666246984a50d64a163e71163aeb I get this:\n\n $ git-rev-list --objects HEAD | sort | perl -lne '\n substr($_, 40) = \"\";\n ($p ^ $_) =~ /^(\\0*)/;\n $count[length $1]++;\n $p = $_;\n END { print \"$_: $count[$_]\" for 0..$#count }\n '\n 0: 16\n 1: 240\n 2: 3839\n 3: 24458\n 4: 8275\n 5: 619\n 6: 45\n 7: \n 8: 1\n\nYeay Perl. :)\n\n-- \nRandal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095\n \nPerl/Unix/security consulting, Technical writing, Comedy, etc. etc.\nSee PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!\n"},{"id":"38484","messageId":"Pine.LNX.4.64.0704020938470.6730@woody.linux-foundation.org","threadId":"7495","inReplyTo":"86bqi6kae7.fsf@blue.stonehenge.com","subject":"Re: Distribution of longest common hash prefixes","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-02T17:00:22Z","receivedAt":"2007-04-02T17:00:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 2 Apr 2007, Randal L. Schwartz wrote:\n> \n> I don't have access to the linux-2.6 kernel, but on git.git at\n> d8b6a1a10b93666246984a50d64a163e71163aeb I get this:\n> \n> $ git-rev-list --objects HEAD | sort | perl -lne '\n> substr($_, 40) = \"\";\n> ($p ^ $_) =~ /^(\\0*)/;\n> $count[length $1]++;\n> $p = $_;\n> END { print \"$_: $count[$_]\" for 0..$#count }\n> '\n> 0: 16\n> 1: 240\n> 2: 3839\n> 3: 24458\n> 4: 8275\n> 5: 619\n> 6: 45\n> 7: \n> 8: 1\n> \n> Yeay Perl. :)\n\nNo yay yet.. That counts hex digits, not bits.\n\nHowever, both this and Peter's original thing show an interesting pattern \nin common: for the case where the data is dense (ie a few bits in common), \nyou actually don't end up counting \"bits in common\", but \"edges when the \nbits change in the sorted output\".\n\nFor example, in the above, the 16/240/3839 comes simply from the fact that \nthere are sixteen times that the first digit changes (and that makes the \nprogram think that it has zero bits in common). There are 256 times that \nthe two first digit changes, but 16 of those the first one changed too, so \nonly in 240 cases did just the second digit change).\n\nAnd there are 4096 places where the three first digit change, but 256 of \nthose were already counted, so you get 3840 for the third case (but the \ngit repo didn't have enough objects, so you missed one, and then the next \nones will hit a peak and then start an exponential decrease.\n\nSo with a nice random linear distribution (which we'd expect from a good \nhash), you should see an exponential increase to a maximum (which you'd \nexpect to be at \"floor(lnx(nr-objects))\", and then an exponential decrease \nright back.\n\nWith the kernel, with 439342 objects reachable from HEAD, the peak should \nbe around 4 (for a base-16 thing) and around 18 for the binary thing. \nWhich is exactly what you get..\n\n\t\tLinus\n\n--- for the kernel, using your nybble-counter ---\n0: 16\n1: 240\n2: 3840\n3: 61357\n4: 293375\n5: 74775\n6: 5372\n7: 350\n8: 16\n9: 1\n"},{"id":"38485","messageId":"86y7laitlz.fsf@blue.stonehenge.com","threadId":"7495","inReplyTo":"Pine.LNX.4.64.0704020938470.6730@woody.linux-foundation.org","subject":"Re: Distribution of longest common hash prefixes","fromName":"Randal L. Schwartz","fromEmail":"merlyn@stonehenge.com","sentAt":"2007-04-02T17:17:12Z","receivedAt":"2007-04-02T17:17:12Z","isPatch":false,"sender":{"key":"merlyn@stonehenge.com","avatar":"https://gravatar.com/avatar/dc528d210743ff0333e6213f9ee7b33b23f1b7bc1f3c5a8c2d819074ecd7ab19?d=mp&s=160"},"body":">>>>> \"Linus\" == Linus Torvalds writes:\n\nLinus> No yay yet.. That counts hex digits, not bits.\n\nI thought the goal was to figure out how long (on the average) you had to give\na SHA1 to be \"unique\".\n\nBut even that's wrong, because of the following:\n\nCAFEFEED357\nDEADBEEF123\nDEADBEEF456\nDEADBEEF467\nDEADBEEF478\n\nfor that sequence, I'd count 0, 8, 9, 9 when in fact, it should be 8, 9, 9, 9.\nIt's not the items in common with the previous value... it's the longer of the\nitems in common with the string on either side. The easiest way for that\nwould be to use a 3-item window:\n\ngit-rev-list --objects HEAD | sort | perl -lne '\n substr($_, 40) = \"\";\n if (defined $p) {\n ($p ^ $_) =~ /^(\\0*)/;\n $common = length $1;\n if (defined $pcommon) {\n $count[$pcommon > $common ? $pcommon : $common]++;\n }\n }\n $p = $_;\n $pcommon = $common;\n END { print \"$_: $count[$_]\" for 0..$#count }\n'\n\nthis also fixes the bug where I compare the first line to nothing.\nWith this, I get (on git.git):\n\n 0: \n 1: \n 2: 6\n 3: 21153\n 4: 15008\n 5: 1232\n 6: 90\n 7: \n 8: 2\n\nwhich now makes sense. There are 2 items that need 9 hex chars\nto be unique.\n\n-- \nRandal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095\n \nPerl/Unix/security consulting, Technical writing, Comedy, etc. etc.\nSee PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!\n"},{"id":"38486","messageId":"m3tzvylmoa.fsf@lugabout.jhcloos.org","threadId":"7495","inReplyTo":"86bqi6kae7.fsf@blue.stonehenge.com","subject":"Re: Distribution of longest common hash prefixes","fromName":"James Cloos","fromEmail":"cloos@jhcloos.com","sentAt":"2007-04-02T17:18:22Z","receivedAt":"2007-04-02T17:18:22Z","isPatch":false,"sender":{"key":"cloos@jhcloos.com","avatar":"https://gravatar.com/avatar/ec9a05787d29afe41e243e4b60bd0e2f69d757688e8f0bfe5e78bc185a3e317f?d=mp&s=160"},"body":">>>>> \"Randal\" == Randal L Schwartz writes:\n\nRandal> I don't have access to the linux-2.6 kernel\n\nAs of commit b6a8b31, I get this for the kernel tree from Randal's code:\n\n0: 16\n1: 240\n2: 3840\n3: 61357\n4: 293437\n5: 74792\n6: 5373\n7: 350\n8: 16\n9: 1\n\n(That is, of course, counting hex digits (aka nybbles), not bits as\nPeter's code does.)\n\n-JimC\n-- \nJames Cloos OpenPGP: 1024D/ED7DAEA6\n"},{"id":"38487","messageId":"86r6r2isva.fsf@blue.stonehenge.com","threadId":"7495","inReplyTo":"86y7laitlz.fsf@blue.stonehenge.com","subject":"Re: Distribution of longest common hash prefixes","fromName":"Randal L. Schwartz","fromEmail":"merlyn@stonehenge.com","sentAt":"2007-04-02T17:33:13Z","receivedAt":"2007-04-02T17:33:13Z","isPatch":false,"sender":{"key":"merlyn@stonehenge.com","avatar":"https://gravatar.com/avatar/dc528d210743ff0333e6213f9ee7b33b23f1b7bc1f3c5a8c2d819074ecd7ab19?d=mp&s=160"},"body":">>>>> \"Randal\" == Randal L Schwartz writes:\n\nRandal> git-rev-list --objects HEAD | sort | perl -lne '\nRandal> substr($_, 40) = \"\";\nRandal> if (defined $p) {\nRandal> ($p ^ $_) =~ /^(\\0*)/;\nRandal> $common = length $1;\nRandal> if (defined $pcommon) {\nRandal> $count[$pcommon > $common ? $pcommon : $common]++;\nRandal> }\nRandal> }\nRandal> $p = $_;\nRandal> $pcommon = $common;\nRandal> END { print \"$_: $count[$_]\" for 0..$#count }\nRandal> '\n\nAnd that's off by one on either end. :)\n\n git-rev-list --objects HEAD | sort | perl -lne '\n substr($_, 40) = \"\";\n if (defined $p) {\n ($p ^ $_) =~ /^(\\0*)/;\n $common = length $1;\n if (defined $pcommon) {\n $count[$pcommon > $common ? $pcommon : $common]++;\n } else {\n $count[$common]++; # first item\n }\n }\n $p = $_;\n $pcommon = $common;\n END {\n $count[$common]++; # last item\n print \"$_: $count[$_]\" for 0..$#count;\n }\n '\n\nWhich now yields:\n\n 0: \n 1: \n 2: 6\n 3: 21155\n 4: 15008\n 5: 1232\n 6: 90\n 7: \n 8: 2\n\nAnd *that* totals to 37493, which is the number of objects. Yeay.\n\n-- \nRandal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095\n \nPerl/Unix/security consulting, Technical writing, Comedy, etc. etc.\nSee PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!\n"},{"id":"38509","messageId":"m3r6r1jsmq.fsf@lugabout.jhcloos.org","threadId":"7495","inReplyTo":"86r6r2isva.fsf@blue.stonehenge.com","subject":"Re: Distribution of longest common hash prefixes","fromName":"James Cloos","fromEmail":"cloos@jhcloos.com","sentAt":"2007-04-03T17:04:54Z","receivedAt":"2007-04-03T17:04:54Z","isPatch":false,"sender":{"key":"cloos@jhcloos.com","avatar":"https://gravatar.com/avatar/ec9a05787d29afe41e243e4b60bd0e2f69d757688e8f0bfe5e78bc185a3e317f?d=mp&s=160"},"body":">>>>> \"Randal\" == Randal L Schwartz writes:\n\nRandal> git-rev-list --objects HEAD | sort | perl -lne '\nRandal> substr($_, 40) = \"\";\nRandal> if (defined $p) {\nRandal> ($p ^ $_) =~ /^(\\0*)/;\nRandal> $common = length $1;\nRandal> if (defined $pcommon) {\nRandal> $count[$pcommon > $common ? $pcommon : $common]++;\nRandal> } else {\nRandal> $count[$common]++; # first item\nRandal> }\nRandal> }\nRandal> $p = $_;\nRandal> $pcommon = $common;\nRandal> END {\nRandal> $count[$common]++; # last item\nRandal> print \"$_: $count[$_]\" for 0..$#count;\nRandal> }\nRandal> '\n\nWith that version the kernel gives:\n\n0: \n1: \n2: \n3: 565\n4: 288450\n5: 139080\n6: 10699\n7: 700\n8: 32\n9: 2\n\nAdding in $_ = unpack(\"B*\",pack(\"H*\",$_));\nto the script, to do the work on bits, gives:\n\n14: \n15: 565\n16: 14723\n17: 66765\n18: 107838\n19: 99124\n20: 67367\n21: 39238\n22: 21503\n23: 10972\n24: 5591\n25: 2927\n26: 1472\n27: 709\n28: 382\n29: 166\n30: 98\n31: 54\n32: 20\n33: 6\n34: 2\n35: 4\n36: \n37: 2\n\n-JimC\n-- \nJames Cloos OpenPGP: 1024D/ED7DAEA6\n"},{"id":"38510","messageId":"867istcrhr.fsf@blue.stonehenge.com","threadId":"7495","inReplyTo":"m3r6r1jsmq.fsf@lugabout.jhcloos.org","subject":"Re: Distribution of longest common hash prefixes","fromName":"Randal L. Schwartz","fromEmail":"merlyn@stonehenge.com","sentAt":"2007-04-03T17:11:44Z","receivedAt":"2007-04-03T17:11:44Z","isPatch":false,"sender":{"key":"merlyn@stonehenge.com","avatar":"https://gravatar.com/avatar/dc528d210743ff0333e6213f9ee7b33b23f1b7bc1f3c5a8c2d819074ecd7ab19?d=mp&s=160"},"body":">>>>> \"James\" == James Cloos writes:\n\nJames> With that version the kernel gives:\n\nJames> 0: \nJames> 1: \nJames> 2: \nJames> 3: 565\nJames> 4: 288450\nJames> 5: 139080\nJames> 6: 10699\nJames> 7: 700\nJames> 8: 32\nJames> 9: 2\n\nFascinating. So you can spell out *any* commit in linux-2.6.git with\n10 hex chars. What do we need 40 for, again? :)\n\n-- \nRandal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095\n \nPerl/Unix/security consulting, Technical writing, Comedy, etc. etc.\nSee PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!\n"},{"id":"38511","messageId":"20070403172123.GD27706@spearce.org","threadId":"7495","inReplyTo":"867istcrhr.fsf@blue.stonehenge.com","subject":"Re: Distribution of longest common hash prefixes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-03T17:21:23Z","receivedAt":"2007-04-03T17:21:23Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"Randal L. Schwartz\" wrote:\n> >>>>> \"James\" == James Cloos writes:\n> \n> James> With that version the kernel gives:\n> \n> James> 0: \n> James> 1: \n> James> 2: \n> James> 3: 565\n> James> 4: 288450\n> James> 5: 139080\n> James> 6: 10699\n> James> 7: 700\n> James> 8: 32\n> James> 9: 2\n> \n> Fascinating. So you can spell out *any* commit in linux-2.6.git with\n> 10 hex chars. What do we need 40 for, again? :)\n\nWell, the other thing is those 2 commits at 9 bytes probably were\nnot that way a year ago. One of those might have only needed 8,\nand the other is newer, so now you need 9.\n\nWhat the above tells me is that 8 is almost a safe default for our\nabbreviations, but isn't safe enough, as there are collisions past 8.\n\n-- \nShawn.\n"},{"id":"38513","messageId":"Pine.LNX.4.64.0704031046150.6730@woody.linux-foundation.org","threadId":"7495","inReplyTo":"20070403172123.GD27706@spearce.org","subject":"Re: Distribution of longest common hash prefixes","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-03T17:50:34Z","receivedAt":"2007-04-03T17:50:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 Apr 2007, Shawn O. Pearce wrote:\n> \n> Well, the other thing is those 2 commits at 9 bytes probably were\n> not that way a year ago. One of those might have only needed 8,\n> and the other is newer, so now you need 9.\n\nWell, neither of the the two objects at 9 bytes may not be (and probably \naren't) commits and of the 32 8-nibble cases who knows how many are \nactually commits (probably none), so an 8-byte SHA1 is *probably* unique \nat least if you just look at commits.\n\nRemove the \"--objects\" to find out.\n\n> What the above tells me is that 8 is almost a safe default for our\n> abbreviations, but isn't safe enough, as there are collisions past 8.\n\nYeah, the short SHA1 form is obviously always going to be risky. But in \npractice, since people almost always use it just for commits, it's \nprobably good enough in practice, and even if you get a collision in 8 \nnibbles, most of the time it will probably be trivial to figure out which \none was meant, so it's not like it's a disaster if somebody ends up \nreporting a bug with a non-unique abbreviation.\n\n\t\tLinus\n"},{"id":"38514","messageId":"7vhcrxz5a8.fsf@assigned-by-dhcp.cox.net","threadId":"7495","inReplyTo":"Pine.LNX.4.64.0704031046150.6730@woody.linux-foundation.org","subject":"Re: Distribution of longest common hash prefixes","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-03T18:22:55Z","receivedAt":"2007-04-03T18:22:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Yeah, the short SHA1 form is obviously always going to be risky. But in \n> practice, since people almost always use it just for commits, it's \n> probably good enough in practice, and even if you get a collision in 8 \n> nibbles, most of the time it will probably be trivial to figure out which \n> one was meant, so it's not like it's a disaster if somebody ends up \n> reporting a bug with a non-unique abbreviation.\n\nAre you hinting to update sha1_name.c::get_sha1() so that we do\nnot accept abbreviated non-commit object names?\n"},{"id":"38520","messageId":"Pine.LNX.4.64.0704031219430.6730@woody.linux-foundation.org","threadId":"7495","inReplyTo":"7vhcrxz5a8.fsf@assigned-by-dhcp.cox.net","subject":"Re: Distribution of longest common hash prefixes","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-03T19:27:02Z","receivedAt":"2007-04-03T19:27:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 Apr 2007, Junio C Hamano wrote:\n> \n> Are you hinting to update sha1_name.c::get_sha1() so that we do\n> not accept abbreviated non-commit object names?\n\nNo, but it might be nice if we had some fairly graceful way of handling \nabbreviated SHA1's that ended up being ambiguous (maybe they weren't \nambiguous in the original context, but became ambiguous later).\n\nSome way of just listing the alternatives, and sorting - and showing - by \ntype (so that if you know it's supposed to be a commit, you can trivially \npick it out from other objects that happen to collide in the first \ndigits).\n\nRight now we can do it with\n\n\tgit-rev-list --objects --all | grep '^'\n\nbut that's actually not even correct (maybe the reason sha1_name decided \nit was ambiguous was due to an _unreachable_ SHA1?), and it's also very \ninefficient.\n\nWe could have some helper that just looked things up (it's easy enough to \nlook up all potential SHA1 matches both in the filesystem and in a \npack-file - no need for any rev-list thing that lists all objects).\n\nIs this a pressing concern? Absolutely not. I don't think we've ever had \nany real problems with this, and you *can* do it by hand with a bit of \ninefficient scripting right now..\n\n\t\t\tLinus\n"},{"id":"38521","messageId":"alpine.LFD.0.98.0704031529300.28181@xanadu.home","threadId":"7495","inReplyTo":"7vhcrxz5a8.fsf@assigned-by-dhcp.cox.net","subject":"Re: Distribution of longest common hash prefixes","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-03T19:34:02Z","receivedAt":"2007-04-03T19:34:02Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 Apr 2007, Junio C Hamano wrote:\n\n> Linus Torvalds writes:\n> \n> > Yeah, the short SHA1 form is obviously always going to be risky. But in \n> > practice, since people almost always use it just for commits, it's \n> > probably good enough in practice, and even if you get a collision in 8 \n> > nibbles, most of the time it will probably be trivial to figure out which \n> > one was meant, so it's not like it's a disaster if somebody ends up \n> > reporting a bug with a non-unique abbreviation.\n> \n> Are you hinting to update sha1_name.c::get_sha1() so that we do\n> not accept abbreviated non-commit object names?\n\nNO, I hope not.\n\nInstead (and if the concern is real) we should error out when the \nabbreviated name is ambigous and impose no restriction otherwise.\n\n\nNicolas\n"},{"id":"38532","messageId":"7vhcrxw6h5.fsf@assigned-by-dhcp.cox.net","threadId":"7495","inReplyTo":"alpine.LFD.0.98.0704031529300.28181@xanadu.home","subject":"Re: Distribution of longest common hash prefixes","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-03T20:25:26Z","receivedAt":"2007-04-03T20:25:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Tue, 3 Apr 2007, Junio C Hamano wrote:\n>\n>> Linus Torvalds writes:\n>> \n>> > Yeah, the short SHA1 form is obviously always going to be risky. But in \n>> > practice, since people almost always use it just for commits, it's \n>> > probably good enough in practice, and even if you get a collision in 8 \n>> > nibbles, most of the time it will probably be trivial to figure out which \n>> > one was meant, so it's not like it's a disaster if somebody ends up \n>> > reporting a bug with a non-unique abbreviation.\n>> \n>> Are you hinting to update sha1_name.c::get_sha1() so that we do\n>> not accept abbreviated non-commit object names?\n>\n> NO, I hope not.\n>\n> Instead (and if the concern is real) we should error out when the \n> abbreviated name is ambigous and impose no restriction otherwise.\n\nI stated it wrongly. What I was getting at was that we might\nwant to consider an abbreviation that matches only a single\ncommit unambiguous even when there are ambiguous objects of\nother kinds.\n\nNot that I consider it a pressing issue, though.\n"},{"id":"38535","messageId":"alpine.LFD.0.98.0704031635100.28181@xanadu.home","threadId":"7495","inReplyTo":"7vhcrxw6h5.fsf@assigned-by-dhcp.cox.net","subject":"Re: Distribution of longest common hash prefixes","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-03T20:39:02Z","receivedAt":"2007-04-03T20:39:02Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 Apr 2007, Junio C Hamano wrote:\n\n> I stated it wrongly. What I was getting at was that we might\n> want to consider an abbreviation that matches only a single\n> commit unambiguous even when there are ambiguous objects of\n> other kinds.\n\nMaybe. But by the time your object hash distribution starts showing \nambiguous objects with a given abbreviated name between a commit and a \nnon commit, I'll bet you'll start to see ambiguities between commits \nsoon enough as well.\n\n> Not that I consider it a pressing issue, though.\n\nIndeed. And even then it is not something really hard to implement \neither.\n\n\nNicolas\n"},{"id":"38571","messageId":"20070403230846.GB8479@dspnet.fr.eu.org","threadId":"7495","inReplyTo":"alpine.LFD.0.98.0704031635100.28181@xanadu.home","subject":"Re: Distribution of longest common hash prefixes","fromName":"Olivier Galibert","fromEmail":"galibert@pobox.com","sentAt":"2007-04-03T23:08:46Z","receivedAt":"2007-04-03T23:08:46Z","isPatch":false,"sender":{"key":"galibert@pobox.com","avatar":null},"body":"On Tue, Apr 03, 2007 at 04:39:02PM -0400, Nicolas Pitre wrote:\n> On Tue, 3 Apr 2007, Junio C Hamano wrote:\n> \n> > I stated it wrongly. What I was getting at was that we might\n> > want to consider an abbreviation that matches only a single\n> > commit unambiguous even when there are ambiguous objects of\n> > other kinds.\n> \n> Maybe. But by the time your object hash distribution starts showing \n> ambiguous objects with a given abbreviated name between a commit and a \n> non commit, I'll bet you'll start to see ambiguities between commits \n> soon enough as well.\n\nIsn't the number of objects an order of magnitude bigger than the\nnumber of commits? Well, I guess that depends on your workflow...\n\n OG.\n"},{"id":"38573","messageId":"Pine.LNX.4.64.0704031613210.6730@woody.linux-foundation.org","threadId":"7495","inReplyTo":"20070403230846.GB8479@dspnet.fr.eu.org","subject":"Re: Distribution of longest common hash prefixes","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-03T23:22:41Z","receivedAt":"2007-04-03T23:22:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 4 Apr 2007, Olivier Galibert wrote:\n> \n> Isn't the number of objects an order of magnitude bigger than the\n> number of commits? Well, I guess that depends on your workflow...\n\nJudging by the kernel tree, it's not an order of magnitude, although it's \nfairly close:\n\n\t[torvalds@woody linux]$ git rev-list --all | wc -l\n\t51156\n\n\t[torvalds@woody linux]$ git rev-list --all --objects | wc -l\n\t444265\n\nSo you have about 50k commit objects, and about 390k \"other\" objects. \nAbout 7.7 \"other\" objects per commit. Not quite an order-of-magnitude, but \nclose.\n\nPart of the reason for this is that the kernel people tend to encourage \nlots of smaller commits over single large commits, so we have lots of \ncommits.\n\nTo counter-act that somewhat, the kernel tree is also pretty deep, so a \nlot of the \"other\" objects are actually the tree objects that create the \ndirectory structure - it's quite normal to have a single file (blob) \nchange, and then three new trees that lead up to that file, and the one \ncommit that explains it.\n\nOther projects - like git itself - have relatively fewer tree objects, \nwhich is probably why the ratio for git itself is just 3.04 \"other\" \nobjects for each commit (ie on average, commits probably touch two blobs \nand the top-level tree - about 10 commits, and 30k non-commit objects).\n\nSo repo layout matters. Iirc, last I did the statistics, the git \nrepository had more blobs than trees, while the kernel repo had more trees \nthan blobs. And the commits-to-other-objects is obviously fairly different \nas a result (I think both git and the kernel have the \"many small changes\" \napproach, so they're similar in that respect).\n\nOther repositories probably have more \"big changes\". Especially if you \ncreate the repo initially by importing just big releases over time, you'll \nhave relatively few commits, and lots of blob/tree changes. \n\n\t\t\tLinus\n"},{"id":"38655","messageId":"m3bqi3ons2.fsf@lugabout.jhcloos.org","threadId":"7495","inReplyTo":"Pine.LNX.4.64.0704031046150.6730@woody.linux-foundation.org","subject":"Re: Distribution of longest common hash prefixes","fromName":"James Cloos","fromEmail":"cloos@jhcloos.com","sentAt":"2007-04-04T21:03:02Z","receivedAt":"2007-04-04T21:03:02Z","isPatch":false,"sender":{"key":"cloos@jhcloos.com","avatar":"https://gravatar.com/avatar/ec9a05787d29afe41e243e4b60bd0e2f69d757688e8f0bfe5e78bc185a3e317f?d=mp&s=160"},"body":">>>>> \"Linus\" == Linus Torvalds writes:\n\nLinus> Well, neither of the the two objects at 9 bytes may not be (and\nLinus> probably aren't) commits and of the 32 8-nibble cases who knows\nLinus> how many are actually commits (probably none), so an 8-byte SHA1\nLinus> is *probably* unique at least if you just look at commits.\n\nLinus> Remove the \"--objects\" to find out.\n\nThat makes for:\n\n0: \n1: \n2: 1\n3: 23320\n4: 25431\n5: 2259\n6: 134\n7: 8\n\nBut is the kernel large enough to be sufficiently representative?\n\nDid Jon complete an import of the 'zilla src? \n\nHas anyone tried to import OOo?\n\n-JimC\n-- \nJames Cloos OpenPGP: 1024D/ED7DAEA6\n"}]}