• Derrick Stolee's avatar
    commit-reach: make can_all_from_reach... linear · 4fbcca4e
    Derrick Stolee authored
    The can_all_from_reach_with_flags() algorithm is currently quadratic in
    the worst case, because it calls the reachable() method for every 'from'
    without tracking which commits have already been walked or which can
    already reach a commit in 'to'.
    Rewrite the algorithm to walk each commit a constant number of times.
    We also add some optimizations that should work for the main consumer of
    this method: fetch negotitation (haves/wants).
    The first step includes using a depth-first-search (DFS) from each
    'from' commit, sorted by ascending generation number. We do not walk
    beyond the minimum generation number or the minimum commit date. This
    DFS is likely to be faster than the existing reachable() method because
    we expect previous ref values to be along the first-parent history.
    If we find a target commit, then we mark everything in the DFS stack as
    a RESULT. This expands the set of targets for the other 'from' commits.
    We also mark the visited commits using 'assign_flag' to prevent re-
    walking the same commits.
    We still need to clear our flags at the end, which is why we will have a
    total of three visits to each commit.
    Performance was measured on the Linux repository using
    'test-tool reach can_all_from_reach'. The input included rows seeded by
    tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as
    v3.[0-9]*. This mimics a (very large) fetch that says "I have all major
    v3 releases and want all major v4 releases." The "large" case included
    X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate
    tags to the set, which does not greatly increase the number of objects
    that are considered, but does increase the number of 'from' commits,
    demonstrating the quadratic nature of the previous code.
    Small Case:
    Before: 1.52 s
     After: 0.26 s
    Large Case:
    Before: 3.50 s
     After: 0.27 s
    Note how the time increases between the two cases in the two versions.
    The new code increases relative to the number of commits that need to be
    walked, but not directly relative to the number of 'from' commits.
    Signed-off-by: 's avatarDerrick Stolee <dstolee@microsoft.com>
    Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
commit-reach.h 2.6 KB