{"thread":{"id":"62435","subject":"[PATCH] rev-list: skip bitmap traversal for --left-right","startedAt":"2024-11-01T12:16:14Z","lastAt":"2025-02-02T12:28:52Z","messageCount":6,"participants":["Jeff King","Taylor Blau","Ayush Chandekar"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"506441","messageId":"20241101121606.GA2327410@coredump.intra.peff.net","threadId":"62435","inReplyTo":null,"subject":"[PATCH] rev-list: skip bitmap traversal for --left-right","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-01T12:16:06Z","receivedAt":"2024-11-01T12:16:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Running:\n\n  git rev-list --left-right --use-bitmap-index one...two\n\nwill produce output without any left-right markers, since the bitmap\ntraversal returns only a single set of reachable commits. Instead we\nshould refuse to use bitmaps here and produce the correct output using a\ntraditional traversal.\n\nThis is probably not the only remaining option that misbehaves with\nbitmaps, but it's particularly egregious in that it feels like it\n_could_ work. Doing two separate traversals for the left/right sides and\nthen taking the symmetric set differences should yield the correct\nanswer, but our traversal code doesn't know how to do that.\n\nIt's not clear if naively doing two separate traversals would always be\na performance win. A traditional traversal only needs to walk down to\nthe merge base, but bitmaps always fill out the full reachability set.\nSo depending on your bitmap coverage, we could end up walking old bits\nof history twice to fill out the same uninteresting bits on both sides.\nWe'd also of course end up with a very large --boundary set, if the user\nasked for that.\n\nSo this might or might not be something worth implementing later. But\nfor now, let's make sure we don't produce the wrong answer if somebody\ntries it.\n\nThe test covers this, but also the same thing with \"--count\" (which is\nwhat I originally tried in a real-world case). Ironically the\ntry_bitmap_count() code already realizes that \"--left-right\" won't work\nthere. But that just causes us to fall back to the regular bitmap\ntraversal code, which itself doesn't handle counting (we produce a list\nof objects rather than a count).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/rev-list.c      |  7 +++++++\n t/t5310-pack-bitmaps.sh | 12 ++++++++++++\n 2 files changed, 19 insertions(+)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex f62bcbf2b1..3078787115 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -485,6 +485,13 @@ static int try_bitmap_traversal(struct rev_info *revs,\n \tif (revs->max_count >= 0)\n \t\treturn -1;\n \n+\t/*\n+\t * We can't know which commits were left/right in a single traversal,\n+\t * and we don't yet know how to traverse them separately.\n+\t */\n+\tif (revs->left_right)\n+\t\treturn -1;\n+\n \tbitmap_git = prepare_bitmap_walk(revs, filter_provided_objects);\n \tif (!bitmap_git)\n \t\treturn -1;\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 7044c7d7c6..6bcbea64cc 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -503,6 +503,18 @@ test_expect_success 'boundary-based traversal is used when requested' '\n \tdone\n '\n \n+test_expect_success 'left-right not confused by bitmap index' '\n+\tgit rev-list --left-right other...HEAD >expect &&\n+\tgit rev-list --use-bitmap-index --left-right other...HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'left-right count not confused by bitmap-index' '\n+\tgit rev-list --left-right --count other...HEAD >expect &&\n+\tgit rev-list --use-bitmap-index --left-right --count other...HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_bitmap_cases \"pack.writeBitmapLookupTable\"\n \n test_expect_success 'verify writing bitmap lookup table when enabled' '\n-- \n2.47.0.441.g1a09955689\n"},{"id":"506451","messageId":"ZyToaRxR7upLg0IE@nand.local","threadId":"62435","inReplyTo":"20241101121606.GA2327410@coredump.intra.peff.net","subject":"Re: [PATCH] rev-list: skip bitmap traversal for --left-right","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-01T14:40:41Z","receivedAt":"2024-11-01T14:40:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Nov 01, 2024 at 08:16:06AM -0400, Jeff King wrote:\n>  builtin/rev-list.c      |  7 +++++++\n>  t/t5310-pack-bitmaps.sh | 12 ++++++++++++\n>  2 files changed, 19 insertions(+)\n\nNice find, and well explained (not just why it doesn't work today but\ncould in the future, but why making it work in the future with bitmaps\ndoes not necessarily a clear performance improvement).\n\nProbably you and I should think more about other rev-list options that\n*don't* work with --use-bitmap-index. I share your feeling there that\nthere probably exist such options which silently do nothing (or the\nwrong thing) in the presence of '--use-bitmap-index'.\n\nLet's merge this one down.\n\nThanks,\nTaylor\n"},{"id":"506551","messageId":"20241104174126.GB2985568@coredump.intra.peff.net","threadId":"62435","inReplyTo":"ZyToaRxR7upLg0IE@nand.local","subject":"Re: [PATCH] rev-list: skip bitmap traversal for --left-right","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-04T17:41:26Z","receivedAt":"2024-11-04T17:41:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 01, 2024 at 10:40:41AM -0400, Taylor Blau wrote:\n\n> Nice find, and well explained (not just why it doesn't work today but\n> could in the future, but why making it work in the future with bitmaps\n> does not necessarily a clear performance improvement).\n> \n> Probably you and I should think more about other rev-list options that\n> *don't* work with --use-bitmap-index. I share your feeling there that\n> there probably exist such options which silently do nothing (or the\n> wrong thing) in the presence of '--use-bitmap-index'.\n\nI'm pretty sure --cherry-pick and --cherry-mark are examples, but I\nsuspect it's the tip of the iceberg. I don't know if it's worth spending\nmuch effort on this. It's certainly a wart, but there's a certain amount\nof \"if it hurts, don't do it\". The --left-right one bugged me so much\njust because I thought it _would_ work. ;)\n\n-Peff\n"},{"id":"506552","messageId":"20241104174628.GA2990236@coredump.intra.peff.net","threadId":"62435","inReplyTo":"20241104174126.GB2985568@coredump.intra.peff.net","subject":"Re: [PATCH] rev-list: skip bitmap traversal for --left-right","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-04T17:46:28Z","receivedAt":"2024-11-04T17:46:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 04, 2024 at 12:41:27PM -0500, Jeff King wrote:\n\n> On Fri, Nov 01, 2024 at 10:40:41AM -0400, Taylor Blau wrote:\n> \n> > Nice find, and well explained (not just why it doesn't work today but\n> > could in the future, but why making it work in the future with bitmaps\n> > does not necessarily a clear performance improvement).\n> > \n> > Probably you and I should think more about other rev-list options that\n> > *don't* work with --use-bitmap-index. I share your feeling there that\n> > there probably exist such options which silently do nothing (or the\n> > wrong thing) in the presence of '--use-bitmap-index'.\n> \n> I'm pretty sure --cherry-pick and --cherry-mark are examples, but I\n> suspect it's the tip of the iceberg. I don't know if it's worth spending\n> much effort on this. It's certainly a wart, but there's a certain amount\n> of \"if it hurts, don't do it\". The --left-right one bugged me so much\n> just because I thought it _would_ work. ;)\n\nActually, I wonder if this could be an interesting #leftoverbits or\nintern mini-project:\n\n  1. Look at the set of rev-list options and pick one.\n\n  2. Repack a repo (say, git.git) with reachability bitmaps using \"git\n     repack -adb\".\n\n  3. Compare output of \"rev-list --your-option\" with and without\n     --use-bitmap-index. If the outputs do not reasonably match, add\n     code to try_bitmap_traversal() to forbid it and bail to the\n     non-bitmap path. Maybe also other try_bitmap_*() functions, as\n     well.\n\nIt's a little more involved than other miniprojects just because there\nmay be some judgement needed for \"reasonably match\". Being byte-for-byte\nidentical is good, but in some cases the output will be different (e.g.,\nbitmap output is in a different order, lacks path annotations, etc). So\nit would help in step (1) if you understand what the option is supposed\nto do and how you'd expect it to work with bitmaps. ;)\n\n-Peff\n"},{"id":"506553","messageId":"ZykTwaWaveGGvapw@nand.local","threadId":"62435","inReplyTo":"20241104174628.GA2990236@coredump.intra.peff.net","subject":"Re: [PATCH] rev-list: skip bitmap traversal for --left-right","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-04T18:34:41Z","receivedAt":"2024-11-04T18:34:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Nov 04, 2024 at 12:46:28PM -0500, Jeff King wrote:\n> On Mon, Nov 04, 2024 at 12:41:27PM -0500, Jeff King wrote:\n>\n> > On Fri, Nov 01, 2024 at 10:40:41AM -0400, Taylor Blau wrote:\n> >\n> > > Nice find, and well explained (not just why it doesn't work today but\n> > > could in the future, but why making it work in the future with bitmaps\n> > > does not necessarily a clear performance improvement).\n> > >\n> > > Probably you and I should think more about other rev-list options that\n> > > *don't* work with --use-bitmap-index. I share your feeling there that\n> > > there probably exist such options which silently do nothing (or the\n> > > wrong thing) in the presence of '--use-bitmap-index'.\n> >\n> > I'm pretty sure --cherry-pick and --cherry-mark are examples, but I\n> > suspect it's the tip of the iceberg. I don't know if it's worth spending\n> > much effort on this. It's certainly a wart, but there's a certain amount\n> > of \"if it hurts, don't do it\". The --left-right one bugged me so much\n> > just because I thought it _would_ work. ;)\n>\n> Actually, I wonder if this could be an interesting #leftoverbits or\n> intern mini-project:\n\nI agree; that would be a good project for interns. Great idea!\n\nThanks,\nTaylor\n"},{"id":"511659","messageId":"20250202122837.335101-1-ayu.chandekar@gmail.com","threadId":"62435","inReplyTo":"ZykTwaWaveGGvapw@nand.local","subject":"Re: [PATCH] rev-list: skip bitmap traversal for --left-right","fromName":"Ayush Chandekar","fromEmail":"ayu.chandekar@gmail.com","sentAt":"2025-02-02T12:28:37Z","receivedAt":"2025-02-02T12:28:52Z","isPatch":true,"sender":{"key":"ayu.chandekar@gmail.com","avatar":"https://avatars.githubusercontent.com/u/137001939?v=4"},"body":"Hey,\nI found this issue quite interesting. Would you like to discuss a bit more,\nmaybe about how to implement it?\n\nI am looking forward to solving this.\n\nRegards,\nAyush\n"}]}