From: Derrick Stolee Date: Tue, 1 May 2018 12:47:21 +0000 (+0000) Subject: commit: use generation number in remove_redundant() X-Git-Tag: v2.19.0-rc0~192^2~3 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/04bc8d1ecc30bae9589f3d77a0a89f3dca28a024?hp=04bc8d1ecc30bae9589f3d77a0a89f3dca28a024 commit: use generation number in remove_redundant() The static remove_redundant() method is used to filter a list of commits by removing those that are reachable from another commit in the list. This is used to remove all possible merge- bases except a maximal, mutually independent set. To determine these commits are independent, we use a number of paint_down_to_common() walks and use the PARENT1, PARENT2 flags to determine reachability. Since we only care about reachability and not the full set of merge-bases between 'one' and 'twos', we can use the 'min_generation' parameter to short-circuit the walk. When no commit-graph exists, there is no change in behavior. For a copy of the Linux repository, we measured the following performance improvements: git merge-base v3.3 v4.5 Before: 234 ms After: 208 ms Rel %: -11% git merge-base v4.3 v4.5 Before: 102 ms After: 83 ms Rel %: -19% The experiments above were chosen to demonstrate that we are improving the filtering of the merge-base set. In the first example, more time is spent walking the history to find the set of merge bases before the remove_redundant() call. The starting commits are closer together in the second example, therefore more time is spent in remove_redundant(). The relative change in performance differs as expected. Reported-by: Jakub Narebski Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano ---