Subject: Re: [PATCH 1/2] Teach Git how to parse standard power of 2 suffixes.

From: "Shawn O. Pearce" <[email-masked]>
Date: Sun, 31 Dec 2006 00:47:41 -0500

Junio C Hamano <[email-masked]> wrote:
> Shawn Pearce <[email-masked]> writes:
> 
> > So in your test case where you thought you entered 20 pages, what you
> > really had was just 2 pages.  We rounded 20 bytes down to 0 pages,
> > then forced that to a minimum of 2 pages.  :-)
> 
> Yes.
> 
> And I found something else that is interesting.  I still had 2
> pages windows but reduced packedgitlimit to 256kB and re-run the
> same test to reproduce all merges in git.git.  It still did not
> fail, but it took even shorter wallclock time (again, it is only
> 3 seconds or so out of 5 1/2 minuts, so it is probably
> statistically insignificant).

Its possible the packed_git.windows list is hurting us here.
Its O(n) to locate a given window.  The larger the ratio between
packedGitWindowSize and packedGitLimit the longer that list can get,
and the longer it can take to locate a window.

Maybe that should be a simple red-black tree?

More testing probably needs to be done though.

-- 
Shawn.