{"thread":{"id":"25622","subject":"bug in git notes fanout","startedAt":"2010-11-02T22:06:56Z","lastAt":"2010-11-02T23:36:28Z","messageCount":2,"participants":["Shawn Pearce","Johan Herland"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"155007","messageId":"AANLkTi=JfwJq8wq_1an014WO+A_Dwp5cDKa+xHi10awr@mail.gmail.com","threadId":"25622","inReplyTo":null,"subject":"bug in git notes fanout","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2010-11-02T22:06:56Z","receivedAt":"2010-11-02T22:06:56Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Why doesn't the fan-out work for this case?\n\n  git notes --ref buggy.fanout add -m test HEAD\n  perl -e 'for($i=0;$i<1024;$i++){printf \"%s %s%4.4x\\n\", $ARGV[0],\n\"0\"x36, $i}' $(git rev-parse HEAD) | git notes --ref buggy.fanout copy\n--stdin\n  git ls-tree refs/notes/buggy.fanout\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t0000000000000000000000000000000000000000\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t0000000000000000000000000000000000000001\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t0000000000000000000000000000000000000002\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t0000000000000000000000000000000000000003\n...\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t000000000000000000000000000000000000018c\n...\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t00000000000000000000000000000000000003e1\n...\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t00000000000000000000000000000000000003e2\n...\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t00000000000000000000000000000000000003fd\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t00000000000000000000000000000000000003fe\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t00000000000000000000000000000000000003ff\n100644 blob 9daeafb9864cf43055ae93beb0afd6c7d144bfa4\t638d3d9244720e0f07f22a953d25db878e9ad3f5\n\n\nI thought the entire points of the notes fanout being 0/40, 2/38,\n2/2/36, 2/2/2/34 was to prevent git from having a big linear search\nwithin any single tree when a large number of notes are added to a\nnote branch.\n\nIIRC when the notes stuff was being debated on this list we insisted\nthat the fan-out algorithm had to be consistent, ensuring that if I\ncreate a note for 638d3d92 and Junio creates a note on the same\nobject, they will wind up at the same path in the notes, and we won't\nhave doppleganger notes (two different notes in the same tree with the\nsame object).\n\nBasically this issue arises because we are adding node support to\nJGit.  Our planned implementation would have inserted\n00000000000000000000000000000000000003ff into\n00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/03/ff because\nthere are so many notes that at each depth we wind up with >255\nentries, and split the tree again.  But that results in a very\ndifferent structure from what the C implementation is doing today.\n\nAs far as I can tell from the C code, it won't split unless every hex\ndigit in the 0..f range is used.  That is just a weird heuristic, and\nactual paths used depend on the actual SHA-1s that we add to the tree.\n If I get \"unlucky\" and add 5 commits that start with \"f\" and never\nadd one that starts with \"0\", I won't get fan-out, even though my\nnotes tree has more than 256 items in it.\n\n*sigh*\n\nThis is almost as bad as the \"lets sort names in trees by name *and* type!\".\n\n-- \nShawn.\n"},{"id":"155012","messageId":"201011030036.28318.johan@herland.net","threadId":"25622","inReplyTo":"AANLkTi=JfwJq8wq_1an014WO+A_Dwp5cDKa+xHi10awr@mail.gmail.com","subject":"Re: bug in git notes fanout","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-11-02T23:36:28Z","receivedAt":"2010-11-02T23:36:28Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Tuesday 02 November 2010, Shawn Pearce wrote:\n> Why doesn't the fan-out work for this case?\n> \n>   git notes --ref buggy.fanout add -m test HEAD\n>   perl -e 'for($i=0;$i<1024;$i++){printf \"%s %s%4.4x\\n\", $ARGV[0],\n> \"0\"x36, $i}' $(git rev-parse HEAD) | git notes --ref buggy.fanout copy\n> --stdin\n>   git ls-tree refs/notes/buggy.fanout\n> 100644 blob ...\t0000000000000000000000000000000000000000\n> 100644 blob ...\t0000000000000000000000000000000000000001\n> 100644 blob ...\t0000000000000000000000000000000000000002\n> 100644 blob ...\t0000000000000000000000000000000000000003\n> ...\n> 100644 blob ...\t000000000000000000000000000000000000018c\n> ...\n> 100644 blob ...\t00000000000000000000000000000000000003e1\n> ...\n> 100644 blob ...\t00000000000000000000000000000000000003e2\n> ...\n> 100644 blob ...\t00000000000000000000000000000000000003fd\n> 100644 blob ...\t00000000000000000000000000000000000003fe\n> 100644 blob ...\t00000000000000000000000000000000000003ff\n> 100644 blob ...\t638d3d9244720e0f07f22a953d25db878e9ad3f5\n\nYes, for your extremely far-fetched testcase, the current implementation is \npessimal. However, please, consider exactly _what_ the notes tree contains. \nYes, that's right: SHA1 sums. Now, try to come up with a real-world scenario \nwhere your notes tree would end up looking like the above.\n\nI guess the same \"problem\" exists with the 2/38 fanout that is done for \nloose objects in .git/objects/. If you happen to only add objects whose SHA1 \nstart with 00..., you will get worst case behaviour there as well. Again, if \nyou can construct a real-world testcase for this, I am probably not the only \none interested in looking at it...\n\n> I thought the entire points of the notes fanout being 0/40, 2/38,\n> 2/2/36, 2/2/2/34 was to prevent git from having a big linear search\n> within any single tree when a large number of notes are added to a\n> note branch.\n\nYes, and by assuming that SHA1 gives a fairly uniform distribution of keys \n(a pretty safe assumption if the rest of Git's design is anything to go by), \nwe can conclude that the large number of keys would be fairly evenly spread \nout across the notes tree.\n\n> IIRC when the notes stuff was being debated on this list we insisted\n> that the fan-out algorithm had to be consistent, ensuring that if I\n> create a note for 638d3d92 and Junio creates a note on the same\n> object, they will wind up at the same path in the notes, and we won't\n> have doppleganger notes (two different notes in the same tree with the\n> same object).\n\nLet's separate the cases here:\n\nA. There is absolutely no guarantee that two different notes trees will \nplace a note for 638d3d92 at the same location/path. I.e. if you add a note \nto your notes tree, and Junio adds one to his, they might end up at \ndifferent paths. This depends on how many, and which other notes are in your \nrespective notes trees.\n\nB. When combining/merging those notes tree, the notes code _does_ guarantee \nthat there won't be doppelganger notes. I.e. if you're both working in the \nsame notes tree (in the same repo), the notes code will not allow you to add \ntwo notes to 638d3d92 at different locations in the notes tree.\n\nOf course you might artificially construct a notes tree that contains \ndoppelganger notes, and the current implementation will successfully read \nthat notes tree (combining the doppelganger notes using the configured \ncombine_notes function), but - crucially - the notes code will _never_ \ngenerate a notes tree with doppelganger notes.\n\n> Basically this issue arises because we are adding node support to\n> JGit.  Our planned implementation would have inserted\n> 00000000000000000000000000000000000003ff into\n> 00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/03/ff because\n> there are so many notes that at each depth we wind up with >255\n> entries, and split the tree again.  But that results in a very\n> different structure from what the C implementation is doing today.\n> \n> As far as I can tell from the C code, it won't split unless every hex\n> digit in the 0..f range is used.  That is just a weird heuristic, and\n> actual paths used depend on the actual SHA-1s that we add to the tree.\n\nRead that sentence again. As explained above, since SHA1 provides a near-\nuniform distribution, looking at hex digits in the 0..f range is a very \ninexpensive and moderately good heuristic to estimating whether it's time to \nmake a split.\n\nGranted, there might be better heuristics, and the current design allows us \nto implement such heuristics without making pre-existing notes trees \ninvalid.\n\n>  If I get \"unlucky\" and add 5 commits that start with \"f\" and never\n> add one that starts with \"0\", I won't get fan-out, even though my\n> notes tree has more than 256 items in it.\n\nTrue, however, the uniform distribution of SHA1 pretty much guarantees that \nas you keep adding notes, you're going to get one that starts with \"0\", and \nthen you'll get the needed split.\n\n\nHope this helps,\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"}]}