A blog about writing efficient codes for numerical computation

[Dahua]

I am considering a blog post about writing fast codes to do numerical computation in Julia.

The structure is to first establish basic guidelines and then provide some examples to demonstrate how to implement them in practice.

Tentative list of guidelines:

Basics:

• de-vectorization
• cache friendliness (locality of computation)
• pre-allocation (avoid allocating arrays within loop body)
• pre-computation (compute values to be used repeatedly)
• merge computation in a loop

Advanced:

• identify opportunities to use BLAS
• explore equivalent formulas (through algebraic transformation) that can be computed more efficiently
• avoid overflow or underflow (e.g. use log-scale in probability-related computation)

Any thoughts?

[Milktrader]

+1

[Viral Shah]

Please do!

-viral

[Miles Lubin]

This sounds great!

On Saturday, July 6, 2013 9:29:52 AM UTC-4, Dahua wrote:

[Ben Ward]

This would be great for someone like me - who needs to do computation but like many people in life-sciences may have only done a module or two or in my case is self taught. The result is I know how to solve problems I come across, but not necessarily in the most efficient or intelligently written way.

[Glen Hertz]

+1  ...and all without touching Fortran or C!

I really like your code for summing the rows of a matrix so it is cache friendly.  It is easy to understand and 5x faster.

On Saturday, July 6, 2013 9:29:52 AM UTC-4, Dahua wrote:

[Jonne Guyt]

This would be really helpful. I have translated my multinomial (and mixed logit) into Julia (from Matlab) but haven't seen the speed-ups I was expecting / hoping for.

[Stefan Karpinski]

This will be tremendous, Dahua. Interestingly, a lot of this stuff is not actually that Julia-specific, but is what "the pros" do in C/Fortran. In most high-level languages, the *only* chance of writing fast code is to vectorize as much as possible and then rely on someone else already having done this work for the code that implements vectorized operations. The unusual combination here that in Julia you're writing high-level code yet it makes sense to apply low-level optimization approaches.

[Dahua]

Great point, Stefan. This is one of the reasons why I love Julia.

[John Myles White]

It would be nice to have an example of where things are slow. The multinomial sampler code still needs improvement.

-- John

[John Myles White]

This sounds great, Dahua. One guideline I hope you'll suggest is to always define an in-place version of a function as the core case for vector-input functions, then define a pure function that combines memory allocation with in-place computation in terms of the mutating base-case.

 -- John

[Glen Hertz]

Hi,

By the way, I wish we had names for mutating operators (eg +!, .*!, etc).  Are there standard function names for the mutating versions of the non-mutating operators (eg add! is a mutating +, etc)? 

Glen

[Viral Shah]

Along with the blog entry, I think that it is also worth capturing this in the Performance Tips section of the manual.

http://docs.julialang.org/en/latest/manual/performance-tips/

-viral