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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html