3 ms·

I've never seen recursive looping over a thing get turned into efficient SIMD code in any language. Starting with loops has no good reason to be better able to

I've never seen recursive looping over a thing get turned into efficient SIMD code in any language. Starting with loops has no good reason to be better able to achieve that but for practical compilers it makes a huge difference. Julia code might also uses a lot of in place operations which would be hard for a compiler to infer as safe.

Der_Einzige 5y ago
This is why I find it so annoying that CS programs seem to worship functional programming (at least MY program did!). No, I AM going to write procedural code, and it WILL be faster than your "high IQ" 1 line recursive solution. Also funny to see how little recursion gets used in CUDA/Pytorch/GPU programming - which is what we are seeing to be more and more important over time.
- Vetch 5y ago
  Functional programming is a lot more than just recursion and there's nothing about GPUs that precludes an immutable first array based language with functional programming as core. Google Research's Dex is an example.
  - cookieater 5y ago
    Speaking of functional programming and GPU's - check out Futhark :D. Very on the fringe but very interesting.
ummonk 5y ago
And functional paradigms have a way to express looping over a thing that's much better than recursion: filter / map / reduce.
jhgb 5y ago
> I've never seen recursive looping over a thing get turned into efficient SIMD code in any language. Starting with loops has no good reason to be better able to achieve that but for practical compilers it makes a huge difference. Well, for example at the very least in Common Lisp you'll have much more joy with higher-order functions than with loops. The simple reason for that is the existence of compiler macros (http://clhs.lisp.se/Body/03_bba.htm http://clhs.lisp.se/Body/03_bba.htm) which can replace function compositions with arbitrary code. And it's much easier to figure out what the function composition does than to write a loop vectorizer.
- freemint 5y ago
  Maybe loops are not fun in common lisp the? I had much fun with loops in PicoLisp. Julia also has similar macro capabilities to common lisp. > And it's much easier to figure out what the function composition does than to write a loop vectorizer I probably agree but complicated loop vectorisation would probably expressed in Einstein tensor contraction notation such as Tullio.jl provides. I wonder a Fourier transform would look using function decomposition. @tullio F[k] := S[x] * exp(-impi/8 (k-1) * x) (k ∈ axes(S,1))
  - jhgb 5y ago
    Loops are a lot of fun in Common Lisp, what with LOOP (https://gigamonkeys.com/book/loop-for-black-belts.html https://gigamonkeys.com/book/loop-for-black-belts.html), ITERATE (https://common-lisp.net/project/iterate/doc/Don_0027t-Loop-Iterate.html https://common-lisp.net/project/iterate/doc/Don_0027t-Loop-I...), and FOR (https://shinmera.github.io/for/ https://shinmera.github.io/for/). But their fundamental problem of trying to extract a "bird's eye view" of what you're actually trying to do remains here. Maybe a new iteration construct specifically supporting parallelization would help here. Some of these things might already work quite well, for example it should not be difficult to discern from (let me use ITERATE's example) (iterate (for el in list) (finding el minimizing (length el))) that you're computing argmin using a pure function, which should be easy to do in parallel, whereas the way you'd typically write this in C would be probably difficult for the compiler to confirm as such (it would have to look for pattern such as "if (f(current)<f(best)) { best=current; }" or something like that. (BTW have you seen another loop construct supporting argmin/argmax in another language? I haven't so far.) Whether this could be done somewhat generally and extensibly is something I have to ponder on.

Der_Einzige 5y ago

This is why I find it so annoying that CS programs seem to worship functional programming (at least MY program did!). No, I AM going to write procedural code, and it WILL be faster than your "high IQ" 1 line recursive solution. Also funny to see how little recursion gets used in CUDA/Pytorch/GPU programming - which is what we are seeing to be more and more important over time.

Vetch 5y ago
Functional programming is a lot more than just recursion and there's nothing about GPUs that precludes an immutable first array based language with functional programming as core. Google Research's Dex is an example.
- cookieater 5y ago
  Speaking of functional programming and GPU's - check out Futhark :D. Very on the fringe but very interesting.

ummonk 5y ago

And functional paradigms have a way to express looping over a thing that's much better than recursion: filter / map / reduce.

jhgb 5y ago

> I've never seen recursive looping over a thing get turned into efficient SIMD code in any language. Starting with loops has no good reason to be better able to achieve that but for practical compilers it makes a huge difference. Well, for example at the very least in Common Lisp you'll have much more joy with higher-order functions than with loops. The simple reason for that is the existence of compiler macros (http://clhs.lisp.se/Body/03_bba.htm http://clhs.lisp.se/Body/03_bba.htm) which can replace function compositions with arbitrary code. And it's much easier to figure out what the function composition does than to write a loop vectorizer.

freemint 5y ago
Maybe loops are not fun in common lisp the? I had much fun with loops in PicoLisp. Julia also has similar macro capabilities to common lisp. > And it's much easier to figure out what the function composition does than to write a loop vectorizer I probably agree but complicated loop vectorisation would probably expressed in Einstein tensor contraction notation such as Tullio.jl provides. I wonder a Fourier transform would look using function decomposition. @tullio F[k] := S[x] * exp(-impi/8 (k-1) * x) (k ∈ axes(S,1))
- jhgb 5y ago
  Loops are a lot of fun in Common Lisp, what with LOOP (https://gigamonkeys.com/book/loop-for-black-belts.html https://gigamonkeys.com/book/loop-for-black-belts.html), ITERATE (https://common-lisp.net/project/iterate/doc/Don_0027t-Loop-Iterate.html https://common-lisp.net/project/iterate/doc/Don_0027t-Loop-I...), and FOR (https://shinmera.github.io/for/ https://shinmera.github.io/for/). But their fundamental problem of trying to extract a "bird's eye view" of what you're actually trying to do remains here. Maybe a new iteration construct specifically supporting parallelization would help here. Some of these things might already work quite well, for example it should not be difficult to discern from (let me use ITERATE's example) (iterate (for el in list) (finding el minimizing (length el))) that you're computing argmin using a pure function, which should be easy to do in parallel, whereas the way you'd typically write this in C would be probably difficult for the compiler to confirm as such (it would have to look for pattern such as "if (f(current)<f(best)) { best=current; }" or something like that. (BTW have you seen another loop construct supporting argmin/argmax in another language? I haven't so far.) Whether this could be done somewhat generally and extensibly is something I have to ponder on.