4 ms·

Well, expressions like these look to me very clearly like a pattern that can be implemented using SIMD instructions: map (uncurry (+)) (zip [1,2,3] [4,5,6]

by panzi 13y ago

Well, expressions like these look to me very clearly like a pattern that can be implemented using SIMD instructions: map (uncurry (+)) (zip [1,2,3] [4,5,6]) I guess because of these standard functions and the fact that everything in Haskell is immutable and side effect free it should be comparably easy to do SIMD optimizations. It's only a guess, though.

colanderman 13y ago
Not if [1,2,3] and [4,5,6] are actually lists, or aren't aligned properly, or aren't the correct bitwidth, or the expression can't saturate/wrap, etc. The compiler needs to be able to see that the data conforms to all those restrictions (possibly more), and that's not a trivial thing to do.
- panzi 13y ago
  Shouldn't the compiler be able to see this? After all, Haskell is statically typed. Ok, maybe the compiler (optimizer) needs to look across function boundaries, but it should be possible, shouldn't it?
  - colanderman 13y ago
    In the simplest cases, sure. But inferring that amount of information in general programs is very much an open problem. Even with GCC, which incorporates what is roughly (at least within an order of magnitude) state-of-the-art autovectorization, you have to be careful how you write your loops and structure your arrays or the compiler won't pick up on it. Here's an example in Haskell: consider the case that the list of numbers was generated from a list of some other structure; something like "map x coordinates" to get all the X values from a list of X-Y-Z coordinates. For vectorization to work, those values need to be packed together in memory; however the structure isn't organized as such (at best, you'd have XYZXYZXYZ). That means a nontrivial memory copy, which will cost much more than the vectorization will gain you. So the structure needs to be reorganized, but then that might cause other pessimizations.
    - panzi 13y ago
      I see.

by panzi 13y ago

colanderman 13y ago

Not if [1,2,3] and [4,5,6] are actually lists, or aren't aligned properly, or aren't the correct bitwidth, or the expression can't saturate/wrap, etc. The compiler needs to be able to see that the data conforms to all those restrictions (possibly more), and that's not a trivial thing to do.

panzi 13y ago
Shouldn't the compiler be able to see this? After all, Haskell is statically typed. Ok, maybe the compiler (optimizer) needs to look across function boundaries, but it should be possible, shouldn't it?
- colanderman 13y ago
  In the simplest cases, sure. But inferring that amount of information in general programs is very much an open problem. Even with GCC, which incorporates what is roughly (at least within an order of magnitude) state-of-the-art autovectorization, you have to be careful how you write your loops and structure your arrays or the compiler won't pick up on it. Here's an example in Haskell: consider the case that the list of numbers was generated from a list of some other structure; something like "map x coordinates" to get all the X values from a list of X-Y-Z coordinates. For vectorization to work, those values need to be packed together in memory; however the structure isn't organized as such (at best, you'd have XYZXYZXYZ). That means a nontrivial memory copy, which will cost much more than the vectorization will gain you. So the structure needs to be reorganized, but then that might cause other pessimizations.
  - panzi 13y ago
    I see.