Don't pass structs bigger than 16 bytes on AMD64
gist.github.com
gist.github.com
https://llvm.org/docs/LangRef.html#calling-conventions
For those curious, the relevant diff in neatlang is: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5.... It looks much more involved than changing the emitted LLVM calling conventions. Possibly the author wants these types exposed with some deterministic calling convention to C programs.
As any Asm programmer can tell you, this is one of the low-hanging fruits that compilers can easily be beaten at --- don't blindly follow convention, do what makes the most sense in a specific scenario.
consider a pair of functions foo and foo0 that differ only in that the former performs an additional action on its argument -- perhaps refcount adjustment or type conversion.
you can then do (in a register-based abi like amd64 sysv);
foo:
do the action ;fallthrough
foo0:
rest of the function follows
You can structure the code so foo calls foo0, but the compiler and linker have to work together to pull that off and I don't think GCC and clang do so.
If the functions are being built into split sections, generally no.
If they aren't, and foo isn't called nd foo is, I've never seen a tool chain remove just foo but not foo0, which is nice to have.
I can imagine if higher level code isn't within a specific pattern, the compiler might struggle to recognize an opportunity for optimizing the code and skip it. - the higher level programmer could potentially arrange code in ways the optimizers better recognize.
Not exactly, they're describing doing it without a jump - the first function simply ends at the start of the second function, so the CPU starts running the second function directly after the first with no jump necessary.
Edit: If you're saying a tail call could enable such an optimization, you're right, but it still requires placing the functions in the right spots to eliminate the jump entirely, which is hard.
Where it mattered for me was on an ARM core managing a much larger DSP. The DSP consumed most of the memory bandwidth, so fetching a cacheline of instructions or an MMU mapping into the ARM had long and variable latency as it had to wait for the DSP to finish a large burst to or from the shared memory.
i think your edit is on point. optimizations exist, but the hard thing is to know when to apply them and them restructuring the binary etc. - you can imagine you might optimize one bit only to find its impossible to run further code etc. because the optimization breaks it. or even different phases of optimization either feeding eachother more optimization opportunities or negating them(how to order optimizations). compilers and optimizers are such magic really, how far weve come in there. i got one book bigger and fatter than any ive ever seen, more thick than an oldksool bible. and its on compilers :'). its so big im afraid to start it!
foo() {
// do something
return foo0();
}
foo0() {
// do the rest of the things
}
For example, in the following that saves a function call cost on every nil call.
fn foo(bar) {
if bar != nil {
foo0(bar)
}
}I was at a place that had a convention to do
Function blah(…)
Argument validation
Call realBlah(…)
I guess (although could be wrong, this is the first time I’ve seen it) this strategy is basically incompatible with inlining, though?
recursive inlining
--You don't have to use a stack. A stack is a convenient data structure for this purpose, but there are other ways to do it.
--You don't even need to keep track of return points at all. That's what continuations are about: Nothing ever returns.
Unlikely to be able to reserve a register though
Are you speaking from experience?
As a former googler, I can say with certainty that the guidelines for passing any non primitive is pointer or ref.
string_view might be the only exception I can think of.
std::string in the case you cited is only really relevant if you std::move() into it and you would otherwise incur a string copy. Yes, it's bigger than 16 bytes (24 bytes), but that pales in comparison to the alternative.
(Taking std::string&& would eliminate the possibility of misuse / accidental copies, but that pattern is generally discouraged by Google's style guide for various reasons.)
Also, just because you see a certain pattern an awful lot even at Google doesn't mean that it's best practice -- there are plenty of instances of protobufs being passed by value...
An unnecessary memory allocation is much more of a performance hit than suboptimal calling convention.
But yeah, in a c++ codebase, good modern practices are often verbose and clunky.
IMO it's hard to beat pass by value considering both performance and cognitive load.
...but that requires the argument to be a type from a template D: so you'd have to write:
template<typename String = std::string>
void dosomething(String &&str)
1. `foo(T)` indicates polymorphic over both `T::T(const T&)` and `T::T(T&&)`. This gives you benefits of both pass-by-move (using `std::move` as needed), or copy.
2. Usage of `foo(T&&)` signals code-smell or an anti-pattern as `foo(T)` should be used instead unless it is perfecting forwarding / universal reference `template <typename T> foo(T&&)`.
What about std::span? std::optional? etc.
You also usually want to pass smart pointers (unique_ptr, shared_ptr) by value to avoid breaking your ownership model, or pass by raw pointer or reference to the held data. The obvious case that comes to mind where you'd want to write const unique_ptr<T>& is when iterating over a vector<unique_ptr<T>>. Otherwise, pass ptr.get() for an optional param, or *ptr for a required param where you've already checked ptr != nullptr.
Wrapper types like optional, variant, StatusOr? Usually pass by reference, unless the pointed-to type is small (<= 8 bytes).
One common pattern where I see wide structs being passed by value is the use of option structs (https://abseil.io/tips/173) that are usually constructed via designated initializers. There is some marginal benefit to being able to std::move() out individual fields but it's not really a big deal either way, as said computation is usually only done once on program initialization.
Luckily, the Zig core team has recognized it is an issue and plan to address it before 1.0 :)
https://github.com/ziglang/zig/issues/1108
You get all the benefits of Zig being able to choose the function ABI, but if the optimization would have caused a bug, you'll get an immediate panic at the function entrypoint, instead of silently corrupted data.
There is also a another paradigm where parameters are marked as in, out or inout parameters as in D (?) and cpp2 which makes the intent clear
Apparently, it's not (anymore?):
https://github.com/ziglang/zig/issues/5973#issuecomment-1801...
If that same object is directly passed it's just on the stack. So it's most likely in the cache.
It's a tradeoff between reducing memory usage and reducing cache misses.
As always, do global, not local benchmarking.
The logic makes sense for them. The problem is everyone else copying Google without understanding their own data. Any domain where real time performance is important need to put aside the SWE books and pick up a CPU/GPU architecture reference instead.
If the elegant code is O(n) and the spaghetti code is O(n^2) you might notice the difference.
And, of course, there's also maintenance to consider.
In some sense, compiler are there exactly to turn our elegant solutions into spaghetti code.
Global objects also hinder compiler optimizations.
"Parameters larger than 16 bytes are always passed on the stack" ... isn't nearly as obvious.
...but also don't stress it too much for functions that are not called frequently - and for frequently called small functions like in the example, just make sure that the compiler can inline the code (for instance via LTO) this will unlock much more useful optimizations beyond just passing args in registers.
If your program is performance-sensitive, profile it, peak-optimize it, and only then commit jackassery such as unpacking structs into arguments.
And this is not a "supreme importance of performance" microoptimization. This single change moved me from place 23 to place 5. That's a 2x speedup!
[1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...
This is the approach the article's author took.
why can't it simply pass a pointer to the struct (it's probably already on the stack) without rewriting the struct to the stack? isn't that what a reference is?
You want to call a function that is not expecting its arguments to be in registers, and you don't have unlimited registers on this hardware at this time, so I don't understand all the hand-wringing about either option. I guess what I'm saying is that this is all being treated like "because we assume optimization and we know how optimization works, we're entitled to have what's important in registers all the time so things will go faster, so this must be a bug and we have to fix it."
The actual solution is to inline the callee and rely on the compiler, switch to asm and hand guarantee, or create a new language that has register calling or data flow semantics that are different than what you have now. The conversation that's taking place here sounds to me like relying on undefined behaviors, something we used to do because we knew we could rely on them but you can't any more.
It's a tedious low level detail, but that's what you have to pay attention to in C++ if you want the best performance. And to be clear, it is just a performance optimization - the struct passing code will work fine, just not as fast.
Java (JIT) beats C++ and even Scala.
What is Julia HO and why is it so ridiculously fast?
The speed difference between Python and Pypy is massive. Is there any reason not to use Pypy? Shouldn't it be the standard?
see: https://github.com/jinyus/related_post_gen/#user-content-fn-...
In addition, vanilla python is finally starting to tackle the worst performance problems (like the GIL getting removed for instance), so they might catch up to pypy eventually. There's also several different JITs installable into cpython systems these days too which is less painful than switching to pypy.
Personally, I am saddened pypy didn't replace standard python, but even in my own career I couldn't find a big speed difference in practice because all the heavy lifting utilizes C, C++, or fortran libraries wrapped by thin python apis.
Once we give up responsibility of the machine architecture to a compiler, we then have to chase issues like this. What gestures can I make to my compiler, to make it use better machine operations? It's maddening. Like a game of charades.
Sure abstractions gain us tremendously, are an invaluable aid to quickly conceiving of an application and creating something safe and understandable and even beautiful.
But we lost all hope of making it fast, or small, or 'efficient' in any physical way.
My favorite example from my lifetime: On the Dell Triton our app programmers had a main loop that included a call using complex types. The entry point had, and I disassembled to see, five constructors and destructors called to coerce the types into something the API needed.
It consumed the entirety of the embedded processor hyper-thread. They were unconcerned, as it worked as designed.
I added a little casting in the call arguments, which reduced the CPU time to something like 15%.
Isn’t the size and layout of the structure known at compile time? Why couldn’t the ref count be found by subtraction rather than by being passed?
The standard way to implement this is to use address - 1 for such metadata, but any offset in a contiguous allocation works.
struct Array{void *ptr; uint64_t cap;}
sizeof(struct Array) //16 struct Array{void *ptr; uint64_t len; uint64_t cap;}
sizeof(struct Array) //24
struct Array{void *ptr; uint32_t len; uint32_t cap;}
Now thanks to alignment you could use spare bits in the pointer to afford bigger lengths.
struct Array{int64_t ptr:60; uint64_t len:34, cap:34;}But if you meant an actual array as in Rust's [T; N] then it's weird to talk about them as if they've got some specific size, their size is a parameter (N) of the type.
The size of Rust's [u8; 16] or C's unsigned char [16] is 16 bytes but like, duh. And there's no magic here, [u8; 24] or unsigned char [24] is 24 bytes.
This is so I can use regular C pointers to pass them to system functions that expect pointers. Because C still uses just pointers. But I have the length for bounds checking in my own code.
But my resizable types are much bigger. Probably 32 bytes because they store a destructor too. I pass them by pointer because plain pointers are almost always just one item, meaning no bounds checking is necessary.
Yes, that does mean the actual array is two indirections away, but that style gives me a lot of safety because araay indexing is a code smell.
Also in most cases people's destructors don't have associated local state, so, they needn't take up space in each object. All C objects have non-zero size, so if you have an object representing the destructor even if it has no state that takes up space. In C++ there's a hack to avoid paying this price, but in C there is not.
Well, yeah, but I hate all other languages [1], and I'm willing to pay the price in C.
That same sort of thing allowed me to implement RAII in C, though.
[1]: https://gavinhoward.com/2023/02/why-i-use-c-when-i-believe-i...
2) you could store the capacity before the array payload
So this only matters for the FFI case and it's probably usually a bad idea to give a mutable String (as opposed to a read-only &str) to foreign language code.
Likewise for Vec<T> and &[T] indeed underneath Rust's String is literally Vec<u8> and &str is literally &[u8] but in both cases with the explicit requirement that the bytes are valid UTF-8 text.
By array I guess you mean a dynamically sized, but not dynamically-resizable pointer and size/length pair? So you aren't storing the "capacity" like Rust's Vec would be doing.
You can do the same thing in Rust with Box<[T]> if I am understanding you correctly. Box<[T]> in this specific case is a fat pointer, which is a pointer to the underlying allocation and a length.
One of the issues with Box though, at least as of the last time I looked at it, is that the only way you could create a Box<[T]> without unsafe or nightly was to create a Vec, and then call into_boxed_slice on it. The conversion from Vec to Box actually causes a new allocation to be created if the size and capacity fields in the Vec are not equal. In C it would be possible to reuse the Vec's buffer, but dealloc (and all other alloc related functions it seems) in Rust requires passing in information about the layout the of the underlying allocation, and size is part of the layout!
In C++ I guess you would want to use std::unique_ptr<T[]>, and manually store the length, which is not great but still works. I'm not sure if unique_ptr is guaranteed to be the size of a pointer or not, so this may or may not work.
Regular statically-sized arrays are the same size in each language ofc. In Rust and C++ statically-sized arrays do have one benefit though, you get bounds checking on them "for free". Since the length is baked into the type, the accessor methods know the bounds at compile time, so no runtime length information is required to do runtime bounds checking! You can do this in C by hand for each array you define but that is impractical, you could probably use a macro to do this though.
If I did understand what you meant, I think this brings up an interesting topic. Having a first-class dynamically-sized non-resizable array type can be pretty useful! Rust already can do this awkwardly with Box, but C++ currently doesn't have a way to do this without manually storing the length and doing manual bounds checking that I know of. It would not be terribly difficult to implement this and there probably are libraries that exist for it, but I still thing it's interesting.
# comment for Vec::into_boxed_slice https://doc.rust-lang.org/src/alloc/vec/mod.rs.html#1075
# rust std::alloc::dealloc requires std::alloc::Layout https://doc.rust-lang.org/std/alloc/fn.dealloc.html
I have to use a pointer+length pair because many system functions in C require a pointer, but I want bounds for bounds checking.
Yes, I do my own arrays in C.
I also have dynamic arrays, but those are not 16 bytes, and I treat them differently.
Edit: i looked at your profiles information and have discovered lots of fun stuff
As you have probably discovered, my array stuff is just part of a monorepo. But yes. :)
Edit: The code at the Yzena one is not up to date because I've had to keep commits local. But I have 1200+ commits since, and I plan to make them public in April.