Saving a Third of Our Memory by Re-Ordering Go Struct Fields (2020)
wagslane.dev
wagslane.dev
> 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.
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.
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.
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.)
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.
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)
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.
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.
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).
Nobody said you should not be able to do it, at all? The argument is about default behaviour.
Rust is specifically a langage which reorders by default.
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.
Thats the 70s problem described in the documentation
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.
By Go doing nothing, a developer can manually solve both A and B.
So, currently, there is no way to force memory layout, other than, as https://github.com/golang/go/issues/10014#issuecomment-26346... says
“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.”
Seems unsatisfactory to me.
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.
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)
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.
And that’s why it tells you to fuck off when you have an unused variable, a non-solution to a non-problem.
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).
Agree.
But you do not have to ever understand others point of view because your opinion is a fact and absolute must on any programing language design.
“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.
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.
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.
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.
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.)
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.
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.
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.
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."
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.
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?
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.
It is now deprecated in favour of https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/fie....
You can now check for these using go vet:
go install golang.org/x/tools/go/analysis/passes/fieldalignment/cmd/fieldalignment@latest
go vet -vettool=$(which fieldalignment) ./...>> 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).
The struct alignment linter is not included by default. To enable it, run the linter with this command: golangci-lint run --enable maligned
It’s fast, easy to use, and makes Go programming so much nicer and safer!
The page goes on to list several difficulties with go get of the sort that suggest fundamental design flaws. Anyone have experience with this?
https://www.2ndquadrant.com/en/blog/on-rocks-and-sand/
The linting story for postgres schemas isn't as good as it is in golang tho, so harder to automatically detect/solve for.
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 think that's very specifically discouraged in Go, unless there's a way to do it without using the "unsafe" package that I don't know of:
> Package unsafe contains operations that step around the type safety of Go programs.
> Packages that import unsafe may be non-portable and are not protected by the Go 1 compatibility guidelines.
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 of course a much bigger change than just moving one line in the struct definition.
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.
There is more to it than lazy language designers.
Neither is an issue in Go, since everything’s statically compiled and it doesn’t make any ABI guarantee.
Making this opt-out (or making precise layout opt-in) actually improves the situation there, because then you have clear, explicit guarantees.
As for the documentation,
Check -dynlink and -shared on "go compile"
https://pkg.go.dev/cmd/compile@go1.17.6
Also -buildmode and -shared on "go link"
https://pkg.go.dev/cmd/link#hdr-Command_Line
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).
As for one possible example,
https://www.ardanlabs.com/blog/2020/07/extending-python-with...
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.
So for HPC code, you very much do want the ability to re-order them manually.
C, C++, Pascal all define the order explicitly, the platform ABI generally defines the padding rules.
If you include toy languages, you might get there.
Even languages like Go and Rust recognize that at API boundaries you need a stable and defined ABI.
These languages still allow you to consume and provide C compatible ABIs explicitly but this does not interfere with data optimizations for native data.
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.
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.
In which case you’d be saving HALF your memory instead of just a third.