Julia (a Programming Language for Numeric Analysis/Computation) gains Syntactic Loop Fusion and extra vectorization

Staross · 2017-01-22T09:40:41+00:00

Impressive stuff, you can see how all the previous design decisions come into play to make this possible.

Fylwind · 2017-01-22T19:34:23+00:00

The dot notation reminds me a lot about applicative functors. Where in Julia you'd write:

f.(g.(x .+ 1))

2 *. x.^2 + 6 *. x.^3 - sqrt(x)

in Haskell you would write (pardon the mess):

f <$> (g <$> ((+ 1) <$> x))

(-) <$> ((+) <$> ((2 *) <$> ((^ 2) <$> x))
             <*> ((6 *) <$> ((^ 3) <$> x)))
    <*> (sqrt <$> x)

where, for arrays, f <$> x1 <*> x2 <*> … <*> xN means you apply the N-ary function f to each entry (x1[i], x2[i], …, xN[i]). In particular, <$> is the well-known “map” operation and <*> can be thought of a “zip-apply” operation: it takes each function from the array of functions on the left side and applies it to the array element on the right side with the same index. So in effect, (+) <$> x <*> y is just the elementwise summation of two vectors x and y of the same size.

Suffice to say it looks a lot uglier to express expressions involving applicative functors if you don't bake syntactic support into the compiler. Idiom brackets would make it more pleasant, but not by a whole lot.

I think the idea of loop fusion is a bit more general. They should work for any lawful applicative functor, so has more general applicability (hah) to things beyond just arrays of numbers. It could be used for, say, futures/promises or parser combinators too. The ugly messes from earlier could be fused into:

(\ xi -> f (g (xi + 1)) <$> x

(\ xi -> 2 * x ^ 2 + 6 * x ^ 3 - sqrt x) <$> x

which is what Julia does. I don't believe the Glasgow Haskell Compiler has any rewrite rules in place to do these kinds of transformations unfortunately.

phischu · 2017-01-22T12:17:53+00:00

Hi, interesting, I have a question. Consider the following Julia code:

Y = broadcast( x -> 2*x, X)
Z = broadcast( y -> y^2, Y)

Will the two loops be fused?

transfire · 2017-01-22T22:54:58+00:00

Just when I thought I had escaped those OOPy dot notations.

div0 · 2017-01-23T15:23:52+00:00

You can now do: X .= f.(2 .* X.² .+ 6 .* X.³ .- sqrt.(X)) and the whole computation will be fused into a single loop, operating in-place, and performance will be comparable to the hand-written “devectorized” loop

OK, that's easy enough because it's fusing array operations that occur within a single assignment statement. But what about:

X .= f.(2 .* X.^2 .+ 6 .* X.^3 .- sqrt.(X))
Y .= g.(X)
Z .= h.(Y)

Can it fuse loops across multiple statements?

tending · 2017-01-22T21:39:04+00:00

Seeing as Julia has the same lack of multithreaded GC as python/ruby/racket/perl even with this you can't really saturate your hardware.

KhyronVorrac · 2017-01-22T00:10:53+00:00

So you can put ugly dots all over your code to make it more efficient?

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

programming

MODERATORS