tags:

views:

2279

answers:

8

Can the alignment of a structure type be found if the alignments of the structure members are known?

Eg. for:

struct S
{
 a_t a;
 b_t b;
 c_t c[];
};

is the alignment of S = max(alignment_of(a), alignment_of(b), alignment_of(c))?

Searching the internet I found that "for structured types the largest alignment requirement of any of its elements determines the alignment of the structure" (in What Every Programmer Should Know About Memory) but I couldn't find anything remotely similar in the standard (latest draft more exactly).


Edited: Many thanks for all the answers, especially to Robert Gamble who provided a really good answer to the original question and the others who contributed.

In short:

To ensure alignment requirements for structure members, the alignment of a structure must be at least as strict as the alignment of its strictest member.

As for determining the alignment of structure a few options were presented and with a bit of research this is what I found:

  • c++ std::tr1::alignment_of
    • not standard yet, but close (technical report 1), should be in the C++0x
    • the following restrictions are present in the latest draft: Precondition:T shall be a complete type, a reference type, or an array of unknown bound, but shall not be a function type or (possibly cv-qualified) void.
      • this means that my presented use case with the C99 flexible array won't work (this is not that surprising since flexible arrays are not standard c++)
    • in the latest c++ draft it is defined in the terms of a new keyword - alignas (this has the same complete type requirement)
    • in my opinion, should c++ standard ever support C99 flexible arrays, the requirement could be relaxed (the alignment of the structure with the flexible array should not change based on the number of the array elements)
  • c++ boost::alignment_of
    • mostly a tr1 replacement
    • seems to be specialized for void and returns 0 in that case (this is forbidden in the c++ draft)
    • Note from developers: strictly speaking you should only rely on the value of ALIGNOF(T) being a multiple of the true alignment of T, although in practice it does compute the correct value in all the cases we know about.
    • I don't know if this works with flexible arrays, it should (might not work in general, this resolves to compiler intrinsic on my platform so I don't know how it will behave in the general case)
  • Andrew Top presented a simple template solution for calculating the alignment in the answers
    • this seems to be very close to what boost is doing (boost will additionally return the object size as the alignment if it is smaller than the calculated alignment as far as I can see) so probably the same notice applies
    • this works with flexible arrays
  • use Windbg.exe to find out the alignment of a symbol
    • not compile time, compiler specific, didn't test it
  • using offsetof on the anonymous structure containing the type
    • see the answers, not reliable, not portable with c++ non-POD
  • compiler intrinsics, eg. MSVC __alignof
    • works with flexible arrays
    • alignof keyword is in the latest c++ draft


If we want to use the "standard" solution we're limited to std::tr1::alignment_of, but that won't work if you mix your c++ code with c99's flexible arrays.

As I see it there is only 1 solution - use the old struct hack:

struct S
{
 a_t a;
 b_t b;
 c_t c[1]; // "has" more than 1 member, strictly speaking this is undefined behavior in both c and c++ when used this way
};

The diverging c and c++ standards and their growing differences are unfortunate in this case (and every other case).


Another interesting question is (if we can't find out the alignment of a structure in a portable way) what is the most strictest alignment requirement possible. There are a couple of solutions I could find:

  • boost (internally) uses a union of variety of types and uses the boost::alignment_of on it
  • the latest c++ draft contains std::aligned_storage
    • The value of default-alignment shall be the most stringent alignment requirement for any C++ object type whose size is no greater than Len
      • so the std::alignment_of< std::aligned_storage<BigEnoughNumber>>::value should give us the maximum alignment
      • draft only, not standard yet (if ever), tr1::aligned_storage does not have this property

Any thoughts on this would also be appreciated.

I have temporarily unchecked the accepted answer to get more visibility and input on the new sub-questions

A: 

I don't think memory layout is guaranteed in any way in any C standard. This is very much vendor and architect-dependent. There might be ways to do it that work in 90% of cases, but they are not standard.

I would be very glad to be proven wrong, though =)

gnud
There are actually several guarantees made by the standard including: 1) there is no padding before the first member of a structure, 2) structure members are arranged in memory in the order they are defined, and 3) arrays do not have padding between their members.
Robert Gamble
Combine these guarantees with the fact that all structures can be used as array elements and it follows that the alignment of a structure must be at least as strict as the alignment of its most strict member.
Robert Gamble
I know we're talking about C here, but just to be clear, C++ relaxes the requirement that struct members be arranged in the order they are defined in certain conditions.
Michael Burr
@Mike BTrue, but the C rules still apply if the type is POD.
Hrvoje Prgeša
+13  A: 

There are two closely related concepts to here:

  1. The alignment required by the processor to access a particular object
  2. The alignment that the compiler actually uses to place objects in memory

To ensure alignment requirements for structure members, the alignment of a structure must be at least as strict as the alignment of its strictest member. I don't think this is spelled out explicitly in the standard but it can be inferred from the the following facts (which are spelled out individually in the standard):

  • Structures are allowed to have padding between their members (and at the end)
  • Arrays are not allowed to have padding between their elements
  • You can create an array of any structure type

If the alignment of a structure was not at least as strict as each of its members you would not be able to create an array of structures since some structure members some elements would not be properly aligned.

Now the compiler must ensure a minimum alignment for the structure based on the alignment requirements of its members but it can also align objects in a stricter fashion than required, this is often done for performance reasons. For example, many modern processors will allow access to 32-bit integers in any alignment but accesses may be significantly slower if they are not aligned on a 4-byte boundary.

There is no portable way to determine the alignment enforced by the processor for any given type because this is not exposed by the language, although since the compiler obviously knows the alignment requirements of the target processor it could expose this information as an extension.

There is also no portable way (at least in C) to determine how a compiler will actually align an object although many compilers have options to provide some level of control over the alignment.

Robert Gamble
i believe you are right. but i find it difficult to make the logical conclusion out of the three facts. could you outline the main steps please?
Johannes Schaub - litb
wait i think i get it. if the alignment of the struct was less strict, then there wouldn't be a way to pad the members correctly. the alignment of the struct must be a multiple of the alignment of all its members' alignment right?
Johannes Schaub - litb
I'm not sure what you don't follow, I think that is about as well as I can put it. Do you accept the 3 statements I made? If so, a structure that did not have the the alignment of it strictest member would have members that are not be properly aligned in an array of such structures.
Robert Gamble
I think you've got it now, it there is a way you think I can be more clear, please let me know and I will update my answer.
Robert Gamble
your answer is all fine i think. got it now :)
Johannes Schaub - litb
As for determining the alignment, what about c++ std::tr1::alignment_of<S>::value?
Hrvoje Prgeša
I don't know about alignment_of (I am a C programmer, don't know much C++), is that standard? Can you provide a link?
Robert Gamble
I am not sure about the second point. Assume you have a struct S { int a; char b; }, in a 32 bit architecture that requires integers to be bound to a 4 byte boundary. Surely an array of S will have padding between two elements, would it not?
David Rodríguez - dribeas
@dribeas: No, the padding would have to be part of the structure. You can try this out for yourself by printing out the value of sizeof(struct S).
Robert Gamble
Thanks for the clarification.
David Rodríguez - dribeas
@Robert Gamblealignment_of is standard (technical report 1 more precisely).MSDN link: http://msdn.microsoft.com/en-us/library/bb982233.aspx
Hrvoje Prgeša
"The alignment of a structure must at least as great as the alignment of each of its members" - the "at least" part is still bugging me - why would it ever be larger?
Hrvoje Prgeša
@Hrvoje: I can't think of any reason that the alignment be greater on the structure than any of its members although the compiler could insert as much padding as it wants to the end. I'll update my answer after I think about this a little more...
Robert Gamble
isn't that obvious? struct as{ char a; char b; }; << align on 4byte for better speed ? anyway tr1 is not the c++ standard.
Johannes Schaub - litb
@litb now its obvious, thank youYes, you're right - its not standard yet, just planned for inclusion in c++0x
Hrvoje Prgeša
+2  A: 

It is possible to assume a structure alignment if you know more details about the compiler options that are in use. For example, #pragma pack(1) will force alignment on the byte level for some compilers.

Side note: I know the question was about alignment, but a side issue is padding. For embedded programming, binary data, and so forth -- In general, don't assume anything about structure alignment if possible. Rather use explicit padding if necessary in the structures. I've had cases where it was impossible to duplicate the exact alignment used in one compiler to a compiler on a different platform without adding padding elements. It had to do with the alignment of structures inside of structures, so adding padding elements fixed it.

Ryan
I think you are confusing alignment with padding, they are related but distinct concepts. Padding is used to ensure proper alignment which is what the pack pragma handles; if you need to use explicit padding in your structure there is almost certainly something wrong with the code that accesses it.
Robert Gamble
If you program embedded devices or binary communications, you end up dealing with alignment *and* padding quite often. Although the question was about alignment, I just wanted to mention padding in case it was a side issue.
Ryan
I'm also curious about your statement, "...if you need to use explicit padding in your structure..." Have you programmed ebedded devices and cross-platform/compiler? Have you have seen the Linux kernal code? Sometimes it is absolutely necessary.
Ryan
@Robert Gamble: "there is almost certainly something wrong with the code" Not necessarily. If you want to ensure that two elements do not appear on the same Cache Line, in order to prevent ping-pong on a multi-core processor, you need to add the correct amount of padding between elements manually.
ceretullis
+2  A: 

As the others mentioned, its implementation dependant. Visual Studio 2005 uses 8 bytes as the default structure alignment. Internally, items are aligned by their size - a float has 4 byte alignment, a double uses 8, etc.

You can override the behavior with #pragma pack. GCC (and most compilers) have similar compiler options or pragmas.

Dan Hewett
+5  A: 

I wrote this type trait code to determine the alignment of any type(based on the compiler rules already discussed). You may find it useful:

template <class T>
class Traits
{
public:
    struct AlignmentFinder
    {
     char a; 
     T b;
    };

    enum {AlignmentOf = sizeof(AlignmentFinder) - sizeof(T)};
};

So now you can go:

std::cout << "The alignment of structure S is: " << Traits<S>::AlignmentOf << std::endl;
Andrew Top
This should be equivalent to std::tr1::alignment_of<T>::value, though it is a really clean and simple implementation.
Hrvoje Prgeša
Didn't know about std::tr1::alignment_of<T>... Too bad, I did some searching too and didn't find anything. Thanks for mentioning it.
Andrew Top
+2  A: 

The following macro will return the alignment requirement of any given type (even if it's a struct):

#define TYPE_ALIGNMENT( t ) offsetof( struct { char x; t test; }, test )

Note: I probably borrowed this idea from a Microsoft header at some point way back in my past...


Edit: as Robert Gamble points out in the comments, this macro is not guaranteed to work. In fact, it will certainly not work very well if the compiler is set to pack elements in structures. So if you decide to use it, use it with caution.

Some compilers have an extension that allows you obtain the alignment of a type (for example, starting with VS2002, MSVC has an __alignof() intrinsic). Those should be used when available.

Michael Burr
This will give you the alignment the compiler choose to use for type t within the given structure but this might not be the alignment of type t when it doesn't appear in such a structure.
Robert Gamble
I grant that the standard may not guarantee this macro will work, so it may be appropriate to guard it with #if preprocessor controls so it's defined correctly for particular compilers. That said, it does seem to work quite well in prctice.
Michael Burr
Also, as I recall, offsetof is only guarantied to work for PODs only so if t is a non POD this is again outside the standard.
Hrvoje Prgeša
+2  A: 

If you want to find this out for a particular case in Windows, open up windbg:

Windbg.exe -z \path\to\somemodule.dll -y \path\to\symbols

Then, run:

dt somemodule!CSomeType
Paul Betts
+1  A: 

I agree mostly with Paul Betts, Ryan and Dan. Really, it's up to the developer, you can either keep the default alignment symanic's which Robert noted about (Robert's explanation is just the default behaviour and not by any means enforced or required), or you can setup whatever alignment you want /Zp[##].

What this means is that if you have a typedef with floats', long double's, uchar's etc... various assortments of arrays's included. Then have another type which has some of these oddly shaped members, and a single byte, then another odd member, it will simply be aligned at whatever preference the make/solution file defines.

As noted earlier, using windbg's dt command at runtime you can find out how the compiler laid out the structure in memory.

You can also use any pdb reading tool like dia2dump to extract this info from pdb's statically.

RandomNickName42