On Thu, 14 Aug 2008, Linus Torvalds wrote:

quoted text
>

> Doing a rev-list of all objects is a fairly rare operation, but even if

> you want to clone/repack all of your archives the whole time, please

> realize that listing objects is _not_ a simple operation. It opens up and

> parses every single tree in the whole history. That's a _lot_ of data to

> unpack.

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

	..
so most of it is in inflate, 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.
For me, an instruction-level profile of lookup_object() shows that the

cost is all in the hashcmp (53% of the profile is on that "repz cmpsb")

and in the loading of the object pointer (26% of the profile is on the

test instruction after the "obj_hash[i]" load). I don't think we can

really improve that code much - the hash table is very efficient, and the

cost is just in the fact that we have a lot of meory accesses.
We could try to use the (more memory-hungry) "hash.c" implementation for

object hashing, which actually includes a 32-bit key inside the hash

table, but while that will avoid the cost of fetching the object pointer

for the cases where we have collisions, most of the time the cost is not

in the collision, but in the fact that we _hit_.
I bet the hit percentage is 90+%, and the cost really is just that we

encounter the same object hundreds or thousands of times.
Please realize that even if there may be "only" a million objects in the

kernel, there are *MANY* more ways to _reach_ those objects, and that is

what git-rev-list --objects does! It's not O(number-of-objects), it's

O(number-of-object-linkages).
For my current kernel archive, for example, the number of objects is

roughly 900k. However, think about how many times we'll actually reach a

blob: that's roughly (blobs per commit)*(number of commits), which can be

approximated with
	echo $(( $(git ls-files | wc -l) * $(git rev-list --all | wc -l) ))
which is 24324*108518=2639591832 ie about 2.5 _billion_ times.
Now, we don't actually do anything close to that many lookups, because

when a subdirectory doesn't change at all, we'll skip the whole tree after

having seen it just once, so that will cut down on the number of objects

we have to look up by probably a couple of orders of magnitude.
But this is why the "one large directory" load performs worse: in the

worst case, if you really have a totally flat directory tree, you'd

literally see that 2.5 billion object lookup case.
So it's not that git scales badly. It's that "git rev-list --objects" is

really a very expensive operation, and while some good practices (deep

directory structures) makes it able to optimize the load away a lot, it's

still potentially very tough.
			Linus

--

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