{"thread":{"id":"48116","subject":"The most efficient way to test if repositories share the same objects","startedAt":"2018-03-22T16:48:31Z","lastAt":"2018-03-23T14:36:15Z","messageCount":8,"participants":["Konstantin Ryabitsev","Ævar Arnfjörð Bjarmason","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"342508","messageId":"14d0937f-0e39-7af7-a395-3046ec5d5c16@linuxfoundation.org","threadId":"48116","inReplyTo":null,"subject":"The most efficient way to test if repositories share the same objects","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2018-03-22T16:48:15Z","receivedAt":"2018-03-22T16:48:31Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"Hi, all:\n\nWhat is the most efficient way to test if repoA and repoB share common\ncommits? My goal is to automatically figure out if repoB can benefit\nfrom setting alternates to repoA and repacking. I currently do it by\ncomparing the output of \"show-ref --tags -s\", but that does not work for\nrepos without tags.\n\nBest,\n-- \nKonstantin Ryabitsev\n\n"},{"id":"342537","messageId":"87o9jfyl0y.fsf@evledraar.gmail.com","threadId":"48116","inReplyTo":"14d0937f-0e39-7af7-a395-3046ec5d5c16@linuxfoundation.org","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-03-22T19:20:45Z","receivedAt":"2018-03-22T19:20:54Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Mar 22 2018, Konstantin Ryabitsev wrote:\n\n> What is the most efficient way to test if repoA and repoB share common\n> commits? My goal is to automatically figure out if repoB can benefit\n> from setting alternates to repoA and repacking. I currently do it by\n> comparing the output of \"show-ref --tags -s\", but that does not work for\n> repos without tags.\n\nIf you're using show-ref already to get the tag tips, you can use\nfor-each-ref to get all tips.\n\nBut of course that'll just give you the tips. You could then use `git\ncat-file --batch-check` on both ends to see what commits from the other\nthey report knowing about, in case they have branches that are\nahead/behind the other.\n"},{"id":"342539","messageId":"xmqqlgejlx8e.fsf@gitster-ct.c.googlers.com","threadId":"48116","inReplyTo":"87o9jfyl0y.fsf@evledraar.gmail.com","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-22T19:35:29Z","receivedAt":"2018-03-22T19:35:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> But of course that'll just give you the tips. You could then use `git\n> cat-file --batch-check` on both ends to see what commits from the other\n> they report knowing about, in case they have branches that are\n> ahead/behind the other.\n\nI am not sure how you are envisioning to use \"cat-file\n--batch-check\" here.  Do you mean to take \"rev-list --all\" output\nfrom both and compare, or something?\n\nI am not sure how Konstantin defines \"the most efficient\", but if it\nis \"with the smallest number of bits exchanged between the\nrepositories\", then the answer would probably be to find the root\ncommit(s) in each repository and if they share any common root(s).\nIf there isn't then there is no hope to share objects between them,\nof course.\n"},{"id":"342540","messageId":"87muyzyjhm.fsf@evledraar.gmail.com","threadId":"48116","inReplyTo":"xmqqlgejlx8e.fsf@gitster-ct.c.googlers.com","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-03-22T19:53:57Z","receivedAt":"2018-03-22T19:54:05Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Mar 22 2018, Junio C. Hamano wrote:\n\n> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n>\n>> But of course that'll just give you the tips. You could then use `git\n>> cat-file --batch-check` on both ends to see what commits from the other\n>> they report knowing about, in case they have branches that are\n>> ahead/behind the other.\n>\n> I am not sure how you are envisioning to use \"cat-file\n> --batch-check\" here.  Do you mean to take \"rev-list --all\" output\n> from both and compare, or something?\n\nBy doing something like this:\n\n    (\n        cd /tmp &&\n        git clone http://github.com/gitster/git gitster-git;\n        git clone http://github.com/avar/git avar-git;\n        git -C gitster-git for-each-ref --format=\"%(object)\" | git -C avar-git cat-file --batch-check|grep -E -o '(commit|missing)'|sort|uniq -c &&\n        git -C avar-git for-each-ref --format=\"%(object)\" | git -C gitster-git cat-file --batch-check|grep -E -o '(commit|missing)'|sort|uniq -c\n    )\n\nWhich outputs:\n\n    673 commit\n    696 missing\n    374 commit\n    495 missing\n\nWhich of course, as noted, isn't going to be a good general solution in\nall cases, but it's blindingly fast, and since the original question is\nessentially that he's starting out with doing a rough equivalent of\nthat, but for tags only, maybe it'll work for his use-case.\n\n> I am not sure how Konstantin defines \"the most efficient\", but if it\n> is \"with the smallest number of bits exchanged between the\n> repositories\", then the answer would probably be to find the root\n> commit(s) in each repository and if they share any common root(s).\n> If there isn't then there is no hope to share objects between them,\n> of course.\n\nYes, that would probably be much better:\n\n    diff -ru <(git -C avar-git log --oneline --pretty=format:%H --max-parents=0) \\\n             <(git -C gitster-git log --oneline --pretty=format:%H --max-parents=0) &&\n    do_stuff_because_they_have_stuff_in_common\n"},{"id":"342544","messageId":"906555df-e906-775a-0255-fbc71f7138f6@linuxfoundation.org","threadId":"48116","inReplyTo":"xmqqlgejlx8e.fsf@gitster-ct.c.googlers.com","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2018-03-22T21:32:40Z","receivedAt":"2018-03-22T21:32:50Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"On 03/22/18 15:35, Junio C Hamano wrote:\n> I am not sure how Konstantin defines \"the most efficient\", but if it\n> is \"with the smallest number of bits exchanged between the\n> repositories\", then the answer would probably be to find the root\n> commit(s) in each repository and if they share any common root(s).\n> If there isn't then there is no hope to share objects between them,\n> of course.\n\nHmm... so, this a cool idea that I'd like to use, but there are two\nannoying gotchas:\n\n1. I cannot assume that refs/heads/master is meaningful -- my problem is\nactually with something like\nhttps://source.codeaurora.org/quic/la/kernel/msm-3.18 -- you will find\nthat master is actually unborn and there are 7700 other heads (don't get\nme started on that unless you're buying me a lot of drinks).\n\n2. Even if there is a HEAD I know I can use, it's pretty slow on large\nrepos (e.g. linux.git):\n\n$ time git rev-list --max-parents=0 HEAD\na101ad945113be3d7f283a181810d76897f0a0d6\ncd26f1bd6bf3c73cc5afe848677b430ab342a909\nbe0e5c097fc206b863ce9fe6b3cfd6974b0110f4\n1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n\nreal    0m6.311s\nuser    0m6.153s\nsys     0m0.110s\n\nIf I try to do this for each of the 7700 heads, this will take roughly\n12 hours.\n\nMy current strategy has been pretty much:\n\ngit -C msm-3.10.git show-ref --tags -s | sort -u > /tmp/refs1\ngit -C msm-3.18.git show-ref --tags -s | sort -u > /tmp/refs2\n\nand then checking if an intersection of these matches at least half of\nrefs in either repo:\n\n----\n#/usr/bin/env python\nimport numpy\n\nrefs1 = numpy.array(open('/tmp/refs1').readlines())\nrefs2 = numpy.array(open('/tmp/refs2').readlines())\n\nin_common = len(numpy.intersect1d(refs1, refs2))\nif in_common > len(refs1)/2 or in_common > len(refs2)/2:\n    print('Lots of shared refs')\nelse:\n    print('None or too few shared refs')\n----\n\nThis works well enough at least for those repos with lots of shared\ntags, but will miss potentially large repos where there's only heads\nthat can be pointing at commits that aren't necessarily the same between\ntwo repos.\n\nThanks for your help!\n\nBest,\n-- \nKonstantin Ryabitsev\nDirector, IT Infrastructure Security\nThe Linux Foundation\n\n"},{"id":"342545","messageId":"xmqqa7uzlr8x.fsf@gitster-ct.c.googlers.com","threadId":"48116","inReplyTo":"906555df-e906-775a-0255-fbc71f7138f6@linuxfoundation.org","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-22T21:44:46Z","receivedAt":"2018-03-22T21:44:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Konstantin Ryabitsev <konstantin@linuxfoundation.org> writes:\n\n> $ time git rev-list --max-parents=0 HEAD\n> a101ad945113be3d7f283a181810d76897f0a0d6\n> cd26f1bd6bf3c73cc5afe848677b430ab342a909\n> be0e5c097fc206b863ce9fe6b3cfd6974b0110f4\n> 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n>\n> real    0m6.311s\n> user    0m6.153s\n> sys     0m0.110s\n>\n> If I try to do this for each of the 7700 heads, this will take roughly\n> 12 hours.\n\nWouldn't it be more efficient to avoid doing so one-by-one?  \nThat is, wouldn't\n\n\trev-list --max-parents=0 --all\n\nbe a bit faster than\n\n\tfor-each-ref |\n\twhile read object type refname\n\tdo\n\t\trev-list --max-parents=0 $refname\n\tdone\n\nI wonder?\n"},{"id":"342575","messageId":"179c3cf0-72bd-559a-1e00-b18ce97e8136@linuxfoundation.org","threadId":"48116","inReplyTo":"xmqqa7uzlr8x.fsf@gitster-ct.c.googlers.com","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2018-03-23T13:57:18Z","receivedAt":"2018-03-23T13:57:27Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"On 03/22/18 17:44, Junio C Hamano wrote:\n> Wouldn't it be more efficient to avoid doing so one-by-one?  \n> That is, wouldn't\n> \n> \trev-list --max-parents=0 --all\n> \n> be a bit faster than\n> \n> \tfor-each-ref |\n> \twhile read object type refname\n> \tdo\n> \t\trev-list --max-parents=0 $refname\n> \tdone\n> \n> I wonder?\n\nYeah, you're right -- I forgot that we can pass --all. The check takes\n30 seconds, which is a lot better than 12 hours. :) It's a bit heavy\nstill, but msm kernel repos are one of the heaviest outliers, so let me\ntry to run with this.\n\nThanks for the suggestion!\n\nBest,\n-- \nKonstantin Ryabitsev\nDirector, IT Infrastructure Security\nThe Linux Foundation\n\n"},{"id":"342582","messageId":"87lgeiyi3t.fsf@evledraar.gmail.com","threadId":"48116","inReplyTo":"179c3cf0-72bd-559a-1e00-b18ce97e8136@linuxfoundation.org","subject":"Re: The most efficient way to test if repositories share the same objects","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-03-23T14:36:06Z","receivedAt":"2018-03-23T14:36:15Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Mar 23 2018, Konstantin Ryabitsev wrote:\n\n> On 03/22/18 17:44, Junio C Hamano wrote:\n>> Wouldn't it be more efficient to avoid doing so one-by-one?\n>> That is, wouldn't\n>>\n>> \trev-list --max-parents=0 --all\n>>\n>> be a bit faster than\n>>\n>> \tfor-each-ref |\n>> \twhile read object type refname\n>> \tdo\n>> \t\trev-list --max-parents=0 $refname\n>> \tdone\n>>\n>> I wonder?\n>\n> Yeah, you're right -- I forgot that we can pass --all. The check takes\n> 30 seconds, which is a lot better than 12 hours. :) It's a bit heavy\n> still, but msm kernel repos are one of the heaviest outliers, so let me\n> try to run with this.\n>\n> Thanks for the suggestion!\n\nUnless you have just one CPU core your script would probably benefit\nfrom being wrapped in GNU parallel. I.e.:\n\n    parallel 'stuff-to-do {}' ::: $(list-of-repos)\n\nOr something similar.\n"}]}