• Patrick Reynolds's avatar
    use a hashmap to make remotes faster · d0da003d
    Patrick Reynolds authored
    Remotes are stored as an array, so looking one up or adding one without
    duplication is an O(n) operation.  Reading an entire config file full of
    remotes is O(n^2) in the number of remotes.  For a repository with tens of
    thousands of remotes, the running time can hit multiple minutes.
    
    Hash tables are way faster.  So we add a hashmap from remote name to
    struct remote and use it for all lookups.  The time to add a new remote to
    a repo that already has 50,000 remotes drops from ~2 minutes to < 1
    second.
    
    We retain the old array of remotes so iterators proceed in config-file
    order.
    Signed-off-by: default avatarPatrick Reynolds <patrick.reynolds@github.com>
    Reviewed-by: default avatarJeff King <peff@peff.net>
    Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
    d0da003d
remote.h 7.11 KB