hckrnws
It's common for compilers to generate mildly unusual code because they translate high-level code into an abstract intermediate notation, run a variety optimization steps on that notation, and then emit machine-specific code to perform whatever the optimizations yielded. There's no constraint along the lines of "but select the most logical opcode for this task".
The claim that the code is inefficient is really not substantiated well in this blog post. Sometimes, long-winded assembly actually runs faster because of pipelining, register aliasing, and other quirks. Other times, a "weird" way of zeroing a register may actually take up less space in memory, etc.
> The claim that the code is inefficient is really not substantiated well in this blog post. Sometimes, long-winded assembly actually runs faster because of pipelining, register aliasing, and other quirks.
I had a case back in the 2010s where I was trying to optimize a hot loop. The loop involved an integer division by a factor which was common for all elements, similar to a vector normalization pass. For reasons I don't recall, I couldn't get rid of the division entirely.
I saw the compiler emitted an "idiv [mem]" instruction, and I thought surely that was suboptimal. So I reproduced the assembly but changed the code slightly so I could have "idiv reg" instead. All it involved was loading the variable into an unused register before the loop and use that inside the loop.
So I benchmarked it and much to my surprise it was a fair bit slower.
I thought I might have been due to loop target alignment, so I spent some time inserting no-ops to align things in various supposedly optimal ways, but it never got as fast. I changed my assembly to mirror what the compiler had spit out and voila, back to the fastest speed again...
Tried to ask around, and someone suggested it had to do with some internal register load/store contention or something along those lines.
At that point I knew I was done optimizing code by writing assembly. Not my cup of tea.
idiv [mem], and I assume mem is staying the same means it's in the lowest level cache... As fast as registers at that point. You're just adding to register contention attempting to move things into registers.
If you're doing enough divisions with the same divisor, it'd be faster to do what compilers do for division by a known constant, where they multiply by an integer reciprocal and shift
Yea that can work well. I have extensive fixed-point math experience from my days of coding 3D graphics on my 286 and up, but for some reason I can't recall I didn't consider that viable in this case.
Not to suggest you weren't competent, but did you consider and try and control for the fact that your measurement could be the problem?
Not going to dismiss it, but I did try to not do stupid stuff. I used QueryPerformanceCounter outside the loop, pinned the benchmark thread to a single core, and the array of elements it processed was fairly large. So I don't think overhead and throttling was an issue. The measurements were very consistent and repeatable.
Fair enough, I've only really ever found assembly level optimization on embedded microcontrollers to make any degree of sense. Performance optimization usually means something along the lines of "convince co-workers not to implement their own bubble sort" in my lines of work
Yeah, I've also come across a lot of assembly code which was faster 10 years ago, but where the compiler now beats it. So for a while now my take has been to mostly avoid asm, but if needed always have a compiled version, and always do runtime performance detection to select optimal version.
It's also rarely worth being optimal in scalar code anymore, particularly at compilation speed cost. The exception here is memory accesses and branches that will miss. So the writing of useless zeros is egregious but other stuff just isn't usually worth caring about these days. It's "good enough" in an age where even in embedded land I can run a 48mhz cortex m0 for 10 years on a battery and not worry about a few extra ANDS. I'm much more likely to hit size than speed limitations.
Not to mention for anything not super battery limited you can get a m55 running at 800mhz with a separate 1ghz npu, hardware video encoders, etc.
This is before you move into the rockchip/etc space.
We really just aren't scalar compute limited in tons of places these days. There are certainly places but 10-15 years ago missing little scalar optimizations could make very noticeable differences in the performance of lots of apps and now it just doesn't anymore
> The claim that the code is inefficient is really not substantiated well in this blog post.
I didn't run benchmarks, but in the case of clang writing zeros to memory (which are never used thereafter), there's no way that particular code is optimal.
For the gcc output, it seems unlikely that the three versions are all optimal, given the inconsistent strategies used. In particular, the code that sets the output value to 0 or 1 in the size = 3 version is highly unlikely to be optimal in my opinion. I'd be amazed if it is!
Your point that unintuitive code is sometimes actually optimal is well taken though :)
Stefan Kanthak has previously noted that GCC's code generator is quite horrible, in these extensive investigations:
The OP should try with -march=native so the compiler can use vector instructions.
Slightly off-topic but I like this way to test if memory is all zeroes: https://rusty.ozlabs.org/2015/10/20/ccanmems-memeqzero-itera... (see "epiphany #2" at the bottom of the page) I really wish there was a standard libc function for it.
> The OP should try with -march=native so the compiler can use vector instructions.
I just tried "-O3 -march=znver5" as well as "-O3 -march=native" and it didn't seem to make any difference.
Was looking at the llvm case with the dead store to the stack.
https://godbolt.org/z/Kb736onb4
\*\* IR Dump After Expand memcmp() to load/stores (expand-memcmp) \*\*
; Function Attrs: mustprogress nofree norecurse nounwind willreturn memory(argmem: read) uwtable
define dso_local noundef zeroext i1 @isAllZeros(ptr noundef nonnull readonly align 4 captures(none) dereferenceable(8) %0) local_unnamed_addr #0 {
%2 = alloca %"struct.std::array", align 8
call void @llvm.lifetime.start.p0(ptr %2)
store i64 0, ptr %2, align 8
%3 = load i64, ptr %0, align 4
%4 = load i64, ptr %2, align 8
%5 = icmp ne i64 %3, %4
%6 = zext i1 %5 to i32
%7 = icmp eq i32 %6, 0
call void @llvm.lifetime.end.p0(ptr %2)
ret i1 %7
}
Filed https://github.com/llvm/llvm-project/issues/180991 which I think is what the author should do in cases like this (rather than a blog post).
Strange is fine. Strange what we expect to see if the compiler is working, as some optimizations are unintuitive.
Inefficient is not fine, but there's no attempt to measure that here.
In my experience C++ abstractions give the optimizer a harder job and thus it generates worse code. In this case, different code is emitted by clang if you write a C version[0] versus C++ original[1].
Usually abstraction like this means that the compiler has to emit generic code which is then harder to flow through constraints and emit the same final assembly since it's less similar to the "canonical" version of the code that wouldn't use a magic `==` (in this case) or std::vector methods or something else like that.
To back up the other commenter - it's not the same. https://godbolt.org/z/r6e443x1c shows that if you write imperfect C++ clang is perfectly capable of optimizing it.
What's strange is I'm finding that gcc really struggles to correctly optimize this.
This was my function
for (auto v : array) {
if (v != 0)
return false;
}
return true;
Here's gcc for 42 elements:
https://godbolt.org/z/sjz7xd8Gs
and here's clang for 42 elements:
https://godbolt.org/z/frvbhrnEK
Very bizarre. Clang pretty readily sees that it can use SIMD instructions and really optimizes this while GCC really struggles to want to use it. I've even seen strange output where GCC will emit SIMD instructions for the first loop and then falls back on regular x86 compares for the rest.
Edit: Actually, it looks like for large enough array sizes, it flips. At 256 elements, gcc ends up emitting simd instructions while clang does pure x86. So strange.
I;ve had to coerce gcc to emitting SIMD code by using int instead of bool. Also, the early return may be putting it off.
Doing both of those things does seem to help: https://godbolt.org/z/1vv7cK4bE
GCC trunk seems to like using `bool` so we may eventually be able to retire the hack of using `int`.
I see yeah that makes sense. I wanted to highlight that "magic" will, on average, give the optimizer a harder time. Explicit offset loops like that are generally avoided in many C++ styles in favor of iterators.
Even at a higher level of abstraction, the compiler seems to pull through: https://godbolt.org/z/1nvE34YTe
It emits a cmp/jmp still when arithmetic would be fine though which is the difference highlighted in the article and examples in this thread. It's nice that it simplifies down to assembly, but the assembly is somewhat questionable (especially that xor eax eax branch target on the other side).
Except that the C++ version doesn't need to be like that.
Abstractions are welcome when it doesn't matter, when it matters there are other ways to write the code and it keeps being C++ compliant.
Compilers also like to unnecessarily copy data to stack: https://github.com/llvm/llvm-project/issues/53348 Which can be particularly annoying in cryptographic code where you want to minimize number of copies of sensitive data.
Sure, the code is strange, but it is not necessarily inefficient. The only way to determine whether it is inefficient is to profile the generated code. And perhaps, compare the performance of compiler-generated code with tweaked or hand-generated assembler code that you think might be better.
GCC and Clang both have highly detailed models of processor execution pipelines that are used to perform optimization and instruction scheduling. This allows them to perform optimizations that mere mortals can only do with assistance from tools like Intel VTune, which provides insight into how execution pipelines are running, and where and when they are stalling.
It's entirely possible that the multiple memory fetches may fuse in the execution pipeline, and that seemingly unnecessary instructions may dual issue, and execute in parallel. Or that minor variations in generated instructions may allow four instructions to be decoded in parallel instead of three at a critical moment in the code. These are the kind of insights that GCC and Clang have into how the code will actually execute that you do not.
Both GCC and Clang have highly detailed models of the processor's execution pipeline for literally hundreds of processors. These models allow the compiler to determine which instructions execute in parallel, and to predict and avoid stalls at various places in the processor's execution pipeline.
Counter-intuitively, many code optimization problems rely not upon the the instructions being executed, and not even on how many instructions are being executed, since pretty much every instruction in passably well-optimized code will execute in parallel with at least one other instruction. The actual problem becomes one of predicting whether any operation in a 7- to 20-stage execution pipeline will stall or not, and whether there are ways to schedule instructions so that the stalls either don't occur at all, or don't matter at all.
Optimizations that are dependent on memory access are particularly perilous. Modern processors have elaborate and sometimes unpredictable methods for optimizing memory accesses: not just cache optimizations, but also fusing of reads and writes, optimizations for streaming reads and writes, single-cycle reads and writes for memory operations that look like they are stack-related, strategies for scheduling reads and writes to avoid bus-turnaround time, and probably others. Very often, the only thing that matters is the memory access stalls, with all other instructions operating in parallel in the time that it takes for the memory reads and writes to complete. (Does your processor have handling in the execution pipeline that prevents a potentially expensive branch misprediction in that tight code loop? I don't know. But GCC and Clang do!).
For a human to compete with GCC or Clang code, intuition about how code executes isn't sufficient. If you are not using sophisticated profiling tools like Intel VTune, you really won't have insight into whether your hand-generated assembler is stalling in the execution pipeline. And that is typically the problem that determines how well code executes. How the data must flow is invariant from input to output. In this case, the input array must be read, and a register must be set to zero or one on output. And both compilers, and processor execution pipelines are capable of doing quite extraordinary things to maximize opportunites for parallel execution and pipelining. So. The ONLY way to tell whether any of that generated code is inefficient is to benchmark it. Intuition is not remotely sufficient.
As far as I can see, both compilers have done quite heroic and spectacular jobs of optimizing code. It is not at all clear whether the compilers know something about how memory operations fuse in the instruction pipeline that you don't. The only oddity is the extra memory write to initialize the zero array that shows up in a single case, which, in fairness, occurs because you have introduced a faux optimization in the original code. One of the compilers heroically (and probably correctly) optimized the bulk of the code, and tragically missed an opportunity to remove a faux optimization that YOU have introduced. Even then, it's still not clear that an extra memory write is going to execute slower. (A write to l0 cache (either one or two cpu clock cycles), followed by a bunch of reads from l0 cache -- does the cache controller allow parallel reads and writes or does it not? I don't know, but GCC and Clang do! Obviously not a good thing, but does it ACTUALLY impact performance? I don't know. And the only way to tell, is for you to actually profile the code.
Also worth mentioning in passing: if you are not compiling with --march=native, all your code is being optimized for some prehistoric ancient least-common-denominator Intel processor, probably a 1990's-era 486, that nobody actually has anymore that has god-only-knows what inadequacies in its execution pipeline. So make sure you are.
- Credentials: professional programmer with 45 years experience, including extensive experience optimizing and profiling high-performance graphics device drivers, and audio plugin code, some of which was done in the era where humans actually could speed up compiler-generated code by (typically) 2 or 3%, in an industry when 2 or 3% improvements in benchmark scores could increase profits by millions of dollars. Currently of the opinion that any optimization that produces less than a 25% performance improvement is just not worth the extra effort and risk.
> Sure, the code is strange, but it is not necessarily inefficient.
Out of the 6 pieces of Assembly code in the article, 2 of them are definitely inefficient - specifically, the 2 clang ones that contain irrelevant writes to the stack. Even if a CPU was smart enough to ignore those instructions with no performance penalty (which in itself is doubtful), at the very least those instructions take up space in memory/caches unnecessarily.
The gcc output when arraySize is 3 is almost certain to be inefficient as well, when you look at portions such as:
mov eax, 1
test eax, eax
sete al
ret
So yes, in general benchmarking is the only way to be sure. But when you look at the specifics of the generated code, we can see that at best 4 of the 6 snippets of Assembly code are optimal, and the actual number of optimal snippets is probably lower than 4 (my best guess is 2 here).
All that said, I might benchmark everything later on and post a new article about it.
> Also worth mentioning in passing: if you are not compiling with --march=native, all your code is being optimized for some prehistoric ancient least-common-denominator Intel processor, probably a 1990's-era 486, that nobody actually has anymore that has god-only-knows what inadequacies in its execution pipeline. So make sure you are.
With `u32` as the element type, rustc 1.93 (with `-O`) does the correct thing for size=1, checks both elements separately (i.e. worse than in the article) for size=2, checks all three elements separately (i.e. not being crazy like in the article) for size=3, and starts doing SIMD at size=4.
This code is not equivalent to the C++ version. You can directly use `*x == [0_u32; SIZE]`. The code generated by the two is different. (But the iterator version not producing optimal code is also an issue.)
Very good point! Thanks!
With the correction, it interestingly enough produces the good behavior also at size=2. It also delays SIMD until size=5. But then it bizarrely stops doing SIMD again after size=64.
https://godbolt.org/z/P979nY4nf
The iterator version stays SIMD-y also after size=64, but stops at some point. What?! I don't know enough to understand what's going on. Anyone?
Might it have something to do with compiler heuristics? Compilers cannot analyze everything, since the more compilation time is spent on analysis, the slower compilation will be. So compilers might use heuristics to guess when to do analysis and how much, and when not to. As part of trade-offs between better optimization of compiled programs and decreasing compilation times.
> Both GCC and Clang generate strange/inefficient code
At the same time Anthropic anounces its own compiler. How sweet.
For the avoidance of doubt, I neither work for Anthropic nor do I have a horse in this race in any other way. I didn't even know about the Anthropic compiler when I wrote the blog post.
Crafted by Rajat
Source Code