Hi Derrick, On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee <dstolee@xxxxxxxxxxxxx> wrote: > > The is_descendant_of method previously used in_merge_bases() to check if > the commit can reach any of the commits in the provided list. This had > two performance problems: > > 1. The performance is quadratic in worst-case. > > 2. A single in_merge_bases() call requires walking beyond the target > commit in order to find the full set of boundary commits that may be > merge-bases. > > The can_all_from_reach method avoids this quadratic behavior and can > limit the search beyond the target commits using generation numbers. It > requires a small prototype adjustment to stop using commit-date as a > cutoff, as that optimization is no longer appropriate here. > > Performance was meausured on a copy of the Linux repository using the > 'test-tool reach is_descendant_of' command using this input: > > A:v4.9 > X:v4.10 > X:v4.11 > X:v4.12 > X:v4.13 > X:v4.14 > X:v4.15 > X:v4.16 > X:v4.17 > X.v3.0 > > Note that this input is tailored to demonstrate the quadratic nature of > the previous method, as it will compute merge-bases for v4.9 versus all > of the later versions before checking against v4.1. > > Before: 0.31 s > After: 0.27 s > > Since we previously used the is_descendant_of method in the ref_newer > method, we also measured performance there using > 'test-tool reach ref_newer': > > Before: 0.12 s > After: 0.11 s > > Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx> > --- > > One thing I know is missing from this commit is a special-case to use > the old logic when there is no commit-graph present. The > can_all_from_reach() algorithm can be worse when we do not have good > generation number cutoffs. In the previous case of > can_all_from_reach_with_flags(), we already had an established pattern > of using commit date as a cutoff, so the generation number is only a > second cutoff and the algorithm cannot walk more commits than before. I like this series, Thanks for writing it! Stefan
