Memory Copy Hunting
tigerbeetle.com
tigerbeetle.com
I don't know about other tools and places, but one nice thing about working at Facebook is the internal Infer linter tool[1] is generally good about producing warnings for "this copy could be a ref instead"[2] (in the majority C++ codebase) at code review time, without manually combing the LLVM IR for memcpys. (Internally, Infer is using several handwritten analyses on C++ AST.)
Reading further, it seems like they are essentially looking for the pattern where a memcpy call is generated with a large constant size parameter at compile time. Things of this nature should be somewhat easy to write a static analyzer pass for, if you've got an existing AST/SSA level framework. I believe there is already an Infer pass for this for C++, but it might be a different internal analyzer.
[1]: https://fbinfer.com/
[2]: https://github.com/facebook/infer/blob/main/infer/documentat... (and related warnings, e.g., https://github.com/facebook/infer/blob/main/infer/documentat... )
Infer does whole-program analysis, so it can for example detect whether it is safe to move an object instead of copying it, because nothing touches it afterwards.
Ideally, you want to do this analysis on compiler IR, _before_ it gets lowered to LLVM IR. But to do that in a sustainable way, you need a quasi-stable internal IR format. Zig is rather new, and, while the compiler is a delight to hack on, there are no stable extension interfaces, and the code itself is very much not settled yet. So that's the main thing we get out of LLVM IR here is relative stability. You can quickly hack something together, and be reasonably sure that you won't have to spend a lot of time upgrading the infra with every compiler upgrade. LLVM IR of course is not absolutely stable, but it is stable enough, and way more stable than compiler internals at the moment.
For example, at my job we have a series of functions in our codebase that should never, ever allocate. It doesn’t register as an issue on our profiles or stress tests, but we know that it’s theoretically possible that if they allocated it could cause certain weird performance issues. Rather than hope that one of our customers never unlocks the magic confluence of events that triggers this behavior, we just make sure those functions don’t allocate in our unit tests and rule out that failure condition completely.
A bit paranoid yeah, but every now and then the paranoia is justified.
Currently only enabled for debug builds of the compiler, but there's talk there about making it a more general purpose tool for finding where the costly generic function instantations are.
On a semi-related note, if you want to look into compiler backends/IRs, there's QBE[0], which is far simpler than LLVM IR, but gets most of the point across
We'll be hosting a happy hour on Tuesday August 1st at 5pm. If you'd like to join, RSVP below and you're invited! Among others, some friends from the Zig communities will be coming through, and a DuckDB developer or two may be there. :)
It uses debug info to get a full stack including inline information which is especially helpful when running on Rust code.
It's taking code written in terms of value semantics, copying stuff around, and replacing it with more efficient code that avoids the copy.
Doing that by improving the compiler is a win. Doing it by changing the source to be easier to compile is a loss. You're trading readability for performance when instead you should fix the compiler and get both.
Zig is very much on the close-to-cpu side of the spectrum here. When it comes to copies, the current version of the language/compiler doesn't _yet_ provide the required guarantees with required ergonomics, but this is being actively worked on:
- https://github.com/ziglang/zig/issues/2765 - https://github.com/ziglang/zig/issues/12251 - https://github.com/ziglang/zig/issues/5973
In the meantime, you need to look one level below the source language to ensure that the runtime behavior of the code is what you want it to be.
Interesting distinction to draw. That's a pretty good definition for high level vs low level programming languages. Vector types and compiler intrinsics with an eye on the generated assembly are a good way to go for high performance subroutines. If you're willing to change the compiler back end to better serve the ISA, there's a decent chance you can emit exactly the machine code you wanted from somewhat convenient source code. edit: your post at https://matklad.github.io/2023/04/09/can-you-trust-a-compile... is great on this topic, thanks for the blog.
Where I disagree is the implication that higher level languages do not need a way to write code certain that an optimisation (transform?) will fire. All the constexpr clutter from C++ is an attempt to force optimisations to happen regardless of compiler (or compiler invocation, e.g. to say you want some map thing in .rodata in -O0 debug builds).
Transforms guaranteed by the language - whether vectorisation, monomorphising generics, garbage collection, constant folding - are inherently more useful things than heuristic optimisations where you hope for the best. I'm happy to see Zig is moving in that direction for memory copies and wish them good hunting with the aliasing analysis.
Hinted at in a sister comment, I think a missing lever in software dev is adding guaranteed-to-fire compiler transforms in application libraries. E.g. define some regex implementation along with optimisations that act on said regex implementation. Requires a sanely extensible compiler.
Also, some of the optimizations they are hunting are implicit and surprising. Probably not something a new compiler optimization is going to automatically fix.
This is a post about crawling the compiler IR to find things the compiler missed so that the programmer can change their code to work around the compiler. Even if the crawl-the-IR is a heuristic, moving that into the compiler would mean exactly the cases that were reported are now fixed automatically.
Non-deterministic compilers are broken. Arguably by definition, but also by heuristic as a non-deterministic compiler is enough of a nightmare to debug and fix that it can be expected to grow more errors over time.
Heuristic compilers are very much a thing. Also sadly fragile optimisations are a thing, where minor changes to the application take it over some threshold and the change in output is larger than anticipated.
However, the plan of attack of "change the program until the compiler did what you hoped for" is itself a heuristic that future changes to program and compiler may upset. An alternative is to patch the compiler to do the right thing, and add a regression test to the compiler so that it will continue to do the right thing. That has better engineering properties in the large.
> Non-deterministic compilers are broken.
I am not talking about non-determinism from run-to-run with identical sources and compiler version. I am talking about output variations between (1) different versions of the compiler, and (2) as the sources change slightly. Either of these things can easily nudge the heuristics a compiler uses in optimization into doing something different/worse.
Minor changes in compiler version and input source leading to widely varying output is a definite hazard. Especially when people change their code to make it run faster, or change the compiler to make some code run faster. That's one with no clear good solution.
for (items) |item| {
}
for (items) |*item| {
}
for (items) |*_item| {
const item: *const @typeInfo(@TypeOf(_item)).Pointer.child = _item;
// there's no "drop _item" so unfortunately _item remains in scope but we promise not to use it.
}
const _items: []const @typeInfo(@TypeOf(items)).Pointer.child = items;
for (_items) |*item| {
// now item is of the correct type, even if items is a slice of mutable things.
}For example, in C++ I would distinguish between mutating iteration and non-mutating iteration like this:
for (const auto& item : collection) {} // non-mutating
for (auto& item : collection) {} // mutatingThis is actually a very intriguing programming language keyword. I feel like there are lots of cases where you don't want to split something into a separate function just to avoid being able to use a variable that was used previously, and these things often get refactored over time to the point where the not-to-be-used variable gets used unexpectedly.
Right.
> so if you really genuinely care about copying that much you should be inspecting and profiling the binary they output
Sure, but manual inspection is burdensome and unreliable. Are you advocating against just use the language-level constructs (pointers/references) that guarantee a copy isn't performed?
I remember a Jon Chesterfield pointing out to me that people mistake inlining to be solely about call-overhead and not specialization - you should be able to nudge the compiler which one you want if at all (the "don't do anything" case being more often desired than pass-authors might think, myself include)
I recall multiple mentions over the years that inlining is the most important optimisation because of how many further optimisations it unlocks. I guess having some experience with Rust helps there, as the inlining itself is only a small fraction of all the work required to achieve "zero-cost abstraction". It’s very much load-bearing, but it’s the start if the work, not the end.
Pretty much everything in rust is going to be using traits and c++ uses templates for most things as well.
Every time you use a trait or a template, the code is expanded for the specific instance, and this gives a lot of opportunity for inlining stuff.
A lot of other languages would not have the same opportunity to inline code when doing polymorphism stuff because they rely on dynamic dispatch or something similar that can't be inlined very well or at all.
So I'm not disagreeing with you at all but I think rust and c++ get to inline stuff a little more aggressively, but this is just my theory and may be incorrect!
Yes. We have divisions - application, language library, language implementation - which are broadly convenient but drop information on the boundaries. The implementation probably pattern matches on the library and the library will probably depends on quirks of the implementation (e.g. compiler intrinsics written for it), but the application is unlikely to be be able to extend the implementation. In cases where it can, there's a tendency to call it monkey patching and disapprove.
> people mistake inlining to be solely about call-overhead and not specialization
Yeah, that sounds like me. Inlining is an approximation to per-callsite specialisation which is easier to implement, where you pay for ease of compiler development with (machine) code duplication. attributes noinline and alwaysinline are relatively likely to exist, but specialise with respect to the third parameter is still on a wishlist.
This is in the ballpark of compilers could be better, and should be better, than the current state of the art.
I wonder if it should be "kilobytes", 300 bytes are nothing considering that fs block size is usually 4KB.