On Thu, 14 Aug 2008, Linus Torvalds wrote:
> Btw, it's not that hard to run oprofile (link git statically to get better

quoted text
> 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()"

quoted text
> 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