Hacker News Reader

Comment by msellout | Hacker News Reader

Summary in the conclusion:

"The end result is an implementation several orders of magnitude faster than the current reference implementation in Java. ... [Python] makes the first version easy to implement and provides plenty of powerful tools for optimization later when you understand where and how you need it." [edited to be a statement instead of rhetorical question]

View on HN

Actually, even the subsection headings in bold give a very succinct summary:

- Python has easy development (https://xkcd.com/353/)

- Great libraries (ie, free matlab)

- Cython for efficiency via C

- The algorithms themselves determine speediness (ie numerical methods)

The algorithms themselves determine speediness

This is so important I wish people would focus more on it. I recently rewrote some Javascript code in (pure) python and got a good 2 orders of magnitude speed up on large inputs just by picking the right data structures and replacing an O(n^3) nested loop with an O(n log n) approach.

Which data structures did you use? In Python, I tend to rely on dict, list, and set for 90% or more of my code. I wouldn't want to rely on structures written in pure Python.

Nothing exotic. One of the changes for example was replacing a list of list with a set of tuples, which greatly sped up checking if an object was in the collection. Another change was using a generator comprehension and an included itertool function rather than hand rolled nested for loops.

Once you've exhausted all the low-hanging fruit, like people calling .keys() on dicts, or doing unnecessary linear searches, Cython really starts to shine. I've seen it perform ~40 times better than pure Python in time-consuming loops.

We do scientific computing at my company. Numpy does 90% of the work, but there are some algorithms that just aren't easily expressed with arrays. That's where Cython comes in.

Can you explain the context in which .keys() is called often and is not appropriate and the alternative?

.keys() returns a list (in python2) so if you write

  for k in dict.keys():
    ...

then python first builds a list of all the keys, loops through them and then throws away the list. If the dict is large, this can be quite expensive. The correct way is to either use .iterkeys() which returns an iterator which generates the keys one at a time, or simply iterate directly over the dict, saving you need to first copy all the keys into a list you'll just throw away.

This has been 'fixed' in python3 and .keys() now returns an iterable view of the keys, and if you actually want a list of the keys you have to explicit and write list(dict.keys())

The easiest is to never use .keys() or .iterkeys(), and always iterate over the bare dict:

    for k in dict:
        ...

    if k in dict:
        ...

If you do need a list of keys, list(dict) has the advantage of working in both Python 2 and 3.

Just to clarify your python 2 note: In python 3 keys() returns an iterator, so there is no penalty (i.e. iterkeys was dropped, keys assumed iterkeys interface).

The equivalent python2 behaviour can be obtained using list(somedict.keys())

> Numpy does 90% of the work

Numpy and scipy have been the core of a huge amount of my optimisations. The first question I try and ask is

"Could this be solved with matrix multiplications and summing?"

Often the answer is "yes" and allows you to group a huge amount of calculations all together, and use the heavily optimised code available numpy/scipy.

I recently swapped out something that was running at about 100 rows calculated/second to about half a million in about 0.2s.

In fairness, I should point out that the really slow version was also written by me :)

http://www.vetta.org/2008/05/scipy-the-embarrassing-way-to-c... ;)

Fantastic!

Have you written a blog post about this? If not, care to? Trying to speed up a codebase, it's of interest to me (and no doubt others too).

Yes, this is actually one of the rare moments where I find my past background in competitive programming helpful. There's a habit I've picked up of constantly running through techniques to speed up whenever I'm coding. Not necessarily the most efficient way to code, but it's a habit difficult to change.

Just typed "import antigravity" in python repl. It took me to the same link. :-)

Let me just add Numba to the list. It compiles numpy-using code to native via llvm and can remove temporary arrays in the process.

I tried a very simple toy program the other day and while I had to write some things slightly un-pythonically (it can't deal with syntax like a[:] = b+c yet), it performed practically as good as hand-written C code.

If your code falls within the subset it supports :) I've not yet got it to run our code in nopython mode - I think the latest problem is a function expecting a function as an argument, but the error messages aren't helpful or enlightening, even with DEBUG turned on.

The dev team is pretty responsive and prioritize adding features based on bug reports like this. Can you open an issue?

https://github.com/numba/numba

All the points the author makes through the post are interesting, and Python is definitely great for protoyping, but I think the initial premise is false: "people don't tend to think of [Python] as a high performance language; for that you would want a compiled language -- ideally C or C++ but Java would do."

Java is compiled to bytecode, but it isn't a "compiled language" since that bytecode has to be interpreted by the JVM. All the good libraries the author mention are probably implemented in C or FORTRAN, and so a true implementation in C with the right compiler optimizations would for sure be faster than the python code.

Java(well, Sun's Hotspot) is most definitely compiled, but mostly by the JIT at runtime. The interpreter only runs for the the first warmup, usually 10,000 method calls and the JIT kicks in and translates the method to machine code. The tricky part is it's not simple to control exactly how and when it does its job, although it usually works very well.

The major implementations of the JVM are jited, not interpreted. Yes, you get great performance with jitting, tho not necessarily without unpredictable GC pauses and without a loss of energy efficiency from having to run a jit alongside your actual code.

GC pauses have little to nothing to do JIT process itself. You can get JVMs w/ read barriers and soft-realtime guarantees.[0][1] Please note, gc and jit are quite a different thing, even if the gc needs help from the jit.

[0]: https://www-01.ibm.com/support/knowledgecenter/SSYKE2_7.0.0/... [1]: https://www.azul.com/products/zing/

"...and so a true implementation in C with the right compiler optimizations would for sure be faster than the python code."

True. But this assumes that time is not a constraint.

I think you need to think of it this way (as a thought experiment): you start two programmers off, one in C and one in Python, both with a vague understanding of how to solve the problem and approximately the same skill level. Then after X hours, you stop both and see how far they've gotten.

I think the argument then is that you might find that the C programmer hasn't yet solved the problem, whereas the Python programmer might have a solution + a deeper understanding of where the slow parts are, and started optimizing those.

So in the end the C programmer may win, but perhaps it's not about winning in this sense but more about how fast you can get to a point where you can move on to the next thing.

Absolutely. For this kind of one-shot scientific computing, the only way the C programmer can win is if the Python programmer is sitting on their hands for weeks waiting for their program to run.

Unless (1) the relevant library happens to be written in C and there are no python bindings and the problem is simple OR (2) there is an existing solution which is 95% complete in C and one needs to write from scratch in python. I've never come across situation (1) with a new project. Situation (2) is quite common.

But in those cases, the Python programmer could just wrap the C library in Python, which I suspect is often a lot easier than starting from scratch.

I've tried to do a test like this and the results surprised me. While the testing conditions weren't perfect, I tracked how much time it took to port Fortran code to C++, and how much time it took to write the C++/CUDA optimized version. I would have expected writing all the optimized CUDA kernels would add significant time to the project, but in reality it was something like 1.3x for a solution 15x faster.

I think as developers we often underestimate the amount of work we need to put into the non coding part of development for larger projects, like testing, debugging, optimization, and design. When these components become important then despite the local productivity gains of using rapid development languages like python or Julia, it would overall be a wash if you're writing the system from scratch in a language like C.

On the contrary, I pick Python to make the "testing, debugging, optimization, and design" faster.

I agree with his conclusion that Python has great tools to help performance, but the GIL makes it impossible to effectively make use of separate cores, so I have to wonder just how badly the Java version was written. Properly written high-performance Java (store all data in contiguous arrays, do away with all the OO crap, reuse objects like crazy) should perform as fast, or faster than optimized Python, and you can scale it to as many threads as you like.

Python has MPI4PY and Multiprocessing. Not sure why you need threads in the first place. Also, many matrix operations autoscale to all cores when compiled against Atlas.

Finally, you can release the GIL with Cython: http://docs.cython.org/src/userguide/parallelism.html

Reply on news.ycombinator.com