Re: pack operation is thrashing my server

On Thu, 14 Aug 2008, Linus Torvalds wrote:

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.

so most of it is in inflate,

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

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