Hello all, I completed my proposal and I'm sharing it with you. Even thought it's close to the deadline I hope it gets reviewed. I'm looking for more related material like mailing list conversations to include in my proposal and learn more. How can I further improve it? Have I missed something? I know I didn't include any links here. The PDF version I submitted has links. Thanks in advance, I'm sorry for the late submission, Plato ~~~~~~~~~~ # Contact info [...] # About me Final year undergrad @ University of Athens, majoring Computer Science and minoring Mathematics. Throughout my studies I was selected to help conduct uni lab lectures voluntarily for courses: data structures in C (4 years), oop in C++ (2 years). GPA: 8.4/10. I was a founding member of my university department’s ACM student chapter, with the goal to grow and bond our uni community by organizing lectures and workshops by students, academic researchers and professionals. Mostly I was active in open source channels where I directed, along with others, conversations about how to get involved and contribute to open source projects. We even launched our own dummy project to help provide aided exposure with PRs, reviews and related procedures, which was accompanied by a talk I conducted (pt. 1, pt. 2) regarding the workflow with Git & Github. Covid outbreak hindered the development of the ACM student chapter. My computing world volunteerism does not stop there as I helped construct the website & autograder for the cryptography course in ‘15 for NTUA ECE, a different university from the one I’m enrolled in. I also gave a talk for first-year undergrads on how to switch from Windows to Linux and why, including its advantages and disadvantages. In late 2019 I was recommended by a prof. to work in my uni department to develop systems for academic and educational purposes. I focused on setting up and synchronizing LDAP databases, SCIM identity management, LSC and maintenance of our GitLab instance. # Benefits to Community I plan to become a long term Git contributor, help develop and influence its design and attract new contributors. I plan to give a talk to my fellow undergrad and graduate classmates about my experience in GSoC with Git. How they can become involved, the GSoC program, Git’s codebase structure and how things are done within the Git organization. I will invite them to participate in GSoC ‘23 with Git where, hopefully, I will mentor the selected candidates. My participation with GSoC this year will lay the foundations for me to learn and accumulate the necessary experience and understanding so I can give back to GSoC, Git, my university and fellow classmates. Throughout my GSoC journey, and after it, I’ll publish digests about my bitmap work and related knowledge under kioplato.github.io, similar to the ones in Git Rev News. I’ll also PR related parts to Git Rev News. This way my work will be transparent and accessible to anyone who’s interested. It will also serve as reference throughout my GSoC journey and towards future GSoC candidates interested in participating with Git organization. Improving Git will benefit open source projects and their communities as well, increasing productivity due to reduction in wait times as the proposed project will, hopefully, yield non-trivial speed-up over network operations. Git is a widely used technology throughout the industry and further developing it will benefit everyone who’s trying to improve our lives through technology. # Microproject & Git related work – In 2019, I planned to participate in GSoC ‘20. To familiarize myself with Git and get involved early, I picked up this microproject from GSoC ‘19 and submitted a patch converting remove_subtree() function from entry.c to use dir-iterator API instead of opendir, readdir, closedir API. This function is required to iterate directory paths after their contents, rendering my patch invalid, as pointed out by Matheus, since dir-iterator didn’t and still doesn’t offer such functionality. I didn’t follow up with a dir-iterator API patch to implement the required functionality nor did I attempt to participate in GSoC ‘20 due to having limited time. – My dream to participate in GSoC continues and I plan to participate in GSoC ‘22. I picked up from where I left off and introduced the first set of changes requested by this thread to dir-iterator and submitted RFC v1. The first set of changes refer to dir-iterator iterating directories before and/or after their contents. My goal is to considerably improve dir-iterator, guided by the needs of its possible customers like read_directory_recursive(), resulting in a simpler, more maintainable codebase. Getting selected for GSoC will put this goal on hold. – While reading through the SoC documentation in git.github.com I noticed the CI section of the General Microproject Information webpage wasn’t updated after the switch from Travis-ci to Github actions. The CI instructions were out of date, pointing to Travis-ci. I builded the site, updated the section and opened a PR to git.github.com repo, which was merged. # Proposal Abstract Pre Git v2.0.0, network operations like fetches and clones were hindered by the counting objects phase. In this phase, Git needed to calculate which objects are required to be sent. However, Git only knows the tips of all branches, so its only option was to walk down the graph. To deal with this, Git adopted JGit’s reachability bitmaps in EWAH format. This method led to a significant speed-up over the network operations, as it indexed which objects are reachable from salient commits. While EWAH bitmaps eliminate a performance bottleneck by indexing which commits are reachable from a given commit, there are possible improvements to be made. There is a sense that EWAH bitmap compression is slow in some cases. Are Roaring bitmaps better in Git’s case? There is strong evidence they will be. Are Roaring bitmaps faster to access specific parts of the bitmap due to its random-access feature and how can we use this? Is the current bitmap format sufficient to incorporate a lookup table which specifies the commits which have a bitmap? How can we improve it? This project attempts to answer these questions. The proposed project would entail a) Designing & implementing a suite of performance tests benchmarking EWAH to validate our assumption that the performance of bitmap decompression is worth pursuing. Compare the two bitmap compressions and perform any necessary changes to the .bitmap format to accommodate the new compression scheme. Speeding-up read, write bitmap operations or reducing used memory will convince us to switch to Roaring bitmaps. b) Further explore the idea of introducing a small “table of contents”, indexing which commits have a bitmap and where to find them in the .bitmap file. In this case we will need to implement a new .bitmap format to add a variable-width table of contents. # Proposal Timeline The proposed project is challenging and in combination with its experimental nature requires diligence and careful planning. I need to be realistic. I will need time to familiarize myself and be confident in my understanding regarding Git’s implementation related to bitmaps, packing objects and related material, before proceeding with the actual changes to .bitmap format and performance testing. These require time and effort, therefore I’ll reserve sufficient time to get them right: I’ll dedicate 35-40 hours/week. I will reserve more if the project requires it and I’m open to extending the duration of the program in case the proposed goals are not achieved. ## Overview The plan is to first validate the need for an alternate bitmap compression algorithm. This will be verified from the performance test suite. → If there is indeed a need, we will attempt to adopt Roaring bitmaps instead of EWAH, and compare the two implementations. Hopefully Roaring bitmaps will speed-up bitmap operations and convince us to adopt. → Regardless of the necessity of an alternate bitmap compression algorithm, the idea of introducing a “table of contents” to the bitmap format will be explored, even post GSoC. If the performance tests prove that EWAH is good enough, then the “table of contents” along with a new .bitmap format will become my primary focus. 1. Spend time understanding bitmap data structure, EWAH, Git’s bitmap format, codebase and respective implementations. Self code and tinker with codebase. Don’t be afraid to ask questions and make sure it’s clear to me what’s expected. Material: Bitmap EWAH Bitmap format Bitmaps & inverted lists Git: 1 2 3 4 5 2. Design & implement a suite of performance tests. Validate our assumption that the performance of bitmap decompression is worth pursuing. Material: Git performance tests Taylor’s .bitmap format: mail-list fork 3. Implement Roaring bitmap with run containers. Think about the architecture & design. Compare it against the existing implementation. Adopt if bitmap operations are faster. Material: Roaring paper Roaring spec Bitmap format Git: 1 2 3 4 5 4. (alternative) Dedicate some time to investigate and sketch out a new .bitmap format for the “table of contents” sub-project. Current bitmap format comes with limitations. Material: Bitmap format Taylor’s .bitmap format: mail-list fork Stolee’s chunk-format API 5. (alternative) Implement a new bitmap format to incorporate the variable-width “table of contents” metadata. Implement and run related tests to verify speed-up. Material: Bitmap format Taylor’s .bitmap format: mail-list fork Stolee’s chunk-format API ## Timeline - April 19: GSoC contributor application deadline - April 20 - May 08 (~3 weeks, 19 days, 120h): Understand codebase Tinker with and understand Bitmap, EWAH, Git’s EWAH, Bitmap format. Local testing and self code. Gather a good understanding of Git’s codebase related to bitmaps in general 1 2 3 4 5. Explore related Git commands like git gc, pack-objects, unpack-objects, repack, bundle and other related commands. See which code paths trigger and understand what’s happening. Ask questions to mentors Taylor & Sivaraam and wider audience. Read documentation. - May 09 - May 13 (~1 week, 5 days, 40h): Understand performance tests library Understand the architecture of Git’s performance tests & existing bitmap performance tests. Investigate which code paths trigger in the codebase. Consult Taylor’s performance test parts: mail-list to aid with understanding of how the performance tests work. - May 20: Accepted GSoC contributor projects announced & Community bonding period begins - May 14 - June 03 (3 weeks, 21 days, 120+h): Compression perf tests & validate assumptions Design and implement a suite of performance tests. Consult existing tests, README, conversations, Taylor’s previous work on .bitmap format: mail-list fork. Validate our assumption that the performance of bitmap decompression is worth pursuing. Discuss possible new .bitmap format. Tie up loose ends. - June 13: Coding officially begins - June 04 - July 03 (4 weeks, 30 days, 160h): Implement Roaring & compare to EWAH Implement Roaring bitmaps with run containers. Understand Roaring specification and other compressions. Self code and local testing to understand Roaring format. Read Roaring paper. Minimally implement Roaring bitmaps and compare against existing compression. Adopt if bitmap operations are faster. Discuss possible new .bitmap format. Tie up loose ends. - July 04 - July 24 (3 weeks, 21 days, 120h): Bitmap perf tests & further discuss bitmap format Consult Taylor’s previous work on .bitmap format with commit lookup table: mail-list fork. Implement more tests to identify & discuss possible improvements to be made to the current .bitmap format. Investigate how we can incorporate a variable-width table of contents to a new .bitmap format. How does the way we read hash-cache extension limit the current .bitmap format? Can we make it compatible with Stolee’s chunk-format API? Further understand current .bitmap format. Understand pack objects, deltas, related operations & code paths. Self code and tinker. - July 29: Phase 1 Evaluation deadline: Submit code - July 25 - July 29 (5 days): Submit phase 1 evaluation - July 30 - Aug 21 (4 weeks, 160h): Implement new .bitmap format ideas & run perf tests Experiment with new .bitmap format ideas and document possible speed-up. Continue discussions related to .bitmap formats. Consult previous conversations. Hopefully arrive at a satisfying new .bitmap format. Think about its architecture & design. - Aug 22 - Sep 04 (2 weeks, 80h): Unallocated time in case of delays & bad time management - Sep 05 - Sep 12 (1 week): Submit final work product & mentor evaluation. The above timeline serves mostly as a guideline. The overall pace and progress of the project depends on intermediate steps like “Compression perf tests & validate assumptions”. There is a plethora of work to be done and possible improvements to be discussed in this area. That’s the purpose behind the multiple subprojects of the proposed project i.e. additional flexibility. As a possible GSoC candidate, I want to successfully complete GSoC and get this project right. I want to explore bitmaps, their compressions and offer as much as I can. For this reason I’ll take advantage and start preparing from 20 April as the proposal timeline suggests. This will give me additional flexibility, given the nature of the project (e.g. in case EWAH compression is good enough), and confidence since I’ll have more time to work and understand underlying implementations. Even if I’m not selected, these conversations and my exposure to bitmaps will help the selected candidate. Additionally, I will try to participate in the process and help the selected candidate. # Related Work There is strong evidence that Roaring bitmaps, usually, perform better than its alternatives: – Guzun et al compared Concise, WAH, EWAH, Roaring (without run containers) with a hybrid system combining EWAH and uncompressed bitsets. In many of their tests, but not all, Roaring was superior to Concise, WAH and EWAH. – Wang et al compared a wide range of bitmap compression techniques. They conclude their comparison by a strong recommendation in favor of Roaring: “Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods such as BBC, WAH, EWAH, PLWAH, CONCISE, VALWAH, and SBH.” – Lemire et al reviewed and evaluated the CRoaring library. They compared BitMagic, EWAH (code from this library is part of the Git version-control tool), uncompressed bitset, WAH & Concise, C++ std::vector and std::unordered_set for hash-set performance. In their tests Roaring performance was superior. They concluded by saying “No single approach can be best in all cases, but Roaring offers good all-around performance”. – CRoaring is an implementation of the Roaring bitmaps in C and C++. Will be used as reference while adopting Roaring bitmaps in Git. – Bitmap implementation in C. Excellent for getting introduced into the bitmap data structure. Will be used as reference. – Roaring format specification thoroughly describes the compressed bitmap format. Will be consulted throughout the project’s duration. – EWAH implementation in C. Excellent for getting introduced into how things are currently implemented. Git’s EWAH implementation will complement that. – Roaring bitmaps publication: Consistently faster and smaller compressed bitmaps with Roaring. Will be used as reference. – Comparison between bitmap compressions: An Experimental Study of Bitmap Compression vs. Inverted List Compression. Will be used for additional context since it provides a brief explanation of all bitmap compressions. – Taylor’s previous work on .bitmap table of contents: mail-list fork Taylor found that we could get a significant speed-up in some cases, but that the speed-up was basically obliterated whenever we had to do any follow-on traversal if the bitmap coverage wasn't completely up-to-date. Previous work that introduced EWAH bitmaps could be used for possible additional context, exposure, related conversations, code paths and reference. – Initial patch series, designed by Shawn Pearce for JGit, implemented by Vicent Marti – Initial patch improvements by Jeff v1, v2, v3, v4. – Merged initial patch: compressed bitmaps, use bitmaps when packing objects Related Github blog posts: Counting objects, Scaling monorepo maintenance # Biographical Information – Me and Git I have been using Git since 2015, in my work and to collaborate on uni and fun projects. Throughout these years I’ve read the entire pro Git book while following most parts through my terminal, reproducing the behavior, in order to make me a better software engineer. The workshop I conducted (pt. 1, pt. 2) regarding the workflow with Git & Github was heavily influenced by pro Git book which is apparent in the workshop’s pdf. I’ve also read material like hacking Git, github.blog posts, Git Rev News and similar technical documents. – Me, C and Shell C is my native programming language. I have written 80.000+ LOC and I’ve implemented various systems. Most notably: B+ Tree, LSH for KNN & clustering, simple search engine, graph editor, MPI & OpenMP parallel system, threaded server, multiprocess systems with workers, archiver, many algorithms & data structures (kd-trees, red-black, AVL, splay tree, linked-lists, skip lists, hashtable, etc), many of which I’ve converted to be thread-safe. In my uni we’re C/C++ oriented. I’ve been using Arch Linux exclusively for 4+ years to learn and tinker with my setup. I run dwm, st, self compiled Linux kernel, various shell scripts, btrfs, full disk encryption, lvm to configure my computer just how I like it. I’m confident in my C & shell skills. – Professional Experience Jan 2020 - June 2021 (1.5 year) GUnet Worked on setting up and synchronizing LDAP databases, SCIM identity management, LSC and maintenance of our GitLab instance. – Teaching 2019: Workshop regarding the workflow of Git & Github. (pt. 1, pt. 2) 2017: Workshop for first-year undergrads on how to switch from Windows to Linux and why, including its advantages & disadvantages and related utilities like IDEs, compilers, packages. 2016 - 2020: Lab assistant courses data structures in C (4 years), oop course in C++ (2 years).
