Python / C: small runtime difference?

[Martin Schneider]

Hi!

I want to extend Python with a C module, so to get the technology clear, I
wrote a Bubblesort over 10.000 elements in Python and in a C extension for
Python and got it running (YES! )

But...

The Python Bubblesort runs 103 seconds, the C extension Bubblesort runs 28
seconds, this is about 1:4, which is far worse than I expected (assumed
about 100:1 or alike).

The interface overhead is neglectable (1/10 second).

Is this normal?

I am using Borland's free compiler BCC on Win32 and Python 1.5.2 (because
the customer uses other modules which do not run under newer versions).

Thank you for your ideas!

Martin

 

[Martin Schneider]

One step ahead: My test program sorted a two-dimensional array containing
pairs of a string and a long integer, and the strcpy routine seems pretty
slow.

After reducing the problem to numerical sort only, I could improve the
relation to 1:50.

Is this a normal ratio?

Martin

 

[=?ISO-8859-1?Q?Gerhard_H=E4ring?=]

One step ahead: My test program sorted a two-dimensional array containing
pairs of a string and a long integer, and the strcpy routine seems pretty
slow.

After reducing the problem to numerical sort only, I could improve the
relation to 1:50.

Is this a normal ratio?

Not for optimized C. But your algorithm is very naive I must say. If I
were to implement such an algorithm in C, I'd avoid copying as much as
possible. It's best to have an array of pointers to structs. Then in
your bubble-sort algorithm, only exchange the pointers, don't copy the
structs themselves.

FWIW your Python code most likely doesn't copy either, it only moves
references around, which is quite fast. So if you make your C code as
smart as Python automatically is <wink>, your C code should be a hell of
a lot faster than your Python code

HTH,

-- Gerhard

 

[Martin Schneider]

Hi, Gerhard,

thanks for your answer

Here's my python code:

for i in range(len(fileList)-1):
for j in range(len(fileList)-i-1):
if fileList[j+1] < fileList[j]:
tmp = fileList[j]
fileList[j] = fileList[j+1]
fileList[j+1] = tmp

Of course I don't know what Python does here internally.

It's best to have an array of pointers to structs. Then in
your bubble-sort algorithm, only exchange the pointers, don't copy the
structs themselves.

Okay - I'll try that

So if you make your C code as
smart as Python automatically is <wink>, your C code should be a hell of
a lot faster than your Python code

Maybe I'll let you know.

Thanks!

Martin

 

[Alan Gauld]

for i in range(len(fileList)-1):
for j in range(len(fileList)-i-1):
if fileList[j+1] < fileList[j]:
tmp = fileList[j]
fileList[j] = fileList[j+1]
fileList[j+1] = tmp

I think you might tweak that by doing:

fileList[j],fileList[j+1] = fileList[j+1],fileList[j]

which misses out the intermediate tmp assignment.
If you are gonna tweak the C you might as well tweak the
Python too! (But not with a real python, they tweak back
hard!

Alan G.
Author of the Learn to Program website
http://www.freenetpages.co.uk/hp/alan.gauld

 

[Martin Schneider]

If you are gonna tweak the C you might as well tweak the

Python too! (But not with a real python, they tweak back
hard!

I'll remember that

Martin

 

[Albert Hofkamp]

Hi, Gerhard,

thanks for your answer

Here's my python code:

for i in range(len(fileList)-1):
for j in range(len(fileList)-i-1):
if fileList[j+1] < fileList[j]:
tmp = fileList[j]
fileList[j] = fileList[j+1]
fileList[j+1] = tmp

Of course I don't know what Python does here internally.

You are modifying lists in-place, which means no copies of the data and
no copies of the lists are made, everything is done using pointer
copying (and updating reference counts).

Okay - I'll try that

That should make a huge difference for anything but the simplest data.
Also, using a better sort algorithm should improve performance
dramatically (i.e. compare your code versus the builtin sort() function
of lists).

Maybe I'll let you know.

It probably will not become slower


Albert

 

[Martin Schneider]

Also, using a better sort algorithm should improve performance

dramatically (i.e. compare your code versus the builtin sort() function
of lists).

I chose a simple bubblesort because I wanted to compare the performance of
handcoded Python with handcoded C. I know that the internal sort() routine
of Python will beat the living daylights out of my bubblesort

Thanks
Martin

 

[Tim Hochberg]

for i in range(len(fileList)-1):
for j in range(len(fileList)-i-1):
if fileList[j+1] < fileList[j]:
tmp = fileList[j]
fileList[j] = fileList[j+1]
fileList[j+1] = tmp

I think you might tweak that by doing:

fileList[j],fileList[j+1] = fileList[j+1],fileList[j]

which misses out the intermediate tmp assignment.

Careful here. You'd have to time it to be sure, but the above is
probably slower than what you're replacing. The reason is that the
above creates an anonymous tuple then unpacks it. More or less
equivalent to:

tmp = (fileList[j+1], fileList[j])
fileList[j], fileList[j+1] = tmp

I'd be tempted to do it anyway in all but the tightest loops as I think
it's clearer.

-tim