6 ms·
Python vs Julia – an example from machine learning
- westurner 13y ago1. Where is the source for this benchmark? 2.http://benchmarksgame.alioth.debian.org http://benchmarksgame.alioth.debian.org could be a bit more representative of broad-based algorithmic performance. 3. There are lots of Python libraries for application features other than handpicked algorithms. I would be interested to see benchmarks of the marshaling code in IJulia (IPython with Julia)
- Sweyla 13y agoNo kidding the Active Set solution in Cython is slow, it barely leverages Cython at all! It uses a Python list which is managed by Python and uses none of Cython's static typing. Implement the algorithm inside a "with nogil" and you will see some nice speed-ups. It won't look pretty, but for certain performance-sensitive code it will be worth it.
- ajtulloch 13y agoHi, author here. Yeah, the active set implementation in Cython is relatively slow - see [1] for where I discussed how I benchmarked the existing algorithm and demonstrated the PAVA implementation was faster. Then again, until two days ago the Cython active set algorithm was the production implementation of isotonic regression in scikit-learn, so it's not like it was a strawman example that I made up. [1]: http://tullo.ch/articles/speeding-up-isotonic-regression/ http://tullo.ch/articles/speeding-up-isotonic-regression/
- Sweyla 13y agoTry this implementation for PAVA: https://gist.github.com/gustavla/9499068 https://gist.github.com/gustavla/9499068 Also, how are you timing Python? When I run this on a sample size of 10 using IPython's %timeit, it takes a few microseconds, which is 2 orders of magnitude from what you report.
- halayli 13y agoWhy not use C++11 if performance matters?
- emidln 13y ago"Why not use Fortran 2008 if performance matters?"
- pekk 13y agoWell, why not? Julia is very different from Python, if I am willing to use a completely different tool then the field is wide open and includes anything that has better performance on average
- StefanKarpinski 13y agoJulia's mental programming model for many things is not much different from Python: dynamically typed, pass by sharing, the implicit scoping rules are even quite similar. Sure, Julia has a few extra bells and whistles, like type annotations and dynamic multiple dispatch (which you can ignore and you have something very much like Python but faster), but still, Fortran and C++ are much more different from Python than Julia is.
- tejinderss 13y agoAny tentative idea when Julia 1.0 will be released?
- StefanKarpinski 13y agoPossibly late 2014 or early 2015, but we're not going to rush it if things don't feel ready yet.
- coldtea 13y agoBecause not all "completely different tools" are equally valid or use the same compromises.
- idunning 13y agoVery cool. We had a similar experience when implementing the Simplex method for linear optimization, except we evaluated PyPy versus Julia instead of Cython. Its similar in that it benchmarks "just" the language, not BLAS, which is common pitfall I see when people compare the two. I guess at this point, a year or so later, it isn't surprising to me anymore that Julia is as fast as it is for these sorts of computational tasks - its been demonstrated pretty comprehensively at this point. Slides: http://www.mit.edu/~mlubin/informs2013.pdf http://www.mit.edu/~mlubin/informs2013.pdf Paper: http://arxiv.org/abs/1312.1431 http://arxiv.org/abs/1312.1431
- lqdc13 13y agoI am always confused by this. I think the primary reason for picking a language is how simple it is to write something in it. So if I can call scipy and get the result easily in one line, I would do that. When implementing new algorithms, it will indeed be easier with Julia. Pypy unfortunately cannot be used by most people who would benefit a lot from it because numpy/scipy isn't currently supported. I am curious if you tried running your pypy code with Numba.
- EpicEng 13y agoDepends on your requirements. In many applications, performance matters a whole lot more than "how much can I accomplish in one line of code."
- gregimba 13y agoIf you need speed wouldn't the ability to write as a C extension beat using Julia?
- odonnellryan 13y agoI think the point is the fun of the language. See here: http://julialang.org/ http://julialang.org/ and scroll down a bit for the speed comparison.
- nnq 13y agoWow, looking at those benchmarks it amazes me that Mathematica is so much faster than Matlab and Octave! I used to recommend Mathematica to anyone wishing to "play around with math" and "get a feel for it", due to the user friendly interface and 'manipulate' function that allows you to pop a few sliders for realtime manipulation of parameters in functions and instant visual feedback in one line of code, but always thought of it as either a "toy" or a "learning tool", compared to Matlab that is used by "serious engineers" (mind it, I like neither, I'm a Python and C person, but I'm also closer to what some would consider a "software engineer" and definitely not a mathematician or scientist).
- dagw 13y agoThere are really two reasons that Mathematica isn't taken seriously by engineers. The first is that Mathematica started life as a symbolic math package while engineers need numeric math. Now mathematica has done a lot over the past few release to catch up on the numeric side, but the notion that it is just for symbolic math lingers. The second is the language itself. Matlab is a procedural language heavily inspired by Fortran. Mathematica of the other hand as a largely functional language that takes several design cues from Lisp. Historically most engineers came from a Fortran rather than a Lisp background and most engineering programming is still taught in a "Fortran-inspired" way, so the Matlab language is simply more comfortable for most engineers to think and work in.
- carlob 13y agoTo be honest, I've given a quick look at the implementation in Mathematica, and I think one could do much better. The code is mostly wrapped in Compile statements and is very procedural in style. As a quick test I compared their quicksort with the built in Sort obtaining results about 30 times faster than theirs.
- hartror 13y agoAs others have pointed out improvements could be made to improve performance of the Cython code. However it seems to me the take away from this post should be in this application Julia has a better performance profile while being as simple and expressive as Python [1]. As a Python programmer that often works with these sorts of problems this reinforces my perception that Julia, while not suited to all programming problems offers a productivity gain when it comes to mathematical/algorithmic computing. Sure I could sit and tweak the Cython code or rewrite the hot loops in C++, but it seems to me Julia hits a sweet spot where I am less likely to have to compromise programmer performance for computational performance. [1] I will note however that the code in the OP doesn't seem like the clearest implementation of the algorithms in either language, some of that heavy nesting should be factored for a start.
- ajtulloch 13y agoIn terms of the heavy nesting, that's born out of performance measurements - factoring out the inner loop into a `cdef inline` function in Cython appeared to be a performance hit, so I manually inlined it. When it came for the Julia implementation, I wanted to keep it as similar as possible to the tuned Cython implementation for pedagogical purposes. In general, if anyone has performance improvements or code cleanups to the Cython PAVA code [1] (the implementation used by scikit-learn), please benchmark and send a pull request over to the scikit-learn team. I'm sure they'll be very happy to accept improvements. [1]: https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/_isotonic.pyx https://github.com/scikit-learn/scikit-learn/blob/master/skl...
- sesqu 13y agoThis isn't github, but I'll point out one cleanup: # solution[i:k + 1] is a decreasing subsequence, so should read # solution[i:k] is a decreasing subsequence, so
- StefanKarpinski 13y agoAnother subtle but important point is that the Julia code can be very easily made completely generic without sacrificing any performance or clarity. All you need to do is remove those Float64 annotations and replace the 0.0 values with `zero(y[1]*weights[1])`. With that small change, the same exact code will work for Float32, Rational, BigFloat, Complex (if that even makes sense), etc. – even new, user-defined numeric types that didn't exist when you wrote this code and that you know nothing about, as long as they can be compared, multiplied, added, and divided. This kind of generality isn't necessary for a lot of user-level code, where there's a specific application, but it is quite important when writing libraries that need to be as reusable as possible. And this is where the Cython solution has some problems – sure, you can make it pretty fast, but in doing so, you lose the generality that the original Python code had, and your code becomes as monomorphic as C.
- maxerickson 13y agoHow much time is Cython spending making the copy into the solution array? (Or is Julia making a copy and I just don't see it?)
- amit_m 13y agotl;dr: Julia is killing it.
- est 13y agoIn every benchmark article: you are doing X wrong. Use Y method instead.
- coldtea 13y agoYes, it's as if those people think that instead of trying to measure rough relative speed for similar implementations of some algorithm (which is what you want when you benchmark), you are interest in finding the optimal algorithm for the problem.
- thisrod 13y agoThis looks dodgy to me. The purple and red lines on the graph don't end up parallel, so the active set algorithm appears to have time complexity O(n) in Julia, but O(n^2) or O(n^3) in Python. Can that be explained?
- srean 13y agoIf the objective is to get a fast implementation of isotonic regression, I think the priority would be to choose the right algorithm. PAVA is indeed one of the fastest such algorithms and has a running time bound that is linear in the number of data points. I may be wrong, but from a quick look at the code it seems neither the [P/C]ython version nor the Julia version has an implementation that ensures linear time. The files are named Linear PAVA so I believe there was an expectation that they are indeed linear time. Consider applying it to this sequence 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, -30. It seems that the number of operations required according to these implementations would be quadratic in the size of the sequence. (It will average the tail repeatedly.) I cannot read Julia yet, so not sure about the Julia version, but the others do indeed look very much a quadratic time algorithm at the least. The behavior will of course depend on input, so on certain inputs they may have a runtime that scales linearly. Complexity addresses the worst case behavior and as I showed coming up with such bad cases is not hard, and they need not be very un-natural either. OTOH: If the objective was to compare speeds of CPython, Cython and Julia, then it does not matter whether an efficient algorithm was chosen for the task. My hunch is, because the current implementations computes more than necessary, it is going to magnify the speed difference between Cython and Julia. Does Julia do any inlining ? Or are there any plans for such. If so, that would be one aspect where it could shine. As mentioned in the comment the Cython version is unfactored and manually inlined for performance. If Julia inlines in its JIT pass, such measures would be unnecessary and would allow one to write cleaner code.
- ajtulloch 13y agoYeah, I implemented a guaranteed O(N) PAVA in Julia (see https://github.com/ajtulloch/Isotonic.jl/blob/master/src/pooled_pava.jl https://github.com/ajtulloch/Isotonic.jl/blob/master/src/poo...), and experimented with one in Cython - it was uniformly slower than the 'linear' PAVA across a few sample datasets I tried. See e.g. http://bit.ly/1oDF7nH http://bit.ly/1oDF7nH for some graphs. I'm not claiming I've written the fastest possible implementations or anything though - please feel free to improve any of this code and submit to scikit-learn if you find some improvements!
- srean 13y ago
- pjmlp 13y agoAnother good example how dynamic languages can be made to execute faster with good native code generation support than having to force people to use C or similar. Looking forward to Julia's JIT improvements. This is only the early days.
- e12e 13y agoWait, are we looking at the same graphs? Doesn't this show that for large problem sets cython and julia are pretty much equivalent as long as you choose the best algorithm?
- t3kcit 13y agoWhy are you not using typed memory views in Cython? That might easily close the performance gap.
- dbecker 13y agoWould love to see numba added into this benchmark.
- crasta 13y agoComing from R, I have to ask... Why am I seeing 'for' and 'while' loops? Why isn't this code vectorized? It looks like both implementations suck.
- 3JPLW 13y agoYeah, it's a big change in mindset for Julia. Basically, the reason MATLAB/Numpy/R folks harp so much about vectorizing code is because their interpreters are slow, and within a vectorized function they can punt to some C/C++/Cython implementation. But Julia loops compile down to almost ideal assembly; they are remarkably fast. In fact, verbose loops acting in-place almost always beat the vectorized alternatives because they don't need to allocate space for the result. The wonderful thing about Julia is that you can code it vectorized first, and if that's not fast enough (or if it uses too much memory), you can easily rewrite it in the same language.
- CatMtKing 13y agoAye, first thing I learned about R was that their for loops suck. On the bright side, it taught me how to use apply.
- shabadoop 13y agoThat, and the fact that Julia has pretty good CUDA modules, makes it seem like Julia is perfectly suited for work with Neural Networks.
- crasta 13y agoYou can't parallelize a for-loop the way you can apply a function on every member of a vector. If code can be vectorized in Julia, that is what I'm interested in seeing. These samples are obviously not intended for distributed compute. Thousands of CUDA cores sit idle waiting for this synchronous for-loop to finish.
- maxerickson 13y agoCython has a construct for parallelizing for loops. http://docs.cython.org/src/userguide/parallelism.html http://docs.cython.org/src/userguide/parallelism.html I wouldn't want to claim an informed opinion about whether it is a good style or not, but a block with no side effects isn't that far off from a function with no side effects.