Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Python is faster than C

Reply
Thread Tools

Python is faster than C

 
 
Armin Rigo
Guest
Posts: n/a
 
      04-04-2004
Hi,

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.

However, in most real examples, you are not sorting a list of integers
but of something more complex anyway, where the built-in sort wins
easily. My message was intended as a long-term hint that maybe, at some
point, the built-in sort will actually be more often faster than the C
one if rewritten in Python. The advantage would then be that (as Psyco
does in a limited fashion) you can specialize the code for the
particular kind of list you are dealing with.


Armin
 
Reply With Quote
 
 
 
 
Josiah Carlson
Guest
Posts: n/a
 
      04-04-2004
> 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
 
Reply With Quote
 
 
 
 
Christian Tismer
Guest
Posts: n/a
 
      04-04-2004
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_with(each)
except SomeThingWrongWithThis:
# 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_with(each)
exceptSomeThingWrongWithThis
can_continue = some_recovery(each)
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



 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      04-04-2004
Armin Rigo <(E-Mail Removed)> 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.
 
Reply With Quote
 
RPM1
Guest
Posts: n/a
 
      04-04-2004

"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


 
Reply With Quote
 
Joe Mason
Guest
Posts: n/a
 
      04-04-2004
In article <(E-Mail Removed)>, 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
 
Reply With Quote
 
Joe Mason
Guest
Posts: n/a
 
      04-04-2004
In article <(E-Mail Removed)>, 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
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      04-04-2004
[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(result):
result, copy = itertools.tee(result)
print "<%s object at 0x%8x:" %
(type(result).__name__, id(result)),
for elem in itertools.islice(copy, 3):
print repr(elem),
else:
print '...',
print '>'
else:
print repr(result)
_ = result


# intended result
>>> enumerate('abcdefgh')

<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
 
Reply With Quote
 
Hye-Shik Chang
Guest
Posts: n/a
 
      04-04-2004
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('abcdefgh')

> <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

 
Reply With Quote
 
Ville Vainio
Guest
Posts: n/a
 
      04-04-2004
>>>>> "Armin" == Armin Rigo <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
RE: Wow, Python much faster than MatLab Doran, Harold Python 10 01-01-2007 06:56 PM
Wow, Python much faster than MatLab Stef Mientki Python 11 01-01-2007 02:05 AM
Lisp development with macros faster than Python development?.. seberino@spawar.navy.mil Python 37 07-11-2005 02:10 PM
Re: Python is faster than C Armin Rigo Python 6 04-05-2004 04:33 PM
RE: Python is faster than C Robert Brewer Python 2 04-05-2004 04:16 AM



Advertisments