Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)

[Jeff King <peff@peff.net>]

On Mon, May 21, 2012 at 07:52:19PM -0400, Jeff King wrote:

> Try doing "git fetch . refs/*:refs/*" in a repository with a large
> number of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on
> my machine. But using the version of git in "next" takes about 16.5s.
> Bisection points to your 432ad41 (refs: store references hierarchically,
> 2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.

A few more facts:

  - I usually compile with -O0 because I am debugging so frequently.
    With -O3, those numbers become 6.0s and 11.2s, respectively. Much
    faster, but there is still a performance regression.

  - Almost all of the refs are packed. IIRC, the packed-refs file should
    already be sorted. I wonder if we did not bother double-checking
    that before your patch, and now we do. That could explain the
    difference.

  - I don't compile with INTERNAL_QSORT. So mentioning msort_with_tmp is
    slightly confusing, as it is actually the version from libc, not
    ours IOW, it is really just qsort. But the primary culprit remains
    sort_ref_dir.

-Peff