[PATCH 0 of 3] Fast implemenation of parseindex in C

[Matt Mackall]

On Sat, 2008-10-11 at 19:00 +0200, Bernhard Leiner wrote:
> 2008/10/10 Benoit Boissinot <bboissin at gmail.com>:
> > On Fri, Oct 10, 2008 at 6:34 PM, Bernhard Leiner
> >> It looks like the speedup for small to medium size index files is
> >> about 5 - 6 (like Matt expected/hoped) but the speedup gets lower when
> >> the file gets bigger.
> >>
> >> And so far I have no explanation why.
> >
> > Did you try running it with valgrind --tool=callgrind (and kcachegrind
> > to visualize the data) ?
> >
> > Maybe that would help figuring out what to problem is.
> 
> Thanks a lot for this hint. I figured out that the reason for the
> slowdown with big index files: The Python list append function does
> not scale in O(1) but something in the area of O(n).
> 
> Since for large indexes with no inlined data the number of entries is
> known in advance it is possible to create the index list with the
> correct size in advance and just use PyList_SET_ITEM (which runs in
> O(1)) afterwards. I have now a speedsup of about 6 also for very large
> indexes.

Great news.

-- 
Mathematics is the supreme nostalgia of our time.