On Thu, 14 Aug 2008, Linus Torvalds wrote:

quoted text
> Btw, it's not that hard to run oprofile (link git statically to get better 
> numbers). For me, the answer to what is going on for a kernel rev-list is 
> pretty straightforward:
> 
> 	263742   26.6009  lookup_object
> 	135945   13.7113  inflate
> 	110525   11.1475  inflate_fast
> 	75124     7.5770  inflate_table
> 	64676     6.5232  strlen
> 	48635     4.9053  memcpy
> 	47744     4.8154  find_pack_entry_one
> 	35265     3.5568  _int_malloc
> 	31579     3.1850  decode_tree_entry
> 	28388     2.8632  adler32
> 	19441     1.9608  process_tree
> 	10398     1.0487  patch_delta
> 	8925      0.9002  _int_free
> 	..

OK, inflate went down since last time I profiled this, but that's 
probably because lookup_object went up.

quoted text
> so most of it is in inflate,

Which, again, would be eliminated entirely by pack v4.

quoted text
> but I suspect the cost of "lookup_object()" 
> is so high becuase when we parse the trees we also have to look up every 
> blob - even if they didn't change - just to see whether we already saw it 
> or not.

One optimization with pack v4 was to have delta chunks aligned on tree 
records, and because tree objects are no longer compressed, parsing a 
tree object could be done by simply walking the delta chain directly.  
Then, another optimization would consist of simply skipping any part of 
a tree object making a delta reference to a base object which has 
already been parsed which would avoid a large bunch of lookup_object() 
calls too.

And because 
delta base objects are normally seen first in recency order then this 
would reduce the combinatorial complexity significantly.


Nicolas
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html