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

From: Shawn O. Pearce <spearce@spearce.org>
Date: Dec 31, 2006, 05:47 UTC
Message-ID: <20061231054741.GA6106@spearce.org>
In-Reply-To: <7vejqgk4l1.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano <junkio@cox.net> wrote:

Show 14 quoted lines

> Shawn Pearce <spearce@spearce.org> 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.