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

[Martin Geisler]

Sune Foldager <cryo at cyanite.org> writes:

>> On Sat, 2008-10-11 at 19:00 +0200, Bernhard Leiner wrote:
>>>
>>> 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).
>
> This is, on the other hand, rather bad news (for python)... why on
> earth would't list append be implemented to run O(1)?? :-(

Python lists are arrays with pointers to the objects and they ought to
have amortized O(1) append behaviour. There are some notes here:

  http://effbot.org/zone/python-list.htm#performance

If you need an efficient prepend operation, then a deque (Python 2.4) is
your friend:

  http://www.python.org/doc/2.4/lib/module-collections.html

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://lists.mercurial-scm.org/pipermail/mercurial-devel/attachments/20081012/3c40fbb9/attachment.asc>