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