Performance of Python builtins

[miller.paul.w]

Is there any place outside the actual C source for Python that has
information about the performance of Python's built-in operations? For
example, I'd *expect* list.append to be O(1), and I hope that list
is O(1), but I don't really know that for sure, since it would depend
a lot on the internal implementation.

I'm really only asking this for curiosity's sake --- more as a
reasonable, non-trollish version of the "Python is slow" post than
anything. I've never really had any problems with the performance
of Python code that I couldn't solve by either changing my algorithm
or, if all else has truly failed, rewriting in C or Pyrex.

What I'd like to see is something like http://svn.python.org/projects/python/trunk/Objects/listsort.txt
where Python's sorting algorithm is described, except with the focus
on other built-in constructs.

Thanks!

 

[Paul Rubin]

Is there any place outside the actual C source for Python that has
information about the performance of Python's built-in operations?

Really, just the source code and the general culture. It's not in the
docs; that would be a pretty rare thing.

For example, I'd *expect* list.append to be O(1), and I hope that
list is O(1), but I don't really know that for sure, since it
would depend a lot on the internal implementation.

list is O(1). list.append is amortized O(1) but on some calls can
take much longer. Basically list.append preallocates some extra space
for further appends but when you use up the extra space there is some
copying.

I'm really only asking this for curiosity's sake --- more as a
reasonable, non-trollish version of the "Python is slow" post than
anything. I've never really had any problems with the performance
of Python code that I couldn't solve by either changing my algorithm
or, if all else has truly failed, rewriting in C or Pyrex.

"You can fix your Python program's performance problems by rewriting
it in C" is not that convincing an answer to a concern that Python is
slow ;-).

 

[miller.paul.w]

(e-mail address removed) writes:

Thanks for your reply. I guess I'll have to go source diving to truly
answer the question.

"You can fix your Python program's performance problems by rewriting
it in C" is not that convincing an answer to a concern that Python is
slow ;-).

Wasn't meant to be. But, it is a credit to Guido that, beyond the
pain inherent in coding in C, there's relatively little pain involved
in writing an extension module.

 

[Terry Reedy]

| Is there any place outside the actual C source for Python that has
| information about the performance of Python's built-in operations?

Unfortunately no. Guido does not want to put guarantees in the language
definition, so there is no urgency to document this. An auxiliary doc
might be accepted. But the people who could write such a thing are busy
doing otherwise. Certainly, no one has volunteered to write *and update*
such.

 

[miller.paul.w]

| Is there any place outside the actual C source for Python that has
| information about the performance of Python's built-in operations?

Unfortunately no.  Guido does not want to put guarantees in the language
definition, so there is no urgency to document this.  An auxiliary doc
might be accepted.  But the people who could write such a thing are busy
doing otherwise.  Certainly, no one has volunteered to write *and update*
such.

I see. Just to be clear, though, I wasn't looking for "guarantees" as
such, like (I believe) the STL sometimes provides. I was just looking
for some idea of what current implementations' performance
characteristics are.

I suppose I could probably create such a resource. Keeping it updated
would be another thing entirely, since I don't really want to monitor
every single commit to Python's svn repository. Hypothetically, if
someone made such a document, do you think it could be arranged for
that person to be notified whenever CPython's implementation changes
to invalidate it?

 

[Benjamin]

Is there any place outside the actual C source for Python that has
information about the performance of Python's built-in operations? For
example, I'd *expect* list.append to be O(1), and I hope that list
is O(1), but I don't really know that for sure, since it would depend
a lot on the internal implementation.

I'm really only asking this for curiosity's sake --- more as a
reasonable, non-trollish version of the "Python is slow" post than
anything. I've never really had any problems with the performance
of Python code that I couldn't solve by either changing my algorithm
or, if all else has truly failed, rewriting in C or Pyrex.

What I'd like to see is something likehttp://svn.python.org/projects/python/trunk/Objects/listsort.txt
where Python's sorting algorithm is described, except with the focus
on other built-in constructs.

http://wiki.python.org/moin/TimeComplexity is a start.

 

[miller.paul.w]

http://wiki.python.org/moin/TimeComplexityis a start.

Awesome. That's pretty much what I was after!