[PATCH] revised manifest speedups

[Chris Mason]

On Fri, 26 Aug 2005 11:52:50 -0700
Matt Mackall <mpm at selenic.com> wrote:

> On Wed, Aug 24, 2005 at 11:04:36AM -0400, Chris Mason wrote:
> > Hello everyone,
> > 
> > Last night I reworked my latest manifest speedups to use the python
> > array type instead of my nlbuf extension.  I think the code is much
> > less complex now, and this patch is only 3 or 4 seconds slower than
> > my C extension was.
> > 
> > The algorithm is still based on bisect.  The basic idea is to
> > forget about maintaining a line based representation of the
> > manifest and store it all in a big char array.  The manifestsearch
> > function does the heavy lifting of finding offsets into the buffer
> > for delta generation.
> 
> Does your bisection remember where the last insert/delete was and
> narrow the search?

Yes, the start of the last match is passed as the starting point for
the next search.

> Do you sort the insert/delete list?

The only sorting done is at the very beginning, I sort the list of
files that have changed.  This part is the same as without the patch.
Since I search in sorted order, the results come out in sorted order.

>  
> > This has been through light testing here.  Matt, if it seems
> > reasonable, I'll hammer on it.
> 
> Looks promising. I'll probably want the compress bit separately.
> 

Not impossible, but twice the QA for me.  Unless you just want it to
help make the search changes easier to read (ie, you don't want to
apply just one of them, and I don't have to hammer on just the
compression bits).

-chris