• Junio C Hamano's avatar
    sha1-lookup: make selection of 'middle' less aggressive · 12ecb011
    Junio C Hamano authored
    If we pick 'mi' between 'lo' and 'hi' at 50%, which was what the
    simple binary search did, we are halving the search space
    whether the entry at 'mi' is lower or higher than the target.
    The previous patch was about picking not the middle but closer
    to 'hi', when we know the target is a lot closer to 'hi' than it
    is to 'lo'.  However, if it turns out that the entry at 'mi' is
    higher than the target, we would end up reducing the search
    space only by the difference between 'mi' and 'hi' (which by
    definition is less than 50% --- that was the whole point of not
    using the simple binary search), which made the search less
    efficient.  And the risk of overshooting becomes very high, if
    we try to be too precise.
    This tweaks the selection of 'mi' to be a bit closer to the
    middle than we would otherwise pick to avoid the problem.
    Signed-off-by: default avatarJunio C Hamano <[email protected]>
sha1-lookup.c 5.19 KB