Introduction to AVX2 optimizations in x264

A couple of comments/elaborations on the "core differences" mentioned in the article:

The first difference mentioned is that whereas the first SSE2 implementations were often implemented using 64-bit ALUs internally, yielding roughly the same performance as doing two equivalent MMX ops manually, this isn't the case with AVX2. However, it may be worth noting, that it largely _is_ the case with the current AVX ("AVX1", i.e. pre-Haswell) implementations.

The second cited difference is that there's a 128-bit "boundary" in many of the operations. This is effectively what can throw down the drain the hopes of getting 2x gains over SSE2 just by naïvely migrating into AVX2. For instance, you cannot do shuffles to/from arbitrary components anymore, but have to consider the 128-bit lane boundaries instead.

The third issue, i.e. data layouts of internal formats and the assumptions of various algorithms are probably the most significant factors that determine how large a benefit you are going to get. Typically the internal data layouts (i.e. is my pixel block size 2x2, 4x4, 16x8 or something else?) are married with the ISA. Thus, when migrating from one instruction set to another, these typically may need to be reconsidered if speed is paramount. Interestingly enough, this means that when the ISA changes, you most likely want to do some higher-level algorithmic optimizations as well.

x264 actually turns off vectorization in the configure script, because it's caused crashes and bugs in the past on various platforms. But even if you enable it, it usually almost never triggers. Even the Intel compiler's autovectorization only triggers in a few functions, despite its reputation, and typically does an pretty mediocre job.

The problem has many parts:

1. Autovectorization in general is just extremely difficult and even trivial code segments often get compiled very badly. It feels like the compiler is trying to fit the code into a few autovectorization special cases -- for example, a 16x16->16 multiply gets compiled into a 16x16->32 multiply, and then it laboriously extracts the 16 bits, probably because nobody wrote code to explicitly handle the former variant. A good autovectorizer would have to have a vast array of these sort of things to "know what to do" in a particular case, I'd imagine.

A lot of autovectorization resources seem to be tuned towards floating point math (which typically doesn't need the same sort of tricks), which probably exacerbates the problem in x264's case.

2. The compiler doesn't know enough. It can't guarantee alignment, it doesn't know about the possible ranges of the input values or the relationship among them, it doesn't know the things the programmer knows.

3. SIMD algorithms are often wildly different from the original C. Much of the process of writing assembly is figuring out how to restructure, reorder, and transform algorithms to be more suitable for SIMD. The compiler can't really realistically do this; its job is to translate your C operations into machine operations, not rewrite your algorithm.

Part of this problem is that C is just not a great vector math language, but part of it is also that the optimal algorithm structure will depend on the capabilities of your SIMD instructions and their performance. For example, when the pmaddubsw instruction is available, it's faster to do x264's SATD using a horizontal transform first, but if not, it's faster to do it with a vertical transform first. The Atom CPU has pmaddubsw, but only has a 64-bit multiplier, making it too slow to utilize the horizontal version (so it gets the vertical version instead).

You can definitely finagle code into getting hit by the autovectorizer, especially with Intel's compiler, but it takes a lot of futzing to make it happy, and even when it is happy, it can be many times slower than proper assembly. Of course, it's not useless -- it can get you some relatively free performance improvements without writing actual SIMD code. But it's not a replacement.