23 views

Skip to first unread message

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.

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

padBefore(c) + sizeof(char) + padAfter(c) = X(T) * n(0)

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),

padAfter(t) = X(T) * n(1)

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.

Comments?

Tom

[ See http://www.gotw.ca/resources/clcm.htm for info about ]

[ comp.lang.c++.moderated. First time posters: Do this! ]

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

> 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

>

> padBefore(c) + sizeof(char) + padAfter(c) = X(T) * n(0)

Are padBefore(c) and padAfter(c) the same as spaceBefore(c) and

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

>

> padBefore(c) + sizeof(char) + padAfter(c) = X(T) * n(0)

[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

>

> padBefore(c) + sizeof(char) + padAfter(c) = X(T) * n(0)

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

addr(s) := reinterpret_cast<char*>(&s)

and

A<T> a[2];

we know that addr(a[0].t) and addr(a[1].t) are suitably aligned

for the type T,

addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

and

addr(a[1])-addr(a[0]) == sizeof(A<T>) .

Thus,

sizeof(A<T>) == addr(a[1].t)-addr(a[0].t) ,

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

your final result

X(T) == sizeof(A<T>)-sizeof(T)

really depends on it.

Regards,

Vladimir Marko

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

to

Vladimir Marko wrote:

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

> of T is as follows:

>

> Given the definitions

> addr(s) := reinterpret_cast<char*>(&s)

> and

> A<T> a[2];

> we know that addr(a[0].t) and addr(a[1].t) are suitably aligned

> for the type T,

> addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

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

> addr(a[1])-addr(a[0]) == sizeof(A<T>) .

> Thus,

> sizeof(A<T>) == addr(a[1].t)-addr(a[0].t) ,

> 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

Nov 29, 2004, 4:44:51 PM11/29/04

to

Vladimir Marko wrote:

<snip>

<snip>

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

> of T is as follows:

>

> Given the definitions

> addr(s) := reinterpret_cast<char*>(&s)

> and

> A<T> a[2];

> we know that addr(a[0].t) and addr(a[1].t) are suitably aligned

> for the type T,

> addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

> and

> addr(a[1])-addr(a[0]) == sizeof(A<T>) .

> Thus,

> sizeof(A<T>) == addr(a[1].t)-addr(a[0].t) ,

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

> of T is as follows:

>

> Given the definitions

> addr(s) := reinterpret_cast<char*>(&s)

> and

> A<T> a[2];

> we know that addr(a[0].t) and addr(a[1].t) are suitably aligned

> for the type T,

> addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

> and

> addr(a[1])-addr(a[0]) == sizeof(A<T>) .

> Thus,

> sizeof(A<T>) == addr(a[1].t)-addr(a[0].t) ,

> 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

> your final result

> 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.

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

> your final result

> 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

padding.

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

Nov 30, 2004, 6:06:37 AM11/30/04

to

<snip>

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

> 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

> >

> > padBefore(c) + sizeof(char) + padAfter(c) = X(T) * n(0)

>

> Are padBefore(c) and padAfter(c) the same as spaceBefore(c) and

> 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

the compiler doesn't do anything stupid, like adding unnecessary padding

(which is what my definition of "decent compiler" was) the value is exact.

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.

> 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

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...

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.

> 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.

>

> Comments?

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

> 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

[snip]

> > addr(s) := reinterpret_cast<char*>(&s)

[snip]

> > addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

>

> 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]

> > addr(s) := reinterpret_cast<char*>(&s)

> > addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

>

> 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.

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,

addr(a[0].t)-addr(a[0]) == addr(a[1].t)-addr(a[1])

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,

Vladimir Marko

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu