> It seems fine to me for the spec not to guarantee anything about struct field order in memory. The spec doesn't operate at that level.
> That said, no Go compiler should probably ever reorder struct fields. That seems like it is trying to solve a 1970s problem, namely packing structs to use as little space as possible. The 2010s problem is to put related fields near each other to reduce cache misses, and (unlike the 1970s problem) there is no obvious way for the compiler to pick an optimal solution. A compiler that takes that control away from the programmer is going to be that much less useful, and people will find better compilers.
How often is "reduce cache misses" that different from "use as little space as possible"? They're basically the same if the struct can be no more than one cacheline wide. When the struct is larger, it's possible you're accessing certain sets of fields together often enough for this to be a useful consideration, but I have no intuition on how common it is. Although it occurs to me that when this happens, switching from arrays of structs to structs of arrays may be a better optimization anyway.
fwiw, Rust leaves the ordering unspecified (unless you specify it via #repr[(C)]). Currently it orders to minimize padding. (In theory a future compiler could reorder to minimize cache misses based on a profile or something.) According to https://doc.rust-lang.org/nomicon/repr-rust.html part of the rationale for reordering was generics. If you have a struct Foo<T, U>, the optimal ordering depends on the size of T and U. The same argument won't apply to Go until 1.18 is released.
> How often is "reduce cache misses" that different from "use as little space as possible"?
I thought the same exact thing. If I can reduce my struct sizes I can pack N more structs into my cache line. That's almost certainly going to be the best cache-based win.
If your struct is large enough that you care about shaving padding, you probably have hot fields and cold fields and the best cached based win will be arranging them contiguously.
Counterexample: the struct in the article. It's "large enough that you care about shaving padding" in aggregate. The 2 optimal arrangements eliminate padding so it uses 1/16th of an x86-64 cache line. This guarantees the whole struct is on one cache line and uses the least total cache, so the 2 arrangements with padding are strictly worse, regardless of which fields are hot or cold.
A struct of arrays form may be better still, but that's more than rearranging fields and beyond the compiler to produce.
More generally, there are surely cases where it's better to arrange all the hot fields together at the expense of increasing the struct size, but I'm unsure it's the common case, and my bullshit alarm fires when people say so without evidence. (Even more so if they're also saying programmers are commonly arranging the fields optimally by hand.)
That does not match my real world experience. If you have an array of small structs then the padding matters. And if some fields are hot while others are cold you usually want to split the array of structs into two arrays of structs, one with the cold part and one with the hot. The use case Go optimizes for is not common in the fields I have been working in.
I think the default should be to minimize size and that it should be possible to opt out for the rare case where exact order matters.
Can go structs be nested by value? (As opposed to by reference)
I'd imagine that this could be a very practical way to to do a manual hot/cold grouping in an environment that prioritizes packing over keeping order. (if the cold ones are particularly cold you might of course prefer them to be in a by reference nested struct anyways, so the hot subset packs better with their peers in an array)
If I have a [10000]T I need to shave very little padding before I see some impact, even though both the padded and unpadded T might be relatively small.
Specifically in Go, a smaller size can get even lone values into a smaller size class. Saving one byte may save you 384 if it's from 2305 to 2304.
The example in the link had 3 fields and padding made the structure 50% bigger than it needed to be. That probably likely big enough to have hot and cold fields but clearly they cared about shaving padding.
it's very likely that it's one of the cases that when reducing cache misses does really matter it's very different from using as little space as possible, and the degree to which it matter dwarfs the degree to which it's not a frequent concern (i.e. fat tail).
for example, if I have a struct that contains a bunch of atomic fields, I may actually want to control the layout to ensure they are far apart (even inserting padding) to prevent e.g. false sharing https://en.wikipedia.org/wiki/False_sharing.
The common and normal behaviour you want is to minimise struct size so you can fit the maximum instances in cache and memory.
The need for more precise control is very much the exception, and thus not unlike preventing inlining (which you may actually want) it could (and should) be an opt-out.
my point is that these are the fat tail + survivor bias of cases where you do actually care about performance to this degree, so it probably is actually more common in practice when you're looking into it.
even though precise control is the exception, if you can't do it, you can't use your language in a lot of critical contexts (and end up linking C, Zig, Rust, etc).
scottlamb seemed to be implying it's not worth being able to since it's an uncommon use case, so I was explaining why even if it's uncommon it's must-have.
Yeah, a cache line is 64 bytes. If you care about putting data that's used together adjacent you're assuming that objects a lot larger than 64 bytes are the most common case but I'm not at all sure that's true. I would guess that we're using up our memory with large heap allocated arrays and large numbers of structs that fit within a cache line. But of course, that's something that ought to be actually measured.
struct packing is one way to reduce cache misses. One can also reduce cache misses by redesigning structs to better match the data usage pattern (eg ArraysOfStructs vs StructsOfArrays).
First off, using less memory is an effective way to reduce cache misses: if you shrink memory by ⅓, that allows you 50% more objects in the same cache size. And this applies to anything--it's the only way to reduce cache misses that is universal. So saying that it's not solving the "real" problem is really a spit-take, because it's a pretty effective way of solving that "real" problem.
Suppose you considered cases where a smart ordering could avoid hitting unused cache lines. If a struct is larger than a cache line, it's possible to put co-used values on one cache line and avoid bringing in the other cache lines. But this kind of optimization isn't going to work unless the struct is cache-aligned to begin with--otherwise, your clever ordering is only going to sometimes work and sometimes potentially cause unnecessary multiple cache lines to need to be brought in. As to whether or not cacheline-alignment is a good idea, well, the extra padding will increase memory usage (see point #1), and the potential benefit is going to be limited by how hot or cold field accesses actually are.
The other case that comes to mind is false-sharing, which is definitely a real concern. Except, we're talking about reordering struct fields, which means it's false sharing within fields of a struct, and that's a much smaller subset of where false sharing actually occurs--false sharing tends to be more of an issue when you have an array of objects, and you need to make the struct element a multiple of cacheline size to avoid it. The only reasonable cases I can think of off the top of my head are going to involve structs which have intrusive atomic reference counting or some sort of intrusive lock in them--and you can solve both of those cases by making large cacheline-sized versions of those structs that prevent any fields of the outer struct from being stuck on the same cache lines as those data structures.
So I rather expect that it is very possible to have a field reordering algorithm that would improve cache misses in all the obvious cases (as I mentioned in point #1) while not preventing the user from having sufficient control to optimize for minimizing cache misses in the rarer cases in the subsequent point.
He was basically saying A is an old problem, the new problem is B. However, there's no obvious way to solve B, so we don't solve B.
But why not solve A then? Unless.. A is not a problem anymore nowadays. (Is it, though?)
But if A is not a problem anymore, he could have just said struct field ordering was an old problem and not a problem anymore in 2010s, without mentioning the other problem.
Meanwhile the blog post suggests that struct field ordering is still a problem even in 2020s.
This is a strawman argument. It presents the two options as mutually incompatible, whereas they are not (as demonstrated by other languages that allow to do both).
But if I understand things correctly, go, the spec, doesn’t provide the developer a way to control field order. It’s only the (main) implementation that currently happens to keep field order matching the order in the source code.
“defining the type using [n]byte and modifying the fields using the encoding/binary package. On many processors the performance will be approximately the same.”
> But if I understand things correctly, go, the spec, doesn’t provide the developer a way to control field order.
The spec doesn't, but the actual compiler implementation does. If the compiler is not allowed to re-order fields, they remain in the order the programmer specified in the code. That's why the fix in the article works in the first place.
But the compiler isn’t “not allowed to re-order fields”. The spec allows it to do that. This fix works for the current compiler, but may not do so for next week’s.
Technically you could say it wouldn’t even be a breaking change if a compiler update changed that (practically people would have reason to be angry if they slipped something like that in without creating a major version and adding warning flags to the release notes)
> By Go doing nothing, a developer can manually solve both A and B.
In Rust, you can annotate a struct declaration with "#[repr(C)]" to prevent the compiler from reordering fields. I don't see why the Go compiler couldn't offer something similar.
Go’s philosophy seems to be a very minimal/low-feature language, that’s fairly low level, even if that means somewhat more awkward or mistake-prone code. Go’s current approach seems more Go-y than an annotation like this.
> Go’s philosophy seems to be a very minimal/low-feature language, that’s fairly low level, even if that means somewhat more awkward or mistake-prone code.
And that’s why it tells you to fuck off when you have an unused variable, a non-solution to a non-problem.
Yeah, keeps the code cleaner, no unwanted variable and imports as I have tonnes of these in my Java codebase. One can use IDEs to fix it but I am not gonna generate 1000 files changed PR for this and apparently neither did last 5-6 people who worked this project.
Maybe you have not worked in these enterprise type projects where Java/Go is most likely used. In these places anything that is not build failure / compiler error is not an issue to be fixed now or ever.
You may want to take context in account when reading comments, they don’t existing in a blank void.
> One can use IDEs to fix it but I am not gonna generate 1000 files changed PR for this and apparently neither did last 5-6 people who worked this project.
That really has nothing to do with the subject at hand, and linters exist (in fact for most actual errors go requires a linter because the compiler is so anemic); for projects which are already in the pits, incremental linting is a thing (where linter errors are only a hard CI failure when they’re part of the PR’s diff).
“Currently, attributes and macros/syntax extensions are both conceptually macros: they are user-definable syntactic extensions that transform token trees to token trees.”
FWIW I definitely admit the point about Go compiler directives sort of cheating into this space a bit - I see them used responsibly for the most part but it’s a valid point. (Go’s struct tags OTOH, are an escape hatch I revile…).
In short: yes. The wording in that quote is imprecise: I suspect that by 'attributes', pcwalton was referring to user-definable attributes like #[serde(rename_all = "...")] and to custom derive macros like #[derive(Serializable)]. It is impossible to achieve the effects of the #[repr(C)] attribute using macros or token tree transformations.
> very minimal/low-feature language, that’s fairly low level, even if that means somewhat more awkward or mistake-prone code
Do you think this is a good trade-off?
If you're using a tool every day or at least regularly, the one-time cost of mastering a slightly more complex tool is amortized over all uses of that tool.
You may be using the tool every day, but are you using this "disable field reordering" annotation every day? Also, after you used it, you may remember what "#[repr(C)]" does, but I bet most of the other developers working with the code in the future will have to look it up (unless you leave a comment). So the trade-off is not as cheap as you think...
You could add something like that, but I suspect the new default behaviour would then break a number of programs (in particular things that use reflect and unsafe). There aren't many guarantees around this kind of usage but in practice the go devs are pretty reluctant to make changes that are known to break things without a very good reason, even in things where there's not a formal compatability promise.
Yeah, for sure. I didn't mean to imply that it wraps up the whole argument, merely that it was the step in the original reasoning that the parent was missing.
Look up “false sharing”, the situation where two goroutines that access disjoint sets of fields contend for the same cache line.
Compilers are not smart enough to detect it, but if they lay out struct fields in declaration order, the programmer has a way to avoid the problem: by putting the two threads’ fields far apart.
Yeah, quite often in HPC you very much do want to be able to control the alignment and packing (even though it's annoying to do), because you'll get caching issues otherwise, depending on the access patterns and size of the data.
Why not just offer the option to have manual control? That's what Rust does; by default rustc reorders fields, but you can also manually annotate your struct with #[repr(C)], which enforces no reordering.
Because in practice the Go solution is the other way around: You can optionally decide to worry about it by turning on the linter that detects this. It's not a very different solution in practice.
I actually kind of like the idea of a minimal language with a robust linting/static analysis community. You can modularly pick what things you want to worry about. The correct answer for the vast bulk of Go programmers is not to worry about this, and the ones who want to, the tools are readily available and already integrated into a tool that anyone writing serious Go code should already be using.
It makes a difference in the presence of generics, since at that point laying out fields efficiently in the face of every possible combination of types is a task that only the compiler can perform. There's nothing that says that it needs to be the default behavior, but if you want efficient space usage then you need more than a lint, you need some way to enable automatic field reordering.
Fair enough, I don't think of generics as quite existing yet so I haven't started considering them yet.
I suspect in practice we're not going to see a lot of structs with a bajillion generics in them, though. Generics are going to solve the problems the Go developers said they will solve but there's still just enough friction in them (particularly the inability to introduce new types in methods) that I expect it will not be practical to create C++-like libraries of generic things that take generics that take generics as arguments, and in practice, "stick the small number of generic things (most likely one) at the end of the struct" will mostly cover the bases.
(I have no problem saying that if you need the n'th degree in performance, you shouldn't have picked Go. I think it has a great bang-for-the-buck ratio, but it definitely does not occupy the "best possible performance" slot.)
> I suspect in practice we're not going to see a lot of structs with a bajillion generics in them
Sure, but note that it only takes a single generic parameter to exhibit this behavior. Consider the original struct definition in the OP: if we imagine that the first field was generic instead of uint8, then the struct has padding only when the type is less than 16 bits in size. No matter where you manually reorder that field, some possible types will still result in padding if the fields are forced to be laid out in order, and it took no more than a single type parameter.
Yeah. Automatically optimizing for space gives good cache footprint if you don't know anything about access patterns so it might as well be the default.
Also, with generics, there are cases where the optimal field ordering depends on the generic type parameters, so letting the compiler reorder fields on a per-generic-instance basis gives better space utilization than any given source field ordering.
Such a feature would probably require golang to either implement annotations or a new keyword.
I'm not sure golang doesn't have annotations, but probably for the same reasons it's taken so long to implement generics, it's a language stuck in the 70's, with a user base and leadership that will fight tooth and nail to try and stay that way.
Go most definitely allows annotations on structure fields [1]. You say the language is stuck in the 70s, but the GP has a quote from the Go authors saying that having the compiler reorder structure fields is a 1970s problem...
Well anyway, mostly it just sounds like the typical Rust enthusiast "How dare you have a strongly-held opinion that differs from my strongly-held opinion". As someone who used to work on a codebase that had to be portable across X86, Alpha, SPARC, and Itanium, paying attention to structure field order quickly becomes a routine matter. It hardly seems worthy of an argument over the merits of a programming language.
> Well anyway, mostly it just sounds like the typical Rust enthusiast "How dare you have a strongly-held opinion that differs from my strongly-held opinion"
To the contrary, it sounds like "Here's a solution that gives better results in 99% of cases, for reasons X, Y, Z, and better control and guarantees in those other 1% of cases."
Its not really a 70s problem, its a solution to a problem if the 1970s. RISC machines raised bus error if not properly aligned to avoid "double" access to the same value.
It does, the `//go:` stricture is a pragma / annotation.
And though I don’t remember any being at the struct-definition level, Go 1.16 added one at the “const” (toplevel var) level so adding it for structs doesn’t seem like an issue.
> with a user base and leadership that will fight tooth and nail to try and stay that way.
This is hilarious. If majority users and authors of language all like same thing then for whom this problem is to be fixed in general? Is it for non-users of Go?
Memory usage is a real problem once you have large amounts of data, of course Go is GC’d and so has a substantial memory hit anyway so I understand weighing that aspect less.
The real killer once that’s factored out is cache performance, and that really is a killer: for high performance code you can easily lose double digit %s of perf hit. You can do even worse in, but in the optimal case (a flat array) load predictors and prefetchers get you to only 10-20% hit from cache pressure.
This is my recollection from maybe 5 years ago (hell maybe even 10), so it could be worse now.
This post shows how knowledge is lost with the past of time.
>> Modern CPU hardware performs reads and writes to memory most efficiently when the data is naturally aligned.
Is not only "modern" CPUs, every RISC (80s, 40 years ago) mandate word alignment. In fact, the program will receive a bus fault if not aligned.
The compilers pad between fields to ensure alignment is right. That’s also
why "packed" structures can be defined in some languages.
>> This was is a weird quirk
Not really, a lot of code has been programed that way since I remember (80s).
There is a linter for this I believe. There can never be an automated fix for this since code can depend on the memory layout.
Anyway, this is common in programming. At least it was not 4 bytes for the alignment.
Things like this also impact performance. We had a project where we lost both memory and speed after migrating to C++. Turned out to be the virtual destructor that was the culprit.
I would not be surprised if somethings may break if there is a discrepancy between the structs and the memory layout. Stranger things have been seen. If people followed best practices, there would not be a problem in the first place. How to work with and check memory alignment is very much a known area. …and I do believe there is linter for this in Go as well.
Having manual/explicit struct layout obviously allows solving this, but the usual reason languages (at any level) have them is because it’s a nightmare to do C-Style interop without it. What’s the alternative here?
Yes, that's how I thought it worked in most languages (that have structs, and allow C-interop). You leave it open for the compiler to do anything/nothing unless you do e.g. repr(C) (In rust) or [StructLayout(LayoutKind.Explicit)] or similar (C#).
I wouldn't want this to be explicit in the spec but nor would I manage without having the back door. In languages that don't have "structs" at all, it's obviously not as necessary because you'll be forced to jump through hoops anyway (JNI, for example).
This is a good optimisation, but I can't help wondering why such a long article for something trivial and well-known for about as long as people have been programming.
It is about 10 paragraphs long, and them some code samples. And they explain it at a level that is accessible to people who don't come from a low level background. Seems pretty good to me.
Yes, they should. Also many other kinds of data representation optimizations whwre there are lots of fruit to pick. Unfortunately this rarely happens.
Language specs rarely support it well, so much of the blame is on language designers. But it's a somewhat chicken and egg situation. Language users don't demand it either because they never had it in other languages.
It does? Could you please point to a good introduction/summary? I am actually quite interested to see how they manage the ABI compatibility compared to e.g. Swift.
Swift is one of the few AOT compiled languages where they went the extra mile to ensure some kind of ABI compatibility across language versions, Go just did the usual stuff and no guarantees are given.
You can either create a dynamic linked package, that will dynamically link with other Go compiled code (from same toolchain), or expose a C ABI from a Go compiled .so (which may or may not include the runtime as well).
Huh. So it's basically undocumented w.r.t. the actual implementation details, I was mostly interested in how they manage to bolt interfaces onto structs when they're separately compiled: e.g. if libFoo.so has "struct Foo {}" and "func (x Foo) Frob() { ... }" in it, and if libFrob.so has "interface Frobber { func Frob() }", and then they're linked together to the main application, will Foo actually implement Frobber? If yes, how?
Yes, JIT runtimes have an easier time here (and can more easily do feedback based optimizations on access patterns). For AOT you can do LTO / whole program opt and punt on calls to outside libs, plus provide generics style specializable library code that is not AOT compiled.
I submit it's mostly solvable in language design. They're not all lazy of course, but claiming to be very performance-oriented is a half truth as long as you don't have a strong story here.
Smaller size is good for cache, but other factors matter
From the above
Single-Threaded Environment
When a single thread on a single core is accessing the data in a struct, we can improve caching performance by using as little cache lines as possible.
By optimizing for memory footprint, as discussed in the previous section, the struct uses less memory and hence occupies less space in the cache.
By placing heavily used members close together, we hope (based on the locality of reference principle) that they will end up closer together in the cache, preferably even on the same cache line, and hence use less cache space.
By separating hot fields form cold ones, we reduce the amount of cache lines filled with unused data.
Not undefined behaviour, but you can get "false sharing" where data from structs/member variables ends up in particular cache lines depending on their address (and the -way of the caches of the processors). Depending on the algorithm and the access patterns it's relatively common (at leasts in HPC space in my experience) to get overhead / inefficiencies due to false sharing or other aliasing issues (4k aliasing on Intel CPUs, although that's arguably a slightly different issue), due to cache line 'collisions' of different member variables being written to in the caches in sub-optimal ways due to the algorthm.
So for HPC code, you very much do want the ability to re-order them manually.
Automatic reordering makes maintaining ABI compatibility either very hard (how do you add a field to a struct if you don’t know where the compiler will put it?), or slow (objc supports field reordering, etc but it results in a lot of indirection when you access a field from outside the class’s implementation section)
C, C++, Pascal all define the order explicitly, the platform ABI generally defines the padding rules.
Most of today's apps languages, for example. But also Go documents that there's only a internal ABI that's not stable across versions, so it doesn't serve for most ABIy things, like system libraries. Rust seems to be similar. I wonder what the situation is like in GPU language land...
These languages still allow you to consume and provide C compatible ABIs explicitly but this does not interfere with data optimizations for native data.
Again, provide an actual example. Many “modern” languages don’t ship in compiled form so the important part is mostly just API.
Go and rust can’t be used for system libraries: you have to create C interface. This means that if you have two libraries, both written in rust then they have to communicate through a C layer.
The alternative (what rust does) is to have every application contain a complete copy of every library it uses, which is horrific for performance.
Modern applications languages: Clojure/ClojureScript, Java, F#, C#, Visual Basic, Python, Javascript, TypeScript, PHP, Swift, Dart, Go (included even if it's labeled as a systems language). Of those only Swift does stable ABIs.
Yep, not shipping (native) compiled code is usually how you end up with no ABIs. But these these languages and runtimes still don't really support optimizations of data structures very well, I think it's largely because they weren't specified and implementerd to do it from the start and now there are all kinds of ingrained things about the semantics and estsabilished implementations and user expectations that get in the way of doing big things like feedback based rewriting of data layouts.
> It seems fine to me for the spec not to guarantee anything about struct field order in memory. The spec doesn't operate at that level.
> That said, no Go compiler should probably ever reorder struct fields. That seems like it is trying to solve a 1970s problem, namely packing structs to use as little space as possible. The 2010s problem is to put related fields near each other to reduce cache misses, and (unlike the 1970s problem) there is no obvious way for the compiler to pick an optimal solution. A compiler that takes that control away from the programmer is going to be that much less useful, and people will find better compilers.