Recherche avancée

Sur d’autres sites (9332)

• Anatomy of an optimization : H.264 deblocking

  26 mai 2010, par Dark Shikari — H.264, assembly, development, speed, x264

  As mentioned in the previous post, H.264 has an adaptive deblocking filter. But what exactly does that mean — and more importantly, what does it mean for performance ? And how can we make it as fast as possible ? In this post I’ll try to answer these questions, particularly in relation to my recent deblocking optimizations in x264.

  H.264′s deblocking filter has two steps : strength calculation and the actual filter. The first step calculates the parameters for the second step. The filter runs on all the edges in each macroblock. That’s 4 vertical edges of length 16 pixels and 4 horizontal edges of length 16 pixels. The vertical edges are filtered first, from left to right, then the horizontal edges, from top to bottom (order matters !). The leftmost edge is the one between the current macroblock and the left macroblock, while the topmost edge is the one between the current macroblock and the top macroblock.

  Here’s the formula for the strength calculation in progressive mode. The highest strength that applies is always selected.

  If we’re on the edge between an intra macroblock and any other macroblock : Strength 4
  If we’re on an internal edge of an intra macroblock : Strength 3
  If either side of a 4-pixel-long edge has residual data : Strength 2
  If the motion vectors on opposite sides of a 4-pixel-long edge are at least a pixel apart (in either x or y direction) or the reference frames aren’t the same : Strength 1
  Otherwise : Strength 0 (no deblocking)

  These values are then thrown into a lookup table depending on the quantizer : higher quantizers have stronger deblocking. Then the actual filter is run with the appropriate parameters. Note that Strength 4 is actually a special deblocking mode that performs a much stronger filter and affects more pixels.

  One can see somewhat intuitively why these strengths are chosen. The deblocker exists to get rid of sharp edges caused by the block-based nature of H.264, and so the strength depends on what exists that might cause such sharp edges. The strength calculation is a way to use existing data from the video stream to make better decisions during the deblocking process, improving compression and quality.

  Both the strength calculation and the actual filter (not described here) are very complex if naively implemented. The latter can be SIMD’d with not too much difficulty ; no H.264 decoder can get away with reasonable performance without such a thing. But what about optimizing the strength calculation ? A quick analysis shows that this can be beneficial as well.

  Since we have to check both horizontal and vertical edges, we have to check up to 32 pairs of coefficient counts (for residual), 16 pairs of reference frame indices, and 128 motion vector values (counting x and y as separate values). This is a lot of calculation ; a naive implementation can take 500-1000 clock cycles on a modern CPU. Of course, there’s a lot of shortcuts we can take. Here’s some examples :

  • If the macroblock uses the 8×8 transform, we only need to check 2 edges in each direction instead of 4, because we don’t deblock inside of the 8×8 blocks.
  • If the macroblock is a P-skip, we only have to check the first edge in each direction, since there’s guaranteed to be no motion vector differences, reference frame differences, or residual inside of the macroblock.
  • If the macroblock has no residual at all, we can skip that check.
  • If we know the partition type of the macroblock, we can do motion vector checks only along the edges of the partitions.
  • If the effective quantizer is so low that no deblocking would be performed no matter what, don’t bother calculating the strength.

  But even all of this doesn’t save us from ourselves. We still have to iterate over a ton of edges, checking each one. Stuff like the partition-checking logic greatly complicates the code and adds overhead even as it reduces the number of checks. And in many cases decoupling the checks to add such logic will make it slower : if the checks are coupled, we can avoid doing a motion vector check if there’s residual, since Strength 2 overrides Strength 1.

  But wait. What if we could do this in SIMD, just like the actual loopfilter itself ? Sure, it seems more of a problem for C code than assembly, but there aren’t any obvious things in the way. Many years ago, Loren Merritt (pengvado) wrote the first SIMD implementation that I know of (for ffmpeg’s decoder) ; it is quite fast, so I decided to work on porting the idea to x264 to see if we could eke out a bit more speed here as well.

  Before I go over what I had to do to make this change, let me first describe how deblocking is implemented in x264. Since the filter is a loopfilter, it acts “in loop” and must be done in both the encoder and decoder — hence why x264 has it too, not just decoders. At the end of encoding one row of macroblocks, x264 goes back and deblocks the row, then performs half-pixel interpolation for use in encoding the next frame.

  We do it per-row for reasons of cache coherency : deblocking accesses a lot of pixels and a lot of code that wouldn’t otherwise be used, so it’s more efficient to do it in a single pass as opposed to deblocking each macroblock immediately after encoding. Then half-pixel interpolation can immediately re-use the resulting data.

  Now to the change. First, I modified deblocking to implement a subset of the macroblock_cache_load function : spend an extra bit of effort loading the necessary data into a data structure which is much simpler to address — as an assembly implementation would need (x264_macroblock_cache_load_deblock). Then I massively cleaned up deblocking to move all of the core strength-calculation logic into a single, small function that could be converted to assembly (deblock_strength_c). Finally, I wrote the assembly functions and worked with Loren to optimize them. Here’s the result.

  And the timings for the resulting assembly function on my Core i7, in cycles :

  deblock_strength_c : 309
  deblock_strength_mmx : 79
  deblock_strength_sse2 : 37
  deblock_strength_ssse3 : 33

  Now that is a seriously nice improvement. 33 cycles on average to perform that many comparisons–that’s absurdly low, especially considering the SIMD takes no branchy shortcuts : it always checks every single edge ! I walked over to my performance chart and happily crossed off a box.

  But I had a hunch that I could do better. Remember, as mentioned earlier, we’re reloading all that data back into our data structures in order to address it. This isn’t that slow, but takes enough time to significantly cut down on the gain of the assembly code. And worse, less than a row ago, all this data was in the correct place to be used (when we just finished encoding the macroblock) ! But if we did the deblocking right after encoding each macroblock, the cache issues would make it too slow to be worth it (yes, I tested this). So I went back to other things, a bit annoyed that I couldn’t get the full benefit of the changes.

  Then, yesterday, I was talking with Pascal, a former Xvid dev and current video hacker over at Google, about various possible x264 optimizations. He had seen my deblocking changes and we discussed that a bit as well. Then two lines hit me like a pile of bricks :

  <_skal_> tried computing the strength at least ?
  <_skal_> while it’s fresh

  Why hadn’t I thought of that ? Do the strength calculation immediately after encoding each macroblock, save the result, and then go pick it up later for the main deblocking filter. Then we can use the data right there and then for strength calculation, but we don’t have to do the whole deblock process until later.

  I went and implemented it and, after working my way through a horde of bugs, eventually got a working implementation. A big catch was that of slices : deblocking normally acts between slices even though normal encoding does not, so I had to perform extra munging to get that to work. By midday today I was able to go cross yet another box off on the performance chart. And now it’s committed.

  Sometimes chatting for 10 minutes with another developer is enough to spot the idea that your brain somehow managed to miss for nearly a straight week.

  NB : the performance chart is on a specific test clip at a specific set of settings (super fast settings) relevant to the company I work at, so it isn’t accurate nor complete for, say, default settings.

  Update : Here’s a higher resolution version of the current chart, as requested in the comments.
  

  http://git.videolan.org/?p=x264.git ;a=commit ;h=b9ec3ea27812288485329ac7771143021cd4917b

• RoQ on Dreamcast

  18 mars 2011, par Multimedia Mike — Sega Dreamcast

  I have been working on that challenge to play back video on the Sega Dreamcast. To review, I asserted that the RoQ format would be a good fit for the Sega Dreamcast hardware. The goal was to play 640x480 video at 30 frames/second. Short version : I have determined that it is possible to decode such video in real time. However, I ran into certain data rate caveats.

  First off : Have you ever wondered if the Dreamcast can read an 80mm optical disc ? It can ! I discovered this when I only had 60 MB of RoQ samples to burn on a disc and a spindle full of these 210MB-capacity 80mm CD-Rs that I never have occasion to use.

  
  
  

  New RoQ Library
  There are open source RoQ decoders out there but I decided to write a new one. A few reasons : 1) RoQ is so simple that I didn’t think it would take too long ; 2) it would be nice to have a RoQ library that is license-compatible (BSD-like) with the rest of the KallistiOS distribution ; 3) the idroq.tar.gz distribution, while license-compatible, has enough issues that I didn’t want to correct it.

  Thankfully, I was correct about the task not being too difficult : I put together a new RoQ decoder in short order. I’m a bit embarrassed to admit that the part I had the most trouble with was properly converting YUV -> RGB.
  
  About the approach I took : While the original idroq.tar.gz decoder maintains YUV 4:2:0 codebooks (which led to chroma bugs during motion compensation) and FFmpeg’s decoder maintains YUV 4:4:4 codebooks, this decoder is built to convert the YUV 4:2:0 vectors into RGB565 vectors during the vector unpacking phase. Thus, the entire frame is rendered in RGB565 — no lengthy YUV -> RGB conversion after decoding — and all pixels are shuffled around as 16-bit units (minor speedup vs. shuffling everything as bytes).

  I also entertained the idea of maintaining YUYV codebooks (since the DC supports that colorspace as a texture format). But I scrapped that idea when I remembered it would lead to the same chroma bleeding problem seen in the original idroq.tar.gz decoder.

  Onto The Dreamcast
  I developed the library on a Linux computer, allowing it to output a series of PNM files for visual verification and debugging. Dropping it into a basic DC/KOS-compatible program was trivial and the first order of business was profiling.

  At first, I profiled the entire decode operation : open file, then read and decode each chunk while tossing away the results. I was roundly disappointed to see that, e.g., an 8.5-second RoQ sample needed a little more than 20 seconds to complete. Not real time. I performed a series of optimizations on the decoding library that netted notable performance gains when profiling on Linux. When I brought these same optimizations over to the DC, decoding time didn’t improve at all. This was my first suspicion that perhaps my assumptions regarding the DC’s optical drive’s data rate were not correct.

  Dreamcast Data Rate Profiling
  Let’s start with some definitions : In terms of data rate, an ’X’, i.e., 1X is the minimum data rate needed to read CD quality audio from a disc. At that speed, a drive should be able to stream 75 sectors each second. When reading mode 1/form 1 CD-ROM data, each sector has 2048 bytes (2 kbytes), so a single-speed data rate should achieve 150 kbytes/sec.

  The Dreamcast is supposed to possess a 12X optical drive. This would imply a maximum data rate of 150 kbytes/sec * 12 = 1800 kbytes/sec.

  Rigging up a trivial experiment using the RoQ samples burned on a few different CD-R discs, the best data rate I can see is about 500-525 kbytes/sec, or around 3.5X.

  Where’s the discrepancy ? My first theory has to do with the fact that not all optical media is created equal. This is why optical drives often advertise a slew of numbers which refer to the best theoretical speed for reading a CD vs. writing a CD-R vs. writing a CD-RW, etc. Perhaps the DC drive can’t read CD-Rs very quickly. To test this theory, I tried streaming a large file from a conventionally mastered CD-ROM. This worked well for the closest CD-ROM I had on hand : I was able to stream data at a rate that works out to about 6.5X.

  I smell a science project for another evening : Profiling read speeds from a mastered CD-ROM, burned CD-R, and also a mastered GD-ROM, on each of the 3 Dreamcast consoles I possess (I’ve heard that there’s variance between optical drives depending on manufacturing run).

  The Good News
  I added a little finer-grained code to profile just the video decoding functions. The good news is that the decoder meets my real time goals : That 8.5-second RoQ sample encoded at 640x480x30fps makes its way through the video decoding functions on the DC in a little less than 5 seconds. If the optical drive can supply the data fast enough, the video decoder can take care of the rest.

  The RoQ encoder included with FFmpeg does not honor any bitrate parameters. Instead, I encoded the same file at 320x240. It reportedly decoded in real time and can be streamed in real time as well.

  I say "reportedly" because I’m simply working from textual output at this point ; the next phase is to hook the decoder up to the display hardware.

• Evolution #4753 (Nouveau) : Styles du privé : listes d’objets (suite des boîtes et des formulaires)

  30 avril 2021

  Les boîtes et les formulaires ont été visuellement « raccordés » ensembles.
  Je pense que logiquement les listes d’objets devraient suivre.
  En fait ce sont 3 variations d’un même composant : une boîte avec entête, corps et pied.

  Pour les listes on peut séparer la question en 2 aspects :

  1) L’emballage extérieur¶

  Là il s’agirait de reprendre les choix graphiques propres à « l’emballage extérieur » des boîtes et formulaires : bordure, arrondi, espacements.
  Exemple sur l’image suivant où les 3 sont visibles (nb : ceux en colonne sont automatiquement « ressérés », d’où la différence de padding etc.)

  

  Après en fonction de l’un ou de l’autre, il y aura peut-être lieu d’ajuster le padding ou la taille du titre. Mais pour l’instant ce sont ceux en place.

  2) L’intérieur¶

  Ensuite je propose de procéder à quelques ajustements à l’intérieur de ces listes.
  Je pense que certains choix ont été faits pour s’accommoder du manque de place en largeur à l’époque, et ne sont plus nécessaires maintenant.

  Pour me faire un idée de ce qui fonctionnerait le mieux, et comprendre les détails visuels qui me gênaient un peu, j’ai parcouru quelques articles de recommandations sur l’ergonomie des data tables.
  Alors ils traitent plutot des fonctionnalités de ces tables dans leur ensemble, mais il y a aussi quelques guidelines visuelles intéressantes.

  • https://uxdesign.cc/data-table-for-enterprise-ux-cb48fb9fdf1e
  • https://medium.com/nextux/design-better-data-tables-4ecc99d23356
  • https://www.uxbooth.com/articles/designing-user-friendly-data-tables/
  • https://uxdesign.cc/lets-design-data-tables-bf065a60e588

  Je retiens quelques règles simples :

  • Des espacements suffisants et consistants (le padding quoi)
  • Une taille de police identique partout (au moins dans le tbody). C’est fatiguant pour l’oeil et moins lisible quand on passe sans arrêt d’un taille de police à l’autre sur une même ligne. Et je ne suis pas sûr qu’il y ait forcément besoin de gras pour certains éléments comme les titres ou autres.
  • À quelques exceptions près (id, picto), pas de largeur fixes sur les colonnes, laisser faire le navigateur.

  Donc voilà, c’est pas grand chose à ajuster non plus.
  Les colonnes des tables ont des classes .importante et .secondaire.
  À mon avis elle ne devraient plus avoir d’incidence en vue « normale », mais juste décider quelles colonnes afficher et masquer en vue réduite, dans les colonnes ou ailleurs.

  Donc dans les grandes lignes ça donnerait quelques chose comme ça (juste une maquette) :

  

  3) Détails¶

  Enfin pour ces 3 composants, je propose qu’il y ait une classe modificatrice commune pour produire un affichage compact, c’est à dire ressérer tout le contenu.
  Cette classe serait automatiquement appliquée dans les colonnes.

  Ça pourrait être « compact », mais sur d’autres composants pour varier les tailles je suis parti sur mini / large. Donc mini aussi ?