{"thread":{"id":"49709","subject":"[RFC] Generation Number v2","startedAt":"2018-10-29T16:55:37Z","lastAt":"2018-11-03T17:27:30Z","messageCount":17,"participants":["Derrick Stolee","Stefan Beller","Junio C Hamano","Ævar Arnfjörð Bjarmason","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"361922","messageId":"6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com","threadId":"49709","inReplyTo":null,"subject":"[RFC] Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-29T16:55:33Z","receivedAt":"2018-10-29T16:55:37Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"We've discussed in several places how to improve upon generation\nnumbers. This RFC is a report based on my investigation into a\nfew new options, and how they compare for Git's purposes on\nseveral existing open-source repos.\n\nYou can find this report and the associated test scripts at\nhttps://github.com/derrickstolee/gen-test.\n\nI have some more work to do in order to make this fully\nreproducible (including a single script to clone all of the\nrepos I used, compute the commit-graphs using the different\nindex versions, and run the tests).\n\nTL;DR: I recommend we pursue one of the following two options:\n\n1. Maximum Generation Number.\n2. Corrected Commit Date.\n\nEach of these perform well, but have different implementation\ndrawbacks. I'd like to hear what everyone thinks about those\ndrawbacks.\n\nPlease also let me know about any additional tests that I could\nrun. Now that I've got a lot of test scripts built up, I can re-run\nthe test suite pretty quickly.\n\nThanks,\n-Stolee\n\n\n\nGeneration Number Performance Test\n==================================\n\nGit uses the commit history to answer many basic questions, such as\ncomputing a merge-base. Some of these algorithms can benefit from a\n_reachability index_, which is a condition that allows us to answer\n\"commit A cannot reach commit B\" in some cases. These require pre-\ncomputing some values that we can load and use at run-time. Git\nalready has a notion of _generation number_, stores it in the commit-\ngraph file, and uses it in several reachability algorithms.\n\nYou can read more about generation numbers and how to use them in\nalgorithms in [this blog \npost](https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/).\n\nHowever, [generation numbers do not always improve our \nalgorithms](https://public-inbox.org/git/pull.28.git.gitgitgadget@gmail.com/T/#u).\nSpecifically, some algorithms in Git already use commit date as a\nheuristic reachability index. This has some problems, though, since\ncommit date can be incorrect for several reasons (clock skew between\nmachines, purposefully setting GIT_COMMIT_DATE to the author date, etc.).\nHowever, the speed boost by using commit date as a cutoff was so\nimportant in these cases, that the potential for incorrect answers was\nconsidered acceptable.\n\nWhen these algorithms were converted to use generation numbers, we\n_added_ the extra constraint that the algorithms are _never incorrect_.\nUnfortunately, this led to some cases where performance was worse than\nbefore. There are known cases where `git merge-base A B` or\n`git log --topo-order A..B` are worse when using generation numbers\nthan when using commit dates.\n\nThis report investigates four replacements for generation numbers, and\ncompares the number of walked commits to the existing algorithms (both\nusing generation numbers and not using them at all). We can use this\ndata to make decisions for the future of the feature.\n\n### Implementation\n\nThe reachability indexes below are implemented in\n[the `reach-perf` branch in \nhttps://github.com/derrickstolee/git](https://github.com/derrickstolee/git/tree/reach-perf).\nThis implementation is in a very rough condition, as it is intended to\nbe a prototype, not production-quality.\n\nUsing this implementation, you can compute commit-graph files for the\nspecified reachability index using `git commit-graph write --reachable \n--version=`.\nThe `git` client will read the version from the file, so our tests\nstore each version as `.git/objects/info/commit-graph.` and copy\nthe necessary file to `.git/objects/info/commit-graph` before testing.\n\nThe algorithms count the number of commits walked, as to avoid the\nnoise that would occur with time-based performance reporting. We use\nthe (in progress) trace2 library for this. To find the values reported,\nuse the `GIT_TR2_PERFORMANCE` environment variable.\n\nTo ignore reachability indexes entirely and use the old algorithms\n(reported here as \"OLD\" values) use the environment variable\n`GIT_TEST_OLD_PAINT=1`.\n\n\nReachability Index Versions\n---------------------------\n\n**V0: (Minimum) Generation Number.**\nThe _generation number_ of a commit is exactly one more than the maximum\ngeneration number of a parent (by convention, the generation number of a\ncommit with no parents is 1). This is the definition currently used by\nGit (2.19.0 and later). Given two commits A and B, we can then use the\nfollowing reachability index:\n\n     If gen(A) < gen(B), then A cannot reach B.\n\n_Commentary:_ One issue with generation numbers is that some algorithms\nin Git use commit date as a heuristic, and allow incorrect answers if\nthere is enough clock skew. Using that heuristic, the algorithms can walk\nfewer commits than the algorithms using generation number. The other\nreachability indexes introduced below attempt to fix this problem.\n\n**V1: (Epoch, Date) Pairs.**\nFor each commit, store a pair of values called the _epoch_ and the _date_.\nThe date is the normal commit date. The _epoch_ of a commit is the minimum\nX such that X is at least the maximum epoch of each parent, and at least\none more than the epoch of any parent whose date is larger than the date\nof this commit (i.e. there is clock skew between this commit and this\nparent). In this way, we can use the following reachability index:\n\n    If epoch(A) < epoch(B), then A cannot reach B.\n    If epoch(A) == epoch(B) and date(A) < date(B), then A cannot reach B.\n\n**V2: Maximum Generation Numbers.**\nThe _maximum generation number_ of a commit (denoted by maxgen(A)) is\ndefined using its _children_ and the total number of commits in the repo.\nIf A is a commit with no children (that is, there is no commit B with\nA as a parent) then maxgen(A) is equal to the number of commits in the repo.\nFor all other commits A, maxgen(A) is one less than the minimum maxgen(B)\namong children B. This can be computed by initializing maxgen(C) to the\nnumber of commits, then walking the commit graph in topological order,\nassigning maxgen(P) = min { maxgen(P), maxgen(C) - 1 } for each parent P\nof the currently-walking commit C. We then have the same reachability\nindex as minimum generation number:\n\n   If maxgen(A) < maxgen(B), then A cannot reach B.\n\n_Commentary:_ The known examples where (minimum) generation numbers perform\nworse than commit date heuristics involve commits with recent commit dates\nbut whose parents have very low generation number compared to most recent\ncommits. In a way, minimum generation numbers increase the odds that we\ncan say \"A cannot reach B\" when A is fixed and B is selected at random.\nMaximum generation numbers increase the odds that we can say \"A cannot\nreach B\" when B is fixed and A is selected at random. This helps us when\nwe are exploring during a reachability algorithm and have explored few\ncommits and want to say that the large set of unexplored commits cannot\nreach any of the explored commits.\n\n**V3: Corrected Commit Date.**\nFor a commit C, let its _corrected commit date_ (denoted by cdate(C))\nbe the maximum of the commit date of C and the commit dates of its\nparents.\n\n   If cdate(A) < cdate(B), then A cannot reach B.\n\n**V4: FELINE Index.**\nThe FELINE index is a two-dimentional reachability index as defined in\n[Reachability Queries in Very Large Graphs: A Fast Refined Online Search \nApproach](https://openproceedings.org/EDBT/2014/paper_166.pdf)\nby Veloso, Cerf, Jeira, and Zaki. The index is not deterministically\ndefined, but instead is defined in the following way:\n\n1. Compute a reverse topological order of the commits. Let felineX(C)\n    be the position in which C appears in this list. Since this is\n    a reverse topological order, felineX(C) > felineX(P) for each parent\n    P of C.\n\n2. Compute a reverse topological order of the commits using Kahn's\n    algorithm, but when selecting among a list of commits with in-degree\n    zero, prioritize the commit by minimizing felineX. Let felineY(C)\n    be the position in which C appears in this list.\n\nEssentially, the felineY order is selected with the goal of swapping\npositions of topologically-independent commits relative to the felinX\nordering. The resulting reachability index is as follows:\n\n    If felineX(A) < felineY(B), then A cannot reach B.\n    If felineY(A) < felineY(B), then A cannot reach B.\n\n_Commentary:_ In terms of comparing two commits directly, this index\nis quite strong. However, when we are performing our reachability\nalgorithms that care about reachable sets (git log --graph), or\nboundaries between reachable sets (git merge-base, git log --graph A..B)\nwe need to track a single pair (minX,minY) for comparion. In order to not\nmiss anything during our search, we need to update this pair to be\nthe minimum felineX(A) and minimum felineY(B) among all explored commits\nA and B. That is, the pair (minX, minY) is below our entire explored set.\nThis can be a disadvantage for these algorithms.\n\n### Comparing Reachability Index Versions Viability\n\nBefore considering how well these indexes perform during our algorithm\nruns, let's take a moment to consider the implementation details and\nhow they relate to the existing commit-graph file format and existing\nGit clients.\n\n* **Compatible?** In our test implementation, we use a previously unused\n   byte of data in the commit-graph format to indicate which reachability\n   index version we are using. Existing clients ignore this value, so we\n   will want to consider if these new indexes are _backwards compatible_.\n   That is, will they still report correct values if they ignore this byte\n   and use the generation number column from the commit-graph file assuming\n   the values are minimum generation numbers?\n\n* **Immutable?** Git objects are _immutable_. If you change an object you\n   actually create a new object with a new object ID. Are the values we \nstore\n   for these reachability indexes also immutable?\n\n* **Local?** Are these values **locally computable**? That is, do we only\n   need to look at the parents of a commit (assuming those parents have\n   computed values) in order to determine the value at that commit?\n\n| Index                     | Compatible? | Immutable? | Local? |\n|---------------------------|-------------|------------|--------|\n| Minimum Generation Number | Yes         | Yes        | Yes    |\n| (Epoch, Date) pairs       | Yes         | Yes        | Yes    |\n| Maximum Generation Number | Yes         | No         | No     |\n| Corrected Commit Date     | No          | Yes        | Yes    |\n| FELINE index              | Yes         | No         | No     |\n\n_Note:_ The corrected commit date uses the generation number column\nto store an offset of \"how much do I need to add to my commit date\nto get my corrected commit date?\" The values stored in that column\nare then not backwards-compatible.\n\n_Note:_ The FELINE index requires storing two values instead of just\none. One of these values could be stored in the generation number\ncolumn and the other in an optional chunk, hence it could be backwards\ncompatible. (This is not how it is implemented in our example\nimplementation.)\n\n\nData\n----\n\nWe focused on three types of performance tests that test the indexes\nin different ways. Each test lists the `git` command that is used,\nand the table lists which repository is used and which inputs.\n\n### Test 1: `git log --topo-order -N`\n\nThis test focuses on the number of commits that are parsed during\na `git log --topo-order` before writing `N` commits to output.\n\nYou can reproduce this test using `topo-order-tests.sh` and\nsee all the data in `topo-order-summary.txt`. The values reported\nhere are a sampling of the data, ignoring tests where all values\nwere the same or extremely close in value.\n\n\n| Repo         | N     | V0     | V1     | V2     | V3 | V4    |\n|--------------|-------|--------|--------|--------|--------|-------|\n| android-base | 100   |  5,487 |  8,534 |  6,937 |  6,419 | 6,453 |\n| android-base | 1000  | 36,029 | 44,030 | 41,493 | 41,206 |45,431 |\n| chromium     | 100   |    101 |424,406 |    101 |    101 |   101 |\n| gerrit       | 100   |  8,212 |  8,533 |    164 |    159 |   162 |\n| gerrit       | 1000  |  8,512 |  8,533 |  1,990 |  1,973 | 3,766 |\n| Linux        | 100   | 12,458 | 12,444 | 13,683 | 13,123 |13,124 |\n| Linux        | 1000  | 24,436 | 26,247 | 27,878 | 26,430 |27,875 |\n| Linux        | 10000 | 30,364 | 28,891 | 27,878 | 26,430 |27,875 |\n| electron     | 1000  | 19,927 | 18,733 |  1,072 | 18,214 |18,214 |\n| Ffmpeg       | 10000 | 32,154 | 47,429 | 10,435 | 11,054 |11,054 |\n| jgit         | 1000  |  1,550 |  6,264 |  1,067 |  1,060 | 1,233 |\n| julia        | 10000 | 43,043 | 43,043 | 10,201 | 23,505 |23,828 |\n| odoo         | 1000  | 17,175 |  9,714 |  4,043 |  4,046 | 4,111 |\n| php-src      | 1000  | 19,014 | 27,530 |  1,311 |  1,305 | 1,320 |\n| rails        | 100   |  1,420 |  2,041 |  1,757 |  1,428 | 1,441 |\n| rails        | 1000  |  7,952 | 10,145 | 10,053 |  8,373 | 8,373 |\n| swift        | 1000  |  1,914 |  4,004 |  2,071 |  1,939 | 1,940 |\n| tensorflow   | 1000  | 10,019 | 39,221 |  6,711 | 10,051 |10,051 |\n| TypeScript   | 1000  |  2,873 | 12,014 |  3,049 |  2,876 | 2,876 |\n\n\n### Test 2: `git log --topo-order -10 A..B`\n\nThis test focuses on the number of commits that are parsed during\na `git log --topo-order A..B` before writing ten commits to output.\nSince we fix a very small set of output commits, we care more about\nthe part of the walk that determines which commits are reachable\nfrom `B` but not reachable from `A`. This part of the walk uses\ncommit date as a heuristic in the existing implementation.\n\nYou can reproduce this test using `topo-compare-tests.sh` and\nsee all the data in `topo-compare-summary.txt`. The values reported\nhere are a sampling of the data, ignoring tests where all values\nwere the same or extremely close in value.\n\n_Note:_ For some of the rows, the `A` and `B` values may be\nswapped from what is expected. This is due to (1) a bug in the\nreference implementation that doesn't short-circuit the walk\nwhen `A` can reach `B`, and (2) data-entry errors by the author.\nThe bug can be fixed, but would have introduced strange-looking\nrows in this table.\n\n| Repo         | A            | B            | OLD     | V0     | V1     \n| V2     | V3      | V4     |\n|--------------|--------------|--------------|---------|--------|--------|--------|---------|--------|\n| android-base | 53c1972bc8f  | 92f18ac3e39  |  39,403 | 1,544 |  6,957 \n|     26 |   1,015 |  1,098 |\n| gerrit       | c4311f7642   | 777a8cd1e0   |   6,457 | 7,836 | 10,869 \n|    415 |     414 |    445 |\n| electron     | 7da7dd85e    | addf069f2    |  18,164 | 945 |  6,528 \n|     17 |      17 |     18 |\n| julia        | 7faee1b201   | e2022b9f0f   |  22,800 | 4,221 | 12,710 \n|    377 |     213 |    213 |\n| julia        | ae69259cd9   | c8b5402afc   |   1,864 | 1,859 | 13,287 \n|     12 |   1,859 |  1,859 |\n| Linux        | 69973b830859 | c470abd4fde4 | 111,692 | 77,263 | 96,598 \n| 80,238 |  76,332 | 76,495 |\n| Linux        | c3b92c878736 | 19f949f52599 | 167,418 | 5,736 |  4,684 \n|  9,675 |   3,887 |  3,923 |\n| Linux        | c8d2bc9bc39e | 69973b830859 |  44,940 | 4,056 | 16,636 \n| 10,405 |   3,475 |  4,022 |\n| odoo         | 4a31f55d0a0  | 93fb2b4a616  |  25,139 | 19,528 | 20,418 \n| 19,874 |  19,634 | 27,247 |\n| swift        | 4046359efd   | b34b6a14c7   |  13,411 | 662 |    321 \n|     12 |      80 |    134 |\n| tensorflow   | ec6d17219c   | fa1db5eb0d   |  10,373 | 4,762 | 36,272 \n|    174 |   3,631 |  3,632 |\n| TypeScript   | 35ea2bea76   | 123edced90   |   3,450 | 267 | 10,386 \n|     27 |     259 |    259 |\n\n\n### Test 3: `git merge-base A B`\n\nThis test focuses on the number of commits that are parsed during\na `git merge-base A B`. This part of the walk uses commit date as\na heuristic in the existing implementation.\n\nYou can reproduce this test using `merge-base-tests.sh` and\nsee all the data in `merge-base-summary.txt`. The values reported\nhere are a sampling of the data, ignoring tests where all values\nwere the same or extremely close in value.\n\n\n| Repo         | A            | B            | OLD     | V0      | \nV1      | V2      | V3      | V4      |\n|--------------|--------------|--------------|---------|---------|---------|---------|---------|---------|\n| android-base | 53c1972bc8f  | 92f18ac3e39  |  81,999 | 109,025 |  \n81,885 |  77,475 |  81,999 |  82,001 |\n| gerrit       | c4311f7642   | 777a8cd1e0   |   6,468 | 7,995 |   6,566 \n|   6,478 |   6,468 |   6,468 |\n| electron     | 7da7dd85e    | addf069f2    |  18,160 | 19,871 |  \n18,670 |   2,231 |  18,160 |  18,160 |\n| julia        | 7faee1b201   | e2022b9f0f   |  22,803 | 42,339 |  \n42,212 |   6,803 |  22,803 |  22,803 |\n| julia        | c8b5402afc   | ae69259cd9   |   7,076 | 42,909 |  \n42,770 |   2,690 |   7,076 |   7,076 |\n| Linux        | 69973b830859 | c470abd4fde4 |  44,984 | 47,457 |  \n44,679 |  38,461 |  44,984 |  44,984 |\n| Linux        | c3b92c878736 | 19f949f52599 | 111,740 | 111,027 | \n111,196 | 107,835 | 111,771 | 111,368 |\n| Linux        | c8d2bc9bc39e | 69973b830859 | 167,468 | 635,579 | \n630,138 |  33,716 | 167,496 | 153,774 |\n| odoo         | 4a31f55d0a0  | 93fb2b4a616  |  25,150 | 27,259 |  \n23,977 |  24,041 |  23,974 |  26,829 |\n| swift        | 4046359efd   | b34b6a14c7   |  13,434 | 13,254 |  \n13,940 |  16,023 |  13,127 |  15,008 |\n| tensorflow   | ec6d17219c   | fa1db5eb0d   |  10,377 | 10,448 |  \n10,377 |   8,460 |  10,377 |  10,377 |\n| TypeScript   | 35ea2bea76   | 123edced90   |   3,464 | 3,439 |   3,464 \n|   3,581 |   3,464 |   3,464 |\n\n\nConclusions\n-----------\n\nBased on the performance results alone, we should remove minimum\ngeneration numbers, (epoch, date) pairs, and FELINE index from\nconsideration. There are enough examples of these indexes performing\npoorly.\n\nIn contrast, maximum generation numbers and corrected commit\ndates both performed quite well. They are frequently the top\ntwo performing indexes, and rarely significantly different.\n\nThe trade-off here now seems to be: which _property_ is more important,\nlocally-computable or backwards-compatible?\n\n* Maximum generation number is backwards-compatible but not\n   locally-computable or immutable.\n\n* Corrected commit-date is locally-computable and immutable,\n   but not backwards-compatible.\n\n_Editor's Note:_ Every time I think about this trade-off, I can't\ncome to a hard conclusion about which is better. Instead, I'll\nleave that up for discussion.\n\n\n"},{"id":"361937","messageId":"CAGZ79ka-FTqaXdrMixjUp2THJ3L0YvEnkKxs3XFgB3WEEy2-Tg@mail.gmail.com","threadId":"49709","inReplyTo":"6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-10-29T19:22:03Z","receivedAt":"2018-10-29T19:22:18Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"> Based on the performance results alone, we should remove minimum\n> generation numbers, (epoch, date) pairs, and FELINE index from\n> consideration. There are enough examples of these indexes performing\n> poorly.\n>\n> In contrast, maximum generation numbers and corrected commit\n> dates both performed quite well. They are frequently the top\n> two performing indexes, and rarely significantly different.\n>\n> The trade-off here now seems to be: which _property_ is more important,\n> locally-computable or backwards-compatible?\n>\n> * Maximum generation number is backwards-compatible but not\n> locally-computable or immutable.\n\nThese maximum generation numbers sound like the reverse of\nthe generation numbers as they are currently implemented, i.e.\nwe count all commits between the commit A and all heads.\nHow would this impact creation of a commit?\n\nThe current generation numbers can be lazily updated or not\nupdated at all. In my understanding of the maximum generation\nnumbers, a new commit would make these maximum generation\nnumbers invalid (i.e. they have to be recomputed).\n\nAre there ways out by deferring the computation of maximum\ngeneration numbers while still being able to work with some\ncommits that are un-accounted for?\n\nWhen recomputing these numbers, the current generation number\n(V0) has the property that already existing numbers can be re-used\nas-is. We only need to compute the numbers for new commits,\nand then insert this to the appropriate data structures (which is\na separate problem, one could imagine a split generation\nnumbers file like the split index)\n\nFor the V2 maximum generation numbers, would we need to\nrewrite the numbers for all commits once we recompute them?\nAssuming that is true, it sounds like the benchmark doesn't\ncover the whole costs associated with V2, which is why the\nexceptional performance can be explained.\n\n(Note: The table as read in\nhttps://public-inbox.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\nseems line broken, using gmails web interface is not good\nfor ASCII art and patches, git-send-email would fare better)\n\n>\n> * Corrected commit-date is locally-computable and immutable,\n> but not backwards-compatible.\n\nHow are these dates not backwards incompatible?\nWe don't have to expose these dates to the user, but\n- just like generation numbers - could store them and use them\nbut not tell the user about it.\n\nWe would need to be really careful to not expose them at all\nas they look like the real dates, so that could make for an\nawkward bug report.\n\nThe approach of \"corrected commit date\" sounds like we could\nhave a very lazy approach, i.e. no extra data structures needed\nfor many commits (as the corrected date equals the real date)\nand only need to store the corrections for some commits.\nSuch an approach however would not make it easy to know\nif we operate on corrected dates, or if we even checked them\nfor correctness before.\n\nSo if we'd have an additional row in the generation numbers file\ntelling the corrected date, then we should be able to be backwards\ncompatible?\n"},{"id":"361939","messageId":"78882b71-09b2-cb4a-4285-5aa7b61907fe@gmail.com","threadId":"49709","inReplyTo":"CAGZ79ka-FTqaXdrMixjUp2THJ3L0YvEnkKxs3XFgB3WEEy2-Tg@mail.gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-29T20:06:59Z","receivedAt":"2018-10-29T20:07:02Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/29/2018 3:22 PM, Stefan Beller wrote:\n>> Based on the performance results alone, we should remove minimum\n>> generation numbers, (epoch, date) pairs, and FELINE index from\n>> consideration. There are enough examples of these indexes performing\n>> poorly.\n>>\n>> In contrast, maximum generation numbers and corrected commit\n>> dates both performed quite well. They are frequently the top\n>> two performing indexes, and rarely significantly different.\n>>\n>> The trade-off here now seems to be: which _property_ is more important,\n>> locally-computable or backwards-compatible?\n>>\n>> * Maximum generation number is backwards-compatible but not\n>> locally-computable or immutable.\n> These maximum generation numbers sound like the reverse of\n> the generation numbers as they are currently implemented, i.e.\n> we count all commits between the commit A and all heads.\n> How would this impact creation of a commit?\n\nThe indexes listed here would be computed at the same time as a \ncommit-graph (and only change on commit-graph writes).\n\nThis idea of having something depend on the \"global state\" isn't ideal \n(in my opinion) but it certainly works for the tests specified below.\n\n> The current generation numbers can be lazily updated or not\n> updated at all. In my understanding of the maximum generation\n> numbers, a new commit would make these maximum generation\n> numbers invalid (i.e. they have to be recomputed).\n\nNew commits would change the value you would get by the definition (on \nrewrite of the commit-graph) but don't violate the reachability index \nproperty (maxgen(A) < maxgen(B) =>\nA can't reach B). So that doesn't effect their usefulness.\n\n> Are there ways out by deferring the computation of maximum\n> generation numbers while still being able to work with some\n> commits that are un-accounted for?\n\nCreating a commit that doesn't exist in the commit-graph file results in \na commit with generation number INFINITY. The new commits can't be \nreached by commits with finite generation number.\n\n> When recomputing these numbers, the current generation number\n> (V0) has the property that already existing numbers can be re-used\n> as-is. We only need to compute the numbers for new commits,\n> and then insert this to the appropriate data structures (which is\n> a separate problem, one could imagine a split generation\n> numbers file like the split index)\n>\n> For the V2 maximum generation numbers, would we need to\n> rewrite the numbers for all commits once we recompute them?\n> Assuming that is true, it sounds like the benchmark doesn't\n> cover the whole costs associated with V2, which is why the\n> exceptional performance can be explained.\nYou're right, we need to recompute the entire list of maximum generation \nnumber values. However, you are a bit hung up on \"maxgen\" being a fixed \nfunction that is correct at all times. We could compute the \"maxgen\" for \nthe set of commits that are written to the \"split\" commit-graph while \nleaving the base the same. There is one tricky part here: we need to \ninitialize the values starting at \"num commits in the combined \ncommit-graph\" (commits in the base and split portion). The minimum \npossible value in the split portion will be larger than the maximum \npossible value in the base portion. Since the (future) implementation of \nsplit commit-graphs would have all commit-parent edges pointing down \ninto the base and not from the base into the split, this will continue \nto satisfy our reachability index property.\n\nAs for the cost: we need to do a topo-order walk and then a quick \nminimum-value check across all parents. This is O(N), and the constant \nis small. This may be a cost worth paying.\n\n> (Note: The table as read in\n> https://public-inbox.org/git/6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com/\n> seems line broken, using gmails web interface is not good\n> for ASCII art and patches, git-send-email would fare better)\n\nSorry for that. I copy-pasted into Thunderbird. Hopefully most users can \nredirect to the GitHub-rendered markdown if they have trouble.\n\n>\n>> * Corrected commit-date is locally-computable and immutable,\n>> but not backwards-compatible.\n> How are these dates not backwards incompatible?\n> We don't have to expose these dates to the user, but\n> - just like generation numbers - could store them and use them\n> but not tell the user about it.\n>\n> We would need to be really careful to not expose them at all\n> as they look like the real dates, so that could make for an\n> awkward bug report.\n\nBy \"backwards-compatible\" I mean that we could store them in the \ncommit-graph file without breaking existing clients (or by introducing \nextra data).\n\nWe could easily add these corrected commit dates as an optional chunk, \nbut that adds 8 bytes per commit, and we already use 8 bytes for the \n(generation, date) pairs.\n\nThe solution I made in my prototype is to replace the generation number \nwith an offset for how much to add to the commit-date to get the \ncorrected commit-date. However, an old client would interpret these \noffsets as generations and have incorrect output.\n\nA potential way to get around this is to consider the pair (offset, \ndate) and define the offset(C) to be the minimum of min { offset(P), \ndate(P) - date(C) }. This would satisfy the requirements for the V0 \nreachability index. I'm making a note to implement _this_ version and \ngive it a test.\n\n>\n> The approach of \"corrected commit date\" sounds like we could\n> have a very lazy approach, i.e. no extra data structures needed\n> for many commits (as the corrected date equals the real date)\n> and only need to store the corrections for some commits.\n> Such an approach however would not make it easy to know\n> if we operate on corrected dates, or if we even checked them\n> for correctness before.\n>\n> So if we'd have an additional row in the generation numbers file\n> telling the corrected date, then we should be able to be backwards\n> compatible?\nYeah, an optional chunk with the corrected date would work, but be wasteful.\n\nThanks,\n-Stolee\n"},{"id":"361941","messageId":"3576719c-3cfb-547a-3548-3aaebfe6e8a2@gmail.com","threadId":"49709","inReplyTo":"6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-29T20:25:40Z","receivedAt":"2018-10-29T20:25:42Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Here is a re-formatted version of the tables I introduced earlier.\nThe tables were too wide for public-inbox to render correctly (when\npaired with my email client). Hopefully this bulleted-list format\nworks better. Thanks, Stefan, for pointing out the rendering\nproblems!\n\n### Test 1: `git log --topo-order -N`\n\nThis test focuses on the number of commits that are parsed during\na `git log --topo-order` before writing `N` commits to output.\n\nYou can reproduce this test using `topo-order-tests.sh` and\nsee all the data in `topo-order-summary.txt`. The values reported\nhere are a sampling of the data, ignoring tests where all values\nwere the same or extremely close in value.\n\nandroid-base, N = 100\n     V0: 5487\n     V1: 8534\n     V2: 6937\n     V3: 6419\n     V4: 6453\nandroid-base, N = 1000\n     V0: 36029\n     V1: 44030\n     V2: 41493\n     V3: 41206\n     V4: 45431\nchromium, N = 100\n     V0:    101\n     V1: 424406\n     V2:    101\n     V3:    101\n     V4:    101\ngerrit, N = 100\n     V0: 8212\n     V1: 8533\n     V2:  164\n     V3:  159\n     V4:  162\ngerrit, N = 1000\n     V0: 8512\n     V1: 8533\n     V2: 1990\n     V3: 1973\n     V4: 3766\nLinux, N = 100\n     V0: 12458\n     V1: 12444\n     V2: 13683\n     V3: 13123\n     V4: 13124\nLinux, N = 1000\n     V0: 24436\n     V1: 26247\n     V2: 27878\n     V3: 26430\n     V4: 27875\nLinux, N = 10000\n     V0: 30364\n     V1: 28891\n     V2: 27878\n     V3: 26430\n     V4: 27875\nelectron, N = 1000\n     V0: 19927\n     V1: 18733\n     V2:  1072\n     V3: 18214\n     V4: 18214\nFfmpeg, N = 10000\n     V0: 32154\n     V1: 47429\n     V2: 10435\n     V3: 11054\n     V4: 11054\njgit, N = 1000\n     V0: 1550\n     V1: 6264\n     V2: 1067\n     V3: 1060\n     V4: 1233\njulia, N = 10000\n     V0: 43043\n     V1: 43043\n     V2: 10201\n     V3: 23505\n     V4: 23828\nodoo, N = 1000\n     V0: 17175\n     V1:  9714\n     V2:  4043\n     V3:  4046\n     V4:  4111\nphp-src, N = 1000\n     V0: 19014\n     V1: 27530\n     V2:  1311\n     V3:  1305\n     V4:  1320\nrails, N = 100\n     V0: 1420\n     V1: 2041\n     V2: 1757\n     V3: 1428\n     V4: 1441\nrails, N = 1000\n     V0:  7952\n     V1: 10145\n     V2: 10053\n     V3:  8373\n     V4:  8373\nswift, N = 1000\n     V0: 1914\n     V1: 4004\n     V2: 2071\n     V3: 1939\n     V4: 1940\ntensorflow, N = 1000\n     V0: 10019\n     V1: 39221\n     V2:  6711\n     V3: 10051\n     V4: 10051\nTypeScript, N = 1000\n     V0:  2873\n     V1: 12014\n     V2:  3049\n     V3:  2876\n     V4:  2876\n\n\n### Test 2: `git log --topo-order -10 A..B`\n\nThis test focuses on the number of commits that are parsed during\na `git log --topo-order A..B` before writing ten commits to output.\nSince we fix a very small set of output commits, we care more about\nthe part of the walk that determines which commits are reachable\nfrom `B` but not reachable from `A`. This part of the walk uses\ncommit date as a heuristic in the existing implementation.\n\nYou can reproduce this test using `topo-compare-tests.sh` and\nsee all the data in `topo-compare-summary.txt`. The values reported\nhere are a sampling of the data, ignoring tests where all values\nwere the same or extremely close in value.\n\n_Note:_ For some of the rows, the `A` and `B` values may be\nswapped from what is expected. This is due to (1) a bug in the\nreference implementation that doesn't short-circuit the walk\nwhen `A` can reach `B`, and (2) data-entry errors by the author.\nThe bug can be fixed, but would have introduced strange-looking\nrows in this table.\n\nandroid-base 53c1972bc8f 92f18ac3e39\n   OLD: 39403\n    V0:  1544\n    V1:  6957\n    V2:    26\n    V3:  1015\n    V4:  1098\ngerrit c4311f7642 777a8cd1e0\n   OLD:  6457\n    V0:  7836\n    V1: 10869\n    V2:   415\n    V3:   414\n    V4:   445\nelectron 7da7dd85e addf069f2\n   OLD: 18164\n    V0:   945\n    V1:  6528\n    V2:    17\n    V3:    17\n    V4:    18\njulia 7faee1b201 e2022b9f0f\n   OLD: 22800\n    V0:  4221\n    V1: 12710\n    V2:   377\n    V3:   213\n    V4:   213\njulia ae69259cd9 c8b5402afc\n   OLD:  1864\n    V0:  1859\n    V1: 13287\n    V2:    12\n    V3:  1859\n    V4:  1859\nLinux 69973b830859 c470abd4fde4\n   OLD: 111692\n    V0:  77263\n    V1:  96598\n    V2:  80238\n    V3:  76332\n    V4:  76495\nLinux c3b92c878736 19f949f52599\n   OLD: 167418\n    V0:   5736\n    V1:   4684\n    V2:   9675\n    V3:   3887\n    V4:   3923\nLinux c8d2bc9bc39e 69973b830859\n   OLD: 44940\n    V0:  4056\n    V1: 16636\n    V2: 10405\n    V3:  3475\n    V4:  4022\nodoo 4a31f55d0a0 93fb2b4a616\n   OLD: 25139\n    V0: 19528\n    V1: 20418\n    V2: 19874\n    V3: 19634\n    V4: 27247\nswift 4046359efd b34b6a14c7\n   OLD: 13411\n    V0:   662\n    V1:   321\n    V2:    12\n    V3:    80\n    V4:   134\ntensorflow ec6d17219c fa1db5eb0d\n   OLD: 10373\n    V0:  4762\n    V1: 36272\n    V2:   174\n    V3:  3631\n    V4:  3632\nTypeScript 35ea2bea76 123edced90\n   OLD:  3450\n    V0:   267\n    V1: 10386\n    V2:    27\n    V3:   259\n    V4:   259\n\n\n### Test 3: `git merge-base A B`\n\nThis test focuses on the number of commits that are parsed during\na `git merge-base A B`. This part of the walk uses commit date as\na heuristic in the existing implementation.\n\nYou can reproduce this test using `merge-base-tests.sh` and\nsee all the data in `merge-base-summary.txt`. The values reported\nhere are a sampling of the data, ignoring tests where all values\nwere the same or extremely close in value.\n\nandroid-base 53c1972bc8f 92f18ac3e39\n   OLD:  81999\n    V0: 109025\n    V1:  81885\n    V2:  77475\n    V3:  81999\n    V4:  82001\ngerrit c4311f7642 777a8cd1e0\n   OLD: 6468\n    V0: 7995\n    V1: 6566\n    V2: 6478\n    V3: 6468\n    V4: 6468\nelectron 7da7dd85e addf069f2\n   OLD: 18160\n    V0: 19871\n    V1: 18670\n    V2:  2231\n    V3: 18160\n    V4: 18160\njulia 7faee1b201 e2022b9f0f\n   OLD: 22803\n    V0: 42339\n    V1: 42212\n    V2:  6803\n    V3: 22803\n    V4: 22803\njulia c8b5402afc ae69259cd9\n   OLD:  7076\n    V0: 42909\n    V1: 42770\n    V2:  2690\n    V3:  7076\n    V4:  7076\nLinux 69973b830859 c470abd4fde4\n   OLD: 44984\n    V0: 47457\n    V1: 44679\n    V2: 38461\n    V3: 44984\n    V4: 44984\nLinux c3b92c878736 19f949f52599\n   OLD: 111740\n    V0: 111027\n    V1: 111196\n    V2: 107835\n    V3: 111771\n    V4: 111368\nLinux c8d2bc9bc39e 69973b830859\n   OLD: 167468\n    V0: 635579\n    V1: 630138\n    V2:  33716\n    V3: 167496\n    V4: 153774\nodoo 4a31f55d0a0 93fb2b4a616\n   OLD: 25150\n    V0: 27259\n    V1: 23977\n    V2: 24041\n    V3: 23974\n    V4: 26829\nswift 4046359efd b34b6a14c7\n   OLD: 13434\n    V0: 13254\n    V1: 13940\n    V2: 16023\n    V3: 13127\n    V4: 15008\ntensorflow ec6d17219c fa1db5eb0d\n   OLD: 10377\n    V0: 10448\n    V1: 10377\n    V2:  8460\n    V3: 10377\n    V4: 10377\nTypeScript 35ea2bea76 123edced90\n   OLD: 3464\n    V0: 3439\n    V1: 3464\n    V2: 3581\n    V3: 3464\n    V4: 3464\n\n"},{"id":"361962","messageId":"xmqqy3ag13us.fsf@gitster-ct.c.googlers.com","threadId":"49709","inReplyTo":"6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-30T03:59:55Z","receivedAt":"2018-10-30T04:00:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> **V3: Corrected Commit Date.**\n> For a commit C, let its _corrected commit date_ (denoted by cdate(C))\n> be the maximum of the commit date of C and the commit dates of its\n> parents.\n\n\"maximum of the commit date of C and the corrected commit dates of\nits parents\"?\n\nWe've talked about exactly this one in the past (long before any of\nMicrosoft folks other than Dscho came to the scene) but without an\nimplementation, or detailed design and analysis. I am very happy to\nsee the idea among other possibilities to be considered again. This\ntime around, we may finally come up with something better than the\n\"commit dates with SLOP\" thing ;-).\n\n> Essentially, the felineY order is selected with the goal of swapping\n> positions of topologically-independent commits relative to the felinX\n> ordering. The resulting reachability index is as follows:\n>\n> If felineX(A) < felineY(B), then A cannot reach B.\n> If felineY(A) < felineY(B), then A cannot reach B.\n\nI presume that the first line is a typo and you compare the same X index?\n\n> * **Compatible?** In our test implementation, we use a previously unused\n> byte of data in the commit-graph format to indicate which reachability\n> index version we are using. Existing clients ignore this value, so we\n> will want to consider if these new indexes are _backwards compatible_.\n> That is, will they still report correct values if they ignore this byte\n> and use the generation number column from the commit-graph file assuming\n> the values are minimum generation numbers?\n\nI personally consider that the current commit-graph with generation\nnumbers experimental, so I am not sure how much we care about this.\n\nHaving said that.\n\nBy the above definition, any new index that is wider than the\ncurrent generation number cannot be compatible (can we even tell the\nexisting clients how wide each elements in the ix array is?)\n\nIn any case, perhaps the first thing to do is to update the clients\nso that they stop ignoring the version number field, and instead\nwork without generation number when there is no version of reach.ix\navailable in the file? That way, a better reachablility index can\nbe chosen freely without having to worry about the compatibility.\n\n> * **Immutable?** Git objects are _immutable_. If you change an object you\n> actually create a new object with a new object ID. Are the values we\n> store\n> for these reachability indexes also immutable?\n\nEven if we do not embed the reachability ix in commit objects,\nhaving an immutable value is probably a must if we want to make them\nincrementally computable, so this is a very good property to have.\nUnless there is a clever idea to incrementally compute a mutable\nreach.ix, my gut instinct says that this property is a must.\n\nAnother thing, perhaps related to \"local\" below, is if exactly the\nsame reach.ix is computed by anybody, given an identical commit\nhistory graph (perhaps \"reproducibility\"?). I think most of the\ncandidates you listed are reproducible without a fixed tie-breaker,\nbut I am not sure about felineY() thing.\n\n> * **Local?** Are these values **locally computable**? That is, do we only\n> need to look at the parents of a commit (assuming those parents have\n> computed values) in order to determine the value at that commit?\n\nA subset of non-local reachability ix, for example, the ones that\nneed to know what each commit's children are, cannot be immutable,\nas adding new objects to the graph (either with locally committing,\nor transferring objects from other repositories) would affect the\nix; is this true for all non-local reachability ix, I wonder?\n\n> We focused on three types of performance tests that test the indexes\n> in different ways. Each test lists the `git` command that is used,\n> and the table lists which repository is used and which inputs.\n>\n> ### Test 1: `git log --topo-order -N`\n>\n> This test focuses on the number of commits that are parsed during\n> a `git log --topo-order` before writing `N` commits to output.\n\nA devil's advocate comment. Your patches seem to be very focused on\nthis \"unlimited\" case for the past few weeks, but I am not so sure\nif that is a case worth optimizing for. If \"git log --topo-order -N\nHEAD~M..\" (for some number M) gives us a similar result as unlimited\ncase but with much less effort, wouldn't it be good enough that lets\nus concentrate on other use cases instead?\n\n> Based on the performance results alone, we should remove minimum\n> generation numbers, (epoch, date) pairs, and FELINE index from\n> consideration. There are enough examples of these indexes performing\n> poorly.\n\nOK.\n\n> In contrast, maximum generation numbers and corrected commit\n> dates both performed quite well. They are frequently the top\n> two performing indexes, and rarely significantly different.\n>\n> The trade-off here now seems to be: which _property_ is more important,\n> locally-computable or backwards-compatible?\n\nNice summary. \n\nAs I already said, I personally do not think being compatible with\ncurrently deployed clients is important at all (primarily because I\nstill consider the whole thing experimental), and there is a clear\nway forward once we correct the mistake of not having a version\nnumber in the file format that tells the updated clients to ignore\nthe generation numbers. For longer term viability, we should pick\nsomething that is immutable, reproducible, computable with minimum\ninput---all of which would lead to being incrementally computable, I\nwould think.\n\n"},{"id":"362096","messageId":"61a829ce-0d29-81c9-880e-7aef1bec916e@gmail.com","threadId":"49709","inReplyTo":"xmqqy3ag13us.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC] Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-31T12:30:29Z","receivedAt":"2018-10-31T12:30:32Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/29/2018 11:59 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> **V3: Corrected Commit Date.**\n>> For a commit C, let its _corrected commit date_ (denoted by cdate(C))\n>> be the maximum of the commit date of C and the commit dates of its\n>> parents.\n> \"maximum of the commit date of C and the corrected commit dates of\n> its parents\"?\n\nThat's what I mean. Thanks.\n\n>\n> We've talked about exactly this one in the past (long before any of\n> Microsoft folks other than Dscho came to the scene) but without an\n> implementation, or detailed design and analysis. I am very happy to\n> see the idea among other possibilities to be considered again. This\n> time around, we may finally come up with something better than the\n> \"commit dates with SLOP\" thing ;-).\n>\n>> Essentially, the felineY order is selected with the goal of swapping\n>> positions of topologically-independent commits relative to the felinX\n>> ordering. The resulting reachability index is as follows:\n>>\n>> If felineX(A) < felineY(B), then A cannot reach B.\n>> If felineY(A) < felineY(B), then A cannot reach B.\n> I presume that the first line is a typo and you compare the same X index?\n\nYes, sorry for the typos. I fixed them in the report on GitHub.\n\n>\n>> * **Compatible?** In our test implementation, we use a previously unused\n>> byte of data in the commit-graph format to indicate which reachability\n>> index version we are using. Existing clients ignore this value, so we\n>> will want to consider if these new indexes are _backwards compatible_.\n>> That is, will they still report correct values if they ignore this byte\n>> and use the generation number column from the commit-graph file assuming\n>> the values are minimum generation numbers?\n> I personally consider that the current commit-graph with generation\n> numbers experimental, so I am not sure how much we care about this.\n>\n> Having said that.\n>\n> By the above definition, any new index that is wider than the\n> current generation number cannot be compatible (can we even tell the\n> existing clients how wide each elements in the ix array is?)\n>\n> In any case, perhaps the first thing to do is to update the clients\n> so that they stop ignoring the version number field, and instead\n> work without generation number when there is no version of reach.ix\n> available in the file? That way, a better reachablility index can\n> be chosen freely without having to worry about the compatibility.\n\nI can work on that. It should be as simple as setting commit->generation to\nGENERATION_NUMBER_ZERO in fill_commit_in_graph when the graph\nhas a different version.\n\n>\n>> * **Immutable?** Git objects are _immutable_. If you change an object you\n>> actually create a new object with a new object ID. Are the values we\n>> store\n>> for these reachability indexes also immutable?\n> Even if we do not embed the reachability ix in commit objects,\n> having an immutable value is probably a must if we want to make them\n> incrementally computable, so this is a very good property to have.\n> Unless there is a clever idea to incrementally compute a mutable\n> reach.ix, my gut instinct says that this property is a must.\n>\n> Another thing, perhaps related to \"local\" below, is if exactly the\n> same reach.ix is computed by anybody, given an identical commit\n> history graph (perhaps \"reproducibility\"?). I think most of the\n> candidates you listed are reproducible without a fixed tie-breaker,\n> but I am not sure about felineY() thing.\n>\n>> * **Local?** Are these values **locally computable**? That is, do we only\n>> need to look at the parents of a commit (assuming those parents have\n>> computed values) in order to determine the value at that commit?\n> A subset of non-local reachability ix, for example, the ones that\n> need to know what each commit's children are, cannot be immutable,\n> as adding new objects to the graph (either with locally committing,\n> or transferring objects from other repositories) would affect the\n> ix; is this true for all non-local reachability ix, I wonder?\n\nAs a thought experiment, we could define a function size(C) to be the\nnumberof commits reachable from C. This is not locally-computable\nfrom the size values at C's parents due to the inclusion-exclusion\nprinciple. We would need to compute it by walking the reachable set\nand counting (resulting in quadratic performance overall) but is\nimmutable. Since the performance cost is so expensive (unlike the\nlinear costs in the other non-local versions) I didn't include it\nin my comparison.\n\n>\n>> We focused on three types of performance tests that test the indexes\n>> in different ways. Each test lists the `git` command that is used,\n>> and the table lists which repository is used and which inputs.\n>>\n>> ### Test 1: `git log --topo-order -N`\n>>\n>> This test focuses on the number of commits that are parsed during\n>> a `git log --topo-order` before writing `N` commits to output.\n> A devil's advocate comment. Your patches seem to be very focused on\n> this \"unlimited\" case for the past few weeks, but I am not so sure\n> if that is a case worth optimizing for. If \"git log --topo-order -N\n> HEAD~M..\" (for some number M) gives us a similar result as unlimited\n> case but with much less effort, wouldn't it be good enough that lets\n> us concentrate on other use cases instead?\n\nI mostly included these statistics to make sure we didn't add a \nregression in\nthis case. Note that I didn't report the OLD values in this table, \nbecause that\nwould be an unfair comparison.\n\n>> Based on the performance results alone, we should remove minimum\n>> generation numbers, (epoch, date) pairs, and FELINE index from\n>> consideration. There are enough examples of these indexes performing\n>> poorly.\n> OK.\n>\n>> In contrast, maximum generation numbers and corrected commit\n>> dates both performed quite well. They are frequently the top\n>> two performing indexes, and rarely significantly different.\n>>\n>> The trade-off here now seems to be: which _property_ is more important,\n>> locally-computable or backwards-compatible?\n> Nice summary.\n>\n> As I already said, I personally do not think being compatible with\n> currently deployed clients is important at all (primarily because I\n> still consider the whole thing experimental), and there is a clear\n> way forward once we correct the mistake of not having a version\n> number in the file format that tells the updated clients to ignore\n> the generation numbers. For longer term viability, we should pick\n> something that is immutable, reproducible, computable with minimum\n> input---all of which would lead to being incrementally computable, I\n> would think.\n\nThis is good reasoning. The \"reproducible\" property is also important for\nsupport reasons, too! Sounds like the corrected commit date is the best\nway forward.\n\nAside: I spent some time thinking about making the corrected commit dates\nbackward compatible by ensuring the offsets are monotonic in the commit\nhistory (so we could store the offset as commit->generation and the existing\ngeneration comparisons would still work). However, it performs poorly on the\nLinux repository 'git merge-base v4.8 v4.9' example.\n\nThanks,\n-Stolee\n"},{"id":"362101","messageId":"875zxil1if.fsf@evledraar.gmail.com","threadId":"49709","inReplyTo":"xmqqy3ag13us.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC] Generation Number v2","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-10-31T12:54:48Z","receivedAt":"2018-10-31T12:54:55Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, Oct 30 2018, Junio C Hamano wrote:\n\n> Derrick Stolee writes:\n>> In contrast, maximum generation numbers and corrected commit\n>> dates both performed quite well. They are frequently the top\n>> two performing indexes, and rarely significantly different.\n>>\n>> The trade-off here now seems to be: which _property_ is more important,\n>> locally-computable or backwards-compatible?\n>\n> Nice summary.\n>\n> As I already said, I personally do not think being compatible with\n> currently deployed clients is important at all (primarily because I\n> still consider the whole thing experimental), and there is a clear\n> way forward once we correct the mistake of not having a version\n> number in the file format that tells the updated clients to ignore\n> the generation numbers. For longer term viability, we should pick\n> something that is immutable, reproducible, computable with minimum\n> input---all of which would lead to being incrementally computable, I\n> would think.\n\nI think it depends on what we mean by backwards compatibility. None of\nour docs are saying this is experimental right now, just that it's\nopt-in like so many other git-config(1) options.\n\nSo if we mean breaking backwards compatibility in that we'll write a new\nfile or clobber the existing one with a version older clients can't use\nas an optimization, fine.\n\nBut it would be bad to produce a hard error on older clients, but\navoiding that seems as easy as just creating a \"commit-graph2\" file in\n.git/objects/info/.\n"},{"id":"362102","messageId":"6902dbff-d9f6-e897-2c20-d0cb47a50795@gmail.com","threadId":"49709","inReplyTo":"875zxil1if.fsf@evledraar.gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-31T13:04:12Z","receivedAt":"2018-10-31T13:04:15Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/31/2018 8:54 AM, Ævar Arnfjörð Bjarmason wrote:\n> On Tue, Oct 30 2018, Junio C Hamano wrote:\n>\n>> Derrick Stolee writes:\n>>> In contrast, maximum generation numbers and corrected commit\n>>> dates both performed quite well. They are frequently the top\n>>> two performing indexes, and rarely significantly different.\n>>>\n>>> The trade-off here now seems to be: which _property_ is more important,\n>>> locally-computable or backwards-compatible?\n>> Nice summary.\n>>\n>> As I already said, I personally do not think being compatible with\n>> currently deployed clients is important at all (primarily because I\n>> still consider the whole thing experimental), and there is a clear\n>> way forward once we correct the mistake of not having a version\n>> number in the file format that tells the updated clients to ignore\n>> the generation numbers. For longer term viability, we should pick\n>> something that is immutable, reproducible, computable with minimum\n>> input---all of which would lead to being incrementally computable, I\n>> would think.\n> I think it depends on what we mean by backwards compatibility. None of\n> our docs are saying this is experimental right now, just that it's\n> opt-in like so many other git-config(1) options.\n>\n> So if we mean breaking backwards compatibility in that we'll write a new\n> file or clobber the existing one with a version older clients can't use\n> as an optimization, fine.\n>\n> But it would be bad to produce a hard error on older clients, but\n> avoiding that seems as easy as just creating a \"commit-graph2\" file in\n> .git/objects/info/.\n\nWell, we have a 1-byte version number following the \"CGPH\" header in\nthe commit-graph file, and clients will ignore the commit-graph file\nif that number is not \"1\". My hope for backwards-compatibility was\nto avoid incrementing this value and instead use the unused 8th byte.\n\nHowever, it appears that we are destined to increment that version\nnumber, anyway. Here is my list for what needs to be in the next\nversion of the commit-graph file format:\n\n1. A four-byte hash version.\n\n2. File incrementality (split commit-graph).\n\n3. Reachability Index versioning\n\nMost of these changes will happen in the file header. The chunks\nthemselves don't need to change, but some chunks may be added that\nonly make sense in v2 commit-graphs.\n\nThanks,\n-Stolee\n"},{"id":"362170","messageId":"86efc50yq5.fsf@gmail.com","threadId":"49709","inReplyTo":"6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-01T12:27:30Z","receivedAt":"2018-11-01T12:27:46Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"[I have noticed that in some places I wrote A..B instead of B..A. Sorry\n about that]\n\nDerrick Stolee writes:\n\n> We've discussed in several places how to improve upon generation\n> numbers. This RFC is a report based on my investigation into a\n> few new options, and how they compare for Git's purposes on\n> several existing open-source repos.\n>\n> You can find this report and the associated test scripts at\n> https://github.com/derrickstolee/gen-test.\n\nWhich use prototype test implementation from the `reach-perf` branch in\nhttps://github.com/derrickstolee/git.\n\n> I have some more work to do in order to make this fully\n> reproducible (including a single script to clone all of the\n> repos I used, compute the commit-graphs using the different\n> index versions, and run the tests).\n>\n> TL;DR: I recommend we pursue one of the following two options:\n>\n> 1. Maximum Generation Number.\n> 2. Corrected Commit Date.\n>\n> Each of these perform well, but have different implementation\n> drawbacks. I'd like to hear what everyone thinks about those\n> drawbacks.\n\nI agree with Junio that incremental computation is more important than\nbackwards compatibility (that the old clients can work with the new\ncommit-graph without changes). We would have compatibility breaking\nanyway with the planned move from SHA-1 to NewHash aka. SHA-256.\n\n> Please also let me know about any additional tests that I could\n> run. Now that I've got a lot of test scripts built up, I can re-run\n> the test suite pretty quickly.\n\nI would add straighforward 1-to-N and N-to-1 reachability tests in the\nform of `git branch / tag --contains` and `git branch / tag --merged`,\nand perhaps also ahead-behind calculations used by `git status`, and\nN-to-M reachability tests used by tag following code in push and fetch.\n\nPossibly also A...B walk, if it is not implemented via calculating\nmerge-base.\n\nMaybe even --ancestry-path walk, though I am not sure how important best\nperformance for rhis case is (we would want good performance, but\nperhaps best is not needed for rarely used command).\n\nSee explanation below.\n\n\n> Generation Number Performance Test\n> ==================================\n>\n> Git uses the commit history to answer many basic questions, such as\n> computing a merge-base. Some of these algorithms can benefit from a\n> _reachability index_, which is a condition that allows us to answer\n> \"commit A cannot reach commit B\" in some cases. These require pre-\n> computing some values that we can load and use at run-time. Git\n> already has a notion of _generation number_, stores it in the commit-\n> graph file, and uses it in several reachability algorithms.\n\nNote that there are other kinds of reachability indices.\n\nFirst, there are reachability indices that can answer the full\nreachability query (if commit A can reach commit B, or if commit A\ncannot reach commit B) directly, without walking the commit graph at\nall: so called label-only approach. For example one could store for\neach commit the compressed list of all commits reachable from it\n(transitive closure compression).\n\nThose, I think (but I have not checked), would be of not much use for\nGit, as the size of the index grows stronger than linear with the number\nof commits, as grows the time to compute such index. So probably of no\nuse to Git, at least not directly (Git uses so called \"bitmap index\",\nsee e.g. [1], which stores reachability bit-vector as compressed\nbitmap... but not for all commits, only for a small subset).\n\n\nSecond, beside negative-cut reachability indexes, that can answer with\ncertainity that \"commit A cannot reach commit B\", like the generation\nnumbers (also known as level, or topological level), there also\npositive-cut indexes (usually if not always based on the spanning tree\nor trees for the DAG), that can answer when \"commit A can reach commit\nB\".\n\nI think that those can lead to significant speedups for at least some\ntypes of commit traversal and reachability queries that Git needs to\nanswer. But currently no algorithms has a provision for using\npositive-cut filter index. Anyway, such index would be auxiliary thing,\nsee the next point.\n\n\nThird, we require more than having reachability index in the sense of\nhaving some kind of _labelling_, often composite, that can answer either\n\"commit A cannot reach commit B\" or \"commit A can reach commit B\",\ndepending on the type. Git for most operations needs more, namely an\nactual _ordering_, that is a weak order (or to be more exact a total\npreorder, i.e. there can be two different commits with the same\n\"generation number\" or index, but always either idx(A) ≲ idx(B) or\nidx(B) ≲ idx(A)) and not only partial ordering (where there can be\nincomparable elements, i.e neither idx(A) ≼ idx(B) nor idx(B) ≼ idx(A)).\nThis is because it needs to be used in priority queue to decide which\ncommit to travel next; more on that later. This is also why there can\nbe only one such \"main\" reachability _index_.\n\n[1]: https://githubengineering.com/counting-objects/\n\n> You can read more about generation numbers and how to use them in\n> algorithms in [this blog\n> post](https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/).\n>\n> However, [generation numbers do not always improve our\n> algorithms](https://public-inbox.org/git/pull.28.git.gitgitgadget@gmail.com/T/#u).\n> Specifically, some algorithms in Git already use commit date as a\n> heuristic reachability index. This has some problems, though, since\n> commit date can be incorrect for several reasons (clock skew between\n> machines, purposefully setting GIT_COMMIT_DATE to the author date,\n> etc.).\n\nThat's what we use the \"slop\" mechanism for: Git would walk a few\ncommits more than necessary than if there were no clock skew (if commit\ndates were monotonic), and assume that the skew is not to severe to\nfinish early.\n\nBut as we are adding more early termination condition, this introduces\nmore places where things can go wrong for Git to return incorrect\nresults. Thus the need for strict, non-heuristic reachability index.\n\n> However, the speed boost by using commit date as a cutoff was so\n> important in these cases, that the potential for incorrect answers was\n> considered acceptable.\n\nYes, and there were few places where date as cutoff was used; we have\nsince added more place where generation number / reachbility index is\nused as cutoff. Thus more potential for incorrect answers if using\nheuristics.\n\n> When these algorithms were converted to use generation numbers, we\n> _added_ the extra constraint that the algorithms are _never incorrect_.\n\nRight.\n\n> Unfortunately, this led to some cases where performance was worse than\n> before. There are known cases where `git merge-base A B` or\n> `git log --topo-order A..B` are worse when using generation numbers\n> than when using commit dates.\n\nIn Git there are at least four different types of graph traversal\nqueries, with somewhat different requirements, and affected differently\nby various reachability indexes.\n\n\n## Pure reachability queries\n\nFirst there are pure reachability queries, when we are interested only\nin nswering he question whether commit A can reach commit B or not. We\nare nt interested in list of commits between A and B; if reachability\nindex, be it negative-cut or positive-cut, can answer the question, it\nis all we need. If we need to walk (perform online search), then we are\ninterested in just being able to arrive; we need to walk only one path.\n\nThis query can be performed one-to-one, one-to-many (which of commits\nfrom the list can be reached from commit A), many-to-one (which commits\nfrom the list can reach commit B), and many-to-many -- the latest for\nexample with recently added get_reachable_subset().\n\nThese types of queries are done by \"git branch --contains\" (and\n\"--no-contains\") and \"git branch --merged\" (and \"--no-merged\"), the same\nfor \"git tag\"; if I remember it correctly those were among first\noperations that were sped up by commit-graph mechanism. Many-to-many\nqueries are done for tag following in \"git push\" and \"git fetch\".\n\nNote that those queries are missing from gen-test.\n\n\n## Topological ordering\n\nHere reachability index is used to find out in-degree of considered\ncommits (starting from a set of starting points). Here we don't really\nneed to walk all paths, but we need to walk all possible ways of\narriving at given commit.\n\nThough I guess the [new] incremental algorithm could be modified to only\ncheck for in-degree being zero or non-zero. Would it make it slower or\nfaster; I guess in absence of good positive-cut reachability filter it\nwould make it slower.\n\nThis operation is benchmarked both standalone i.e. `git log --topo-order -N`\nand in combination with A..B walk in `git log --topo-order -10 A..B`.\n\n\n## (Po)set difference, or B..A range\n\nIn this type of query, with at least one \"negative\" / \"negated\" commit,\nwe want to find out all commits that are reachable from commit A that\nare not reachable from commit B.\n\nNote that A (commit in positive set) is treated differently with respect\nto traversal from B (commit in negative set). We need to travel (and\npossibly list) all paths from A, while when traveling from B the only\nthing important is reachability, not the actual path or paths. We want\nto travel as few commits as possible when walking from B, and here one\ngeneration numbers are better than the other in the presence of multiple\npaths.\n\nThe situation in nontrivial case could look as follows:\n\n ---.---.---o---*---*---*----*---*-----*---A\n \\\n \\---x-----x-----x-----B\n\nIn such case, the algorithm paints down from positive set i.e. commit A,\nand from negative set i.e. commit B, and walk down from A till we get to\ncommits painted down from B.\n\nWe want to walk those commits somewhat in sync, using priority-queue\nbased variant of breadth-first search (well, kind of), so that we don't\nwalk more commits from A than necessary, only to notice later that these\nare actually reachable from B, and neither we want to walk more commits\nfrom B than necessary, going past the boundary commit.\n\nSidenote: I think that positive-cut auxiliary reachability index\n(reachability filter) can help speed up this operation, making it\npossible to mark commit as reachable from the negative set (from commit\nB) and stop early without actually having to walk from B... though the\nmore in sync walks from A and B would be, the less it would probably\nhelp.\n\nThis is tested using `git log --topo-order -10 A..B`.\n\n\n## Merge base, and A...B walk\n\nIn this case we either find one or all commits that are reachable from\nboth A and B, or (which is related query) find all commits reachable\nfrom A that are not reachable from B and vice versa, that is all commits\nreachable from B that are not reachable from A.\n\nIn this case we walk from both A and B the same way: the operation is\nsymmetric. In the merge base calculations we need to walk only one path\nif there are many equivaent ones; in A...B walk we have to actually walk\nthem. Thus merge base calculation would exhibit, we can concurr, the\nsame behaviour with respect to reachability indexes as A..B case.\n\nThis is tested using `git merge-base A B`; finding all merge bases, and\nA...B walk are not tested yet.\n\nNote that IIRC it was merge-base calculation where the problem of\nperformance regression when using generation number (topological level)\nas an ordering was first encountered. The performance regression happen\nfor situation like this (the graph is taken from original commit fixing\nthe issue, just rephrased).\n\n 0 1 2 3 4 5 6 7 8 9 10 11 4 δgen(c)\n .---M---*---*---*---*---*---*---*---*--*----A B\n |\\ 2 / / δgen(c)\n | \\---------------------------------x-/ /\n \\ 2 3 / δgen(c)\n \\---------------------------------#---------#--/\n\n\n ------------------------------------------------------------>\n time\n\nHere optimal solution would be walk the branch / path with commits\nmarked with 'x' from commit A, while walking the branch / path with\ncommits marked '#' from commit B, and after walking 4 commits notice\nthat the commit M is reachable from both A and B -- thus we have found\n[one of] the merge base.\n\nUsing (minimum) generation numbers we would walk the path marked with\n'*' first, unnecessarily. (IIUC that for a commit we mark also its\nparents, isn't it?).\n\nUsing corrected commit date we would walk at most only a few commits on\nthe *-marked branch.\n\n 0 1 2 3 4 5 6 7 8 9 10 11 11 δmaxgen(c)\n .---M---*---*---*---*---*---*---*---*--*----A B\n |\\ 10 / / δmaxgen(c)\n | \\---------------------------------x-/ /\n \\ 9 10 / δmaxgen(c)\n \\---------------------------------#---------#--/\n\n\n ------------------------------------------------------------>\n time\n\nUsing maximum generation numbers we would also walk at most few *-marked\ncommits.\n\nSidenote: on the figure below you can easily see easy correspondence\nbetween maxgen(c) and revgen(c) indices, see below.\n\n 12 11 10 9 8 7 6 5 4 3 2 1 1 revgen(c)\n .---M---*---*---*---*---*---*---*---*--*----A B\n |\\ 2 / / revgen(c)\n | \\---------------------------------x-/ /\n \\ 3 2 / revgen(c)\n \\---------------------------------#---------#--/\n\n\n## Strict ancestry, or ancestry path\n\nWhen given a range of commits to display (e.g. A..B), only display\ncommits that exist directly on the ancestry chain between B and A,\ni.e. commits that are both descendants of B, and ancestors of A. In\nother words, find all paths from B to A (if they exist).\n\nIn this case we want to walk all the paths, heavily pruning. This\nshould be less dependent on reachability index quality as an index (as\nan ordering), and more on pruning ability of the filter.\n\nThis case is not tested in gen-test, but I wonder how often this feature\nis actualy used (if it would be worth adding it to the benchmark, and if\nso, with what weight behind it).\n\n\n> This report investigates four replacements for generation numbers, and\n> compares the number of walked commits to the existing algorithms (both\n> using generation numbers and not using them at all). We can use this\n> data to make decisions for the future of the feature.\n>\n> ### Implementation\n>\n> The reachability indexes below are implemented in\n> [the `reach-perf` branch in\n> https://github.com/derrickstolee/git](https://github.com/derrickstolee/git/tree/reach-perf).\n> This implementation is in a very rough condition, as it is intended to\n> be a prototype, not production-quality.\n>\n> Using this implementation, you can compute commit-graph files for the\n> specified reachability index using `git commit-graph write --reachable\n> --version=`.\n> The `git` client will read the version from the file, so our tests\n> store each version as `.git/objects/info/commit-graph.` and copy\n> the necessary file to `.git/objects/info/commit-graph` before testing.\n>\n> The algorithms count the number of commits walked, as to avoid the\n> noise that would occur with time-based performance reporting. We use\n> the (in progress) trace2 library for this. To find the values reported,\n> use the `GIT_TR2_PERFORMANCE` environment variable.\n\nWhere we can read more about this trace2 library? Thanks in advance.\n\n>\n> To ignore reachability indexes entirely and use the old algorithms\n> (reported here as \"OLD\" values) use the environment variable\n> `GIT_TEST_OLD_PAINT=1`.\n>\n>\n> Reachability Index Versions\n> ---------------------------\n>\n> **V0: (Minimum) Generation Number.**\n> The _generation number_ of a commit is exactly one more than the maximum\n> generation number of a parent (by convention, the generation number of a\n> commit with no parents is 1). This is the definition currently used by\n> Git (2.19.0 and later). Given two commits A and B, we can then use the\n> following reachability index:\n>\n>     If gen(A) < gen(B), then A cannot reach B.\n>\n> _Commentary:_ One issue with generation numbers is that some algorithms\n> in Git use commit date as a heuristic, and allow incorrect answers if\n> there is enough clock skew. Using that heuristic, the algorithms can walk\n> fewer commits than the algorithms using generation number. The other\n> reachability indexes introduced below attempt to fix this problem.\n\nThis is the existing solution.\n\n> **V1: (Epoch, Date) Pairs.**\n> For each commit, store a pair of values called the _epoch_ and the _date_.\n> The date is the normal commit date. The _epoch_ of a commit is the minimum\n> X such that X is at least the maximum epoch of each parent, and at least\n> one more than the epoch of any parent whose date is larger than the date\n> of this commit (i.e. there is clock skew between this commit and this\n> parent). In this way, we can use the following reachability index:\n>\n>    If epoch(A) < epoch(B), then A cannot reach B.\n>    If epoch(A) == epoch(B) and date(A) < date(B), then A cannot reach B.\n\nI wonder what makes it perform worse than corrected date aka V3.\n\n> **V2: Maximum Generation Numbers.**\n> The _maximum generation number_ of a commit (denoted by maxgen(A)) is\n> defined using its _children_ and the total number of commits in the repo.\n> If A is a commit with no children (that is, there is no commit B with\n> A as a parent) then maxgen(A) is equal to the number of commits in the repo.\n> For all other commits A, maxgen(A) is one less than the minimum maxgen(B)\n> among children B. This can be computed by initializing maxgen(C) to the\n> number of commits, then walking the commit graph in topological order,\n> assigning maxgen(P) = min { maxgen(P), maxgen(C) - 1 } for each parent P\n> of the currently-walking commit C. We then have the same reachability\n> index as minimum generation number:\n>\n>   If maxgen(A) < maxgen(B), then A cannot reach B.\n\nIf I understand it correctly, this is the same as reverse generation\nnumbers, or reverse topological levels; in other words genertion numbers\non reversed graph -- only transformed:\n\n maxgen(A) == number_of_commits - (revgen(A) - 1)\n\nWe define revgen(A) in the following way:\n- for head tips (for source nodes), i.e. commits with in-degree of 0,\n with no children, have revgen(A) = 1 (revgen(A) = 0 is left for\n commits outside commit-graph, which translates to INFINITY for\n maxgen(A)).\n- otherwise, it is 1 more than maximum revgen(C) of its children\n\nThey are equivalent, but maxgen(A) is \"backward compatibile\", that is\nthe rechability condition is exactly the same as for ordinary generation\nnumbers:\n\n    If gen(A) < gen(B), then A cannot reach B.\n    If maxgen(A) < maxgen(B), then A cannot reach B.\n\nBut\n\n    If revgen(A) > revgen(B), then A cannot reach B.\n\n>\n> _Commentary:_ The known examples where (minimum) generation numbers perform\n> worse than commit date heuristics involve commits with recent commit dates\n> but whose parents have very low generation number compared to most recent\n> commits. In a way, minimum generation numbers increase the odds that we\n> can say \"A cannot reach B\" when A is fixed and B is selected at random.\n> Maximum generation numbers increase the odds that we can say \"A cannot\n> reach B\" when B is fixed and A is selected at random. This helps us when\n> we are exploring during a reachability algorithm and have explored few\n> commits and want to say that the large set of unexplored commits cannot\n> reach any of the explored commits.\n\nI guess that the situation where shortcut path have recent date, while\nhaving less commits in path (and thus lover ordinary generation number)\nis more common in real commit graphs because one might want to base a\ncommit (for example a bugfix) on an old commit, but commits usually get\nmerged quickly, and not left for long time. If they re left for long\ntime, they usually needs correction (via rebase) before being merged,\nand again we have commit with date close to the date of merge, leading\nto a shortcut.\n\nDoes this reasoning looks correct to you?\n\n> **V3: Corrected Commit Date.**\n> For a commit C, let its _corrected commit date_ (denoted by cdate(C))\n> be the maximum of the commit date of C and the [corrected] commit dates of its\n> parents.\n\nWouldn't it be better to use the maximum of the commit date of C, and\none second more than the corrected commit dates of its parents? This\nway corrected dates would be strictly monotonic along the chain.\n\nSidenote: in theory, sufficiently bad clock skew (like e.g. wrong year\nin the future) could screw large swatches of the commit graph. In\npractice, in real-life repositories, this doesn't happen, I guess.\n\n>   If cdate(A) < cdate(B), then A cannot reach B.\n>\n> **V4: FELINE Index.**\n> The FELINE index is a two-dimentional reachability index as defined in\n> [Reachability Queries in Very Large Graphs: A Fast Refined Online\n> Search Approach](https://openproceedings.org/EDBT/2014/paper_166.pdf)\n> by Veloso, Cerf, Jeira, and Zaki. The index is not deterministically\n> defined, but instead is defined in the following way:\n>\n> 1. Compute a reverse topological order of the commits. Let felineX(C)\n>    be the position in which C appears in this list. Since this is\n>    a reverse topological order, felineX(C) > felineX(P) for each parent\n>    P of C.\n\nWell, it depends on the definition of the topological order if it is\ntolopogical order or reverse topological order. Anyway, the FELINE\npaper includes discussion about FELINE-I, i.e. inversed feline index.\nFrom FELINE and FELINE-I, one of those is what was used here.\n\n> 2. Compute a reverse topological order of the commits using Kahn's\n>    algorithm, but when selecting among a list of commits with in-degree\n>    zero, prioritize the commit by minimizing felineX. Let felineY(C)\n>    be the position in which C appears in this list.\n\nNote that the second step, as given in the paper, is actually\ndeterministic (assuming that we follow the recommendations; well, up to\na point). It needs some topological order for felineX, though.\n\n> Essentially, the felineY order is selected with the goal of swapping\n> positions of topologically-independent commits relative to the felinX\n> ordering. The resulting reachability index is as follows:\n>\n>    If felineX(A) < felineX(B), then A cannot reach B.\n>    If felineY(A) < felineY(B), then A cannot reach B.\n>\n> _Commentary:_ In terms of comparing two commits directly, this index\n> is quite strong. However, when we are performing our reachability\n> algorithms that care about reachable sets (git log --graph), or\n> boundaries between reachable sets (git merge-base, git log --graph A..B)\n> we need to track a single pair (minX,minY) for comparion. In order to not\n> miss anything during our search, we need to update this pair to be\n> the minimum felineX(A) and minimum felineY(B) among all explored commits\n> A and B. That is, the pair (minX, minY) is below our entire explored set.\n> This can be a disadvantage for these algorithms.\n\nActually the problem is that FELINE index is partial order, not an\nordering; not something that we can use in a priority queue.\n\nBut the single [reverse] topological ordering is a reachability index in\nitself, and it is an ordering. Thus we can use felineX as an index in\npriority queue (or we can use felineY).\n\nOne thing to notice is that FELINE index performs well on real world\nlarge graphs which have quite different structure from commit graphs;\namong others they have either very large number of sources (head tips)\nor sinks (root nodes), or both; those numbers grow with the number of\nnodes. For commit graphs they don't perform as well; well, at least\nccording to my explorations on that matter in the Google Colaboratory\nnotebook [2].\n\n[2]: https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n\n>\n> ### Comparing Reachability Index Versions Viability\n>\n> Before considering how well these indexes perform during our algorithm\n> runs, let's take a moment to consider the implementation details and\n> how they relate to the existing commit-graph file format and existing\n> Git clients.\n>\n> * **Compatible?** In our test implementation, we use a previously unused\n>   byte of data in the commit-graph format to indicate which reachability\n>   index version we are using. Existing clients ignore this value, so we\n>   will want to consider if these new indexes are _backwards compatible_.\n>   That is, will they still report correct values if they ignore this byte\n>   and use the generation number column from the commit-graph file assuming\n>   the values are minimum generation numbers?\n\nIn other words \"backward compatibility\" for a reachability index means\nthat the reachability condition is exactly the same as it was:\n\n    If index(A) < index(B), then A cannot reach B.\n\nand also values of the reachability index are written in place of\ngeneration numbers in the commit-graph.\n\n>\n> * **Immutable?** Git objects are _immutable_. If you change an object you\n>   actually create a new object with a new object ID. Are the values we\n>   store for these reachability indexes also immutable?\n>\n> * **Local?** Are these values **locally computable**? That is, do we only\n>   need to look at the parents of a commit (assuming those parents have\n>   computed values) in order to determine the value at that commit?\n\nThose two features imply that the number of commits that we need to walk\nto be able to update reachability index after appending new commits is\nO(new commits), which means O(changes). I would allow for simple\ntransformations of other values, e.g. adding a constant; we need to\nrewrite commit-graph file anyway.\n\nI wonder if there are reachability indexes that are either immutable but\nnot local, or not immutable but local. Doesn't being local imply\nimmutability, with some common-sense assumptions (like no random choice\nfor parent-less commits)?\n\n> | Index                     | Compatible? | Immutable? | Local? |\n> |---------------------------|-------------|------------|--------|\n> | Minimum Generation Number | Yes         | Yes        | Yes    |\n> | (Epoch, Date) pairs       | Yes         | Yes        | Yes    |\n> | Maximum Generation Number | Yes         | No         | No     |\n> | Corrected Commit Date     | No          | Yes        | Yes    |\n> | FELINE index              | Yes         | No         | No     |\n>\n> _Note:_ The corrected commit date uses the generation number column\n> to store an offset of \"how much do I need to add to my commit date\n> to get my corrected commit date?\" The values stored in that column\n> are then not backwards-compatible.\n\nAdditional note: this offset / delta based approach to storing corrected\ncommit data is a form of lightweight compression, allowing it to fit\nsafely in 30 bits (while the commit date uses 32+2 = 34 bits itself).\n\nAssuming that we want to keep this feature from the original\ncommit-graph file format, that is.\n\n> _Note:_ The FELINE index requires storing two values instead of just\n> one. One of these values could be stored in the generation number\n> column and the other in an optional chunk, hence it could be backwards\n> compatible. (This is not how it is implemented in our example\n> implementation.)\n\nSo the table above refers to this hypothetical implementation when\nstating that FELINE is backwards compatibile, but current test\nimplementation is not, isn't it?\n\n>\n> Data\n> ----\n>\n> We focused on three types of performance tests that test the indexes\n> in different ways. Each test lists the `git` command that is used,\n> and the table lists which repository is used and which inputs.\n>\n> ### Test 1: `git log --topo-order -N`\n>\n> This test focuses on the number of commits that are parsed during\n> a `git log --topo-order` before writing `N` commits to output.\n>\n> You can reproduce this test using `topo-order-tests.sh` and\n> see all the data in `topo-order-summary.txt`. The values reported\n> here are a sampling of the data, ignoring tests where all values\n> were the same or extremely close in value.\n>\n>\n> | Repo         | N     | V0     | V1     | V2     | V3     | V4    |\n> |--------------|-------|--------|--------|--------|--------|-------|\n> | android-base | 100   |  5,487 |  8,534 |  6,937 |  6,419 | 6,453 |\n> | android-base | 1000  | 36,029 | 44,030 | 41,493 | 41,206 |45,431 |\n> | chromium     | 100   |    101 |424,406 |    101 |    101 |   101 |\n> | gerrit       | 100   |  8,212 |  8,533 |    164 |    159 |   162 |\n> | gerrit       | 1000  |  8,512 |  8,533 |  1,990 |  1,973 | 3,766 |\n> | Linux        | 100   | 12,458 | 12,444 | 13,683 | 13,123 |13,124 |\n> | Linux        | 1000  | 24,436 | 26,247 | 27,878 | 26,430 |27,875 |\n> | Linux        | 10000 | 30,364 | 28,891 | 27,878 | 26,430 |27,875 |\n> | electron     | 1000  | 19,927 | 18,733 |  1,072 | 18,214 |18,214 |\n> | Ffmpeg       | 10000 | 32,154 | 47,429 | 10,435 | 11,054 |11,054 |\n> | jgit         | 1000  |  1,550 |  6,264 |  1,067 |  1,060 | 1,233 |\n> | julia        | 10000 | 43,043 | 43,043 | 10,201 | 23,505 |23,828 |\n> | odoo         | 1000  | 17,175 |  9,714 |  4,043 |  4,046 | 4,111 |\n> | php-src      | 1000  | 19,014 | 27,530 |  1,311 |  1,305 | 1,320 |\n> | rails        | 100   |  1,420 |  2,041 |  1,757 |  1,428 | 1,441 |\n> | rails        | 1000  |  7,952 | 10,145 | 10,053 |  8,373 | 8,373 |\n> | swift        | 1000  |  1,914 |  4,004 |  2,071 |  1,939 | 1,940 |\n> | tensorflow   | 1000  | 10,019 | 39,221 |  6,711 | 10,051 |10,051 |\n> | TypeScript   | 1000  |  2,873 | 12,014 |  3,049 |  2,876 | 2,876 |\n\nDo I understand it correctly that the range of N for a given project is\nlimited by the depth of the project history (hence maximum N of 10000\nfor Linux kernel, but only 100 for chromium)?\n\nI wonder what the OLD numbers are for these operations.\n\n>\n> ### Test 2: `git log --topo-order -10 A..B`\n>\n> This test focuses on the number of commits that are parsed during\n> a `git log --topo-order A..B` before writing ten commits to output.\n> Since we fix a very small set of output commits, we care more about\n> the part of the walk that determines which commits are reachable\n> from `B` but not reachable from `A`. This part of the walk uses\n> commit date as a heuristic in the existing implementation.\n[...]\n\n> ### Test 3: `git merge-base A B`\n>\n> This test focuses on the number of commits that are parsed during\n> a `git merge-base A B`. This part of the walk uses commit date as\n> a heuristic in the existing implementation.\n[...]\n\n> Conclusions\n> -----------\n>\n> Based on the performance results alone, we should remove minimum\n> generation numbers, (epoch, date) pairs, and FELINE index from\n> consideration. There are enough examples of these indexes performing\n> poorly.\n>\n> In contrast, maximum generation numbers and corrected commit\n> dates both performed quite well. They are frequently the top\n> two performing indexes, and rarely significantly different.\n>\n> The trade-off here now seems to be: which _property_ is more important,\n> locally-computable or backwards-compatible?\n>\n> * Maximum generation number is backwards-compatible but not\n>   locally-computable or immutable.\n>\n> * Corrected commit-date is locally-computable and immutable,\n>   but not backwards-compatible.\n>\n> _Editor's Note:_ Every time I think about this trade-off, I can't\n> come to a hard conclusion about which is better. Instead, I'll\n> leave that up for discussion.\n\nIn my opinion being able to update commit-graph data fast is more\nimportant than being backward-compatibile, i.e. beig able to use\ncommit-data file generated by new clients (and servers) by old clients.\n\n\nThank you for all your work,\n--\nJakub Narębski\n"},{"id":"362177","messageId":"0c6b42e4-e825-ff70-a528-e118abf4c435@gmail.com","threadId":"49709","inReplyTo":"86efc50yq5.fsf@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-11-01T13:29:38Z","receivedAt":"2018-11-01T13:29:43Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 11/1/2018 8:27 AM, Jakub Narebski wrote:\n> [I have noticed that in some places I wrote A..B instead of B..A. Sorry\n> about that]\n>\n> Derrick Stolee writes:\n>\n>> Please also let me know about any additional tests that I could\n>> run. Now that I've got a lot of test scripts built up, I can re-run\n>> the test suite pretty quickly.\n> I would add straighforward 1-to-N and N-to-1 reachability tests in the\n> form of `git branch / tag --contains` and `git branch / tag --merged`,\n> and perhaps also ahead-behind calculations used by `git status`, and\n> N-to-M reachability tests used by tag following code in push and fetch.\n>\n> Possibly also A...B walk, if it is not implemented via calculating\n> merge-base.\n\nI believe this uses paint_down_to_common(), but looks at the PARENT1 and\nPARENT2 flags afterward to determine the left/right/both relationships.\n\n> Maybe even --ancestry-path walk, though I am not sure how important best\n> performance for rhis case is (we would want good performance, but\n> perhaps best is not needed for rarely used command).\n\nCurrently, the implementation of --ancestry-path does not use a\nreachability index.\n\n>\n> See explanation below.\n>\n>\n>> Generation Number Performance Test\n>> ==================================\n>>\n>> Git uses the commit history to answer many basic questions, such as\n>> computing a merge-base. Some of these algorithms can benefit from a\n>> _reachability index_, which is a condition that allows us to answer\n>> \"commit A cannot reach commit B\" in some cases. These require pre-\n>> computing some values that we can load and use at run-time. Git\n>> already has a notion of _generation number_, stores it in the commit-\n>> graph file, and uses it in several reachability algorithms.\n> Note that there are other kinds of reachability indices.\n>\n> First, there are reachability indices that can answer the full\n> reachability query (if commit A can reach commit B, or if commit A\n> cannot reach commit B) directly, without walking the commit graph at\n> all: so called label-only approach. For example one could store for\n> each commit the compressed list of all commits reachable from it\n> (transitive closure compression).\n>\n> Those, I think (but I have not checked), would be of not much use for\n> Git, as the size of the index grows stronger than linear with the number\n> of commits, as grows the time to compute such index. So probably of no\n> use to Git, at least not directly (Git uses so called \"bitmap index\",\n> see e.g. [1], which stores reachability bit-vector as compressed\n> bitmap... but not for all commits, only for a small subset).\n>\n>\n> Second, beside negative-cut reachability indexes, that can answer with\n> certainity that \"commit A cannot reach commit B\", like the generation\n> numbers (also known as level, or topological level), there also\n> positive-cut indexes (usually if not always based on the spanning tree\n> or trees for the DAG), that can answer when \"commit A can reach commit\n> B\".\n>\n> I think that those can lead to significant speedups for at least some\n> types of commit traversal and reachability queries that Git needs to\n> answer. But currently no algorithms has a provision for using\n> positive-cut filter index. Anyway, such index would be auxiliary thing,\n> see the next point.\n>\n>\n> Third, we require more than having reachability index in the sense of\n> having some kind of _labelling_, often composite, that can answer either\n> \"commit A cannot reach commit B\" or \"commit A can reach commit B\",\n> depending on the type. Git for most operations needs more, namely an\n> actual _ordering_, that is a weak order (or to be more exact a total\n> preorder, i.e. there can be two different commits with the same\n> \"generation number\" or index, but always either idx(A) ≲ idx(B) or\n> idx(B) ≲ idx(A)) and not only partial ordering (where there can be\n> incomparable elements, i.e neither idx(A) ≼ idx(B) nor idx(B) ≼ idx(A)).\n> This is because it needs to be used in priority queue to decide which\n> commit to travel next; more on that later. This is also why there can\n> be only one such \"main\" reachability _index_.\n>\n> [1]: https://githubengineering.com/counting-objects/\n\nThanks for the details. At the moment, I'm only interested in improving our\nnegative-cut reachability index, as we have algorithms that can take \nadvantage\nof them (and can compare their performance directly).\n\n>\n>> You can read more about generation numbers and how to use them in\n>> algorithms in [this blog\n>> post](https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/).\n>>\n>> However, [generation numbers do not always improve our\n>> algorithms](https://public-inbox.org/git/pull.28.git.gitgitgadget@gmail.com/T/#u).\n>> Specifically, some algorithms in Git already use commit date as a\n>> heuristic reachability index. This has some problems, though, since\n>> commit date can be incorrect for several reasons (clock skew between\n>> machines, purposefully setting GIT_COMMIT_DATE to the author date,\n>> etc.).\n> That's what we use the \"slop\" mechanism for: Git would walk a few\n> commits more than necessary than if there were no clock skew (if commit\n> dates were monotonic), and assume that the skew is not to severe to\n> finish early.\n>\n> But as we are adding more early termination condition, this introduces\n> more places where things can go wrong for Git to return incorrect\n> results. Thus the need for strict, non-heuristic reachability index.\n>\n>> However, the speed boost by using commit date as a cutoff was so\n>> important in these cases, that the potential for incorrect answers was\n>> considered acceptable.\n> Yes, and there were few places where date as cutoff was used; we have\n> since added more place where generation number / reachbility index is\n> used as cutoff. Thus more potential for incorrect answers if using\n> heuristics.\n>\n>> When these algorithms were converted to use generation numbers, we\n>> _added_ the extra constraint that the algorithms are _never incorrect_.\n> Right.\n>\n>> Unfortunately, this led to some cases where performance was worse than\n>> before. There are known cases where `git merge-base A B` or\n>> `git log --topo-order A..B` are worse when using generation numbers\n>> than when using commit dates.\n> In Git there are at least four different types of graph traversal\n> queries, with somewhat different requirements, and affected differently\n> by various reachability indexes.\n>\n>\n> ## Pure reachability queries\n>\n> First there are pure reachability queries, when we are interested only\n> in nswering he question whether commit A can reach commit B or not. We\n> are nt interested in list of commits between A and B; if reachability\n> index, be it negative-cut or positive-cut, can answer the question, it\n> is all we need. If we need to walk (perform online search), then we are\n> interested in just being able to arrive; we need to walk only one path.\n>\n> This query can be performed one-to-one, one-to-many (which of commits\n> from the list can be reached from commit A), many-to-one (which commits\n> from the list can reach commit B), and many-to-many -- the latest for\n> example with recently added get_reachable_subset().\n>\n> These types of queries are done by \"git branch --contains\" (and\n> \"--no-contains\") and \"git branch --merged\" (and \"--no-merged\"), the same\n> for \"git tag\"; if I remember it correctly those were among first\n> operations that were sped up by commit-graph mechanism. Many-to-many\n> queries are done for tag following in \"git push\" and \"git fetch\".\n>\n> Note that those queries are missing from gen-test.\n\nThese are definitely a good idea to pursue further testing. The only\nthing I canthink of right now is that the tests can be hard to set up,\nbut perhaps`git branch --remote --contains` or `git tag --contains`\nwould be interesting.\n\n> ## Topological ordering\n>\n> Here reachability index is used to find out in-degree of considered\n> commits (starting from a set of starting points). Here we don't really\n> need to walk all paths, but we need to walk all possible ways of\n> arriving at given commit.\n\nYou make a good point here about the difference between \"all paths to C\"\nand\"all children of C\", since the number of paths can grow exponentially\n(and frequentlydoes in Git) but the number of children is linear (and\nsmall in practice).\n\n> Though I guess the [new] incremental algorithm could be modified to only\n> check for in-degree being zero or non-zero. Would it make it slower or\n> faster; I guess in absence of good positive-cut reachability filter it\n> would make it slower.\n\nI don't understand how a positive-cut filter helps in this case. The point\nof the in-degreecalculation is to say \"we already output all commits that\ncan reach this commit\" beforewe output another commit. How could a\npositive-cut filter help here?\n\n> This operation is benchmarked both standalone i.e. `git log --topo-order -N`\n> and in combination with A..B walk in `git log --topo-order -10 A..B`.\n>\n>\n> ## (Po)set difference, or B..A range\n>\n> In this type of query, with at least one \"negative\" / \"negated\" commit,\n> we want to find out all commits that are reachable from commit A that\n> are not reachable from commit B.\n>\n> Note that A (commit in positive set) is treated differently with respect\n> to traversal from B (commit in negative set). We need to travel (and\n> possibly list) all paths from A, while when traveling from B the only\n> thing important is reachability, not the actual path or paths. We want\n> to travel as few commits as possible when walking from B, and here one\n> generation numbers are better than the other in the presence of multiple\n> paths.\n>\n> The situation in nontrivial case could look as follows:\n>\n> ---.---.---o---*---*---*----*---*-----*---A\n> \\\n> \\---x-----x-----x-----B\n>\n> In such case, the algorithm paints down from positive set i.e. commit A,\n> and from negative set i.e. commit B, and walk down from A till we get to\n> commits painted down from B.\n>\n> We want to walk those commits somewhat in sync, using priority-queue\n> based variant of breadth-first search (well, kind of), so that we don't\n> walk more commits from A than necessary, only to notice later that these\n> are actually reachable from B, and neither we want to walk more commits\n> from B than necessary, going past the boundary commit.\n>\n> Sidenote: I think that positive-cut auxiliary reachability index\n> (reachability filter) can help speed up this operation, making it\n> possible to mark commit as reachable from the negative set (from commit\n> B) and stop early without actually having to walk from B... though the\n> more in sync walks from A and B would be, the less it would probably\n> help.\n>\n> This is tested using `git log --topo-order -10 A..B`.\n>\n>\n> ## Merge base, and A...B walk\n>\n> In this case we either find one or all commits that are reachable from\n> both A and B, or (which is related query) find all commits reachable\n> from A that are not reachable from B and vice versa, that is all commits\n> reachable from B that are not reachable from A.\n>\n> In this case we walk from both A and B the same way: the operation is\n> symmetric. In the merge base calculations we need to walk only one path\n> if there are many equivaent ones; in A...B walk we have to actually walk\n> them. Thus merge base calculation would exhibit, we can concurr, the\n> same behaviour with respect to reachability indexes as A..B case.\n>\n> This is tested using `git merge-base A B`; finding all merge bases, and\n> A...B walk are not tested yet.\n>\n> Note that IIRC it was merge-base calculation where the problem of\n> performance regression when using generation number (topological level)\n> as an ordering was first encountered. The performance regression happen\n> for situation like this (the graph is taken from original commit fixing\n> the issue, just rephrased).\n>\n> 0 1 2 3 4 5 6 7 8 9 10 11 4 δgen(c)\n> .---M---*---*---*---*---*---*---*---*--*----A B\n> |\\ 2 / / δgen(c)\n> | \\---------------------------------x-/ /\n> \\ 2 3 / δgen(c)\n> \\---------------------------------#---------#--/\n>\n>\n> ------------------------------------------------------------>\n> time\n>\n> Here optimal solution would be walk the branch / path with commits\n> marked with 'x' from commit A, while walking the branch / path with\n> commits marked '#' from commit B, and after walking 4 commits notice\n> that the commit M is reachable from both A and B -- thus we have found\n> [one of] the merge base.\n>\n> Using (minimum) generation numbers we would walk the path marked with\n> '*' first, unnecessarily. (IIUC that for a commit we mark also its\n> parents, isn't it?).\n>\n> Using corrected commit date we would walk at most only a few commits on\n> the *-marked branch.\n>\n> 0 1 2 3 4 5 6 7 8 9 10 11 11 δmaxgen(c)\n> .---M---*---*---*---*---*---*---*---*--*----A B\n> |\\ 10 / / δmaxgen(c)\n> | \\---------------------------------x-/ /\n> \\ 9 10 / δmaxgen(c)\n> \\---------------------------------#---------#--/\n>\n>\n> ------------------------------------------------------------>\n> time\n>\n> Using maximum generation numbers we would also walk at most few *-marked\n> commits.\n>\n> Sidenote: on the figure below you can easily see easy correspondence\n> between maxgen(c) and revgen(c) indices, see below.\n>\n> 12 11 10 9 8 7 6 5 4 3 2 1 1 revgen(c)\n> .---M---*---*---*---*---*---*---*---*--*----A B\n> |\\ 2 / / revgen(c)\n> | \\---------------------------------x-/ /\n> \\ 3 2 / revgen(c)\n> \\---------------------------------#---------#--/\n>\n>\n> ## Strict ancestry, or ancestry path\n>\n> When given a range of commits to display (e.g. A..B), only display\n> commits that exist directly on the ancestry chain between B and A,\n> i.e. commits that are both descendants of B, and ancestors of A. In\n> other words, find all paths from B to A (if they exist).\n>\n> In this case we want to walk all the paths, heavily pruning. This\n> should be less dependent on reachability index quality as an index (as\n> an ordering), and more on pruning ability of the filter.\n>\n> This case is not tested in gen-test, but I wonder how often this feature\n> is actualy used (if it would be worth adding it to the benchmark, and if\n> so, with what weight behind it).\n\nAs mentioned earlier, the --ancestry-path algorithm does not currently use a\nnegative-cut filter, so we would not gather any data on this at the moment.\n\nHowever, I imagine the algorithm is similar to the typical A..B case, as we\nneedto discover the (po)set difference, construct the reversed digraph on\nthosecommits, and walk backwards from A. Assuming the difference is much\nsmallerthan the entire commit graph, then the main cost is the walk that\ndiscovers thedifference, and hence is covered somewhat by the `git log\n--topo-order A..B` tests.\n\n>> This report investigates four replacements for generation numbers, and\n>> compares the number of walked commits to the existing algorithms (both\n>> using generation numbers and not using them at all). We can use this\n>> data to make decisions for the future of the feature.\n>>\n>> ### Implementation\n>>\n>> The reachability indexes below are implemented in\n>> [the `reach-perf` branch in\n>> https://github.com/derrickstolee/git](https://github.com/derrickstolee/git/tree/reach-perf).\n>> This implementation is in a very rough condition, as it is intended to\n>> be a prototype, not production-quality.\n>>\n>> Using this implementation, you can compute commit-graph files for the\n>> specified reachability index using `git commit-graph write --reachable\n>> --version=`.\n>> The `git` client will read the version from the file, so our tests\n>> store each version as `.git/objects/info/commit-graph.` and copy\n>> the necessary file to `.git/objects/info/commit-graph` before testing.\n>>\n>> The algorithms count the number of commits walked, as to avoid the\n>> noise that would occur with time-based performance reporting. We use\n>> the (in progress) trace2 library for this. To find the values reported,\n>> use the `GIT_TR2_PERFORMANCE` environment variable.\n> Where we can read more about this trace2 library? Thanks in advance.\n\nhttps://public-inbox.org/git/pull.29.git.gitgitgadget@gmail.com/\n[PATCH 0/8] WIP: trace2: a new trace facility\n\n>> To ignore reachability indexes entirely and use the old algorithms\n>> (reported here as \"OLD\" values) use the environment variable\n>> `GIT_TEST_OLD_PAINT=1`.\n>>\n>>\n>> Reachability Index Versions\n>> ---------------------------\n>>\n>> **V0: (Minimum) Generation Number.**\n>> The _generation number_ of a commit is exactly one more than the maximum\n>> generation number of a parent (by convention, the generation number of a\n>> commit with no parents is 1). This is the definition currently used by\n>> Git (2.19.0 and later). Given two commits A and B, we can then use the\n>> following reachability index:\n>>\n>>     If gen(A) < gen(B), then A cannot reach B.\n>>\n>> _Commentary:_ One issue with generation numbers is that some algorithms\n>> in Git use commit date as a heuristic, and allow incorrect answers if\n>> there is enough clock skew. Using that heuristic, the algorithms can walk\n>> fewer commits than the algorithms using generation number. The other\n>> reachability indexes introduced below attempt to fix this problem.\n> This is the existing solution.\n>\n>> **V1: (Epoch, Date) Pairs.**\n>> For each commit, store a pair of values called the _epoch_ and the _date_.\n>> The date is the normal commit date. The _epoch_ of a commit is the minimum\n>> X such that X is at least the maximum epoch of each parent, and at least\n>> one more than the epoch of any parent whose date is larger than the date\n>> of this commit (i.e. there is clock skew between this commit and this\n>> parent). In this way, we can use the following reachability index:\n>>\n>>    If epoch(A) < epoch(B), then A cannot reach B.\n>>    If epoch(A) == epoch(B) and date(A) < date(B), then A cannot reach B.\n> I wonder what makes it perform worse than corrected date aka V3.\n\nIn the example `git merge-base v4.8 v4.9` in the Linux repo, the topology\nincludestwo commits (say, C1 and C2) of low generation number but high\ncommit-date. Thesecommits also have low epoch. However, there are 607\ncommits in the repo whosecommit date is smaller than a parent's commit\ndate. This means that the epoch in themain trunk of the repo can be as\nhigh as 607, while the epoch for C1 and C2 is likely in the single digits.\nThis means that we need to walk all commits with epoch greaterthan\nmin { epoch(C1), epoch(C2) } before we explore C1 and C2 and terminate\nthe walk.\n\nIn V3, the commits C1 and C2 have high corrected commit date, higher than\nany of thecommits that require positive offset to overcome the clock skew\nwith their parents. Thisallows the walk to be very similar to the old\nalgorithm, as seen in this `git merge-base A B`test summary:\n\nLinux c8d2bc9bc39e 69973b830859\n   OLD: 167468\n    V0: 635579\n    V1: 630138\n    V2:  33716\n    V3: 167496\n    V4: 153774\n\n>\n>> **V2: Maximum Generation Numbers.**\n>> The _maximum generation number_ of a commit (denoted by maxgen(A)) is\n>> defined using its _children_ and the total number of commits in the repo.\n>> If A is a commit with no children (that is, there is no commit B with\n>> A as a parent) then maxgen(A) is equal to the number of commits in the repo.\n>> For all other commits A, maxgen(A) is one less than the minimum maxgen(B)\n>> among children B. This can be computed by initializing maxgen(C) to the\n>> number of commits, then walking the commit graph in topological order,\n>> assigning maxgen(P) = min { maxgen(P), maxgen(C) - 1 } for each parent P\n>> of the currently-walking commit C. We then have the same reachability\n>> index as minimum generation number:\n>>\n>>   If maxgen(A) < maxgen(B), then A cannot reach B.\n> If I understand it correctly, this is the same as reverse generation\n> numbers, or reverse topological levels; in other words genertion numbers\n> on reversed graph -- only transformed:\n>\n> maxgen(A) == number_of_commits - (revgen(A) - 1)\n>\n> We define revgen(A) in the following way:\n> - for head tips (for source nodes), i.e. commits with in-degree of 0,\n> with no children, have revgen(A) = 1 (revgen(A) = 0 is left for\n> commits outside commit-graph, which translates to INFINITY for\n> maxgen(A)).\n> - otherwise, it is 1 more than maximum revgen(C) of its children\n>\n> They are equivalent, but maxgen(A) is \"backward compatibile\", that is\n> the rechability condition is exactly the same as for ordinary generation\n> numbers:\n>\n>     If gen(A) < gen(B), then A cannot reach B.\n>     If maxgen(A) < maxgen(B), then A cannot reach B.\n>\n> But\n>\n>     If revgen(A) > revgen(B), then A cannot reach B.\n\nYes, these are the same idea, and the reason to phrase it as I did is to\nkeep theinequality in the same direction.\n\n>\n>> _Commentary:_ The known examples where (minimum) generation numbers perform\n>> worse than commit date heuristics involve commits with recent commit dates\n>> but whose parents have very low generation number compared to most recent\n>> commits. In a way, minimum generation numbers increase the odds that we\n>> can say \"A cannot reach B\" when A is fixed and B is selected at random.\n>> Maximum generation numbers increase the odds that we can say \"A cannot\n>> reach B\" when B is fixed and A is selected at random. This helps us when\n>> we are exploring during a reachability algorithm and have explored few\n>> commits and want to say that the large set of unexplored commits cannot\n>> reach any of the explored commits.\n> I guess that the situation where shortcut path have recent date, while\n> having less commits in path (and thus lover ordinary generation number)\n> is more common in real commit graphs because one might want to base a\n> commit (for example a bugfix) on an old commit, but commits usually get\n> merged quickly, and not left for long time. If they re left for long\n> time, they usually needs correction (via rebase) before being merged,\n> and again we have commit with date close to the date of merge, leading\n> to a shortcut.\n>\n> Does this reasoning looks correct to you?\n\nThese \"bug fixes based on old commits\" cases are few and far between, so\nare notenough to explain how often maximum generation number works well.\nInstead, Iwould say that it works well because the typical Git pattern is\nto merge into a singletrunk. In the case of projects like Linux, there are\nmultiple \"trunks\" that are run bylieutenants and are merged into a \"super\ntrunk\"; even in these cases, the numberof trunks is much smaller than the\nnumber of topics. Let's focus on a single-trunkmodel for the discussion \nbelow.\n\nWhen working with a single trunk, most merge commits are in the first-parent\nhistoryof that trunk. As we travel down those trunks, the maximum generation\nis decreasing.This means that the number of commits that can have equal\ngeneration is limited bythe number of commits in a single topic, which is\ntypically small. This is opposed tothe minimum generation, which can be\nunbounded. For example, if everyone basestheir Git patches on the latest\nrelease, then if we walk into those topics, then weneed to walk all the way\nto that release to determine reachability.\n\nHere is a picture, representing each topic as an interval of consecutive\ngenerationvalues:\n\n# Minimum Generation Numbers:\n\nv2.19.0----------M1----M2----M3----M4\n     |\\          /     /     /     /\n     | [topic1]-/     /     /     /\n     |\\              /     /     /\n     | [topic2]-----//     /\n     |\\     /     /\n     | [topic3]---------/     /\n      \\                      /\n       [topic4]-------------/\n\n     =====generation====>\n\n# Maximum Generation Numbers:\n\nv2.19.0----------M1----M2----M3----M4\n     |\\          /      |     |     |\n     | [topic1]-/       |     |     |\n     |\\                 |     |     |\n     | \\-------[topic2]/      |     |\n     |\\                       |     |\n     | \\-------------[topic3]/      |\n      \\                             |\n       \\-------------------[topic4]/\n\n     =====generation====>\n\n>> **V3: Corrected Commit Date.**\n>> For a commit C, let its _corrected commit date_ (denoted by cdate(C))\n>> be the maximum of the commit date of C and the [corrected] commit dates of its\n>> parents.\n> Wouldn't it be better to use the maximum of the commit date of C, and\n> one second more than the corrected commit dates of its parents? This\n> way corrected dates would be strictly monotonic along the chain.\n>\n> Sidenote: in theory, sufficiently bad clock skew (like e.g. wrong year\n> in the future) could screw large swatches of the commit graph. In\n> practice, in real-life repositories, this doesn't happen, I guess.\n\nYes, you're right. Congyi Wu from the Azure Repos server team pointed \nthis out to\nme privately, as well. His example was someone merging a commit with date\n3000-01-01, and making all later commits be useless. Adding one to the \ncommit dates\nof the parents \"fixes\" this issue by reverting our negative-cut index to \nbe equivalent\nto minimum generation number for all commits with this commit in their \nhistory.\n\n>\n>>   If cdate(A) < cdate(B), then A cannot reach B.\n>>\n>> **V4: FELINE Index.**\n>> The FELINE index is a two-dimentional reachability index as defined in\n>> [Reachability Queries in Very Large Graphs: A Fast Refined Online\n>> Search Approach](https://openproceedings.org/EDBT/2014/paper_166.pdf)\n>> by Veloso, Cerf, Jeira, and Zaki. The index is not deterministically\n>> defined, but instead is defined in the following way:\n>>\n>> 1. Compute a reverse topological order of the commits. Let felineX(C)\n>>    be the position in which C appears in this list. Since this is\n>>    a reverse topological order, felineX(C) > felineX(P) for each parent\n>>    P of C.\n> Well, it depends on the definition of the topological order if it is\n> tolopogical order or reverse topological order. Anyway, the FELINE\n> paper includes discussion about FELINE-I, i.e. inversed feline index.\n> From FELINE and FELINE-I, one of those is what was used here.\n>\n>> 2. Compute a reverse topological order of the commits using Kahn's\n>>    algorithm, but when selecting among a list of commits with in-degree\n>>    zero, prioritize the commit by minimizing felineX. Let felineY(C)\n>>    be the position in which C appears in this list.\n> Note that the second step, as given in the paper, is actually\n> deterministic (assuming that we follow the recommendations; well, up to\n> a point). It needs some topological order for felineX, though.\n>\n>> Essentially, the felineY order is selected with the goal of swapping\n>> positions of topologically-independent commits relative to the felinX\n>> ordering. The resulting reachability index is as follows:\n>>\n>>    If felineX(A) < felineX(B), then A cannot reach B.\n>>    If felineY(A) < felineY(B), then A cannot reach B.\n>>\n>> _Commentary:_ In terms of comparing two commits directly, this index\n>> is quite strong. However, when we are performing our reachability\n>> algorithms that care about reachable sets (git log --graph), or\n>> boundaries between reachable sets (git merge-base, git log --graph A..B)\n>> we need to track a single pair (minX,minY) for comparion. In order to not\n>> miss anything during our search, we need to update this pair to be\n>> the minimum felineX(A) and minimum felineY(B) among all explored commits\n>> A and B. That is, the pair (minX, minY) is below our entire explored set.\n>> This can be a disadvantage for these algorithms.\n> Actually the problem is that FELINE index is partial order, not an\n> ordering; not something that we can use in a priority queue.\n>\n> But the single [reverse] topological ordering is a reachability index in\n> itself, and it is an ordering. Thus we can use felineX as an index in\n> priority queue (or we can use felineY).\n>\n> One thing to notice is that FELINE index performs well on real world\n> large graphs which have quite different structure from commit graphs;\n> among others they have either very large number of sources (head tips)\n> or sinks (root nodes), or both; those numbers grow with the number of\n> nodes. For commit graphs they don't perform as well; well, at least\n> ccording to my explorations on that matter in the Google Colaboratory\n> notebook [2].\n>\n> [2]: https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg\n>\n>> ### Comparing Reachability Index Versions Viability\n>>\n>> Before considering how well these indexes perform during our algorithm\n>> runs, let's take a moment to consider the implementation details and\n>> how they relate to the existing commit-graph file format and existing\n>> Git clients.\n>>\n>> * **Compatible?** In our test implementation, we use a previously unused\n>>   byte of data in the commit-graph format to indicate which reachability\n>>   index version we are using. Existing clients ignore this value, so we\n>>   will want to consider if these new indexes are _backwards compatible_.\n>>   That is, will they still report correct values if they ignore this byte\n>>   and use the generation number column from the commit-graph file assuming\n>>   the values are minimum generation numbers?\n> In other words \"backward compatibility\" for a reachability index means\n> that the reachability condition is exactly the same as it was:\n>\n>     If index(A) < index(B), then A cannot reach B.\n>\n> and also values of the reachability index are written in place of\n> generation numbers in the commit-graph.\n>\n>> * **Immutable?** Git objects are _immutable_. If you change an object you\n>>   actually create a new object with a new object ID. Are the values we\n>>   store for these reachability indexes also immutable?\n>>\n>> * **Local?** Are these values **locally computable**? That is, do we only\n>>   need to look at the parents of a commit (assuming those parents have\n>>   computed values) in order to determine the value at that commit?\n> Those two features imply that the number of commits that we need to walk\n> to be able to update reachability index after appending new commits is\n> O(new commits), which means O(changes). I would allow for simple\n> transformations of other values, e.g. adding a constant; we need to\n> rewrite commit-graph file anyway.\n>\n> I wonder if there are reachability indexes that are either immutable but\n> not local, or not immutable but local. Doesn't being local imply\n> immutability, with some common-sense assumptions (like no random choice\n> for parent-less commits)?\n\nLocal probably implies immutable, but the reverse does not. The example \nI gave\nelsewhere in the thread was \"number of commits reachable from C\". You can't\ndetermine this directly from the values of your parents, but it doesn't \nchange\neven if you add more commits to the graph.\n\n>\n>> | Index                     | Compatible? | Immutable? | Local? |\n>> |---------------------------|-------------|------------|--------|\n>> | Minimum Generation Number | Yes         | Yes        | Yes    |\n>> | (Epoch, Date) pairs       | Yes         | Yes        | Yes    |\n>> | Maximum Generation Number | Yes         | No         | No     |\n>> | Corrected Commit Date     | No          | Yes        | Yes    |\n>> | FELINE index              | Yes         | No         | No     |\n>>\n>> _Note:_ The corrected commit date uses the generation number column\n>> to store an offset of \"how much do I need to add to my commit date\n>> to get my corrected commit date?\" The values stored in that column\n>> are then not backwards-compatible.\n> Additional note: this offset / delta based approach to storing corrected\n> commit data is a form of lightweight compression, allowing it to fit\n> safely in 30 bits (while the commit date uses 32+2 = 34 bits itself).\n>\n> Assuming that we want to keep this feature from the original\n> commit-graph file format, that is.\n>\n>> _Note:_ The FELINE index requires storing two values instead of just\n>> one. One of these values could be stored in the generation number\n>> column and the other in an optional chunk, hence it could be backwards\n>> compatible. (This is not how it is implemented in our example\n>> implementation.)\n> So the table above refers to this hypothetical implementation when\n> stating that FELINE is backwards compatibile, but current test\n> implementation is not, isn't it?\n\nCorrect.\n\n>\n>> Data\n>> ----\n>>\n>> We focused on three types of performance tests that test the indexes\n>> in different ways. Each test lists the `git` command that is used,\n>> and the table lists which repository is used and which inputs.\n>>\n>> ### Test 1: `git log --topo-order -N`\n>>\n>> This test focuses on the number of commits that are parsed during\n>> a `git log --topo-order` before writing `N` commits to output.\n>>\n>> You can reproduce this test using `topo-order-tests.sh` and\n>> see all the data in `topo-order-summary.txt`. The values reported\n>> here are a sampling of the data, ignoring tests where all values\n>> were the same or extremely close in value.\n>>\n>>\n>> | Repo         | N     | V0     | V1     | V2     | V3     | V4    |\n>> |--------------|-------|--------|--------|--------|--------|-------|\n>> | android-base | 100   |  5,487 |  8,534 |  6,937 |  6,419 | 6,453 |\n>> | android-base | 1000  | 36,029 | 44,030 | 41,493 | 41,206 |45,431 |\n>> | chromium     | 100   |    101 |424,406 |    101 |    101 |   101 |\n>> | gerrit       | 100   |  8,212 |  8,533 |    164 |    159 |   162 |\n>> | gerrit       | 1000  |  8,512 |  8,533 |  1,990 |  1,973 | 3,766 |\n>> | Linux        | 100   | 12,458 | 12,444 | 13,683 | 13,123 |13,124 |\n>> | Linux        | 1000  | 24,436 | 26,247 | 27,878 | 26,430 |27,875 |\n>> | Linux        | 10000 | 30,364 | 28,891 | 27,878 | 26,430 |27,875 |\n>> | electron     | 1000  | 19,927 | 18,733 |  1,072 | 18,214 |18,214 |\n>> | Ffmpeg       | 10000 | 32,154 | 47,429 | 10,435 | 11,054 |11,054 |\n>> | jgit         | 1000  |  1,550 |  6,264 |  1,067 |  1,060 | 1,233 |\n>> | julia        | 10000 | 43,043 | 43,043 | 10,201 | 23,505 |23,828 |\n>> | odoo         | 1000  | 17,175 |  9,714 |  4,043 |  4,046 | 4,111 |\n>> | php-src      | 1000  | 19,014 | 27,530 |  1,311 |  1,305 | 1,320 |\n>> | rails        | 100   |  1,420 |  2,041 |  1,757 |  1,428 | 1,441 |\n>> | rails        | 1000  |  7,952 | 10,145 | 10,053 |  8,373 | 8,373 |\n>> | swift        | 1000  |  1,914 |  4,004 |  2,071 |  1,939 | 1,940 |\n>> | tensorflow   | 1000  | 10,019 | 39,221 |  6,711 | 10,051 |10,051 |\n>> | TypeScript   | 1000  |  2,873 | 12,014 |  3,049 |  2,876 | 2,876 |\n> Do I understand it correctly that the range of N for a given project is\n> limited by the depth of the project history (hence maximum N of 10000\n> for Linux kernel, but only 100 for chromium)?\n\nI ran the tests with N equal to 100, 1000, and 10000 on all repos, but only\nincluded results for values that were interesting. For chromium, something\nabout the topology let all versions (except V1) report N + 1, so I \ndidn't include\nthe other values.\n\n> I wonder what the OLD numbers are for these operations.\n\nThe OLD numbers are equal to the number of commits reachable from HEAD\nin every case. I didn't think this was interesting to report. You can \nsee the\nnumbers for yourself in the output data file:\n\nhttps://github.com/derrickstolee/gen-test/blob/master/topo-order-summary.txt\n\n>\n>> ### Test 2: `git log --topo-order -10 A..B`\n>>\n>> This test focuses on the number of commits that are parsed during\n>> a `git log --topo-order A..B` before writing ten commits to output.\n>> Since we fix a very small set of output commits, we care more about\n>> the part of the walk that determines which commits are reachable\n>> from `B` but not reachable from `A`. This part of the walk uses\n>> commit date as a heuristic in the existing implementation.\n> [...]\n>\n>> ### Test 3: `git merge-base A B`\n>>\n>> This test focuses on the number of commits that are parsed during\n>> a `git merge-base A B`. This part of the walk uses commit date as\n>> a heuristic in the existing implementation.\n> [...]\n>\n>> Conclusions\n>> -----------\n>>\n>> Based on the performance results alone, we should remove minimum\n>> generation numbers, (epoch, date) pairs, and FELINE index from\n>> consideration. There are enough examples of these indexes performing\n>> poorly.\n>>\n>> In contrast, maximum generation numbers and corrected commit\n>> dates both performed quite well. They are frequently the top\n>> two performing indexes, and rarely significantly different.\n>>\n>> The trade-off here now seems to be: which _property_ is more important,\n>> locally-computable or backwards-compatible?\n>>\n>> * Maximum generation number is backwards-compatible but not\n>>   locally-computable or immutable.\n>>\n>> * Corrected commit-date is locally-computable and immutable,\n>>   but not backwards-compatible.\n>>\n>> _Editor's Note:_ Every time I think about this trade-off, I can't\n>> come to a hard conclusion about which is better. Instead, I'll\n>> leave that up for discussion.\n> In my opinion being able to update commit-graph data fast is more\n> important than being backward-compatibile, i.e. beig able to use\n> commit-data file generated by new clients (and servers) by old clients.\n>\n>\n> Thank you for all your work,\n\nThanks for the thoughtful discussion!\n\n-Stolee\n"},{"id":"362211","messageId":"86tvl0zhos.fsf@gmail.com","threadId":"49709","inReplyTo":"CAGZ79ka-FTqaXdrMixjUp2THJ3L0YvEnkKxs3XFgB3WEEy2-Tg@mail.gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-01T20:06:11Z","receivedAt":"2018-11-01T20:06:19Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Stefan Beller writes:\n\n>> Based on the performance results alone, we should remove minimum\n>> generation numbers, (epoch, date) pairs, and FELINE index from\n>> consideration. There are enough examples of these indexes performing\n>> poorly.\n>>\n>> In contrast, maximum generation numbers and corrected commit\n>> dates both performed quite well. They are frequently the top\n>> two performing indexes, and rarely significantly different.\n>>\n>> The trade-off here now seems to be: which _property_ is more important,\n>> locally-computable or backwards-compatible?\n>>\n>> * Maximum generation number is backwards-compatible but not\n>> locally-computable or immutable.\n>\n> These maximum generation numbers sound like the reverse of\n> the generation numbers as they are currently implemented, i.e.\n> we count all commits between the commit A and all heads.\n\nActually\n\n maximum generation number =\n number of commits - reverse generation number\n\n> How would this impact creation of a commit?\n>\n> The current generation numbers can be lazily updated or not\n> updated at all. In my understanding of the maximum generation\n> numbers, a new commit would make these maximum generation\n> numbers invalid (i.e. they have to be recomputed).\n>\n> Are there ways out by deferring the computation of maximum\n> generation numbers while still being able to work with some\n> commits that are un-accounted for?\n\nAs I understand it, new commits added since commit-graph file was\ncreated would get simply INFINITY maximum/maximal generation numbers (if\nwe were using reverse generation numbers, new commits would get ZERO for\ngeneration number).\n\n> When recomputing these numbers, the current generation number\n> (V0) has the property that already existing numbers can be re-used\n> as-is. We only need to compute the numbers for new commits,\n> and then insert this to the appropriate data structures (which is\n> a separate problem, one could imagine a split generation\n> numbers file like the split index)\n\nSidenote: I wonder if there is some on-disk data structure with\nsimilarly fast read, but easier update.\n\n> For the V2 maximum generation numbers, would we need to\n> rewrite the numbers for all commits once we recompute them?\n> Assuming that is true, it sounds like the benchmark doesn't\n> cover the whole costs associated with V2, which is why the\n> exceptional performance can be explained.\n\nLet's check it using a simple example\n\nFirst, (minimum) parent-based generation numbers before and after\nextending the commit graph:\n\n 1 2 3 4 5 6 7 new\n 1 2 3 4 5 - - old\n .---.-----.---.-----.---*---*\n \\\n \\ 3 4 5 6 new\n \\ 3 4 5 6 old\n \\-.---.-----.---.\n \\\n \\ 5 new\n \\ - old\n \\-*\n\n\nNext, maximum generation numbers. We start with 9 commits, and we end\nup with 12 commits after the change\n\n 6 7 8 9 10 11 12 new\n 4 5 7 8 9 - - old\n .---.-----.---.-----.---*---*\n \\\n \\ 9 10 11 12 new\n \\ 6 7 8 9 old\n \\-.---.-----.---.\n \\\n \\ 12 new\n \\ - old\n \\-*\n\n\nAs you can see all maximum generation numbers got rewritten.\n\nThough if instead using the number of commits, we use the maximum\ngeneration number, or in other words the length of the longest path, we\nget the following:\n\n 1 2 3 4 5 6 7 new\n 1 2 4 5 6 - - old\n .---.-----.---.-----.---*---*\n \\\n \\ 4 5 6 7 new\n \\ 3 4 5 6 old\n \\-.---.-----.---.\n \\\n \\ 7 new\n \\ - old\n \\-*\n\nA bit better, but still much change in numbers.\n\n[...]\n>>\n>> * Corrected commit-date is locally-computable and immutable,\n>> but not backwards-compatible.\n>\n> How are these dates not backwards incompatible?\n> We don't have to expose these dates to the user, but\n> - just like generation numbers - could store them and use them\n> but not tell the user about it.\n>\n> We would need to be really careful to not expose them at all\n> as they look like the real dates, so that could make for an\n> awkward bug report.\n>\n> The approach of \"corrected commit date\" sounds like we could\n> have a very lazy approach, i.e. no extra data structures needed\n> for many commits (as the corrected date equals the real date)\n> and only need to store the corrections for some commits.\n> Such an approach however would not make it easy to know\n> if we operate on corrected dates, or if we even checked them\n> for correctness before.\n>\n> So if we'd have an additional row in the generation numbers file\n> telling the corrected date, then we should be able to be backwards\n> compatible?\n\nHere, from what I understand, being \"backwards compatibile\" means being\nable to use commit-graph file using the new format by old client,\ntrating the data as if they were generation numbers and not data\noffsets.\n\nBest,\n--\nJakub Narębski\n"},{"id":"362214","messageId":"86o9b8zbs9.fsf@gmail.com","threadId":"49709","inReplyTo":"3576719c-3cfb-547a-3548-3aaebfe6e8a2@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-01T22:13:42Z","receivedAt":"2018-11-01T22:13:50Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n\n> Here is a re-formatted version of the tables I introduced earlier.\n> The tables were too wide for public-inbox to render correctly (when\n> paired with my email client). Hopefully this bulleted-list format\n> works better. Thanks, Stefan, for pointing out the rendering\n> problems!\n>\n> ### Test 1: `git log --topo-order -N`\n>\n> This test focuses on the number of commits that are parsed during\n> a `git log --topo-order` before writing `N` commits to output.\n>\n> You can reproduce this test using `topo-order-tests.sh` and\n> see all the data in `topo-order-summary.txt`. The values reported\n> here are a sampling of the data, ignoring tests where all values\n> were the same or extremely close in value.\n>\n> android-base, N = 100\n>     V0: 5487\n>     V1: 8534\n>     V2: 6937\n>     V3: 6419\n>     V4: 6453\n[...]\n\n> ### Test 2: `git log --topo-order -10 A..B`\n[...]\n> android-base 53c1972bc8f 92f18ac3e39\n>   OLD: 39403\n>    V0:  1544\n>    V1:  6957\n>    V2:    26\n>    V3:  1015\n>    V4:  1098\n\nTwo minor issues. First, now that the data is not in the table format,\nwhere every bit of horizontal space matters, why not spell the names of\nnew proposed \"generation numbers\" (or rather reachability orderings) in\nfull, instead of using V0...V4 shortcuts? It is not as if we were short\nof space.\n\nSecond, why OLD data is present in tests 2 and 3, but not in test 1?\n\nBest,\n-- \nJakub Narębski\n"},{"id":"362259","messageId":"86ftwjzv1h.fsf@gmail.com","threadId":"49709","inReplyTo":"86tvl0zhos.fsf@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-02T09:30:02Z","receivedAt":"2018-11-02T09:30:12Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jakub Narebski writes:\n> Stefan Beller writes:\n[...]\n>> How would this impact creation of a commit?\n>>\n>> The current generation numbers can be lazily updated or not\n>> updated at all. In my understanding of the maximum generation\n>> numbers, a new commit would make these maximum generation\n>> numbers invalid (i.e. they have to be recomputed).\n[...]\n>> For the V2 maximum generation numbers, would we need to\n>> rewrite the numbers for all commits once we recompute them?\n>> Assuming that is true, it sounds like the benchmark doesn't\n>> cover the whole costs associated with V2, which is why the\n>> exceptional performance can be explained.\n>\n> Let's check it using a simple example\n>\n> First, (minimum) parent-based generation numbers before and after\n> extending the commit graph:\n>\n> 1 2 3 4 5 6 7 new\n> 1 2 3 4 5 - - old\n> .---.-----.---.-----.---*---*\n> \\\n> \\ 3 4 5 6 new\n> \\ 3 4 5 6 old\n> \\-.---.-----.---.\n> \\\n> \\ 5 new\n> \\ - old\n> \\-*\n\nLet me check yet another idea, using (minimum) parent-based V0 generation\nnumbers (counting distance from the sink / root) as a starting number\nfor source / heads commits.\n\n 1 2 3 4 5 6 7 new\n 1 2 3 4 5 - - old\n .---.-----.---.-----.---*---*\n \\\n \\ 3 4 5 6 new\n \\ 3 4 5 6 old\n \\-.---.-----.---.\n \\\n \\ 5 new\n \\ - old\n \\-*\n\n\nWell, on this example it looks like this variant of maximum generation\nnumbers can be done incrementally, but let's check another example\n\n 1 2 3 4 5 6 7 8 9 new\n 1 2 3 4 5 6 7 8 - old\n .---.-----.---.---.---.-----.---.---*\n \\ /\n \\ 3 4 / 5 6 7 8 new\n \\ 5 6 / - - - - old\n \\-.---.---------/---*---*---*---*\n\nIt looks like it doesn; give as good results as I thought. Less values\nare changed, but you would still need to recalculate them, unless it can\nbe proven that they do not need it.\n\n>\n> Next, maximum generation numbers. We start with 9 commits, and we end\n> up with 12 commits after the change\n>\n> 6 7 8 9 10 11 12 new\n> 4 5 7 8 9 - - old\n> .---.-----.---.-----.---*---*\n> \\\n> \\ 9 10 11 12 new\n> \\ 6 7 8 9 old\n> \\-.---.-----.---.\n> \\\n> \\ 12 new\n> \\ - old\n> \\-*\n>\n>\n> As you can see all maximum generation numbers got rewritten.\n>\n> Though if instead using the number of commits, we use the maximum\n> generation number, or in other words the length of the longest path, we\n> get the following:\n>\n> 1 2 3 4 5 6 7 new\n> 1 2 4 5 6 - - old\n> .---.-----.---.-----.---*---*\n> \\\n> \\ 4 5 6 7 new\n> \\ 3 4 5 6 old\n> \\-.---.-----.---.\n> \\\n> \\ 7 new\n> \\ - old\n> \\-*\n>\n> A bit better, but still much change in numbers.\n\n-- \nJakub Narębski\n"},{"id":"362270","messageId":"86tvkzy580.fsf@gmail.com","threadId":"49709","inReplyTo":"61a829ce-0d29-81c9-880e-7aef1bec916e@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-02T13:33:03Z","receivedAt":"2018-11-02T13:33:09Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 10/29/2018 11:59 PM, Junio C Hamano wrote:\n>> Derrick Stolee writes:\n[...]\n>>> * **Compatible?** In our test implementation, we use a previously unused\n>>> byte of data in the commit-graph format to indicate which reachability\n>>> index version we are using. Existing clients ignore this value, so we\n>>> will want to consider if these new indexes are _backwards compatible_.\n>>> That is, will they still report correct values if they ignore this byte\n>>> and use the generation number column from the commit-graph file assuming\n>>> the values are minimum generation numbers?\n>>\n>> I personally consider that the current commit-graph with generation\n>> numbers experimental, so I am not sure how much we care about this.\n>>\n>> Having said that.\n>>\n>> By the above definition, any new index that is wider than the\n>> current generation number cannot be compatible (can we even tell the\n>> existing clients how wide each elements in the ix array is?)\n>>\n>> In any case, perhaps the first thing to do is to update the clients\n>> so that they stop ignoring the version number field, and instead\n>> work without generation number when there is no version of reach.ix\n>> available in the file? That way, a better reachablility index can\n>> be chosen freely without having to worry about the compatibility.\n>\n> I can work on that. It should be as simple as setting commit->generation to\n> GENERATION_NUMBER_ZERO in fill_commit_in_graph when the graph\n> has a different version.\n\nThat is a very good idea, but we have here a chicken-and-egg problem.\nThe only way to denote that the generation numbers / reachability index\nhave changed (for reading/using: that it changed in backwards\nincompatibile way; for update: that it changed at all) is to change the\nformat version:\n\n 1-byte version number:\n Currently, the only valid version is 1.\n\nBut if we assume that different commit-graph format version simply means\nthat commit->generation is to be set to GENERATION_NUMBER_ZERO, then we\nblock possible changes to the structure of the commit-graph file.\n\n[Reads further in thread]\n\nAh, I see that's why you want to introduce [1]:\n\nDS>\nDS> 3. Reachability Index versioning\n\n[1]: https://public-inbox.org/git/6902dbff-d9f6-e897-2c20-d0cb47a50795@gmail.com/\n\n>>> * **Immutable?** Git objects are _immutable_. If you change an object you\n>>> actually create a new object with a new object ID. Are the values we store\n>>> for these reachability indexes also immutable?\n>>\n>> Even if we do not embed the reachability ix in commit objects,\n>> having an immutable value is probably a must if we want to make them\n>> incrementally computable, so this is a very good property to have.\n>> Unless there is a clever idea to incrementally compute a mutable\n>> reach.ix, my gut instinct says that this property is a must.\n\nI think that the reachability index can be mutable and non-local, but\nstill being able to be incrementally updated, though perhaps it would\nrequire not only calculations for new commits, but recalculations for\nsome limited subset of commits existing in the commit-graph file.\n\nI'm trying to modify exact definition of maximal generation numbers to\ncheck if I can find out a version that exhibits nearly-incremental\nupdates property.\n\n>> Another thing, perhaps related to \"local\" below, is if exactly the\n>> same reach.ix is computed by anybody, given an identical commit\n>> history graph (perhaps \"reproducibility\"?). I think most of the\n>> candidates you listed are reproducible without a fixed tie-breaker,\n>> but I am not sure about felineY() thing.\n\nfelineY() is deterministic (or can be made deterministic) for given\nfelineX() (i.e. given [reverse] topological order).\n\n>>> * **Local?** Are these values **locally computable**? That is, do we only\n>>> need to look at the parents of a commit (assuming those parents have\n>>> computed values) in order to determine the value at that commit?\n>>\n>> A subset of non-local reachability ix, for example, the ones that\n>> need to know what each commit's children are, cannot be immutable,\n>> as adding new objects to the graph (either with locally committing,\n>> or transferring objects from other repositories) would affect the\n>> ix; is this true for all non-local reachability ix, I wonder?\n>\n> As a thought experiment, we could define a function size(C) to be the\n> number of commits reachable from C.\n\nLet's call it reach(C), instead ;-)\n\n> This is not locally-computable\n> from the size values at C's parents due to the inclusion-exclusion\n> principle. We would need to compute it by walking the reachable set\n> and counting (resulting in quadratic performance overall) but is\n> immutable. Since the performance cost is so expensive (unlike the\n> linear costs in the other non-local versions) I didn't include it\n> in my comparison.\n\nLet's define Reach(C) as set of all commits reachable from commit C.\nThen reach(C) = ||Reach(C)||, where ||S|| is number of elements in the\nset S.\n\nIf commit A can reach commit B, then B ∈ Reach(A), but also Reach(B) ⊂\nReach(A), thus reach(B) < reach(A). Therefore if reach(A) <= reach(B)\nthen A cannot reach commit B -- reach(C) can be used as reachability\nindex.\n\nHowever the performance cost of calculating reach(C), i.e. full\ntraversal of the commit graph without ability for incremental update\n(well, you can do incremental update starting from the commits that have\nreachability bitmap [2]) is prohibitive. Never mind the fact that this\nindex would have, I think, the same performance problems as (minimum)\ngeneraton numbers.\n\n[2]: https://githubengineering.com/counting-objects/\n\n\nSIDENOTE 1: as gen(C) can be thought of as the lower boundary on\nreach(C), similarly sumgen(C) defined as being 1 for parent-less\ncommits, and being (sum_{P ∈ parents(C)} sumgen(P)) + 1 otherwise being\nthe upper boundary on reach(C). This sumgen(C) can also be used as\ngeneration number / reachability index.\n\n gen(C) <= reach(C) <= sumgen(C)\n\n\nSIDENOTE 2: The idea of using a proxy for Reach(B) ⊆ Reach(A) as a\nnegative-cut filter (negative-cut reachability index) is used in two\ntypes of reachability indices: one is Independent Permutation Labelling\n(IP+) [3] approach, the other is Bloom Filter Labelling (BFL) [4]. Both\nalgorithms are local, and with given permutation (which can be replaced\nby object ID, I think) for IP+ and given set of hash functions etc. for\nBFL they are both immutable.\n\n[3] Hao Wei, Jeffrey Xu Yu, Can Lu, Ruoming Jin \"Reachability Querying:\n An Independent Permutation Labeling Approach\", Proceedings of the\n VLDB Endowment, Vol. 7, No. 12 (2014)\n\n[4] Jiao Su, Qing Zhu, Hao Wei, Jeffrey Xu Yu \"Reachability Querying:\n Can It Be Even Faster?\", IEEE Transactions on Knowledge and Data\n Engineering (2016)\n\n\nBest,\n-- \nJakub Narębski\n"},{"id":"362294","messageId":"86a7mrxtko.fsf@gmail.com","threadId":"49709","inReplyTo":"6902dbff-d9f6-e897-2c20-d0cb47a50795@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-02T17:44:39Z","receivedAt":"2018-11-02T17:44:46Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 10/31/2018 8:54 AM, Ævar Arnfjörð Bjarmason wrote:\n>> On Tue, Oct 30 2018, Junio C Hamano wrote:\n>>> Derrick Stolee writes:\n>>>>\n>>>> In contrast, maximum generation numbers and corrected commit\n>>>> dates both performed quite well. They are frequently the top\n>>>> two performing indexes, and rarely significantly different.\n>>>>\n>>>> The trade-off here now seems to be: which _property_ is more important,\n>>>> locally-computable or backwards-compatible?\n>>>\n>>> Nice summary.\n>>>\n>>> As I already said, I personally do not think being compatible with\n>>> currently deployed clients is important at all (primarily because I\n>>> still consider the whole thing experimental), and there is a clear\n>>> way forward once we correct the mistake of not having a version\n>>> number in the file format that tells the updated clients to ignore\n>>> the generation numbers. For longer term viability, we should pick\n>>> something that is immutable, reproducible, computable with minimum\n>>> input---all of which would lead to being incrementally computable, I\n>>> would think.\n>>\n>> I think it depends on what we mean by backwards compatibility. None of\n>> our docs are saying this is experimental right now, just that it's\n>> opt-in like so many other git-config(1) options.\n>>\n>> So if we mean breaking backwards compatibility in that we'll write a new\n>> file or clobber the existing one with a version older clients can't use\n>> as an optimization, fine.\n>>\n>> But it would be bad to produce a hard error on older clients, but\n>> avoiding that seems as easy as just creating a \"commit-graph2\" file in\n>> .git/objects/info/.\n>\n> Well, we have a 1-byte version number following the \"CGPH\" header in\n> the commit-graph file, and clients will ignore the commit-graph file\n> if that number is not \"1\". My hope for backwards-compatibility was\n> to avoid incrementing this value and instead use the unused 8th byte.\n\nHow? Some of the considered new generation numbers were backwards\ncompatibile in the sense that for graph traversal the old code for\n(minimum) generation numbers could be used. But that is for reading.\nIf the old client tried to update new generation number using old\ngeneration number algorithm (assuming locality), it would write some\nchimaera that may or may not work.\n\n> However, it appears that we are destined to increment that version\n> number, anyway. Here is my list for what needs to be in the next\n> version of the commit-graph file format:\n\nAs a reminder, here is how the commit-graph format looks now [1]\n\n HEADER:\n 4-byte signature: CGPH\n 1-byte version number: 1\n 1-byte Hash Version: 1 = SHA-1\n 1-byte number (C) of \"chunks\": 3 or 4\n 1-byte (reserved for later use) \n CHUNK LOOKUP:\n (C + 1) * 12 bytes listing the table of contents for the chunks\n CHUNK DATA:\n OIDF\n OIDL\n CDAT\n EDGE [optional, depends on graph structure]\n TRAILER:\n checksum\n\n[1]: Documentation/technical/commit-graph-format.txt\n\n\n> 1. A four-byte hash version.\n\nWhy do you need a four-byte hash version? 255 possible hash functions\nis not enough?\n\n> 2. File incrementality (split commit-graph).\n\nThis would probably require a segment lookup part, and one chunk of each\ntype per segment (or even one chunk lookup table per segment). It may\nor may not need generation number which can support segmenting (here\nmaximal generation numbers have the advantage); but you can assume that\nif segment(A) > segment(B) then reach.ix(A) > reach.ix(B),\ni.e. lexicographical-like sort.\n\n> 3. Reachability Index versioning\n\nI assume that you mean here versioning for the reachability index that\nis stored in the CDAT section (if it is in a separate chunk, it should\nbe easy to version).\n\nThe easiest thing to do when encountering unknown or not supported\ngeneration number (perhaps the commit-graph file was created in the past\nby earlier version of Git, perahs it came from server with newer Git, or\nperhaps the same repository is sometimes accessed using newer and\nsometimes older Git version), is to set commit->generation_number to\nGENERATION_NUMBER_ZERO, as you wrote in [2].\n\nWe could encode backward-compatibility (for using) somewhat, but I\nwonder how much it would be of use.\n\n[2]: https://public-inbox.org/git/61a829ce-0d29-81c9-880e-7aef1bec916e@gmail.com/\n\n> Most of these changes will happen in the file header. The chunks\n> themselves don't need to change, but some chunks may be added that\n> only make sense in v2 commit-graphs.\n\nWhat I would like to see in v2 commit-graph format would be some kind\nconvention for naming / categorizing chunks, so that Git would be able\nto handle unknown chunks gracefully.\n\nIn PNG format there are various types of chunks. Quoting Wikipedia:\n\n Chunk types [in PNG format] are given a four-letter case sensitive\n ASCII type/name; compare FourCC. The case of the different letters in\n the name (bit 5 of the numeric value of the character) is a bit field\n that provides the decoder with some information on the nature of\n chunks it does not recognize.\n\n The case of the first letter indicates whether the chunk is critical\n or not. If the first letter is uppercase, the chunk is critical; if\n not, the chunk is ancillary. Critical chunks contain information that\n is necessary to read the file. If a decoder encounters a critical\n chunk it does not recognize, it must abort reading the file or supply\n the user with an appropriate warning.\n\nCurrently this is solved with the format version. For given format\nversion some chunks are necessary (critical); if there would be another\ntype of chunk that must be understood, we can simply increase format\nversion. \n\n The case of the second letter indicates whether the chunk is \"public\"\n (either in the specification or the registry of special-purpose public\n chunks) or \"private\" (not standardised). Uppercase is public and\n lowercase is private. This ensures that public and private chunk names\n can never conflict with each other (although two private chunk names\n could conflict).\n\nFor Git this could be \"official\" and \"experimental\"... though I don't\nsee people sharing commit-graph files with experimental chunks that can\nbe used only by some local unpublished fork of Git.\n\n The third letter must be uppercase to conform to the PNG\n specification. It is reserved for future expansion. Decoders should\n treat a chunk with a lower case third letter the same as any other\n unrecognised chunk.\n\nIn short: reserved. This could be the fate of all of those 4 flags that\nwe do not need.\n\n The case of the fourth letter indicates whether the chunk is safe to\n copy by editors that do not recognize it. If lowercase, the chunk may\n be safely copied regardless of the extent of modifications to the\n file. If uppercase, it may only be copied if the modifications have\n not touched any critical chunks.\n\nIf the data contained in the chunks is immutable, then it could be\ncopied when updating commit-graph file... but what to do with new\ncommits, with what to fill the data for a new commit for a copied\nunknown chunk? All zeros? All ones? Some value defined in the chunk\nitself?\n\nBest,\n-- \nJakub Narębski\n"},{"id":"362359","messageId":"861s82wdbp.fsf@gmail.com","threadId":"49709","inReplyTo":"0c6b42e4-e825-ff70-a528-e118abf4c435@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-03T12:33:14Z","receivedAt":"2018-11-03T12:33:24Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 11/1/2018 8:27 AM, Jakub Narebski wrote:\n>> Derrick Stolee writes:\n>>\n>>> Please also let me know about any additional tests that I could\n>>> run. Now that I've got a lot of test scripts built up, I can re-run\n>>> the test suite pretty quickly.\n>>\n>> I would add straighforward 1-to-N and N-to-1 reachability tests in the\n>> form of `git branch / tag --contains` and `git branch / tag --merged`,\n>> and perhaps also ahead-behind calculations used by `git status`, and\n>> N-to-M reachability tests used by tag following code in push and fetch.\n\n1-to-N and N-to-1 can be done with `git branch --merged` / `--contains`.\n\n>> Possibly also A...B walk, if it is not implemented via calculating\n>> merge-base.\n>\n> I believe this uses paint_down_to_common(), but looks at the PARENT1 and\n> PARENT2 flags afterward to determine the left/right/both relationships.\n\nRight, so I guess this is the same internal mechanism that `git\nmerge-base` utilizes, just used a bit differently. Thus benchmarking\n`git merge-base` should cover also A...B performance, I guess.\n\n>> Maybe even --ancestry-path walk, though I am not sure how important best\n>> performance for rhis case is (we would want good performance, but\n>> perhaps best is not needed for rarely used command).\n>\n> Currently, the implementation of --ancestry-path does not use a\n> reachability index.\n\nWell, using reachability index would certainly give it a boost.\n\n[...]\n>>> Generation Number Performance Test\n>>> ==================================\n>>>\n>>> Git uses the commit history to answer many basic questions, such as\n>>> computing a merge-base. Some of these algorithms can benefit from a\n>>> _reachability index_, which is a condition that allows us to answer\n>>> \"commit A cannot reach commit B\" in some cases. These require pre-\n>>> computing some values that we can load and use at run-time. Git\n>>> already has a notion of _generation number_, stores it in the commit-\n>>> graph file, and uses it in several reachability algorithms.\n>>\n>> Note that there are other kinds of reachability indices.\n>>\n>> First, there are reachability indices that can answer the full\n>> reachability query (if commit A can reach commit B, or if commit A\n>> cannot reach commit B) directly, without walking the commit graph at\n>> all: so called label-only approach. For example one could store for\n>> each commit the compressed list of all commits reachable from it\n>> (transitive closure compression).\n>>\n>> Those, I think (but I have not checked), would be of not much use for\n>> Git, as the size of the index grows stronger than linear with the number\n>> of commits, as grows the time to compute such index. So probably of no\n>> use to Git, at least not directly (Git uses so called \"bitmap index\",\n>> see e.g. [1], which stores reachability bit-vector as compressed\n>> bitmap... but not for all commits, only for a small subset).\n>>\n>>\n>> Second, beside negative-cut reachability indexes, that can answer with\n>> certainity that \"commit A cannot reach commit B\", like the generation\n>> numbers (also known as level, or topological level), there also\n>> positive-cut indexes (usually if not always based on the spanning tree\n>> or trees for the DAG), that can answer when \"commit A can reach commit\n>> B\".\n>>\n>> I think that those can lead to significant speedups for at least some\n>> types of commit traversal and reachability queries that Git needs to\n>> answer. But currently no algorithms has a provision for using\n>> positive-cut filter index. Anyway, such index would be auxiliary thing,\n>> see the next point.\n>>\n>>\n>> Third, we require more than having reachability index in the sense of\n>> having some kind of _labelling_, often composite, that can answer either\n>> \"commit A cannot reach commit B\" or \"commit A can reach commit B\",\n>> depending on the type. Git for most operations needs more, namely an\n>> actual _ordering_, that is a weak order (or to be more exact a total\n>> preorder, i.e. there can be two different commits with the same\n>> \"generation number\" or index, but always either idx(A) ≲ idx(B) or\n>> idx(B) ≲ idx(A)) and not only partial ordering (where there can be\n>> incomparable elements, i.e neither idx(A) ≼ idx(B) nor idx(B) ≼ idx(A)).\n>> This is because it needs to be used in priority queue to decide which\n>> commit to travel next; more on that later. This is also why there can\n>> be only one such \"main\" reachability _index_.\n>>\n>> [1]: https://githubengineering.com/counting-objects/\n>\n> Thanks for the details. At the moment, I'm only interested in improving our\n> negative-cut reachability index, as we have algorithms that can take\n> advantage of them (and can compare their performance directly).\n\nRight, I can agree with that. Positive-cut reachability index use would\nneed to be added separately.\n\nWhat I wanted to emphasize is the need for a _number_ (or a total\npreorder), not simply an _index_ (a label, perhaps a composite one).\nThis means, as I wrote, that there would be only one main \"generation\nnumber\". It also limits the number of possible reachability indexes to\nconsider.\n\n[...]\n>> In Git there are at least four different types of graph traversal\n>> queries, with somewhat different requirements, and affected differently\n>> by various reachability indexes.\n>>\n>>\n>> ## Pure reachability queries\n>>\n>> First there are pure reachability queries, when we are interested only\n>> in nswering he question whether commit A can reach commit B or not. We\n>> are nt interested in list of commits between A and B; if reachability\n>> index, be it negative-cut or positive-cut, can answer the question, it\n>> is all we need. If we need to walk (perform online search), then we are\n>> interested in just being able to arrive; we need to walk only one path.\n>>\n>> This query can be performed one-to-one, one-to-many (which of commits\n>> from the list can be reached from commit A), many-to-one (which commits\n>> from the list can reach commit B), and many-to-many -- the latest for\n>> example with recently added get_reachable_subset().\n>>\n>> These types of queries are done by \"git branch --contains\" (and\n>> \"--no-contains\") and \"git branch --merged\" (and \"--no-merged\"), the same\n>> for \"git tag\"; if I remember it correctly those were among first\n>> operations that were sped up by commit-graph mechanism. Many-to-many\n>> queries are done for tag following in \"git push\" and \"git fetch\".\n>>\n>> Note that those queries are missing from gen-test.\n>\n> These are definitely a good idea to pursue further testing. The only\n> thing I can think of right now is that the tests can be hard to set up,\n> but perhaps`git branch --remote --contains` or `git tag --contains`\n> would be interesting.\n\nAlso `git tab --merged`, for the \"reverse\" check; then this should cover\nboth sides of N-to-M queries used by `git fetch` (add_missing_tags() via\nnew get_reachable_subset()).\n\nIn any case, if all else fails, we can add new test-something script...\n\n>> ## Topological ordering\n>>\n>> Here reachability index is used to find out in-degree of considered\n>> commits (starting from a set of starting points). Here we don't really\n>> need to walk all paths, but we need to walk all possible ways of\n>> arriving at given commit.\n>\n> You make a good point here about the difference between \"all paths to C\"\n> and \"all children of C\", since the number of paths can grow exponentially\n> (and frequently does in Git) but the number of children is linear (and\n> small in practice).\n\nSidenote: I wonder how the distribution of number of parent\n(out-degree), numbers of childern (in-degree), and number of paths to a\ncommit looks like.\n\n>> Though I guess the [new] incremental algorithm could be modified to only\n>> check for in-degree being zero or non-zero. Would it make it slower or\n>> faster; I guess in absence of good positive-cut reachability filter it\n>> would make it slower.\n>\n> I don't understand how a positive-cut filter helps in this case. The point\n> of the in-degreecalculation is to say \"we already output all commits that\n> can reach this commit\" beforewe output another commit. How could a\n> positive-cut filter help here?\n\nThat was more of an idle thought than a concrete proposal.\n\nWith the new 3-phase algorithm, we populate topo_queue with commits of\nan in-degree of zero, calculating this on-degree if necessary. I\nthought that those pre-candidates could have been eliminated early with\npositive-cut index, instead of having to compute in-degree in full.\n\n[...]\n>> ## Strict ancestry, or ancestry path\n>>\n>> When given a range of commits to display (e.g. A..B), only display\n>> commits that exist directly on the ancestry chain between B and A,\n>> i.e. commits that are both descendants of B, and ancestors of A. In\n>> other words, find all paths from B to A (if they exist).\n>>\n>> In this case we want to walk all the paths, heavily pruning. This\n>> should be less dependent on reachability index quality as an index (as\n>> an ordering), and more on pruning ability of the filter.\n>>\n>> This case is not tested in gen-test, but I wonder how often this feature\n>> is actualy used (if it would be worth adding it to the benchmark, and if\n>> so, with what weight behind it).\n>\n> As mentioned earlier, the --ancestry-path algorithm does not currently use a\n> negative-cut filter, so we would not gather any data on this at the moment.\n>\n> However, I imagine the algorithm is similar to the typical A..B case, as we\n> need to discover the (po)set difference, construct the reversed digraph on\n> those commits, and walk backwards from A. Assuming the difference is much\n> smaller than the entire commit graph, then the main cost is the walk that\n> discovers the difference, and hence is covered somewhat by the `git log\n> --topo-order A..B` tests.\n\nI would say that --ancestry-path is a little like A..B walk, a little\nlike the in-degree computing in --topo-order (because in in-degree\ncomputing we are also interested only in paths that arrive at given\ncommit).\n\n[...]\n>>> **V1: (Epoch, Date) Pairs.**\n>>>\n>>> For each commit, store a pair of values called the _epoch_ and the _date_.\n>>> The date is the normal commit date. The _epoch_ of a commit is the minimum\n>>> X such that X is at least the maximum epoch of each parent, and at least\n>>> one more than the epoch of any parent whose date is larger than the date\n>>> of this commit (i.e. there is clock skew between this commit and this\n>>> parent). In this way, we can use the following reachability index:\n>>>\n>>>    If epoch(A) < epoch(B), then A cannot reach B.\n>>>    If epoch(A) == epoch(B) and date(A) < date(B), then A cannot reach B.\n>>\n>> I wonder what makes it perform worse than corrected date aka V3.\n>\n> In the example `git merge-base v4.8 v4.9` in the Linux repo, the topology\n> includes two commits (say, C1 and C2) of low generation number but high\n> commit-date. These commits also have low epoch. However, there are 607\n> commits in the repo whose commit date is smaller than a parent's commit\n> date. This means that the epoch in themain trunk of the repo can be as\n> high as 607, while the epoch for C1 and C2 is likely in the single digits.\n> This means that we need to walk all commits with epoch greater than\n> min { epoch(C1), epoch(C2) } before we explore C1 and C2 and terminate\n> the walk.\n>\n> In V3, the commits C1 and C2 have high corrected commit date, higher than\n> any of the commits that require positive offset to overcome the clock skew\n> with their parents. This allows the walk to be very similar to the old\n> algorithm, as seen in this `git merge-base A B` test summary:\n>\n> Linux c8d2bc9bc39e 69973b830859\n[I have added names of algorithms / generationn numbers here]\n\n>   OLD: 167468 ----- no reachability index\n>    V0: 635579 gen(C) (Minimum) Generation Number\n>    V1: 630138 epoch(C) (Epoch, Date) Pairs\n>    V2:  33716 maxgen(C) Maximum Generation Numbers\n>    V3: 167496 cdate(C) Corrected Commit Date\n>    V4: 153774 felineX(C) FELINE Index\n\nAh, so the problem with (Epoch, Date) pairs is that the trunk acquires\nhigh epoch, while side branches (which may be shortcuts) often have\nlower epoch. Makes sense, if maybe not obvious without such\nexamination.\n\n>>> **V2: Maximum Generation Numbers.**\n>>> The _maximum generation number_ of a commit (denoted by maxgen(A)) is\n>>> defined using its _children_ and the total number of commits in the repo.\n>>> If A is a commit with no children (that is, there is no commit B with\n>>> A as a parent) then maxgen(A) is equal to the number of commits in the repo.\n>>> For all other commits A, maxgen(A) is one less than the minimum maxgen(B)\n>>> among children B. This can be computed by initializing maxgen(C) to the\n>>> number of commits, then walking the commit graph in topological order,\n>>> assigning maxgen(P) = min { maxgen(P), maxgen(C) - 1 } for each parent P\n>>> of the currently-walking commit C. We then have the same reachability\n>>> index as minimum generation number:\n>>>\n>>>   If maxgen(A) < maxgen(B), then A cannot reach B.\n>>\n>> If I understand it correctly, this is the same as reverse generation\n>> numbers, or reverse topological levels; in other words genertion numbers\n>> on reversed graph -- only transformed:\n>>\n>> maxgen(A) == number_of_commits - (revgen(A) - 1)\n\nActually using number_of_commits may not be the best choice here with\nrespect to number of commits that need to have maxgen(C) be recalculated\non update...\n\n>> We define revgen(A) in the following way:\n>> - for head tips (for source nodes), i.e. commits with in-degree of 0,\n>> with no children, have revgen(A) = 1 (revgen(A) = 0 is left for\n>> commits outside commit-graph, which translates to INFINITY for\n>> maxgen(A)).\n>> - otherwise, it is 1 more than maximum revgen(C) of its children\n>>\n>> They are equivalent, but maxgen(A) is \"backward compatibile\", that is\n>> the rechability condition is exactly the same as for ordinary generation\n>> numbers:\n>>\n>>     If gen(A) < gen(B), then A cannot reach B.\n>>     If maxgen(A) < maxgen(B), then A cannot reach B.\n>>\n>> But\n>>\n>>     If revgen(A) > revgen(B), then A cannot reach B.\n>\n> Yes, these are the same idea, and the reason to phrase it as I did is to\n> keep the inequality in the same direction.\n\n...and if using gen(C) as a starting point, you avoid rewriting whole\nDAG on update.\n\nDefinition of maxgen'(C):\n\n - if A is commit without children (that is, there is no commit B with\n A as a parent), then maxgen'(A) = gen(A)\n - otherwise, maxgen'(A) = -1 + min_{B has A as parent}(maxgen'(B))\n\nUpdate algorithm:\n\n 1. compute gen(A) for all new commits, which is O(changes)\n 2. select commit A with highest gen(A) that doesn't have maxgen'(A):\n [such commit does not have any children, because of gen() properties]\n and add it to queue Q\n 2.1. take commit C from the queue Q\n 2.2. for each parent P of commit C\n 2.2.1. if maxgen'(P) <= maxgen'(C) - 1, continue\n 2.2.2. update maxgen'(P) to maxgen'(C) - 1\n 2.2.3. add P to queue Q\n\nI have tested this version of maxgen(C) algorithm in a very few cases in\nother post in this thread [3], and it looks like the amount of commits\nthat need to have maxgen() recalculated is limited.\n\n[3]: https://public-inbox.org/git/86ftwjzv1h.fsf@gmail.com/\n\n[...]\n>>> _Commentary:_ The known examples where (minimum) generation numbers perform\n>>> worse than commit date heuristics involve commits with recent commit dates\n>>> but whose parents have very low generation number compared to most recent\n>>> commits. In a way, minimum generation numbers increase the odds that we\n>>> can say \"A cannot reach B\" when A is fixed and B is selected at random.\n>>> Maximum generation numbers increase the odds that we can say \"A cannot\n>>> reach B\" when B is fixed and A is selected at random. This helps us when\n>>> we are exploring during a reachability algorithm and have explored few\n>>> commits and want to say that the large set of unexplored commits cannot\n>>> reach any of the explored commits.\n>>>\n>> I guess that the situation where shortcut path have recent date, while\n>> having less commits in path (and thus lover ordinary generation number)\n>> is more common in real commit graphs because one might want to base a\n>> commit (for example a bugfix) on an old commit, but commits usually get\n>> merged quickly, and not left for long time. If they re left for long\n>> time, they usually needs correction (via rebase) before being merged,\n>> and again we have commit with date close to the date of merge, leading\n>> to a shortcut.\n>>\n>> Does this reasoning looks correct to you?\n>\n> These \"bug fixes based on old commits\" cases are few and far between, so\n> are not enough to explain how often maximum generation number works well.\n> Instead, I would say that it works well because the typical Git pattern is\n> to merge into a single trunk. In the case of projects like Linux, there are\n> multiple \"trunks\" that are run by lieutenants and are merged into a \"super\n> trunk\"; even in these cases, the number of trunks is much smaller than the\n> number of topics. Let's focus on a single-trunk model for the\n> discussion below.\n>\n> When working with a single trunk, most merge commits are in the first-parent\n> historyof that trunk. As we travel down those trunks, the maximum generation\n> is decreasing. This means that the number of commits that can have equal\n> generation is limited bythe number of commits in a single topic, which is\n> typically small. This is opposed to the minimum generation, which can be\n> unbounded. For example, if everyone bases their Git patches on the latest\n> release, then if we walk into those topics, then we need to walk all the way\n> to that release to determine reachability.\n>\n> Here is a picture, representing each topic as an interval of consecutive\n> generation values:\n>\n> # Minimum Generation Numbers:\n>\n> v2.19.0----------M1----M2----M3----M4\n>     |\\          /     /     /     /\n>     | [topic1]-/     /     /     /\n>     |\\              /     /     /\n>     | [topic2]-----/     /     /\n>     |\\                  /     /\n>     | [topic3]---------/     /\n>      \\                      /\n>       [topic4]-------------/\n>\n>     =====generation====>\n>\n> # Maximum Generation Numbers:\n>\n> v2.19.0----------M1----M2----M3----M4\n>     |\\          /      |     |     |\n>     | [topic1]-/       |     |     |\n>     |\\                 |     |     |\n>     | \\-------[topic2]/      |     |\n>     |\\                       |     |\n>     | \\-------------[topic3]/      |\n>      \\                             |\n>       \\-------------------[topic4]/\n>\n>     =====generation====>\n\nAll right, so the problem with (minimum) generation numbers performance\nwill be exhibited in any project that utilizes the topic branch\nworkflow.\n\nNice to know the case.\n\n>>> **V3: Corrected Commit Date.**\n>>> For a commit C, let its _corrected commit date_ (denoted by cdate(C))\n>>> be the maximum of the commit date of C and the [corrected] commit dates of its\n>>> parents.\n>>\n>> Wouldn't it be better to use the maximum of the commit date of C, and\n>> one second more than the corrected commit dates of its parents? This\n>> way corrected dates would be strictly monotonic along the chain.\n>>\n>> Sidenote: in theory, sufficiently bad clock skew (like e.g. wrong year\n>> in the future) could screw large swatches of the commit graph. In\n>> practice, in real-life repositories, this doesn't happen, I guess.\n>\n> Yes, you're right. Congyi Wu from the Azure Repos server team pointed\n> this out to me privately, as well. His example was someone merging a\n> commit with date 3000-01-01, and making all later commits be\n> useless. Adding one to the commit dates of the parents \"fixes\" this\n> issue by reverting our negative-cut index to be equivalent to minimum\n> generation number for all commits with this commit in their history.\n\nI wonder if the problem with bad clock skew with the date far in the\nfuture could be solved by using instead for such cases (where\ndate(parent) > date(commit) + large Delta) the average of the commit and\nof the grandparents (parents of parent commit with such large positive\nclock skew). Though this wouldn't be strictly speaking immutable...\n\nAnother edge case, which I hope is not a problem in real-life\nrepositories, is clock skew very far in the past, and storing offsets in\n30-bits. If there was some malformed commit which has 0 as commit date\nepoch (Unix time), i.e. 1970-01-01, then the delta / offset may not fit\nin 30 bits that we use for storing generation numbers; there are 32+2 =\n34 bits for comit date. Something to think about.\n\n[...]\n>>> ### Comparing Reachability Index Versions Viability\n>>>\n>>> Before considering how well these indexes perform during our algorithm\n>>> runs, let's take a moment to consider the implementation details and\n>>> how they relate to the existing commit-graph file format and existing\n>>> Git clients.\n>>>\n>>> * **Compatible?** In our test implementation, we use a previously unused\n>>>   byte of data in the commit-graph format to indicate which reachability\n>>>   index version we are using. Existing clients ignore this value, so we\n>>>   will want to consider if these new indexes are _backwards compatible_.\n>>>   That is, will they still report correct values if they ignore this byte\n>>>   and use the generation number column from the commit-graph file assuming\n>>>   the values are minimum generation numbers?\n>>\n>> In other words \"backward compatibility\" for a reachability index means\n>> that the reachability condition is exactly the same as it was:\n>>\n>>     If index(A) < index(B), then A cannot reach B.\n>>\n>> and also values of the reachability index are written in place of\n>> generation numbers in the commit-graph.\n\nNote that it is backwards-compatibility only for use of generation\nnumbers, but of course not for an update.\n\n>>> * **Immutable?** Git objects are _immutable_. If you change an object you\n>>>   actually create a new object with a new object ID. Are the values we\n>>>   store for these reachability indexes also immutable?\n>>>\n>>> * **Local?** Are these values **locally computable**? That is, do we only\n>>>   need to look at the parents of a commit (assuming those parents have\n>>>   computed values) in order to determine the value at that commit?\n>>>\n>> Those two features imply that the number of commits that we need to walk\n>> to be able to update reachability index after appending new commits is\n>> O(new commits), which means O(changes). I would allow for simple\n>> transformations of other values, e.g. adding a constant; we need to\n>> rewrite commit-graph file anyway.\n>>\n>> I wonder if there are reachability indexes that are either immutable but\n>> not local, or not immutable but local. Doesn't being local imply\n>> immutability, with some common-sense assumptions (like no random choice\n>> for parent-less commits)?\n>\n> Local probably implies immutable, but the reverse does not. The\n> example I gave elsewhere in the thread was \"number of commits\n> reachable from C\". You can't determine this directly from the values\n> of your parents, but it doesn't change even if you add more commits to\n> the graph.\n\nRight, reach(C) is immutable but not local.\n\nLocal may not mean immutable if the starting points, i.e. parentless\ncommits, get assingled not-immutable values. But I don't see how that\ncould happen without some randomness.\n\n>>> Data\n>>> ----\n>>>\n>>> We focused on three types of performance tests that test the indexes\n>>> in different ways. Each test lists the `git` command that is used,\n>>> and the table lists which repository is used and which inputs.\n>>>\n>>> ### Test 1: `git log --topo-order -N`\n[...]\n>>>\n>>> | Repo         | N     | V0     | V1     | V2     | V3     | V4    |\n>>> |--------------|-------|--------|--------|--------|--------|-------|\n>>> | android-base | 100   |  5,487 |  8,534 |  6,937 |  6,419 | 6,453 |\n>>> | android-base | 1000  | 36,029 | 44,030 | 41,493 | 41,206 |45,431 |\n>>> | chromium     | 100   |    101 |424,406 |    101 |    101 |   101 |\n>>> | gerrit       | 100   |  8,212 |  8,533 |    164 |    159 |   162 |\n>>> | gerrit       | 1000  |  8,512 |  8,533 |  1,990 |  1,973 | 3,766 |\n>>> | Linux        | 100   | 12,458 | 12,444 | 13,683 | 13,123 |13,124 |\n>>> | Linux        | 1000  | 24,436 | 26,247 | 27,878 | 26,430 |27,875 |\n>>> | Linux        | 10000 | 30,364 | 28,891 | 27,878 | 26,430 |27,875 |\n>>> | electron     | 1000  | 19,927 | 18,733 |  1,072 | 18,214 |18,214 |\n>>> | Ffmpeg       | 10000 | 32,154 | 47,429 | 10,435 | 11,054 |11,054 |\n>>> | jgit         | 1000  |  1,550 |  6,264 |  1,067 |  1,060 | 1,233 |\n>>> | julia        | 10000 | 43,043 | 43,043 | 10,201 | 23,505 |23,828 |\n>>> | odoo         | 1000  | 17,175 |  9,714 |  4,043 |  4,046 | 4,111 |\n>>> | php-src      | 1000  | 19,014 | 27,530 |  1,311 |  1,305 | 1,320 |\n>>> | rails        | 100   |  1,420 |  2,041 |  1,757 |  1,428 | 1,441 |\n>>> | rails        | 1000  |  7,952 | 10,145 | 10,053 |  8,373 | 8,373 |\n>>> | swift        | 1000  |  1,914 |  4,004 |  2,071 |  1,939 | 1,940 |\n>>> | tensorflow   | 1000  | 10,019 | 39,221 |  6,711 | 10,051 |10,051 |\n>>> | TypeScript   | 1000  |  2,873 | 12,014 |  3,049 |  2,876 | 2,876 |\n>>\n>> Do I understand it correctly that the range of N for a given project is\n>> limited by the depth of the project history (hence maximum N of 10000\n>> for Linux kernel, but only 100 for chromium)?\n>\n> I ran the tests with N equal to 100, 1000, and 10000 on all repos, but only\n> included results for values that were interesting. For chromium, something\n> about the topology let all versions (except V1) report N + 1, so I\n> didn't include the other values.\n\nAh, that information (only interesting cases were included) would be\nsomething good to know.\n\nI wonder if the relative performance of different generation numbers is\ncorrelated with the topology of the commit graph, for example with\nincrement patterns to intergation patterns ratio in the commit metagraph\n(like --simplify-by-decoration), like in [4] and related works.\n\n[4] Marco Biazzini, Martin Monperrus, Benoit Baudry \"On Analyzing the\n Topology of Commit Histories in Decentralized Version Control\n Systems\", DOI: 10.1109/ICSME.2014.48 (2014)\n\n>> I wonder what the OLD numbers are for these operations.\n>\n> The OLD numbers are equal to the number of commits reachable from HEAD\n> in every case. I didn't think this was interesting to report. You can\n> see the numbers for yourself in the output data file:\n>\n> https://github.com/derrickstolee/gen-test/blob/master/topo-order-summary.txt\n\nThanks for the info.\n\n-- \nJakub Narębski\n"},{"id":"362373","messageId":"86r2g2ul51.fsf@gmail.com","threadId":"49709","inReplyTo":"86ftwjzv1h.fsf@gmail.com","subject":"Re: [RFC] Generation Number v2","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-11-03T17:27:22Z","receivedAt":"2018-11-03T17:27:30Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jakub Narebski writes:\n> Jakub Narebski writes:\n>> Stefan Beller writes:\n> [...]\n>>> How would this impact creation of a commit?\n>>>\n>>> The current generation numbers can be lazily updated or not\n>>> updated at all. In my understanding of the maximum generation\n>>> numbers, a new commit would make these maximum generation\n>>> numbers invalid (i.e. they have to be recomputed).\n> [...]\n>>> For the V2 maximum generation numbers, would we need to\n>>> rewrite the numbers for all commits once we recompute them?\n>>> Assuming that is true, it sounds like the benchmark doesn't\n>>> cover the whole costs associated with V2, which is why the\n>>> exceptional performance can be explained.\n>>\n>> Let's check it using a simple example\n>>\n>> First, (minimum) parent-based generation numbers before and after\n>> extending the commit graph:\n>>\n>> 1 2 3 4 5 6 7 new\n>> 1 2 3 4 5 - - old\n>> .---.-----.---.-----.---*---*\n>> \\\n>> \\ 3 4 5 6 new\n>> \\ 3 4 5 6 old\n>> \\-.---.-----.---.\n>> \\\n>> \\ 5 new\n>> \\ - old\n>> \\-*\n>\n> Let me check yet another idea, using (minimum) parent-based V0 generation\n> numbers (counting distance from the sink / root) as a starting number\n> for source / heads commits.\n[...]\n\n> [...] but let's check another example\n>\n> 1 2 3 4 5 6 7 8 9 new\n> 1 2 3 4 5 6 7 8 - old\n> .---.-----.---.---.---.-----.---.---*\n> \\ /\n> \\ 3 4 / 5 6 7 8 new\n> \\ 5 6 / - - - - old\n> \\-.---.---------/---*---*---*---*\n\nBut let's do this correctly.\n\n\n 1 2 3 4 5 6 7 8 9 new\n 1 2 3 4 5 6 7 8 - old\n .---.-----.---.------.---.-----.---.---*\n \\ /\n \\ 3 4 / new\n \\ 5 6 / old\n \\-.---.------------/\n \\\n \\ 5 6 7 8 new\n \\ - - - - old\n \\--*---*-----*---*\n\nWell, it looks as if I draw it incorrectly, but performed calculations\nright. You may need to modify / change some data, but it looks as if it\nis not that much of a problem.\n\nThe new version of the maximum generation numbers looks like it gives\nthe same results as generation numbers for the \"longest\" path, and\nupdate may affect only the side-branches that were added to. All\nbranches merged into the trunk, and not added to should be safe with\nrespect to updating.\n\nCan anyone here prove a thing about update of those modified maximum\ngeneration numbers? Thanks in advance.\n\nBest,\n-- \nJakub Narębski\n"}]}