Recherche avancée

Sur d’autres sites (3950)

• Bit-field badness

  30 janvier 2010, par Mans — Compilers, Optimisation

  Consider the following C code which is based on an real-world situation.

  struct bf1_31 
      unsigned a:1 ;
      unsigned b:31 ;
   ;
  void func(struct bf1_31 *p, int n, int a)
  
  
  
      int i = 0 ;
  
      do 
  
          if (p[i].a)
  
              p[i].b += a ;
  
       while (++i < n) ;
  
  
  

  How would we best write this in ARM assembler ? This is how I would do it :
  

  func :
          ldr     r3,  [r0], #4
          tst     r3,  #1
          add     r3,  r3,  r2,  lsl #1
          strne   r3,  [r0, #-4]
          subs    r1,  r1,  #1
          bgt     func
          bx      lr
  

  The add instruction is unconditional to avoid a dependency on the comparison. Unrolling the loop would mask the latency of the ldr instruction as well, but that is outside the scope of this experiment.

  Now compile this code with gcc -march=armv5te -O3 and watch in horror :

  func :
          push    r4
          mov     ip, #0
          mov     r4, r2
  loop :
          ldrb    r3, [r0]
          add     ip, ip, #1
          tst     r3, #1
          ldrne   r3, [r0]
          andne   r2, r3, #1
          addne   r3, r4, r3, lsr #1
          orrne   r2, r2, r3, lsl #1
          strne   r2, [r0]
          cmp     ip, r1
          add     r0, r0, #4
          blt     loop
          pop     r4
          bx      lr
  

  This is nothing short of awful :

  • The same value is loaded from memory twice.
  • A complicated mask/shift/or operation is used where a simple shifted add would suffice.
  • Write-back addressing is not used.
  • The loop control counts up and compares instead of counting down.
  • Useless mov in the prologue ; swapping the roles or r2 and r4 would avoid this.
  • Using lr in place of r4 would allow the return to be done with pop {pc}, saving one instruction (ignoring for the moment that no callee-saved registers are needed at all).

  Even for this trivial function the gcc-generated code is more than twice the optimal size and slower by approximately the same factor.

  The main issue I wanted to illustrate is the poor handling of bit-fields by gcc. When accessing bitfields from memory, gcc issues a separate load for each field even when they are contained in the same aligned memory word. Although each load after the first will most likely hit L1 cache, this is still bad for several reasons :

  • Loads have typically two or three cycles result latency compared to one cycle for data processing instructions. Any bit-field can be extracted from a register with two shifts, and on ARM the second of these can generally be achieved using a shifted second operand to a following instruction. The ARMv6T2 instruction set also adds the SBFX and UBFX instructions for extracting any signed or unsigned bit-field in one cycle.
  • Most CPUs have more data processing units than load/store units. It is thus more likely for an ALU instruction than a load/store to issue without delay on a superscalar processor.
  • Redundant memory accesses can trigger early flushing of store buffers rendering these less efficient.

  No gcc bashing is complete without a comparison with another compiler, so without further ado, here is the ARM RVCT output (armcc --cpu 5te -O3) :

  func :
          mov     r3, #0
          push    r4, lr
  loop :
          ldr     ip, [r0, r3, lsl #2]
          tst     ip, #1
          addne   ip, ip, r2, lsl #1
          strne   ip, [r0, r3, lsl #2]
          add     r3, r3, #1
          cmp     r3, r1
          blt     loop
          pop     r4, pc
  

  This is much better, the core loop using only one instruction more than my version. The loop control is counting up, but at least this register is reused as offset for the memory accesses. More remarkable is the push/pop of two registers that are never used. I had not expected to see this from RVCT.

  Even the best compilers are still no match for a human.

• Changes to the WebM Open Source License

  5 juin 2010, par noreply@blogger.com (John Luther)

  You’ll see on the WebM license page and in our source code repositories that we’ve made a small change to our open source license. There were a couple of issues that popped up after we released WebM at Google I/O a couple weeks ago, specifically around how the patent clause was written.

  As it was originally written, if a patent action was brought against Google, the patent license terminated. This provision itself is not unusual in an OSS license, and similar provisions exist in the 2nd Apache License and in version 3 of the GPL. The twist was that ours terminated "any" rights and not just rights to the patents, which made our license GPLv3 and GPLv2 incompatible. Also, in doing this, we effectively created a potentially new open source copyright license, something we are loath to do.

  Using patent language borrowed from both the Apache and GPLv3 patent clauses, in this new iteration of the patent clause we’ve decoupled patents from copyright, thus preserving the pure BSD nature of the copyright license. This means we are no longer creating a new open source copyright license, and the patent grant can exist on its own. Additionally, we have updated the patent grant language to make it clearer that the grant includes the right to modify the code and give it to others. (We’ve updated the licensing FAQ to reflect these changes as well.)

  We’ve also added a definition for the "this implementation" language, to make that more clear.

  Thanks for your patience as we worked through this, and we hope you like, enjoy and (most importantly) use WebM and join with us in creating more freedom online. We had a lot of help on these changes, so thanks to our friends in open source and free software who traded many emails, often at odd hours, with us.

  Chris DiBona is the Open Source Programs Manager at Google.

  

• VP8 And FFmpeg

  18 juin 2010, par Multimedia Mike — VP8

  UPDATE, 2010-06-17 : You don’t need to struggle through these instructions anymore. libvpx 0.9.1 and FFmpeg 0.6 work together much better. Please see this post for simple instructions on getting up and running quickly.

  Let’s take the VP8 source code (in Google’s new libvpx library) for a spin ; get it to compile and hook it up to FFmpeg. I am hesitant to publish specific instructions for building in the somewhat hackish manner available on day 1 (download FFmpeg at a certain revision and apply a patch) since that kind of post has a tendency to rise in Google rankings. I will just need to remember to update this post after the library patches are applied to the official FFmpeg tree.

  Statement of libvpx’s Relationship to FFmpeg
  I don’t necessarily speak officially for FFmpeg. But I’ve been with the project long enough to explain how certain things work.

  Certainly, some may wonder if FFmpeg will incorporate Google’s newly open sourced libvpx library into FFmpeg. In the near term, FFmpeg will support encoding and decoding VP8 via external library as it does with a number of other libraries (most popularly, libx264). FFmpeg will not adopt the code for its own codebase, even if the license may allow it. That just isn’t how the FFmpeg crew rolls.

  In the longer term, expect the FFmpeg project to develop an independent, interoperable implementation of the VP8 decoder. Sometime after that, there may also be an independent VP8 encoder as well.

  Building libvpx
  Download and build libvpx. This is a basic ’configure && make’ process. The build process creates a static library, a bunch of header files, and 14 utilities. A bunch of these utilities operate on a file format called IVF which is apparently a simple transport method for VP8. I have recorded the file format on the wiki.

  We could use a decoder for this in the FFmpeg code base for testing VP8 in the future. Who’s game ? Just as I was proofreading this post, I saw that David Conrad has sent an IVF demuxer to the ffmpeg-devel list.

  There doesn’t seem to be a ’make install’ step for the library. Instead, go into the overly long directory (on my system, this is generated as vpx-vp8-nopost-nodocs-generic-gnu-v0.9.0), copy the contents of include/ to /usr/local/include and the static library in lib/ to /usr/local/lib .

  Building FFmpeg with libvpx
  Download FFmpeg source code at the revision specified or take your chances with the latest version (as I did). Download and apply provided patches. This part hurts since there is one diff per file. Most of them applied for me.

  Configure FFmpeg with 'configure --enable-libvpx_vp8 --enable-pthreads'. Ideally, this should yield no complaints and ’libvpx_vp8’ should show up in the enabled decoders and encoders sections. The library apparently relies on threading which is why '--enable-pthreads' is necessary. After I did this, I was able to create a new webm/VP8/Vorbis file simply with :

   ffmpeg -i input_file output_file.webm
  

  Unfortunately, I can’t complete the round trip as decoding doesn’t seem to work. Passing the generated .webm file back into FFmpeg results in a bunch of errors of this format :

  [libvpx_vp8 @ 0x8c4ab20]v0.9.0
  [libvpx_vp8 @ 0x8c4ab20]Failed to initialize decoder : Codec does not implement requested capability
  

  Maybe this is the FFmpeg revision mismatch biting me.

  FFmpeg Presets
  FFmpeg features support for preset files which contain collections of tuning options to be loaded into the program. Google provided some presets along with their FFmpeg patches :

  • 1080p50
  • 1080p
  • 360p
  • 720p50
  • 720p

  To invoke one of these (assuming the program has been installed via ’make install’ so that the presets are in the right place) :

   ffmpeg -i input_file -vcodec libvpx_vp8 -vpre 720p output_file.webm
  

  This will use a set of parameters that are known to do well when encoding a 720p video.

  Code Paths
  One of goals with this post was to visualize a call graph after I got the decoder hooked up to FFmpeg. Fortunately, this recon is greatly simplified by libvpx’s simple_decoder utility. Steps :

  • Build libvpx with --enable-gprof
  • Run simple_decoder on an IVF file
  • Get the pl_from_gprof.pl and dot_from_pl.pl scripts frome Graphviz’s gprof filters
  • gprof simple_decoder | ./pl_from_gprof.pl | ./dot_from_pl.pl > 001.dot
  • Remove the 2 [graph] and 1 [node] modifiers from the dot file (they only make the resulting graph very hard to read)
  • dot -Tpng 001.dot > 001.png

  Here are call graphs generated from decoding test vectors 001 and 017.

  
  

  

  Like this, only much larger and scarier (click for full graph)

  
  

  It’s funny to see several functions calling an empty bubble. Probably nothing to worry about. More interesting is the fact that a lot of function_c() functions are called. The ’_c’ at the end is important— that generally indicates that there are (or could be) SIMD-optimized versions. I know this codebase has plenty of assembly. All of the x86 ASM files appear to be written such that they could be compiled with NASM.

  Leftovers
  One interesting item in the code was vpx_scale/leapster. Is this in reference to the Leapster handheld educational gaming unit ? Based on this item from 2005 (archive.org copy), some Leapster titles probably used VP6. This reminds me of finding references to the PlayStation in Duck/On2’s original VpVision source release. I don’t know of any PlayStation games that used Duck’s original codecs but with thousands to choose from, it’s possible that we may find a few some day.