5 ms·

Doubling the speed of jpegtran with SIMD

117 points by jgrahamc 11y ago

guardian5x 11y ago
I wonder if they've considered using libjpeg-turbo instead of libjpeg9a, which comes with a lot of SIMD optimization and is regarded to be 2x-5x as fast as IJG's implementation.[1] [1] http://www.libjpeg-turbo.org/About/Performance http://www.libjpeg-turbo.org/About/Performance
- listic 11y ago
  My thought as well. As far as I understand, these intrinsics map to SSE instructions (they are 128-bit). One could use the later AVX (256-bit, found in server chips since 2011). Probably they decided to start with the lowest common denomintor of SSE, because they don't have AVX in all of their servers? The term SIMD is generic.
  - unwind 11y ago
    That is explicitly mentioned in the article: Note: we could also choose to use 256-bit wide YMM registers here, but that would only work on the newest CPUs, while gaining little performance. I'm not saying they're right and you're wrong, but you make it sound as if they never even considered AVX.
    - liotier 11y ago
      > Note: we could also choose to use 256-bit wide YMM registers here, but that would only work on the newest CPUs, while gaining little performance. Should that be an #ifdef ?
      - booblik 11y ago
        There is an #ifdef in the final code on github
      - repsilat 11y ago
        Maybe if the machine running the code is the machine that compiles it, or if you have a good way to send processor-specific binaries to the right places. More useful, I think, would be a runtime check far enough up the stack (i.e., away from tight loops) that it doesn't affect performance. Probably doesn't even need to be that high, it'll branch-predict correctly every time but the first iteration, and the binary bloat probably won't hurt your icache because the number of instructions you ever actually execute stays more or less the same.
  - xioxox 11y ago
    AVX 2 is required to get the wider integer instructions, so this would require Haswell processors.
    - deleted 11y ago
      [deleted]
- jgrahamc 11y ago
  We considered libjpeg-turbo, but the performance of jpegtran there is much unchanged. If you look at the Huffman encoding function it is exactly the same. Applying the optimizations to libjpeg-turbo also yield a 2x performance improvement for our usage.
chatman 11y ago
They should've included graphs to their article, e.g. to compare speedups at each compression level using histograms. Even tabulation of their results may have looked cool.
- deleted 11y ago
  [deleted]
pierrec 11y ago
I sort of expect a top-notch compiler to perform this automatically (especially if it allows profiling). The MSVC++ compiler has pretty impressive auto-vectorization, as I've verified several times by testing the performance of my DSP code with SIMD enabled and disabled. Just make sure your code facilitates auto-vectorization, and it should be more readable and future-proof while achieving the same result, assuming the compiler is smart enough. (Also, since this is CloudFlare, <insert rant and dream about SIMD happening in LuaJIT>... Thanks CloudFlare!)
- legulere 11y ago
  The problem is that often the compiler can't automatically vectorize because some preconditions are not met. The knowledge about those preconditions is mostly limited to compiler people and so far, by what I know, there's no static analysis tool that tells you why the compiler couldn't vectorize a loop.
  - claudius 11y ago
    The Intel compiler has various options to report autovectorisation success. You still have to go through them and follow the advice, of course, but by and large they are not entirely useless.
  - leecb 11y ago
    Clang can tell you why a loop wasn't vectorized with a couple of compiler flags: -Rpass-analysis=loop-vectorize -Rpass-missed=loop-vectorized http://llvm.org/docs/Vectorizers.html#diagnostics http://llvm.org/docs/Vectorizers.html#diagnostics
  - RogerL 11y ago
    MSVC also will report whether vectorization succeeded, and why it didn't if it failed.
  - flamedoge 11y ago
    do a profile run and I'll bet you it will insert as many runtime checks necessary to get around those precondition checks.
dahart 11y ago
Very nice! An independent but very useful way to speed up image batches, as log as you're working in batches and not one at a time: parallel jpegtran ::: *.jpg Combine it with these SIMD improvements, and your batch will be done before you hit enter.
- sloppycee 11y ago
  http://www.gnu.org/software/parallel/ http://www.gnu.org/software/parallel/
karim79 11y ago
While this is a great project from both an academic and performance perspective, the resulting images are substantially larger than ones produced using Mozjpeg. From the article: We at CloudFlare make sure that our servers run at top notch performance, so our customers' websites do as well!. Correct me if I'm wrong, but it does seem to me that this is of greater value to CloudFlare in terms of electricity savings than to CloudFlare's customers. Less computing time for CloudFlare at the expense of larger output files for CloudFlare's customers to serve, files which will potentially be served again and again and count against the customer's transfer quota. It might not seem like much, but it adds up when you consider how many times a single image in the wild can be downloaded. Consider the following example: # Original size is 21796912 bytes # jpegtran with SIMD jpegtran -copy none -optimize -progressive bigjpeg.jpg > bigjpeg_jpegtran.jpg # bigjpeg_jpegtran.jpg resulting size is 19771224 bytes # mozjpeg 3.1 mozjpeg -copy none -optimize -progressive bigjpeg.jpg > bigjpeg_mozjpeg.jpg # bigjpeg_mozjpeg.jpg size is 19328832 bytes That's a difference of 442KB! I'm not emphasizing the computing time here. I do not dispute that this is orders of magnitude faster than Mozjpeg, but isn't it worth doing the extra work to get a smaller file? That file could be served billions of times. My argument is simply that the extra computing effort in the beginning leads to much grander savings in the long run. In my (quick) testing Jpegtran's squishing performance is consistently less than that of Mozjpeg. So what, actually, is right thing to do in the end?
- 0x07c0 11y ago
  If they get larger file sizes then that probably means they are doing something wrong. Optimized a mpg encoder with SSE once. And larger file size was usually do to some lose of floating point precision. Going thorough the functions and comparing output from serial to vector function should give the bug. Fixing this stuff also can give some more speed up!

117 points by jgrahamc 11y ago

I wonder if they've considered using libjpeg-turbo instead of libjpeg9a, which comes with a lot of SIMD optimization and is regarded to be 2x-5x as fast as IJG's implementation.[1] [1] http://www.libjpeg-turbo.org/About/Performance http://www.libjpeg-turbo.org/About/Performance

listic 11y ago
My thought as well. As far as I understand, these intrinsics map to SSE instructions (they are 128-bit). One could use the later AVX (256-bit, found in server chips since 2011). Probably they decided to start with the lowest common denomintor of SSE, because they don't have AVX in all of their servers? The term SIMD is generic.
- unwind 11y ago
  That is explicitly mentioned in the article: Note: we could also choose to use 256-bit wide YMM registers here, but that would only work on the newest CPUs, while gaining little performance. I'm not saying they're right and you're wrong, but you make it sound as if they never even considered AVX.
  - liotier 11y ago
    > Note: we could also choose to use 256-bit wide YMM registers here, but that would only work on the newest CPUs, while gaining little performance. Should that be an #ifdef ?
    - booblik 11y ago
      There is an #ifdef in the final code on github
    - repsilat 11y ago
      Maybe if the machine running the code is the machine that compiles it, or if you have a good way to send processor-specific binaries to the right places. More useful, I think, would be a runtime check far enough up the stack (i.e., away from tight loops) that it doesn't affect performance. Probably doesn't even need to be that high, it'll branch-predict correctly every time but the first iteration, and the binary bloat probably won't hurt your icache because the number of instructions you ever actually execute stays more or less the same.
- xioxox 11y ago
  AVX 2 is required to get the wider integer instructions, so this would require Haswell processors.
  - deleted 11y ago
    [deleted]
jgrahamc 11y ago
We considered libjpeg-turbo, but the performance of jpegtran there is much unchanged. If you look at the Huffman encoding function it is exactly the same. Applying the optimizations to libjpeg-turbo also yield a 2x performance improvement for our usage.

chatman 11y ago

They should've included graphs to their article, e.g. to compare speedups at each compression level using histograms. Even tabulation of their results may have looked cool.

deleted 11y ago
[deleted]

pierrec 11y ago

I sort of expect a top-notch compiler to perform this automatically (especially if it allows profiling). The MSVC++ compiler has pretty impressive auto-vectorization, as I've verified several times by testing the performance of my DSP code with SIMD enabled and disabled. Just make sure your code facilitates auto-vectorization, and it should be more readable and future-proof while achieving the same result, assuming the compiler is smart enough. (Also, since this is CloudFlare, <insert rant and dream about SIMD happening in LuaJIT>... Thanks CloudFlare!)

legulere 11y ago
The problem is that often the compiler can't automatically vectorize because some preconditions are not met. The knowledge about those preconditions is mostly limited to compiler people and so far, by what I know, there's no static analysis tool that tells you why the compiler couldn't vectorize a loop.
- claudius 11y ago
  The Intel compiler has various options to report autovectorisation success. You still have to go through them and follow the advice, of course, but by and large they are not entirely useless.
- leecb 11y ago
  Clang can tell you why a loop wasn't vectorized with a couple of compiler flags: -Rpass-analysis=loop-vectorize -Rpass-missed=loop-vectorized http://llvm.org/docs/Vectorizers.html#diagnostics http://llvm.org/docs/Vectorizers.html#diagnostics
- RogerL 11y ago
  MSVC also will report whether vectorization succeeded, and why it didn't if it failed.
- flamedoge 11y ago
  do a profile run and I'll bet you it will insert as many runtime checks necessary to get around those precondition checks.

dahart 11y ago

Very nice! An independent but very useful way to speed up image batches, as log as you're working in batches and not one at a time: parallel jpegtran ::: *.jpg Combine it with these SIMD improvements, and your batch will be done before you hit enter.

sloppycee 11y ago
http://www.gnu.org/software/parallel/ http://www.gnu.org/software/parallel/

karim79 11y ago

While this is a great project from both an academic and performance perspective, the resulting images are substantially larger than ones produced using Mozjpeg. From the article: We at CloudFlare make sure that our servers run at top notch performance, so our customers' websites do as well!. Correct me if I'm wrong, but it does seem to me that this is of greater value to CloudFlare in terms of electricity savings than to CloudFlare's customers. Less computing time for CloudFlare at the expense of larger output files for CloudFlare's customers to serve, files which will potentially be served again and again and count against the customer's transfer quota. It might not seem like much, but it adds up when you consider how many times a single image in the wild can be downloaded. Consider the following example: # Original size is 21796912 bytes # jpegtran with SIMD jpegtran -copy none -optimize -progressive bigjpeg.jpg > bigjpeg_jpegtran.jpg # bigjpeg_jpegtran.jpg resulting size is 19771224 bytes # mozjpeg 3.1 mozjpeg -copy none -optimize -progressive bigjpeg.jpg > bigjpeg_mozjpeg.jpg # bigjpeg_mozjpeg.jpg size is 19328832 bytes That's a difference of 442KB! I'm not emphasizing the computing time here. I do not dispute that this is orders of magnitude faster than Mozjpeg, but isn't it worth doing the extra work to get a smaller file? That file could be served billions of times. My argument is simply that the extra computing effort in the beginning leads to much grander savings in the long run. In my (quick) testing Jpegtran's squishing performance is consistently less than that of Mozjpeg. So what, actually, is right thing to do in the end?

0x07c0 11y ago
If they get larger file sizes then that probably means they are doing something wrong. Optimized a mpg encoder with SSE once. And larger file size was usually do to some lose of floating point precision. Going thorough the functions and comparing output from serial to vector function should give the bug. Fixing this stuff also can give some more speed up!