Python is slow?

[sturlamolden]

I have recently been playing with a kd-tree for solving the "post
office problem" in a 12-dimensional space. This is pure cpu bound
number crunching, a task for which I suspected Python to be
inefficient.

My prototype in Python 2.5 using NumPy required 0.41 seconds to
construct the tree from 50,000 samples. Unfortunately, searching it
felt a bit slow, finding the 11 nearest-neighbours of 1,000 points
took 29.6 seconds (and there were still 49,000 to go). Naturally, I
blamed this on Python. It would be 100 times faster if I used C++,
right?

After having a working Python prototype, I resorted to rewrite the
program in C++. The Python prototype took an hour to make, debug and
verify. The same thing in C++ took me almost a day to complete, even
with a working prototype as model. To my surprise, the resulting beast
of C++ required 64.3 seconds to construct the same kd-tree. Searching
the tree was not faster either, 1,000 points required 38.8 seconds. I
wasted a day, only to find my Python prototype being the faster.

We may conclude that I'm bad at programming C++, but I suspect that is
not the case here. Albeit micro-benchmarks may indicate that Python is
100-200 times slower than C++, they may not be applicable to the real
world. Python can be very efficient. And when combined with libraries
like NumPy, beating it's performance with hand-crafted C++ is
difficult. At least, my 10 years experience programming scientific
software in various languages was not sufficient to beat my own Python
prototype with C++.

That is not to say I have never seen C++ run a lot faster than Python.
But it tends to be very short pieces of CPU bound code, no more than a
function or two. But as the problem grows in complexity, C++
accumulates too much of its own bloat.

[Robert Singer]

On Tue, 23 Sep 2008 06:23:12 -0700 (PDT), sturlamolden
<st**********@y ahoo.nowrote:

>I have recently been playing with a kd-tree for solving the "post
office problem" in a 12-dimensional space. This is pure cpu bound
number crunching, a task for which I suspected Python to be
inefficient.

Well, python is not a number crunching language. However much we would
like it to be (we would ? :-). No scripting language is.
Developing time is shorter, I agree, but when you have, for example a
problem which takes 8,31 minutes to go through in optimized fortran
code (like the one I had the other day), then that hardly matters.

>
My prototype in Python 2.5 using NumPy required 0.41 seconds to
construct the tree from 50,000 samples. Unfortunately, searching it
felt a bit slow, finding the 11 nearest-neighbours of 1,000 points
took 29.6 seconds (and there were still 49,000 to go). Naturally, I
blamed this on Python. It would be 100 times faster if I used C++,
right?

Not necessarily.
Before resorting to rewriting the problem try psyco. It speeds up
things sometimes.
Also, (I'm not that familiar with python yet, so I don't know how to
do it in python), try finding the bottlenecks of your calculation. Are
the loops where most of the processing time is wasted, or disk
accessing, or ... ?

>
After having a working Python prototype, I resorted to rewrite the
program in C++. The Python prototype took an hour to make, debug and
verify. The same thing in C++ took me almost a day to complete, even
with a working prototype as model. To my surprise, the resulting beast
of C++ required 64.3 seconds to construct the same kd-tree. Searching
the tree was not faster either, 1,000 points required 38.8 seconds. I
wasted a day, only to find my Python prototype being the faster.

>
We may conclude that I'm bad at programming C++, but I suspect that is
not the case here. Albeit micro-benchmarks may indicate that Python is
100-200 times slower than C++, they may not be applicable to the real
world. Python can be very efficient. And when combined with libraries
like NumPy, beating it's performance with hand-crafted C++ is
difficult. At least, my 10 years experience programming scientific
software in various languages was not sufficient to beat my own Python
prototype with C++.

That is not to say I have never seen C++ run a lot faster than Python.
But it tends to be very short pieces of CPU bound code, no more than a
function or two. But as the problem grows in complexity, C++
accumulates too much of its own bloat.

Well, personally, I try to combine fortran (being a fortran programmer
by trade) with python (in the last few years), as I find fortran to
be, by two grades, more comfortable for solving scientific problems
then c (or python for that matter, although it has its merits).
Starting from ith his capabilities for "normal" array handling, to
optimisation and easy readability, to whatnot.
Best regards
Bob

[Grant Edwards]

On 2008-09-23, sturlamolden <st**********@y ahoo.nowrote:

[...]

After having a working Python prototype, I resorted to rewrite the
program in C++. The Python prototype took an hour to make, debug and
verify. The same thing in C++ took me almost a day to complete, even
with a working prototype as model. To my surprise, the resulting beast
of C++ required 64.3 seconds to construct the same kd-tree. Searching
the tree was not faster either, 1,000 points required 38.8 seconds. I
wasted a day, only to find my Python prototype being the faster.

We may conclude that I'm bad at programming C++,

AFAICT, _everybody_ is bad at programming C++.

One begins to suspect it's not the fault of the programmers.

--
Grant Edwards grante Yow! Finally, Zippy
at drives his 1958 RAMBLER
visi.com METROPOLITAN into the
faculty dining room.

[George Sakkis]

On Sep 23, 9:57 am, Grant Edwards <[e-mail] mwrote:

On 2008-09-23, sturlamolden <sturlamol...@y ahoo.nowrote:

[...]

After having a working Python prototype, I resorted to rewrite the
program in C++. The Python prototype took an hour to make, debug and
verify. The same thing in C++ took me almost a day to complete, even
with a working prototype as model. To my surprise, the resulting beast
of C++ required 64.3 seconds to construct the same kd-tree. Searching
the tree was not faster either, 1,000 points required 38.8 seconds. I
wasted a day, only to find my Python prototype being the faster.

We may conclude that I'm bad at programming C++,

AFAICT, _everybody_ is bad at programming C++.

+1 QOTW

[skip]

>We may conclude that I'm bad at programming C++,

GrantAFAICT, _everybody_ is bad at programming C++.

GrantOne begins to suspect it's not the fault of the programmers.

+1 QOTW...

Skip

[bearophileHUGS]

sturlamolden:

CPython is generally slow (you can see this from the huge amount of
solutions invented to solve the speed problem, like Cython, Numpy,
Psyco, ShedSkin, Weave, Inline, SIP, Boost Python, SWIG, etc etc), but
for most of the usages Python is used for, it's not a significant
problem. I know that sounds like a tautology :-)

Well written C++ code is generally faster or much faster than similar
Python code, but programming in Python is often simpler, and it
generally requires less time. So it may happen that to solve a problem
a Python program that runs in 1 hour that requires 1 hour to be
written allows you to find the solution in less time than a C++
program that runs in 5-10 minutes that requires you 3-4 hours to be
written :-)

Note that C++ is just one option, but there are other languages
around, like CLisp or D (or even a modern JavaVM), that are often an
acceptable compromise between Python and C/C++.

So you can show us a reduced/minimal working version of your Python
code, so I/someone may find ways to speed it up, translate it to C or C
++ or CLisp or D, etc.

Note that I have written a kd-tree in both Python (with Psyco
compulsively) and D, this is the Psyco version:
http://code.activestate.com/recipes/572156/

Bye,
bearophile

[sturlamolden]

On Sep 23, 3:44*pm, Robert Singer <rsinger@____.c omwrote:

Well, python is not a number crunching language. However much we would
like it to be (we would ? :-).

No scripting language is.

Not even Matlab, R, IDL, Octave, SciLab, S-PLUS or Mathematica?

Before resorting to rewriting the problem try psyco. It speeds up
things sometimes.

I did, Psyco did not help.

Also, (I'm not that familiar with python yet, so I don't know how to
do it in python), try finding the bottlenecks of your calculation.

I did use a profiler, there is no particular single bottle-neck.

Well, personally, I try to combine fortran (being a fortran programmer
by trade) with python

Good compilers are too expensive, and gfortran is not good enough yet.

[namekuseijin]

On Sep 23, 10:57*am, Grant Edwards <[e-mail] mwrote:

AFAICT, _everybody_ is bad at programming C++.

Thankfully, at least Numpy developers are not bad at C programming.

[bearophileHUGS]

sturlamolden:

>F# and OCaml look promising though.<

I bet on the future of D and Haskell (and maybe Fortress) instead :-)
We'll see.

>Sure I could show you the code, Python and C++, if I had a place to post it.<

I think the Python version suffices. If it's not too much private you
may post the single minimal/reduced runnable Python module here, it
will be deleted in some time (if you want you can also use a private
paste):
http://codepad.org/

>It looks very different form yours though.<

Is this a good or bad thing? ;-)

Bye,
bearophile

[sturlamolden]

On Sep 23, 8:52*pm, bearophileH...@ lycos.com wrote:

I think the Python version suffices. If it's not too much private you
may post the single minimal/reduced runnable Python module here, it
will be deleted in some time (if you want you can also use a private
paste):http://codepad.org/

http://codepad.org/rh8GzzJT

Available 24 hours from now.

Is this a good or bad thing? ;-)

It's just facinating how different people working on similar problems
come up with different looking code.