Implementing alignof

Why care about alignment?

Neither the C nor C++ standard mentions alignment. Most programs can just ignore its existence. You need to worry about alignment when:

Some compilers implement alignof (or __alignof__) as an extension, but we like portability.

C Implementation

C is easy because all data types are Plain Ol' Data (POD) and struct layout order is predictable.

#define ALIGNOF(type) offsetof (struct { char c; type member; }, member)

This implementation is simple and effective, but it has a problem typical of C macros — it doesn't work for inside out declarations like

    void (*) (void)

But there's a typical C workaround — users just call ALIGNOF with a typedef'ed name.

    typedef void (*fptr) (void);
    ... ALIGNOF (fptr) ...

C++ Implementation #1

The above implementation doesn't work for C++. The C++ committee has decreed:

Types must be declared in declarations, not in expressions.

We will need to declare our struct outside of any expression. But we would like the call to ALIGNOF to be an expression. If only we could declare a struct that would work for any embedded type T ….

With the power of templates, we can.

template<typename T> struct alignment_trick { char c; T member; };
#define ALIGNOF(type) offsetof (alignment_trick<type>, member)

This doesn't have the "inside out" declaration bug that C does.

Unfortunately, the C++ standard does not allow the offsetof macro to be used with non-POD data types. If we want to support those, we'll have to be a little cleverer.

C++ Implementation #2

The sizeof operator is fundamental to making many C++ metaprogramming techniques possible.

One idea is to note that alignment is always a power of two, and the alignment must be a factor of the size of an object (else an array of such objects would have some of them misaligned). We can implement this using standard bit-twiddling tricks, which you should learn because they will prove useful on a job interview someday.

    template <typename T>
    struct alignof
    {
      enum { s = sizeof (T), value = s ^ (s & (s - 1)) };
    };

This implementation has the advantage that a type like  char [7]  has an alignment of 1, but it doesn't work very well for basic fundamental types, most of which have sizes that are a power of two.

C++ Implementation #3

Another idea is to create a succession of structs, like this:

    struct S1 { T x; char c1; };
    struct S2 { T x; char c1; char c2; };
    struct S3 { T x; char c1; char c2; char c3; };
    struct S4 { T x; char c1; char c2; char c3; char c4; };
    ...

Some of these structs might have the same size as T, because existing padding in T was being reused. But eventually, as more chars are added, the size has to jump eventually. That jump is very likely to be the alignment of T, and at worst, is a multiple of the alignment.

    template <typename T> struct alignof;

    template <typename T, int size_diff>
    struct helper
    {
      enum { value = size_diff };
    };

    template <typename T>
    struct helper<T, 0>
    {
      enum { value = alignof<T>::value };
    };

    template <typename T>
    struct alignof
    {
      struct Big { T x; char c; };

      enum { diff = sizeof (Big) - sizeof (T),
             value = helper<Big, diff>::value };
    };

Unfortunately, not every compiler supports partial template specialization yet. To make our code more portable, we rewrite as follows:

    template <typename T> struct alignof;

    template <int size_diff>
    struct helper
    {
      template <typename T> struct Val { enum { value = size_diff }; };
    };

    template <>
    struct helper<0>
    {
      template <typename T> struct Val { enum { value = alignof<T>::value }; };
    };

    template <typename T>
    struct alignof
    {
      struct Big { T x; char c; };

      enum { diff = sizeof (Big) - sizeof (T),
	     value = helper<diff>::template Val<Big>::value };
    };

Combining implementations

We can combine the two above techniques (neither one wins consistently) like this:

    template <typename T>
    struct alignof
    {
      enum { x = ffs::alignof<T>::value,
	     y = QuantumJump::alignof<T>::value,
	     value = x < y ? x : y };
    };

#define ALIGNOF(type) alignof<type>::value

Exercise for the reader: should we also merge C++ implementation #1?

Amazing facts about alignment

On modern x86 processors, the type double is most efficiently aligned at multiples of 8. And in fact, gcc aligns "free" doubles at multiples of 8 within stack frames. Unfortunately, ancient ABIs require that the alignment of a double within a struct is 4. The unexpected consequence is that, on x86 Linux, gcc has

   struct Double { double d; };
   __alignof__ (double) == 8
   __alignof__ (Double) == 4;

The same ancient ABIs specify that the size of long double is 12. Because the alignment must be a factor of the size, we have the curious situation that:

   __alignof__ (double) == 8
   __alignof__ (long double) == 4;

even though long double "wants" to be at least as aligned as double.

All of our alignof implementations have embedded types within structs. Is there any way to detect the difference in alignment between types like double and Double at compile time? I don't know of any way. Fortunately, it doesn't matter very much, because we never care about the alignment of types that aren't struct members.

Previous work

Both Andrei Alexandrescu and Herb Sutter discuss alignof in recent articles.

[1] Andrei Alexandrescu. "Discriminated Unions (II)" (C/C++ Users Journal, 20(6), June 2002).

[2] Herb Sutter. "Style Case Study #3: Construction Unions" (GotW #85).

Complete Source Code

An implementation of ALIGNOF for C++ and C, together with a test suite, is available here. Also included is a portable implementation of ALIGN_POD_TYPE, which returns, for a given type, a POD type with the same alignment as that type.


Back to Martin's home page
Last modified: Wed Feb 5 21:26:31 PST 2003
Copyright © 2003 Martin Buchholz