473,836 Members | 1,590 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 2664
> 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).
You can implement such a thing already. In fact, xrange up until
recently, supported basically everything that a list object did, except
for mutations. The reason it doesn't anymore is because for multiple
versions of Python, such behavior was buggy and poorly supported. If
you are bored enough, feel free to make your own xrange-like object that
supports mutation. Heck, it can even subclass 'list', though it need
not have any standard list internals.

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.)
Also, you are free to implement such a thing. I believe that the
current CPython implementation doesn't follow this route (and other
suggested optimizations) is because it needlessly complicates the
implementation of CPython.

Ideally: If you do x=range(100); x[50]='hi' then the interpreter first
builds this optimized range representation and assigns it to x; and when
in the next statement you modify this list x it says 'oops! i cannot do
that with this representation' , so it reverts to an array-like
representation (i.e. it creates all 100 elements) and then changes the
50th. No gain here. If on the other hand you only ever do 'easy'
things with your list, like iterate over it or read elements, then it
can all be done with the range representation, without falling back to
the array representation.
Why not instead use a dictionary-based approach for special items? It
would be far more memory efficient, and wouldn't incur the modification
penalty.

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.


I think that one of the desires of offering 'iterator' concepts to
users, both new and seasoned, is that it allows people to think in ways
they didn't before. Allowing people to make those optimizations 'by
hand', I believe (as an educator and computer scientist), allows them to
grow as programmers (or computer scientists, as the case may be).

Don't get me wrong, it would be terribly convenient for Python to
abstract away all the nastiness of optimization, but if/when someone
were to do something that had been /very/ fast before, but was now
awfully slow (think the current Queue.Queue object for small vs. large
numbers of items), they are going to jump to the conclusion that Python
is broken in some fundamental way, maybe come here to complain about
Python being broken, and those who are familliar with the internals
would say, "you are ruining Python's early optimization by this thing
that you do".

Which really gets us to the fact that you are asking for the Python
internals to be optimized. In fact, while simultaneously saying "don't
optimize early", you are optimizing early by saying that range should be
optimized, as should string multiplication, etc. Goodness man, pick a
position and stick with it.

- Josiah
Jul 18 '05 #11
On Sat, 3 Apr 2004, Armin Rigo wrote:
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 :-)
{...}
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.
{...}
Protesting-ly yours,


While I certainly appreciate pysco and what it can do, I believe your
protest to be unreasonable as it denies better performance on platforms
that psyco doesn't yet (& probably never will) support.

Moreover, your protest about iterators is also unreasonable as people are
benefitting from the reduced memory consumption iterators and their ilk
bring (quite often accompanied by performance gains from not having to
thrash large amounts of RAM through pitiful caches). As such, iterators
are a _different_ optimisation, and I hope that you can come to terms with
this and psycoise them too!

--
Andrew I MacIntyre "These thoughts are mine alone..."
E-mail: an*****@bullsey e.apana.org.au (pref) | Snail: PO Box 370
an*****@pcug.or g.au (alt) | Belconnen ACT 2616
Web: http://www.andymac.org/ | Australia

Jul 18 '05 #12
Armin Rigo <ar***@tunes.or g> writes:
Ideally: If you do x=range(100); x[50]='hi' then the interpreter first
builds this optimized range representation and assigns it to x; and when
in the next statement you modify this list x it says 'oops! i cannot do
that with this representation' , so it reverts to an array-like
representation (i.e. it creates all 100 elements) and then changes the
50th. No gain here. If on the other hand you only ever do 'easy'
things with your list, like iterate over it or read elements, then it
can all be done with the range representation, without falling back to
the array representation.


Maybe there is something to this.
Jul 18 '05 #13

"Armin Rigo" wrote ...
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.


I think Psyco is great! But Python + Psyco does not outperform
C overall. Try writing a chess program in Python and see how it
performs against C.

Patrick
Jul 18 '05 #14
In article <40************ ***@tunes.org>, Armin Rigo wrote:
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.)


What this does is makes the interpreter more complicated for features
that not all programs will use. Only a very few programs will have long
strings of repeated characters, and it's reasonable to ask them to
implement their own stringlike class if they really want it.

If this is built into the interpreter, then either it's an optional
feature, in which case all those programs that rely on it to be remotely
memory-efficient aren't portable, or it requires every single
implementation to include it, including the PalmOS port and the one
that's supposed to run on cell phones.

Joe
Jul 18 '05 #15
In article <40************ ***@tunes.org>, Armin Rigo wrote:
Joe Mason wrote:
> 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.


Why can't the C implementation do the same thing?


You could, if you wanted to optimize specifically lists of integers. If
you did the result would probably be really fast. The problem is that
you can only really special-case so many types: the C code has to deal
with all cases without knowing which cases are likely. The Psyco
version quickly figures out that for this list it pays off to make a
special case for integers; with another list, the machine code would be
different, special-cased differently.


Ah, good point. (In fact, not special-casing lots of things in the C
code is exactly what I was arguing against in my other post.)

Joe
Jul 18 '05 #16
[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')]
Raymond Hettinger
Jul 18 '05 #17
>>>>> "Armin" == Armin Rigo <ar***@tunes.or g> writes:

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

Iterators are an optimization? I always considered them just a more
clean and elegant way to do the same thing :-).

--
Ville Vainio http://tinyurl.com/2prnb
Jul 18 '05 #18
On Sat, Apr 03, 2004 at 09:44:38PM -0800, 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:

[snip]
# 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')]


Yeah! I love this idea. It may make not only enumerate() but also
reverse() and itertools internal objects more interactive-friendly.
Hye-Shik

Jul 18 '05 #19
Joe Mason <jo*@notcharles .ca> wrote in
news:sl******** ********@gate.n otcharles.ca:
In article <40************ ***@tunes.org>, Armin Rigo wrote:
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.


Why can't the C implementation do the same thing?

It easily could, however sorting a list of ints sounds to me like a
comparatively unusual thing to do in any real application. Sorting strings,
or sorting more complex data structures are much more usual. In other words
it would be kind of pointless to introduce an optimisation that only helps
speedup benchmarks.

Also the builtin sort handles other cases which are important. Not all data
you want to sort is randomly ordered. The builtin sort method should
outperform quicksort in those cases where the input is already largely
sorted. The builtin sort is also stable, although for a list of random
integers you might be hard pushed to tell :-)
Jul 18 '05 #20

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

Similar topics

49
2885
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
3754
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
2071
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
9906
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
5907
by: Lad | last post by:
Is anyone capable of providing Python advantages over PHP if there are any? Cheers, L.
9
4533
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
6769
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
1689
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
2543
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
9671
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10852
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...
1
10596
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
9382
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7793
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6980
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();...
1
4459
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
2
4021
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3116
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.