Languages which allow compilers to reorganize structures for better packing (like, I think, Ada) have to have some provision to disable that in cases when the programmer requires the structure to conform to some externally imposed layout.
I wish we could say that C does this to adhere to some principle of being predictable and obeying the programmer literally. However, that cannot be claimed with a straight face by anyone who knows anything about this language, in which you can cause undefined behavior just by giving the code a dirty look in the text editor window. What C gives you with predictable structure layout, it immediately takes away with scrambled evaluation order of function arguments and constituent subexpressions of most operators.
Anyway, one consequence of a predictable layout is that C programs can do punning among structures which share a common initial sequence of members. One form of such punning is even required by ISO C to work: when a union is made of such struct types. Related hacks not involving binding through a union, however, also broadly work in de facto practice.
The optimization is present in other languages that did not start with this restriction, but it's too late for C now.
Which?
.NET is the only one I could find that appears to do some from of smart packing [1]
The new hotness languages behave like:
Go doesn't sort by size. It packs to the byte, but guarantees structures within structures will start on the 32/64bit boundary (depending on 32/64bit system) so it'll pad for them.
Rust ignores field size and just aligns to the 32bit boundary, unless you trigger `#[repr(C)]` which will pack like C. Rust doesn't give any guarantees about a structure is laid out to be perfectly honest.
C++, NIM, D.
I can find no reference on Crystal except that you can opt into C behavior. So I don't know what default is.
[1] https://msdn.microsoft.com/en-us/library/ms253935(v=vs.80).a...
It says Struct fields are aligned to to the 32/64bit boundary based on system architecture. Then you have #[repr(u8/u16/u32/u64)] which will align to 8/16/32/64 boundary.
https://doc.rust-lang.org/nomicon/repr-rust.html
The bulk of this section is describing how Rust has reserved the right to reorder and pack stuff. The first example happens to be 32-bit aligned because it contains a value that is.
A huge and important use of structs is to communicate with other things, like hardware, libraries, and other languages, and in in those cases it's very important that the struct matches what the other side expects. You don't want the compiler to rearrange your TCP packet, for example.
It might make sense to have a compiler extension to optimize packing for internal-only data structures, but I doubt any compilers bother. It's just another entry on the long list of things that C assumes the programmer will do themselves if it's important to them.
Sure you can!
// MyHeader.h
struct MyStruct {
int A;
char b;
int* c;
};
// A.cpp
#include "MyHeader.h"
<...>
// B.cpp
#pragma pack(push, 16)
#include "MyHeader.h"
#pragma pack(pop)
<...> if ((SERIAL_STATUS_PORT(port_addr) & SERIAL_DTR) != 0) {
/* DTR line is asserted */
}You see in a lot of high performance networking code too, you just get a block of bytes off the wire, cast it to a struct and use it straight away. High risk, high reward :-)
For all I know, other languages may do just this (there's a comment farther down about Rust which appears to say this).
Modern compilers all have warnings you can opt into, to alert you when the compiler inserts implicit padding, if you want to ensure things get packed nicely.
I wasn't aware of that sort of thing. any resources on learning these sorts of details of performance tuning, aside from hard-earned experience?
E.g. the page for "CPU cache" references:
- CPUs read/write by cacheline
- Caches need to coordinate to avoid stale data through "cache coherence protocols" (which have a cost as mentioned on their own wiki page)
"False sharing" is just the interplay of those two mechanisms in worst case scenarios and such corner cases.
About the only time I've used this knowledge of false sharing has been when implementing a work-stealing task queue system. And I suppose the few times I've written a parallel for loop of some description.
Trying to think of similar performance issues to guide you towards, a few come to mind:
1) CPU caches are basically implemented as fixed sized hashmaps with a really poor hash - the address modulo some power of two, with a fixed limit of collisions supported.
http://www.lshift.net/blog/2013/10/08/cpu-cache-collisions-i...
I've never actually used this knowledge, although I could see it coming up if I were working on the design of a database's in-memory storage or something.
2) Reading "write combined" memory is really bad, including implicitly reading by failing to write entire cachelines (comes up with GPU resources such as textures)
https://fgiesen.wordpress.com/2013/01/29/write-combining-is-...
This one I'm mindful of whenever I'm porting programs to use new graphics APIs, or writing the low level systems that deal with them in the first place. I feel there's at least one more situation where write combined memory has come up for me in practice (since typical memory access is not write combined), but it escapes me at the moment. Fortunately most graphics API docs at least warn you not to read the memory they're pointing you towards, although they're not always as explicit as "memcpy entire cachelines from orbit, just to be sure."
3) Performance of atomics touching multiple cachelines is terrible, when it's even supported:
https://fgiesen.wordpress.com/2014/08/18/atomics-and-content...
Normally I find out that this has been happening when I port a program to ARM and suddenly it crashes doing some kind of atomic operation or lock, because someone reinterpreted a char buffer instead of allocating properly, because cross-cacheline atomics are too crazy for ARM to bother implementing. Things like SSE and AVX also tend to perform... not so great, unless stuff is properly aligned for them.
EDIT: I guess fgiesen is one resource, at least, as it cropped up twice trying to google for sources for the things I'm talking about ;)
...so, ascending order?
This is not guaranteed. If you want to ensure all array member starting addresses are aligned for all compilers and platforms you need to add explicit dead space. You should also be using the fixed-width numeric types.
If a struct is declared like this:
struct foo {
whatever_type_t first_member;
// ...
};
then an array of this type can also be declared: struct foo farray[42];
A conforming ISO C implementation has to ensure that farray[1].first_member, and farray[2].first_member, and so on, are all allocated such that they meet the alignment requirements fro whatever_type_t. It cannot be that farray[0].first_member is accessible, but farray[1].first_member throws an alignment exception or whatever. Programmers should not have to do anything to ensure this.So, if necessary, padding is added at the end of struct foo to make this alignment happen.
In practice, compilers add the padding even if it's not required for at least two reasons: performance (misaligned accesses, though supported, may be slow) and compatibility (having the structure look the same across multiple architectures supported by the same compiler, at most modulo byte order).
> You should also be using the fixed-width numeric types.
I'm not aware that C provides any other, currently. Though you can simulate them with libraries, of course.
uint32_t and friends instead of the implementation-defined unsigned int/long.
See http://pubs.opengroup.org/onlinepubs/007904975/basedefs/stdi... for many details (including things like the name for "the fastest signed integer type with at least 8 bits", which could be signed char on machines that support byte access in hardware and signed 32-bit on machines where byte addressing means loading a word, bit-bashing the new value in, and storing it back).
6.7.2.1 para 15 of the C11 standard:
Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa.
6.7.2.1 para 17:
There may be unnamed padding at the end of a structure or union.
6.2.5 para 20:
An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type.
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf
So, on a platform with strict alignment, in order to achieve contiguous packing of structures (required by the last) and to achieve each structure member having a valid pointer (required by the first) the implementation must add enough optional padding (allowed by the middle) to make the size of the structure aligned.
> You should also be using the fixed-width numeric types.
I believe the parent is referring to the int8_t, int16_t types rather than the implementation-defined int, short, long types here.
> So, on a platform with strict alignment, in order to achieve contiguous packing of structures (required by the last) and to achieve each structure member having a valid pointer (required by the first) the implementation must add enough optional padding (allowed by the middle) to make the size of the structure aligned.
It's not in the standard per se. It's a requirement for machine code to function on certain platforms. The standard basically just says that in all cases compilers have to generate machine code that works properly. It is imposed by the designers of the processor, not the C standard.
> I believe the parent is referring to the int8_t, int16_t types rather than the implementation-defined int, short, long types here.
This is indeed what I was talking about.
The alignment requirement is platform-dependent. Some platforms can perform unaligned loads, which means an object can be allocated at any byte offset in memory. There are no requirements in the C standard for alignment other than conforming to the specific hardware.
> In practice, compilers add the padding even if it's not required for at least two reasons: performance (misaligned accesses, though supported, may be slow) and compatibility (having the structure look the same across multiple architectures supported by the same compiler, at most modulo byte order).
Yes, and in practice this depends on the compiler and the platform, which was my point.
> I'm not aware that C provides any other, currently. Though you can simulate them with libraries, of course.
None of the numeric types enumerated in the standard have a fixed size associated with them in the C standard[1]. They have minimum representation ranges, but that is it.
[1] I'm not counting IEEE754 floating-point types, since that is a standard imposed on the C standard itself.
(The option would be nice, though... most of the time, you don't care.)
The worst that you will get is padding at the end of the structure so that if two or more of them are arrayed, the first member is correctly aligned at all the array indices.