Recherche avancée

Sur d’autres sites (9472)

• Announcing the world’s fastest VP8 decoder : ffvp8

  24 juillet 2010, par Dark Shikari — ffmpeg, google, speed, VP8

  Back when I originally reviewed VP8, I noted that the official decoder, libvpx, was rather slow. While there was no particular reason that it should be much faster than a good H.264 decoder, it shouldn’t have been that much slower either ! So, I set out with Ronald Bultje and David Conrad to make a better one in FFmpeg. This one would be community-developed and free from the beginning, rather than the proprietary code-dump that was libvpx. A few weeks ago the decoder was complete enough to be bit-exact with libvpx, making it the first independent free implementation of a VP8 decoder. Now, with the first round of optimizations complete, it should be ready for primetime. I’ll go into some detail about the development process, but first, let’s get to the real meat of this post : the benchmarks.

  We tested on two 1080p clips : Parkjoy, a live-action 1080p clip, and the Sintel trailer, a CGI 1080p clip. Testing was done using “time ffmpeg -vcodec libvpx or vp8 -i input -vsync 0 -an -f null -”. We all used the latest SVN FFmpeg at the time of this posting ; the last revision optimizing the VP8 decoder was r24471.

  

  As these benchmarks show, ffvp8 is clearly much faster than libvpx, particularly on 64-bit. It’s even faster by a large margin on Atom, despite the fact that we haven’t even begun optimizing for it. In many cases, ffvp8′s extra speed can make the difference between a video that plays and one that doesn’t, especially in modern browsers with software compositing engines taking up a lot of CPU time. Want to get faster playback of VP8 videos ? The next versions of FFmpeg-based players, like VLC, will include ffvp8. Want to get faster playback of WebM in your browser ? Lobby your browser developers to use ffvp8 instead of libvpx. I expect Chrome to switch first, as they already use libavcodec for most of their playback system.

  Keep in mind ffvp8 is not “done” — we will continue to improve it and make it faster. We still have a number of optimizations in the pipeline that aren’t committed yet.

  Developing ffvp8

  The initial challenge, primarily pioneered by David and Ronald, was constructing the core decoder and making it bit-exact to libvpx. This was rather challenging, especially given the lack of a real spec. Many parts of the spec were outright misleading and contradicted libvpx itself. It didn’t help that the suite of official conformance tests didn’t even cover all the features used by the official encoder ! We’ve already started adding our own conformance tests to deal with this. But I’ve complained enough in past posts about the lack of a spec ; let’s get onto the gritty details.

  The next step was adding SIMD assembly for all of the important DSP functions. VP8′s motion compensation and deblocking filter are by far the most CPU-intensive parts, much the same as in H.264. Unlike H.264, the deblocking filter relies on a lot of internal saturation steps, which are free in SIMD but costly in a normal C implementation, making the plain C code even slower. Of course, none of this is a particularly large problem ; any sane video decoder has all this stuff in SIMD.

  I tutored Ronald in x86 SIMD and wrote most of the motion compensation, intra prediction, and some inverse transforms. Ronald wrote the rest of the inverse transforms and a bit of the motion compensation. He also did the most difficult part : the deblocking filter. Deblocking filters are always a bit difficult because every one is different. Motion compensation, by comparison, is usually very similar regardless of video format ; a 6-tap filter is a 6-tap filter, and most of the variation going on is just the choice of numbers to multiply by.

  The biggest challenge in an SIMD deblocking filter is to avoid unpacking, that is, going from 8-bit to 16-bit. Many operations in deblocking filters would naively appear to require more than 8-bit precision. A simple example in the case of x86 is abs(a-b), where a and b are 8-bit unsigned integers. The result of “a-b” requires a 9-bit signed integer (it can be anywhere from -255 to 255), so it can’t fit in 8-bit. But this is quite possible to do without unpacking : (satsub(a,b) | satsub(b,a)), where “satsub” performs a saturating subtract on the two values. If the value is positive, it yields the result ; if the value is negative, it yields zero. Oring the two together yields the desired result. This requires 4 ops on x86 ; unpacking would probably require at least 10, including the unpack and pack steps.

  After the SIMD came optimizing the C code, which still took a significant portion of the total runtime. One of my biggest optimizations was adding aggressive “smart” prefetching to reduce cache misses. ffvp8 prefetches the reference frames (PREVIOUS, GOLDEN, and ALTREF)… but only the ones which have been used reasonably often this frame. This lets us prefetch everything we need without prefetching things that we probably won’t use. libvpx very often encodes frames that almost never (but not quite never) use GOLDEN or ALTREF, so this optimization greatly reduces time spent prefetching in a lot of real videos. There are of course countless other optimizations we made that are too long to list here as well, such as David’s entropy decoder optimizations. I’d also like to thank Eli Friedman for his invaluable help in benchmarking a lot of these changes.

  What next ? Altivec (PPC) assembly is almost nonexistent, with the only functions being David’s motion compensation code. NEON (ARM) is completely nonexistent : we’ll need that to be fast on mobile devices as well. Of course, all this will come in due time — and as always — patches welcome !

  Appendix : the raw numbers

  Here’s the raw numbers (in fps) for the graphs at the start of this post, with standard error values :

  Core i7 620QM (1.6Ghz), Windows 7, 32-bit :
  Parkjoy ffvp8 : 44.58 0.44
  Parkjoy libvpx : 33.06 0.23
  Sintel ffvp8 : 74.26 1.18
  Sintel libvpx : 56.11 0.96

  Core i5 520M (2.4Ghz), Linux, 64-bit :
  Parkjoy ffvp8 : 68.29 0.06
  Parkjoy libvpx : 41.06 0.04
  Sintel ffvp8 : 112.38 0.37
  Sintel libvpx : 69.64 0.09

  Core 2 T9300 (2.5Ghz), Mac OS X 10.6.4, 64-bit :
  Parkjoy ffvp8 : 54.09 0.02
  Parkjoy libvpx : 33.68 0.01
  Sintel ffvp8 : 87.54 0.03
  Sintel libvpx : 52.74 0.04

  Core Duo (2Ghz), Mac OS X 10.6.4, 32-bit :
  Parkjoy ffvp8 : 21.31 0.02
  Parkjoy libvpx : 17.96 0.00
  Sintel ffvp8 : 41.24 0.01
  Sintel libvpx : 29.65 0.02

  Atom N270 (1.6Ghz), Linux, 32-bit :
  Parkjoy ffvp8 : 15.29 0.01
  Parkjoy libvpx : 12.46 0.01
  Sintel ffvp8 : 26.87 0.05
  Sintel libvpx : 20.41 0.02

• Announcing the world’s fastest VP8 decoder : ffvp8

  24 juillet 2010, par Dark Shikari — VP8, ffmpeg, google, speed

  Back when I originally reviewed VP8, I noted that the official decoder, libvpx, was rather slow. While there was no particular reason that it should be much faster than a good H.264 decoder, it shouldn’t have been that much slower either ! So, I set out with Ronald Bultje and David Conrad to make a better one in FFmpeg. This one would be community-developed and free from the beginning, rather than the proprietary code-dump that was libvpx. A few weeks ago the decoder was complete enough to be bit-exact with libvpx, making it the first independent free implementation of a VP8 decoder. Now, with the first round of optimizations complete, it should be ready for primetime. I’ll go into some detail about the development process, but first, let’s get to the real meat of this post : the benchmarks.

  We tested on two 1080p clips : Parkjoy, a live-action 1080p clip, and the Sintel trailer, a CGI 1080p clip. Testing was done using “time ffmpeg -vcodec libvpx or vp8 -i input -vsync 0 -an -f null -”. We all used the latest SVN FFmpeg at the time of this posting ; the last revision optimizing the VP8 decoder was r24471.

  

  As these benchmarks show, ffvp8 is clearly much faster than libvpx, particularly on 64-bit. It’s even faster by a large margin on Atom, despite the fact that we haven’t even begun optimizing for it. In many cases, ffvp8′s extra speed can make the difference between a video that plays and one that doesn’t, especially in modern browsers with software compositing engines taking up a lot of CPU time. Want to get faster playback of VP8 videos ? The next versions of FFmpeg-based players, like VLC, will include ffvp8. Want to get faster playback of WebM in your browser ? Lobby your browser developers to use ffvp8 instead of libvpx. I expect Chrome to switch first, as they already use libavcodec for most of their playback system.

  Keep in mind ffvp8 is not “done” — we will continue to improve it and make it faster. We still have a number of optimizations in the pipeline that aren’t committed yet.

  Developing ffvp8

  The initial challenge, primarily pioneered by David and Ronald, was constructing the core decoder and making it bit-exact to libvpx. This was rather challenging, especially given the lack of a real spec. Many parts of the spec were outright misleading and contradicted libvpx itself. It didn’t help that the suite of official conformance tests didn’t even cover all the features used by the official encoder ! We’ve already started adding our own conformance tests to deal with this. But I’ve complained enough in past posts about the lack of a spec ; let’s get onto the gritty details.

  The next step was adding SIMD assembly for all of the important DSP functions. VP8′s motion compensation and deblocking filter are by far the most CPU-intensive parts, much the same as in H.264. Unlike H.264, the deblocking filter relies on a lot of internal saturation steps, which are free in SIMD but costly in a normal C implementation, making the plain C code even slower. Of course, none of this is a particularly large problem ; any sane video decoder has all this stuff in SIMD.

  I tutored Ronald in x86 SIMD and wrote most of the motion compensation, intra prediction, and some inverse transforms. Ronald wrote the rest of the inverse transforms and a bit of the motion compensation. He also did the most difficult part : the deblocking filter. Deblocking filters are always a bit difficult because every one is different. Motion compensation, by comparison, is usually very similar regardless of video format ; a 6-tap filter is a 6-tap filter, and most of the variation going on is just the choice of numbers to multiply by.

  The biggest challenge in an SIMD deblocking filter is to avoid unpacking, that is, going from 8-bit to 16-bit. Many operations in deblocking filters would naively appear to require more than 8-bit precision. A simple example in the case of x86 is abs(a-b), where a and b are 8-bit unsigned integers. The result of “a-b” requires a 9-bit signed integer (it can be anywhere from -255 to 255), so it can’t fit in 8-bit. But this is quite possible to do without unpacking : (satsub(a,b) | satsub(b,a)), where “satsub” performs a saturating subtract on the two values. If the value is positive, it yields the result ; if the value is negative, it yields zero. Oring the two together yields the desired result. This requires 4 ops on x86 ; unpacking would probably require at least 10, including the unpack and pack steps.

  After the SIMD came optimizing the C code, which still took a significant portion of the total runtime. One of my biggest optimizations was adding aggressive “smart” prefetching to reduce cache misses. ffvp8 prefetches the reference frames (PREVIOUS, GOLDEN, and ALTREF)… but only the ones which have been used reasonably often this frame. This lets us prefetch everything we need without prefetching things that we probably won’t use. libvpx very often encodes frames that almost never (but not quite never) use GOLDEN or ALTREF, so this optimization greatly reduces time spent prefetching in a lot of real videos. There are of course countless other optimizations we made that are too long to list here as well, such as David’s entropy decoder optimizations. I’d also like to thank Eli Friedman for his invaluable help in benchmarking a lot of these changes.

  What next ? Altivec (PPC) assembly is almost nonexistent, with the only functions being David’s motion compensation code. NEON (ARM) is completely nonexistent : we’ll need that to be fast on mobile devices as well. Of course, all this will come in due time — and as always — patches welcome !

  Appendix : the raw numbers

  Here’s the raw numbers (in fps) for the graphs at the start of this post, with standard error values :

  Core i7 620QM (1.6Ghz), Windows 7, 32-bit :
  Parkjoy ffvp8 : 44.58 0.44
  Parkjoy libvpx : 33.06 0.23
  Sintel ffvp8 : 74.26 1.18
  Sintel libvpx : 56.11 0.96

  Core i5 520M (2.4Ghz), Linux, 64-bit :
  Parkjoy ffvp8 : 68.29 0.06
  Parkjoy libvpx : 41.06 0.04
  Sintel ffvp8 : 112.38 0.37
  Sintel libvpx : 69.64 0.09

  Core 2 T9300 (2.5Ghz), Mac OS X 10.6.4, 64-bit :
  Parkjoy ffvp8 : 54.09 0.02
  Parkjoy libvpx : 33.68 0.01
  Sintel ffvp8 : 87.54 0.03
  Sintel libvpx : 52.74 0.04

  Core Duo (2Ghz), Mac OS X 10.6.4, 32-bit :
  Parkjoy ffvp8 : 21.31 0.02
  Parkjoy libvpx : 17.96 0.00
  Sintel ffvp8 : 41.24 0.01
  Sintel libvpx : 29.65 0.02

  Atom N270 (1.6Ghz), Linux, 32-bit :
  Parkjoy ffvp8 : 15.29 0.01
  Parkjoy libvpx : 12.46 0.01
  Sintel ffvp8 : 26.87 0.05
  Sintel libvpx : 20.41 0.02

• Beware the builtins

  14 janvier 2010, par Mans — Compilers

  GCC includes a large number of builtin functions allegedly providing optimised code for common operations not easily expressed directly in C. Rather than taking such claims at face value (this is GCC after all), I decided to conduct a small investigation to see how well a few of these functions are actually implemented for various targets.

  For my test, I selected the following functions :

  • __builtin_bswap32 : Byte-swap a 32-bit word.
  • __builtin_bswap64 : Byte-swap a 64-bit word.
  • __builtin_clz : Count leading zeros in a word.
  • __builtin_ctz : Count trailing zeros in a word.
  • __builtin_prefetch : Prefetch data into cache.

  To test the quality of these builtins, I wrapped each in a normal function, then compiled the code for these targets :

  • ARMv7
  • AVR32
  • MIPS
  • MIPS64
  • PowerPC
  • PowerPC64
  • x86
  • x86_64

  In all cases I used compiler flags were -O3 -fomit-frame-pointer plus any flags required to select a modern CPU model.
  

  ARM

  Both __builtin_clz and __builtin_prefetch generate the expected CLZ and PLD instructions respectively. The code for __builtin_ctz is reasonable for ARMv6 and earlier :

  rsb     r3, r0, #0
  and     r0, r3, r0
  clz     r0, r0
  rsb     r0, r0, #31
  

  For ARMv7 (in fact v6T2), however, using the new bit-reversal instruction would have been better :

  rbit    r0, r0
  clz     r0, r0
  

  I suspect this is simply a matter of the function not yet having been updated for ARMv7, which is perhaps even excusable given the relatively rare use cases for it.

  The byte-reversal functions are where it gets shocking. Rather than use the REV instruction found from ARMv6 on, both of them generate external calls to __bswapsi2 and __bswapdi2 in libgcc, which is plain C code :

  SItype
  __bswapsi2 (SItype u)
  
    return ((((u) & 0xff000000) >> 24)
            | (((u) & 0x00ff0000) >>  8)
            | (((u) & 0x0000ff00) <<  8)
            | (((u) & 0x000000ff) << 24)) ;
  
  DItype
  
  __bswapdi2 (DItype u)
  
  
  
     return ((((u) & 0xff00000000000000ull) >> 56)
  
            | (((u) & 0x00ff000000000000ull) >> 40)
  
            | (((u) & 0x0000ff0000000000ull) >> 24)
  
            | (((u) & 0x000000ff00000000ull) >>  8)
  
            | (((u) & 0x00000000ff000000ull) <<  8)
  
            | (((u) & 0x0000000000ff0000ull) << 24)
  
            | (((u) & 0x000000000000ff00ull) << 40)
  
            | (((u) & 0x00000000000000ffull) << 56)) ;
  
  
  

  While the 32-bit version compiles to a reasonable-looking shift/mask/or job, the 64-bit one is a real WTF. Brace yourselves :

  push    r4, r5, r6, r7, r8, r9, sl, fp
  mov     r5, #0
  mov     r6, #65280 ; 0xff00
  sub     sp, sp, #40 ; 0x28
  and     r7, r0, r5
  and     r8, r1, r6
  str     r7, [sp, #8]
  str     r8, [sp, #12]
  mov     r9, #0
  mov     r4, r1
  and     r5, r0, r9
  mov     sl, #255 ; 0xff
  ldr     r9, [sp, #8]
  and     r6, r4, sl
  mov     ip, #16711680 ; 0xff0000
  str     r5, [sp, #16]
  str     r6, [sp, #20]
  lsl     r2, r0, #24
  and     ip, ip, r1
  lsr     r7, r4, #24
  mov     r1, #0
  lsr     r5, r9, #24
  mov     sl, #0
  mov     r9, #-16777216 ; 0xff000000
  and     fp, r0, r9
  lsr     r6, ip, #8
  orr     r9, r7, r1
  and     ip, r4, sl
  orr     sl, r1, r2
  str     r6, [sp]
  str     r9, [sp, #32]
  str     sl, [sp, #36] ; 0x24
  add     r8, sp, #32
  ldm     r8, r7, r8
  str     r1, [sp, #4]
  ldm     sp, r9, sl
  orr     r7, r7, r9
  orr     r8, r8, sl
  str     r7, [sp, #32]
  str     r8, [sp, #36] ; 0x24
  mov     r3, r0
  mov     r7, #16711680 ; 0xff0000
  mov     r8, #0
  and     r9, r3, r7
  and     sl, r4, r8
  ldr     r0, [sp, #16]
  str     fp, [sp, #24]
  str     ip, [sp, #28]
  stm     sp, r9, sl
  ldr     r7, [sp, #20]
  ldr     sl, [sp, #12]
  ldr     fp, [sp, #12]
  ldr     r8, [sp, #28]
  lsr     r0, r0, #8
  orr     r7, r0, r7, lsl #24
  lsr     r6, sl, #24
  orr     r5, r5, fp, lsl #8
  lsl     sl, r8, #8
  mov     fp, r7
  add     r8, sp, #32
  ldm     r8, r7, r8
  orr     r6, r6, r8
  ldr     r8, [sp, #20]
  ldr     r0, [sp, #24]
  orr     r5, r5, r7
  lsr     r8, r8, #8
  orr     sl, sl, r0, lsr #24
  mov     ip, r8
  ldr     r0, [sp, #4]
  orr     fp, fp, r5
  ldr     r5, [sp, #24]
  orr     ip, ip, r6
  ldr     r6, [sp]
  lsl     r9, r5, #8
  lsl     r8, r0, #24
  orr     fp, fp, r9
  lsl     r3, r3, #8
  orr     r8, r8, r6, lsr #8
  orr     ip, ip, sl
  lsl     r7, r6, #24
  and     r5, r3, #16711680 ; 0xff0000
  orr     r7, r7, fp
  orr     r8, r8, ip
  orr     r4, r1, r7
  orr     r5, r5, r8
  mov     r9, r6
  mov     r1, r5
  mov     r0, r4
  add     sp, sp, #40 ; 0x28
  pop     r4, r5, r6, r7, r8, r9, sl, fp
  bx      lr
  

  That’s right, 91 instructions to move 8 bytes around a bit. GCC definitely has a problem with 64-bit numbers. It is perhaps worth noting that the bswap_64 macro in glibc splits the 64-bit value into 32-bit halves which are then reversed independently, thus side-stepping this weakness of gcc.

  As a side note, ARM RVCT (armcc) compiles those functions perfectly into one and two REV instructions, respectively.

  AVR32

  There is not much to report here. The latest gcc version available is 4.2.4, which doesn’t appear to have the bswap functions. The other three are handled nicely, even using a bit-reverse for __builtin_ctz.

  MIPS / MIPS64

  The situation MIPS is similar to ARM. Both bswap builtins result in external libgcc calls, the rest giving sensible code.

  PowerPC

  I scarcely believe my eyes, but this one is actually not bad. The PowerPC has no byte-reversal instructions, yet someone seems to have taken the time to teach gcc a good instruction sequence for this operation. The PowerPC does have some powerful rotate-and-mask instructions which come in handy here. First the 32-bit version :

  rotlwi  r0,r3,8
  rlwimi  r0,r3,24,0,7
  rlwimi  r0,r3,24,16,23
  mr      r3,r0
  blr
  

  The 64-bit byte-reversal simply applies the above code on each half of the value :

  rotlwi  r0,r3,8
  rlwimi  r0,r3,24,0,7
  rlwimi  r0,r3,24,16,23
  rotlwi  r3,r4,8
  rlwimi  r3,r4,24,0,7
  rlwimi  r3,r4,24,16,23
  mr      r4,r0
  blr
  

  Although I haven’t analysed that code carefully, it looks pretty good.

  PowerPC64

  Doing 64-bit operations is easier on a 64-bit CPU, right ? For you and me perhaps, but not for gcc. Here __builtin_bswap64 gives us the now familiar __bswapdi2 call, and while not as bad as the ARM version, it is not pretty :

  rldicr  r0,r3,8,55
  rldicr  r10,r3,56,7
  rldicr  r0,r0,56,15
  rldicl  r11,r3,8,56
  rldicr  r9,r3,16,47
  or      r11,r10,r11
  rldicr  r9,r9,48,23
  rldicl  r10,r0,24,40
  rldicr  r0,r3,24,39
  or      r11,r11,r10
  rldicl  r9,r9,40,24
  rldicr  r0,r0,40,31
  or      r9,r11,r9
  rlwinm  r10,r3,0,0,7
  rldicl  r0,r0,56,8
  or      r0,r9,r0
  rldicr  r10,r10,8,55
  rlwinm  r11,r3,0,8,15
  or      r0,r0,r10
  rldicr  r11,r11,24,39
  rlwinm  r3,r3,0,16,23
  or      r0,r0,r11
  rldicr  r3,r3,40,23
  or      r3,r0,r3
  blr
  

  That is 6 times longer than the (presumably) hand-written 32-bit version.

  x86 / x86_64

  As one might expect, results on x86 are good. All the tested functions use the available special instructions. One word of caution though : the bit-counting instructions are very slow on some implementations, specifically the Atom, AMD chips, and the notoriously slow Pentium4E.

  Conclusion

  In conclusion, I would say gcc builtins can be useful to avoid fragile inline assembler. Before using them, however, one should make sure they are not in fact harmful on the required targets. Not even those builtins mapping directly to CPU instructions can be trusted.