{"thread":{"id":"53510","subject":"[GSoC] Blog post on reachability queries","startedAt":"2020-05-20T16:38:55Z","lastAt":"2020-05-21T14:23:03Z","messageCount":2,"participants":["Abhishek Kumar","jnareb@gmail.com"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"398266","messageId":"20200520163653.GA76552@Abhishek-Arch","threadId":"53510","inReplyTo":null,"subject":"[GSoC] Blog post on reachability queries","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-05-20T16:37:22Z","receivedAt":"2020-05-20T16:38:55Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Greetings everyone!\n\nI am working on implementing Generation Number v2. I have written an\narticle about reachability queries, which I feel is necessary background\nfor understanding the project.\n\nHere's the summary of article:\n> Reachability refers to the ability to get from one vertex to another\n> within a graph.\n>\n> Reachability queries are an interesting problem, improving performance\n> for many graph operations. Better and more sophisticated solutions are\n> being created as the size of working graphs keeps increasing.\n>\n> Reachability for the undirected graph can be found in linear\n> preprocessing and constant query time with disjoint set unions. The\n> answer isn't as evident for a directed graph because of differing\n> performance on positive and negative queries, nature and size of graph\n> and other factors. Topological Levels, Post Order DFS Intervals and\n> Contraction Hierachies are some of the building blocks for such\n> algorithms.\n\nIn a later article, I will talk about the specifics of generation number\nfor Git. In particular, how Git uses reachability queries, the need for\nGeneration Number v2 i.e., _Correted Commit Date With Strictly Monotonic\nOffset_ and other interesting tidbits I come across.\n\nYou can find the article here:\n\nhttps://abhishekkumar2718.github.io/programming/2020/05/20/reachability-queries.html\n\nI appreciate any suggestions or feedback.\n\nThanks\nAbhishek\n"},{"id":"398360","messageId":"85tv09weyd.fsf@LAPTOP-ACER-ASPIRE-F5.i-did-not-set--mail-host-address--so-tickle-me","threadId":"53510","inReplyTo":"20200520163653.GA76552@Abhishek-Arch","subject":"Re: [GSoC] Blog post on reachability queries","fromName":"","fromEmail":"jnareb@gmail.com","sentAt":"2020-05-21T14:16:42Z","receivedAt":"2020-05-21T14:23:03Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n> Greetings everyone!\n>\n> I am working on implementing Generation Number v2. I have written an\n> article about reachability queries, which I feel is necessary background\n> for understanding the project.\n\nThank you for your introductory work.  It is always nice to have the\nproblem to be solved well described.\n\nThat said, I am not sure if all this theoretical introduction is needed\nto understand the reachability labeling that Git is using, and is the\ncenterpoint of \"Generation Number v2\", namely the generation number or\ntopological level.\n\n> Here's the summary of article:\n>\n>> Reachability refers to the ability to get from one vertex to another\n>> within a graph.\n>>\n>> Reachability queries are an interesting problem, improving performance\n>> for many graph operations. Better and more sophisticated solutions are\n>> being created as the size of working graphs keeps increasing.\n\nOne caveat: the solution that works for the scale-free small-world graph\nlike citation network might not work for the commit graph, and vice\nversa.  Also, not all algorithms for static graph would work well for\nconstantly growing history graph (for commit graph).\n\nBut it is also what makes it interesting, in my opinion.\n\n>>\n>> Reachability for the undirected graph can be found in linear\n>> preprocessing and constant query time with disjoint set unions. The\n>> answer isn't as evident for a directed graph because of differing\n>> performance on positive and negative queries, nature and size of graph\n>> and other factors. Topological Levels, Post Order DFS Intervals and\n>> Contraction Hierarchies are some of the building blocks for such\n>> algorithms.\n\nAll right.\n\n>\n> In a later article, I will talk about the specifics of generation number\n> for Git. In particular, how Git uses reachability queries, the need for\n> Generation Number v2 i.e., _Corrected Commit Date With Strictly Monotonic\n> Offset_ and other interesting tidbits I come across.\n\nActually, _Corrected Commit Date With Strictly Monotonic Offset_ variant\nof generation number v2 is needed to have *backward compatibility*.  It\nturned out that there was a bug in implementing versioning for\nserialized commit-graph format, namely that unsupported (newer) versions\nof file make Git crash, instead of just not using commit-graph file to\nspeed up operations.\n\nBut it seems that there is a workaround. It happens that if commit graph\nfile is missing the CDAT chunk, then Git wouldn't use it to speed up\noperations, but would not hard fail.  So if we put generation number v2\nin a chunk with different name, e.g. CDA2, we would not need backward\ncompatibility.  Then simpler (and benchmarked) variant of _Corrected\nDate_ would be enough.\n\nThere are advantages and disadvantages of each approach (assuming that\nthe second one actually works as described).  The first is more complex,\nbut backward compatibile with respect to reading (using) commit-graph.\nThe second is simpler, but old Git using new format would get\nperformance regression.\n\n> You can find the article here:\n>\n> https://abhishekkumar2718.github.io/programming/2020/05/20/reachability-queries.html\n\nRegards,\n--\nJakub Narębski\n"}]}