Re: Start handling references internally as a sorted in-memory list

From: Linus Torvalds <torvalds@osdl.org>
Date: Sep 12, 2006, 01:05 UTC
Message-ID: <Pine.LNX.4.64.0609111800590.27779@g5.osdl.org>
In-Reply-To: <7vsliyez2m.fsf@assigned-by-dhcp.cox.net>

On Mon, 11 Sep 2006, Junio C Hamano wrote:

> 
> I thought what triggered the restructuring of this part was N
> actually being large enough to cause pain to some people, so I
> suspect later might need to be reasonably soon ;-).

Well, the current problems is actually related to the _IO_ load of O(n) (and to some degree the disk usage), and that is indeed fairly high. The new O(n**2) is all for a (very) simple CPU loop, so I suspect "n" has to be in the millions before it even approaches the IO load problem ;)

> I've been wondering what happens if you pack "refs/heads/foo",
> delete it, and create "refs/heads/foo/bar" with your proposal.
> I'll find the answer (which is _not_ "42") in the updated
> do_for_each_ref(), I guess.

Right now, the code in question only contains some preliminary support for refs at all, and it's technically incorrect. If you ever have a "packed-refs" file that contains _anything_ outside of the actual loose refs, it won't do the right thing.

But I'd rather have this as a base, than send one huge patch that does everything.

For example, right now the code doesn't support negative refs (even the simple kind) at all, so you don't need to even have the "file turned into a directory" case for it to "not work".

So right now it's basically just scaffolding. It's hopefully _good_ scaffolding, so that when I send the next few patches, it actually starts working.. ;)

		Linus