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(100000)
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
>>
>>
