On Mon, Jul 16, 2018 at 6:00 AM Derrick Stolee via GitGitGadget <gitgitgadget@xxxxxxxxx> wrote: > > From: Derrick Stolee <dstolee@xxxxxxxxxxxxx> > > 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. > > Since in_merge_bases() uses paint_down_to_common(), is_descendant_of() > naturally found cutoffs to avoid walking the entire commit graph. Since > we want to always return the correct result, we cannot use the > min_commit_date cutoff in can_all_from_reach. We then rely on generation > numbers to provide the cutoff. > > Since not all repos will have a commit-graph file, nor will we always > have generation numbers computed for a commit-graph file, create a new > method, generation_numbers_enabled(), that checks for a commit-graph > file and sees if the first commit in the file has a non-zero generation > number. In the case that we do not have generation numbers, use the old > logic for is_descendant_of(). > > 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.26 s > After: 0.21 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' with this input: > > A:v4.9 > B:v3.19 > > Before: 0.10 s > After: 0.08 s > > By adding a new commit with parent v3.19, we test the non-reachable case > of ref_newer: > > Before: 0.09 s > After: 0.08 s > > Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx> > --- Thanks for the commit message. The code itself looks good! I think this series is nearly done, I have only commented on style issues so far, which are easier to address than fundamental design issues or naming things. Thanks, Stefan
