{"thread":{"id":"55261","subject":"rev-list --use-bitmap-index","startedAt":"2021-03-05T08:18:32Z","lastAt":"2021-03-06T23:01:53Z","messageCount":4,"participants":["Bryan Turner","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"418302","messageId":"CAGyf7-EXQJ2rWFqvt++Gi2=ZSCBonNtS1JSBkW4k+ORrQiyizQ@mail.gmail.com","threadId":"55261","inReplyTo":null,"subject":"rev-list --use-bitmap-index","fromName":"Bryan Turner","fromEmail":"bturner@atlassian.com","sentAt":"2021-03-05T08:18:15Z","receivedAt":"2021-03-05T08:18:32Z","isPatch":false,"sender":{"key":"bturner@atlassian.com","avatar":"https://gravatar.com/avatar/16bcf3167981c1ef7c804e502642366d888a35b0d0b0a4ca01fdc442aa1acb1e?d=mp&s=160"},"body":"The documentation for --use-bitmap-index notes that if used with\n--objects trees and blobs they won't have their paths printed, but it\nappears to change a whole lot more than that. In my testing, it\nappears to mean --date-order, --format. --parents, and maybe more are\neffectively ignored.\n\nIt appears this changed in 2.26.0. The release notes for that version\ninclude this blurb, which seems like it might be relevant, but I'm not\nsure:\n* The object reachability bitmap machinery and the partial cloning\n  machinery were not prepared to work well together, because some\n  object-filtering criteria that partial clones use inherently rely\n  on object traversal, but the bitmap machinery is an optimization\n  to bypass that object traversal. There however are some cases\n  where they can work together, and they were taught about them.\n\nI have a repository with a bitmap:\n$ git repack -abdfln --keep-unreachable\nMarked 2 islands, done.\nEnumerating objects: 3603142, done.\nPropagating island marks: 100% (2576295/2576295), done.\nCounting objects: 100% (3603142/3603142), done.\nDelta compression using up to 20 threads\nCompressing objects: 100% (2898179/2898179), done.\nWriting objects: 100% (3603142/3603142), done.\nReusing bitmaps: 291, done.\nSelecting bitmap commits: 293052, done.\nBuilding bitmaps: 100% (363/363), done.\n\nHere's some output from Git 2.25.1:\n$ /opt/git/2.25.1/bin/git rev-list --boundary --ignore-missing\n--date-order --parents --use-bitmap-index\nc6abb83d2798415fa9fe0ebd683623620076b412\n1c55e675a66cb98955232e1bd230119fd97a5467\n634396036782682e7cd8c955070dfb30546ed58c -- | head\nc6abb83d2798415fa9fe0ebd683623620076b412\n2c7281b151d0079acc3f9b2c67d4667e1c9bf6d9\n634396036782682e7cd8c955070dfb30546ed58c\n1c55e675a66cb98955232e1bd230119fd97a5467\n2c7281b151d0079acc3f9b2c67d4667e1c9bf6d9\nd672894d3b2413b62034cb3cdb3470e5dee0001c\n76250ec85aadff2ff451ec13efdadb8ccfd6b239\nd672894d3b2413b62034cb3cdb3470e5dee0001c\n013343e1900330429bcd1e31bb2ae7261fc1e3af\n3e1e27621aa5f1d49286e23d77199004a835699e\n3e1e27621aa5f1d49286e23d77199004a835699e\nb944291d204cb7f3d5eb7678360b16435c53b2f3\nb745a7b9bd9434eefb411d5f2a80a7187e3e8b93\n1c55e675a66cb98955232e1bd230119fd97a5467\n7f2c871e0d239e87bef7a1505ae928ae3a09a402\n76250ec85aadff2ff451ec13efdadb8ccfd6b239\n04f561866a9c015c14c69a0294b753ced5e084f2\n013343e1900330429bcd1e31bb2ae7261fc1e3af\nd907528818d010a360113790e227ebbcd8a61395\nb745a7b9bd9434eefb411d5f2a80a7187e3e8b93\nb944291d204cb7f3d5eb7678360b16435c53b2f3\n7f2c871e0d239e87bef7a1505ae928ae3a09a402\nc2ec4d3d76d865a9b701eb8be822d31252278a76\n\nChanging to Git 2.26.0, I see this:\n$ /opt/git/2.26.0/bin/git rev-list --boundary --ignore-missing\n--date-order --parents --use-bitmap-index\nc6abb83d2798415fa9fe0ebd683623620076b412\n1c55e675a66cb98955232e1bd230119fd97a5467\n634396036782682e7cd8c955070dfb30546ed58c -- | head\n634396036782682e7cd8c955070dfb30546ed58c\n1c55e675a66cb98955232e1bd230119fd97a5467\n7f2c871e0d239e87bef7a1505ae928ae3a09a402\nc2ec4d3d76d865a9b701eb8be822d31252278a76\n899053a9043045fcfeb7f9254f2700d286c60a63\nf1adcf64a8c06cb12f4e3e876040ee596fb3c0ca\n16792db59ffdbbefe4a27a11a9831eac39be69a0\nb844c3d11d09c2aec3428ce61bef02fdd097b9f9\n802918fb139ef96cae5259822d22a36478c5e7b1\n3a6105686ab302093648733dbf5fada3b44db72b\n\nNo parents now, and the commits aren't in the same order. I've tested\nwith 2.30.1 and it produces the same output as 2.26.0. If I remove the\nbitmap, all versions produce the same output as 2.25.1 does, with\nparents and in the expected order. (I should note, the bitmap is\nperfectly up-to-date; I did the repack right before running these\nrev-list commands. I've also tried the rev-list without several of the\noptions in place, like --boundary, and it behaves the same. This\ncommand line is assembled automatically, so I'm just including it here\nhow the system produced it.)\n\nIs this expected? If so, perhaps the --use-bitmap-index documentation\nshould be updated to indicate that it has unexpected interactions with\na whole lot more than just --objects? Or perhaps I'm doing something\nwrong/unexpected here? What sorts of traversals are --use-bitmap-index\nexpected to be used for?\n\nBest regards,\nBryan Turner\n"},{"id":"418303","messageId":"CAGyf7-FsrTUzrEwgzSXotmEV1VZHAgOA18i_E2D3P7cbuCUQ=A@mail.gmail.com","threadId":"55261","inReplyTo":"CAGyf7-EXQJ2rWFqvt++Gi2=ZSCBonNtS1JSBkW4k+ORrQiyizQ@mail.gmail.com","subject":"Re: rev-list --use-bitmap-index","fromName":"Bryan Turner","fromEmail":"bturner@atlassian.com","sentAt":"2021-03-05T08:24:58Z","receivedAt":"2021-03-05T08:25:35Z","isPatch":false,"sender":{"key":"bturner@atlassian.com","avatar":"https://gravatar.com/avatar/16bcf3167981c1ef7c804e502642366d888a35b0d0b0a4ca01fdc442aa1acb1e?d=mp&s=160"},"body":"On Fri, Mar 5, 2021 at 12:18 AM Bryan Turner <bturner@atlassian.com> wrote:\n>\n> The documentation for --use-bitmap-index notes that if used with\n> --objects trees and blobs they won't have their paths printed, but it\n> appears to change a whole lot more than that. In my testing, it\n> appears to mean --date-order, --format. --parents, and maybe more are\n> effectively ignored.\n>\n> It appears this changed in 2.26.0. The release notes for that version\n> include this blurb, which seems like it might be relevant, but I'm not\n> sure:\n> * The object reachability bitmap machinery and the partial cloning\n>   machinery were not prepared to work well together, because some\n>   object-filtering criteria that partial clones use inherently rely\n>   on object traversal, but the bitmap machinery is an optimization\n>   to bypass that object traversal. There however are some cases\n>   where they can work together, and they were taught about them.\n>\n> I have a repository with a bitmap:\n> $ git repack -abdfln --keep-unreachable\n> Marked 2 islands, done.\n> Enumerating objects: 3603142, done.\n> Propagating island marks: 100% (2576295/2576295), done.\n> Counting objects: 100% (3603142/3603142), done.\n> Delta compression using up to 20 threads\n> Compressing objects: 100% (2898179/2898179), done.\n> Writing objects: 100% (3603142/3603142), done.\n> Reusing bitmaps: 291, done.\n> Selecting bitmap commits: 293052, done.\n> Building bitmaps: 100% (363/363), done.\n>\n> Here's some output from Git 2.25.1:\n> $ /opt/git/2.25.1/bin/git rev-list --boundary --ignore-missing\n> --date-order --parents --use-bitmap-index\n> c6abb83d2798415fa9fe0ebd683623620076b412\n> 1c55e675a66cb98955232e1bd230119fd97a5467\n> 634396036782682e7cd8c955070dfb30546ed58c -- | head\n> c6abb83d2798415fa9fe0ebd683623620076b412\n> 2c7281b151d0079acc3f9b2c67d4667e1c9bf6d9\n> 634396036782682e7cd8c955070dfb30546ed58c\n> 1c55e675a66cb98955232e1bd230119fd97a5467\n> 2c7281b151d0079acc3f9b2c67d4667e1c9bf6d9\n> d672894d3b2413b62034cb3cdb3470e5dee0001c\n> 76250ec85aadff2ff451ec13efdadb8ccfd6b239\n> d672894d3b2413b62034cb3cdb3470e5dee0001c\n> 013343e1900330429bcd1e31bb2ae7261fc1e3af\n> 3e1e27621aa5f1d49286e23d77199004a835699e\n> 3e1e27621aa5f1d49286e23d77199004a835699e\n> b944291d204cb7f3d5eb7678360b16435c53b2f3\n> b745a7b9bd9434eefb411d5f2a80a7187e3e8b93\n> 1c55e675a66cb98955232e1bd230119fd97a5467\n> 7f2c871e0d239e87bef7a1505ae928ae3a09a402\n> 76250ec85aadff2ff451ec13efdadb8ccfd6b239\n> 04f561866a9c015c14c69a0294b753ced5e084f2\n> 013343e1900330429bcd1e31bb2ae7261fc1e3af\n> d907528818d010a360113790e227ebbcd8a61395\n> b745a7b9bd9434eefb411d5f2a80a7187e3e8b93\n> b944291d204cb7f3d5eb7678360b16435c53b2f3\n> 7f2c871e0d239e87bef7a1505ae928ae3a09a402\n> c2ec4d3d76d865a9b701eb8be822d31252278a76\n\nApologies, it looks like Gmail helpfully jumped in and ruined my\noutput for me. Let me try this with shorter hashes:\nc6abb83 2c7281b\n6343960 1c55e67\n2c7281b d672894 76250ec\nd672894 013343e 3e1e276\n3e1e276 b944291 b745a7b\n1c55e67 7f2c871\n76250ec 04f5618\n013343e d907528\nb745a7b b944291\n7f2c871 c2ec4d3d\n\n>\n> Changing to Git 2.26.0, I see this:\n> $ /opt/git/2.26.0/bin/git rev-list --boundary --ignore-missing\n> --date-order --parents --use-bitmap-index\n> c6abb83d2798415fa9fe0ebd683623620076b412\n> 1c55e675a66cb98955232e1bd230119fd97a5467\n> 634396036782682e7cd8c955070dfb30546ed58c -- | head\n> 634396036782682e7cd8c955070dfb30546ed58c\n> 1c55e675a66cb98955232e1bd230119fd97a5467\n> 7f2c871e0d239e87bef7a1505ae928ae3a09a402\n> c2ec4d3d76d865a9b701eb8be822d31252278a76\n> 899053a9043045fcfeb7f9254f2700d286c60a63\n> f1adcf64a8c06cb12f4e3e876040ee596fb3c0ca\n> 16792db59ffdbbefe4a27a11a9831eac39be69a0\n> b844c3d11d09c2aec3428ce61bef02fdd097b9f9\n> 802918fb139ef96cae5259822d22a36478c5e7b1\n> 3a6105686ab302093648733dbf5fada3b44db72b\n\nAll of these are on their own lines, as shown.\n\n>\n> No parents now, and the commits aren't in the same order. I've tested\n> with 2.30.1 and it produces the same output as 2.26.0. If I remove the\n> bitmap, all versions produce the same output as 2.25.1 does, with\n> parents and in the expected order. (I should note, the bitmap is\n> perfectly up-to-date; I did the repack right before running these\n> rev-list commands. I've also tried the rev-list without several of the\n> options in place, like --boundary, and it behaves the same. This\n> command line is assembled automatically, so I'm just including it here\n> how the system produced it.)\n>\n> Is this expected? If so, perhaps the --use-bitmap-index documentation\n> should be updated to indicate that it has unexpected interactions with\n> a whole lot more than just --objects? Or perhaps I'm doing something\n> wrong/unexpected here? What sorts of traversals are --use-bitmap-index\n> expected to be used for?\n>\n> Best regards,\n> Bryan Turner\n"},{"id":"418305","messageId":"YEHv/tlTWv72BDJ2@coredump.intra.peff.net","threadId":"55261","inReplyTo":"CAGyf7-EXQJ2rWFqvt++Gi2=ZSCBonNtS1JSBkW4k+ORrQiyizQ@mail.gmail.com","subject":"Re: rev-list --use-bitmap-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-03-05T08:46:54Z","receivedAt":"2021-03-05T08:48:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 05, 2021 at 12:18:15AM -0800, Bryan Turner wrote:\n\n> The documentation for --use-bitmap-index notes that if used with\n> --objects trees and blobs they won't have their paths printed, but it\n> appears to change a whole lot more than that. In my testing, it\n> appears to mean --date-order, --format. --parents, and maybe more are\n> effectively ignored.\n\nYes, quite a few options won't work with bitmaps. The order you get is\nnot a traversal order at all, but mostly just the order of objects\nwithin the pack (and then with any extra traversal we had to do tacked\nonto the end!). Likewise something like \"--boundary\", as that implies\nthat we actually walked the graph. We probably _could_ support --format\nand --parents, but don't.\n\nProbably the documentation should be strengthened to say that\n--use-bitmap-index implies thinking about the resulting objects as a set\nresult, rather than a traversal. Or maybe that's getting too into the\nweeds.\n\n> It appears this changed in 2.26.0. The release notes for that version\n> include this blurb, which seems like it might be relevant, but I'm not\n> sure:\n\nIt has always been the case that those options wouldn't work with\nbitmaps. But v2.26 did let us use bitmaps in more cases.\n\nThe blurb you mentioned is a bit of a red herring; it only applies when\n--filter is used. The interesting commit for your example below is\n4eb707ebd6 (rev-list: allow commit-only bitmap traversals, 2020-02-14).\n\nThe \"--use-bitmap-index\" option is really \"if you can use bitmaps to\nspeed things up, do so\". So prior to v2.26 it was simply being ignored\nin your example (and you got no speedup benefit from specifying it).\n\nThat \"use it if you can\" behavior should probably likewise be\ndocumented. Callers need to be prepared to receive either result (and\nhence asking for stuff like --boundary does not make any sense at all).\n\n> Is this expected? If so, perhaps the --use-bitmap-index documentation\n> should be updated to indicate that it has unexpected interactions with\n> a whole lot more than just --objects? Or perhaps I'm doing something\n> wrong/unexpected here? What sorts of traversals are --use-bitmap-index\n> expected to be used for?\n\nThe interesting traversals IMHO are:\n\n  - with --objects, quickly getting the result set (but without paths,\n    and without any ordering)\n\n  - with --count (with or without --objects), because we avoid quite a\n    bit of work by counting bits rather than walking the graph\n\n  - with the new --disk-usage, which likewise avoids a bunch of work\n\nAsking about just commits via bitmaps isn't that big a speed improvement\nthese days, because commit graphs make the cost to actually traverse\neach commit way cheaper (see the numbers in the commit I mentioned\nabove).\n\nSo the behavior you're seeing is expected, but probably not all that\nuseful (and you should likely just drop --use-bitmap-index).\n\n-Peff\n"},{"id":"418413","messageId":"CAGyf7-Fp+xmC6KNr7pY+DFgv+oRGPHS+5sp8PE5c1RQQ4GNiOw@mail.gmail.com","threadId":"55261","inReplyTo":"YEHv/tlTWv72BDJ2@coredump.intra.peff.net","subject":"Re: rev-list --use-bitmap-index","fromName":"Bryan Turner","fromEmail":"bturner@atlassian.com","sentAt":"2021-03-06T23:00:43Z","receivedAt":"2021-03-06T23:01:53Z","isPatch":false,"sender":{"key":"bturner@atlassian.com","avatar":"https://gravatar.com/avatar/16bcf3167981c1ef7c804e502642366d888a35b0d0b0a4ca01fdc442aa1acb1e?d=mp&s=160"},"body":"On Fri, Mar 5, 2021 at 12:47 AM Jeff King <peff@peff.net> wrote:\n>\n> On Fri, Mar 05, 2021 at 12:18:15AM -0800, Bryan Turner wrote:\n>\n> > The documentation for --use-bitmap-index notes that if used with\n> > --objects trees and blobs they won't have their paths printed, but it\n> > appears to change a whole lot more than that. In my testing, it\n> > appears to mean --date-order, --format. --parents, and maybe more are\n> > effectively ignored.\n>\n> Yes, quite a few options won't work with bitmaps. The order you get is\n> not a traversal order at all, but mostly just the order of objects\n> within the pack (and then with any extra traversal we had to do tacked\n> onto the end!). Likewise something like \"--boundary\", as that implies\n> that we actually walked the graph. We probably _could_ support --format\n> and --parents, but don't.\n>\n> Probably the documentation should be strengthened to say that\n> --use-bitmap-index implies thinking about the resulting objects as a set\n> result, rather than a traversal. Or maybe that's getting too into the\n> weeds.\n\nI can't speak for anyone else, but to me that actually feels a lot\nless \"in the weeds\" than the current documentation.\n- The existing documentation talks about \"speeding up the traversal\",\nbut your comment here suggests what it actually does is _eliminate_\nthe traversal--producing output that's totally different (in terms of\nordering and content) to what a traversal would have produced\n- The existing documentation talks about one specific flag, --objects,\nwhere the output can change dramatically depending on whether\n--use-bitmap-index is applied, but it doesn't hint at all that there\nare other flags that are also affected, or may just be outright\nignored\n\nDocumenting that --use-bitmap-index produces a set, rather than a\ntraversal, might be more clear.\n\n>\n> > It appears this changed in 2.26.0. The release notes for that version\n> > include this blurb, which seems like it might be relevant, but I'm not\n> > sure:\n>\n> It has always been the case that those options wouldn't work with\n> bitmaps. But v2.26 did let us use bitmaps in more cases.\n>\n> The blurb you mentioned is a bit of a red herring; it only applies when\n> --filter is used. The interesting commit for your example below is\n> 4eb707ebd6 (rev-list: allow commit-only bitmap traversals, 2020-02-14).\n>\n> The \"--use-bitmap-index\" option is really \"if you can use bitmaps to\n> speed things up, do so\". So prior to v2.26 it was simply being ignored\n> in your example (and you got no speedup benefit from specifying it).\n>\n> That \"use it if you can\" behavior should probably likewise be\n> documented. Callers need to be prepared to receive either result (and\n> hence asking for stuff like --boundary does not make any sense at all).\n>\n> > Is this expected? If so, perhaps the --use-bitmap-index documentation\n> > should be updated to indicate that it has unexpected interactions with\n> > a whole lot more than just --objects? Or perhaps I'm doing something\n> > wrong/unexpected here? What sorts of traversals are --use-bitmap-index\n> > expected to be used for?\n>\n> The interesting traversals IMHO are:\n>\n>   - with --objects, quickly getting the result set (but without paths,\n>     and without any ordering)\n>\n>   - with --count (with or without --objects), because we avoid quite a\n>     bit of work by counting bits rather than walking the graph\n>\n>   - with the new --disk-usage, which likewise avoids a bunch of work\n>\n> Asking about just commits via bitmaps isn't that big a speed improvement\n> these days, because commit graphs make the cost to actually traverse\n> each commit way cheaper (see the numbers in the commit I mentioned\n> above).\n>\n> So the behavior you're seeing is expected, but probably not all that\n> useful (and you should likely just drop --use-bitmap-index).\n\nThanks for all the details, Jeff, and for taking the time to provide\nsuch a thorough answer. I had figured there must be some potential\ndownsides to --use-bitmap-index--otherwise, if it was just a simple\n\"go faster\" knob I'd expect it would have long ago been enabled by\ndefault--but trying to figure out what they are is tricky. And as they\nstart to materialize, the next challenge is to figure out, given those\ndownsides, where the upsides are useful.\n\nBased on your list here, there are a couple places where I think I\ncould see some benefits, in other commands that I run, but it's clear\nit's not a general-use option.\n\n-b\n\n>\n> -Peff\n"}]}