{"thread":{"id":"48411","subject":"[RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","startedAt":"2018-05-04T19:40:48Z","lastAt":"2018-05-15T10:01:20Z","messageCount":10,"participants":["Jakub Narebski","Ævar Arnfjörð Bjarmason","Derrick Stolee","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"346689","messageId":"86zi1fus3t.fsf@gmail.com","threadId":"48411","inReplyTo":null,"subject":"[RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-04T19:40:38Z","receivedAt":"2018-05-04T19:40:48Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nWith early parts of commit-graph feature (ds/commit-graph and\nds/lazy-load-trees) close to being merged into \"master\", see\nhttps://public-inbox.org/git/xmqq4ljtz87g.fsf@gitster-ct.c.googlers.com/\nI think it would be good idea to think what other data could be added\nthere to make Git even faster.\n\n\nCommit-graph format\n===================\n\nA quick reminder: in its current incarnation the commit graph file\nincludes the following data [1]:\n\n1. Some commit data that is just enough for many Git operations:\n - commit parents\n - commit tree (root tree OID)\n - committer date\n\n2. The generation number of the commit. Commits with no parents have\n generation number 1; commits with parents have generation number one\n more than the maximum generation number of its parents.\n\nThe commit-graph file is split into chunks, which theoretically allows\nextending the format wihout need for a version bump... though there is\ncurrently no specified policy about unknown chunks (and understandably\nso, as currently there are not any).\n\nI think it would be good idea to talk about what more could be added to\nbe stored in the commit-graph file.\n\n[1]: https://github.com/git/git/blob/pu/Documentation/technical/commit-graph-format.txt\n\n\nRequirements and recommendations about possible new chunks\n==========================================================\n\nBecause the main goal of commit-graph feature is better performance in\nlarge repositories, any proposed new chunks (or, at higher level, every\nproposed piece of new data) needs to have the following properties.\n\n\n1. First, it needs to have bounded and sensible size. This means that\nthe size of new proposed chunk should be constant, proportional to the\nnumber of commits, or at worst proportional to the number of edges.\n\nFrom the existing chunks, OIDF (OID Fanout) has constant size, both OIDL\n(OID Lookup) and CGET/CDAT (Commit Data) has size proportional to the\nnumber of commits, while not always present EDGE (Large Edge List) has\nsize proportional to the number of \"excess\" edges in \"huge vertices\"\n(octopus merges).\n\n\n2. Second, we want fast access, in most cases fast random access. This\nmeans using fixed-size records. All currently existing chunks have\nrecords (columns) of fixed and aligned size.\n\nThis restriction means that idexes where we have variable amount of data\nper vertex (per commit) are discouraged.\n\n\n3. Third, it needs to be reasonably fast to create, and fast to update.\nThis means time to create the chunk to be proportional to number of\ncommits, or sum of number of commits and edges (which for commit graph\nand other sparse graphs is proprtional to the number of nodes / commits\nanyway). In my opinion time proportional to n*lug(n), where 'n' is the\nnumber of commits, is also acceptable. Times proportional to n^2 or n^3\nare not acceptable.\n\nIt is also strongly preferred that time to update the chunk is\nproportional to the number of new commits, so that incremental\n(append-only) update is possible. The generation numbers index has this\nproperty.\n\n\nGeneric new chunks\n==================\n\nThere are a few ideas for new chunks, new pieces of data to be added to\nthe commit-graph file, that are not connected with some labeling scheme\nfor directed acyclic graphs like GRAIL, FERRARI, FELINE or TF-Label.\nLet's list them here.\n\nIf you have an idea of another bit of information that could be added to\nthe commit-graph file, please tell us.\n\n\nBloom filter for changed paths\n------------------------------\n\nThe goal of this chunk is to speed up checking if the file or directory\nwas changed in given commit, for queries such as \"git log -- \" or\n\"git blame \". This is something that according to \"Git Merge\ncontributor summit notes\" [2] is already present in VSTS (Visual Studio\nTeam Services - the server counterpart of GVFS: Git Virtual File System)\nat Microsoft:\n\nAV> - VSTS adds bloom filters to know which paths have changed on the commit\nAV> - tree-same check in the bloom filter is fast; speeds up file history checks\nAV> - might be useful in the client as well, since limited-traversal is common\nAV> - if the file history is _very_ sparse, then bloom filter is useful\nAV> - but needs pre-compute, so useful to do once\nAV> - first make the client do it, then think about how to serve it centrally\n\n[2]: https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/\n\nI think it was what Derrick Stolee was talking about at the end of his\npart of \"Making Git for Windows\" presentation at Git Merge 2018:\nhttps://youtu.be/oOMzi983Qmw?t=1835\n\nThis was also mentioned in subthread of \"Re: [PATCH v2 0/4] Lazy-load\ntrees when reading commit-graph\", starting from [3]\n[3]: https://public-inbox.org/git/86y3hyeu6c.fsf@gmail.com/\n\nA quick reminder: a Bloom filter is a space-efficient probabilistic data\nstructure that is used to test whether an element is a member of a set.\nFalse negatives are not possible: if a Bloom filter says that the\nelement is not in set, then it certainly isn't. False positives matches\nare possible: if a Bloom filter says that element is in set, then maybe\nit is -- it is possible with some probability that it really is not.\nThe probability depends on number of elements in set, number of bits\nBloom filter uses (with fewer than 10 bits per element are required for\na 1% false positive probability), and number of [independent] hash\nfunctions it uses.\n\nThis Bloom filter can be used to store in a compact and fixed-size way a\nset of files (and possibly also directories) changed by given commit.\nThen when \"git log -- \" is called, Git can quickly check if the\ncommit in question touches given file. If Bloom filter say that it most\nprobably is, only then Git would need to perform a diff to check if it\nactually is (and usually get data to show).\n\nThere are a few problems that needs to be solved, though.\n\n* First, and most important is the performance considerations of\n actually creating Bloom filter. It is very expensive to do the full\n diff for each commit to create Bloom filter.\n\n As Derrick Stolee said in [3]:\n\n DS> My guess is that only server-side operations will need the added\n DS> response time, and can bear the cost of computing them when\n DS> writing the commit-graph file. Clients are less likely to be\n DS> patient waiting for a lot of diff calculations.\n DS>\n DS> If we add commit-graph file downloads to the protocol, then the\n DS> server could do this computation and send the data to all\n DS> clients. But that would be \"secondary\" information that maybe\n DS> clients want to verify, which is as difficult as computing it\n DS> themselves.\n\n* What to do about merge commits, and octopus merges in particular?\n Should Bloom filter be stored for each of the parents? How to ensure\n fast access then (fixed-width records) - use large edge list?\n\n* Then there is problem of rename and copying detection - I think we can\n simply ignore it: unless someone has an idea about how to handle it?\n\n Though this means that \"git log --follow \" wouldn't get any\n speedup, and neither the half of \"git gui blame\" that runs \"git blame\n --incremental -C -C -w\" -- the one that allows code copying and\n movement detection.\n\nOne possible way of solving the issue of large amount of work required\nto compute Bloom filter could be updating it as a side effect of\noperation that calculates full diff anyway (like \"git log -p\" or \"git\nshow\") if the commit is in commit-graph file. We would need then some\nspecial value that marks Bloom filter as not filled in (in addition to\nthe one saying that there were too many changes, and the one saying that\nthere were no changes at all - as rare as the latter might been).\n\nBecause not all queries that require calculating diff do it for full\nhierarchy, maybe additionally there could be a additional field denoting\nthe depth to which diff and changed files were calculated. For example\ndepth of 1 means that only top-level files and top-level directories\nwere added to Bloom filter, so you can only verify the first component\nof the path to check if it could have been changed. Zero depth may mean\nunlimited.\n\nA final note: Git would use this Bloom filter for changed files in quite\ndifferent way than is this structure typical use case: instead of\nchecking large number of elements against given Bloom filter, Git would\nbe checking given element against large amount of Bloom filters. This\nmeans that the optimization people came up with, like fast-forward Bllom\nfilters (https://github.com/efficient/ffbf) wouldn't necessary help.\n\n\nCommit-graph validity\n---------------------\n\nOne problem with commit-graph feature that needs to be solved is that it\nstores one particular view of the project history, and there exist\nfeatures that change it. Beween writing commit-graph file and using it,\ncommits may have been replaced by commits with different parents,\nshallow clone may have been shortened or deepened, or grafts file may\nhave been edited.\n\nOne possible solution would be to automatically turn off commit-graph if\nany of those features is present. For shallow clone it may even be\nacceptable solution - the hstory is shortened, so the queries are fast\nanyway, and commit-graph is less needed.\n\nIf we join the working repository with the historical one (via grafts or\nreplacements) to examine the full history of a project, last thing we\nwould want is to make operations slower.\n\nA possible way of solving this would be to add a chunk which says for\nwhat combination of graft file content, shallow file content, and the\nstate of replace refs given commit-graph file is valid for. If they do\nnot match, Git would not use commit-graph feature and fall back on\nordinary slower mechanism of answering queries.\n\nMoreover, with this solution, when shallow clone changes its depth\n(e.g. with 'git fetch --deepen=' or 'git fetch --unshallow), or\nwhen a replacement is added with 'git replace', Git can either update\ncommit-graph file, or update the validity - saying that commit-graph\nfile is valid for the new state. The latter is more important for\ngit-replace, which does not need to affect history at all. There isn't\nanything like that for grafts, but the mechanism is deprecated anyway,\nand I am not opposed to just turning off commit-graph feature if there\nis grafts file present: this could help convince people to upgrade to\ngit-replace, which should be easy now thanks to the new\n--convert-graft-file option.\n\nThe verification could be as simple as verification hash / check over\ncontents of grafts file, over contents of shallow file, and over\nreplacement refs represented as fragment of packed-refs file.\n\n\nTopographical ordering of commits\n---------------------------------\n\nThe idea is simple: store topological order of commits, so that 'git log\n--topo-order' and 'git log --graph' are faster.\n\nThis could be done with two chunks: one storing the position of given\ncommit in topological order (commits sorted by their OID, like for\nmetadata), and list of commits in topological order. The first chunk\ncan also be thought of as the index into later.\n\nThis way it would be possible to list commits in topological order\nstarting at given commit, and ending at given commit or after given\nnumber of commits.\n\nThe problem is with updating this data. It should be possible to update\na topological order, but I am not sure if it would be possible to update\ntopological order based only on changed files and existing order to\nstill fulfill the criteria on --topo-order:\n\n --topo-order ::\n Show no parents before all of its children are shown, and avoid\n showing commits on multiple lines of history intermixed.\n\nThe second requirement may (or may not be) hard to fulfill when updating.\n\n\nBitmap indices indicator\n------------------------\n\nBitmap index is supported since 2015 for Git itself [4], and since at\nleast 2013 for JGit [5]. The main goal of this feature was to improve\nthe \"counting objects\" phase of clone and fetch performance.\n\nA quick reminder: bitmap index file is computed per packfile, and it\nrefers to objects by their position in packfile. Bitmap index can be\ncurrenly generated only for a packfile with full closure (i.e. where\nevery single object in the packfile can find its parent links inside the\nsame packfile).\n\nA single bitmap in a bitmap index file is a bit vector, where i-th\nposition (i-th bit of bitmap) corresponds to the i-th object in\npackfile. There are 4 bitmaps that act as type indexes, for example\ncommit type index has \"1\" on i-th position if i-th object in packfile is\na commit object. There are also N entries for commits, where i-th bit\nin bitmap for given commit denotes whether i-th object is reachable from\nthe commit this bitmap is for.\n\nI think that bitmap indexes does not see much use when Git needs to\nanswer reachability query; correct me if I am wrong here. Maybe some\nkind of indicator that given commit has reachability bitmap in some\nbitmap file could help?\n\nAs soon as we arrive at commit for which reachability bitmap exist,\nanswering reachability query is easy: just find out the position of the\ncommit we want to check if it is reachable in same packfile, and if i-th\nbit in bitmap is \"1\" then it is reachable. Finding path is slightly\nmore involved: just use reachability bitmap to steer walk, always\nchoosing only reachable parents.\n\nI don't know if we can find merge-base, also known as lowest common\nancestor (or sometimes as greatest common ancestor) with reachability\nbitmaps. You can easily find *all* ancestors (with bitwise AND\noperation on bitmaps). Maybe starting from the ones that have highest\ngeneration numbers we can remove redundant ancestors (with AND NOT --\nbut not all commits have reachability bitmaps).\n\nI wonder if it would be better to store indicators that commit has\nreachability bitmap (and in which packfile, if it is possible with\nmentioned restriction to have more than one bitmap file) in commit-file,\nor if it would be easier when reading commit-graph information into\nmemory to simply read bitmap file for this information and add it to\nin-memory representation.\n\n[4]: http://githubengineering.com/counting-objects/\n[5]: https://www.eclipsecon.org/2013/sites/eclipsecon.org.2013/files/Scaling%20Up%20JGit%20-%20EclipseCon%202013.pdf\n\n\nAs this post is getting long, I'll post other ideas, about commit\nlabeling for faster reachability queries in a separate email.\n\nRegards,\n-- \nJakub Narębski\n"},{"id":"346691","messageId":"87in83xjzl.fsf@evledraar.gmail.com","threadId":"48411","inReplyTo":"86zi1fus3t.fsf@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-05-04T20:07:42Z","receivedAt":"2018-05-04T20:07:50Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 04 2018, Jakub Narebski wrote:\n\n> With early parts of commit-graph feature (ds/commit-graph and\n> ds/lazy-load-trees) close to being merged into \"master\", see\n> https://public-inbox.org/git/xmqq4ljtz87g.fsf@gitster-ct.c.googlers.com/\n> I think it would be good idea to think what other data could be added\n> there to make Git even faster.\n\nThanks for the write-up.\n\n> 3. Third, it needs to be reasonably fast to create, and fast to update.\n> This means time to create the chunk to be proportional to number of\n> commits, or sum of number of commits and edges (which for commit graph\n> and other sparse graphs is proprtional to the number of nodes / commits\n> anyway). In my opinion time proportional to n*lug(n), where 'n' is the\n> number of commits, is also acceptable. Times proportional to n^2 or n^3\n> are not acceptable.\n\nI don't think this requirement makes sense...\n\n> DS> If we add commit-graph file downloads to the protocol, then the\n> DS> server could do this computation and send the data to all\n> DS> clients. But that would be \"secondary\" information that maybe\n> DS> clients want to verify, which is as difficult as computing it\n> DS> themselves.\n\n... when combined with this. If hypothetically there was some data that\nsignificantly sped up Git and the algorithm to generate it was\nridiculously expensive, that would be fine when combined with the\nability to fetch it pre-generated from the server. There could always be\nan option where you trust the server and optionally don't verify the\ndata, or where it's much cheaper to verify than compute.\n"},{"id":"346692","messageId":"87h8nnxio8.fsf@evledraar.gmail.com","threadId":"48411","inReplyTo":"86zi1fus3t.fsf@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-05-04T20:36:07Z","receivedAt":"2018-05-04T20:36:14Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 04 2018, Jakub Narebski wrote:\n\n(Just off-the cuff here and I'm surely about to be corrected by\nDerrick...)\n\n> * What to do about merge commits, and octopus merges in particular?\n> Should Bloom filter be stored for each of the parents? How to ensure\n> fast access then (fixed-width records) - use large edge list?\n\nYou could still store it fixed with, you'd just say that if you\nencounter a merge with N parents the filter wouldn't store files changed\nin that commit, but rather whether any of the N (including the merge)\nhad changes to files as of the their common merge-base.\n\nThen if they did you'd need to walk all sides of the merge where each\ncommit would also have the filter to figure out where the change(s)\nwas/were, but if they didn't you could skip straight to the merge base\nand keep walking.\n\nWhich, on the topic of what else a commit graph could store: A mapping\nfrom merge commits of N parents to the merge-base of those commits.\n\nYou could also store nothing for merges (or only files the merge itself\nchanged v.s. its parents). Derrick talked about how the bloom filter\nimplementation has a value that's \"Didn't compute (for whatever reason),\nlook at it manually\".\n\n> * Then there is problem of rename and copying detection - I think we can\n> simply ignore it: unless someone has an idea about how to handle it?\n>\n> Though this means that \"git log --follow \" wouldn't get any\n> speedup, and neither the half of \"git gui blame\" that runs \"git blame\n> --incremental -C -C -w\" -- the one that allows code copying and\n> movement detection.\n\nCouldn't the bloom filter also speed up --follow if you did two passes\nthrough the history? The first to figure out all files that ever changed\nnames, and then say you did `--follow sha1-name.c` on git.git. The\nfilter would have had all the bits for both sha1_name.c and sha1-name.c\nset on all commits that touched either for all of the history.\n\nOf course this would only work with a given default value of -M, but\non the assumption that most users left it at the default, and\nfurthermore that renames weren't so common as to make the filter useless\nwith too many false-positives as a result, it might be worth it. If you\n"},{"id":"346717","messageId":"86h8nm2pv8.fsf@gmail.com","threadId":"48411","inReplyTo":"87h8nnxio8.fsf@evledraar.gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-05T13:28:43Z","receivedAt":"2018-05-05T13:28:52Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n> On Fri, May 04 2018, Jakub Narebski wrote:\n>\n> (Just off-the cuff here and I'm surely about to be corrected by\n> Derrick...)\n>\n>> * What to do about merge commits, and octopus merges in particular?\n>> Should Bloom filter be stored for each of the parents? How to ensure\n>> fast access then (fixed-width records) - use large edge list?\n>\n> You could still store it fixed with, you'd just say that if you\n> encounter a merge with N parents the filter wouldn't store files changed\n> in that commit, but rather whether any of the N (including the merge)\n> had changes to files as of the their common merge-base.\n\nWell, that is one solution: to store union of changes (sum of changes)\nfrom all parents of a merge commit in a Bloom filter for a merge.\n\nBut this wouldn't help us to skip merge entirely, because which parent\nwe would walk then? But perhaps I am mistaken, and that does not\nmatter.\n\n> Then if they did you'd need to walk all sides of the merge where each\n> commit would also have the filter to figure out where the change(s)\n> was/were, but if they didn't you could skip straight to the merge base\n> and keep walking.\n\nAnother solution that I thought of is to use the same mechanism that\ncommit-graph file uses for storing merges: store Bloom filters for first\ntwo parents, and if there are more parents (octopus merge), store Bloom\nfilters for the remaining parents in large edge extension for Bloom\nfilters.\n\nThis meant accepting some padding waste for CDAT chunk, to have faster\naccess. We could do the same for Bloom filters, but it may mean quite a\nbit of waste, depending on how many bits Bloom filter would use... but\nthere is another solution: for merge commits store Bloom filters for\nfirst two parents that are half the size - this means of course more\nfalse positives, but it may be acceptable solution.\n\n> Which, on the topic of what else a commit graph could store: A mapping\n> from merge commits of N parents to the merge-base of those commits.\n\nThe problem is that those N parents may have more than one merge-base,\nand if so then those merge-bases may have also multiple merge-bases,\nrecursively (what 'recursive' merge strategy handles). Though this\ncould be solved with 'large merge-base list' extension, just like\nexisting EDGE chunk - I think we can assume that most merge parents have\nonly single merge-base (but I have not checked this).\n\n> You could also store nothing for merges (or only files the merge itself\n> changed v.s. its parents). Derrick talked about how the bloom filter\n> implementation has a value that's \"Didn't compute (for whatever reason),\n> look at it manually\".\n\nRight, another solution could be to store nothing for merges, or store\nBloom filter for changes against only first parent. The goal of Bloom\nfilter is to avoid calculating diff if we don't need to.\n\nDerrick, could you tell us what solution VSTS uses for Bloom filters on\nmerge commits? Thanks in advance.\n\n>> * Then there is problem of rename and copying detection - I think we can\n>> simply ignore it: unless someone has an idea about how to handle it?\n>>\n>> Though this means that \"git log --follow \" wouldn't get any\n>> speedup, and neither the half of \"git gui blame\" that runs \"git blame\n>> --incremental -C -C -w\" -- the one that allows code copying and\n>> movement detection.\n>\n> Couldn't the bloom filter also speed up --follow if you did two passes\n> through the history? The first to figure out all files that ever changed\n> names, and then say you did `--follow sha1-name.c` on git.git. The\n> filter would have had all the bits for both sha1_name.c and sha1-name.c\n> set on all commits that touched either for all of the history.\n>\n> Of course this would only work with a given default value of -M, but\n> on the assumption that most users left it at the default, and\n> furthermore that renames weren't so common as to make the filter useless\n> with too many false-positives as a result, it might be worth it. If you\n\nI think it would be much simpler to just ensure that we store in Bloom\nfilter as changed files also pure renames, and leave doing rename\ndetection to the walk. This way we do not fix old rename detecion\nalgorithm in stone.\n\nThe walk would simply change the name of file it would ask Bloom filters\nabout.\n\nThank you for your comments,\n-- \nJakub Narębski\n"},{"id":"346823","messageId":"86muxcuyod.fsf@gmail.com","threadId":"48411","inReplyTo":"86zi1fus3t.fsf@gmail.com","subject":"[RFC] Other chunks for commit-graph, part 2 - reachability indexes","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-06T23:55:30Z","receivedAt":"2018-05-06T23:55:43Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Hello,\n\nIn previous email I wrote:\n\nJN> As this post is getting long, I'll post other ideas, about commit\nJN> labeling for faster reachability queries in a separate email.\n\nThis is this email.\n\n\nHere is second part of series dedicated to discussing what other data,\nlike various reachability indexes / labeling could be added to the\ncommit-graph file (as new chunks) to make Git even faster.\n\nBy reachability I mean answering the question whether commit A can reach\ncommit B, or in other words if commit B is an ancestor of commit A.\nThis type of query is used in many Git operations.\n\nThe commit-graph has one such reachability index built-in already, in\nthe form of generation numbers; this index is called level or\ntopological level of node / vertex in the literature / articles about\ngraph algorithms.\n\n> 2. The generation number of the commit. Commits with no parents have\n> generation number 1; commits with parents have generation number one\n> more than the maximum generation number of its parents.\n\nI have played a bit with various reachability indexes, starting with the\nones described in \"Reachability Queries in Very Large Graphs: A Fast\nRefined Online Search Approach\" (FELINE index) paper by Renê R. Veloso,\nLoïc Cerf, Wagner Meira Jr and Mohammed J. Zaki (2014), available in the\nPDF form at https://openproceedings.org/EDBT/2014/paper_166.pdf\n\nI have started working on Jupyter Notebook on Google Colaboratory to\nfind out how much speedup we can get using those indexes for Git\nlarge-ish commit graphs (which turns out to be quite specific type of\ngraph, more about which later), namely git.git and Linux kernel ones.\n\nThe Jupyter Notebook (which runs on Google cloud, but can be also run\nlocally) uses Python kernel, NetworkX librabry for graph manipulation,\nand matplotlib (via NetworkX) for display.\n\nAvailable at:\nhttps://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\nhttps://drive.google.com/file/d/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg/view?usp=sharing\n\nAt current size it started to be a bit unwieldy, especially recomputing\nit from the start, so I am thinking about splitting it up and moving it\nto GitHub; then I can e.g. put code and data in separate files, so they\ndo not have to be recalculated (cloning full Linux repository takes\nquite a bit of time). I have started the process: first step which is\ncopy of Colaboratory notebook is now available as the following repo:\nhttps://github.com/jnareb/git-commit-graph-ext\nhttps://github.com/jnareb/git-commit-graph-ext/blob/master/Graphs_FELINE_index.ipynb\n\n\nLet's start with the reminder from part 1:\n\n> Requirements and recommendations about possible new chunks\n> ==========================================================\n>\n> Because the main goal of commit-graph feature is better performance in\n> large repositories, any proposed new chunks (or, at higher level, every\n> proposed piece of new data) needs to have the following properties.\n>\n>\n> 1. First, it needs to have bounded and sensible size. This means that\n> the size of new proposed chunk should be constant, proportional to the\n> number of commits, or at worst proportional to the number of edges.\n>\n> From the existing chunks, OIDF (OID Fanout) has constant size, both OIDL\n> (OID Lookup) and CGET/CDAT (Commit Data) has size proportional to the\n> number of commits, while not always present EDGE (Large Edge List) has\n> size proportional to the number of \"excess\" edges in \"huge vertices\"\n> (octopus merges).\n>\n>\n> 2. Second, we want fast access, in most cases fast random access. This\n> means using fixed-size records. All currently existing chunks have\n> records (columns) of fixed and aligned size.\n>\n> This restriction means that idexes where we have variable amount of data\n> per vertex (per commit) are discouraged.\n>\n>\n> 3. Third, it needs to be reasonably fast to create, and fast to update.\n> This means time to create the chunk to be proportional to number of\n> commits, or sum of number of commits and edges (which for commit graph\n> and other sparse graphs is proprtional to the number of nodes / commits\n> anyway). In my opinion time proportional to n*lug(n), where 'n' is the\n> number of commits, is also acceptable. Times proportional to n^2 or n^3\n> are not acceptable.\n>\n> It is also strongly preferred that time to update the chunk is\n> proportional to the number of new commits, so that incremental\n> (append-only) update is possible. The generation numbers index has this\n> property.\n\nThough as Ævar said in response, which I agree with:\n\nÆB> If hypothetically there was some data that significantly sped up Git\nÆB> and the algorithm to generate it was ridiculously expensive, that\nÆB> would be fine when combined with the ability to fetch it\nÆB> pre-generated from the server. There could always be an option where\nÆB> you trust the server and optionally don't verify the data, or where\nÆB> it's much cheaper to verify than compute.\n\nhttps://public-inbox.org/git/86h8nm2pv8.fsf@gmail.com/T/#mdbc6a4ef052ae95136faf6d243d0c29ddfac58a8\n\n\nTypes of algorithms to speed up reachability queries\n====================================================\n\nThe [research] issue for answering reachability queries is to find a\ntradeoff between the online processing cost and the offline processing\ncost. All different approaches aim to find a trade-off among three main\ncosts: (a) query time which is the time to answer a reachability query\nonline [which for Git would be time to perform operation such as `git\nbranch --contains`], (b) construction time which is the time to\nconstruct an index offline [which for Git would be time for client or\nserver to create commit-graph file data], and (c) the index size which\nis the space needed to maintain the index [which for Git would be the\nsize of commit-graph file].\n\nWe can classify existing works / existing algorithms into two\ncategories. The two main approaches are Label-Only and Label+G. The\nLabel-Only approach is to answer reachability queries using the labels\ncomputed only (this includes transitive closure compression and hop\nlabeling / transitive closure factorization methods). The Label+G\napproach is to make use of the labels computed as much as possible, but\nit may need to traverse the graph G (it also called refined online\nsearch). The main idea behind Label+G is to reduce the time to\nconstruct an effective index, since the computing cost to create\neffective Label-Only index can be very high.\n\nNote: this categorization is taken from the IP paper.\n\nBeside those two groups there also exists so called boosting frameworks.\nThis algorithms try to reduce answering reachability query on very large\ngraph to answering reachability queries on smaller graph (reachability\nbackbone in case of SCARAB framework, reduced/simplified graph in case\nof DAG Reduction method).\n\nLet's table boosting frameworks for later (for example to examine\nwhether SCARAB could be used to choose which commits should have\nreachability bitmaps). If we follow \"Requirements and recommendations\nabout possible new chunks\", then we can limit examinations to Label+G\napproaches. Besides, commit-graphs can get large enough so that\nLabel-Only approaches starts to get unfeasible: index creation time and\nindex size gets very large.\n\n\nCommit graph characteristics\n============================\n\nBut first lets try to address the elephant in the room: would those\nalgorithms work well for the graph of revisions?\n\nThese methods are usually evaluated on a variety of real graph datasets,\nboth small and large, as well as large synthetic ones. The real graphs\ndatasets include XML documents, genome databases, citation networks,\nsemantic knowledge databases and ontology terms, taxonomies, social\nnetworks and web graphs.\n\nIt turns out that graph of revisions has size (number of nodes) that for\nlarge repositories number of commits/nodes (50k for git.git, 750k for\nLinux kernel, 1.7M for MS Windows) falls somewhere in the middle between\nsize of small graphs with 6k to 40k nodes and size of large graphs, most\nof which has number of nodes staring from 1.5M and bigger.\n\nMany of those example graphs (that are used for evaluation of\nreachability algorithms) are approximately scale-free, with relative\ncommonness of vertices with a degree that greatly exceeds the average --\nwhich is not the case for graph of revisions. Some approaches include\nspecial handling for those vertices to speed up queries; this probably\nis not needed for DAG of commits, and I will skip these parts for now.\n\nCommit graphs are sparse graphs, with average number of parents (the\nratio of edges to nodes in graph) below 2.0; even closer to 1.\n\nOne major difference is that in those graphs the percentage of\nreachability queries that are answered negatively over all possible\nreachability queries is over 90%. On the other hand, the ratio of\nreachability queries that are answered positively over all possible\nreachability queries is very small; this ratio is called\nreachability-ratio (or simply R-ratio), usually denoted as 'r'. For\nthose real graph datasets, the R-ratio is between 2.1e-1 to 1.3e-7. But\nfor graph of revision (based on sample of one) it looks like this\nR-ratio is around 4.5e-1 (with, if I am not mistaken, maximum R-ratio\npossible in DAGs being 0.5 or 5.0e-1, that is 50%). This may affect the\nevaluation of method for commit graphs; on the other hand as positive\nqueries are more interesting, some works do evaluations separately in\npositive and negative queries, or on equal mixure of positive and\nnegative queries.\n\nAnother issue is that many of those \"evaluation\" graphs usually have the\nlarge number of sources (nodes with only outgoing edges, \"roots\" in\ngraph terminology, \"tips\" or \"heads\" in Git terminology -- childless\nnodes) or/and the large number of sinks (nodes with no outgoing edges,\n\"leafs\" in graph terminology, \"roots\" in Git terminology -- parentless\nnodes). This seems to matter for FELINE index, which as my experiments\nin mentioned Jupyter notebook shows is much less efective on commit\ngraphs than indicated in original work. Note that while live\nrepositories would have much larger amount of branches than public\nrepositories (that I have used for tests) where there are only a few\nlong-lived public branches, even for Windows repo it is small percentage\nof total number of nodes / commits (the Windows repo according to the\nGit Merge 2018 presentation by Derrick has 90k branches and 1700k\ncommits; it is not as where 1/4 of nodes were source nodes).\n\n\nNegative and positive-cut filters, false negatives and false positives\n======================================================================\n\nIn Label+Graph approaches, indexing (node/edge labels) is enough to\nanswer some queries in constant time.\n\nIf the indexing can answer positive queries in constant time we call it\n_positive-cut filter_. This means that querying the index can state\nthat node B is reachable from node A (positive result); reaachability is\nguaranteed. However if we don't get such answer from the index, we\ndon't know if B is reachable from A, or if B is not reachable from A.\nThe case where B is reachable from A, but the index doesn't say it, we\ncan call _false negatives_: we get negative answer from the index, while\nthe actual ressult of reachability query is positive.\n\nIf the indexing can answer negative queries in constant time we call it\n_negative-cut filter_. This means that querying the index can state\nthat node B is definitevly not reachable from node A (negative result).\nOtherwise we don't know if B is or is not reachable from A. The case\nwhere there is no path from A to B, but the index doesn't say it, we can\ncall _false positives_ or _falsely-implied path_.\n\nGeneration numbers (or topological levels) are an example of negative\ncut filter. If gen(A) < gen(B) then A cannot reach B.\n\nNote: The terminology used here is taken from the FELINE paper (which\ndoes not necesarily mean that it originated here; it appears in earlier\nGRAIL paper too).\n\nWhen one wants just to find if there exist path from A to B, both\npositive-cut and negative-cut filters can be used.\n\n Data: (u, v) ∈ V^2, two vertices of the DAG\n Result: r(u, v), whether v is reachable from u\n Note: simplified DFS algorithm, no visited filter\n begin\n if positive-cut(u, v) then\n return true;\n if u == v then\n return true;\n if not negative-cut(u, v) then\n forall the w ∈ parents(u) do\n if Reachable(w, v) then\n return true;\n\n return false;\n\nThis is the case for '--contains' and '--merged' queries in Git.\n\nWhen one wants to find a single path from A to B if it exists, then both\nnegative-cut and most positive-cut filters can be used.\n\nWhen one wants to find out all paths from A to B (e.g. for `git log A ^B\n--strict-ancestor`) then in most cases only negative-cut filters are\nreally useful.\n\n\nOnline search algorithms\n========================\n\nWhen the index or indexes used cannot answer reachability query by\nitself, one needs to perform a search from the source node to the target\nnode, applying positive-cut and negative-cut filters to reduce search\nspace.\n\nOne possible solution, often used for rechability testing in various\nworks, is to perform depth-first search (DFS). This can be done simply\nby using recursion (like in the above pseudo-code), but for large graphs\none need to use iterative approach by employing stack. DFS is needed to\ncompute some of the reachability indexes.\n\nHowever DFS it is not always the best strategy. Breadth-first search\n(BFS) guarantees to find the shortest path with the cost of using more\nmemory. In average, BFS is expected to be faster considering the cases\nwhere the target node is close to the source node that has a large\nreachability set. This is especially true for graphs of revisions, that\nare deep but narrow (their width is much smaller than their depth;\nmaximum number of commits with the same generation number is much\nsmaller than maximum generation number). In BFS we store nodes to be\nwalked in a queue.\n\nBesides the standard graph search strategies of DFS and BFS, sometimes\nthere is also considered bidirectional breadth-first search (BBFS),\nwhich has a few advantages over BFS. In bidirectional search two BFS are\nstarted simultaneously utilizing separate queues: one starting from\nsource node and going forward, and one starting from target node and\ngoing backward (walking the reverse of DAG). The first advantage of\nbidirectional search is that it can answer positive queries faster when\nthe average degree of the graph is high. In negative queries, the worst\ncase scenario is that bidirectional search takes twice as much time as a\nBFS would take; however there are substantial amount of cases where\nbidirectional search is much faster than BFS.\n\nSome indexes are geared towards making BBFS faster; this needs to be\ntaken into account when evaluating them, as we would not want to have to\ndeal with reversed commit graph.\n\nGit actually uses a variant of BFS in paint_down_to_commin() in\ncommit.c, where it uses priority queue, sorted by generation number then\nby date. We can say that it is closest-first search variant of BFS.\n\n\nReachability indexes\n====================\n\nThe Label+Graph approaches to include the following algorithms to speed\nup reachability queries:\n\n- Tree+SPPI (2005)\n (Surrogate & Surplus Predecessor Index)\n- GRIPP (2007)\n (GRaph Indexing based on Pre- and Postorder numbering)\n+ GRAIL (2010 & 2012)\n (Graph Reachability indexing via rAndomized Interval Labeling)\n* PReaCH (2014)\n (Pruned Reachability Contraction Hierarchies)\n+ FERRARI (2013)\n (Flexible and Efficient Reachability Range Assignment for gRaph Indexing)\n+ FELINE (2014)\n (Fast rEfined onLINE search)\n+ IP (2014)\n (Independent Permutation labeling approach)\n+ BFL (2016)\n (Bloom Filter Labeling)\n\nAlgorithms prefixed with '-' are those older ones usually compared\nagainst in different works that I won't cover here while algorithms\nprefixed with '+' are those that I will cover somewhat. Algorithms\nprefixed with '*' are less known works that I think might be\ninteresting.\n\n\nLevels / generation numbers\n---------------------------\n\nOne of the simplest negative-cut filters, used by almost all works as a\nsupplementary filter... and also by Git's commit-graph feature. The\ngeneration number, or [topological] level is defined as length of\nshortest path from a sink node (\"root\" in Git terminology). You can also\ndefine \"reverse\" or \"backward\" levels starting from source nodes, and\nsome works use that.\n\nMore useful in actually computing generation number for a commit, or\nlevel of a node is recursive definition given at the beginning of this\nemail. Note that usually nodes without outgoing edges (\"root\" nodes)\nare assigned level zero, but giving it value of one like commit-graph\nfeature does is also valid convention.\n\nThe recursive definition shows that it is possible to calculate\ngeneration numbers incrementally. In particular the cost of updating\ngeneration numbers is proportional to the number of new commits. This\nis not the case for \"reverse\" level numbers -- we won't consider it\nthen.\n\nGeneration numbers / topological levels are denoted using gen(B) symbol\nin commit-graph documentation and commit messages, and l_u or L(u) in\nworks about graph reachability algorithms. Let's use gen(A) here.\n\nThe following holds true:\n\n If A can reach B, and A != B, then gen(A) > gen(B)\n\nThis means that we get the following negative cut condition (this\ncondition is equivalent to the one above):\n\n If gen(A) <= gen(B) and A != B, then A cannot reach B\n\nSometimes it is easier to make use of the weaker negative-cut condition:\n\n If gen(A) < gen(B), then A cannot reach B\n\n\nTopological ordering\n--------------------\n\nA topological sort or topological ordering of a directed acyclic graph\nis a linear ordering of its vertices such that for every directed edge\n(u,v) from vertex u to vertex v, u comes before v in the ordering. Any\nDAG has at least one topological ordering, and algorithms are known for\nconstructing a topological ordering of any DAG in linear time.\n\nA topological ordering should be able to be updated quite easily, while\nthe reverse topological ordering should be able to be updated in time\nproportional to the number of added commits (though there are no\nguarantees about properties of such topological order).\n\nThe following holds true:\n\n If A can reach B, and A != B, then topo(A) > topo(B)\n If A can reach B, then topo(A) >= topo(B)\n\nBecause this is ordering, we also have that if topo(A) <= topo(B) and\ntopo(A) >= topo(B), then A = B; if topo(A) = topo(B) then A = B.\n\nThis means that we have the following negative-cut condition:\n\n If topo(A) < topo(B), then A cannot reach B\n\nThe condition is reversed for the reverse topological ordering.\n\nNote: The FELINE index can be thought of as composed of two topological\nordering, where the second ordering is constructed using heuristic\nalgorithm in such way that it tries to minimize number of false\npositives (falsely-implied paths) for the combination of those two\ntopological sort negative-cut filters.\n\n\nPost-order in spanning tree\n---------------------------\n\nDirected rooted tree is a directed graph in which, for a vertex u called\nthe [tree] root and any other vertex v, there is exactly one directed\npath from u to v. A spannig tree of a directed acyclic graph G is a\nsubgraph that is a tree or set of trees (directed rooted tree for DAG)\nwhich includes all of the vertices of graph G. Source nodes of G are\nroots of spanning trees of G.\n\nThe reachability problem on trees can be solved effectively by interval\nlabeling, which takes linear time and space for constructing the index,\nand provides constant time querying. Given a tree/forest T, interval\nlabeling assigns each node a label I(u) = [s_u, e_u] which represents\ninterval starting at s_u and ending at e_u. A desired labeling\nsuitable for answering reachability queries in trees must satisfy the\ncondition that I(u) subsumes I(v), or in other words interval I(v) is a\nsubset of interval I(v) if and only if u reaches v.\n\nOne such labeling is _min-post labeling_ method for trees. In this\nlabeling e_u = post(u) is the post-order value of the node u, defined as\nthe rank of the node u in a post order traversal of the tree. The\nstarting value of the interval s_u is defined as the lowest post-order\nrank for any node x in the subtree rooted at u (i.e., including u).\nNote that because of how this interval was defined the check\nI(v) ⊆ I(u) can be replaced by simpler post(v) ∈ I(u).\n\nPre order traversal of tree gives _pre-max labeling_ method for trees,\nexactly equivalent to the min-post labeling described above.\n\nThis method used for a spanning tree gives positive-cut filter: if it\ngives positive results for u ---> v query, then node v is reachable from\nu via spanning tree. If the answer from spanning tree labeling is\nnegative, node v can still be reachable from u, but via non-tree edge.\nThis is the idea behind positive-cut filter in GRAIL method, and this is\nalso positive-cut filter used in FELINE work/paper. GRAIL calls this\npositive-cut interval an interior interval.\n\n\nThe post-order or pre-order labeling of spanning tree is also labeling\nof nodes in the original DAG. Hence for negative-cut filter we can\nassign to each node u the interval starting at minimum of labels of\nnodes reachable in the DAG from u, and ending at maximum of labels of\nnodes reachable in the DAG from u. Then if node v has label outside\nthis interval I'(u), then u cannot reach v. GRAIL calls this\nnegative-cut interval an exterior interval.\n\nNow if the traversal of tree was done using DFS (depth-first search),\nthen the ending of min-post interval I(u) for a spanning tree is also\nend of interval I'(u) for DAG. Moreover the minimum of post(v) for\nnodes reachable from u, that is the starting point for the DAG interval,\ncan be calculated iteratively during post-order traversal of the tree.\n(It is possible that DFS is not needed; PReaCH work proves it for DFS,\nbut I have not examined proof in GRAIL work in detail). GRAIL approach\nuses those two intervals together: the interval label for node u is\ngiven as I(u) = [s_u, m_u, e_u ], where EI(u) = [s_u, e_u] and\nII(u) = [m_u, e_u] are the exterior (negative-cut) and interior\n(positive-cut) intervals respectively.\n\nThe motivating idea in GRAIL is to use interval labeling multiple times,\nfor multiple random spaanning trees to improve searching phase\n(answering reachability queries). The GRAIL work proposes several\nheuristics how to choose best set of spanning trees. The recommended\nnumber of those trees for large graphs is k = 5.\n\nUsing multiple spanning trees is not the only solution. Alternative is\ntrying to get more out of single DFS numbering. PReaCH work\n(arXiv:1404.4465) adds one more possible and possibly large positive-cut\ninterval (called \"full\" interval there), and possibly one more\nnegative-cut interval (called \"empty\" interval). Note that the original\nwork uses pre-order numbering and pre-max intervals, but the result can\nbe easily translated to post-numbering and min-post intervals (I have\ndone this in mentioned Jupyter notebook).\n\nThe additional positive-cut interval for node u, if it exists, is the\npositive-cut interval for a node w = p_tree(u) that is reachable from u\nand not in positive-cut interval of u, and has maximum size of said\npositive-cut interval. This can be computed iteratively, while\ncomputing post-number ordering on u. This seems promising for graph of\nrevisions.\n\nOne can also find additional negative-cut interval, finding f_gap so\nthat [f_gap, min] is \"empty\" interval, and the negative cut is split\nfrom [f_min, post] to two intervals: [f_min, f_gap] and [min, post].\nThis also can be computed iteratively.\n\n\nThe FERRARI approach is more generic. It starts with the fact that the\nreachable set R(v) of a vertex v in the DAG is only partly represented\nby the spanning tree interval I_T(v), as the tree interval only accounts\nfor reachability relationships that are preserved in tree T. The\nreachable set R(v) can be represented as set of intervals II(v). The\nresulting index (collection of reachable interval sets) can be regarded\nas a materialization of the transitive closure of the graph, which gets\ntoo large and is thus infeasible for large graphs.\n\nInstead of storing full set of intervals II(v) representing reachability\nset R(v), FERRARI index assigns a mixture of exact and approximate\nreachability intervals, given a user-specified size constraint on the\nindex. In FERRARI-L (local version) it is replaced by at most k\nintervals, some of which come from II(v) and some are merges of\nintervals from II(v). If node w is in one of exact intervals for node\nv, then v can reach w; if node w is outside all of intervals for node v,\nthen v cannot reach w. Intervals are chosen in such way as to maximize\nthe sum of sizes of exact intervals, maximizing positive-cut\neffectiveness.\n\nIn FERRARI-G variant the user-specified size constraint is made global;\nsome nodes may use more intervals, and some less, keeping the average\nconstant. This allows to use index space more effectively, at the cost\nof variable-length index and slower access.\n\n\nContraction hierarchies\n-----------------------\n\nIn general, a Reachability Contraction Hierarchy (RCH) can be defined\nbased on any numbering order. We successively contract nodes with\nincreasing order(v). Contracting node v means removing it from the graph\nand possibly inserting new edges such that the reachability relation in\nthe new graph is the same as in the previous graph, The query algorithm\ndoes not use the contracted versions of the graph but only the ordering\nand the shortcuts. This algorithm is based on the observation that in an\nRCH it suffices to look at \"up-down\" paths, with contraction order first\nincreasing, then decreasing; this works best with bidirectional breadth\nfirst search (BBFS).\n\nPReaCH approach exploits the fact that any DAG contains source nodes\n(with in-degree zero) and sink nodes (with out-degree zero). Contracting\nsuch a node v never requires the insertion of shortcuts.\n\nThe index in this case is just one number per node: the contraction\norder. I'm not sure how useful that would be for BFS search, without\naccessing reverse graph.\n\n\nGraph dominance drawing\n-----------------------\n\nThe fundamental idea behind FELINE is to associate every vertex u in V\nwith a unique ordered pair of natural integers i(u), so that if vertex u\ncan reach v, then i(u) ≦ u(v), that is first element is less or equal\nfirst element in pair, and second element is less or equal second\nelement in pair. If this pair of integers (x, y) associated with a\nvertex is understood as coordinates in the Cartesian plane, then the\nimplication means that paths always point right and up, and it is enough\nto check uper-right quadrant.\n\nThe method is inspired by weak dominance drawing, which guarantees the\nimplication for edges. FELINE work shows proof that this leads to the\nimplication for paths.\n\nSuch pair of numbers are negative-cut filter. The algorithm for\ncreating such index in FELINE work uses two topological orderings, where\nthe second is choosen to minimize number of false positives for the\nindex.\n\nIt turns out however from the experiments in mentoned Jupyter notebook\nthat this method doesn't work that well with commit graphs. When there\nare only a few sources and only a few sinks, then node positions gather\naround 'x = y' diagonal line, thus FELINE index check almost reduces to\nthe topological ordering filter mentioned earlier.\n\n\nApproximate set inclusion\n-------------------------\n\nBoth IP and BFL takes reachability testing from a vertex u to a vertex v\nas set-containment testing. Intuitively, if a vertex u can reach a\nvertex v, then u must be able to reach all the vertices that v can\nreach. Let Out(x) denote the set of all vertices that a vertex x can\nreach in a graph. If u can reach v, then Out(v) ⊆ Out(u). This is done\nby checking by checking Out(v) ⊈ Out(u) instead (that Out(v) is not\nsubset or equal to Out(u), which is to check if there is at least one\nelement in Out(v) that is not in Out(u).\n\nBoth instead of getting an exact answer for testing, they get an answer\nwith given probability guarantee in a negative-cut fashion. The IP\nlabel uses k-min-wise independent permutations, while BFL uses Bloom\nfilters.\n\nThose approaches work well with graphs that have not large reachability\nsets (short depth), and where ratio of positive queries to all queries\nis very small. This means that they would most probably won't work well\nfor commit graphs, where neither holds true.\n\n\nSummary\n=======\n\nThe min-post labeling (the base of GRAIL approach) looks promising; it\nneeds to be checked whether PReaCH approach or FERRARI approach be\nbetter for commit graphs.\n\nI hope that this somewhat long post was informative,\n-- \nJakub Narębski\n"},{"id":"346871","messageId":"07250f7b-e880-26f5-d412-4fbe69affd41@gmail.com","threadId":"48411","inReplyTo":"86zi1fus3t.fsf@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-07T14:26:09Z","receivedAt":"2018-05-07T14:26:19Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/4/2018 3:40 PM, Jakub Narebski wrote:\n> Hello,\n>\n> With early parts of commit-graph feature (ds/commit-graph and\n> ds/lazy-load-trees) close to being merged into \"master\", see\n> https://public-inbox.org/git/xmqq4ljtz87g.fsf@gitster-ct.c.googlers.com/\n> I think it would be good idea to think what other data could be added\n> there to make Git even faster.\n\nBefore thinking about adding more data to the commit-graph, I think \ninstead we need to finish taking advantage of the data that is already \nthere. This means landing the generation number patch [1] (I think this \nis close, so I'll send a v6 this week if there is no new feedback.) and \nthe auto-compute patch [2] (this could use more feedback, but I'll send \na v1 based on the RFC feedback if no one chimes in).\n\n[1] \nhttps://public-inbox.org/git/20180501124652.155781-1-dstolee@microsoft.com/\n     [PATCH v5 00/11] Compute and consume generation numbers\n\n[2] \nhttps://public-inbox.org/git/20180417181028.198397-1-dstolee@microsoft.com/\n     [RFC PATCH 00/12] Integrate commit-graph into 'fsck' and 'gc'\n\nThe big wins remaining from this data are `git tag --merged` and `git \nlog --graph`. The `tag` scenario is probably easier: this can be done by \nreplacing the revision-walk underlying the call to use \npaint_down_to_common() instead. Requires adding an external method to \ncommit.c, but not too much code.\n\nThe tougher challenge is `git log --graph`. The revision walk machinery \ncurrently uses two precompute phases before iterating results to the \npager: limit_list() and sort_in_topological_order(); these correspond to \ntwo phases of Kahn's algorithm for topo-sort (compute in-degrees, then \nwalk by peeling commits with in-degree zero). This requires O(N) time, \nwhere N is the number of reachable commits. Instead, we could make this \nbe O(W) time to output one page of results, where W is (roughly) the \nnumber of reachable commits with generation number above the last \nreported result.\n\nIn order to take advantage of this approach, the two phases of Kahn's \nalgorithm need to be done in-line with reporting results to the pager. \nThis means keeping two queues: one is a priority queue by generation \nnumber that computes in-degrees, the other is a priority queue (by \ncommit-date or a visit-order value to do the --topo-order priority) that \npeels the in-degree-zero commits (and decrements the in-degree of their \nparents). I have not begun this refactoring effort because appears \ncomplicated to me, and it will be hard to tease out the logic without \naffecting other consumers of the revision-walk machinery.\n\nI would love it if someone picked up the `git log --graph` task, since \nit will be a few weeks before I have the time to focus on it.\n\nWithout completing the benefits we get from generation numbers, these \ninvestigations into other reachability indexes will be incomplete as \nthey are comparing benefits without all consumers taking advantage of a \nreachability index.\n\n[...]\n> Bloom filter for changed paths\n> ------------------------------\n>\n> The goal of this chunk is to speed up checking if the file or directory\n> was changed in given commit, for queries such as \"git log -- \" or\n> \"git blame \". This is something that according to \"Git Merge\n> contributor summit notes\" [2] is already present in VSTS (Visual Studio\n> Team Services - the server counterpart of GVFS: Git Virtual File System)\n> at Microsoft:\n>\n> AV> - VSTS adds bloom filters to know which paths have changed on the commit\n> AV> - tree-same check in the bloom filter is fast; speeds up file history checks\n> AV> - might be useful in the client as well, since limited-traversal is common\n> AV> - if the file history is _very_ sparse, then bloom filter is useful\n> AV> - but needs pre-compute, so useful to do once\n> AV> - first make the client do it, then think about how to serve it centrally\n>\n> [2]: https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/\n>\n> I think it was what Derrick Stolee was talking about at the end of his\n> part of \"Making Git for Windows\" presentation at Git Merge 2018:\n> https://youtu.be/oOMzi983Qmw?t=1835\n>\n> This was also mentioned in subthread of \"Re: [PATCH v2 0/4] Lazy-load\n> trees when reading commit-graph\", starting from [3]\n> [3]: https://public-inbox.org/git/86y3hyeu6c.fsf@gmail.com/\n\nAgain, the benefits of Bloom filters should only be measured after \nalready taking advantage of a reachability index during `git log`. \nHowever, you could get performance benefits from Bloom filters in a \nnormal `git log` (no topo-order).\n\nThe tricky part about this feature is that the decisions we made in our \nC# implementation for the VSTS Git server may be very different than the \nneeds for the C implementation of the Git client. Questions like \"how do \nwe handle merge commits?\" may have different answers, which can only be \ndiscovered by implementing the feature.\n\n(The answer for VSTS is that we only store Bloom filters containing the \nlist of changed paths against the first parent. The second parent \nfrequently has too many different paths, and if we are computing \nfile-history simplification we have already determined the first parent \nis _not_ TREESAME, which requires verifying the difference by parsing \ntrees against the first parent.)\n\nI'm happy to provide more information on how we built this feature if \nsomeone is writing a patch. Otherwise, I plan to implement it after \nfinishing the parts I think are higher priority.\n\nThanks,\n-Stolee\n"},{"id":"347462","messageId":"86r2mh2cur.fsf@gmail.com","threadId":"48411","inReplyTo":"07250f7b-e880-26f5-d412-4fbe69affd41@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-12T14:00:12Z","receivedAt":"2018-05-12T14:00:21Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 5/4/2018 3:40 PM, Jakub Narebski wrote:\n>>\n>> With early parts of commit-graph feature (ds/commit-graph and\n>> ds/lazy-load-trees) close to being merged into \"master\", see\n>> https://public-inbox.org/git/xmqq4ljtz87g.fsf@gitster-ct.c.googlers.com/\n>> I think it would be good idea to think what other data could be added\n>> there to make Git even faster.\n>\n> Before thinking about adding more data to the commit-graph, I think\n> instead we need to finish taking advantage of the data that is already\n> there. This means landing the generation number patch [1] (I think\n> this is close, so I'll send a v6 this week if there is no new\n> feedback.) and the auto-compute patch [2] (this could use more\n> feedback, but I'll send a v1 based on the RFC feedback if no one\n> chimes in).\n>\n> [1]\n> https://public-inbox.org/git/20180501124652.155781-1-dstolee@microsoft.com/\n>     [PATCH v5 00/11] Compute and consume generation numbers\n>\n> [2]\n> https://public-inbox.org/git/20180417181028.198397-1-dstolee@microsoft.com/\n>     [RFC PATCH 00/12] Integrate commit-graph into 'fsck' and 'gc'\n\nRight, so the RFC might be a bit premature; I wanted the discussion to\nbe out there to think about when adding new uses of existing features.\n\n\nDIGRESSION: it is commendable that you are sending patches in small,\neasy digestible chunks / patch series. It is much easier to review 10+\nseries than 80+ behemoth (though I understand it is not always possible\nto subdivide patch series into smaller self-contained sub-series).\n\nOn the other hand, it would be nice to have some roadmap about series\nand features to be sent in the future, if possible. Something like what\nwas done when 'git rebase --interactive' was getting builtinified: moved\n(in parts) to C. It would be great to have such roadmap with milestones\nachieved and milestones to be done in the cover letter for series.\n\n> The big wins remaining from this data are `git tag --merged` and `git\n> log --graph`. The `tag` scenario is probably easier: this can be done\n> by replacing the revision-walk underlying the call to use\n> paint_down_to_common() instead. Requires adding an external method to\n> commit.c, but not too much code.\n\nI wonder if there is some significant reason behind `git tag --merged`\nusing its own codepath, beside historical reasons. Maybe performance is\nbetter with current code?\n\nUtilizing paint_down_to_common() there, beside reducing amount of code\nyou would have to modify, would also unify code (and possibly reduce\namount of code). That's very nice.\n\n>\n> The tougher challenge is `git log --graph`. The revision walk\n> machinery currently uses two precompute phases before iterating\n> results to the pager: limit_list() and sort_in_topological_order();\n> these correspond to two phases of Kahn's algorithm for topo-sort\n> (compute in-degrees, then walk by peeling commits with in-degree\n> zero). This requires O(N) time, where N is the number of reachable\n> commits. Instead, we could make this be O(W) time to output one page\n> of results, where W is (roughly) the number of reachable commits with\n> generation number above the last reported result.\n\nA reminder: Kahn's algorithm (described for example in [1] and [3])\nlooks like this:\n\n L ← Empty list that will contain the sorted elements\n S ← Collection of all nodes with no incoming edge\n while S is non-empty do\n remove a node 'n' from S\n add 'n' to tail of L\n for each parent 'm' of 'n' do\n decrease the in-degree of 'm'\n if 'm' has in-degree of 0 then\n insert 'm' into S\n\n[1]: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm\n[2]: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/\n\n> In order to take advantage of this approach, the two phases of Kahn's\n> algorithm need to be done in-line with reporting results to the\n> pager. This means keeping two queues: one is a priority queue by\n> generation number that computes in-degrees,\n\nThis simple solition of using priority queue by generation number won't\nwork, I think. In-degree is computed from heads down, generation number\nis computed from roots up.\n\nFor example in the graph below\n\n *<---*<---*<---*<---*<---*<---*<---*<---*<---A\n \\\n \\--*<---B\n\nboth A and B have in-degree of 0, but gen(B) << gen(A).\n\nBut I might be wrong.\n\n> the other is a priority\n> queue (by commit-date or a visit-order value to do the --topo-order\n> priority) that peels the in-degree-zero commits (and decrements the\n> in-degree of their parents). I have not begun this refactoring effort\n> because appears complicated to me, and it will be hard to tease out\n> the logic without affecting other consumers of the revision-walk\n> machinery.\n>\n> I would love it if someone picked up the `git log --graph` task, since\n> it will be a few weeks before I have the time to focus on it.\n\nLet's assume that we have extra data (indexes such as generation number)\nthat can be used for positive-cut (we know that A can reach B) and\nnegative-cut (we know that A cannot reach B) filters. Generation number\naka. topological level can be used in negative-cut filter.\n\nNOTE: I have not looked at current Git code that does topological\nsorting, as to not be suggested by the existing implementation.\n\n\nHow the indexes-amplified incremental Kahn's algorithm could look like:\n\nFirst we need to find at least one node / vertex / commit with an\nin-degree of zero. We are given a list of commits to start from, but\nthey may not all have in-degree of zero - they may be dependent, or in\nother words some of them may be reachable from others and be\nirrelevant. Here negative-cut and positive-cut filters can help.\n\nIf the order of commits on command line does not matter, we can start\nfrom any distinct commit with highest generation number - we know that\nit cannot be reached from other heads / refs and thus has in-degree of\nzero.\n\n L ← Empty list that will contain the sorted elements\n S ← Collection of all nodes with no incoming edge\n R ← Collection of starting points (refs)\n while S is non-empty do\n remove a node 'n' from S\n add 'n' to tail of L\n for each parent 'm' of 'n' do\n if 'm' cannot be reached from R then\n # it has in-degree of 0\n insert 'm' into S\n else if 'm' can be reached from R then\n # it has in-degree greater than 0\n insert 'm' into R\n else\n walk from each 'r of R,\n until we know if 'm' is reachable from R\n then insert it into S or R\n\n perhaps computing in-degrees,\n or marking commits as reachable...\n\n\nDoes it looks correct? I can try to make this pseudocode into actual\nalgorithm.\n\n>\n> Without completing the benefits we get from generation numbers, these\n> investigations into other reachability indexes will be incomplete as\n> they are comparing benefits without all consumers taking advantage of\n> a reachability index.\n\nOn one hand side, you are right: if we try to investigate of some\nreachability index is worth it by checking if it *improves performance\nof actual git operations* without all consumers taking advantage of a\nreachability index would be incomplete.\n\nOn the other hand we can still perform synthetic tests: how much less\ncommits we walk when checking that A can reach B on real commit graphs\n(like I did in mentioned Google Colaboratory notebook [3]). This\nassumes that the cost of accessing commit data (and possibly also\nindexes data) dominates, and the cost of using reachability indexes is\nnegligible.\n\n[3]: https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n\nOn the gripping hand the construction of algorithms in those future\nsteps would be, I think, affected by what types of indexes would we\nhave: negative-cut filters, positive-cut filters, reachability bitmaps,\nBloom filters for changed files, eic.\n\n> [...]\n>> Bloom filter for changed paths\n>> ------------------------------\n>>\n>> The goal of this chunk is to speed up checking if the file or directory\n>> was changed in given commit, for queries such as \"git log -- \" or\n>> \"git blame \". This is something that according to \"Git Merge\n>> contributor summit notes\" [2] is already present in VSTS (Visual Studio\n>> Team Services - the server counterpart of GVFS: Git Virtual File System)\n>> at Microsoft:\n>>\n>> AV> - VSTS adds bloom filters to know which paths have changed on the commit\n>> AV> - tree-same check in the bloom filter is fast; speeds up file history checks\n>> AV> - might be useful in the client as well, since limited-traversal is common\n>> AV> - if the file history is _very_ sparse, then bloom filter is useful\n>> AV> - but needs pre-compute, so useful to do once\n>> AV> - first make the client do it, then think about how to serve it centrally\n>>\n>> [2]: https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/\n>>\n>> I think it was what Derrick Stolee was talking about at the end of his\n>> part of \"Making Git for Windows\" presentation at Git Merge 2018:\n>> https://youtu.be/oOMzi983Qmw?t=1835\n>>\n>> This was also mentioned in subthread of \"Re: [PATCH v2 0/4] Lazy-load\n>> trees when reading commit-graph\", starting from [3]\n>> [3]: https://public-inbox.org/git/86y3hyeu6c.fsf@gmail.com/\n>\n> Again, the benefits of Bloom filters should only be measured after\n> already taking advantage of a reachability index during `git\n> log`. However, you could get performance benefits from Bloom filters\n> in a normal `git log` (no topo-order).\n\nI wonder how much they improve performance of \"git blame\"...\n\n> The tricky part about this feature is that the decisions we made in\n> our C# implementation for the VSTS Git server may be very different\n> than the needs for the C implementation of the Git client. Questions\n> like \"how do we handle merge commits?\" may have different answers,\n> which can only be discovered by implementing the feature.\n>\n> (The answer for VSTS is that we only store Bloom filters containing\n> the list of changed paths against the first parent. The second parent\n> frequently has too many different paths, and if we are computing\n> file-history simplification we have already determined the first\n> parent is _not_ TREESAME, which requires verifying the difference by\n> parsing trees against the first parent.)\n\nThanks for the information. I think for now it is sufficient level of\nthe detail.\n\n> I'm happy to provide more information on how we built this feature if\n> someone is writing a patch. Otherwise, I plan to implement it after\n> finishing the parts I think are higher priority.\n\nAll right, I understand that. Time is a scarse resource.\n\n\nI think that, beside writing patches for Git, exploring how various\npieces of data and various indexes affect walking commit graphs is also\nimportant. My explorations shown that, for example, that FELINE index\nis not good fit for relatively \"narrow\" graphs of revision history.\nExploring this in Python / Jupyter is easier than trying to write a\nexploratory patch for Git, in my opinion. Just IMVHO.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"347596","messageId":"fca023a3-f849-4be8-db42-7027bfe7b0dc@gmail.com","threadId":"48411","inReplyTo":"86r2mh2cur.fsf@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-05-14T13:20:29Z","receivedAt":"2018-05-14T13:20:38Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/12/2018 10:00 AM, Jakub Narebski wrote:\n> Derrick Stolee writes:\n>> On 5/4/2018 3:40 PM, Jakub Narebski wrote:\n>>> With early parts of commit-graph feature (ds/commit-graph and\n>>> ds/lazy-load-trees) close to being merged into \"master\", see\n>>> https://public-inbox.org/git/xmqq4ljtz87g.fsf@gitster-ct.c.googlers.com/\n>>> I think it would be good idea to think what other data could be added\n>>> there to make Git even faster.\n>> Before thinking about adding more data to the commit-graph, I think\n>> instead we need to finish taking advantage of the data that is already\n>> there. This means landing the generation number patch [1] (I think\n>> this is close, so I'll send a v6 this week if there is no new\n>> feedback.) and the auto-compute patch [2] (this could use more\n>> feedback, but I'll send a v1 based on the RFC feedback if no one\n>> chimes in).\n>>\n>> [1]\n>> https://public-inbox.org/git/20180501124652.155781-1-dstolee@microsoft.com/\n>>     [PATCH v5 00/11] Compute and consume generation numbers\n>>\n>> [2]\n>> https://public-inbox.org/git/20180417181028.198397-1-dstolee@microsoft.com/\n>>     [RFC PATCH 00/12] Integrate commit-graph into 'fsck' and 'gc'\n> Right, so the RFC might be a bit premature; I wanted the discussion to\n> be out there to think about when adding new uses of existing features.\n>\n>\n> DIGRESSION: it is commendable that you are sending patches in small,\n> easy digestible chunks / patch series. It is much easier to review 10+\n> series than 80+ behemoth (though I understand it is not always possible\n> to subdivide patch series into smaller self-contained sub-series).\n>\n> On the other hand, it would be nice to have some roadmap about series\n> and features to be sent in the future, if possible. Something like what\n> was done when 'git rebase --interactive' was getting builtinified: moved\n> (in parts) to C. It would be great to have such roadmap with milestones\n> achieved and milestones to be done in the cover letter for series.\n\nI suppose that is what I intended in the \"Future Work\" section of \nDocumentation/technical/commit-graph.txt. It gives a set of things that \nneed to be done in order to make this a default feature, not just an \nexpert-level feature. When I wrote the section, I was focused entirely \non \"commit-graph version 1.0\" and I didn't know how long that would \ntake. The series have been getting interest and review (in great part to \nyour interest, Jakub) so they have been moving to 'next' faster than I \nanticipated.\n\nI'll plan on writing a more detailed list of future directions, but for \nnow I'll list the things I know about and how I see them in priority order:\n\nCommit-graph v1.0:\n* ds/generation-numbers\n* 'verify' and fsck/gc integration\n* correct behavior with shallow clones, replace-objects, and grafts\n\nCommit-graph v1.1:\n* Place commit-graph storage in the_repository\n* 'git tag --merged' use generation numbers\n* 'git log --graph' use generation numbers\n\nCommit-graph v1.X:\n* Protocol v2 verb for sending commit-graph\n* Bloom filters for changed paths\n\n>\n>> The big wins remaining from this data are `git tag --merged` and `git\n>> log --graph`. The `tag` scenario is probably easier: this can be done\n>> by replacing the revision-walk underlying the call to use\n>> paint_down_to_common() instead. Requires adding an external method to\n>> commit.c, but not too much code.\n> I wonder if there is some significant reason behind `git tag --merged`\n> using its own codepath, beside historical reasons. Maybe performance is\n> better with current code?\n>\n> Utilizing paint_down_to_common() there, beside reducing amount of code\n> you would have to modify, would also unify code (and possibly reduce\n> amount of code). That's very nice.\n>\n>> The tougher challenge is `git log --graph`. The revision walk\n>> machinery currently uses two precompute phases before iterating\n>> results to the pager: limit_list() and sort_in_topological_order();\n>> these correspond to two phases of Kahn's algorithm for topo-sort\n>> (compute in-degrees, then walk by peeling commits with in-degree\n>> zero). This requires O(N) time, where N is the number of reachable\n>> commits. Instead, we could make this be O(W) time to output one page\n>> of results, where W is (roughly) the number of reachable commits with\n>> generation number above the last reported result.\n> A reminder: Kahn's algorithm (described for example in [1] and [3])\n> looks like this:\n>\n> L ← Empty list that will contain the sorted elements\n> S ← Collection of all nodes with no incoming edge\n> while S is non-empty do\n> remove a node 'n' from S\n> add 'n' to tail of L\n> for each parent 'm' of 'n' do\n> decrease the in-degree of 'm'\n> if 'm' has in-degree of 0 then\n> insert 'm' into S\n>\n> [1]: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm\n> [2]: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/\n>\n>> In order to take advantage of this approach, the two phases of Kahn's\n>> algorithm need to be done in-line with reporting results to the\n>> pager. This means keeping two queues: one is a priority queue by\n>> generation number that computes in-degrees,\n> This simple solition of using priority queue by generation number won't\n> work, I think. In-degree is computed from heads down, generation number\n> is computed from roots up.\n>\n> For example in the graph below\n>\n> *<---*<---*<---*<---*<---*<---*<---*<---*<---A\n> \\\n> \\--*<---B\n>\n> both A and B have in-degree of 0, but gen(B) << gen(A).\n>\n> But I might be wrong.\n>\n>> the other is a priority\n>> queue (by commit-date or a visit-order value to do the --topo-order\n>> priority) that peels the in-degree-zero commits (and decrements the\n>> in-degree of their parents). I have not begun this refactoring effort\n>> because appears complicated to me, and it will be hard to tease out\n>> the logic without affecting other consumers of the revision-walk\n>> machinery.\n>>\n>> I would love it if someone picked up the `git log --graph` task, since\n>> it will be a few weeks before I have the time to focus on it.\n> Let's assume that we have extra data (indexes such as generation number)\n> that can be used for positive-cut (we know that A can reach B) and\n> negative-cut (we know that A cannot reach B) filters. Generation number\n> aka. topological level can be used in negative-cut filter.\n>\n> NOTE: I have not looked at current Git code that does topological\n> sorting, as to not be suggested by the existing implementation.\n>\n>\n> How the indexes-amplified incremental Kahn's algorithm could look like:\n>\n> First we need to find at least one node / vertex / commit with an\n> in-degree of zero. We are given a list of commits to start from, but\n> they may not all have in-degree of zero - they may be dependent, or in\n> other words some of them may be reachable from others and be\n> irrelevant. Here negative-cut and positive-cut filters can help.\n>\n> If the order of commits on command line does not matter, we can start\n> from any distinct commit with highest generation number - we know that\n> it cannot be reached from other heads / refs and thus has in-degree of\n> zero.\n>\n> L ← Empty list that will contain the sorted elements\n> S ← Collection of all nodes with no incoming edge\n> R ← Collection of starting points (refs)\n> while S is non-empty do\n> remove a node 'n' from S\n> add 'n' to tail of L\n> for each parent 'm' of 'n' do\n> if 'm' cannot be reached from R then\n> # it has in-degree of 0\n> insert 'm' into S\n> else if 'm' can be reached from R then\n> # it has in-degree greater than 0\n> insert 'm' into R\n> else\n> walk from each 'r of R,\n> until we know if 'm' is reachable from R\n> then insert it into S or R\n>\n> perhaps computing in-degrees,\n> or marking commits as reachable...\n>\n>\n> Does it looks correct? I can try to make this pseudocode into actual\n> algorithm.\n\nI'm not following your pseudocode very well, so instead I'll provide a \nmore concrete description of what I mentioned before:\n\nHere are some data structures.\n\nIDV : A dictionary storing the currently-computed in-degree value of a \ncommit 'c' as 'IDV[c]'. Assume all commits start with in-degree 0.\nIDQ : A queue, for storing the \"in-degree walk\". It is a priority queue \nordered by generation number.\nTOQ : A queue, for storing the \"topo-order walk\". It is a priority queue \nordered by \"visit order\" (see algorithm)\n\nHere are some methods.\n\nAdvanceInDegreeWalk(IDQ, IDV, gen):\n     while !IDX.Empty && IDQ.Max >= gen:\n         c = IDX.Dequeue\n\n         for each parent p of c:\n             IDV[p]++;\n             IDQ.Enqueue(p, generation(p))\n\nInitializeTopoOrder(R):\n     Initialize IDQ, IDV, TOQ\n\n     min_generation = GENERATION_NUMBER_INFINITY\n     visit_order = 0\n\n     for each commit c in R:\n         min_generation = min(min_generation, generation(c))\n         IDQ.Enqueue(c, generation(c))\n\n     AdvanceInDegreeWalk(IDQ, IDV, min_generation)\n\n     for each commit c in R:\n         if IDV[c] == 0:\n             TOQ.Enqueue(c, visit_order++)\n\n     return (IDQ, IDV, TOQ, visit_order)\n\nGetNextInTopoOrder(IDQ, IDV, TOQ, ref visit_order):\n     if TOQ.Empty:\n         return null\n\n     c = TOQ.Dequeue()\n\n     for each parent p of c:\n         IDV[p]--\n         AdvanceInDegreeWalk(IDQ, IDV, generation(p))\n         if IDV[p] == 0:\n             TOQ.Enqueue(p, visit_order++)\n\n     return c\n\n(I mention \"ref visit_order\" to be sure we are passing-by-reference. In \na full implementation, the walk details would be grouped into a struct.)\n\nThis algorithm is relatively simple, but the hard part is teasing the \nrevision walk machinery to initialize the data by calling \nInitializeTopoOrder(R) and to call GetNextInTopoOrder() whenever it \nneeds a new element of the walk. That is, it is hard to be sure we are \nnot causing side-effects as we make that transformation.\n\n>\n>> Without completing the benefits we get from generation numbers, these\n>> investigations into other reachability indexes will be incomplete as\n>> they are comparing benefits without all consumers taking advantage of\n>> a reachability index.\n> On one hand side, you are right: if we try to investigate of some\n> reachability index is worth it by checking if it *improves performance\n> of actual git operations* without all consumers taking advantage of a\n> reachability index would be incomplete.\n>\n> On the other hand we can still perform synthetic tests: how much less\n> commits we walk when checking that A can reach B on real commit graphs\n> (like I did in mentioned Google Colaboratory notebook [3]). This\n> assumes that the cost of accessing commit data (and possibly also\n> indexes data) dominates, and the cost of using reachability indexes is\n> negligible.\n>\n> [3]: https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n>\n> On the gripping hand the construction of algorithms in those future\n> steps would be, I think, affected by what types of indexes would we\n> have: negative-cut filters, positive-cut filters, reachability bitmaps,\n> Bloom filters for changed files, eic.\n>\n>> [...]\n>>> Bloom filter for changed paths\n>>> ------------------------------\n>>>\n>>> The goal of this chunk is to speed up checking if the file or directory\n>>> was changed in given commit, for queries such as \"git log -- \" or\n>>> \"git blame \". This is something that according to \"Git Merge\n>>> contributor summit notes\" [2] is already present in VSTS (Visual Studio\n>>> Team Services - the server counterpart of GVFS: Git Virtual File System)\n>>> at Microsoft:\n>>>\n>>> AV> - VSTS adds bloom filters to know which paths have changed on the commit\n>>> AV> - tree-same check in the bloom filter is fast; speeds up file history checks\n>>> AV> - might be useful in the client as well, since limited-traversal is common\n>>> AV> - if the file history is _very_ sparse, then bloom filter is useful\n>>> AV> - but needs pre-compute, so useful to do once\n>>> AV> - first make the client do it, then think about how to serve it centrally\n>>>\n>>> [2]: https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/\n>>>\n>>> I think it was what Derrick Stolee was talking about at the end of his\n>>> part of \"Making Git for Windows\" presentation at Git Merge 2018:\n>>> https://youtu.be/oOMzi983Qmw?t=1835\n>>>\n>>> This was also mentioned in subthread of \"Re: [PATCH v2 0/4] Lazy-load\n>>> trees when reading commit-graph\", starting from [3]\n>>> [3]: https://public-inbox.org/git/86y3hyeu6c.fsf@gmail.com/\n>> Again, the benefits of Bloom filters should only be measured after\n>> already taking advantage of a reachability index during `git\n>> log`. However, you could get performance benefits from Bloom filters\n>> in a normal `git log` (no topo-order).\n> I wonder how much they improve performance of \"git blame\"...\n>\n>> The tricky part about this feature is that the decisions we made in\n>> our C# implementation for the VSTS Git server may be very different\n>> than the needs for the C implementation of the Git client. Questions\n>> like \"how do we handle merge commits?\" may have different answers,\n>> which can only be discovered by implementing the feature.\n>>\n>> (The answer for VSTS is that we only store Bloom filters containing\n>> the list of changed paths against the first parent. The second parent\n>> frequently has too many different paths, and if we are computing\n>> file-history simplification we have already determined the first\n>> parent is _not_ TREESAME, which requires verifying the difference by\n>> parsing trees against the first parent.)\n> Thanks for the information. I think for now it is sufficient level of\n> the detail.\n>\n>> I'm happy to provide more information on how we built this feature if\n>> someone is writing a patch. Otherwise, I plan to implement it after\n>> finishing the parts I think are higher priority.\n> All right, I understand that. Time is a scarse resource.\n>\n>\n> I think that, beside writing patches for Git, exploring how various\n> pieces of data and various indexes affect walking commit graphs is also\n> important. My explorations shown that, for example, that FELINE index\n> is not good fit for relatively \"narrow\" graphs of revision history.\n> Exploring this in Python / Jupyter is easier than trying to write a\n> exploratory patch for Git, in my opinion. Just IMVHO.\n\nYou are right. Ruling out possibilities is the best outcome these \nprototypes can have. Your work has saved someone a lot of time in \ninvestigating that direction.\n\nThanks,\n-Stolee\n"},{"id":"347626","messageId":"864lja2buq.fsf@gmail.com","threadId":"48411","inReplyTo":"fca023a3-f849-4be8-db42-7027bfe7b0dc@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-14T20:58:37Z","receivedAt":"2018-05-14T20:58:50Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 5/12/2018 10:00 AM, Jakub Narebski wrote:\n>> Derrick Stolee writes:\n>>> On 5/4/2018 3:40 PM, Jakub Narebski wrote:\n>>>>\n>>>> With early parts of commit-graph feature (ds/commit-graph and\n>>>> ds/lazy-load-trees) close to being merged into \"master\", see\n>>>> https://public-inbox.org/git/xmqq4ljtz87g.fsf@gitster-ct.c.googlers.com/\n>>>> I think it would be good idea to think what other data could be added\n>>>> there to make Git even faster.\n>>> Before thinking about adding more data to the commit-graph, I think\n>>> instead we need to finish taking advantage of the data that is already\n>>> there. This means landing the generation number patch [1] (I think\n>>> this is close, so I'll send a v6 this week if there is no new\n>>> feedback.) and the auto-compute patch [2] (this could use more\n>>> feedback, but I'll send a v1 based on the RFC feedback if no one\n>>> chimes in).\n>>>\n>>> [1]\n>>> https://public-inbox.org/git/20180501124652.155781-1-dstolee@microsoft.com/\n>>>     [PATCH v5 00/11] Compute and consume generation numbers\n>>>\n>>> [2]\n>>> https://public-inbox.org/git/20180417181028.198397-1-dstolee@microsoft.com/\n>>>     [RFC PATCH 00/12] Integrate commit-graph into 'fsck' and 'gc'\n>>\n>> Right, so the RFC might be a bit premature; I wanted the discussion to\n>> be out there to think about when adding new uses of existing features.\n>>\n>>\n>> DIGRESSION: it is commendable that you are sending patches in small,\n>> easy digestible chunks / patch series. It is much easier to review 10+\n>> series than 80+ behemoth (though I understand it is not always possible\n>> to subdivide patch series into smaller self-contained sub-series).\n>>\n>> On the other hand, it would be nice to have some roadmap about series\n>> and features to be sent in the future, if possible. Something like what\n>> was done when 'git rebase --interactive' was getting builtinified: moved\n>> (in parts) to C. It would be great to have such roadmap with milestones\n>> achieved and milestones to be done in the cover letter for series.\n>\n> I suppose that is what I intended in the \"Future Work\" section of\n> Documentation/technical/commit-graph.txt. It gives a set of things\n> that need to be done in order to make this a default feature, not just\n> an expert-level feature. When I wrote the section, I was focused\n> entirely on \"commit-graph version 1.0\" and I didn't know how long that\n> would take. The series have been getting interest and review (in great\n> part to your interest, Jakub) so they have been moving to 'next'\n> faster than I anticipated.\n>\n> I'll plan on writing a more detailed list of future directions, but\n> for now I'll list the things I know about and how I see them in\n> priority order:\n>\n> Commit-graph v1.0:\n> * ds/generation-numbers\n> * 'verify' and fsck/gc integration\n> * correct behavior with shallow clones, replace-objects, and grafts\n\nSo the goal of current v1.0 phase is to introduce generation numbers.\nuse them for better performance (\"low hanging fruit\"), ensure that it is\nautomatic and safe -- thus useable for an ordinary user.\n\n>\n> Commit-graph v1.1:\n> * Place commit-graph storage in the_repository\n> * 'git tag --merged' use generation numbers\n> * 'git log --graph' use generation numbers\n>\n> Commit-graph v1.X:\n> * Protocol v2 verb for sending commit-graph\n> * Bloom filters for changed paths\n\nThanks, that is what I was missing. The \"Future Work\" section, while\nvery nice to have (because it does not require to follow git\ndevelopment; it is here in technical documentation), lacked\nprioritization and rough milestones map.\n\n[...]\n>>> The tougher challenge is `git log --graph`. The revision walk\n>>> machinery currently uses two precompute phases before iterating\n>>> results to the pager: limit_list() and sort_in_topological_order();\n>>> these correspond to two phases of Kahn's algorithm for topo-sort\n>>> (compute in-degrees, then walk by peeling commits with in-degree\n>>> zero). This requires O(N) time, where N is the number of reachable\n>>> commits. Instead, we could make this be O(W) time to output one page\n>>> of results, where W is (roughly) the number of reachable commits with\n>>> generation number above the last reported result.\n>>\n>> A reminder: Kahn's algorithm (described for example in [1] and [3])\n>> looks like this:\n>>\n>> L ← Empty list that will contain the sorted elements\n>> S ← Collection of all nodes with no incoming edge\n>> while S is non-empty do\n>> remove a node 'n' from S\n>> add 'n' to tail of L\n>> for each parent 'm' of 'n' do\n>> decrease the in-degree of 'm'\n>> if 'm' has in-degree of 0 then\n>> insert 'm' into S\n>>\n>> [1]: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm\n>> [2]: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/\n[...]\n\n> I'm not following your pseudocode very well,\n\nNot surprising, I've lost myself in the middle of writing it...\n\n> so instead I'll provide a\n> more concrete description of what I mentioned before:\n\nBefore we start with helper data structures, we should start with the\ninputs. For topological sort it is set of starting commits that define\nthe part of commit graph we are interested in; they may be some that are\nredundant, but those that do not are assumed to have in-degree of 0.\n\n> Here are some data structures.\n>\n IDX : ???\n\n> IDV : A dictionary storing the currently-computed in-degree value of a\n> commit 'c' as 'IDV[c]'. Assume all commits start with in-degree 0.\n\nNitpick: I guess that it is really \"with assumed in-degree of 0\".\n\nThis would be stored using commit-slab, isn't it?\n\n> IDQ : A queue, for storing the \"in-degree walk\". It is a priority\n> queue ordered by generation number.\n\nAll right, here we use the fact that if we walk up to and including\ngeneration number of commit, then its in-degree will be calculated\ncorrectly, as any commit with generation number smaller than generation\nnumber of given commit cannot reach given commit and change its\nin-degree.\n\n> TOQ : A queue, for storing the \"topo-order walk\". It is a priority\n> queue ordered by \"visit order\" (see algorithm)\n\nNote: max priority queue ordered by \"visit order\" is practically a\nstack, though I guess we prefer priority queue here to use the same code\nfor '--date-order'.\n\n>\n> Here are some methods.\n>\n> AdvanceInDegreeWalk(IDQ, IDV, gen):\n\nIf I understand it correctly this subroutine walks those commits that do\nnot have correct in-degree calculated, and walks till all commits with\ngeneration number greater or equal to 'gen' cutoff parameter are walked\nand have correct in-degree.\n\nAssumes that all commits in graph but not in IDX have their in-degree\ncalculated.\n\n>     while !IDX.Empty && IDQ.Max >= gen:\n>         c = IDX.Dequeue\n>\n>         for each parent p of c:\n\nHere the ordering of parents walked does not matter (much), as\ngeneration number is used as cutoff only.\n\n>             IDV[p]++;\n>             IDQ.Enqueue(p, generation(p))\n\nAll right, looks correct; with gen = 0 it probably reduces to the\ncurrent code that does in-degree calculation upfront.\n\n>\n> InitializeTopoOrder(R):\n>     Initialize IDQ, IDV, TOQ\n>\n>     min_generation = GENERATION_NUMBER_INFINITY\n>     visit_order = 0\n>\n>     for each commit c in R:\n>         min_generation = min(min_generation, generation(c))\n>         IDQ.Enqueue(c, generation(c))\n>\n>     AdvanceInDegreeWalk(IDQ, IDV, min_generation)\n\nThis means that we walk BFS-like until all starting points, that is all\ncommits in R, have their in-degree calculated. I think we can avoid\nthat, but it may change the exact behavior of '--topo-order'.\n\nCurrently if one commit in R is from orphan branch (like 'todo' in\ngit.git), or has otherwise very low generation number, it would mean\nthat AdvanceInDegreeWalk would walk almost all commits.\n\n>     for each commit c in R:\n>         if IDV[c] == 0:\n>             TOQ.Enqueue(c, visit_order++)\n\nI think we may want to either start from commits in the order given on\ncommand line (given by R), and not reverse order, or maybe even start\nfrom commits with maximum generation number.\n\n>\n>     return (IDQ, IDV, TOQ, visit_order)\n\nAll right.\n\nHere is my [allegedly] improved version, which assumes that we always\nwant to start from commit with maximum generation number (there may be\nmore than one such commit).\n\nLet's add one more data structure:\n\n RRQ : A queue, for storing remaining commits from R (starting point).\n It is a priority queue ordered by generation number.\n\n\nInitializeTopoOrder(R):\n    Initialize IDQ, IDV, TOQ, RRQ\n\n    max_generation = 0\n    visit_order = 0\n\n    for each commit c in R:\n        max_generation = max(max_generation, generation(c))\n        unless IsRedundantFilter(R / c, c): # optional\n            RRQ.Enqueue(c, generation(c))\n\n    while RRQ.Max == max_generation:\n        c = RRQ.Dequeue()\n        IDV[c] = 0 # commits with max gen have in-degree of 0\n        IDQ.Enqueue(c, generation(c))\n\n    # this would be almost no-op\n    AdvanceInDegreeWalk(IDQ, IDV, max_generation)\n\n    for each commit c in reversed R:\n        if generation(c) == max_generation: # then IDV[c] == 0\n            TOQ.Enqueue(c, visit_order++)\n\n    return (IDQ, IDV, TOQ, RRQ, visit_order)\n\n>\n> GetNextInTopoOrder(IDQ, IDV, TOQ, ref visit_order):\n>     if TOQ.Empty:\n>         return null\n>\n>     c = TOQ.Dequeue()\n>\n>     for each parent p of c:\n>         IDV[p]--\n>         AdvanceInDegreeWalk(IDQ, IDV, generation(p))\n>         if IDV[p] == 0:\n>             TOQ.Enqueue(p, visit_order++)\n>\n>     return c\n\nWith the modification to InitializeTopoOrder it would be\n\nGetNextInTopoOrder(IDQ, IDV, TOQ, RRQ, ref visit_order):\n    if TOQ.Empty:\n        return null\n\n    c = TOQ.Dequeue()\n\n    for each parent p of c, sorted by generation number:\n        # some of maybe in-degree zero are now surely in-degree zero\n        while RRQ.Max > generation(p):\n           r = RRQ.Dequeue()\n           IDQ.Enqueue(r, generation(r))\n\n        AdvanceInDegreeWalk(IDQ, IDV, generation(p))\n        IDV[p]--\n        if IDV[p] == 0:\n            TOQ.Enqueue(p, visit_order++)\n\n    return c\n\n\n> (I mention \"ref visit_order\" to be sure we are\n> passing-by-reference. In a full implementation, the walk details would\n> be grouped into a struct.)\n>\n> This algorithm is relatively simple, but the hard part is teasing the\n> revision walk machinery to initialize the data by calling\n> InitializeTopoOrder(R) and to call GetNextInTopoOrder() whenever it\n> needs a new element of the walk. That is, it is hard to be sure we are\n> not causing side-effects as we make that transformation.\n\nRight. I'll take a look at existing code to find out how involved that\nwould be.\n\nIt is a pity that we cannot simply turn in-degree calculation into\nproducer that calculates in-degree in generation number order, and spits\nit to FIFO pipe / channel / supply / blocking queue, while topo-order\ncalculation reads from in-degree pipe, and spits output to pager...\n\nI wonder if we could use Scientist tool to make sure that new and old\ncode give the same results.\n\n[...]\n>> I think that, beside writing patches for Git, exploring how various\n>> pieces of data and various indexes affect walking commit graphs is also\n>> important. My explorations shown that, for example, that FELINE index\n>> is not good fit for relatively \"narrow\" graphs of revision history.\n>> Exploring this in Python / Jupyter is easier than trying to write a\n>> exploratory patch for Git, in my opinion. Just IMVHO.\n\nActually I should have said that FELINE index for commit graphs (that I\nhave checked) does not show improvement over simply using some\ntopological ordering as negative-cut filter.\n\n>\n> You are right. Ruling out possibilities is the best outcome these\n> prototypes can have. Your work has saved someone a lot of time in\n> investigating that direction.\n\nRegards,\n--\nJakub Narębski\n"},{"id":"347692","messageId":"nycvar.QRO.7.76.6.1805151155160.77@tvgsbejvaqbjf.bet","threadId":"48411","inReplyTo":"864lja2buq.fsf@gmail.com","subject":"Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-05-15T10:01:00Z","receivedAt":"2018-05-15T10:01:20Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Kuba,\n\nOn Mon, 14 May 2018, Jakub Narebski wrote:\n\n> [... lots and lots of discussions...]\n>\n> All right.\n> \n> Here is my [allegedly] improved version, which assumes that we always\n> want to start from commit with maximum generation number (there may be\n> more than one such commit).\n> \n> Let's add one more data structure:\n> \n> RRQ : A queue, for storing remaining commits from R (starting point).\n> It is a priority queue ordered by generation number.\n> \n> \n> InitializeTopoOrder(R):\n>     Initialize IDQ, IDV, TOQ, RRQ\n> \n>     max_generation = 0\n>     visit_order = 0\n> \n>     for each commit c in R:\n>         max_generation = max(max_generation, generation(c))\n>         unless IsRedundantFilter(R / c, c): # optional\n>             RRQ.Enqueue(c, generation(c))\n> \n>     while RRQ.Max == max_generation:\n>         c = RRQ.Dequeue()\n>         IDV[c] = 0 # commits with max gen have in-degree of 0\n>         IDQ.Enqueue(c, generation(c))\n> \n>     # this would be almost no-op\n>     AdvanceInDegreeWalk(IDQ, IDV, max_generation)\n> \n>     for each commit c in reversed R:\n>         if generation(c) == max_generation: # then IDV[c] == 0\n>             TOQ.Enqueue(c, visit_order++)\n> \n>     return (IDQ, IDV, TOQ, RRQ, visit_order)\n\nIsn't it premature to throw out code at this stage? My impression from the\nside lines is that Stolee is trying to get concrete code implemented, code\nthat can be tested against concrete repositories, so that the question of\nsingularly overall importance can be asked: is it worth it, is it really\nfaster? And by how much?\n\nIt may not be the best idea to distract Stolee from said implementation\n(i.e. step 1) by getting ahead ourselves with steps 17, 18 or 19. The next\nsteps would seem to be step 2 and 3, and I am sure that Stolee would\nappreciate your help in implementing them.\n\nSo at this point it would maybe make a lot more sense to help Stolee e.g.\nby refactoring the rev-list code that is a *mess* around the topo order,\nso that all kinds of cute algorithms can be implemented *directly* in Git,\nand put to the ultimate test.\n\nCiao,\nDscho"}]}