• D
    commit-reach: use can_all_from_reach · 6cc01743
    Derrick Stolee 提交于
    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: NDerrick Stolee <dstolee@microsoft.com>
    Signed-off-by: NJunio C Hamano <gitster@pobox.com>
    6cc01743
commit-reach.c 16.3 KB