The Lost Art of C Structure Packing(catb.org)
catb.org
The Lost Art of C Structure Packing
http://www.catb.org/esr/structure-packing/
51 comments
Awareness of the layout and size of data is still very common in game development. Mike Acton did a great talk related to this at CppCon a few years ago : https://www.youtube.com/watch?v=rX0ItVEVjHc
This is true for high performance server software, too, especially servers that resemble databases.
I personally find myself thinking about alignment more than I probably should. For Go, I use http://golang-sizeof.tips for experimenting. I've been able to make schema changes to my structs to enable more functionality without increasing memory usage.
I personally find myself thinking about alignment more than I probably should. For Go, I use http://golang-sizeof.tips for experimenting. I've been able to make schema changes to my structs to enable more functionality without increasing memory usage.
Lost but not forgotten.
IDK, most these rules are very trivial and fairly simple to automate. Pretty much boils down to declare the smallest fields first, with a handful of exceptions based on the modulus of size.
Ultimately I like Rust’s approach. Without including ‘[repr(C)]/[repr(packed)]’ the compiler is free to layout the structure in the most efficient way for the target platform. And accessing fields with different compiler’s code is UB. You get the speed up, while keeping backwards compatibility.
Sadly C/C++ are shackled to this archaic system. Also I believe Go, Nim, and Swift are as well (this is speculation).
IDK, most these rules are very trivial and fairly simple to automate. Pretty much boils down to declare the smallest fields first, with a handful of exceptions based on the modulus of size.
Ultimately I like Rust’s approach. Without including ‘[repr(C)]/[repr(packed)]’ the compiler is free to layout the structure in the most efficient way for the target platform. And accessing fields with different compiler’s code is UB. You get the speed up, while keeping backwards compatibility.
Sadly C/C++ are shackled to this archaic system. Also I believe Go, Nim, and Swift are as well (this is speculation).
It's not even lost. Any C code that cares about performance will eventually look into how structures are laid out in cache lines.
It is a requirement for code heavily using atomics as false shares and destroy performance.
[deleted]
If switching compilers results in UB, how is that keeping backwards compatibility?
`[repr(C)]` maintains compatibility with C-ABI, therefore keeping backwards compatibility with C, C++, Rust, etc. As the C ABI, and C structure layout rules are standardized across platforms.
clang-tidy has a struct padding check which diagnoses non-optimal struct orders, and a coworker contributed a clang tool to reorder fields: https://github.com/llvm-mirror/clang-tools-extra/tree/master...
This makes sense if you're only concerned with size. Locality or eliminating false sharing may be more important in large ones
Not lost if you are programming on a mainframe... just not blogged about.
.. And not applicable to 8-bit embedded programmers.
Are you sure? You can still declare a short field on a 8b micro.
What are the alignment requirements for one there though? Unaligned access can come with performance cost or be impossible on 16 and 32 bit machines for some cases (I don't know all the details for ARM and x86) but I'd assume (I don't definitely KNOW, just making an educated guess) that an 8 bit machine that can only do 8 bit operations doesn't need alignment at all and using a short (or a long) always involves reading 8 bits twice (or 4 times) and any 8 bits at all can be read so it can be packed completely tightly. Meanwhile (I'm again just guessing, I'm not low level enough to know that), 16 and 32 bit machines try to read it all in one go into a register and that's why they need alignment or else they take the performance hit to read twice and mask out the value or raise an exception.
This art is certainly not lost though it comes up with language VMs, native compilers, Linux kernel, as a common curio about C and C++, etc.
This art is certainly not lost though it comes up with language VMs, native compilers, Linux kernel, as a common curio about C and C++, etc.
I tried the example below, saved as `main.c`. It seems she automatically reorders the static mem. Can that behavior be disabled? Can someone please explain?
#include<stdio.h>
int main(int argc, char** argv)
{
char *p;
char c;
int x;
printf("char p %p\n", &p);
printf("char %p, offset %i\n", &c, (int)((void*)&c-(void*)&p));
printf("integer %p, offset %i\n", &x, (int)((void*)&x-(void*)&p));
return 0;
}
char p 0x7ffc5107dff0
char 0x7ffc5107dfeb, offset -5
integer 0x7ffc5107dfec, offset -4Those are not structure members. C provides no guarantees about the relative locations of separate variables.
So, it's a compiler specific reordering?
Yes. Probably specific to compiler options too. Only structure members have a defined order.
Variables like that don't even have to have unique addresses. They may live only in registers, or if their usage doesn't overlap they can be given the same stack address!
Subtraction of arbitrary pointers is not legal.
You're technically right, because you can have C compilers for architectures with all sorts of weird memory semantics. But in reality, this will work as expected on all of the major platforms and give you the relative positions of the variables on the stack.
The C standard is not the final say on things, your compiler and platform are. The standard is merely the minimum specifications that are ideally to be supported on all platforms, however you will still be unpleasantly surprised if you rely on it as such.
The C standard is not the final say on things, your compiler and platform are. The standard is merely the minimum specifications that are ideally to be supported on all platforms, however you will still be unpleasantly surprised if you rely on it as such.
It's not defined by the language standard. Real machine addresses have values and can be compared.
Say, you run on 8051. What should the comparison result be for idata pointer with value 4, and xdata pointer 4?
What about kernels (Linux, Windows — doesn't matter)... how do you compare physical address pointer with virtual address pointer?
Sure, they have values. But that might not mean much. Pointers can point to entirely different address spaces.
What about kernels (Linux, Windows — doesn't matter)... how do you compare physical address pointer with virtual address pointer?
Sure, they have values. But that might not mean much. Pointers can point to entirely different address spaces.
Exactly. The behavior of the actual machine matters!
The C language standard defines (pretty imperfectly in the case of processors with multiple address spaces like the 8051 scratchpad RAM) something like a least common denominator you can rely on to "write portable C".
But that's not truth, nor is "portable C" the goal to all engineering efforts. Pointers are numbers. Scratchpad registers can't have pointers taken to them. Those are truths, even if inconvenient.
The C language standard defines (pretty imperfectly in the case of processors with multiple address spaces like the 8051 scratchpad RAM) something like a least common denominator you can rely on to "write portable C".
But that's not truth, nor is "portable C" the goal to all engineering efforts. Pointers are numbers. Scratchpad registers can't have pointers taken to them. Those are truths, even if inconvenient.
Well, you can compare pointers (to distinct objects) too, but only for equality.
(The only in any case not-undefined way of calculating some sort of difference value between such is with the use of the optional uintptr_t, but I'd guess this isn't a sort of undefined behaviour which triggers unwanted compiler tricks, anyway.)
(The only in any case not-undefined way of calculating some sort of difference value between such is with the use of the optional uintptr_t, but I'd guess this isn't a sort of undefined behaviour which triggers unwanted compiler tricks, anyway.)
What does "can be compared" mean? To me it means that "<=>" [1] is well-defined. It doesn't say anything about numerical values.
[1] Spaceship operator. Think "return value of memcmp" but generalized to any operand types.
[1] Spaceship operator. Think "return value of memcmp" but generalized to any operand types.
Any valid pointer values can be compared for equality. Only pointers that point within a single object (like an array, or a struct) can be compared for ordering. Nesting doesn't matter as long as down the line there's a common "parent" of sorts. (That is, if you want to have well-defined behaviour.)
(Edit: and for any pointers that you can compare for ordering, you may also calculate their offset from one another. However, like GP said, in practice you can do that for any pointers on common platforms.)
(Edit: and for any pointers that you can compare for ordering, you may also calculate their offset from one another. However, like GP said, in practice you can do that for any pointers on common platforms.)
No, real pointer values have numerical values. They are numbers, period. You guys are getting balled up thinking about the language standard as the "ultimate reference of truth" in the argument. When the whole point of the linked article is about pointing out that, no, the behavior of the actual machine being used is a more important "truth" in some contexts.
Well, if it's not in the standard, the compiler might disagree with you and produce output different from what you expect. You're not programming the actual machine, you're communicating intended program behavior to the compiler, who programs the actual machine. If you want to avoid misunderstandings between you and the compiler, you'd better adhere to the language definition.
If you are writing normal code then yes. But there are always exceptions.
One is trying to learn how your current target architecture actually works. This is not production code. It's a "where in memory did the compiler decide to put that" question. You may get the results you expect or you may get someting totally bizzare. But since the purpose is discovering how the compiler works there is no wrong result.
Another is if you are writing your own memory manager. Here there are a lot of pointer comparisons to not the same allocated objects. But a memory manager is very OS and architecture specific so you will probably have to rewrite it when porting the code.
Having said all that, I wouldn't subtract the two void pointers like the example did. I would have converted them both to integers first and then subtract. Again, since this is for debugging and/or learning purposes then it's OK to bend the language rules a bit.
One is trying to learn how your current target architecture actually works. This is not production code. It's a "where in memory did the compiler decide to put that" question. You may get the results you expect or you may get someting totally bizzare. But since the purpose is discovering how the compiler works there is no wrong result.
Another is if you are writing your own memory manager. Here there are a lot of pointer comparisons to not the same allocated objects. But a memory manager is very OS and architecture specific so you will probably have to rewrite it when porting the code.
Having said all that, I wouldn't subtract the two void pointers like the example did. I would have converted them both to integers first and then subtract. Again, since this is for debugging and/or learning purposes then it's OK to bend the language rules a bit.
That value of truth is what allows C compilers to wipe out your beloved code on -O3, because you just feel entitled to write UB code.
Why would you want to disable that behavior? If you need them in a specific order, you can disable that behavior by using a struct. Ideally, your automatic variables won't have any memory location at all because they're optimized out or kept in registers.
First: you have UB; %p requires void *.
Second: separate variables don't have to appear in memory in source code order. This applies only to struct members, which do.
Second: separate variables don't have to appear in memory in source code order. This applies only to struct members, which do.
[deleted]
Those are on the stack, and the stack grows down.
That's true most of the time yes. But it's not a rule, some architectures allow the stack pointer to grow in either direction: https://stackoverflow.com/questions/664744/what-is-the-direc...
I've found file: unaligned-memory-access.txt useful.
Ref:- Linux Kernel Source: UNALIGNED MEMORY ACCESSES
Link: https://github.com/torvalds/linux/blob/master/Documentation/...
Hint, compile with -Wpacked
Have to disagree with you here, totally depends on the platform and if you know what you’re doing. Compiling with this option can lead to unaligned memory accesses. On some architectures, most ARM ones for example, unaligned memory accesses lead to hard faults at runtime.
You're thinking of `#pragma pack`. `-Wpadded` just warns about non-optimal layout.
Whoops, yes my bad. -Wpacked will just issue the warning, not actually do the packing!
Wait, doesn't the compiler produce the appropriate code for accessing the packed values without using unaligned memory access if the target platform doesn't support that?
This is going to sound rude but it is not my intention. The reality is that packing DOES NOT matter for most applications these days.
I read an article about a person who was the last in the world to speak some obscure language. Some people wanted to start a school to teach others to speak that language, wanted the government to pay for it, etc.
The two articles gave me the same combined feel of “I feel a little sorry but not a lot” and “who cares.”
The compiler will take care of most.
Unfortunately for that person on the other article, he is basically screwed.
Don’t let that be you.
I read an article about a person who was the last in the world to speak some obscure language. Some people wanted to start a school to teach others to speak that language, wanted the government to pay for it, etc.
The two articles gave me the same combined feel of “I feel a little sorry but not a lot” and “who cares.”
The compiler will take care of most.
Unfortunately for that person on the other article, he is basically screwed.
Don’t let that be you.
The compiler cannot reorder the fields.
This stuff comes up occasionally in optimizing layout of language VM structures, compilers, in the Linux kernel and other low level situations.
I.e. JVM compressed object pointers rely on the alignment and the native objects representation is definitely well laid out to not waste space due to alignment:
https://stackoverflow.com/a/25120926
https://blog.codecentric.de/en/2014/02/35gb-heap-less-32gb-j...
Lua implementation similarly cares about alignment in some cases:
http://lua-users.org/lists/lua-l/2009-02/msg00305.html
This is not exactly 'struct packing' but alignment is closely connected to padding so its part of a wider interconnected topic.
I.e. JVM compressed object pointers rely on the alignment and the native objects representation is definitely well laid out to not waste space due to alignment:
https://stackoverflow.com/a/25120926
https://blog.codecentric.de/en/2014/02/35gb-heap-less-32gb-j...
Lua implementation similarly cares about alignment in some cases:
http://lua-users.org/lists/lua-l/2009-02/msg00305.html
This is not exactly 'struct packing' but alignment is closely connected to padding so its part of a wider interconnected topic.
Urm, the mere fact that somebody is capable to micro-manage every different aspect and detail about a program is purely theoretical, as nobody talks about actually doing so, or if, how often that is done.
It just makes them a competent developer/computer scientist. Just like emergency protocols aren't used often by airplane pilots, doesn't mean they're completely useless.
You may be right, as you'll never be trying to make a binary fit an artificially imposed size limit or things like this, as is sometimes necessary in the demo scene. In my experience, having aspiration always outweighs the ignorance of not having it. YMMV.
It just makes them a competent developer/computer scientist. Just like emergency protocols aren't used often by airplane pilots, doesn't mean they're completely useless.
You may be right, as you'll never be trying to make a binary fit an artificially imposed size limit or things like this, as is sometimes necessary in the demo scene. In my experience, having aspiration always outweighs the ignorance of not having it. YMMV.
I deal with this every day when writing lock free data structures. If you want to really make use of all those cores you can buy now, someone has to pay attention.
Only for certain values of "most". As the author mentions, kernels and embedded applications very often need to have tight control over memory layout.
You probably should not be using C.
depending on what you mean by "most applications", that's been the case for 20+ years.
that said, compilers can't "take care" of a lot of things; and either way, people are still needed to develop and maintain those compilers.
there will also always be software that has significant performance requirements, and opportunities to write higher performing software than competitors.
that said, compilers can't "take care" of a lot of things; and either way, people are still needed to develop and maintain those compilers.
there will also always be software that has significant performance requirements, and opportunities to write higher performing software than competitors.