From: Junio C Hamano <gitster@pobox.com>
Date: Mon, 08 Jul 2013 16:12:37 GMT
Subject: Re: [PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs
Message-ID: <7vmwpx1156.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1373273919-32005-1-git-send-email-drafnel@gmail.com>

Brandon Casey <drafnel@gmail.com> writes:

> ...
> Using an index takes 41 ms longer, or roughly 7.8% longer.
>
> Jeff King measured a no-op push of a single ref into a remote repo
> with 370,000 refs:
>
>         before    after
> real    0m1.087s  0m1.156s
> user    0m1.344s  0m1.412s
> sys     0m0.288s  0m0.284s
>
> Using an index takes 69 ms longer, or roughly 6.3% longer.
>
> None of the measurements above required transferring any objects to
> the remote repository.  If the push required transferring objects and
> updating the refs in the remote repository, the impact of preparing
> the search index would be even smaller.
>
> A similar operation is performed in the reverse direction when pruning
> using a matching or pattern refspec.  Let's avoid O(m*n) behavior in
> the same way by lazily preparing an index on the local refs.

Thanks.  Both the explanation and the code change makes sense to me.

Will queue.