Use locate to return a sequence of (directory, dotdir) pairs.

def find_repositories_with_locate(path):
    """Use locate to return a sequence of (directory, dotdir) pairs."""
    command = [b'locate', b'-0']
    for dotdir in DOTDIRS:
        # Escaping the slash (using '\/' rather than '/') is an
        # important signal to locate(1) that these glob patterns are
        # supposed to match the full path, so that things like
        # '.hgignore' files do not show up in the result.
        command.append(br'%s\/%s' % (escape(path), escape(dotdir)))
        command.append(br'%s\/*/%s' % (escape(path), escape(dotdir)))
    try:
        paths = check_output(command).strip(b'\0').split(b'\0')
    except CalledProcessError:
        return []
    return [os.path.split(p) for p in paths
            if not os.path.islink(p) and os.path.isdir(p)]