{"thread":{"id":"57758","subject":"[GSoC][RFC][Proposal] Reachability bitmap improvements","startedAt":"2022-04-19T00:10:55Z","lastAt":"2022-04-19T00:10:55Z","messageCount":1,"participants":["Plato Kiorpelidis"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"453909","messageId":"CAO2gv81YQRTAvJOW4J9ROK5bi0xizhveLoyVbdXniRZ8N+ic0A@mail.gmail.com","threadId":"57758","inReplyTo":null,"subject":"[GSoC][RFC][Proposal] Reachability bitmap improvements","fromName":"Plato Kiorpelidis","fromEmail":"kioplato@gmail.com","sentAt":"2022-04-19T00:10:22Z","receivedAt":"2022-04-19T00:10:55Z","isPatch":false,"sender":{"key":"kioplato@gmail.com","avatar":null},"body":"Hello all,\n\nI completed my proposal and I'm sharing it with you. Even thought it's\nclose to the deadline I hope it gets reviewed. I'm looking for more\nrelated material like mailing list conversations to include in my\nproposal and learn more.\nHow can I further improve it? Have I missed something?\n\nI know I didn't include any links here. The PDF version I submitted has links.\n\nThanks in advance, I'm sorry for the late submission,\nPlato\n\n~~~~~~~~~~\n\n# Contact info [...]\n\n# About me\n\nFinal year undergrad @ University of Athens, majoring Computer Science\nand minoring Mathematics. Throughout my studies I was selected to help\nconduct uni lab lectures voluntarily for courses: data structures in C\n(4 years), oop in C++ (2 years). GPA: 8.4/10.\n\nI was a founding member of my university department’s ACM student\nchapter, with the goal to grow and bond our uni community by\norganizing lectures and workshops by students, academic researchers\nand professionals. Mostly I was active in open source channels where I\ndirected, along with others, conversations about how to get involved\nand contribute to open source projects. We even launched our own dummy\nproject to help provide aided exposure with PRs, reviews and related\nprocedures, which was accompanied by a talk I conducted (pt. 1, pt. 2)\nregarding the workflow with Git & Github. Covid outbreak hindered the\ndevelopment of the ACM student chapter.\n\nMy computing world volunteerism does not stop there as I helped\nconstruct the website & autograder for the cryptography course in ‘15\nfor NTUA ECE, a different university from the one I’m enrolled in. I\nalso gave a talk for first-year undergrads on how to switch from\nWindows to Linux and why, including its advantages and disadvantages.\n\nIn late 2019 I was recommended by a prof. to work in my uni department\nto develop systems for academic and educational purposes. I focused on\nsetting up and synchronizing LDAP databases, SCIM identity management,\nLSC and maintenance of our GitLab instance.\n\n# Benefits to Community\n\nI plan to become a long term Git contributor, help develop and\ninfluence its design and attract new contributors. I plan to give a\ntalk to my fellow undergrad and graduate classmates about my\nexperience in GSoC with Git. How they can become involved, the GSoC\nprogram, Git’s codebase structure and how things are done within the\nGit organization.\n\nI will invite them to participate in GSoC ‘23 with Git where,\nhopefully, I will mentor the selected candidates. My participation\nwith GSoC this year will lay the foundations for me to learn and\naccumulate the necessary experience and understanding so I can give\nback to GSoC, Git, my university and fellow classmates.\n\nThroughout my GSoC journey, and after it, I’ll publish digests about\nmy bitmap work and related knowledge under kioplato.github.io, similar\nto the ones in Git Rev News. I’ll also PR related parts to Git Rev\nNews. This way my work will be transparent and accessible to anyone\nwho’s interested. It will also serve as reference throughout my GSoC\njourney and towards future GSoC candidates interested in participating\nwith Git organization.\n\nImproving Git will benefit open source projects and their communities\nas well, increasing productivity due to reduction in wait times as the\nproposed project will, hopefully, yield non-trivial speed-up over\nnetwork operations. Git is a widely used technology throughout the\nindustry and further developing it will benefit everyone who’s trying\nto improve our lives through technology.\n\n# Microproject & Git related work\n\n  –  In 2019, I planned to participate in GSoC ‘20. To familiarize\nmyself with Git and get involved early, I picked up this microproject\nfrom GSoC ‘19 and submitted a patch converting remove_subtree()\nfunction from entry.c to use dir-iterator API instead of opendir,\nreaddir, closedir API. This function is required to iterate directory\npaths after their contents, rendering my patch invalid, as pointed out\nby Matheus, since dir-iterator didn’t and still doesn’t offer such\nfunctionality. I didn’t follow up with a dir-iterator API patch to\nimplement the required functionality nor did I attempt to participate\nin GSoC ‘20 due to having limited time.\n\n  –  My dream to participate in GSoC continues and I plan to\nparticipate in GSoC ‘22. I picked up from where I left off and\nintroduced the first set of changes requested by this thread to\ndir-iterator and submitted RFC v1. The first set of changes refer to\ndir-iterator iterating directories before and/or after their contents.\nMy goal is to considerably improve dir-iterator, guided by the needs\nof its possible customers like read_directory_recursive(), resulting\nin a simpler, more maintainable codebase. Getting selected for GSoC\nwill put this goal on hold.\n\n  –  While reading through the SoC documentation in git.github.com I\nnoticed the CI section of the General Microproject Information webpage\nwasn’t updated after the switch from Travis-ci to Github actions. The\nCI instructions were out of date, pointing to Travis-ci. I builded the\nsite, updated the section and opened a PR to git.github.com repo,\nwhich was merged.\n\n# Proposal Abstract\n\nPre Git v2.0.0, network operations like fetches and clones were\nhindered by the counting objects phase. In this phase, Git needed to\ncalculate which objects are required to be sent. However, Git only\nknows the tips of all branches, so its only option was to walk down\nthe graph. To deal with this, Git adopted JGit’s reachability bitmaps\nin EWAH format. This method led to a significant speed-up over the\nnetwork operations, as it indexed which objects are reachable from\nsalient commits.\n\nWhile EWAH bitmaps eliminate a performance bottleneck by indexing\nwhich commits are reachable from a given commit, there are possible\nimprovements to be made. There is a sense that EWAH bitmap compression\nis slow in some cases. Are Roaring bitmaps better in Git’s case? There\nis strong evidence they will be. Are Roaring bitmaps faster to access\nspecific parts of the bitmap due to its random-access feature and how\ncan we use this? Is the current bitmap format sufficient to\nincorporate a lookup table which specifies the commits which have a\nbitmap? How can we improve it? This project attempts to answer these\nquestions.\n\nThe proposed project would entail a) Designing & implementing a suite\nof performance tests benchmarking EWAH to validate our assumption that\nthe performance of bitmap decompression is worth pursuing. Compare the\ntwo bitmap compressions and perform any necessary changes to the\n.bitmap format to accommodate the new compression scheme. Speeding-up\nread, write bitmap operations or reducing used memory will convince us\nto switch to Roaring bitmaps. b) Further explore the idea of\nintroducing a small “table of contents”, indexing which commits have a\nbitmap and where to find them in the .bitmap file. In this case we\nwill need to implement a new .bitmap format to add a variable-width\ntable of contents.\n\n# Proposal Timeline\n\nThe proposed project is challenging and in combination with its\nexperimental nature requires diligence and careful planning. I need to\nbe realistic. I will need time to familiarize myself and be confident\nin my understanding regarding Git’s implementation related to bitmaps,\npacking objects and related material, before proceeding with the\nactual changes to .bitmap format and performance testing. These\nrequire time and effort, therefore I’ll reserve sufficient time to get\nthem right: I’ll dedicate 35-40 hours/week. I will reserve more if the\nproject requires it and I’m open to extending the duration of the\nprogram in case the proposed goals are not achieved.\n\n## Overview\n\nThe plan is to first validate the need for an alternate bitmap\ncompression algorithm. This will be verified from the performance test\nsuite. → If there is indeed a need, we will attempt to adopt Roaring\nbitmaps instead of EWAH, and compare the two implementations.\nHopefully Roaring bitmaps will speed-up bitmap operations and convince\nus to adopt. → Regardless of the necessity of an alternate bitmap\ncompression algorithm, the idea of introducing a “table of contents”\nto the bitmap format will be explored, even post GSoC. If the\nperformance tests prove that EWAH is good enough, then the “table of\ncontents” along with a new .bitmap format will become my primary\nfocus.\n\n1. Spend time understanding bitmap data structure, EWAH, Git’s bitmap\nformat, codebase and respective implementations. Self code and tinker\nwith codebase. Don’t be afraid to ask questions and make sure it’s\nclear to me what’s expected.\nMaterial: Bitmap EWAH Bitmap format Bitmaps & inverted lists Git: 1 2 3 4 5\n2. Design & implement a suite of performance tests. Validate our\nassumption that the performance of bitmap decompression is worth\npursuing.\nMaterial: Git performance tests Taylor’s .bitmap format: mail-list fork\n3. Implement Roaring bitmap with run containers. Think about the\narchitecture & design. Compare it against the existing implementation.\nAdopt if bitmap operations are faster.\nMaterial: Roaring paper Roaring spec Bitmap format Git: 1 2 3 4 5\n4. (alternative) Dedicate some time to investigate and sketch out a\nnew .bitmap format for the “table of contents” sub-project. Current\nbitmap format comes with limitations.\nMaterial: Bitmap format Taylor’s .bitmap format: mail-list fork\nStolee’s chunk-format API\n5. (alternative) Implement a new bitmap format to incorporate the\nvariable-width “table of contents” metadata. Implement and run related\ntests to verify speed-up.\nMaterial: Bitmap format Taylor’s .bitmap format: mail-list fork\nStolee’s chunk-format API\n\n## Timeline\n\n- April 19: GSoC contributor application deadline\n- April 20 - May 08 (~3 weeks, 19 days, 120h): Understand codebase\nTinker with and understand Bitmap, EWAH, Git’s EWAH, Bitmap format.\nLocal testing and self code. Gather a good understanding of Git’s\ncodebase related to bitmaps in general 1 2 3 4 5. Explore related Git\ncommands like git gc, pack-objects, unpack-objects, repack, bundle and\nother related commands. See which code paths trigger and understand\nwhat’s happening. Ask questions to mentors Taylor & Sivaraam and wider\naudience. Read documentation.\n- May 09 - May 13 (~1 week, 5 days, 40h): Understand performance tests library\nUnderstand the architecture of Git’s performance tests & existing\nbitmap performance tests. Investigate which code paths trigger in the\ncodebase. Consult Taylor’s performance test parts: mail-list to aid\nwith understanding of how the performance tests work.\n- May 20: Accepted GSoC contributor projects announced & Community\nbonding period begins\n- May 14 - June 03 (3 weeks, 21 days, 120+h): Compression perf tests &\nvalidate assumptions\nDesign and implement a suite of performance tests. Consult existing\ntests, README, conversations, Taylor’s previous work on .bitmap\nformat: mail-list fork. Validate our assumption that the performance\nof bitmap decompression is worth pursuing. Discuss possible new\n.bitmap format. Tie up loose ends.\n- June 13: Coding officially begins\n- June 04  - July 03 (4 weeks, 30 days, 160h): Implement Roaring &\ncompare to EWAH\nImplement Roaring bitmaps with run containers. Understand Roaring\nspecification and other compressions. Self code and local testing to\nunderstand Roaring format. Read Roaring paper. Minimally implement\nRoaring bitmaps and compare against existing compression. Adopt if\nbitmap operations are faster. Discuss possible new .bitmap format. Tie\nup loose ends.\n- July 04 - July 24 (3 weeks, 21 days, 120h): Bitmap perf tests &\nfurther discuss bitmap format\nConsult Taylor’s previous work on .bitmap format with commit lookup\ntable: mail-list fork. Implement more tests to identify & discuss\npossible improvements to be made to the current .bitmap format.\nInvestigate how we can incorporate a variable-width table of contents\nto a new .bitmap format. How does the way we read hash-cache extension\nlimit the current .bitmap format? Can we make it compatible with\nStolee’s chunk-format API? Further understand current .bitmap format.\nUnderstand pack objects, deltas, related operations & code paths. Self\ncode and tinker.\n- July 29: Phase 1 Evaluation deadline: Submit code\n- July 25 - July 29 (5 days): Submit phase 1 evaluation\n- July 30 - Aug 21 (4 weeks, 160h): Implement new .bitmap format ideas\n& run perf tests\nExperiment with new .bitmap format ideas and document possible\nspeed-up. Continue discussions related to .bitmap formats. Consult\nprevious conversations. Hopefully arrive at a satisfying new .bitmap\nformat. Think about its architecture & design.\n- Aug 22 - Sep 04 (2 weeks, 80h): Unallocated time in case of delays &\nbad time management\n- Sep 05 - Sep 12 (1 week): Submit final work product & mentor evaluation.\n\nThe above timeline serves mostly as a guideline. The overall pace and\nprogress of the project depends on intermediate steps like\n“Compression perf tests & validate assumptions”. There is a plethora\nof work to be done and possible improvements to be discussed in this\narea. That’s the purpose behind the multiple subprojects of the\nproposed project i.e. additional flexibility.\n\nAs a possible GSoC candidate, I want to successfully complete GSoC and\nget this project right. I want to explore bitmaps, their compressions\nand offer as much as I can. For this reason I’ll take advantage and\nstart preparing from 20 April as the proposal timeline suggests. This\nwill give me additional flexibility, given the nature of the project\n(e.g. in case EWAH compression is good enough), and confidence since\nI’ll have more time to work and understand underlying implementations.\nEven if I’m not selected, these conversations and my exposure to\nbitmaps will help the selected candidate. Additionally, I will try to\nparticipate in the process and help the selected candidate.\n\n# Related Work\n\nThere is strong evidence that Roaring bitmaps, usually, perform better\nthan its alternatives:\n –  Guzun et al compared Concise, WAH, EWAH, Roaring (without run\ncontainers) with a hybrid system combining EWAH and uncompressed\nbitsets. In many of their tests, but not all, Roaring was superior to\nConcise, WAH and EWAH.\n –  Wang et al compared a wide range of bitmap compression techniques.\nThey conclude their comparison by a strong recommendation in favor of\nRoaring: “Use Roaring for bitmap compression whenever possible. Do not\nuse other bitmap compression methods such as BBC, WAH, EWAH, PLWAH,\nCONCISE, VALWAH, and SBH.”\n –  Lemire et al reviewed and evaluated the CRoaring library. They\ncompared BitMagic, EWAH (code from this library is part of the Git\nversion-control tool), uncompressed bitset, WAH & Concise, C++\nstd::vector and std::unordered_set for hash-set performance. In their\ntests Roaring performance was superior. They concluded by saying “No\nsingle approach can be best in all cases, but Roaring offers good\nall-around performance”.\n –  CRoaring is an implementation of the Roaring bitmaps in C and C++.\nWill be used as reference while adopting Roaring bitmaps in Git.\n –  Bitmap implementation in C. Excellent for getting introduced into\nthe bitmap data structure. Will be used as reference.\n –  Roaring format specification thoroughly describes the compressed\nbitmap format.\nWill be consulted throughout the project’s duration.\n –  EWAH implementation in C. Excellent for getting introduced into\nhow things are currently implemented. Git’s EWAH implementation will\ncomplement that.\n –  Roaring bitmaps publication: Consistently faster and smaller\ncompressed bitmaps with Roaring. Will be used as reference.\n –  Comparison between bitmap compressions: An Experimental Study of\nBitmap Compression vs. Inverted List Compression. Will be used for\nadditional context since it provides a brief explanation of all bitmap\ncompressions.\n –  Taylor’s previous work on .bitmap table of contents: mail-list fork\nTaylor found that we could get a significant speed-up in some cases,\nbut 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\nPrevious work that introduced EWAH bitmaps could be used for possible\nadditional context, exposure, related conversations, code paths and\nreference.\n –  Initial patch series, designed by Shawn Pearce for JGit,\nimplemented by Vicent Marti\n –  Initial patch improvements by Jeff v1, v2, v3, v4.\n –  Merged initial patch: compressed bitmaps, use bitmaps when packing objects\n\nRelated Github blog posts: Counting objects, Scaling monorepo maintenance\n\n# Biographical Information\n\n –  Me and Git\nI have been using Git since 2015, in my work and to collaborate on uni\nand fun projects. Throughout these years I’ve read the entire pro Git\nbook while following most parts through my terminal, reproducing the\nbehavior, in order to make me a better software engineer. The workshop\nI conducted (pt. 1, pt. 2) regarding the workflow with Git & Github\nwas heavily influenced by pro Git book which is apparent in the\nworkshop’s pdf. I’ve also read material like hacking Git, github.blog\nposts, Git Rev News and similar technical documents.\n\n –  Me, C and Shell\nC is my native programming language. I have written 80.000+ LOC and\nI’ve implemented various systems. Most notably: B+ Tree, LSH for KNN &\nclustering, simple search engine, graph editor, MPI & OpenMP parallel\nsystem, threaded server, multiprocess systems with workers, archiver,\nmany algorithms & data structures (kd-trees, red-black, AVL, splay\ntree, linked-lists, skip lists, hashtable, etc), many of which I’ve\nconverted to be thread-safe. In my uni we’re C/C++ oriented.\nI’ve been using Arch Linux exclusively for 4+ years to learn and\ntinker with my setup. I run dwm, st, self compiled Linux kernel,\nvarious shell scripts, btrfs, full disk encryption, lvm to configure\nmy computer just how I like it. I’m confident in my C & shell skills.\n\n – Professional Experience\nJan 2020 - June 2021 (1.5 year) GUnet\nWorked on setting up and synchronizing LDAP databases, SCIM identity\nmanagement, LSC and maintenance of our GitLab instance.\n\n –  Teaching\n2019: Workshop regarding the workflow of Git & Github. (pt. 1, pt. 2)\n2017: Workshop for first-year undergrads on how to switch from Windows\nto Linux and why, including its advantages & disadvantages and related\nutilities like IDEs, compilers, packages.\n2016 - 2020: Lab assistant courses data structures in C (4 years), oop\ncourse in C++ (2 years).\n"}]}