Re: pack operation is thrashing my server

From: Nicolas Pitre <nico@cam.org>
Date: Aug 14, 2008, 19:04 UTC
Message-ID: <alpine.LFD.1.10.0808141442150.4352@xanadu.home>
In-Reply-To: <alpine.LFD.1.10.0808141022500.3324@nehalem.linux-foundation.org>

On Thu, 14 Aug 2008, Linus Torvalds wrote:

Show 18 quoted lines

> 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