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

[Bernhard Leiner]

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.

I will do some more profiling and will send a new version of my patch
in the next days...

-- 
Bernhard Leiner           http://bernh.net