{"thread":{"id":"58219","subject":"[GSoC] Abhradeep's GSoC blogs (25 Jul, 2022 IST)","startedAt":"2022-07-25T15:24:29Z","lastAt":"2022-07-25T21:52:37Z","messageCount":2,"participants":["Abhradeep Chakraborty","Taylor Blau"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"459893","messageId":"20220725152326.60497-1-chakrabortyabhradeep79@gmail.com","threadId":"58219","inReplyTo":null,"subject":"[GSoC] Abhradeep's GSoC blogs (25 Jul, 2022 IST)","fromName":"Abhradeep Chakraborty","fromEmail":"chakrabortyabhradeep79@gmail.com","sentAt":"2022-07-25T15:23:26Z","receivedAt":"2022-07-25T15:24:29Z","isPatch":false,"sender":{"key":"chakrabortyabhradeep79@gmail.com","avatar":"https://avatars.githubusercontent.com/u/75240995?v=4"},"body":"Hello developers, this is the thread where you can know about\nmy weekly GSoC blog links.\n\nMy Project - Reachability bitmap improvements\n\nBlog update\n------------\n\nTitle - GSoC Week 6: using CRoaring library\nBlog link - https://medium.com/@abhra303/gsoc-week-6-using-croaring-library-be309cfa89f5\n\nSummary -\n\nI missed the week 5 blog update. So this blog covers both\nweek 5 and week 6 work updates. I submitted my latest version\nOf `lookup-table-extension` patch series. There are some issues\nwith CRoaring e.g. it do not store in network byte order (which I\nconfirmed in Roaringbitmap's google group[1]). So, I need to make\nsome changes to fix it. I have already finished implementing\n`roaring_portable_network_serialize` and `..._deserialize`. My\nnext step is to use its functions in Git's codebase. I will\nsubmit the patch series soon.\n\nPrevious blogs \n---------------\n\n-------------------------------------------------------\n\nTitle - GSoC Week 4: diving into roaring bitmaps\nBlog link - https://medium.com/@abhra303/gsoc-week-4-diving-into-roaring-bitmaps-f028f931d873\n\nSummary -\n\nI am thinking of submitting a patch to explain the workings\nof bitmaps. I will be creating a new file 'technical/reachability-\nbitmaps.txt` for that. This week I spent my time on diving more into\nCroaring[1]. I tried to understand how they work internally, the\navailable functions they offer, their serializing format etc.\nThe serialisation format[2] seems fine to me but still I want to\nknow Kaartic and Taylor’s opinions. Another thing I noticed here is\nthat each roaring bitmaps are designed to store sets of 32-bit\n(unsigned) integers. Thus a Roaring bitmap can contain up to 4294967296\nintegers. I am not sure if this is sufficient for us.\nMy next step is to make the new bitmap format version 2(with roaring\nbitmaps) and modify rest of the code so that those code can accept\nthe new bitmap format version.\n\n-------------------------------------------------------\nTitle - GSoC Week 3: working on further improvements\nBlog link - https://medium.com/@abhra303/gsoc-week-3-working-on-further-improvements-13a27db64cd5\n\nSummary -\n\nIn this week, I continued to work on further improvements of \nThe bitmap-lookup-table patch series. Some of the requested\nchanges are (1) Improve the documentation and fix typos (2) add\ncomments (3) Disable `pack.writeBitmapLookupTable` by default\n(4) Fix alignment issues (5) Make a `bitmap_lookup_table_triple`\nstruct (6) Subtract the table_size from index_end irrespective of\nthe value of GIT_TEST_READ_COMMIT_TABLE.\n\nAfter implementing all the requested changes, I started working\non the idea I mentioned in my previous blog as my next step. The\nidea is to stop the xor stack filling loop if the current xor\nbitmap is already stored and assign `xor_bitmap` to it. As this\nbitmap is already stored, we don't need to iterate further as we\nknow all the other bitmaps that are needed to parse this bitmap\nhas already been stored.\n\nMy next step is to roughly implement roaring run bitmaps and\nrun performance tests to check if it's really worth it.\n\n-------------------------------------------------------\nTitle - GSoC Week 2: redesign the table format\nBlog link - https://medium.com/@abhra303/gsoc-week-2-redesign-the-table-format-829dae755a5\n\nSummary - \n\nIn the last week, I worked on the reviews. Some major requested\nchanges are (1) Use commit positions instead of commit oids in\nthe table. (2) Use 8 byte offset positions instead of 4 bytes\n(3) use iterative approach for parsing xor bitmaps (4) Use\n`<commit_pos, offset, xor_pos>` triplets.\n\nWhile implementing these changes, I discovered some bugs in the\nprevious version. I faced errors during this time. But finally\nmanaged to fixed those errors. Taylor helped me to get rid of\nsome errors.\n\nI think that we can optimise the parsing of xor bitmaps further\nby stopping stack filling loop when we get an already parsed\nbitmap since we know that bitmaps having xor relations with it\nhas already been stored/parsed.\n\n------------------------------------------------------- \nTitle - GSoC Week 1: Let's Get started\nBlog link - https://medium.com/@abhra303/gsoc-week-1-lets-get-started-fad78ec34dcf\n\nSummary -\n\nThis is the first blog that I wrote for GSoC. Taylor\nsuggested that I should work on \"integrating a lookup table\nextension\" first as it is smaller compared to other sub-projects.\n\nThe idea is to have a table at the end of .bitmap file which\nwill contain the offsets (and xor-offsets) of the bitmaps of\nselected commits. Whenever git try to get the bitmap of a\nparticular commit, instead of loading each bitmaps one by one,\ngit will parse only the desired bitmap by using the offset and\nxor-offset of the table. This will reduce the overhead of\nloading each and every bitmap.\n-------------------------------------------------------\n"},{"id":"459930","messageId":"Yt8QoUPnZQTB2OQQ@nand.local","threadId":"58219","inReplyTo":"20220725152326.60497-1-chakrabortyabhradeep79@gmail.com","subject":"Re: [GSoC] Abhradeep's GSoC blogs (25 Jul, 2022 IST)","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2022-07-25T21:52:33Z","receivedAt":"2022-07-25T21:52:37Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Abhradeep,\n\nOn Mon, Jul 25, 2022 at 08:53:26PM +0530, Abhradeep Chakraborty wrote:\n> Title - GSoC Week 6: using CRoaring library\n> Blog link - https://medium.com/@abhra303/gsoc-week-6-using-croaring-library-be309cfa89f5\n>\n> Summary -\n>\n> I missed the week 5 blog update. So this blog covers both\n> week 5 and week 6 work updates. I submitted my latest version\n> Of `lookup-table-extension` patch series. There are some issues\n> with CRoaring e.g. it do not store in network byte order (which I\n> confirmed in Roaringbitmap's google group[1]). So, I need to make\n> some changes to fix it. I have already finished implementing\n> `roaring_portable_network_serialize` and `..._deserialize`. My\n> next step is to use its functions in Git's codebase. I will\n> submit the patch series soon.\n\nThanks for another delightful blog post. Like I mentioned off-list, I am\nreally impressed with your progress, and in your ability to reach out\nacross multiple projects in order to make substantial licensing changes.\n\nI'm looking forward to hearing how things go with the CRoaring folks,\nand to helping out where I can. I think that the final implementation of\nRoaring bitmaps into Git's reachability bitmaps will be higher quality\nbecause we're able to rely on existing libraries.\n\nThanks again for all of your hard work. I have your lookup table series\non my list to review right after this, and I think that that should be\ngetting close to being ready.\n\nWell done!\n\nThanks,\nTaylor\n"}]}