10 ms·
Saving a Third of Our Memory by Re-Ordering Go Struct Fields (2020)
- mytailorisrich 5y agoThis 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.
- hresvelgr 5y agoIsn't reordering struct members something that compilers should do automatically? Are there scenarios where reordering produces undefined behaviour?
- deleted 5y ago[deleted]
- onphonenow 5y agoper https://jonasdevlieghere.com/order-your-members/ https://jonasdevlieghere.com/order-your-members/ 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.
- berkut 5y agoNot 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.
- olliej 5y agoAutomatic 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.
- rsecora 5y agoUnderrated comment
- fulafel 5y agoMost languages don't have stable native ABIs.
- olliej 5y agoWhat? Define “most” here, because every actual system language has a stable ABI, otherwise they can’t be used for system libraries. 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.
- fulafel 5y agoMost 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.
- olliej 5y agoAgain, 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.
- fulafel 5y agoYes, 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.
- pjmlp 5y agoDoing it automatically messes up ABI and binary libraries infrastructure. There is more to it than lazy language designers.
- fulafel 5y agoYes, 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.
- pjmlp 5y agoThat doesn't work in environments based on shared libraries or OS IPC component models.
- masklinn 5y ago> Doing it automatically messes up ABI and binary libraries infrastructure. 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.
- pjmlp 5y agoApparently people keep missing the news that Go nowadays also does dynamic linking.
- jeffreyrogers 5y agoMost programmers don't think about memory at this level of granularity unless they've learned C or C++ or written assembly.
- pjmlp 5y agoWhen I started programming that applied to most programming languages even BASIC, ironically how things change.
- emmanueloga_ 5y agowhy not? This kind of thing should be documented somewhere. https://xkcd.com/1053/ https://xkcd.com/1053/ , etc.
- jhgb 5y agoSurely this issue is already explained in introductory programming books. Or at least it used to be, from what I recall.
- rahulpadalkar 5y agoAs a web dev i found this article rather insightful.
- bee_rider 5y agoIt 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.
- ferdowsi 5y agoWhy Go doesn't do this by default: https://github.com/golang/go/issues/10014#issuecomment-91436342 https://github.com/golang/go/issues/10014#issuecomment-91436... > 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.
- Ar-Curunir 5y agoWhy 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.
- roca 5y agoYeah. 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.
- WatchDog 5y agoSuch 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.
- Kon-Peki 5y ago
- WesternWind 5y agoSeems like a prime candidate for a linter to warn about, optionally.
- christophilus 5y agoYep. It’s baked into the Go linter, which seems like a good enough solution to me.
- meling 5y agoThis can help: https://github.com/mdempsky/maligned https://github.com/mdempsky/maligned
- oofabz 5y agoThere are tools for Go that detect non-optimal struct alignment. I use golangci-lint, available at: https://github.com/golangci/golangci-lint https://github.com/golangci/golangci-lint The struct alignment linter is not included by default. To enable it, run the linter with this command: golangci-lint run --enable maligned
- dgellow 5y agoIf you, the person reading this comment, write Go without golangci-lint, you’re really missing something. It’s fast, easy to use, and makes Go programming so much nicer and safer!
- bstpierre 5y agoAlso, don’t let the name mislead you — it’s not just for CI jobs, it’s great to use all the time.
- everybodyknows 5y ago> go get installation aren't guaranteed to work. We recommend using binary installation. The page goes on to list several difficulties with go get of the sort that suggest fundamental design flaws. Anyone have experience with this?
- icholy 5y agohttps://github.com/golang/go/issues/44840 https://github.com/golang/go/issues/44840
- nhoughto 5y agoReminds me of a similar potential gotcha in Postgres https://www.2ndquadrant.com/en/blog/on-rocks-and-sand/ 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.
- post-factum 5y agoReminds me of http://www.catb.org/esr/structure-packing/ http://www.catb.org/esr/structure-packing/
- jbub 5y agoThe standard way to check for these was https://github.com/mdempsky/maligned https://github.com/mdempsky/maligned. It is now deprecated in favour of https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/fieldalignment 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) ./...
- aneutron 5y agoThanks ! That's nice to know !
- AtNightWeCode 5y agoThere 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.
- mariusor 5y ago> There can never be an automated fix for this since code can depend on the memory layout. 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.
- AtNightWeCode 5y agoI 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.
- rsecora 5y agoThis 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).
- alkonaut 5y agoHaving 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?
- epage 5y agoRust reorders struct layout as it wishes unless you opt-in to a C-like layout, so you only pay for it when you need it.
- alkonaut 5y agoYes, 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).
- The_rationalist 5y agoHow is the situation with Java?
- japhib 5y agoI wonder if you also get a couple of wasted bytes between structs to achieve word alignment on an 8-byte boundary? In which case you’d be saving HALF your memory instead of just a third.
- Jonas_ba 5y agoGo doesnt do this by default, but there are some analyzers that help you do this - https://github.com/orijtech/structslop https://github.com/orijtech/structslop
- Too 5y agoArguably, if you are operating at such large data sets you likely benefit even more from struct-of-arrays instead of array-of-structs. This is of course a much bigger change than just moving one line in the struct definition.