473,888 Members | 2,213 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Python is faster than C

Hi!

This is a rant against the optimization trend of the Python interpreter.

Sorting a list of 100000 integers in random order takes:

* 0.75 seconds in Python 2.1
* 0.51 seconds in Python 2.2
* 0.46 seconds in Python 2.3

Tim Peters did a great job optimizing list.sort(). If I try with a
simple, non-stable pure Python quicksort implementation, in Python 2.3:

* 4.83 seconds
* 0.21 seconds with Psyco

First step towards world domination of high-level languages :-)

The reason that Psyco manages to outperform the C implementation is not
that gcc is a bad compiler (it is about 10 times better than Psyco's).
The reason is that the C implementation must use a generic '<' operator
to compare elements, while the Psyco version quickly figures out that it
can expect to find ints in the list; it still has to check this
assumption, but this is cheap and then the comparison is done with a
single machine instruction.

Similarily, here are some results about the heapq module, which is
rewritten in C in the CVS tree for Python 2.4:

l = [random.random() for x in range(200000)]
heapq.heapify(l )

This code executes on my laptop in:

* 1.96 seconds on Python 2.3 (pure Python)
* 0.18 seconds on Python 2.4cvs (rewritten in C)
* 0.16 seconds on Python 2.3 with Psyco

So this is not so much a plug for Psyco as a rant against the current
trend of rewriting standard modules in C. Premature optimization and
all that.

Worse, and more importantly, the optimization starts to become visible
to the programmer. Iterators, for example, are great in limited cases
but I consider their introduction a significant complication in the
language; before, you could expect that some function from which you
would expect a sequence returned a list. Python was all lists and
dicts, with dicts used as namespaces here and there. Nowadays you have
to be careful. Moreover, it is harder to explain:
zip([1,2,3], [4,5,6]) # easy to understand and explain [(1, 4), (2, 5), (3, 6)]
enumerate([6,7,8,9]) # uh ?

<enumerate object at 0x401a102c>

I know you can always do list(_). My point is that this is a
user-visible optimization. enumerate() should return a normal list, and
it should be someone else's job to ensure that it is correctly optimized
away if possible (and I'm not even talking about Psyco, it could be done
in the current Python implementation with a reasonable amount of
effort).
Protesting-ly yours,

Armin
Jul 18 '05
36 2680
Hi !

Yes, but Psyco is writted in C & Python, and it use an C module.
Said "Psyco is faster than C", it's like said "Psyco is faster than Psyco".

@-salutations (and sorry for my *bad english*)
--
Michel Claveau

Jul 18 '05 #21
Hi !

Sorry, but i had let down C language. I can't compare.
See also my answer to Josiah Carlson.

And Psyco is sufficiently good not to need ambiguous arguments.

@-salutations
--
Michel Claveau


Jul 18 '05 #22
from pprint import *
def install_hook():
def displayhook(v):
import __main__
if v is not None:
if isiterator(v):
print "<%s object at 0x%8x:" % (
type(v).__name_ _, id(v)),
v, copy = itertools.tee(v )
for elem in itertools.islic e(copy, 3):
print saferepr(elem),
try:
copy.next()
except StopIteration:
pass
else:
print '...',
sys.stdout.soft space=0
print ">"
else:
pprint(v)
__main__._ = v

sys.displayhook = displayhook

Jeff

Jul 18 '05 #23
Armin Rigo:
Another example would be 'a'*999999999: the result is a string, but
there is no reason that it takes 100MB of memory. Instead, store it
into a C structure that contains a pointer to the original string object
'a' and the repetition counter, but still give this C structure the
Python type str, so that the difference doesn't show up and the Python
language remains simple.


I've written lazy code like this for my own projects, where the
concrete object wasn't fully created until needed. One of the
problems I had with it was error behaviour. In this case, suppose
there isn't enough memory available. Python as is will attempt to
allocate enough space when you request it and raise a MemoryError
if there isn't enough space.

Python as you propose it may allocate the string-like object and
only later (eg, when passing the object to some external C
function which expects a char *) realize the full string. There
isn't enough memory so the allocation fails, raising a MemoryError.
But how is the programmer to realize which operations may raise
a MemoryError? Instead, will everything need a try/except guard
around it?

Andrew
da***@dalkescie ntific.com
Jul 18 '05 #24
Armin Rigo <arigo <at> tunes.org> writes:
Again I'm not saying it is trivial to implement it, but that not having
to expose for optimization purposes 'xrange' and the whole 'iterator'
part of the language would be worth it, in my opinion.


First of all, I'm trying to see whether I can write through this interface.
As you might have realized, sarcastically after they fooled me with that
April joke, my site was really lost, andthis is a tad.

Anyway, I'd like to add that Armin's idea can be extended (as he surely knows)
to special casing seldom assignments to and algorithmically given array.
That is, in the case of just a few assignments, a list could internally
aufment the expression. If the number of elements grows, it could be
turned into a preferred dictionary, after reaching some threshold.
And after another threshold, it could be turned into something like
a real list, or just a specialized, typed list, depending on the type.

In general, I share Armin's impression, that iterators are nothing else
but an explicit way to spell optimizations.
While explicit is better than implicit, in the case of optimizations,
I believe it is an over-specification, and almost completely in the false
direction. We have to prove this in a known project, still.

There is one thing where I think explicit iterator do make some sense,
in a way the reader might not expect.
Let me show:

if you do something like

for each in sequence:
try:
do_something_wi th(each)
except SomeThingWrongW ithThis:
# handle exception somehow

In terms of iterators, we implicitly create an interator here and consume it.
The explicit notation of iterators gives us this advantage:

instead you can do it this way:

it = iter(sequence)
can_continue = 1
while can_continue:
try:
for each in it:
do_something_wi th(each)
exceptSomeThing WrongWithThis
can_continue = some_recovery(e ach)
continue

In words: By the help of iterators, it is possible to write exception
handlers for special cases *outside* the loop, repair the error, and
continue iterating in the loop.
I have used this pattern a lot of times now, and I'm quite happy ith it.

But I have to admit, that this is too a bad, explicit optimization, and
a compiler could be smart enough to do this for me, automatically.

cheers - chris

Jul 18 '05 #25
Raymond Hettinger wrote:


[Armin Rigo]
>>> enumerate([6,7,8,9]) # uh ?

<enumerate object at 0x401a102c>


This got me thinking about how much I would like to see the contents
of an iterator at the interactive prompt.

I wonder if the read-eval-print loop could be trained to make a better
display:

# rough pseudo-code sketch
while 1:
command = raw_input()
result = eval(command)
if result is None:
continue
if is_iterator(res ult):
result, copy = itertools.tee(r esult)
print "<%s object at 0x%8x:" %
(type(result)._ _name__, id(result)),
for elem in itertools.islic e(copy, 3):
print repr(elem),
else:
print '...',
print '>'
else:
print repr(result)
_ = result
# intended result
enumerate('abcd efgh') <enumerate object at 0x401a102c: (0, 'a') (1, 'b') (2, 'c') ...> list(_)

[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e'), (5, 'f'), (6, 'g'),
(7, 'h'), (8, 'i'), (9, 'j'), (10, 'k'), (11, 'l'), (12, 'm'), (13,
'n')]

I thought this myself, but what if the iterator is computationally
intensive?
--
CARL BANKS http://www.aerojockey.com/software
"If you believe in yourself, drink your school, stay on drugs, and
don't do milk, you can get work."
-- Parody of Mr. T from a Robert Smigel Cartoon
Jul 18 '05 #26
Armin Rigo wrote:
Paul Rubin wrote:
I think you're saying that instead of having xrange return a special
object, range should return that special object instead. I'm not too
clear on the distinction.


No, range should return an object that is a list, as far as you can tell
from Python, but which is represented more efficiently than an array of
objects internally. The distinction is between the language level (it
would be a list, with all operations, etc.) and the implementation
(there is no reason why all lists should be arrays of PyObjects
internally).

Another example would be 'a'*999999999: the result is a string, but
there is no reason that it takes 100MB of memory. Instead, store it
into a C structure that contains a pointer to the original string object
'a' and the repetition counter, but still give this C structure the
Python type str, so that the difference doesn't show up and the Python
language remains simple. (This is a bit difficult to implement
currently in CPython, but not impossible.)


Hmm. What would be really cool is an abstract sequence type with all
kinds of knobs to specify the operations you want to support. In
other words, rather than saying "I want a vector" or "I want a linked
list," you say, "I want fast indexing, fast sorting, no insertion, and
no resizing," or "I want no indexing, no sorting, fast insertion, fast
appending on both ends". Then, let the computer choose the actual
implementation.

Better yet, if the compilation is highly optimized, the compiler could
trace the path of the object (best as it can) through the program, and
maybe use profiling data too, to see for itself the how the object is
used, thus freeing the programmer from even specifying the operations.
The programmer could say, "I want a sequence," use it, and the
compiler could choose the best implementation.

The only thing is, I think that would be prohibitively difficult in an
on-the-fly compiled language like Python. Even having a list with one
or two optimized forms would have drawbacks: it would be hard to
optimize the fast parts with the interpretter second-guessing you all
the time, and it would be hard to write extension modules, since
they'd have to be aware of all the different layouts, or have to
always use an API.

And, frankly, I think having a simple implementation is important,
too. Complex implementations are more likely to have lots of bugs
that could burden users more than some distinct optimized types would.
In my opinion, Python is doing the right thing by having one internal
form per type.

Given that, and keeping in mind that some of these optimizations
really do help, the question to ask is: do the extra power and
efficiency the optimized version gives you justify the extra burden of
complexity on the programmer? I believe that the answer is
occasionally yes.

Consider tuples. Tuples are for the most part an optimized version
of list, but with a few powers list doesn't have, and without a few
powers list has. It's the same with iterators.

IMO, the the benefit an iterator gives you is far more than the
benefit a tuple gives you. I would say 'yes' for an iterator, it's
worth a bit of complexity; and probably 'no' for a tuple (although
it's close).
my-two-cents-ly y'rs,

--
CARL BANKS http://www.aerojockey.com/software
"If you believe in yourself, drink your school, stay on drugs, and
don't do milk, you can get work."
-- Parody of Mr. T from a Robert Smigel Cartoon
Jul 18 '05 #27
[Armin Rigo]
Armin> Worse, and more importantly, the optimization starts to
Armin> become visible to the programmer. Iterators, for example,
Armin> are great in limited cases but I consider their
Armin> introduction a significant complication in the language;
Armin> before, you could expect that some function from which you
Armin> would expect a sequence returned a list. Python was all
Armin> lists and
[Ville Vainio] Iterators are an optimization? I always considered them just a more
clean and elegant way to do the same thing :-).


In the planning discussions, optimization was not mentioned as goal.
In fact, I think everyone was surprised that they happened to run
faster than the __getitem__ hack. It was also a surprise at how much
they unified the language and made the various pieces work together a
little better.

The original goals were much smaller:
* less cumbersome file iteration (eliminating the need for xreadlines
and reducing the need for the fileinput module).
* providing an extensible interface
* making the code for non-sequence collections more concise and
readable

There was a thought that the performance of dictionary iteration would
improve. Also, while it was not discussed explicitly, everyone was
aware that iterators were more memory/cache friendly than their list
based counterparts.
Raymond Hettinger
Jul 18 '05 #28
[Jeff Epler]
from pprint import *
def install_hook():
def displayhook(v):
import __main__
if v is not None:
if isiterator(v):
print "<%s object at 0x%8x:" % (
type(v).__name_ _, id(v)),
v, copy = itertools.tee(v )
for elem in itertools.islic e(copy, 3):
print saferepr(elem),
try:
copy.next()
except StopIteration:
pass
else:
print '...',
sys.stdout.soft space=0
print ">"
else:
pprint(v)
__main__._ = v

sys.displayhook = displayhook


This is very nice.

In my sketch, I used Py2.4's itertools.tee() to handle non-restartable
iterators. For Py2.3, a good alternative is:

copy = list(itertools. islice(v, 3))
v = itertools.chain (copy, v)

Now, copy can be used in the display and "v" produces the same values
as the original iterator.
Cheers,

Raymond Hettinger
P.S. If some experimentation shows your code to be useful at the
interactive prompt, please submit a patch on SF so it won't be lost.
Jul 18 '05 #29
> >>>> enumerate('abcd efgh')
<enumerate object at 0x401a102c: (0, 'a') (1, 'b') (2, 'c') ...>
> list(_) [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e'), (5, 'f'), (6, 'g'),
(7, 'h'), (8, 'i'), (9, 'j'), (10, 'k'), (11, 'l'), (12, 'm'), (13,
'n')]


[Carl Banks] I thought this myself, but what if the iterator is computationally
intensive?


Since no more than three items are displayed, the interactive prompt
will still handle this much better than something like range(10000000)
which takes a while to compute and display.

Besides, everything you do in Python pays a little performance penalty
just to make sure you can break out of computationally intensive
tasks.

For me, these almost never arise at the interactive prompt.

Likewise, I program in a less hostile world than Andrew Dalke who has
to contend with pandora's box iterators which ruin the lives of mortal
men who think they can call .next() with impunity ;-)
Raymond Hettinger
Jul 18 '05 #30

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

49
2897
by: Ville Vainio | last post by:
I don't know if you have seen this before, but here goes: http://text.userlinux.com/white_paper.html There is a jab at Python, though, mentioning that Ruby is more "refined". -- Ville Vainio http://www.students.tut.fi/~vainio24
38
3760
by: kbass | last post by:
In different articles that I have read, persons have constantly eluded to the productivity gains of Python. One person stated that Python's productivity gain was 5 to 10 times over Java in some in some cases. The strange thing that I have noticed is that there were no examples of this productivity gain (i.e., projects, programs, etc.,...). Can someone give me some real life examples of productivity gains using Python as opposed other...
7
2074
by: stormslayer | last post by:
Folks: I've been considering a shift to python. I currently use c++builder (borland) or perl. I do computational models / statistics programming, and was interested in python b/c it a. has a library that connects to the R stats package b. has code that seems way more readable than anything else There is, however, at least for my work, a hard constraint. Execution
114
9923
by: Maurice LING | last post by:
This may be a dumb thing to ask, but besides the penalty for dynamic typing, is there any other real reasons that Python is slower than Java? maurice
68
5916
by: Lad | last post by:
Is anyone capable of providing Python advantages over PHP if there are any? Cheers, L.
9
4534
by: Dieter Vanderelst | last post by:
Dear all, I'm currently comparing Python versus Perl to use in a project that involved a lot of text processing. I'm trying to determine what the most efficient language would be for our purposes. I have to admit that, although I'm very familiar with Python, I'm complete Perl noob (and I hope to stay one) which is reflected in my questions. I know that the web offers a lot of resources on Python/Perl differences. But I couldn't find a...
118
6784
by: 63q2o4i02 | last post by:
Hi, I've been thinking about Python vs. Lisp. I've been learning Python the past few months and like it very much. A few years ago I had an AI class where we had to use Lisp, and I absolutely hated it, having learned C++ a few years prior. They didn't teach Lisp at all and instead expected us to learn on our own. I wasn't aware I had to uproot my thought process to "get" it and wound up feeling like a moron. In learning Python I've...
0
273
by: Kurt B. Kaiser | last post by:
Patch / Bug Summary ___________________ Patches : 419 open ( +3) / 3410 closed ( +2) / 3829 total ( +5) Bugs : 910 open (+12) / 6185 closed ( +5) / 7095 total (+17) RFE : 235 open ( +1) / 238 closed ( +0) / 473 total ( +1) New / Reopened Patches ______________________
0
1693
by: Kurt B. Kaiser | last post by:
Patch / Bug Summary ___________________ Patches : 420 open ( +4) / 3410 closed ( +2) / 3830 total ( +6) Bugs : 915 open (+17) / 6186 closed ( +6) / 7101 total (+23) RFE : 235 open ( +1) / 238 closed ( +0) / 473 total ( +1) New / Reopened Patches ______________________
23
2556
by: Python Maniac | last post by:
I am new to Python however I would like some feedback from those who know more about Python than I do at this time. def scrambleLine(line): s = '' for c in line: s += chr(ord(c) | 0x80) return s def descrambleLine(line):
0
9957
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, weíll explore What is ONU, What Is Router, ONU & Routerís main usage, and What is the difference between ONU and Router. Letís take a closer look ! Part I. Meaning of...
0
11173
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10772
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10878
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10434
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7143
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
6011
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4635
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
3245
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.