{"thread":{"id":"47677","subject":"Speed of git branch --contains","startedAt":"2018-01-24T07:12:15Z","lastAt":"2018-01-24T16:20:52Z","messageCount":2,"participants":["Andreas Krey","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"337205","messageId":"20180123203656.GA27016@inner.h.apk.li","threadId":"47677","inReplyTo":null,"subject":"Speed of git branch --contains","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2018-01-23T20:36:56Z","receivedAt":"2018-01-24T07:12:15Z","isPatch":false,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"Hi everybody,\n\nI'm just looking at some scripts that do a 'git branch --contains $id --remote'\nfor each new commit in a repo, and unfortunately each invokation already\ntakes four minutes.\n\nIt feels like git branch does the reachability detection separately\nfor each branch potentially listed. The alternative would be to\n\n- invert the parent map to a child map,\n- use that to compute the set of commits that contain $id,\n- then use that as predicate whether to show a given branch\n  (show iff its head is in the set)\n\nThat would speed things up considerably,\nbut what are the chances to see that change in git?\n\nI can do that as well within the script, with the additional\nbenefit that I only need to do the inversion once, but I might\ninstead take a stab at git branch.\n\n- Andreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"337266","messageId":"87607rgreq.fsf@evledraar.gmail.com","threadId":"47677","inReplyTo":"20180123203656.GA27016@inner.h.apk.li","subject":"Re: Speed of git branch --contains","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-24T16:20:13Z","receivedAt":"2018-01-24T16:20:52Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, Jan 23 2018, Andreas Krey jotted:\n\n> I'm just looking at some scripts that do a 'git branch --contains $id --remote'\n> for each new commit in a repo, and unfortunately each invokation already\n> takes four minutes.\n>\n> It feels like git branch does the reachability detection separately\n> for each branch potentially listed. The alternative would be to\n>\n> - invert the parent map to a child map,\n> - use that to compute the set of commits that contain $id,\n> - then use that as predicate whether to show a given branch\n>   (show iff its head is in the set)\n>\n> That would speed things up considerably,\n> but what are the chances to see that change in git?\n>\n> I can do that as well within the script, with the additional\n> benefit that I only need to do the inversion once, but I might\n> instead take a stab at git branch.\n\nI posted something similar to the list the other day, and Derrick had a\ngreat follow-up to that which summarized the current work on this:\nhttps://public-inbox.org/git/87608bawoa.fsf@evledraar.gmail.com/\n\nJunio mentioned an edge case in that thread which you may not have\nthought of (I didn't). I.e. that one problem with such a mapping is that\na new branch may at any point push new history which includes your\ncommit as a merge, forcing you to re-compute this child map.\n\nThat can be optimized by checking whether some commits come after others\ntimestamp wise, but that brings us to the problem that timestamps aren't\nguaranteed to be monotonically increasing (and may even be years off) by\ngit, which is another optimization challenge for things like --contains.\n"}]}