Can we do better than our C compiler?
briancallahan.net
briancallahan.net
However, that's only one component of vectorization. It's still relying on LLVM to do lots of clean up, among other things.
I feel like there's a lot of reverence surrounding compilers and their capabilities, but at least when it comes to SIMD, it's not hard to find examples where a human can do much better, or can at least come up with algorithms that will do better for that and related problems.
I think saying compilers produce better asm than a programmer is like saying statistical libraries like `GLM.jl` are better at doing statistics than statisticians. True in that you should let the routines crunch the numbers. The skill is in deciding which routines/analysis to run, how to organize them, and -- when necessary -- when to develop your own.
For what it's worth, BLIS' generic C DGEMM code gave around 60% of the hand-coded kernel on Haswell with GCC (8, from memory) on large matrices without any real effort to speed it up. Obviously that's not a simple triply-nested loop, since just vectorizing is useless for large dimensions, and the generic code does get well auto-vectorized.
There are results from Polly/LLVM showing it do well against tuned GEMM. However, Polly apparently pattern-matches the loop nest and replaces it with a Goto BLAS-like implementation, and I don't know whether it's now in clang/flang. I also don't know how well the straight Pluto optimization does relative to BLAS, and whether that's what original Polly uses; it's a pity GCC's version isn't useful.
If you have those, you should be able to instantiate the Manifest: https://github.com/chriselrod/LoopVectorization.jl/tree/mast... and then `include("/path/to/LoopVectorization/benchmark/driver.jl")` to run the benchmarks.
There are other examples. For example, for code as simple as the dot products, clang shows some pretty bad performance characteristics while gcc needed a few infrequently used compiler options to do well there.
Image filtering / convolutions without compile-time known kernel sizes are another example that showed dramatic speedup.
When talking about optimized gemm, LoopVectorization currently only does register tiling. Therefore its matmul performance will continue to degrade beyond 200x200 or so on my deskop. An optimized BLAS implementation would still need to take care of packing arrays to fit into cache, multithreading, etc.
Maybe I should add pluto. I did test Polly before, but it took several minutes to compile the simple c file, and the only benchmark that seemed to improve was the gemm without any transposes. And it still didn't perform particularly well there -- worse than the Intel compilers, IIRC.
PRs are welcome.
I'm reminded of the old story about someone who tried to evolve an FPGA configuration to perform signal processing, and the final generation exploited imperfections in the chip to use fewer gates.
For example: suppose you have a program that renders a 3D scene from a hardcoded scene description. A compiler might do a lot of stuff to that program, but what it will certainly not do is notice that the whole hardcoded scene can be replaced with a small representation in the form of a distance estimation function, if the rendering algorithm is also changed from raytracing to distance estimation.
A human in a demo scene situation will certainly perform (or at least try to perform) that transformation, if only because distance estimation is well known to often provide compact representations of certain, a priori very complex, scenes.
Also, nitpick:
> Clearly this problem is NP-complete as hell
I think it's almost certainly not even in NP; that would require a polynomial algorithm that, given some evidence that you can choose, proves that a particular program really is optimal. I think that's still impossible (but am gladly proven wrong). If I'm correct, it's not NP-complete, it's NP-hard.
Right, there's an infinite number of distinct useful code optimizations, there's a cost to checking if any given optimization can be applied, and some optimizations have _massive_ costs for very rare and specific savings, so any given compiler is making a practical decision to include some optimizations and omit others. There was some discussion in the Rust community about LLVM having a period where they weren't tracking regressions in compile times - so "the perfect optimizing compiler" isn't really a coherent goal. But I still wonder how much faster Optimal Chromium would be. Just another interesting number I'll never know, I suppose.
> I think it's almost certainly not even in NP
Yeah, that was sloppy of me, I think this is undecidable by Rice's theorem. Nice catch!
I can say that every finite computational problem can be solved in O(1), so if the universe is finite, all real problems can be solved in O(1).
This sounds great until you realise that the constant factors involved would overwhelm any practical instance of this strategy.
It means the idea isn't necessarily wholly impractical. That's not nothing.
I imagine superoptimisers scale extremely poorly, but that's a different question. I imagine they're best suited to bit-twiddling problems rather than, say, figuring out the best assembly code to implement a parallel Timsort.
I have to admit ignorance here though, I know almost nothing about superoptimisers.
To actually answer your question, compilers are pretty good, and so are expert human assemblers, but they both miss things even for short snippets.
That said, compilers and superoptimizers can go together well. One of my favorite examples is using program synthesis to generate peephole optimization rules for a compiler[1]. The synthesis step takes a long time and only works for short snippets, but if you can turn the results of that into rules a compiler's optimization system can use, you only have to pay the synthesis cost once and the compiler can apply those rules to speed up large programs.
As an example aside from functional programming, consider instruction set architectures.
There are 3-address RISC instructions and "x := y - z" can be encoded in 32^3 different ways. It is not practical to consider all of them as a separate thing and share them.
The situation is less severe in two address ISAs and even less severe in 1 address (accumulator based) ISA (8086 is a blend between 1 and 2 address ISA).
For zero address ISAs it is even better. There's only one way to compute y-z, by issuing "-", which takes two arguments from stack and places subtraction result into it. Situations that lead to that subtraction are less diverse than in RISC 3-address way. And here comes the gist: one can factor same sequences of opcodes into subroutine ("word" in Forth parlance) and replace these sequences with call to that subroutine.
By programming Forth you do LZ compression on programs.
If you can't compress your program more, you have a perfect Forth program, and I am not quite joking here.
The same applies, albeit not that dramatically and visible, to other things in programs. It is possible to determine algorithmic kernels in programs (by matching optimized data and control flow against a pattern) and replace them with different ones - less computation intensive, parallelized, parametrized, etc. There were such works in optimization literature.
Again, in the kernel matching optimization goes first, because optimization makes program more canonical, so to say. And matching on canonical forms is easier.
The evolved circuit used fewer gates, but only worked on the device under test and when they removed gates that were apparently doing nothing, it failed to perform the task. ML cheating at its best!
I wonder if there's a similar analogy with how a young kid or someone completely unfamiliar with something can come up with an amazing solution that more experienced people would never think of --- because the latter had "hardened" their thinking to accustomed patterns and didn't go beyond them.
There are still cases, especially where clever uses of SIMD instructions can pay off. This is especially the case for video processing, deep learning engines and numerical code. It is still hard to beat the compiler even in those cases. You have to know about branch prediction, that modern processors execute many instructions in parallel (superscalar) as well as instruction latency. You also need to know about the cache hierarchy, but that's the case even when you let the compiler generate the code. Writing highly optimized code like that is not something every programmer will do, but most will use code written by others that has part in optimized assembly. An example of that is ffmpeg.
This was done 15 years ago, with a few minor updates about 6 years ago. Recently, we've revisited it to add support for AVX on Linux, which was missing.
It turns out that gcc can now do more or less as good a job as the hand-crafted asm. The hand-crafted version understood (mis)alignment better than gcc from 15 years ago, but at this point, gcc's inner loop is 1 instruction less than the hand-crafted version, although its setup before reaching the inner loop is several instructions longer.
There is still some human skill required to understand the best way to suggest to gcc what is going on, but it increasingly seems as though it's likely best to let the compiler do the actual code generation, even for SIMD.
So even if you can beat the compiler today, you might not be able to beat it tomorrow.
Therefore it is often useful to have two switchable implementations. High-level code that is basically straightforward, and hand-tuned assembly. You can the compare the two with every new compiler release.
You type your C/C++ code in the left pane, and it generates assembly in the right pane as you type. There is color coding to show you which C/C++ code correlates to the assembly code. If you hover over an assembly instruction such as mov, a tooltip appears telling you what it does.
It makes exploring what the compiler is doing easy and a lot of fun
The good thing about compiler optimizations is not that they produce actual "optimal" binaries, but that they allow you to not care too much about performance when writing code (e.g. using abstractions that will be inlined, etc.) and still get a decent binary. If you then require more performance (which will probably not be the case for most applications) you can still search for bottlenecks and start optimizing by hand there.
Also, this is an odd choice of program to compare. Compilers often do suboptimal on superscalarisation, inlining, or simplifying control flow. In this example, there is not enough space to go wrong nor for a compiler neither for a programmer.
Disassembly is either way our end result so unless you're looking for something particular, it makes sense to browse that first just to check that the compiler gets your intention just right.
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <alloca.h>
#include <sys/uio.h>
int main(int argc, char **argv)
{
if (argc > 1) {
int nstr = argc - 1;
char **svec = argv + 1;
int i, j;
struct iovec *iov = alloca(sizeof *iov * nstr * 2);
for (i = 0, j = 0; i < nstr; i++, j += 2)
{
iov[j].iov_base = svec[i];
iov[j].iov_len = strlen(svec[i]);
iov[j + 1].iov_base = " ";
iov[j + 1].iov_len = 1;
}
iov[j - 1].iov_base = "\n";
writev(STDOUT_FILENO, iov, j);
}
return 0;
}
7f454c4602010100000000000000000002003e0001000000820001000000
000040000000000000000000000000000000000000004000380001004000
000000000100000005000000800000000000000080000100000000008000
010000000000550000000000000055000000000000001000000000000000
0000000000000000200a4c8b0c2449ffc94d39d17441eb0eb00140b701be
80000100b2010f054e8b44d41041807c100100488d520175f4b00140b701
4c89c60f0549ffc24d39ca75cfb00140b701be81000100b2010f05b03c31
ff0f05http://www.muppetlabs.com/~breadbox/software/tiny/teensy.htm... https://www.pimzero.com/2020/04/19/golf_so.html https://rpis.ec/blog/plaidctf-golfso/
There are also a few instructions in the article that are size-suboptimal (e.g. "movl $4, %eax" is 5 bytes (b804000000), while the equivalent "xor %eax, %eax; movb $4, %al" is only 4 bytes (31c0b004)).