Re: git annotate runs out of memory

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Dec 12, 2007, 02:10 UTC
Message-ID: <alpine.LFD.0.9999.0712111806320.25032@woody.linux-foundation.org>
In-Reply-To: <Pine.LNX.4.64.0712111653520.1671@alien.or.mcafeemobile.com>

On Tue, 11 Dec 2007, Davide Libenzi wrote:

Show 10 quoted lines

>
> > That's not the problem. The problem with xdl_trim_ends() is that it 
> > happens *after* you have done all the hashing, so as an optimization it's 
> > fairly useless, because it still leaves the real cost (the per-line 
> > hashing) on the table.
> 
> Careful. The real cost of diffing, is not the O(1) pass of the prepare 
> phase. It's the potentially O(N*M) worst case of the cross-record compare. 
> So that optimization is far from useless. That optimization is indeed 
> mainly targeted to avoid such worst case.

I'm not saying it's useless. I'm saying it's ineffective.

My simple patch that you saw, speeded up a real-life case by A FACTOR OF THREE. We're not talking small potatoes here.

> Also, you'd need some code at the end that hands you back at least the N 
> lines you want for context.

Sure. The special case I added it to specifically wanted a context of zero in the caller, so I could just ignore that.

But doing this in general and handing back the context is a simple matter of

	while (size < orig && context_lines) {
		if (src->buffer[size++] == '\n')
			context_lines--;
	}

which will usually hit in a really short time (ie three lines by default, 
just a few tens of bytes).
			
		Linus