Re: [PATCH] diff-delta: produce optimal pack data

From: Linus Torvalds <torvalds@osdl.org>
Date: Feb 25, 2006, 19:18 UTC
Message-ID: <Pine.LNX.4.64.0602251114070.22647@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0602242326381.31162@localhost.localdomain>

On Sat, 25 Feb 2006, Nicolas Pitre wrote:

> 
> Yes, the hash is larger.  There is a cost in memory usage but not really 
> in CPU cycles.

Note that memory usage translates almost 1:1 (or worse) to CPU cycles in almost all real-life behaviours. Only in carefully tuned benchmarks does it not.

Increased memory usage means more paging, and worse cache behaviour. Now, hashes aren't wonderful for caches in the first place, but imagine the hump you pass when the data doesn't fit in a 64kB L1 any more (or a 256kB L2). Huge.

Show 7 quoted lines

> > You'll find a lot of that in any file: three or four bytes of similarity 
> > just doesn't sound worthwhile to go digging after. 
> 
> Well after having experimented a lot with multiple parameters I think 
> they are worth it after all.  Not only they provide for optimal deltas, 
> but their hash is faster to compute than larger blocks which seems to 
> counter balance for the cost of increased hash list.

Hey, numbers talk. If you've got the numbers, I'll just shut up ;)

		Linus