Re: Serious performance regression in diff between 1.6.6 and 1.7.0

[Brian Downing <bdowning@lavos.net>]

On Thu, Jun 10, 2010 at 12:08:04PM -0500, Brian Downing wrote:
> I also ran this through callgrind to see how often the above were called:

(187,456 files)

>         Calls  Symbol
>   -----------  -------------------
>       197,958  unpack_callback
>       208,460  find_cache_pos
>    37,308,336  ce_in_traverse_path
>   156,950,469  do_compare_entry
>   156,950,469  df_name_compare

Here is an identical run (git-diff HEAD) from the Linux kernel tree
(33,307 files):

        Calls  Symbol
   -----------  -------------------
        35,332  unpack_callback
        37,357  find_cache_pos
     4,979,473  ce_in_traverse_path
     6,828,181  do_compare_entry
     6,828,181  df_name_compare

That makes it look sort of exponential (perhaps around files^1.5),
though from what I can understand of the find_cache_pos code in
unpack-trees it would depend on the exact shape of the repository.  It
does seem to linear-search over whole directory trees of the index
repeatedly, though, which would support the exponential theory.

Unfortunately I don't really understand what the code is trying to do.
Is it not the case that trees and the index are always stored sorted in
the same order?  The examples given in the commit messages that
introduced this fix would imply not, but I'm not sure how that could
come about.

-bcd