{"thread":{"id":"57681","subject":"[GSoC][RFC][PROPOSAL] Reachability bitmap improvements","startedAt":"2022-04-06T21:15:57Z","lastAt":"2022-04-15T05:29:29Z","messageCount":5,"participants":["Abhradeep Chakraborty","Taylor Blau","Philip Oakley"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"453222","messageId":"20220406200440.27010-1-chakrabortyabhradeep79@gmail.com","threadId":"57681","inReplyTo":null,"subject":"[GSoC][RFC][PROPOSAL] Reachability bitmap improvements","fromName":"Abhradeep Chakraborty","fromEmail":"chakrabortyabhradeep79@gmail.com","sentAt":"2022-04-06T20:04:40Z","receivedAt":"2022-04-06T21:15:57Z","isPatch":false,"sender":{"key":"chakrabortyabhradeep79@gmail.com","avatar":"https://avatars.githubusercontent.com/u/75240995?v=4"},"body":"Hello everyone,\n\nHere is the initial version of my proposal on \"Reachability bitmap\nimprovements\". I would really love to have comments on it. If you\nfind any mistakes please notify me about that.\n\nThe proposal template is inspired by Hariom Verma's (This year's\nGSoC mentor) previous year's gsoc proposal.\n\nThanks :)\n\n=============================================\n\nView on Docs: https://docs.google.com/document/d/15tZ5QbMtYN41No5wdMw-2Ilp63vquB7OqAwBCLl_0n0/edit?usp=sharing\n\n==============================================\n\n**Reachability bitmap improvements**\n\nName  :  Abhradeep Chakraborty\nMajor : Information Technology\nMobile No. : [ ... ]\nEmail : chakrabortyabhradeep79@gmail.com\nGitHub Profile: (Abhra303)[https://github.com/Abhra303]\nLinkedIn : www.linkedin.com/in/abhradeep-chakraborty-b36426201\nTime Zone : Indian Standard Time ( IST ) ( UTC +05:30 )\n\n## About Me\n\nI am Abhradeep Chakraborty, currently pursuing B.Tech in Information\nTechnology (now in my 3rd year) at Jalpaiguri Government Engineering\nCollege, India.\n\nIn the last two years, I mainly concentrated on learning and building\nweb development things. I mainly use Django, React for my projects. But\nfor the past 6 months, I have been learning about devops, cloud technologies\n( e.g. docker, Kubernetes, AWS etc.), computer networking and core\ntechnologies (such as git, linux, gcc etc.). I also have an interest in\nsome research based technologies like WebRTC, Web3 etc.\n\nMy ultimate objective is to be a dedicated and active contributor to all\nof these technologies. So, I want to start this contribution journey with\n`git` and therefore I want to be a part of this GSoC program.\n\n## Me & Git\n\nI have started exploring the Git codebase since Sept 2021. At first, I\nmainly focused on knowing the git internals. During this time I read\ndocumentations (Under `Documentation` directory). `MyFirstContribution.txt`[1],\n`MyFirstObjectWalk.txt`[2] and `Hacking Git`[3] helped me to learn about the git\ncontribution workflow, how `git log` ( in other words `object walk`) works\ninternally.\n\nThough I had read many documentations, I was still not able to fully\nunderstand the terminologies (like `refs`, `packfiles`, `blobs`, `trees`\netc.). (ProGit)[https://git-scm.com/book/en/v2] helped me tremendously here.\nI read the full book and it cleared almost every doubt that came into my mind.\n\nI have provided my git involvement history below. Activities are sorted\nby timeline from top to bottom.\n\n==============================\nPRs, Commits & Discussion Participations\n==============================\n\n---------------------------------\n[patch] Amend error messages that violate git coding style convention\nGithub link : https://github.com/gitgitgadget/git/pull/1062\nStatus : Not Merged/ PR\nDescription : There are many error strings which do not follow coding\nstyle guides. This PR was to fix those. There is a ticket dedicated to\nthis ( github Issue - (#635)[https://github.com/gitgitgadget/git/issues/635]).\nThe author of this issue said it would be better to manually correct\nthese things.\nOutcome : As this was my first PR, I made many mistakes and I faced\ndifficulties. Though this was not merged, I learned tremendous new\nthings. These violating strings were in many files ( nearly 200 files).\nAt first, I fixed all the files at once manually. I fixed errors\ngenerated by those changes. Ultimately, I learned about overall git\nstructures, how to fix errors etc.\n\n---------------------------------\n[RFC PATCH 0/1] making set-upstream have default arguments\nMailing List : https://lore.kernel.org/git/20211202144354.17416-1-chakrabortyabhradeep79@gmail.com/\nStatus : Not Merged/ Closed\nDescription : `git push -u` generally ( if `push.default` not set)\nthrows an error if no arguments are provided. This patch request was to\nteach `git push -u` to push and set a default upstream if no arguments\nare provided. There is a github (issue)[https://github.com/gitgitgadget/git/issues/1061]\nalso.\nOutcome : This PR let `git push -u` to push to a default branch and\nset that as the upstream irrespective of `push.default` configuration.\nI realized it was badly affecting the reason `push.default` is built\nfor ( See this (comment)[https://lore.kernel.org/git/20220104132839.1209-1-chakrabortyabhradeep79@gmail.com/]).\nSo, I intentionally stopped working on it.\n\n----------------------------------\nAvoid checking for -h in commands that already use parse-options API ( Issue)\nGithub Issue Link : https://github.com/gitgitgadget/git/issues/1125\nStatus : Closed\n\n----------------------------------\n[PATCH] Add usage strings ci check and amend remaining usage strings\nGithub PR Link : https://github.com/gitgitgadget/git/pull/1147\nMailing List Link : https://lore.kernel.org/git/pull.1147.git.1645030949730.gitgitgadget@gmail.com/\nStatus : Merged into Master\nDescription : According to dscho’s (comment)[https://github.com/gitgitgadget/git/issues/636#issuecomment-1018660439],\nThere were still some usage strings that violated the style guide.\nSo, this patch request fixed those strings and added a CI check to\nverify all the usage strings are passing the style check. In the first\nversion, I built a shell script to check the validity of strings.\nOutcome : The first commit was merged into master. There were some\ncontradictions about the different approaches suggested by reviewers\nin the discussion about the last commit i.e. whether the check should\nbe static check or runtime check, whether I should use `parse options`\nmethod or coccinelle etc (see the (mailing list)[https://lore.kernel.org/git/nycvar.QRO.7.76.6.2202251632320.11118@tvgsbejvaqbjf.bet/]).\nLastly, it was decided that I should try the `coccinelle` method first\nand check if it is better ( see this (comment)[https://lore.kernel.org/git/20220304142154.2350-1-chakrabortyabhradeep79@gmail.com/]).\nI will try to submit a PR regarding this before April 19.\n\n==================================\nMicroProject\n==================================\n\n[PATCH] Partial-Clone : add a partial-clone test case\nGithub PR Link : https://github.com/gitgitgadget/git/pull/1175\nStatus : Merged into Master\nGithub Issue : https://github.com/gitgitgadget/git/issues/827\nDescription : In a blobless-cloned repo, `git log –follow – <path>`\n(`<path>` have an exact OID rename) shouldn’t download blobs of the\nfile from where the new file is renamed. This patch added a test case\nto verify it.\nOutcome : The test was added to the master branch. Moreover, another\nissue was discovered while discussing the patch request. Junio discovered\nthat the test helper function `test_subcommand_inexact` was poorly designed.\nLater Derrick submitted a (PR)[https://github.com/gitgitgadget/git/pull/1185]\nto fix it ( now merged).\n\n==================================\nReview\n==================================\n[PATCH] test-lib-functions : fix test_subcommand_inexact\nGithub PR Link : https://github.com/gitgitgadget/git/pull/1185\nDescription : Junio discovered that the `test_subcommand_inexact` function\n(test-helper function) is poorly designed. This PR addresses that.\nMy comment : Though I placed it under the `Review` section; but I didn’t\nreview the code here. Instead I gave my opinion regarding this in\n(this comment)[https://lore.kernel.org/git/20220324181056.53824-1-chakrabortyabhradeep79@gmail.com/].\n\n## Proposed Project\n\n### Abstract\n\nWhile sending large repositories, git has to decide what needs to be\nsent, how to be sent. For large repositories, git creates pack files\nwhere it packs all the related commits, trees, blobs( in the form of\ndeltas and bases ), tags etc. Now, finding the related objects among\nall the objects might be very expensive.\n\nAs git only knows about the branch tips, it is very expensive to find\nthe related objects from all the objects if we try to traverse down\nfrom the branch tips to all their respective related objects. It becomes\nmore expensive as the number of objects (i.e. commits, trees, blobs\netc.) increases. Ultimately resulting in slow fetching from the git\ndaemon.\n\nTo counter that, reachability bitmaps were introduced. It uses bitmap\ndata structure (an array of bits) to detect if an object is reachable\nfrom a particular commit or not. The commit messages of this\n(patch series)[https://lore.kernel.org/git/1372116193-32762-1-git-send-email-tanoku@gmail.com/]\nare itself a documentation of how it is achieved. All the bitmap\nindexes for selected commits (in a EWAH compressed form) are stored in\na `.bitmap` file which has the same name of its respective packfile.\n\nThe current task is to improve the performance of this bitmap approach.\nThere are three points that we need to work on -\n\n1. Decompression of bitmaps is slow with EWAH. To know if an object is\n   related to a particular commit, we have to decompress the whole thing.\n   So, we have to consider other alternative techniques besides EWAH.\n\n2. Loading a `.bitmap` file can be slow for large bitmaps. This is because\n   we need to read the file sequentially in order to discover the offset of\n   each bitmap within the file. It would be better if we can create a `table\n   of contents` for these bitmaps.\n\n3. Regenerating bitmaps can take a long time. One possible approach is to\n   add a new mode which only adds new bitmaps for commits introduced between\n   successive bitmap generations.\n\n4. If we solve the above points, we would think of other aspects like\n   rethinking how we select which commit receives bitmaps etc.\n\n### Previous Work\n\nI didn’t find any previous patches regarding point no. 1. But there were\nsome discussions about this. Derrick’s\n(comment)[https://lore.kernel.org/git/1685a358-f033-64e0-2e12-df3a1c10af19@gmail.com/]\nsuggested considering the\n(Roaring+Run)[https://roaringbitmap.org/about/]\ntechnique. It is much faster than the currently implemented\n(EWAH)[https://arxiv.org/abs/0901.3751].\n\nTaylor initiated the `developing a table of contents for bitmap` work\nby creating a\n(branch and committing some patches)[https://github.com/git/git/compare/master...ttaylorr:tb/bitmap-commit-table]\nin that branch. From the\n(discussion)[https://lore.kernel.org/git/YNuiM8TR5evSeNsN@nand.local/]\nand the performance test results provided in that discussion,  it seems\nthat it would improve overall performance. So, this would work as a\nreference for me while developing the table of contents for bitmaps\n(obviously after running performance tests and discussing the best\napproach).\n\n### Potential Problem\n\nThe biggest difficulty of this project would be to replace the EWAH\ncompression/decompression altogether with better techniques like the\nRoaring+Run method. I have to be aware of it so that it doesn’t\ngenerate any unintentional behavior or bugs.\n\n### The plan\n\nAs this project includes three ( actually four) sub projects, I would\naddress them one by one -\n1. Firstly I will understand the working of EWAH compression better.\n   I have gone through their documentation and have seen git’s\n   implementation code for it. The commit messages were really helpful\n   here. But I think I should research more. After that,  I can compare\n   (and discuss) each approach with respect to the EWAH approach on\n   some parameters (like amount of computation in each approach,\n   simplicity, memory usage, correctness i.e. does it always give the\n   correct output etc.). This comparison would lead me to take the\n   most ideal approach in this case. There are several techniques which\n   may work/perform better than the current EWAH implementation. I\n   have researched some of these techniques. One of them is obviously\n   the Roaring+Run method. I have gone through their\n   (research paper)[https://arxiv.org/pdf/1709.07821v6.pdf]\n   on this technique; it seems like a good approach to me. Other than\n   that, there is a golang package called\n   (sroar)[https://dgraph.io/blog/post/serialized-roaring-bitmaps-golang/]\n   (i.e. Serialized Roaring bitmaps), which is an open source package\n   ( mainly built for (Dgraph)[https://dgraph.io/])\n   and the creator of this package claims it is\n   (7x faster using 15x less memory)[https://github.com/dgraph-io/sroar#benchmarks].\n   It doesn’t require any encoding/decoding step. I would look into\n   it ( It needs to be implemented in C language though). I have also\n   looked into approaches like\n   (bloom filter)[https://en.wikipedia.org/wiki/Bloom_filter],\n   (Hyperloglog)[https://en.wikipedia.org/wiki/HyperLogLog]. These are\n   very fast and use very less memory. But they give probabilistic\n   answers and sometimes they may give wrong answers. So, those\n   would not be a good fit for us I guess.\n2. I will understand the bitmap related files such as\n   `pack-bitmap-write.c`[4], `pack-bitmap.c`[5] etc. It would\n   help me to decide where and how I can add the code related to\n   `table of contents` for bitmap.\n   Taylor’s (branch work)[https://github.com/git/git/compare/master...ttaylorr:tb/bitmap-commit-table]\n   would work as a reference for me. As the Project idea section\n   suggests, I would also include performance tests to continuously\n   check whether my approach is really improving the performance or\n   not.\n3. As I understand more about bitmap related files, I will surely\n   be able to think whether `adding a new mode` is really necessary\n   or not (It is conceptually a good idea though). If necessary,\n   then I would first make the flow design and discuss it with the\n   community. If all is good, I will start working on it. Creating\n   and running performance tests is a must.\n4. While developing all of these, my understanding of bitmap and\n   its implementation will get better. So, that would help me to\n   think more practically about the questions provided in the `Project\n   Idea` section. Then I would work on it accordingly.\n\n## Estimated Timeline\n\nMy Semester exams will most probably start from May last week. So,\nI may be inactive (or less active) that time.\n(Smart India Hackathon)[https://www.sih.gov.in]\n(semi finals and finals) may also be held during the GSoC event.\nI will get you notified about that.\n\n--> Period\n- Pre GSoC Period\n- Till May 20\n--> Tasks\n- Research more on the bitmap files, compression techniques etc.\n- See if there are any other (better) techniques for it.\n\n--> Period\n- Community Bonding\n- May 20 - June 12\n--> Tasks\n- Discussion on the project started\n- Decide which approach is better for compression/decompression of\n  bitmaps.\n- If a decision is not taken, create branches for each approach.\n- Create branches for each sub project and make skeletons for them.\n\n--> Period\n- Coding Phase 1\n- June 13 - July 25\n--> Tasks\n- Start working on sub-project no. 1 (i.e. bitmap compression\n  technique)\n- Add Performance test\n- If multiple branch are create for this sub-project, compare\n  the test results\n- Take the best performing approach, delete other branches.\n- Update documentation accordingly\n- Fix bugs\n- Finish sub-project 1\n\n--> Period\n- Coding Phase 2\n- July 25 - Sept 4\n--> Tasks\n- Fix sub-project-1 related small bugs\n- Start working on sub-project-2 (i.e. adding\n  `table of content` for bitmap files)\n- Add Performance test\n- Add Documentation\n- Fix bugs\n- If finished, start working on sub-project-3 (i.e. adding a\n  `new mode`)\n- Try to finish it with documentation and performance tests\n\n--> Period\n- Final Week 1\n- Sept 5 - Sept 12\n--> Tasks\n- If both are finished, fix bugs and test overall performance.\n  Else extend the period.\n- Discuss about the last sub project (i.e. questions )\n- If anything needs to be changed/modified or added, extend the\n  GSoC Period\n\n--> Period\n- Coding Phase 3\n- Sept 13 - Nov 13\n--> Tasks\n- Finish code related to all sub projects\n- Add overall documentation\n- Add overall performance tests\n\n\n## Blogging about Git\n\nI love to write blogs and technical articles. Those are my ways to\nconnect and communicate with the developers community. I have\npreviously written articles about Django in a portal named\n(GeeksForGeeks)[https://auth.geeksforgeeks.org/user/riter79/articles].\nRecently I started writing  blogs on\n(Medium platform)[https://medium.com/@abhra303].\n\nDuring the GSoC event, I will frequently write blogs about my\nprogress. I will also share the problems I face and the solutions\nof those problems that I consider.\n\nI got interested in git by reading Olga’s GSoC blogs. That led me\nto contribute to this codebase. So, someone like me will hopefully\nbe motivated by seeing my blogs ;-)\n\n## Availability\n\nI intentionally freed my summer slot for GSoC. So, there wouldn’t\nbe much disturbance/inactive days while working on my project.\nGenerally, I can spend nearly 35-40 hours a week on this project.\nIf the college gets closed for some reason, then the amount of\navailable time will increase. Smart India Hackathon finale would\nbe held in July. So, I may be inactive for a few days. But overall,\nI will be available most of the time.\n\n## Post GSoC\n\nOnce the GSoC finishes, I would look into other issues/tickets and\nwould send PRs solving those issues. As I said before, I want to\nbe a long term contributor to git - I would definitely maintain the\nflow and continue to work on improving the overall git tool.\n\n## Experience with Open Source\n\nI have a pretty good contribution history in open source. The\norganizations/tools where I contributed to are - \n\n - Mozilla/bedrock - written mainly in Python Django and javaScript\n   link - https://github.com/mozilla/bedrock/commits?author=Abhra303\n\n - Datree - a Kubernetes misconfiguration checker tool written mainly\n   in golang\n   link - https://github.com/datreeio/datree/commits?author=Abhra303\n\n - KubeBuilder - A tool to extend the Kubernetes API by creating custom\n   CRDs - written mainly in golang. I recently started looking into it.\n   link : https://github.com/kubernetes-sigs/kubebuilder/issues/2567\n\n## Motivation\n\nI always wanted to develop/contribute to projects that affect millions\nof people. Git is a tool that most ( or maybe every) developers\nuse for their daily work. Contributing to it means my written code\nwill be used behind the scenes in every developer’s machine. That’s my\nmotivation.\n\n## Closing Remarks\n\nLastly, I want to say that I am a dedicated, research preferred quick\nlearner. I am always ready to solve real world problems and learn\nrequired skills for them. For example, I recently took part in a\nhackathon called “Cloud Native Hackathon” and won 1st place in the\ncategory of “best use of Datree”. I knew nothing about\n(Datree)[https://datree.io/] ( and (Kubernetes)[https://kubernetes.io]\npartially) before this hackathon and the hackathon was only 2 days\nlong. But I researched hard ( to know the Kubernetes misconfigurations)\nand learned  jsonSchema ( Here is my\n(blog link)[https://medium.com/@abhra303/how-i-won-cloud-native-hackathon-2021-4b1f5b2a84f2]\nif you want to know my full experience).\n\nI hope you’ll give me a chance to make an impact among the developers\ncommunity by considering my application.\n\nThanks & Regards,\n\nAbhradeep Chakraborty\n\n\n\n[1] https://github.com/gitgitgadget/git/blob/master/Documentation/MyFirstContribution.txt\n[2] https://github.com/gitgitgadget/git/blob/master/Documentation/MyFirstObjectWalk.txt\n[3] https://git-scm.com/docs/user-manual#hacking-git\n[4] https://github.com/git/git/blob/master/pack-bitmap-write.c\n[5] https://github.com/git/git/blob/master/pack-bitmap.c\n"},{"id":"453522","messageId":"YlckmDHRAYnE1J5t@nand.local","threadId":"57681","inReplyTo":"20220406200440.27010-1-chakrabortyabhradeep79@gmail.com","subject":"Re: [GSoC][RFC][PROPOSAL] Reachability bitmap improvements","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2022-04-13T19:29:28Z","receivedAt":"2022-04-13T19:29:45Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Abhradeep,\n\nOn Thu, Apr 07, 2022 at 01:34:40AM +0530, Abhradeep Chakraborty wrote:\n> Hello everyone,\n>\n> Here is the initial version of my proposal on \"Reachability bitmap\n> improvements\". I would really love to have comments on it. If you\n> find any mistakes please notify me about that.\n\nThanks so much for submitting this proposal! I have been excited to look\nthrough it, and am sorry for not getting to it sooner. Let me take a\nlook now and give some of my thoughts.\n\n> ## About Me\n>\n> I am Abhradeep Chakraborty, currently pursuing B.Tech in Information\n> Technology (now in my 3rd year) at Jalpaiguri Government Engineering\n> College, India.\n>\n> In the last two years, I mainly concentrated on learning and building\n> web development things. I mainly use Django, React for my projects. But\n> for the past 6 months, I have been learning about devops, cloud technologies\n> ( e.g. docker, Kubernetes, AWS etc.), computer networking and core\n> technologies (such as git, linux, gcc etc.). I also have an interest in\n> some research based technologies like WebRTC, Web3 etc.\n>\n> My ultimate objective is to be a dedicated and active contributor to all\n> of these technologies. So, I want to start this contribution journey with\n> `git` and therefore I want to be a part of this GSoC program.\n\nGreat! It sounds like working on Git would give you some new experience\nin a different domain than some of your past projects, and help you\nlearn more about how it works and is developed.\n\n> ## Me & Git\n>\n> I have started exploring the Git codebase since Sept 2021. At first, I\n> mainly focused on knowing the git internals. During this time I read\n> documentations (Under `Documentation` directory). `MyFirstContribution.txt`[1],\n> `MyFirstObjectWalk.txt`[2] and `Hacking Git`[3] helped me to learn about the git\n> contribution workflow, how `git log` ( in other words `object walk`) works\n> internally.\n>\n> Though I had read many documentations, I was still not able to fully\n> understand the terminologies (like `refs`, `packfiles`, `blobs`, `trees`\n> etc.). (ProGit)[https://git-scm.com/book/en/v2] helped me tremendously here.\n> I read the full book and it cleared almost every doubt that came into my mind.\n\nTerrific! I am really glad that the MyFirst... documents were helpful\nand made it easier for you to contribute. The ProGit book is a great\nresource, too.\n\nIf you are looking for more resources, I would encourage you to search\naround for blog posts written by Git contributors, particularly related\nto reachability bitmaps (at least for this GSoC project). Some helpful\nplaces to start there would be:\n\n    https://github.blog/2015-09-22-counting-objects/\n    https://github.blog/2021-04-29-scaling-monorepo-maintenance/\n\n> ## Proposed Project\n>\n> ### Abstract\n>\n> While sending large repositories, git has to decide what needs to be\n> sent, how to be sent. For large repositories, git creates pack files\n> where it packs all the related commits, trees, blobs( in the form of\n> deltas and bases ), tags etc. Now, finding the related objects among\n> all the objects might be very expensive.\n\nNote that commits and trees can be stored as deltas against other\ncommits and trees (which themselves might be packed as deltas) and so\non. But we only consider a pair of objects to be delta candidates for\none another when they share a common type (e.g., we would never delta a\ntree object against a blob or vice-versa).\n\n> As git only knows about the branch tips, it is very expensive to find\n> the related objects from all the objects if we try to traverse down\n> from the branch tips to all their respective related objects. It becomes\n> more expensive as the number of objects (i.e. commits, trees, blobs\n> etc.) increases. Ultimately resulting in slow fetching from the git\n> daemon.\n>\n> To counter that, reachability bitmaps were introduced. It uses bitmap\n> data structure (an array of bits) to detect if an object is reachable\n> from a particular commit or not. The commit messages of this\n> (patch series)[https://lore.kernel.org/git/1372116193-32762-1-git-send-email-tanoku@gmail.com/]\n> are itself a documentation of how it is achieved. All the bitmap\n> indexes for selected commits (in a EWAH compressed form) are stored in\n> a `.bitmap` file which has the same name of its respective packfile.\n\nExactly; though note that since that series we now have multi-pack\nbitmaps, too, which use a slightly different ordering called the\n\"pseudo-pack\" order, which (more or less) looks like all of the objects\nin a MIDX first sorted by which pack they came from, and then sorted by\ntheir order within the pack, removing duplicates in favor of the\n\"preferred\" pack.\n\nMore thorough documentation on this can be found in the\n\"multi-pack reverse indexes\" section of\n\"Documentation/technical/pack-format.txt\".\n\n> The current task is to improve the performance of this bitmap approach.\n> There are three points that we need to work on -\n>\n> 1. Decompression of bitmaps is slow with EWAH. To know if an object is\n>    related to a particular commit, we have to decompress the whole thing.\n>    So, we have to consider other alternative techniques besides EWAH.\n\nRight, we can't begin to interpret the bitmaps until after decompressing\nthem (ditto for operations that involve compressed bitmaps, e.g., we\ncan't OR two EWAH compressed bitmaps together without first\ndecompressing them).\n\nBut I want to be careful about the word \"slow\" here. They might be slow,\nor it might be really fast to decompress a given bitmap, depending on\nthe disk performance, CPU pressure, how large the bitmaps are, and so\non. So I think a good first step here is to validate our assumption that\nEWAH decompression is even slow to begin with.\n\n(Of course, the literature on newer formats will readily tell you that\nthe old stuff is slower, but I think it's worth reevaluating those\nstatements in the context of a practical application instead of in\ntheory / benchmarks).\n\n> 2. Loading a `.bitmap` file can be slow for large bitmaps. This is because\n>    we need to read the file sequentially in order to discover the offset of\n>    each bitmap within the file. It would be better if we can create a `table\n>    of contents` for these bitmaps.\n\nSame comments here about whether or not this is slow to begin with. From\nmy experimental patches in this area earlier, I found that we could get\na significant speed-up in some cases, but that the speed-up was\nbasically obliterated whenever we had to do any follow-on traversal if\nthe bitmap coverage wasn't completely up-to-date.\n\n> 3. Regenerating bitmaps can take a long time. One possible approach is to\n>    add a new mode which only adds new bitmaps for commits introduced between\n>    successive bitmap generations.\n\nDefinitely true. Another way to look at this is that it's now possible\nto do some \"incremental\" work as far as repacking a repository goes, but\nthat updating its bitmap is still much less \"incremental\" than it could\nbe.\n\n> 4. If we solve the above points, we would think of other aspects like\n>    rethinking how we select which commit receives bitmaps etc.\n\nArguably we could do this whether or not we solve the above, but doing\nsome combination of the above may make it easier (e.g., if we wanted to\nchange the bitmap selection to store dramatically more commits, then we\nmay want to investigate how much of a bottleneck the sequential read\nrequirement of .bitmap files would become for different numbers of\nselected commits).\n\n> ### Previous Work\n>\n> I didn’t find any previous patches regarding point no. 1. But there were\n> some discussions about this. Derrick’s\n> (comment)[https://lore.kernel.org/git/1685a358-f033-64e0-2e12-df3a1c10af19@gmail.com/]\n> suggested considering the\n> (Roaring+Run)[https://roaringbitmap.org/about/]\n> technique. It is much faster than the currently implemented\n> (EWAH)[https://arxiv.org/abs/0901.3751].\n>\n> Taylor initiated the `developing a table of contents for bitmap` work\n> by creating a\n> (branch and committing some patches)[https://github.com/git/git/compare/master...ttaylorr:tb/bitmap-commit-table]\n> in that branch. From the\n> (discussion)[https://lore.kernel.org/git/YNuiM8TR5evSeNsN@nand.local/]\n> and the performance test results provided in that discussion,  it seems\n> that it would improve overall performance. So, this would work as a\n> reference for me while developing the table of contents for bitmaps\n> (obviously after running performance tests and discussing the best\n> approach).\n\nThis is a great summary of some of the existing work in this area!\n\n> ### The plan\n>\n> As this project includes three ( actually four) sub projects, I would\n> address them one by one -\n>\n> 1. Firstly I will understand the working of EWAH compression better.\n>    I have gone through their documentation and have seen git’s\n>    implementation code for it. The commit messages were really helpful\n>    here. But I think I should research more. After that,  I can compare\n>    (and discuss) each approach with respect to the EWAH approach on\n>    some parameters (like amount of computation in each approach,\n>    simplicity, memory usage, correctness i.e. does it always give the\n>    correct output etc.). This comparison would lead me to take the\n>    most ideal approach in this case. There are several techniques which\n>    may work/perform better than the current EWAH implementation. I\n>    have researched some of these techniques. One of them is obviously\n>    the Roaring+Run method. I have gone through their\n>    (research paper)[https://arxiv.org/pdf/1709.07821v6.pdf]\n>    on this technique; it seems like a good approach to me. Other than\n>    that, there is a golang package called\n>    (sroar)[https://dgraph.io/blog/post/serialized-roaring-bitmaps-golang/]\n>    (i.e. Serialized Roaring bitmaps), which is an open source package\n>    ( mainly built for (Dgraph)[https://dgraph.io/])\n>    and the creator of this package claims it is\n>    (7x faster using 15x less memory)[https://github.com/dgraph-io/sroar#benchmarks].\n>    It doesn’t require any encoding/decoding step. I would look into\n>    it ( It needs to be implemented in C language though). I have also\n>    looked into approaches like\n>    (bloom filter)[https://en.wikipedia.org/wiki/Bloom_filter],\n>    (Hyperloglog)[https://en.wikipedia.org/wiki/HyperLogLog]. These are\n>    very fast and use very less memory. But they give probabilistic\n>    answers and sometimes they may give wrong answers. So, those\n>    would not be a good fit for us I guess.\n\nFor bitmaps, the number one thing we care about is correctness. I have\nnever thought about using Bloom filters before; even though the\none-sided nature of their errors means that we would never forget to\nsend an object that we should have, having an absolute result is vastly\npreferred.\n\nAfter that, I think we mostly care about how quickly they can be\ndecompressed. And after that, I think we care about things like \"how\nfast can they be written\", and \"how large are they\".\n\n> 2. I will understand the bitmap related files such as\n>    `pack-bitmap-write.c`[4], `pack-bitmap.c`[5] etc. It would\n>    help me to decide where and how I can add the code related to\n>    `table of contents` for bitmap.\n>    Taylor’s (branch work)[https://github.com/git/git/compare/master...ttaylorr:tb/bitmap-commit-table]\n>    would work as a reference for me. As the Project idea section\n>    suggests, I would also include performance tests to continuously\n>    check whether my approach is really improving the performance or\n>    not.\n\nDeveloping some performance tests up-front (including expanding on the\nexisting ones in the t/perf suite) I think is a good first step after\ndoing some basic research. That will help keep us honest about whether\nour changes are moving us in the right direction or the wrong one.\n\n> 3. As I understand more about bitmap related files, I will surely\n>    be able to think whether `adding a new mode` is really necessary\n>    or not (It is conceptually a good idea though). If necessary,\n>    then I would first make the flow design and discuss it with the\n>    community. If all is good, I will start working on it. Creating\n>    and running performance tests is a must.\n\n> 4. While developing all of these, my understanding of bitmap and\n>    its implementation will get better. So, that would help me to\n>    think more practically about the questions provided in the `Project\n>    Idea` section. Then I would work on it accordingly.\n\nThis all sounds very good and ambitious. Keep in mind, though, that\nthese projects have a tendency to take much more time than expected ;-).\nIf we get one done, I'll be thrilled! (The goal with suggesting a few\npotential directions to go in is not to say: \"let's do all of these\nthings\", but rather to give you some options in terms of what you find\nmost interesting and exciting to work on).\n\nSo I think it makes sense to try and find a way you can dip your toes\ninto 2-3 of the sub-projects and get a sense for what feels most doable\nand interesting, then focus on that before allocating time for more\nprojects in the future.\n\n> ## Estimated Timeline\n\nLike I said, I'm fine if you spend your entire GSoC project working on\njust one of these projects. So I don't want to get hung up on specific\ntimelines just yet. If you end up working on this, I would suggest\nbudgeting a week or so to try out a couple of different sub-projects,\nand then decide where to spend your time from there.\n\n> ## Blogging about Git\n>\n> I love to write blogs and technical articles. Those are my ways to\n> connect and communicate with the developers community. I have\n> previously written articles about Django in a portal named\n> (GeeksForGeeks)[https://auth.geeksforgeeks.org/user/riter79/articles].\n> Recently I started writing  blogs on\n> (Medium platform)[https://medium.com/@abhra303].\n>\n> During the GSoC event, I will frequently write blogs about my\n> progress. I will also share the problems I face and the solutions\n> of those problems that I consider.\n\nGreat!\n\n> I got interested in git by reading Olga’s GSoC blogs. That led me\n> to contribute to this codebase. So, someone like me will hopefully\n> be motivated by seeing my blogs ;-)\n>\n> ## Availability\n>\n> I intentionally freed my summer slot for GSoC. So, there wouldn’t\n> be much disturbance/inactive days while working on my project.\n> Generally, I can spend nearly 35-40 hours a week on this project.\n> If the college gets closed for some reason, then the amount of\n> available time will increase. Smart India Hackathon finale would\n> be held in July. So, I may be inactive for a few days. But overall,\n> I will be available most of the time.\n\nAll sounds good to me.\n\n> I hope you’ll give me a chance to make an impact among the developers\n> community by considering my application.\n\nThanks very much for your interest and the time you spent putting this\nproposal together. I hope that some of my comments were helpful in\nrefining it, and that you didn't mind my slow response too much.\n\nThanks,\nTaylor\n"},{"id":"453641","messageId":"20220414075846.14059-1-chakrabortyabhradeep79@gmail.com","threadId":"57681","inReplyTo":"YlckmDHRAYnE1J5t@nand.local","subject":"Re: [GSoC][RFC][PROPOSAL] Reachability bitmap improvements","fromName":"Abhradeep Chakraborty","fromEmail":"chakrabortyabhradeep79@gmail.com","sentAt":"2022-04-14T07:58:46Z","receivedAt":"2022-04-14T08:00:40Z","isPatch":false,"sender":{"key":"chakrabortyabhradeep79@gmail.com","avatar":"https://avatars.githubusercontent.com/u/75240995?v=4"},"body":"Taylor Blau <me@ttaylorr.com> wrote:\n\n> Thanks so much for submitting this proposal! I have been excited to look\n> through it, and am sorry for not getting to it sooner. Let me take a\n> look now and give some of my thoughts.\n\nThanks so much Taylor for reviewing my proposal. It's my pleasure!\n\n> Great! It sounds like working on Git would give you some new experience\n> in a different domain than some of your past projects, and help you\n> learn more about how it works and is developed.\n\nYeah, definitely! Looking forward to explore more in this domain :)\n\n> Terrific! I am really glad that the MyFirst... documents were helpful\n> and made it easier for you to contribute. The ProGit book is a great\n> resource, too.\n\nThanks :)\n\n> If you are looking for more resources, I would encourage you to search\n> around for blog posts written by Git contributors, particularly related\n> to reachability bitmaps (at least for this GSoC project). Some helpful\n> places to start there would be:\n>\n>     https://github.blog/2015-09-22-counting-objects/\n>     https://github.blog/2021-04-29-scaling-monorepo-maintenance/\n\nI have read the \"counting objects\" article already. It is a very good\narticle to understand the reachability bitmaps in git. I would surely\ngo through the other article you shared.\n\n> Note that commits and trees can be stored as deltas against other\n> commits and trees (which themselves might be packed as deltas) and so\n> on. But we only consider a pair of objects to be delta candidates for\n> one another when they share a common type (e.g., we would never delta a\n> tree object against a blob or vice-versa).\n\nOops. That is new to me. I didn't know that commits and trees can also\nbe delta-ed. Thanks for this info!!\n\n> Exactly; though note that since that series we now have multi-pack\n> bitmaps, too, which use a slightly different ordering called the\n> \"pseudo-pack\" order, which (more or less) looks like all of the objects\n> in a MIDX first sorted by which pack they came from, and then sorted by\n> their order within the pack, removing duplicates in favor of the\n> \"preferred\" pack.\n>\n> More thorough documentation on this can be found in the\n> \"multi-pack reverse indexes\" section of\n> \"Documentation/technical/pack-format.txt\".\n\nThanks. Will look into it :)\n\n> But I want to be careful about the word \"slow\" here. They might be slow,\n> or it might be really fast to decompress a given bitmap, depending on\n> the disk performance, CPU pressure, how large the bitmaps are, and so\n> on. So I think a good first step here is to validate our assumption that\n> EWAH decompression is even slow to begin with.\n>\n> (Of course, the literature on newer formats will readily tell you that\n> the old stuff is slower, but I think it's worth reevaluating those\n> statements in the context of a practical application instead of in\n> theory / benchmarks).\n\nI think, it is \"conceptually/theoritically\" slow approach. Because as\nyou said -\n> we can't begin to interpret the bitmaps until after decompressing them\n\nIt has to decompress the whole thing instead of evaluating the target\nbitmap. Hardwares can make it fast but theoritically the time complexity\nis slow.\n\nI will validate whether it is practically slow or not though.\n\n> Same comments here about whether or not this is slow to begin with. From\n> my experimental patches in this area earlier, I found that we could get\n> a significant speed-up in some cases, but that the speed-up was\n> basically obliterated whenever we had to do any follow-on traversal if\n> the bitmap coverage wasn't completely up-to-date.\n\nTrue. But atleast it is faster(hopefully) when bitmap coverage is up-to-date.\nWe may optimize/improve it to make it fast overall.\n\n> Arguably we could do this whether or not we solve the above, but doing\n> some combination of the above may make it easier (e.g., if we wanted to\n> change the bitmap selection to store dramatically more commits, then we\n> may want to investigate how much of a bottleneck the sequential read\n> requirement of .bitmap files would become for different numbers of\n> selected commits).\n\nTrue.\n\n> For bitmaps, the number one thing we care about is correctness. I have\n> never thought about using Bloom filters before; even though the\n> one-sided nature of their errors means that we would never forget to\n> send an object that we should have, having an absolute result is vastly\n> preferred.\n>\n> After that, I think we mostly care about how quickly they can be\n> decompressed. And after that, I think we care about things like \"how\n> fast can they be written\", and \"how large are they\".\n\nThat's obvious. I had included those probabilistic approaches because\nI thought we could have a check whether the obtained result is right\nor wrong. In case of wrong answers (2% chance for Hyperloglog), we can\nfollow another approach that alters only the wrong results. But I\nthink, it will become complex. More research is needed to check whether\nit can be done or not.\n\nFor other approaches ( i.e. Roaring+run and sroar), I think these two\nfits the criteria you listed in your comment. Though, I need to work\nmore to fully understand the sroar methodology.\n\n> This all sounds very good and ambitious. Keep in mind, though, that\n> these projects have a tendency to take much more time than expected ;-).\n> If we get one done, I'll be thrilled! (The goal with suggesting a few\n> potential directions to go in is not to say: \"let's do all of these\n> things\", but rather to give you some options in terms of what you find\n> most interesting and exciting to work on).\n>\n> So I think it makes sense to try and find a way you can dip your toes\n> into 2-3 of the sub-projects and get a sense for what feels most doable\n> and interesting, then focus on that before allocating time for more\n> projects in the future.\n>\n> > ## Estimated Timeline\n>\n> Like I said, I'm fine if you spend your entire GSoC project working on\n> just one of these projects. So I don't want to get hung up on specific\n> timelines just yet. If you end up working on this, I would suggest\n> budgeting a week or so to try out a couple of different sub-projects,\n> and then decide where to spend your time from there.\n\nIf that is the case, then I would go for the first sub-project i.e.\n\"Think of an better alternative of EWAH\". It interests me a lot. Though\nI will do what you suggested i.e. \"try and find a way you can dip your\ntoes into 2-3 of the sub-projects and get a sense for what feels most\ndoable and interesting\".\n\nShould I remove \"Estimated Timeline\" ( or/and point 2, 3 from \"The Plan\"\nsection) for now then?\n\n> Thanks very much for your interest and the time you spent putting this\n> proposal together. I hope that some of my comments were helpful in\n> refining it, and that you didn't mind my slow response too much.\n\nThe comments and suggestions are indeed helpful! I even didn't mind\nanything.\n\nThanks :)\n"},{"id":"453650","messageId":"fc0015ac-9ad4-d3b4-39ee-0bf4f9c99fa0@iee.email","threadId":"57681","inReplyTo":"YlckmDHRAYnE1J5t@nand.local","subject":"Re: [GSoC][RFC][PROPOSAL] Reachability bitmap improvements","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2022-04-14T14:24:29Z","receivedAt":"2022-04-14T14:43:06Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Abhradeep,\n\n\nOn 13/04/2022 20:29, Taylor Blau wrote:\n>> Though I had read many documentations, I was still not able to fully\n>> understand the terminologies (like `refs`, `packfiles`, `blobs`, `trees`\n>> etc.). (ProGit)[https://git-scm.com/book/en/v2] helped me tremendously here.\n>> I read the full book and it cleared almost every doubt that came into my mind.\n> Terrific! I am really glad that the MyFirst... documents were helpful\n> and made it easier for you to contribute. The ProGit book is a great\n> resource, too.\n>\n> If you are looking for more resources, I would encourage you to search\n> around for blog posts written by Git contributors, particularly related\n> to reachability bitmaps (at least for this GSoC project). Some helpful\n> places to start there would be:\n>\n>     https://github.blog/2015-09-22-counting-objects/\n>     https://github.blog/2021-04-29-scaling-monorepo-maintenance/\n>\nIt's also worth looking at the Git Rev News articles and light reading links\n     https://git.github.io/rev_news/ and\n     https://git.github.io/rev_news/archive/\n--\nPhilip.\n"},{"id":"453682","messageId":"20220415052856.49433-1-chakrabortyabhradeep79@gmail.com","threadId":"57681","inReplyTo":"fc0015ac-9ad4-d3b4-39ee-0bf4f9c99fa0@iee.email","subject":"Re: [GSoC][RFC][PROPOSAL] Reachability bitmap improvements","fromName":"Abhradeep Chakraborty","fromEmail":"chakrabortyabhradeep79@gmail.com","sentAt":"2022-04-15T05:28:56Z","receivedAt":"2022-04-15T05:29:29Z","isPatch":false,"sender":{"key":"chakrabortyabhradeep79@gmail.com","avatar":"https://avatars.githubusercontent.com/u/75240995?v=4"},"body":"Philip Oakley <philipoakley@iee.email> wrote:\n\n> It's also worth looking at the Git Rev News articles and light reading links\n>      https://git.github.io/rev_news/ and\n>      https://git.github.io/rev_news/archive/\n\nThanks Philip! will surely look into it.\n\nThanks :)\n"}]}