Re: [RFC] Cache negative delta pairs

[Jeff King <peff@peff.net>]

On Wed, Jun 28, 2006 at 08:09:43PM -0700, Junio C Hamano wrote:

> that hit your the negative cache are?  That is, in find_deltas()
> function, we have "while (--j > 0)" loop that attempts to delta
> with the entry that is j (modulo window size) entries away from
> the current one, then j-1, j-2, ...; I am interested in the
> distribution of "j" value for the pair "n,m" that hits your
> negative cache for normal repositories, and I am speculating
> that the value would probably be small relative to the delta
> window size.

Just to make sure I am understanding you correctly, you're interested in
the distribution of 'j' each time we skip a delta for being negative
(or each time we mark a negative, but that should simply equal the
lookup times for the next run). The instrumentation I added simply
prints the value of j each time we skip a delta. The counts are
surprisingly uniform (this is for linux-2.6):
  57209 j=1
  57213 j=2
  57217 j=3
  57221 j=4
  57225 j=5
  57229 j=6
  57233 j=7
  57237 j=8
  57241 j=9
  57245 j=10
They're so uniform (and in order by j!) that I feel like I must have done
something wrong...

-Peff