Re: RFC: New diff-delta.c implementation

On Mon, 24 Apr 2006, Geert Bosch wrote:

> On Mon, Apr 24, 2006 at 01:27:07AM -0400, Nicolas Pitre wrote:
> > Please just completely drop that word fetch "optimization".  Not only 
> > does it produce worse assembly code in the end due to the extra loop 
> > counter and extra shifting in turn increasing register pressure, but it 
> > also assumes that the target data buffer is always word aligned which is 
> > not guaranteed (casting a char pointer to an unsigned and dereferencing 
> > it is not portable since on some architecture such misaligned accesses 
> > are not allowed).  And it even has worse performance.  For example, with 
> > word fetch and shift code, packing the Linux kernel archive on my P4 at 
> > 3GHz:
> 
> > user    6m33.797s
> [vs.]
> > user    6m13.911s
> > So you must be extremely careful when trying to implement such kind of 
> > optimizations.
> 
> As a compiler writer, I am more than aware of this. 
> Your change results in a 70% slowdown on PowerPC.

Huh!?

> On many targets
> byte-accesses are relatively slow. Indeed, I had expect this to be
> mostly neutral on x86, and the 5% slowdown you saw is not unexpected.

FWIW I'd expect a slowdown on ARM as well but I didn't bench it.

> Note that in this case aligned accesses are guaranteed, because the
> index_step is guaranteed to be a multiple of the word size.

Sure, but the data buffers aren't necessarily so.  At least some code to 
align index_step with actual memory offset if necessary should be 
considered.

> > But here comes the sad part.  Even after simplifying the code as much as 
> > I could, performance is still significantly worse than the current 
> > diff-delta.c code.  Repacking again the same Linux kernel repository 
> > with the current code:
> That's unexpected, but I can see how this could be if most files have
> very few differences and are relatively small. For such cases, almost
> any hash will do, and the more complicated hashing will be more compute
> intensive.
> 
> 
> I have benchmarked my original diff code on a set of large files with
> lots of changes. These are hardest to get right, and hardest to get
> good performance with. Just try diffing any two large (uncompressed)
> tar files, and you'll see. On many of such large files, the new code
> is orders of magnitude faster. On these cases, the resulting deltas
> are also much smaller.
> 
> The comparison is a bit between a O(n^2) sort that is fast on small
> or mostly sorted inputs (but horrible on large ones) and a more
> complex O(nlogn) algorithm that is a bit slower for the simple
> cases, but far faster for more complex cases.

Indeed.  And since the primary goal for GIT is to manage relatively 
small files with relatively few differences then we have to optimize for 
that case while trying to simply limit the dammage in the other cases.

> > In the mean time I'll try replacing the adler32 hashing with your Rabin 
> > polynomial hashing into the current code just to see if it helps (and I 
> > think it will help quite a bit).  The best solution might be a mix of 
> > both approaches.
> I think the most interesting part of my code is in process_copies.
> This optimization results in elimination of about half the commands
> in large test cases, while taking virtually no time at all.

Yes, I found that part really nice and clever.

> Also, I believe that any form of hash chaining of secondary hashing
> is useless. I have done many benchmarks, and in all cases a slight
> increase of hash table size was both more effective for pack size and
> faster due to less cache misses.

Well, I did lots of benchmarks too over the Linux kernel repository 
with the current code.  It is of course a dataset quite different from 
two large files.  And simply increasing the hash size to improve on pack 
size did increase CPU usage quite significantly.

> PS. Somehow your code had "double line spacing" :)

Gah.  Your original version must have CRLF line terminations, and vi 
simply notice that and writes the file back with CRLF by default.  Find 
attached a version with those converted to LF only.


Nicolas

-
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