Calculating safe alignment for any type

23 views

Tom

Nov 28, 2004, 1:08:35 PM11/28/04
to
I recently finished reading Herb Sutter's Exceptional C++ style. In the
book he mentions again the long standing problem of calculating alignment
for a type T.

In this post I will (hopefully) show how to calculate safe alignment for any
type T.

First a few definitions:
I will refer to arbitrary addresses as a(n) (e.g. a(1), a(2)) and to
addresses of specific data as a(<name>).
(e.g. a(t) == &t)

Unknown constants, n(<name>), where n(<name>) >= 0

Alignment of T is X(T), s.t. a(t) % X(T) = 0, or X(T) * n(t) = a(t), for
some n(t).

Now to the solution:

Consider the following struct:

template<class T>
struct A
{
char c;
T t;
};

The "c" member is in the stuct to ensure that sizeof(A<T>) > sizeof(T).

Now consider an array of A<T> in memory starting at address a(A).
We can say that

a(t) = a(A) + spaceBefore(c) + sizeof(char) + spaceAfter(c) //1

but because A<T>::t needs to be aligned on a T boundary, we have

Rewrite 1 as

a(t) = a(A) + X(T) * n(0) //2

>From 2, we can see that A<T> has to be aligned on a multiple of X(T), since

a(A) = a(t) - X(T)*n(0)

but a(t) = X(T) * n(t)

so a(A) = X(T) * n(t) - X(T) * n(0) = X(T) * ( n(t) - n(0) )

=> a(A) % X(T) = 0 //3

We can also say that

a(t) + sizeof(T) + spaceAfter(t) = a(next A in memory)

but since a must be aligned on a multiple of X(T),

so we get

a(t) + sizeof(T) + X(T)*n(1) = a(next A in memory) //4

Putting 2) and 4) together

a(A) + X(T) *n(0) + sizeof(T) + X(T)*n(1) = a(next A in memory)

But by definition of "next in memory" we also know that

a(next A in memory) = a(A) + sizeof(A)

So

a(A) + X(T) * n(0) + sizeof(T) + X(T) * n(1) = a(A) + sizeof(A)

Rewrite and simplify:

X(T) * (n(0) + n(1)) = sizeof(A) - sizeof(T) //5

Q.E.D.

So 5) above implies that sizeof(A<T>) - sizeof(T) is a always a safe
alignment for T (i.e. is a multiple of X(T) and
by construction sizeof(A<T>) > sizeof(T).
Also, note that n(0) is the multiplier of X(T) bytes in the struct before t
and n(1) is the number after.
It's easy to see that any decent compiler would make n(0) = 1 and n(1) = 0,
so that
sizeof(A<T>) - sizeof(T) = X(T), i.e. the exact alignment.

Tom

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

M Jared Finder

Nov 29, 2004, 5:43:43 AM11/29/04
to
Tom wrote:
> I recently finished reading Herb Sutter's Exceptional C++ style. In the
> book he mentions again the long standing problem of calculating alignment
> for a type T.
>
> In this post I will (hopefully) show how to calculate safe alignment for any
> type T.
>
> First a few definitions:
> I will refer to arbitrary addresses as a(n) (e.g. a(1), a(2)) and to
> addresses of specific data as a(<name>).
> (e.g. a(t) == &t)
>
> Unknown constants, n(<name>), where n(<name>) >= 0
>
> Alignment of T is X(T), s.t. a(t) % X(T) = 0, or X(T) * n(t) = a(t), for
> some n(t).
>
> Now to the solution:
>
> Consider the following struct:
>
> template<class T>
> struct A
> {
> char c;
> T t;
> };
>
> The "c" member is in the stuct to ensure that sizeof(A<T>) > sizeof(T).
>
> Now consider an array of A<T> in memory starting at address a(A).
> We can say that
>
> a(t) = a(A) + spaceBefore(c) + sizeof(char) + spaceAfter(c) //1

spaceBefore(c) = 0, because of struct layout requirements.

> but because A<T>::t needs to be aligned on a T boundary, we have
>

spaceAfter(c), respectively? If so, then how can you state that the
offset into the struct must be aligned to T, without previously stating
that the whole struct must be aligned to T? I'm not saying that a
struct could have alignment weaker than any one of its members (it
can't), but you should state that first.

When is it useful to know the alignment of a type T as a value less than
sizeof(T) and some platform specific maximum alignment? Surely I am
just overlooking something simple.

-- MJF

Nov 29, 2004, 5:56:03 AM11/29/04
to
Tom <NoS...@ThankYouVeryMuch.com> wrote in message news:<41a9e0de\$0\$1063\$db0f...@news.zen.co.uk>...
[snip]

> Now consider an array of A<T> in memory starting at address a(A).
> We can say that
>
> a(t) = a(A) + spaceBefore(c) + sizeof(char) + spaceAfter(c) //1
>
> but because A<T>::t needs to be aligned on a T boundary, we have
>

You silently assumed that A is aligned on a T boundary here.

> Rewrite 1 as
>
> a(t) = a(A) + X(T) * n(0) //2
>
> >From 2, we can see that A<T> has to be aligned on a multiple of X(T), since
>
> a(A) = a(t) - X(T)*n(0)
>
> but a(t) = X(T) * n(t)
>
> so a(A) = X(T) * n(t) - X(T) * n(0) = X(T) * ( n(t) - n(0) )
>
> => a(A) % X(T) = 0 //3

And here you have successfuly proved the assumption used.

I've seen a lot of pseudoproofs and using P to prove P is quite
common. It's really sad that the vast majority of people can't
distinguish a proof and a pseudoproof.

A correct proof that sizeof(A<T>) is a multiple of the alignment
of T is as follows:

Given the definitions
and
A<T> a[2];
for the type T,
and
Thus,
i.e. sizeof(A<T>) is a multiple of the alignment of T Q.E.D.

AFAICT a "decent compiler" is not covered by the standard and
X(T) == sizeof(A<T>)-sizeof(T)
really depends on it.

Regards,

David Abrahams

Nov 29, 2004, 4:48:07 PM11/29/04
to

> A correct proof that sizeof(A<T>) is a multiple of the alignment
> of T is as follows:
>
> Given the definitions
> and
> A<T> a[2];
> for the type T,

Actually nothing in the standard supports that assumption unless T is
POD. An implementation could build structs as arrays of pointers to
memory that's allocated elsewhere, for example. So addr(a[0]) and
addr(a[0].t) are allowed to have no relationship at all, and subtracting
them could lead to undefined behavior.

Too bad, IMO, because it's a portable assumption in practice and without
it, some very useful programs have undefined behavior.

> and
> Thus,
> i.e. sizeof(A<T>) is a multiple of the alignment of T Q.E.D.

Right.

But, stepping back a moment, what does this tell you? It's not very
interesting to have this information, because sizeof(T) is also a
multiple of the alignment of T. And it very well might be the same as
sizeof(A<T>). With that information you can't even reliably use GCD to
find what you're really interested in, which is probably the least
multiple of the alignment of T you can find.

Anyone interested in a _practical_ algorithm for finding alignment might
look at the implementation of boost::alignment_of in the type traits
library.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

Ben Hutchings

Nov 29, 2004, 4:44:51 PM11/29/04
to
<snip>
> A correct proof that sizeof(A<T>) is a multiple of the alignment
> of T is as follows:
>
> Given the definitions
> and
> A<T> a[2];
> for the type T,
> and
> Thus,
> i.e. sizeof(A<T>) is a multiple of the alignment of T Q.E.D.

Similarly, so is sizeof(T).

> AFAICT a "decent compiler" is not covered by the standard and
> X(T) == sizeof(A<T>)-sizeof(T)
> really depends on it.

<snip>

We do know that sizeof(A<T>) - sizeof(T) is a multiple of the
alignment (since both terms are multiples) and we know that it's
non-zero because members can't overlap. So it seems to be a safe
value to use for alignment, even though it could conceivably be
greater than the true value.

--
Ben Hutchings
Reality is just a crutch for people who can't handle science fiction.

Tom

Nov 30, 2004, 6:07:28 AM11/30/04
to
<snip correction>

Thanks for pointing that out.
The error was an oversight while I was trying to write things down into the
email.
As have shown yourself, it's still possible to show that X(A) = n * X(T).

> AFAICT a "decent compiler" is not covered by the standard and
> X(T) == sizeof(A<T>)-sizeof(T)
> really depends on it.

The final result is

X(T) * (n(0) + n(1)) = sizeof(A) - sizeof(T)

Which is still a safe alignment for X, and is as much as I claimed to
calculate.

There are some guarantees regarding n(0) for POD types, but not for user
defined types.

Now my definition of a "decent compiler" is one that doesn't add unnecessary

So for example if you assume 32 bit ints and a 1 byte char,

struct foo
{
char c;

int i;
};

On a "decent compiler" sizeof(foo) would be 8, with n(0) being 1 and n(1)
being 0.

Thanks for the feedback,

Tom

Tom

Nov 30, 2004, 6:06:37 AM11/30/04
to
<snip>

> spaceBefore(c) = 0, because of struct layout requirements.

No, this is only guaranteed by the standard for POD types.
T could be a non-POD, which would also make A<T> non-POD...

> > but because A<T>::t needs to be aligned on a T boundary, we have
> >
>
> spaceAfter(c), respectively?

Yes, sorry.
I tried to rename them from padAfter to spaceAfter, because in non-POD types
there may be more than padding in the class - e.g. the Vfn table pointer.

> If so, then how can you state that the
> offset into the struct must be aligned to T, without previously stating
> that the whole struct must be aligned to T? I'm not saying that a
> struct could have alignment weaker than any one of its members (it
> can't), but you should state that first.

Yes, I made a logical error in the argument, as pointed out by another
poster.
I shot myself in the foot while trying to write down the explanation of the
idea.
However, he proposed a way to fix it and hence the rest of the argument
still stands.

> When is it useful to know the alignment of a type T as a value less than
> sizeof(T) and some platform specific maximum alignment? Surely I am
> just overlooking something simple.

I was trying to show how to calculate this value portably.
Also, on all compilers I've tried the result of the calculation is the
actual alignment, because if
(which is what my definition of "decent compiler" was) the value is exact.

Tom

Tom

Nov 30, 2004, 6:06:16 AM11/30/04
to
> Anyone interested in a _practical_ algorithm for finding alignment might
> look at the implementation of boost::alignment_of in the type traits
> library.

I see that my initial post is very similar to the code in boost.
Damn. One day I will have an idea someone else hasn't already thought of,
but it's not going to be this one.

Tom

Terje SlettebĂ¸

Nov 30, 2004, 6:08:17 AM11/30/04
to
"Tom" <NoS...@ThankYouVeryMuch.com> wrote in message
news:41a9e0de\$0\$1063\$db0f...@news.zen.co.uk...
> I recently finished reading Herb Sutter's Exceptional C++ style. In the
> book he mentions again the long standing problem of calculating alignment
> for a type T.
>
> In this post I will (hopefully) show how to calculate safe alignment for
any
> type T.

<snip>

> So 5) above implies that sizeof(A<T>) - sizeof(T) is a always a safe
> alignment for T (i.e. is a multiple of X(T) and
> by construction sizeof(A<T>) > sizeof(T).
> Also, note that n(0) is the multiplier of X(T) bytes in the struct before
t
> and n(1) is the number after.
> It's easy to see that any decent compiler would make n(0) = 1 and n(1) =
0,
> so that
> sizeof(A<T>) - sizeof(T) = X(T), i.e. the exact alignment.
>

You might also look at boost::alignment_of, which uses the same technique,
i.e. guaranteeing to get a safe alignment (a value that is a multiple of the
exact alignment): http://www.boost.org/libs/type_traits/index.html.

Regards,

Terje

Dec 1, 2004, 7:49:43 PM12/1/04
to
David Abrahams <da...@boost-consulting.com> wrote in message news:<2_2dnf7Xav5...@rcn.net>...

> An implementation could build structs as arrays of pointers to
> memory that's allocated elsewhere, for example. So addr(a[0]) and
> addr(a[0].t) are allowed to have no relationship at all

I disagree:

9.2p12 says "Nonstatic data members ... have ... addresses within a
class object."

I would expect that to be verifiable with std::less<void*>.

> and subtracting
> them could lead to undefined behavior.

I agree with this for various reasons. For instance it seems that the
'offset' of nonstatic data elements in a non-pod is not required to be
a multiple of 1 char.

Dec 1, 2004, 8:02:11 PM12/1/04
to
David Abrahams <da...@boost-consulting.com> wrote in message news:<2_2dnf7Xav5...@rcn.net>...
[snip]

[snip]

>
> Actually nothing in the standard supports that assumption unless T is
> POD. An implementation could build structs as arrays of pointers to
> memory that's allocated elsewhere, for example. So addr(a[0]) and
> addr(a[0].t) are allowed to have no relationship at all, and subtracting
> them could lead to undefined behavior.
>
> Too bad, IMO, because it's a portable assumption in practice and without
> it, some very useful programs have undefined behavior.
[snip]

Well, it seems that my "proof" contains an "axiom" that is in fact
just an unproved statement. And a statement that I'm starting to
believe to be false.

IMHO the implementation you suggested is invalid. The constructor would
have to allocate the additional storage and such an allocation might
fail. Thus, it would be impossible for a non-POD constructor to be
non-throwing (and if this does not break something in the language it
breaks at least the stdlib, for example auto_ptr).

So, let's propose another malicious implementation. For each data member
the object will contain this member on a random position and its offset
(relative to "this") at a fixed position. The size of the object will
be sufficient for bases, offsets, members and necessary padding for any
permutation of the members. After constructing the bases the constructor
will create a random permutation of the new data members and calculate
and store their offsets before initializing these members. (Random
offsets of bases are impossible since it would break static_cast up and
down the hierarchy.) If we don't introduce a random padding,

will evidently have 50% chance to hold (&a[0].t points to the randomly
located member, not to the index).

If you can find anything that makes this implementation broken wrt the
standard let me know.

Regards,