Re: git annotate runs out of memory
- From
- Davide Libenzi <davidel@xmailserver.org>
- Date
- Dec 12, 2007, 01:12 UTC
- Message-ID
- <Pine.LNX.4.64.0712111653520.1671@alien.or.mcafeemobile.com>
- In-Reply-To
- <alpine.LFD.0.9999.0712111648180.25032@woody.linux-foundation.org>
On Tue, 11 Dec 2007, Linus Torvalds wrote:
Show 7 quoted lines
> > Libxdiff already has a xdl_trim_ends() that strips all the common > > beginning and ending records, but at that point files are already loaded. > > 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.
> So doing the trimming of the ends before you do even that, allows you to > just do the trivial "let's see if the ends are identical" with a plain > memcmp, which is much faster.
Yes, tail trimming done on a block-basis is faster and does not consume memory. The code for libxdiff would have to be a bit more complex though, since memory files can be composed by many sections, of different sizes (so you cannot just assume it's a single block you're trimming the end). Also, you'd need some code at the end that hands you back at least the N lines you want for context.
- Davide