{"thread":{"id":"36407","subject":"Get all tips quickly","startedAt":"2014-04-13T14:19:47Z","lastAt":"2014-04-14T14:20:30Z","messageCount":4,"participants":["Kirill Likhodedov","Ævar Arnfjörð Bjarmason","Michael Haggerty"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"238809","messageId":"4A7A3A96-DC10-4748-BBCC-F52F48977022@jetbrains.com","threadId":"36407","inReplyTo":null,"subject":"Get all tips quickly","fromName":"Kirill Likhodedov","fromEmail":"kirill.likhodedov@jetbrains.com","sentAt":"2014-04-13T14:19:47Z","receivedAt":"2014-04-13T14:19:47Z","isPatch":false,"sender":{"key":"kirill.likhodedov@jetbrains.com","avatar":"https://gravatar.com/avatar/9fd55d2a110e8e96deb3ed7b503d7f3b9b5b1ed5ca9ef6683c15525b11b94e63?d=mp&s=160"},"body":"Hi, \n\nWhat is fastest possible way to get all “tips” (leafs of the Git log graph) in a Git repository with hashes of commits they point to?\n\nWe at JetBrains are tuning performance of Git log integration in our IntelliJ IDEA and want to get all tips as fast as possible. \nCurrently we use 'git log —branches --tags --remotes --no-walk’, but the problem is that it is slow if there are a lot of references. In our repository we have about 35K tags, and therefore the tags is the main slowdown. On the other hand, we have just a couple of dozens of tips as well as branch references, and `git log --branches --remotes` is very fast.\n\nSo we are searching a way to get tags pointing to the graph leafs faster. \n\nWe also tried to read tags by manually parsing .git files (it is faster than invoking git log), but unfortunately annotated tags in .git/refs/tags/ are written without the hashes they point to (unlike .git/packed-refs).\n\nAnd that’s a pity that `git tag` doesn’t show the hashes.\n\nThanks a lot for any help!\n\n-----\nKirill Likhodedov\nJetBrains\nhttp://www.jetbrains.com\n\"Develop with pleasure!\"\n"},{"id":"238810","messageId":"CACBZZX7C+TyDy0=DhnYp81hR8aNoa0Na2sBOYOxk6jF=hh_fVg@mail.gmail.com","threadId":"36407","inReplyTo":"4A7A3A96-DC10-4748-BBCC-F52F48977022@jetbrains.com","subject":"Re: Get all tips quickly","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2014-04-13T18:29:25Z","receivedAt":"2014-04-13T18:29:25Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Sun, Apr 13, 2014 at 4:19 PM, Kirill Likhodedov\n<kirill.likhodedov@jetbrains.com> wrote:\n> Hi,\n>\n> What is fastest possible way to get all “tips” (leafs of the Git log graph) in a Git repository with hashes of commits they point to?\n\nTried \"git for-each-ref\" and the various options it has?\n\nDoing this for 35k tags is still going to be non-trivial.\n"},{"id":"238811","messageId":"534AE379.7000705@alum.mit.edu","threadId":"36407","inReplyTo":"4A7A3A96-DC10-4748-BBCC-F52F48977022@jetbrains.com","subject":"Re: Get all tips quickly","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-04-13T19:20:25Z","receivedAt":"2014-04-13T19:20:25Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/13/2014 04:19 PM, Kirill Likhodedov wrote:\n> What is fastest possible way to get all “tips” (leafs of the Git log\n> graph) in a Git repository with hashes of commits they point to?\n> \n> We at JetBrains are tuning performance of Git log integration in our\n> IntelliJ IDEA and want to get all tips as fast as possible. Currently\n> we use 'git log —branches --tags --remotes --no-walk’, but the\n> problem is that it is slow if there are a lot of references. In our\n> repository we have about 35K tags, and therefore the tags is the main\n> slowdown. On the other hand, we have just a couple of dozens of tips\n> as well as branch references, and `git log --branches --remotes` is\n> very fast.\n> \n> So we are searching a way to get tags pointing to the graph leafs\n> faster.\n\nThe fastest ways to get all references plus the commits that are pointed\nat by annotated references would probably be `git show-ref -d`.  The\nfunny-looking entries like \"refs/tags/v1.7.0^{}\" are the annotated tags\npeeled to the object that they ultimately refer.  But this command\ndoesn't tell the types of the objects, and there can be trees and blobs\nmixed in.\n\nIf your question is also to figure out the minimum set of references\nthat are needed to include all tips (i.e., commits with no descendants),\nthen the answer is trickier.  There is a command that should do what you\nsay:\n\n    git merge-base --independent <commit>...\n\nbut (1) with a lot of references, your arguments wouldn't all fit on the\ncommand line (recursive use of xargs might be needed), (2) I don't know\nif \"merge-base --independent\" is programmed to work efficiently on so\nmany inputs, and (3) I don't know of a cheap way of getting a list of\nall commits referred to by references (i.e., dereferencing annotated\ntags but ignoring references/annotated tags that refer to trees or blobs).\n\n\nAnother approach is to start by finding the leaf commits by SHA-1.  You\ncan do this by listing all commits, and listing all commits' parents,\nand then finding the objects that appear in the first list but not the\nsecond.  This could look like\n\n    comm -23 \\\n        <(git log --all --pretty=format:'%H' | sort -u) \\\n        <(git log --all --pretty=format:'%P' | tr ' ' '\\n' | sort -u)\n\nIf you want reference names corresponding to these SHA-1s, you could use\nname-rev to convert the SHA-1s into refnames:\n\n    git rev-parse --symbolic-full-name $(\n        comm -23 \\\n            <(git log --all --pretty=format:'%H' | sort -u) \\\n            <(git log --all --pretty=format:'%P' | tr ' ' '\\n' | sort -u) |\n        git name-rev --stdin --name-only\n        )\n\nThe \"rev-parse --symbolic-full-name\" is needed because \"name-ref\" seems\nonly able to emit abbreviated reference names.\n\n\nIn practice, you might want to cache some of the results to avoid having\nto do a full tree traversal every time.\n\n> We also tried to read tags by manually parsing .git files (it is\n> faster than invoking git log), but unfortunately annotated tags in\n> .git/refs/tags/ are written without the hashes they point to (unlike\n> .git/packed-refs).\n\nI strongly recommend against parsing these files yourselves.  Your\nsoftware would not be robust against any future changes to the file\nformats etc.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"238849","messageId":"2565BB66-62C0-4E59-9C90-4040E529B3D6@jetbrains.com","threadId":"36407","inReplyTo":"534AE379.7000705@alum.mit.edu","subject":"Re: Get all tips quickly","fromName":"Kirill Likhodedov","fromEmail":"kirill.likhodedov@jetbrains.com","sentAt":"2014-04-14T14:20:30Z","receivedAt":"2014-04-14T14:20:30Z","isPatch":false,"sender":{"key":"kirill.likhodedov@jetbrains.com","avatar":"https://gravatar.com/avatar/9fd55d2a110e8e96deb3ed7b503d7f3b9b5b1ed5ca9ef6683c15525b11b94e63?d=mp&s=160"},"body":"\nHi Michael, Ævar,\n\nThank you very much for your answers.\n\nEach of 'git show-ref’ and ‘git for-each-ref’ is 2 times faster than ‘git log --branches --tags --remotes’ on “warmed up\" FS caches, but take the same time on “cold” FS.\n\nIt seems that all these approaches internally walk down from all references. \n\nSo, given that there is no way to get just tips (I was actually hoping that Git might be storing them somewhere else), we will stick to ‘git show ref -d’.\n\nThanks a lot,\nKirill.\n\n\nOn 13 Apr 2014, at 22:29 , Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:\n\n> Tried \"git for-each-ref\" and the various options it has?\n> \n> Doing this for 35k tags is still going to be non-trivial.\n\nOn 13 Apr 2014, at 23:20 , Michael Haggerty <mhagger@alum.mit.edu> wrote:\n\n> On 04/13/2014 04:19 PM, Kirill Likhodedov wrote:\n>> What is fastest possible way to get all “tips” (leafs of the Git log\n>> graph) in a Git repository with hashes of commits they point to?\n>> \n>> We at JetBrains are tuning performance of Git log integration in our\n>> IntelliJ IDEA and want to get all tips as fast as possible. Currently\n>> we use 'git log —branches --tags --remotes --no-walk’, but the\n>> problem is that it is slow if there are a lot of references. In our\n>> repository we have about 35K tags, and therefore the tags is the main\n>> slowdown. On the other hand, we have just a couple of dozens of tips\n>> as well as branch references, and `git log --branches --remotes` is\n>> very fast.\n>> \n>> So we are searching a way to get tags pointing to the graph leafs\n>> faster.\n> \n> The fastest ways to get all references plus the commits that are pointed\n> at by annotated references would probably be `git show-ref -d`.  The\n> funny-looking entries like \"refs/tags/v1.7.0^{}\" are the annotated tags\n> peeled to the object that they ultimately refer.  But this command\n> doesn't tell the types of the objects, and there can be trees and blobs\n> mixed in.\n> \n> If your question is also to figure out the minimum set of references\n> that are needed to include all tips (i.e., commits with no descendants),\n> then the answer is trickier.  There is a command that should do what you\n> say:\n> \n>    git merge-base --independent <commit>...\n> \n> but (1) with a lot of references, your arguments wouldn't all fit on the\n> command line (recursive use of xargs might be needed), (2) I don't know\n> if \"merge-base --independent\" is programmed to work efficiently on so\n> many inputs, and (3) I don't know of a cheap way of getting a list of\n> all commits referred to by references (i.e., dereferencing annotated\n> tags but ignoring references/annotated tags that refer to trees or blobs).\n> \n> \n> Another approach is to start by finding the leaf commits by SHA-1.  You\n> can do this by listing all commits, and listing all commits' parents,\n> and then finding the objects that appear in the first list but not the\n> second.  This could look like\n> \n>    comm -23 \\\n>        <(git log --all --pretty=format:'%H' | sort -u) \\\n>        <(git log --all --pretty=format:'%P' | tr ' ' '\\n' | sort -u)\n> \n> If you want reference names corresponding to these SHA-1s, you could use\n> name-rev to convert the SHA-1s into refnames:\n> \n>    git rev-parse --symbolic-full-name $(\n>        comm -23 \\\n>            <(git log --all --pretty=format:'%H' | sort -u) \\\n>            <(git log --all --pretty=format:'%P' | tr ' ' '\\n' | sort -u) |\n>        git name-rev --stdin --name-only\n>        )\n> \n> The \"rev-parse --symbolic-full-name\" is needed because \"name-ref\" seems\n> only able to emit abbreviated reference names.\n> \n> \n> In practice, you might want to cache some of the results to avoid having\n> to do a full tree traversal every time.\n> \n>> We also tried to read tags by manually parsing .git files (it is\n>> faster than invoking git log), but unfortunately annotated tags in\n>> .git/refs/tags/ are written without the hashes they point to (unlike\n>> .git/packed-refs).\n> \n> I strongly recommend against parsing these files yourselves.  Your\n> software would not be robust against any future changes to the file\n> formats etc.\n> \n> Michael\n> \n> -- \n> Michael Haggerty\n> mhagger@alum.mit.edu\n> http://softwareswirl.blogspot.com/\n"}]}