[julia-users] Re: some Python / Julia comparisons
Hi Jason,
Could it be possible for you to create a Julia program to compare it with
the famous Jake Vanderplas post ?
http://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/
Under which type of problem Julia fly much higher or easily than
cython/pypy/numba ?
("much" = x3 in my mind)
Le samedi 20 septembre 2014 18:41:02 UTC+2, Jason Trenouth a écrit :
>
> Hi,
>
> I converted some Python programs to Julia recently. The (probably
> incorrect) ramblings are here:
>
> http://a-coda.tumblr.com/post/93907978846/julia-dream
>
> http://a-coda.tumblr.com/post/97973293291/a-recurring-dream
>
> tl;dr - similar in style, but Julia can be a lot faster
>
> __Jason
>
>
[julia-users] Re: some Python / Julia comparisons
One thing that's really nice about Julia is that it's often straightforward
to transliterate python code (or matlab code) in a fairly literal way and
end up with working code that has similar, or sometimes better performance.
But another nice thing about Julia is that it allows you to fairly smoothly
move from python or matlab-like code to c-like code that has much better
performance, in the places where this matters. There's usually some work to
do to achieve this, though. I.e. you can't generally expect that
inefficiently vectorized matlab-style code, or python-style code that uses
tons of Dict lookups, will perform orders of magnitude better in Julia than
it did in the original languages.
To put it differently, "Julia makes code run fast" is too simplistic, but
"Julia lets me write expressive high level code," "Julia lets me write
performant low level code", and "Julia lets me smoothly move back and forth
between high level code and low level code" are all true in my experience.
Okay, so finally the reason for this sermon: if you want to, I think you
could wring a lot more performance out of that Viterbi code. I haven't
actually tried this yet, but I think you could replace a lot of your data
structures with arrays and vectors of floats and ints, and then you'll
probably see performance improvements like 2x or 10x or 100x instead of
1.26x.
If you treat your states, ["Healthy", "Fever"], and your observations
["normal", "cold", "dizzy"] like enums, i.e. think of those strings mapping
onto integers, then your start probability can become a vector of 2 floats,
your transition probability is a 2x2 float array, and your emission
probability is a 2x3 float array.
The big improvement will come from treating "paths" as an int array. Right
now, it's a Dict{K,Any}(), and you allocate a new dict on each iteration,
which is probably really hurting you. You could translate it to a Nx2
array, where N is the number of observations, and 2 is the number of
states, and then allocate it all at the beginning. At each step n, you then
fill in the nth row with integers that tell you which column to look in
above you to keep following the path backwards.
If you try any of this, I'd love to know how it goes. If you're after
performance here, I suspect you'll be impressed by the results.
Best,
Jason
On Saturday, September 20, 2014 9:41:02 AM UTC-7, Jason Trenouth wrote:
>
> Hi,
>
> I converted some Python programs to Julia recently. The (probably
> incorrect) ramblings are here:
>
> http://a-coda.tumblr.com/post/93907978846/julia-dream
>
> http://a-coda.tumblr.com/post/97973293291/a-recurring-dream
>
> tl;dr - similar in style, but Julia can be a lot faster
>
> __Jason
>
>
[julia-users] Re: some Python / Julia comparisons
I got curious, and ended up implementing this myself:
https://gist.github.com/jwmerrill/ff422bf00593e006c1a4
On my laptop, your Viterbi benchmark runs in 6.9s, and this new
implementation runs in 0.5s, so it's something like 14x faster. If you
wanted to push on performance any more, I'd recommend moving to a longer
set of observations, and checking how execution time scales with
1. The number of observations
2. The size of the state space
3. The size of the observation space
You can end up optimizing the wrong things if you only benchmark a toy
example that executes in half a microsecond.
If you do move to a longer set of observations, you might want to switch to
storing and manipulating log probabilities instead of probabilities to
avoid underflow. It looks like this algorithm only ever multiplies
probabilities (never adds them), which is convenient because in log space,
multiplication is translated to addition, but addition is translated to
something that requires taking exponents and logs.
A couple of additional comments:
1. Note the lack of type annotations on the viterbi function. They aren't
necessary for performance, as long as the input is well typed. Sometimes
they can be useful for documentation or error checking though.
2. I made the problem data const. It occurs in global scope, so this is
necessary to make sure that it is precisely typed.
3. Most of the time is now spent allocating V, maxindices, and the output
of path, and also inside first_index. I checked this by running
@profile benchmark_example(10)
Profile.print()
Only the most recent column of V is ever used, so you could probably speed
things up by only storing 1 column of V, and mutating it. first_index could
probably be further optimized by dispatching on the length of the string or
its first char or something like that, but I decided not to mess with that.
On Saturday, September 20, 2014 11:43:11 AM UTC-7, Jason Merrill wrote:
>
> One thing that's really nice about Julia is that it's often
> straightforward to transliterate python code (or matlab code) in a fairly
> literal way and end up with working code that has similar, or sometimes
> better performance.
>
> But another nice thing about Julia is that it allows you to fairly
> smoothly move from python or matlab-like code to c-like code that has much
> better performance, in the places where this matters. There's usually some
> work to do to achieve this, though. I.e. you can't generally expect that
> inefficiently vectorized matlab-style code, or python-style code that uses
> tons of Dict lookups, will perform orders of magnitude better in Julia than
> it did in the original languages.
>
> To put it differently, "Julia makes code run fast" is too simplistic, but
> "Julia lets me write expressive high level code," "Julia lets me write
> performant low level code", and "Julia lets me smoothly move back and forth
> between high level code and low level code" are all true in my experience.
>
> Okay, so finally the reason for this sermon: if you want to, I think you
> could wring a lot more performance out of that Viterbi code. I haven't
> actually tried this yet, but I think you could replace a lot of your data
> structures with arrays and vectors of floats and ints, and then you'll
> probably see performance improvements like 2x or 10x or 100x instead of
> 1.26x.
>
> If you treat your states, ["Healthy", "Fever"], and your observations
> ["normal", "cold", "dizzy"] like enums, i.e. think of those strings mapping
> onto integers, then your start probability can become a vector of 2 floats,
> your transition probability is a 2x2 float array, and your emission
> probability is a 2x3 float array.
>
> The big improvement will come from treating "paths" as an int array. Right
> now, it's a Dict{K,Any}(), and you allocate a new dict on each iteration,
> which is probably really hurting you. You could translate it to a Nx2
> array, where N is the number of observations, and 2 is the number of
> states, and then allocate it all at the beginning. At each step n, you then
> fill in the nth row with integers that tell you which column to look in
> above you to keep following the path backwards.
>
> If you try any of this, I'd love to know how it goes. If you're after
> performance here, I suspect you'll be impressed by the results.
>
> Best,
>
> Jason
>
> On Saturday, September 20, 2014 9:41:02 AM UTC-7, Jason Trenouth wrote:
>>
>> Hi,
>>
>> I converted some Python programs to Julia recently. The (probably
>> incorrect) ramblings are here:
>>
>> http://a-coda.tumblr.com/post/93907978846/julia-dream
>>
>> http://a-coda.tumblr.com/post/97973293291/a-recurring-dream
>>
>> tl;dr - similar in style, but Julia can be a lot faster
>>
>> __Jason
>>
>>
[julia-users] Re: some Python / Julia comparisons
On Sunday, 21 September 2014 19:23:20 UTC+1, Jason Merrill wrote: > > I got curious, and ended up implementing this myself: > Hi Jason, Thanks for this and your previous comment. I might play about with this some more myself, e.g. back translate to Python to compare again. Note that the original Python code was just taken from the Wikipedia page on Viterbi and was probably only meant for educational purposes. I was trying to see how little I could change the code to speed things up while showing off some aspects of Julia. __Jason
[julia-users] Re: some Python / Julia comparisons
On Saturday, 20 September 2014 18:45:31 UTC+1, stone...@gmail.com wrote:
>
> Hi Jason,
>
> Could it be possible for you to create a Julia program to compare it with
> the famous Jake Vanderplas post ?
> http://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/
>
> Under which type of problem Julia fly much higher or easily than
> cython/pypy/numba ?
> ("much" = x3 in my mind)
>
>
Hi,
As a Julia newbie I'm not sure I'm the right person to ask to do such a
bake-off, but there may be others who'll bite.
__Jason
[julia-users] Re: some Python / Julia comparisons
On Sunday, September 21, 2014 12:21:37 PM UTC-7, Jason Trenouth wrote: > > On Sunday, 21 September 2014 19:23:20 UTC+1, Jason Merrill wrote: >> >> I got curious, and ended up implementing this myself: >> > > I was trying to see how little I could change the code to speed things up > while showing off some aspects of Julia. > Yeah, totally, and I think that's valuable. It's nice to know that "you, yes you! can probably port your python code to Julia and get it working today." But I'm advocating that you're missing a lot of the benefit (and a lot of the fun!) if you don't then massage your code to take advantage of Julia's strengths. If I read your post without knowing anything about Julia, I think I might conclude "oh, great, Julia is another language that's good for writing recursive factorial, but the performance improvements aren't so impressive for real algorithms like Viterbi." I wouldn't bother porting my code to a whole different language for a 26% performance improvement, unless maybe I was trying to get a few more fps in a game or something like that.
[julia-users] Re: some Python / Julia comparisons
On Saturday, September 20, 2014 10:45:31 AM UTC-7, stone...@gmail.com wrote:
>
> Hi Jason,
>
> Could it be possible for you to create a Julia program to compare it with
> the famous Jake Vanderplas post ?
> http://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/
>
> Under which type of problem Julia fly much higher or easily than
> cython/pypy/numba ?
> ("much" = x3 in my mind)
>
You should just try it. `pairwise_python` from that post can be translated
to Julia quite literally. I didn't succeed in installing numba in my first
5 minutes of trying, so I can't really report on comparative performance,
but I can tell you that the Julia version's execution time is measured in
ms, and the pure python version's execution time is measured in seconds.
BTW, I think in Julia it might be better to represent the points as a
3x1000 array instead of a 1000x3 array, since you want the point
coordinates to be stored next to each other in memory for this algorithm.
See also "pairwise" from the Distances.jl package.
[julia-users] Re: some Python / Julia comparisons
Python w/ numba and Julia are comparable in speed for the tests I did. This
is
not surprising as numba utilizes LLVM as well. For the above example and on
my
Unix computer, the timings are 15 ms for Python+numba and 20 ms for Julia.
If one gets the data as 1000x3 matrix, should one really first transpose
the
matrix and then apply a distance function on 3x1000? I don't think so.
On Sunday, September 21, 2014 10:52:43 PM UTC+2, Jason Merrill wrote:
>
> On Saturday, September 20, 2014 10:45:31 AM UTC-7, stone...@gmail.com
> wrote:
>>
>> Hi Jason,
>>
>> Could it be possible for you to create a Julia program to compare it with
>> the famous Jake Vanderplas post ?
>> http://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/
>>
>> Under which type of problem Julia fly much higher or easily than
>> cython/pypy/numba ?
>> ("much" = x3 in my mind)
>>
>
> You should just try it. `pairwise_python` from that post can be translated
> to Julia quite literally. I didn't succeed in installing numba in my first
> 5 minutes of trying, so I can't really report on comparative performance,
> but I can tell you that the Julia version's execution time is measured in
> ms, and the pure python version's execution time is measured in seconds.
>
> BTW, I think in Julia it might be better to represent the points as a
> 3x1000 array instead of a 1000x3 array, since you want the point
> coordinates to be stored next to each other in memory for this algorithm.
>
> See also "pairwise" from the Distances.jl package.
>
[julia-users] Re: some Python / Julia comparisons
Examining your Viterbi Julia implementation, I noticed that you expand that
path by
newpath[y] = ( y, path[state] )
This would result in nested tuples. However in python with
newpath[y] = path[state] + [y]
you get a nice flat tuple.
You can modify the Julia code to get a comparable path tuple by :
newpath[y] = tuple( y, path[state]... )
However, that slowed down things by 55% on my machine.
Without drastic modification to the code's structure, the following line
were modified
path = Dict{K,Array{K,1}}() # Made the type even more explicit in path
declaration
path[y] = [y] # Array, not tuple in the base case
#=newpath = Dict{K,Any}()=# Comment this line out
push!(path[state],y) # instead of newpath
#=path = newpath=# Comment out this line also
By cutting down on unnecessary memory allocation, the code with the above
modifications runs 21% faster than your original Julia implementation. In
some ways it is also cleaner and more concise.
On Saturday, September 20, 2014 7:41:02 PM UTC+3, Jason Trenouth wrote:
>
> Hi,
>
> I converted some Python programs to Julia recently. The (probably
> incorrect) ramblings are here:
>
> http://a-coda.tumblr.com/post/93907978846/julia-dream
>
> http://a-coda.tumblr.com/post/97973293291/a-recurring-dream
>
> tl;dr - similar in style, but Julia can be a lot faster
>
> __Jason
>
>
[julia-users] Re: some Python / Julia comparisons
Sorry, just realized the my last modifications were logically incorrect.
Having the newpath variable is essential.
On Monday, September 22, 2014 12:09:34 PM UTC+3, Mohammed El-Beltagy wrote:
>
> Examining your Viterbi Julia implementation, I noticed that you expand
> that path by
> newpath[y] = ( y, path[state] )
> This would result in nested tuples. However in python with
> newpath[y] = path[state] + [y]
> you get a nice flat tuple.
>
> You can modify the Julia code to get a comparable path tuple by :
> newpath[y] = tuple( y, path[state]... )
> However, that slowed down things by 55% on my machine.
>
> Without drastic modification to the code's structure, the following line
> were modified
> path = Dict{K,Array{K,1}}() # Made the type even more explicit in path
> declaration
> path[y] = [y] # Array, not tuple in the base case
> #=newpath = Dict{K,Any}()=# Comment this line out
> push!(path[state],y) # instead of newpath
> #=path = newpath=# Comment out this line also
>
> By cutting down on unnecessary memory allocation, the code with the above
> modifications runs 21% faster than your original Julia implementation. In
> some ways it is also cleaner and more concise.
>
>
>
>
>
>
>
> On Saturday, September 20, 2014 7:41:02 PM UTC+3, Jason Trenouth wrote:
>>
>> Hi,
>>
>> I converted some Python programs to Julia recently. The (probably
>> incorrect) ramblings are here:
>>
>> http://a-coda.tumblr.com/post/93907978846/julia-dream
>>
>> http://a-coda.tumblr.com/post/97973293291/a-recurring-dream
>>
>> tl;dr - similar in style, but Julia can be a lot faster
>>
>> __Jason
>>
>>
Re: [julia-users] Re: some Python / Julia comparisons
On Sunday, September 21, 2014 03:02:38 PM Hans W Borchers wrote: > If one gets the data as 1000x3 matrix, should one really first transpose > the > matrix and then apply a distance function on 3x1000? I don't think so. It depends on the coming algorithm. 1000 points is not very much; the whole thing would fit into L1 cache, and so for 1000 points there's no incentive. But change that to 10^5 points, so the total computational cost is 10^10, and you could get an 5-10 fold speedup even with the cost of that transposition. When it comes to performance, cache is a huge consideration, and an O(N) reordering is totally worth it for an O(N^2) algorithm. Of course, if you're using the Euclidean distance, you can do it using BLAS matrix multiplication (with some loss in precision), and BLAS already worries about cache for you. So in that particular case, with that particular algorithm, it wouldn't be necessary. But basically any other metric (or if you are worried about that loss of precision and want to use the higher-precision "naive" algorithm), you'll want the points arranged along columns. --Tim
