{"thread":{"id":"59460","subject":"What is the status of GSoC 2022 work on making Git use roaring bitmaps?","startedAt":"2023-03-23T19:26:21Z","lastAt":"2023-08-01T17:44:24Z","messageCount":14,"participants":["Jakub Narębski","Taylor Blau","Abhradeep Chakraborty","Han-Wen Nienhuys"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"474026","messageId":"858rfnb770.fsf@gmail.com","threadId":"59460","inReplyTo":null,"subject":"What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2023-03-23T19:26:11Z","receivedAt":"2023-03-23T19:26:21Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nCould you tell me what is the status of the Abhradeep Chakraborty work\nin integrating roaring bitmaps (using CRoaring) in addition to, or\nreplacing current EWAH bitmaps (using ewok)? The last communication\nabout this shows that the patches were on the road to being merged in,\nsee e.g. https://medium.com/@abhra303/gsoc-final-report-feaaacfae737 ,\nbut there is no mention of 'roaring' in Git's code or documentation.\n\nMoreover, there is no proposal to finish this on the GSoC 2023 ideas\npage: https://git.github.io/SoC-2023-Ideas/ . Is it because it would be\ntoo small of a project? Or maybe it turned out that roaring bitmaps\nwere not a good idea - though I haven't found mentions of any benchmarks\nof roaring vs EWAH in the mailing list archives? Or perhaps there is no\none to mentor this proposal?\n\nRegards,\n--\nJakub Narębski\n"},{"id":"474038","messageId":"ZBy18EBE7WM/E4KF@nand.local","threadId":"59460","inReplyTo":"858rfnb770.fsf@gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-03-23T20:26:24Z","receivedAt":"2023-03-23T20:26:33Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Jakub,\n\nOn Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:\n> Hello,\n>\n> Could you tell me what is the status of the Abhradeep Chakraborty work\n> in integrating roaring bitmaps (using CRoaring) in addition to, or\n> replacing current EWAH bitmaps (using ewok)? The last communication\n> about this shows that the patches were on the road to being merged in,\n> see e.g. https://medium.com/@abhra303/gsoc-final-report-feaaacfae737 ,\n> but there is no mention of 'roaring' in Git's code or documentation.\n\nAbhradeep started working on a prototype to teach Git how to read and\nwrite Roaring+Run bitmaps in this series:\n\n https://lore.kernel.org/git/pull.1357.git.1663609659.gitgitgadget@gmail.com/\n\nSome folks gave it a review, but there wasn't any serious traction and I\ndon't think that Abhradeep has had a chance to come back to the series.\n\nFor what it's worth, I would love if Abhradeep (or anybody else\ninterested in working on this area) picked it back up, either using that\nseries as a starting point or going from scratch.\n\n> Moreover, there is no proposal to finish this on the GSoC 2023 ideas\n> page: https://git.github.io/SoC-2023-Ideas/ . Is it because it would be\n> too small of a project? Or maybe it turned out that roaring bitmaps\n> were not a good idea - though I haven't found mentions of any benchmarks\n> of roaring vs EWAH in the mailing list archives? Or perhaps there is no\n> one to mentor this proposal?\n\nI don't have the capacity to mentor a student this cycle, and I am\nprobably the most interested among potential mentors in seeing this\nproject through ;-).\n\nI don't think that it's too small (in fact, it was probably an error on\nmy part to include this as a potential stretch goal in Abhradeep's\nproject). We don't have any evidence that it's a good or bad idea.\n\nAbhradeep promised[1] that he'd include some performance work in his\nnext version of that series. I think the main things we'd be interested\nin are:\n\n - Does using Roaring provide a file-size advantage over\n EWAH-compressed bitmaps?\n - Does Roaring make it faster to inflate bitmaps? To deflate them?\n\nDeflating bitmaps doesn't matter as much, IMHO, since that is a cost\nthat we pay only when we first have to compress bitmaps before writing\nthem. But if we could significantly reduce the inflation cost, that\nwould be an advantage to using Roaring+Run bitmaps over EWAH ones since\nthey would be faster to decompress at read-time.\n\nThanks,\nTaylor\n\n[1]: https://lore.kernel.org/git/CAPOJW5wkXrV8eOysz6aJ5jN2u_u-iTX_3om3tSDKw+EmfCJBEw@mail.gmail.com/\n"},{"id":"474056","messageId":"851qlfazzp.fsf@gmail.com","threadId":"59460","inReplyTo":"ZBy18EBE7WM/E4KF@nand.local","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2023-03-23T22:01:46Z","receivedAt":"2023-03-23T22:02:21Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello Taylor,\n\nThanks for a fast response.\n\nTaylor Blau writes:\n> On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:\n>> Hello,\n>>\n>> Could you tell me what is the status of the Abhradeep Chakraborty work\n>> in integrating roaring bitmaps (using CRoaring) in addition to, or\n>> replacing current EWAH bitmaps (using ewok)? The last communication\n>> about this shows that the patches were on the road to being merged in,\n>> see e.g. https://medium.com/@abhra303/gsoc-final-report-feaaacfae737 ,\n>> but there is no mention of 'roaring' in Git's code or documentation.\n>\n> Abhradeep started working on a prototype to teach Git how to read and\n> write Roaring+Run bitmaps in this series:\n>\n> https://lore.kernel.org/git/pull.1357.git.1663609659.gitgitgadget@gmail.com/\n>\n> Some folks gave it a review, but there wasn't any serious traction and I\n> don't think that Abhradeep has had a chance to come back to the series.\n>\n> For what it's worth, I would love if Abhradeep (or anybody else\n> interested in working on this area) picked it back up, either using that\n> series as a starting point or going from scratch.\n\nWhen I searched the mailing list archives, the thread was never continued.\n\n>> Moreover, there is no proposal to finish this on the GSoC 2023 ideas\n>> page: https://git.github.io/SoC-2023-Ideas/ . Is it because it would be\n>> too small of a project? Or maybe it turned out that roaring bitmaps\n>> were not a good idea - though I haven't found mentions of any benchmarks\n>> of roaring vs EWAH in the mailing list archives? Or perhaps there is no\n>> one to mentor this proposal?\n>\n> I don't have the capacity to mentor a student this cycle, and I am\n> probably the most interested among potential mentors in seeing this\n> project through ;-).\n\nAh, so it is mostly the last issue - lack of a potential mentor for\nconntinuing this project.\n\n> I don't think that it's too small (in fact, it was probably an error on\n> my part to include this as a potential stretch goal in Abhradeep's\n> project). We don't have any evidence that it's a good or bad idea.\n>\n> Abhradeep promised[1] that he'd include some performance work in his\n> next version of that series. I think the main things we'd be interested\n> in are:\n>\n> - Does using Roaring provide a file-size advantage over\n> EWAH-compressed bitmaps?\n> - Does Roaring make it faster to inflate bitmaps? To deflate them?\n\nAs far as I understand it, after reading articles about EWAH[2] and\nabout Roaring Bitmaps[3][4], the Roaring have the advantage that you\ndon't need to decompress (inflate) bitmaps to perform bitwise operations\non them.\n\nRun-Length-Encoding (RLE) formats like EWAH can be made to perform\noperations without decompressing, but only if operations are symmetric.\nThe AND and OR operations are symmetrical, but AND NOT is not. The last\nis used by Git to find \"want\"-ed that are not present (not \"have\") is\nnot. That is why Git needs to decompress bitmap and perform operation.\n\nIf I understand it correctly, for both cases (EWAH and Roaring) you can\ndo membership check without decompressing bitmap.\n\n\n[2] Daniel Lemire et al. \"Sorting improves word-aligned bitmap indexes\",\n arXiv:0901.3751\n\n[3] Samy Chambi, Daniel Lemire et al. \"Optimizing Druid with Roaring\n bitmaps\", https://dl.acm.org/doi/10.1145/2938503.2938515\n[4] Daniel Lemire et al. \"Roaring Bitmaps: Implementation of an\n Optimized Software Library\", arXiv:1709.07821v3\n\n>\n> Deflating bitmaps doesn't matter as much, IMHO, since that is a cost\n> that we pay only when we first have to compress bitmaps before writing\n> them. But if we could significantly reduce the inflation cost, that\n> would be an advantage to using Roaring+Run bitmaps over EWAH ones since\n> they would be faster to decompress at read-time.\n\nWell, if Roaring were to be significantly slower when deflating, but\nonly slightly faster when using / inflating, that would affect their\nevaluation.\n\n>\n> [1]: https://lore.kernel.org/git/CAPOJW5wkXrV8eOysz6aJ5jN2u_u-iTX_3om3tSDKw+EmfCJBEw@mail.gmail.com/\n\nRegards,\n--\nJakub Narębski\n"},{"id":"474070","messageId":"CAPOJW5x+yQsPxdwCWMT9AkMQhJyxKp5BiPXp_1PT6WwF7yF4YQ@mail.gmail.com","threadId":"59460","inReplyTo":"851qlfazzp.fsf@gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Abhradeep Chakraborty","fromEmail":"chakrabortyabhradeep79@gmail.com","sentAt":"2023-03-24T03:48:24Z","receivedAt":"2023-03-24T03:48:42Z","isPatch":false,"sender":{"key":"chakrabortyabhradeep79@gmail.com","avatar":"https://avatars.githubusercontent.com/u/75240995?v=4"},"body":"On Fri, Mar 24, 2023 at 3:32 AM Jakub Narębski wrote:\n>\n> Hello Taylor,\n>\n> Thanks for a fast response.\n>\n> Taylor Blau writes:\n> > On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:\n> >> Hello,\n> >>\n> >> Could you tell me what is the status of the Abhradeep Chakraborty work\n> >> in integrating roaring bitmaps (using CRoaring) in addition to, or\n> >> replacing current EWAH bitmaps (using ewok)? The last communication\n> >> about this shows that the patches were on the road to being merged in,\n> >> see e.g. https://medium.com/@abhra303/gsoc-final-report-feaaacfae737 ,\n> >> but there is no mention of 'roaring' in Git's code or documentation.\n> >\n> > Abhradeep started working on a prototype to teach Git how to read and\n> > write Roaring+Run bitmaps in this series:\n> >\n> > https://lore.kernel.org/git/pull.1357.git.1663609659.gitgitgadget@gmail.com/\n> >\n> > Some folks gave it a review, but there wasn't any serious traction and I\n> > don't think that Abhradeep has had a chance to come back to the series.\n> >\n> > For what it's worth, I would love if Abhradeep (or anybody else\n> > interested in working on this area) picked it back up, either using that\n> > series as a starting point or going from scratch.\n>\n> When I searched the mailing list archives, the thread was never continued.\n\n\nHello community,\n\nI have to apologize for the fact that I didn't continue the patch\nseries. I wasn't\ninvolved in the community either. I am currently too busy to enhance my skills\nto get into a company of \"my dream engineering environment\". The problem is\nthat it needs much effort and time to achieve that.\n\nI have always had a love for the Git project and the community. But\nunfortunately\nI can't contribute to it right now and I don't think I can contribute\nto it prior to\nmy course ends (i.e. June, 2023). I would be happy if anybody else pick the\nissue and continue the work where I left off. I am even ready to\nguide/mentor/help.\n\nThere are certain things in my mind (other than roaring bitmaps) that\nI previously\nshared with Kaartik and Taylor. I will continue to be a part of this\ncommunity and\nwill make contributions after my college ends.\n\n> >> Moreover, there is no proposal to finish this on the GSoC 2023 ideas\n> >> page: https://git.github.io/SoC-2023-Ideas/ . Is it because it would be\n> >> too small of a project? Or maybe it turned out that roaring bitmaps\n> >> were not a good idea - though I haven't found mentions of any benchmarks\n> >> of roaring vs EWAH in the mailing list archives? Or perhaps there is no\n> >> one to mentor this proposal?\n> >\n> > I don't have the capacity to mentor a student this cycle, and I am\n> > probably the most interested among potential mentors in seeing this\n> > project through ;-).\n>\n> Ah, so it is mostly the last issue - lack of a potential mentor for\n> conntinuing this project.\n>\n> > I don't think that it's too small (in fact, it was probably an error on\n> > my part to include this as a potential stretch goal in Abhradeep's\n> > project). We don't have any evidence that it's a good or bad idea.\n\nYeah, It is big enough to take an extra 3 months of code and discussions.\n\n> > Abhradeep promised[1] that he'd include some performance work in his\n> > next version of that series. I think the main things we'd be interested\n> > in are:\n> >\n> > - Does using Roaring provide a file-size advantage over\n> > EWAH-compressed bitmaps?\n> > - Does Roaring make it faster to inflate bitmaps? To deflate them?\n>\n> As far as I understand it, after reading articles about EWAH[2] and\n> about Roaring Bitmaps[3][4], the Roaring have the advantage that you\n> don't need to decompress (inflate) bitmaps to perform bitwise operations\n> on them.\n>\n> Run-Length-Encoding (RLE) formats like EWAH can be made to perform\n> operations without decompressing, but only if operations are symmetric.\n> The AND and OR operations are symmetrical, but AND NOT is not. The last\n> is used by Git to find \"want\"-ed that are not present (not \"have\") is\n> not. That is why Git needs to decompress bitmap and perform operation.\n>\n> If I understand it correctly, for both cases (EWAH and Roaring) you can\n> do membership check without decompressing bitmap.\n>\n>\n> [2] Daniel Lemire et al. \"Sorting improves word-aligned bitmap indexes\",\n> arXiv:0901.3751\n>\n> [3] Samy Chambi, Daniel Lemire et al. \"Optimizing Druid with Roaring\n> bitmaps\", https://dl.acm.org/doi/10.1145/2938503.2938515\n> [4] Daniel Lemire et al. \"Roaring Bitmaps: Implementation of an\n> Optimized Software Library\", arXiv:1709.07821v3\n>\n> >\n> > Deflating bitmaps doesn't matter as much, IMHO, since that is a cost\n> > that we pay only when we first have to compress bitmaps before writing\n> > them. But if we could significantly reduce the inflation cost, that\n> > would be an advantage to using Roaring+Run bitmaps over EWAH ones since\n> > they would be faster to decompress at read-time.\n>\n> Well, if Roaring were to be significantly slower when deflating, but\n> only slightly faster when using / inflating, that would affect their\n> evaluation.\n\nIMHO, I don't think Roaring bitmaps would make any significant performance\nimprovements. It may be faster to decompress, but I believe it takes more\nin memory computation than the EWAH. My biggest concern is its dynamic\nnature. It can dynamically change its underlying data structure into an array,\nbitmap or RLE. I didn't test the performance though and I shouldn't draw any\nconclusions about it.\n\n> >\n> > [1]: https://lore.kernel.org/git/CAPOJW5wkXrV8eOysz6aJ5jN2u_u-iTX_3om3tSDKw+EmfCJBEw@mail.gmail.com/\n>\n> Regards,\n> --\n> Jakub Narębski\n\nI am extremely sorry for the inconvenience and I hope you'll understand the\nsituation.\n\nThanks :)\n\nRegards,\nAbhradeep Chakraborty\n"},{"id":"474179","messageId":"85tty8afvy.fsf@gmail.com","threadId":"59460","inReplyTo":"CAPOJW5x+yQsPxdwCWMT9AkMQhJyxKp5BiPXp_1PT6WwF7yF4YQ@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2023-03-25T17:40:33Z","receivedAt":"2023-03-25T17:40:46Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhradeep Chakraborty writes:\n\nHello Abhradeep,\n\nThank you for your response.\n\n> On Fri, Mar 24, 2023 at 3:32 AM Jakub Narębski wrote:\n>> Taylor Blau writes:\n>>> On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:\n>>>>\n>>>> Could you tell me what is the status of the Abhradeep Chakraborty work\n>>>> in integrating roaring bitmaps (using CRoaring) in addition to, or\n>>>> replacing current EWAH bitmaps (using ewok)? The last communication\n>>>> about this shows that the patches were on the road to being merged in,\n>>>> see e.g. https://medium.com/@abhra303/gsoc-final-report-feaaacfae737 ,\n>>>> but there is no mention of 'roaring' in Git's code or documentation.\n>>>\n>>> Abhradeep started working on a prototype to teach Git how to read and\n>>> write Roaring+Run bitmaps in this series:\n>>>\n>>> https://lore.kernel.org/git/pull.1357.git.1663609659.gitgitgadget@gmail.com/\n>>>\n>>> Some folks gave it a review, but there wasn't any serious traction and I\n>>> don't think that Abhradeep has had a chance to come back to the series.\n>>>\n>>> For what it's worth, I would love if Abhradeep (or anybody else\n>>> interested in working on this area) picked it back up, either using that\n>>> series as a starting point or going from scratch.\n>>\n>> When I searched the mailing list archives, the thread was never continued.\n>\n> Hello community,\n>\n> I have to apologize for the fact that I didn't continue the patch\n> series. I wasn't involved in the community either. I am currently too\n> busy to enhance my skills to get into a company of \"my dream\n> engineering environment\". The problem is that it needs much effort and\n> time to achieve that.\n>\n> I have always had a love for the Git project and the community. But\n> unfortunately I can't contribute to it right now and I don't think I\n> can contribute to it prior to my course ends (i.e. June, 2023). I\n> would be happy if anybody else pick the issue and continue the work\n> where I left off. I am even ready to guide/mentor/help.\n\nLife happens; we can certainly understand the lack of time for work on,\nespecially as a student.\n\n> There are certain things in my mind (other than roaring bitmaps) that\n> I previously shared with Kaartik and Taylor. I will continue to be a\n> part of this community and will make contributions after my college\n> ends.\n\nThank you in advance for your offer.\n\n[...]\n>>> Abhradeep promised[1] that he'd include some performance work in his\n>>> next version of that series. I think the main things we'd be interested\n>>> in are:\n>>>\n>>> - Does using Roaring provide a file-size advantage over\n>>> EWAH-compressed bitmaps?\n>>> - Does Roaring make it faster to inflate bitmaps? To deflate them?\n>>\n>> As far as I understand it, after reading articles about EWAH[2] and\n>> about Roaring Bitmaps[3][4], the Roaring have the advantage that you\n>> don't need to decompress (inflate) bitmaps to perform bitwise operations\n>> on them.\n>>\n>> Run-Length-Encoding (RLE) formats like EWAH can be made to perform\n>> operations without decompressing, but only if operations are symmetric.\n>> The AND and OR operations are symmetrical, but AND NOT is not. The last\n>> is used by Git to find \"want\"-ed that are not present (not \"have\") is\n>> not. That is why Git needs to decompress bitmap and perform\n>> operation.\n\nAt least that is why I think for any operations Git does decompress the\nbitmap into an ordinary bitset / plain bitmap for operations.\n\n>> If I understand it correctly, for both cases (EWAH and Roaring) you can\n>> do membership check without decompressing bitmap.\n>>\n>>\n>> [2] Daniel Lemire et al. \"Sorting improves word-aligned bitmap indexes\",\n>> arXiv:0901.3751\n>>\n>> [3] Samy Chambi, Daniel Lemire et al. \"Optimizing Druid with Roaring\n>> bitmaps\", https://dl.acm.org/doi/10.1145/2938503.2938515\n>> [4] Daniel Lemire et al. \"Roaring Bitmaps: Implementation of an\n>> Optimized Software Library\", arXiv:1709.07821v3\n\nThe last work includes some benchmark. I understand that those\nbenchmarks do not necessary match the particulars of Git's use of\ncompressed bitmaps, but they are there.\n\n>>> Deflating bitmaps doesn't matter as much, IMHO, since that is a cost\n>>> that we pay only when we first have to compress bitmaps before writing\n>>> them. But if we could significantly reduce the inflation cost, that\n>>> would be an advantage to using Roaring+Run bitmaps over EWAH ones since\n>>> they would be faster to decompress at read-time.\n>>\n>> Well, if Roaring were to be significantly slower when deflating, but\n>> only slightly faster when using / inflating, that would affect their\n>> evaluation.\n>\n> IMHO, I don't think Roaring bitmaps would make any significant performance\n> improvements. It may be faster to decompress, but I believe it takes more\n> in memory computation than the EWAH. My biggest concern is its dynamic\n> nature. It can dynamically change its underlying data structure into an array,\n> bitmap or RLE. I didn't test the performance though and I shouldn't draw any\n> conclusions about it.\n\nBenchmarks results in section 5. \"Experiments\", in the D. Lemire et al.\npaper \"Roaring Bitmaps: Implementation of an Optimized Software Library\"\ndoes not include detailed information about memory usage during\noperations (beside mentioning that BitMagic solution, which is one\nsolution they compare Roaring Bitmaps against, has exorbitant memory\nusage).\n\nHowever, there are some relevant results that can be found in this\npaper, namely:\n\n- Roaring had consitently smaller memory usage in bits per value than\n EWAH, though the difference is not large (e.g. 2.60 vs 3.29, or 0.60\n vs 0.64 for different examples of Roaring vs EWAH)\n- time needed to iterate through all values was also smaller, for\n example 5.87 Roaring vs 13.1 EWAH\n- EWAH, WAH, and Concise has terrible random-access membership check\n performance; uncompressed is fastest, but Roaring is only 20x slower\n than uncompressed (e.g. 3.74 for bitset[5] vs 63.6 for Roaring,\n vs 3260 for EWAH)\n- for computing two-by-two intersections (AND), unions (OR), differences\n (AND NOT), and symmetric differences (XOR) Roaring is fastest or\n second-fastest after uncompressed bitset; EWAH is always slower\n- for compting wide union of 200 sets, Roaring is generally faster (in\n several instances several time faster than alternative), except for\n two cases where is about 20% or 10% slower than best (but not than\n EWAH).\n\n[5]: https://github.com/lemire/cbitset\n\n\n> I am extremely sorry for the inconvenience and I hope you'll understand the\n> situation.\n\nThank you for all your work on reachability bitmaps.\n\nBest,\n--\nJakub Narębski\n"},{"id":"480005","messageId":"CAFQ2z_P2HkT8grAFk=6Mr05rJRfsh_sXypVFPyHr0v5xkcjYTA@mail.gmail.com","threadId":"59460","inReplyTo":"85tty8afvy.fsf@gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2023-07-31T17:46:18Z","receivedAt":"2023-07-31T17:46:38Z","isPatch":false,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"On Sat, Mar 25, 2023 at 6:40 PM Jakub Narębski wrote:\n> >>> Abhradeep promised[1] that he'd include some performance work in his\n> >>> next version of that series. I think the main things we'd be interested\n> >>> in are:\n> >>>\n> >>> - Does using Roaring provide a file-size advantage over\n> >>> EWAH-compressed bitmaps?\n\nI modified JGit to write Roaring bitmaps instead of EWAH bitmaps. The\nresulting difference in file sizes are small, and actually favor EWAH:\n\n$ ls -l {ewah-repos,roaring-repos}/*.git/objects/pack/*.bitmap\n-r--r----- 1 hanwen primarygroup 26257386 Jul 31 15:04\newah-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap\n-r--r----- 1 hanwen primarygroup 27621579 Jul 31 15:20\nroaring-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap\n\n-r--r----- 1 hanwen primarygroup 1037356 Jul 31 14:46\newah-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap\n-r--r----- 1 hanwen primarygroup 1242608 Jul 31 14:45\nroaring-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap\n\n-- \nHan-Wen Nienhuys - Google Munich\nI work 80%. Don't expect answers from me on Fridays.\n--\nGoogle Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich\nRegistergericht und -nummer: Hamburg, HRB 86891\nSitz der Gesellschaft: Hamburg\nGeschäftsführer: Paul Manicle, Liana Sebastian\n"},{"id":"480011","messageId":"ZMgXBc5idN+sR3o1@nand.local","threadId":"59460","inReplyTo":"CAFQ2z_P2HkT8grAFk=6Mr05rJRfsh_sXypVFPyHr0v5xkcjYTA@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-07-31T20:18:13Z","receivedAt":"2023-07-31T20:18:18Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Jul 31, 2023 at 07:46:18PM +0200, Han-Wen Nienhuys wrote:\n> On Sat, Mar 25, 2023 at 6:40 PM Jakub Narębski wrote:\n> > >>> Abhradeep promised[1] that he'd include some performance work in his\n> > >>> next version of that series. I think the main things we'd be interested\n> > >>> in are:\n> > >>>\n> > >>> - Does using Roaring provide a file-size advantage over\n> > >>> EWAH-compressed bitmaps?\n>\n> I modified JGit to write Roaring bitmaps instead of EWAH bitmaps. The\n> resulting difference in file sizes are small, and actually favor EWAH:\n>\n> $ ls -l {ewah-repos,roaring-repos}/*.git/objects/pack/*.bitmap\n> -r--r----- 1 hanwen primarygroup 26257386 Jul 31 15:04\n> ewah-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap\n> -r--r----- 1 hanwen primarygroup 27621579 Jul 31 15:20\n> roaring-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap\n>\n> -r--r----- 1 hanwen primarygroup 1037356 Jul 31 14:46\n> ewah-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap\n> -r--r----- 1 hanwen primarygroup 1242608 Jul 31 14:45\n> roaring-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap\n\nThis was one of my hopes with Roaring+Run, too, but I think that it's a\nnon-starter with our current object ordering for reachability bitmaps.\n\nI did the same experiment a few months ago in my fork of git.git, and\nconsistently was able to produce smaller bitmaps when EWAH compressed as\ncompared to Roaring+Run. I think the reason is that our bitmaps are\npretty sparse, and so often have a lot of 0's, interspersed with a few\n1's.\n\nDepending on container alignment, a single 1's bit surrounded by zeros\nwill often get encoded as a length 0 \"run\" container. This means that\ninstead of storing that information in a single bit like we would with\nEWAH, we use two 16-bit unsigned values to store (a) the position[^1],\nand (b) length of the run.\n\nThe length is entirely wasted space, since the bytes are zeros, and\nstoring the position is significantly less efficient than storing a\nsparse bit position in EWAH.\n\nI haven't proved conclusively one way or the other where Roaring+Run is\nsignificantly faster than EWAH or vice-versa. There are some cases where\nthe former is a clear winner, and other cases where it's the latter.\n\nIn any event, my extremely WIP patches to make this mostly work are\navailable here:\n\n https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n\nOne thing that I was able to do to produce slightly smaller Roaring+Run\nencoded .bitmap files is to store some of the bitmaps as XORs against\nearlier bitmaps, similar to what we do with EWAH. Often XORing the raw\nbits, and then compressing that with Roaring+Run can be significantly\nsmaller than storing another full Roaring+Run bitset.\n\nThat's the only part that I've had trouble getting to make it\nconsistently work, and I haven't had time to get back to it, so it's\nbeen collecting dust since the end of May.\n\nThanks,\nTaylor\n\n[^1]: Not the bit position, exactly, but rather the 16 least-significant\n bits of the bit position, since all values in the same container share\n the 16 most-significant bits being a multiple of 2^16.\n"},{"id":"480038","messageId":"CAFQ2z_MzWauauzq_fKdcKTXahutLtADb7uHTh7ysinGNOx75nQ@mail.gmail.com","threadId":"59460","inReplyTo":"ZMgXBc5idN+sR3o1@nand.local","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2023-08-01T11:26:19Z","receivedAt":"2023-08-01T11:26:51Z","isPatch":false,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau wrote:\n> I haven't proved conclusively one way or the other where Roaring+Run is\n> significantly faster than EWAH or vice-versa. There are some cases where\n> the former is a clear winner, and other cases where it's the latter.\n>\n> In any event, my extremely WIP patches to make this mostly work are\n> available here:\n>\n> https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n>\n\nthanks. For anyone reading along, the changes to JGit are here\n\nhttps://git.eclipse.org/r/c/jgit/jgit/+/203448\n\nI was looking into this because I was hoping that roaring might\ndecrease peak memory usage.\n\nI don't have firm evidence that it's better or worse, but I did\nobserve that runtime and memory usage during GC (which is heavy on\nbitmap operations due to delta/xor encoding) was unchanged. That makes\nme pessimistic that there are significant gains to be had.\n\n> One thing that I was able to do to produce slightly smaller Roaring+Run\n\nJust for my edification: what is \"Roaring + Run\" ?\n\n--\nHan-Wen Nienhuys - Google Munich\nI work 80%. Don't expect answers from me on Fridays.\n--\nGoogle Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich\nRegistergericht und -nummer: Hamburg, HRB 86891\nSitz der Gesellschaft: Hamburg\nGeschäftsführer: Paul Manicle, Liana Sebastian\n"},{"id":"480039","messageId":"CANQwDwe8Po-2KxNjWQ+RW+hYGLF=4sYTjQJxcVSAOtbtpfVRhQ@mail.gmail.com","threadId":"59460","inReplyTo":"CAFQ2z_MzWauauzq_fKdcKTXahutLtADb7uHTh7ysinGNOx75nQ@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2023-08-01T11:34:32Z","receivedAt":"2023-08-01T11:35:16Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nOn Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys wrote:\n> On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau wrote:\n> >\n> > I haven't proved conclusively one way or the other where Roaring+Run is\n> > significantly faster than EWAH or vice-versa. There are some cases where\n> > the former is a clear winner, and other cases where it's the latter.\n> >\n> > In any event, my extremely WIP patches to make this mostly work are\n> > available here:\n> >\n> > https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n> >\n>\n> thanks. For anyone reading along, the changes to JGit are here\n>\n> https://git.eclipse.org/r/c/jgit/jgit/+/203448\n>\n> I was looking into this because I was hoping that roaring might\n> decrease peak memory usage.\n>\n> I don't have firm evidence that it's better or worse, but I did\n> observe that runtime and memory usage during GC (which is heavy on\n> bitmap operations due to delta/xor encoding) was unchanged. That makes\n> me pessimistic that there are significant gains to be had.\n\nThe major advantage Roaring bitmaps have over EWAH and other\nsimple Run Length Encoding based compression algorithms is that\nbitmap operations can be done on compressed bitmaps: there is no\nneed to uncompress bitmap to do (want1 OR want2 AND NOT have).\n\nIf I remember correctly, Git (the C implementation) basically un-compresses\nbitmaps to make use of them when using them during fetch.\n\nSome operations can be done on EWAH without decompression, but\nnon-symmetric full-bitmap operation line AND NOT is not one of them.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"480040","messageId":"CAFQ2z_MmUDMTc7wyR1X8oxXdtz54_0HZmS2Q8iv9YMoqZmh0hQ@mail.gmail.com","threadId":"59460","inReplyTo":"CANQwDwe8Po-2KxNjWQ+RW+hYGLF=4sYTjQJxcVSAOtbtpfVRhQ@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2023-08-01T11:54:11Z","receivedAt":"2023-08-01T11:54:28Z","isPatch":false,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"On Tue, Aug 1, 2023 at 1:35 PM Jakub Narębski wrote:\n>\n> Hello,\n>\n> On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys wrote:\n> > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau wrote:\n> > >\n> > > I haven't proved conclusively one way or the other where Roaring+Run is\n> > > significantly faster than EWAH or vice-versa. There are some cases where\n> > > the former is a clear winner, and other cases where it's the latter.\n> > >\n> > > In any event, my extremely WIP patches to make this mostly work are\n> > > available here:\n> > >\n> > > https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n> > >\n> >\n> > thanks. For anyone reading along, the changes to JGit are here\n> >\n> > https://git.eclipse.org/r/c/jgit/jgit/+/203448\n> >\n> > I was looking into this because I was hoping that roaring might\n> > decrease peak memory usage.\n> >\n> > I don't have firm evidence that it's better or worse, but I did\n> > observe that runtime and memory usage during GC (which is heavy on\n> > bitmap operations due to delta/xor encoding) was unchanged. That makes\n> > me pessimistic that there are significant gains to be had.\n>\n> The major advantage Roaring bitmaps have over EWAH and other\n> simple Run Length Encoding based compression algorithms is that\n> bitmap operations can be done on compressed bitmaps: there is no\n> need to uncompress bitmap to do (want1 OR want2 AND NOT have).\n\nAre you sure? The source code for and and andNot look rather similar\nin that they seem to do operations on whole RLE sections at a time,\n\nhttps://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L498\n\nhttps://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L405\n\nLooking at the EWAH format as documented for git-bitmap-format, EWAH\nallows for RLE on both 1s and 0s. It should be possible to efficiently\nclear out a section of the target if the second operand of andNot has\nRLE encoded run of 1s.\n\n-- \nHan-Wen Nienhuys - Google Munich\nI work 80%. Don't expect answers from me on Fridays.\n--\n\nGoogle Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich\n\nRegistergericht und -nummer: Hamburg, HRB 86891\n\nSitz der Gesellschaft: Hamburg\n\nGeschäftsführer: Paul Manicle, Liana Sebastian\n"},{"id":"480041","messageId":"CANQwDwf6x9yZgBLkSLun3pFaGpy4NC0RwYbid2L5wC6=Z9peww@mail.gmail.com","threadId":"59460","inReplyTo":"CAFQ2z_MmUDMTc7wyR1X8oxXdtz54_0HZmS2Q8iv9YMoqZmh0hQ@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2023-08-01T13:17:09Z","receivedAt":"2023-08-01T13:18:07Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nOn Tue, 1 Aug 2023 at 13:54, Han-Wen Nienhuys wrote:\n> On Tue, Aug 1, 2023 at 1:35 PM Jakub Narębski wrote:\n> > On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys wrote:\n> > > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau wrote:\n> > > >\n> > > > I haven't proved conclusively one way or the other where Roaring+Run is\n> > > > significantly faster than EWAH or vice-versa. There are some cases where\n> > > > the former is a clear winner, and other cases where it's the latter.\n> > > >\n> > > > In any event, my extremely WIP patches to make this mostly work are\n> > > > available here:\n> > > >\n> > > > https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n> > > >\n> > >\n> > > thanks. For anyone reading along, the changes to JGit are here\n> > >\n> > > https://git.eclipse.org/r/c/jgit/jgit/+/203448\n> > >\n> > > I was looking into this because I was hoping that roaring might\n> > > decrease peak memory usage.\n> > >\n> > > I don't have firm evidence that it's better or worse, but I did\n> > > observe that runtime and memory usage during GC (which is heavy on\n> > > bitmap operations due to delta/xor encoding) was unchanged. That makes\n> > > me pessimistic that there are significant gains to be had.\n> >\n> > The major advantage Roaring bitmaps have over EWAH and other\n> > simple Run Length Encoding based compression algorithms is that\n> > bitmap operations can be done on compressed bitmaps: there is no\n> > need to uncompress bitmap to do (want1 OR want2 AND NOT have).\n>\n> Are you sure? The source code for and and andNot look rather similar\n> in that they seem to do operations on whole RLE sections at a time,\n>\n> https://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L498\n>\n> https://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L405\n>\n> Looking at the EWAH format as documented for git-bitmap-format, EWAH\n> allows for RLE on both 1s and 0s. It should be possible to efficiently\n> clear out a section of the target if the second operand of andNot has\n> RLE encoded run of 1s.\n\nYou are right, I seem to have misremembered the statement from the\nEWAH paper.\n\nLemma 2 in \"Sorting improves word-aligned bitmap indexes\" (arXiv:0901.3751v7)\nstates that the bitmap operation of L bitmaps is computable in\nO(L*compressed size),\nand for updatable L-ary operation like symmetric boolean operation\nthe bitmap operation is computable in O(log(L)*compressed size).\n\nNow I am not sure if I understand the code of Git correctly, but it seems like\nin pack-bitmap.c the `add_commit_to_bitmap()` function stores the result\nof OR operation on bitmaps as an uncompressed bitmap:\nhttps://github.com/git/git/blob/master/pack-bitmap.c#L1030\n\nBest,\n-- \nJakub Narębski\n"},{"id":"480056","messageId":"ZMlBdb5jEW3s7UWX@nand.local","threadId":"59460","inReplyTo":"CAFQ2z_MzWauauzq_fKdcKTXahutLtADb7uHTh7ysinGNOx75nQ@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-01T17:31:33Z","receivedAt":"2023-08-01T17:31:38Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Aug 01, 2023 at 01:26:19PM +0200, Han-Wen Nienhuys wrote:\n> > One thing that I was able to do to produce slightly smaller Roaring+Run\n>\n> Just for my edification: what is \"Roaring + Run\" ?\n\nRoaring+Run refers to a modified version of the Roaring bitset\ncompression scheme which has an additional container type to represent\nruns of a single (set) bit.\n\nThe run container stores the lower 16-bits of bit position of the start\nof the run, and then it uses another 16-bit value to store the length of\nthe run.\n\nFor more, this paper from David Lemire is a good start:\n\n https://arxiv.org/pdf/1402.6407.pdf\n\nThanks,\nTaylor\n"},{"id":"480057","messageId":"ZMlCB/Pkzlb7Wvq5@nand.local","threadId":"59460","inReplyTo":"CANQwDwe8Po-2KxNjWQ+RW+hYGLF=4sYTjQJxcVSAOtbtpfVRhQ@mail.gmail.com","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-01T17:33:59Z","receivedAt":"2023-08-01T17:34:05Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Aug 01, 2023 at 01:34:32PM +0200, Jakub Narębski wrote:\n> Hello,\n>\n> On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys wrote:\n> > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau wrote:\n> > >\n> > > I haven't proved conclusively one way or the other where Roaring+Run is\n> > > significantly faster than EWAH or vice-versa. There are some cases where\n> > > the former is a clear winner, and other cases where it's the latter.\n> > >\n> > > In any event, my extremely WIP patches to make this mostly work are\n> > > available here:\n> > >\n> > > https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n> > >\n> >\n> > thanks. For anyone reading along, the changes to JGit are here\n> >\n> > https://git.eclipse.org/r/c/jgit/jgit/+/203448\n> >\n> > I was looking into this because I was hoping that roaring might\n> > decrease peak memory usage.\n> >\n> > I don't have firm evidence that it's better or worse, but I did\n> > observe that runtime and memory usage during GC (which is heavy on\n> > bitmap operations due to delta/xor encoding) was unchanged. That makes\n> > me pessimistic that there are significant gains to be had.\n>\n> The major advantage Roaring bitmaps have over EWAH and other\n> simple Run Length Encoding based compression algorithms is that\n> bitmap operations can be done on compressed bitmaps: there is no\n> need to uncompress bitmap to do (want1 OR want2 AND NOT have).\n\nYeah, this is definitely where the majority of CPU savings seems to\nremain. The existing implementation in my branch is much too eager to\nuncompress bitmaps when we need to perform a logical/binary operation on\nthem.\n\nI think with some more surgery we could leave bitmaps in a compressed\nstate for longer. I am not sure whether or not we should ever uncompress\nthe bitmaps, though it's possible that doing so is beneficial since\nuncompressed bitmaps have better query performance (albeit more costly\nmemory usage).\n\nThanks,\nTaylor\n"},{"id":"480059","messageId":"CANQwDwdXoO4BeSzCCedC9VnPoJV-eHSr18YJeAeG2Gvj9-__zQ@mail.gmail.com","threadId":"59460","inReplyTo":"ZMlCB/Pkzlb7Wvq5@nand.local","subject":"Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2023-08-01T17:43:36Z","receivedAt":"2023-08-01T17:44:24Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello\n\nOn Tue, 1 Aug 2023 at 19:34, Taylor Blau wrote:\n> On Tue, Aug 01, 2023 at 01:34:32PM +0200, Jakub Narębski wrote:\n> > On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys wrote:\n> > > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau wrote:\n> > > >\n> > > > I haven't proved conclusively one way or the other where Roaring+Run is\n> > > > significantly faster than EWAH or vice-versa. There are some cases where\n> > > > the former is a clear winner, and other cases where it's the latter.\n> > > >\n> > > > In any event, my extremely WIP patches to make this mostly work are\n> > > > available here:\n> > > >\n> > > > https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps\n> > > >\n> > >\n> > > thanks. For anyone reading along, the changes to JGit are here\n> > >\n> > > https://git.eclipse.org/r/c/jgit/jgit/+/203448\n> > >\n> > > I was looking into this because I was hoping that roaring might\n> > > decrease peak memory usage.\n> > >\n> > > I don't have firm evidence that it's better or worse, but I did\n> > > observe that runtime and memory usage during GC (which is heavy on\n> > > bitmap operations due to delta/xor encoding) was unchanged. That makes\n> > > me pessimistic that there are significant gains to be had.\n> >\n> > The major advantage Roaring bitmaps have over EWAH and other\n> > simple Run Length Encoding based compression algorithms is that\n> > bitmap operations can be done on compressed bitmaps: there is no\n> > need to uncompress bitmap to do (want1 OR want2 AND NOT have).\n>\n> Yeah, this is definitely where the majority of CPU savings seems to\n> remain. The existing implementation in my branch is much too eager to\n> uncompress bitmaps when we need to perform a logical/binary operation on\n> them.\n\nAs I understand it, the current code in Git (in C implementation) uses\nuncompressed bitmap to store the result of OR-ing, but it uses compressed\nEWAH to perform OR .\n\n> I think with some more surgery we could leave bitmaps in a compressed\n> state for longer. I am not sure whether or not we should ever uncompress\n> the bitmaps, though it's possible that doing so is beneficial since\n> uncompressed bitmaps have better query performance (albeit more costly\n> memory usage).\n\nI'm not sure if it would be worth the complexity, but supposedly you can\nperform L bitwise OR operations in O(log(L)) instead of O(L). Current C code\ncomputes OR operation sequentially, see above, and also\n https://github.com/git/git/blob/master/pack-bitmap.c#L103\\0\n\nThere might be thousands of \"wants\" and of \"haves\", but is it common?\n\nBest,\n-- \nJakub Narębski\n"}]}