6 ms·

Ya, it's definitely a language issue; barring super-intelligent compilers that can vectorize things on their own (which GCC does for certain cases), you need a

Ya, it's definitely a language issue; barring super-intelligent compilers that can vectorize things on their own (which GCC does for certain cases), you need a means to express vectorizable operations. You don't need to work at the assembly level for this; you just need a language that can express vector operations in a way that doesn't require a compiler to solve the halting problem, and you need a compiler that knows how to compile such operations to SIMD. Yes, ANSI C doesn't have such a construct, but GNU C (which I'd bet 95% of open-source code uses anyway) does.

astrange 13y ago
Nearly all SIMD in ffmpeg/libav/x264 is just written in assembly. Back in the day, gcc's code generation for even x86 SIMD intrinsic functions was too poor to consider using it. (Plus x86's intrinsics are just plain ugly. It's easier to read asm.) As for the architecture-independent SIMD in GNU C, it's something, but not quite flexible enough. Even C is really not a good enough language to consider implementing this in, because it has an overly-conservative memory model when it comes to char *, which aliases all other memory. For a library dedicated to parsing things which come in the form of bytestreams and 8-bit pixels, this means that most compiler optimizations are defeated right in the inner loops where you'd need them.
- nitrogen 13y ago
  Isn't that what the restrict keyword is for?
  - panzi 13y ago
    Yes, but how long does this exist? My guess would be that it isn't really used (yet) in ffmpeg.
    - anon1385 13y ago
      Since C99 so 15 years, which is older than ffmpeg.
      - panzi 13y ago
        What I meant is how long is it supported by compilers. I know its by GCC, but I think it's not by MSCV. Is it possible to compile ffmpeg with MSVC? But ok, one could use it and just #define it away for crappy compilers.
        jasomill 13y ago
        According to MSDN, Visual C++ has supported the equivalent __restrict keyword since at least 2005 [1], and according to the ffmpeg documentation [2], "FFmpeg can be built with MSVC 2012 or earlier using a C99-to-C89 conversion utility and wrapper, or with MSVC 2013 and ICL natively." [1] http://msdn.microsoft.com/en-us/library/5ft82fed(v=vs.80).aspx http://msdn.microsoft.com/en-us/library/5ft82fed(v=vs.80).as... [2] http://www.ffmpeg.org/platform.html http://www.ffmpeg.org/platform.html
  - astrange 13y ago
    gcc mostly ignores restrict, though it's got a little better in recent versions. icc uses it a little more. But restrict is only good in specific situations - if you have three pointers, and #2 can alias #1 but not #3, there's no way to express that. It also tends to be used on function arguments, not at some higher up point of declaration. So when compilers inline the function and can see more global info about it, the restrict gets lost and optimization gets worse. I think some kind of stronger 'typedef' would be better.
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.

astrange 13y ago

Nearly all SIMD in ffmpeg/libav/x264 is just written in assembly. Back in the day, gcc's code generation for even x86 SIMD intrinsic functions was too poor to consider using it. (Plus x86's intrinsics are just plain ugly. It's easier to read asm.) As for the architecture-independent SIMD in GNU C, it's something, but not quite flexible enough. Even C is really not a good enough language to consider implementing this in, because it has an overly-conservative memory model when it comes to char *, which aliases all other memory. For a library dedicated to parsing things which come in the form of bytestreams and 8-bit pixels, this means that most compiler optimizations are defeated right in the inner loops where you'd need them.

nitrogen 13y ago
Isn't that what the restrict keyword is for?
- panzi 13y ago
  Yes, but how long does this exist? My guess would be that it isn't really used (yet) in ffmpeg.
  - anon1385 13y ago
    Since C99 so 15 years, which is older than ffmpeg.
    - panzi 13y ago
      What I meant is how long is it supported by compilers. I know its by GCC, but I think it's not by MSCV. Is it possible to compile ffmpeg with MSVC? But ok, one could use it and just #define it away for crappy compilers.
      - jasomill 13y ago
        According to MSDN, Visual C++ has supported the equivalent __restrict keyword since at least 2005 [1], and according to the ffmpeg documentation [2], "FFmpeg can be built with MSVC 2012 or earlier using a C99-to-C89 conversion utility and wrapper, or with MSVC 2013 and ICL natively." [1] http://msdn.microsoft.com/en-us/library/5ft82fed(v=vs.80).aspx http://msdn.microsoft.com/en-us/library/5ft82fed(v=vs.80).as... [2] http://www.ffmpeg.org/platform.html http://www.ffmpeg.org/platform.html
- astrange 13y ago
  gcc mostly ignores restrict, though it's got a little better in recent versions. icc uses it a little more. But restrict is only good in specific situations - if you have three pointers, and #2 can alias #1 but not #3, there's no way to express that. It also tends to be used on function arguments, not at some higher up point of declaration. So when compilers inline the function and can see more global info about it, the restrict gets lost and optimization gets worse. I think some kind of stronger 'typedef' would be better.

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.