Don't pass structs bigger than 16 bytes on AMD64

https://gist.github.com/FeepingCreature/5dff669aad380a123b15659e195fb96c

by todsacerdoti • 3 years ago

387 142 3 years ago

gist.github.com

pclmulqdq6• 3 years ago

The cost of argument passing is rarely well-understood, and I'm glad someone wrote this. People routinely pass 24-byte objects by value in places like Google, and the cost of that practice doesn't show up on a profiler because it's spread out on every function.

elromulous• 3 years ago

"in places like Google".

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.

e____g• 3 years ago

I saw std::function and std::string (e.g. TotW 127, https://abseil.io/tips/117) being passed by value a lot in newer google3 code. Both are larger than 16 bytes.

pclmulqdq6• 3 years ago

Yes. A lot of 24-byte structs at Google are passed by value.

dataflow• 3 years ago

string_view might be the only exception I can think of.

What about std::span? std::optional? etc.

medler• 3 years ago

Passing larger objects by value is allowed or even encouraged if it lets you avoid a copy (e.g. if you’re about to move the object)

loeg3• 3 years ago

Does the C++ ABI also spill 24-byte objects to the stack for each call? I guess I don't expect std::string or std::function parameters to be fast but it's still surprising.

pclmulqdq6• 3 years ago

Spilling big objects up the call stack is often not nearly as bad. Most of the time this happens, the object being spilled is constructed during the function, so the copy on return is actually elided.

Cloudef2• 3 years ago

Pass by value / pass by ref is quite a bit of mental overhead as it effectively affects your ABI/API. Zig tries to not force this so as long as you "pass by value", the compiler can actually decide to pass it by reference. It does expose this kind of footgun though https://github.com/ziglang/zig/issues/5973#issuecomment-1330...

gnulinux• 3 years ago

Oof that's a very nasty bug. Is this still relevant in Zig or is there a workaround in the language? I'm not familiar with Zig, heard some good things about it, but this looks like a showstopper.

cassepipe• 3 years ago

I think this is the same in the still experimental Carbon

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

PaulHoule2• 3 years ago

+1 for pointing out that profiling often fails entirely to find widely distributed overhead, like that built into calling conventions.

kccqzy3• 3 years ago

The tradeoff here is that if you pass a pointer to that 24-byte object instead, when you actually need to use the object you need to deref that pointer. But nothing guarantees that the pointed object is nearby! You could very well cause a cache miss and wait a long time (like 100 nanoseconds) to fetch that 24-byte object from main memory.

If that same object is directly passed it's just on the stack. So it's most likely in the cache.

Remnant44• 3 years ago

Yes, but this concern is orthogonal to calling convention. If the parent function does anything to the object, it will be in cache already. If it does not, but loads the fields to register, the parent will take the cache miss instead of the function. You neither gain or lose anything...

gavinhoward7• 3 years ago

This makes me super happy that my C array types are only 16 bytes.

flohofwoe2• 3 years ago

This will still spill on the stack when compiling with MSVC (the cutoff size is 8 bytes there).

gavinhoward7• 3 years ago

Oh, thank you for letting me know.

saagarjha• 3 years ago

Where do you put the capacity?

alcover2• 3 years ago

  struct Array{void *ptr; uint64_t cap;}
  sizeof(struct Array) //16

gavinhoward7• 3 years ago

My array types are not meant to be changed, so no capacity is needed. I have separate resizable ones.

sesuximo• 3 years ago

1) Maybe you could store the bitwise-or of size and capacity on top of each other. If you restrict capacity to a power of two

2) you could store the capacity before the array payload

avgcorrection2• 3 years ago

Yeah, it looks like this would be problem for Rust’s `String` (owned) although not `&str` (borrowed).

tialaramex3• 3 years ago

Inside Rust it doesn't matter, because Rust gets to pick its own ABI rules.

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.

chlorion2• 3 years ago

I'm a little bit confused on what this means.

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

gavinhoward7• 3 years ago

I meant static arrays.

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.

countWSS• 3 years ago

Its common sense: anything passed in registers(preloaded due spec execution) will outperform stack writes and stack wrangling will outperform heap allocated stuff. That why ugly spaghetti code with tons of globals runs blazingly fast and your elegant recursive functions and tuple/struct/lists arguments are incredibly slow, the first one is much easier to optimize into tight assembly loops.

japanman1852• 3 years ago

But what about my academic mental exercise. You mean I learned all these tools and techniques for nothing? How will my manager know if I am a top engineer or not if my code is not impenetrable with ridiculous concepts applied irrationally.

Culonavirus• 3 years ago

Half of the money in IT right now is flowing from investors hearing "blahblah AI blahblah" and seeing dollar bills, which in turn makes half of the movement in IT happen in shitty python code. shrugs

johnnyanmac• 3 years ago

Different scale, different problem. Those "top engineers" at Google are dealing with memory that won't even fit in a hard drive (let alone memory), so stuff like this may as well be pico-optimizations.

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.

eru• 3 years ago

Of course, that assumes that your spaghetti code implements the same algorithm as your elegant code.

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.

vitiral3• 3 years ago

I think that was implied

gpderetta4• 3 years ago

Then again these days some CPUs can rename memory, making stack spills cheaper.

Global objects also hinder compiler optimizations.

mort962• 3 years ago

"Pass parameters in registers, not on the stack" is "common sense".

"Parameters larger than 16 bytes are always passed on the stack" ... isn't nearly as obvious.

loeg3• 3 years ago

The issue here is the SysV amd64 ABI. You could also just make your language-internal ABI not be SysV? As long as these aren't exposed to SysV C callers, you can use any calling convention you want.

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.

userbinator• 3 years ago

Or ABIs in general, really.

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.

5-• 3 years ago

indeed. another fun thing that c-like compilers generally don't do is multiple entry points in a function.

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

and have essentially two functions for the price of one.

PaulHoule2• 3 years ago

Yeah, for the little programs I write on AVR-8 it drives me nuts how much meaningless activity (moving the stack pointer around) that the C compiler does compared to assembly. For a PoV display engine, for instance, you might be able to reserve a few registers for the interrupt handler and still keep your inner loop variables entirely in registers.

CodesInChaos• 3 years ago

Compilers can already vary how parameters are passed to internal functions, especially if link time optimizations are enabled. Not sure how good a job they do at improving performance that way, but I certainly did not enjoy how this complicated reverse engineering.

sim7c003• 3 years ago

first question that came to my mind you answered :) thanks!. i think its interesting a lot of stuff adheres to such ABIs etc. especially since they were conceived of quite a time ago, and often lean towards being compatible with older CPUs, where newer ones with more extended registers etc. might have features that could be used to improve this without making the structs shorter. I guess it's not super interesting to make software for specific hardware or hardware classes / generations as it'll be unusable on some machines, but having compilers etc. that _can_ produce it might be cool if you want to super optimise the code running on your system towards your systems's hardware features.

cmovq• 3 years ago

On Windows with the default cdecl calling convention structs bigger than 8 bytes don’t get passed in registers [1].

[1] https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

bugbuddy4• 3 years ago

In the provided example, you can fix it without affecting any caller by changing the parameter types from “struct Vector” to “const struct Vector &” pass-by-reference. A lot C++ code that I have seen where pointer bugs existed needlessly used pointers even when passing by reference could have worked while being easier and safer to use.

giovannibajo1• 3 years ago

That will still require the compiler to serialize the three registers to the stack, to be able to pass the pointer to the structure to the callee. It seems like the described benefit is avoiding any serialization from registers to stack, which cannot be avoided with pass-by-reference.

bugbuddy4• 3 years ago

But that would only be possible if you write out all the struct fields you are accessing into function parameters. If the struct is complex with a lot of fields, then you would end up with a messy function signature. Also, I am sure there is a limit to how many parameters you can have before this optimization stops working.

fsckboy2• 3 years ago

That will still require the compiler to serialize the three registers to the stack, to be able to pass the pointer to the structure to the callee.

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?

kukkamario3• 3 years ago

No. Actually that is the whole problem here. That is pretty much exactly what the compiler does thanks to ABI. ABI says that the value must be passed by pointer so it has to store it somewhere to get the pointer, which is exactly the same that would happen if we made that explicit by using const-ref. By changing to use separate arguments for the struct values, arguments can be passed in registers instead.

gpderetta4• 3 years ago

on the other hand if the function is simple enough that the call overhead is significant, [[force_inline]] is an option.

1letterunixname• 3 years ago

This was a C99 example, not a C++ one. In many environments, tools cannot be changed arbitrarily because of minimum inertia. If C++ were allowed, then more options are available including moved arguments to reduce copying.

FeepingCreature4• 3 years ago

When I found this issue, it was in code that had twenty or thirty allocas to pass pointers to my byvals. Every function would start with a separate alloca for every parameter that was passed to a call. I always sort of assumed that LLVM would be good at cleaning that sort of thing up. It turns out... no, it isn't.

jeffbee3• 3 years ago

I classify this kind of article as "just enough knowledge to be a pain in the ass". Even if you compile it separately per the instructions, trying to force the compiler to generate ABI-callable functions, you can still undo this error with LTO. Building this program with LTO is dramatically faster in both modes compared to either mode of the non-LTO program.

If your program is performance-sensitive, profile it, peak-optimize it, and only then commit jackassery such as unpacking structs into arguments.

vlovich1232• 3 years ago

That would be good advice except I’ve yet to see a compiler that can make this kind of stuff visible. First it’s distributed throughout your codebase and I’ve not seen any profiler that can show that impact unless you’re lucky and this becomes a hotspot. This applies to nearly all compiler generated code. Valgrind can measure it (sampling profiler probably can’t) but there’s no tooling to highlight diffuse code gen problems

bugbuddy4• 3 years ago

This is clearly a hot path and not inlining a hot path call is probably the first thing any engineer worth his salt would attempt to fix. If and how it can be fixed is a different question.

rwmj3• 3 years ago

Plus the guy is talking about the supreme importance of performance, but is using reference counting.

FeepingCreature4• 3 years ago

(Author) The refcounting version is about as slow as the garbage collected D version on the benchmark. Refcounting operations can often be elided if you optimize a bit.

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!

kragen2• 3 years ago

it's perfectly fine to pass and return structs bigger than 16 bytes by value on amd64 even with the sysv amd64 abi; it's just slow. but it's often worth it to make your code clearer. not in this case, of course, but as loeg points out, inside your own language you can just use a custom abi, as for example each c++ compiler, golang, ocaml, and sbcl do

smallstepforman• 3 years ago

When I first transitioned to x64, I was concerned about graphics vec3 objects (3xfloat) expanding to sizeof()=16 bytes (instead of 12) that I benchmarked the hell out of my graphics engines. Unsuprisingly, using 16 bytes ended up being faster than 12, due to aligning 8 byte reads (internal and on GPU). So a vec3 silently became a vec4 (even though a vec4 also exists).

As always, do global, not local benchmarking.

jstimpfle2• 3 years ago

Probably not a lot faster? And apart from what you're doing with this data, isn't this also going to depend a lot on the CPU? I can see that with 16 bytes, a lot of accesses could be 2x aligned 8 bytes (or 1x16) instead of 3x4 bytes. Some other accesses, maybe not so much. And there is also the issue of increased cache pressure.

connicpu• 3 years ago

On the GPU especially, having the data aligned to 16 bytes is huge just due to the nature of what a GPU is optimized for and the way memory access is designed. The speedup on x86_64 isn't as huge, but the aligned load instructions for SSE/AVX registers are still quite a bit faster than the unaligned load instructions. It can really add up when you're processing thousands of vectors every frame. The cache lines will only go so far when a single 3D affine transformation matrix (floatx4x4) already takes up an entire cache line by itself.

gpderetta4• 3 years ago

x64 ABIs are also significantly better than x86 ones as well.

maccard• 3 years ago

It also has the very nice side effect of aligning with SSE sizes, so you can use \_mm\_load\_ps directly, which makes the code neater and us super easy to vectorise

flohofwoe2• 3 years ago

FWIW, on MSVC the cutoff size is 8 bytes before structs are passed on the stack. It's an ABI detail that shouldn't be relied upon in portable code.

...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.

DeathArrow• 3 years ago

As a .NET developer I always pay attention to passing by value vs passing by reference.

sebazzz• 3 years ago

There is extra complexity there depending on the call path. Given the premise of the article, you shouldn’t pass structs larger than two object references, or larger dan a Int64 (long). You already get to that point quickly. But in .NET there are also things like allocations to worry about.

gumby2• 3 years ago

That means that arrays, in addition to start and end, also need a pointer to the base of the array object, where the reference count is stored.

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.

fanf2• 3 years ago

The refcount is at slice.base[-1] and the array spans slice.start to slice.end

gumby2• 3 years ago

So shouldn’t this be known at compile time? (I’m not familiar with the language in question)

mcv• 3 years ago

The article links to a presumably extremely specialised benchmark[0] with some surprising results. To me as a simple dev, at least:

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?

[0] https://github.com/jinyus/related_post_gen/

enticeing• 3 years ago

Looks like the HO means hand optimized, with special datastructures for this benchmark.

see: https://github.com/jinyus/related_post_gen/#user-content-fn-...

unstruktured• 3 years ago

pypy and cpython don't mix well with each other so you have to create a whole new universe of packages for pypy. Interop with c libraries also adds complexity to the transition.

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.

kortex• 3 years ago

Pypy doesn't work with all libraries (as well as certain function calls in std), and since that's one of the biggest draws of python, it makes it a non-starter much of the time.

jlarocco• 3 years ago

The rule of thumb I've always heard for C++ is that anything non-primitive should be passed as a reference (or a pointer if you really have to) unless you have a good reason to pass by value (and normally you won't). Partly because of the ABI, partly to avoid copy or move constructors.

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.

tdiff• 3 years ago

How does such issues look in profiler? Is there a robust method to detect performance regression due to arg sizes?

JoeAltmaier• 3 years ago

Such a subtle issue! And I lay the blame on our obsession with abstraction.

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%.

epigramx• 3 years ago

Stuff like that are mainly the realm of the compiler. Unless you talk chiefly to compiler programmers. Exception is writing special asm code of course or other adjacent things.

Don't pass structs bigger than 16 bytes on AMD64

Related Stories