Re: Re-organize "git-rev-list --objects" logic

On Fri, 16 Sep 2005, Johannes Schindelin wrote:

On Thu, 15 Sep 2005, Linus Torvalds wrote:

quoted

I know how to make it use _lots_ less memory, which will probably speed it 
up. But that's for another time, and I'd prefer to see this go in first.

Mind to elaborate just a bit?

Right now we keep track of every single object we parse, and never free 
it.

Some of it is necessary to keep track of whether a SHA has been seen or
not, but: we also keep every single relation list around. They're small,
but they are _many_. We can trivially free those after following them.
That should get us back another few tens of megabytes easily. It's the
parent pointers, and the "struct tree_entry" lists.

Now, some memory usage is very fundamental, and we can't get rid of the
"struct object" for each thing we've listed (or each thing we've
determined needs to be pruned). We can perhaps shrink it some, but we'll
always need to have at a minimum the 20-byte sha1 of every object. So if
we list/blacklist a hundred thousand objects, there's no way we can avoid
using a couple of megs just to keep track of that fact in order to avoid
duplicates.

However, I _think_ the majority of the memory use is in the refs. Even a 
full kernel tree only has about 95,000 objects, but we have many _many_ 
more of these relationship links. We've got ~9,000 commits, and pretty 
much each of them will have a different root tree with 20+ entries in it, 
and even when most of them end up pointing to the same blobs/trees (which 
is why we only have 95,000 objects - there's _tons_ of sharing), they'll 
all end up generating a "tree_entry" thing. So just there, you'll have 
something like 180,000 small allocations.

And yes, a "tree_entry" is smaller than a "struct object" or "struct
tree", but with twice as many "struct tree_entries" as there are objects
in _total_, that sure adds up pretty quickly.

And the refs. git-fsck-cache needs to be able to look through the 
dependency chains for all objects. git-rev-list doesn't. Again, they're 
small, but they're all over.

So I suspect half the memory allocations is just for these things. Maybe 
I'm overly optimistic. But I think that even without shrinking the object 
structures themselves, we should be able to make git-rev-list use a lot 
less memory.

			Linus