Padding involved

[Stephen Sprunk]

Standard C has no type "pair of doubles".

Actually, that's precisely what double[2] is;

That's an array of two doubles. He was using "pair of doubles" to mean
a type guaranteed to have 16-byte alignment, unlike an array of doubles.

and _Alignof(double[2]) probably would be 16 on such a platform.

Apparently not:

% cat foo.c
#include <stdio.h>
#define alignof(t) __alignof__(t)
struct twodouble { double x; double y; };
int main(void) {
printf("alignof(double) = %zu\n", alignof(double));
printf("alignof(double[2]) = %zu\n", alignof(double[2]));
printf("alignof(double complex) = %zu\n", alignof(double _Complex));
printf("alignof(struct twodouble) = %zu\n", alignof(struct twdouble));
}
% gcc -std=c99 -pedantic -W -Wall foo.c
% ./a.out
alignof(double) = 8
alignof(double[2]) = 8
alignof(double complex) = 8
alignof(struct twodouble) = 4
% gcc -v
Using built-in specs.
Target: i486-linux-gnu
....

The first three are what I expected, but the last one has me quite
confused; how can a struct have less strict alignment than its members?

While that's the only guarantee, an implementation is free to impose
stricter alignment requirements on arrays of a type than on the type
itself.

Of course, but without such a guarantee, how useful is that?

S

 

[Keith Thompson]

Standard C has no type "pair of doubles".

Actually, that's precisely what double[2] is; and _Alignof(double[2])
probably would be 16 on such a platform.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

So _Alignof(double[2]) == _Alignof(double), by definition.

[...]

While that's the only guarantee, an implementation is free to impose
stricter alignment requirements on arrays of a type than on the type itself.

It's not free to *require* a stricter alignment. Given:

double arr[3];

both arr[0] and arr[1] can be treated as the first element of a
double[2] object. (I'm *fairly* sure of that, but I don't have a
citation to prove it.)

Of course a compiler can allocate arrays at stricter alignments than
required, but it must still be able to (generate code to) access them at
the alignment of their element type.

 

[Keith Thompson]

With regard to the complex type that glen mentioned:

N1570 6.2.5p13:
"Each complex type has the same representation and alignment
requirements as an array type containing exactly two elements of the
corresponding real type;"

For structs, we know a struct's alignment has to be a positive multiple
of the largest member's alignment, and we also know it can't be larger
than the size of the struct, so the only possibilities here are 8 or 16.
I don't know why an implementation might choose the latter, but I can't
find anything in N1570 that says it isn't allowed to. So, correction noted.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

It might have made more sense for a complex type's alignment to be the
same as the alignment of a struct containing two members of the real
type -- but then that would in principle have permitted padding between
the members and/or after the second one (though no sane compiler is
likely to have such padding).

 

[James Kuyper]

On 28-Mar-14 16:19, glen herrmannsfeldt wrote:
On the platform you describe, must every double be aligned on a 16
byte address, so the SSE instructions can always be used?

Pairs of doubles are aligned on 16 byte boundaries.

Standard C has no type "pair of doubles".

Actually, that's precisely what double[2] is;

That's an array of two doubles. He was using "pair of doubles" to mean
a type guaranteed to have 16-byte alignment, unlike an array of doubles.

I thought he meant "pair of doubles" to refer to precisely that: two
doubles. What he was saying was that there was a significant advantage,
on such platforms, to aligning such pairs on 16-byte boundaries; not
that such alignment was a part of the definition of the phrase "pair of
doubles".

and _Alignof(double[2]) probably would be 16 on such a platform.

Apparently not:

Well, it is only something that is permitted; it isn't mandatory.
Perhaps the implementors didn't consider the increased speed of the
instructions he was talking about to be a sufficiently important issue.

% cat foo.c
#include <stdio.h>
#define alignof(t) __alignof__(t)
struct twodouble { double x; double y; };
int main(void) {
printf("alignof(double) = %zu\n", alignof(double));
printf("alignof(double[2]) = %zu\n", alignof(double[2]));
printf("alignof(double complex) = %zu\n", alignof(double _Complex));
printf("alignof(struct twodouble) = %zu\n", alignof(struct twdouble));
}
% gcc -std=c99 -pedantic -W -Wall foo.c
% ./a.out
alignof(double) = 8
alignof(double[2]) = 8
alignof(double complex) = 8
alignof(struct twodouble) = 4
% gcc -v
Using built-in specs.
Target: i486-linux-gnu
...

The first three are what I expected, but the last one has me quite
confused; how can a struct have less strict alignment than its members?

It seems to me that this cannot be correct. It is permitted for a struct
to have stricter alignment than it's member's types, but not for it to
be less strict.

Of course, but without such a guarantee, how useful is that?

It allows the compiler to align arrays of doubles that have an even
length more strictly than individual double objects, therefore
increasing the opportunities to make the code more efficient by taking
advantage of the special instructions that can only be used on suitably
aligned pairs of doubles. That strikes me as useful.

 

[James Kuyper]

Actually, that's precisely what double[2] is; and _Alignof(double[2])
probably would be 16 on such a platform.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

Ah - that's new, I think - I haven't had time to fully digest the
changes made in C2011. In principle the same requirement could have been
worded in earlier versions of the standard in terms of the alignment of
the type without mentioning _Alignof(), but I don't think that it was.
Am I correct?

 

[Eric Sosman]

[...]
% cat foo.c
#include <stdio.h>
#define alignof(t) __alignof__(t)
struct twodouble { double x; double y; };

^

int main(void) {
printf("alignof(double) = %zu\n", alignof(double));
printf("alignof(double[2]) = %zu\n", alignof(double[2]));
printf("alignof(double complex) = %zu\n", alignof(double _Complex));
printf("alignof(struct twodouble) = %zu\n", alignof(struct twdouble));

^ ?

 

[James Kuyper]

Or give up C and move onto other languages?

That seems like an over-reaction. Actual C compilers are far less
user-unfriendly than the C standard allows them to be. Also, C2011 added
_Alignas(), which would seem to address the issue you're raising.

 

[Stephen Sprunk]

On 03/28/2014 06:07 PM, Stephen Sprunk wrote:
On 28-Mar-14 16:19, glen herrmannsfeldt wrote:
Pairs of doubles are aligned on 16 byte boundaries.

Standard C has no type "pair of doubles".

Actually, that's precisely what double[2] is;

That's an array of two doubles. He was using "pair of doubles" to
mean a type guaranteed to have 16-byte alignment, unlike an array
of doubles.

I thought he meant "pair of doubles" to refer to precisely that: two
doubles. What he was saying was that there was a significant
advantage, on such platforms, to aligning such pairs on 16-byte
boundaries; not that such alignment was a part of the definition of
the phrase "pair of doubles".

We know that _Alignof(double) == 8 on the platform in question, so if he
is using "pair of doubles" to refer to something with an alignment of
16, he cannot have meant simply two doubles or an array of two doubles,
so I took my best guess at what he meant: some new type that has a size
of 16+.

and _Alignof(double[2]) probably would be 16 on such a platform.

Apparently not:

Well, it is only something that is permitted; it isn't mandatory.

It's not even permitted. As Keith cited, according to N1570 6.5.3.4p3,
_Alignof(double[2]) == _Alignof(double).

Perhaps the implementors didn't consider the increased speed of the
instructions he was talking about to be a sufficiently important
issue.

There's nothing stopping the implementation from _delivering_ stricter
alignment than promised in order to make use of such instructions, but
there doesn't seem to be any way for it to promise to do so.

% ./a.out
alignof(double) = 8
alignof(double[2]) = 8
alignof(double complex) = 8
alignof(struct twodouble) = 4
% gcc -v
Using built-in specs.
Target: i486-linux-gnu
...

The first three are what I expected, but the last one has me quite
confused; how can a struct have less strict alignment than its
members?

It seems to me that this cannot be correct. It is permitted for a
struct to have stricter alignment than it's member's types, but not
for it to be less strict.

So, compiler bug?

It seems obvious that, for array indexing to work, a struct's alignment
must be at least as strict as any of its members, but I can't find the
specific text in N1570 that says so.

S

 

[Stephen Sprunk]

Standard C doesn't care about speed at all, but users often do.

Note that x86, back to the 8086, doesn't require alignment, but it is
often faster if properly aligned. When the 80486 was popular, and
four byte alignment of double was all that was needed. (A 32 bit
system, with a 32 bit data bus.) C compilers, and more important
most of the time, malloc() would generate four byte alignment.

For way too long after the pentium became popular, C was still
generating four byte alignment.

Changing the alignment could break binary compatibility, which is a
bigger issue on some platforms than others.

My GCC targets "i486", and it offers 8-byte alignment for double. There
is little harm in requiring 8-byte alignment when its output runs on a
486, but there is significant benefit when it runs on a Pentium or later.

Note as above, x86 doesn't require 8 byte alignment for doubles, so C
might as well not do any padding, and malloc() might just as well
return odd addresses.

True, but we know that unaligned accesses have a performance penalty, so
implementations _should_ align when possible as a QoI matter. And C has
to work on systems that don't support unaligned access at all.

Or give up C and move onto other languages?

*shrug* That's obviously OT here.

But if you can't reliably generate them, that doesn't help much.

An implementation _can_ fairly reliably generate them as a QoI matter,
even if it isn't required to do so. But since it's not required, it
still has to be able to handle the unaligned case, which isn't
completely avoidable.

And if it doesn't?

If it doesn't contain only doubles? Then we'd need to know what type
the other members are and what their alignment is to be able to
determine the alignment for the whole structure.

S

 

[Eric Sosman]

[...]
It seems to me that this cannot be correct. It is permitted for a
struct to have stricter alignment than it's member's types, but not
for it to be less strict.

So, compiler bug?

No, typo. Go upthread and look carefully at the code.

 

[glen herrmannsfeldt]

(snip, someone wrote)

% ./a.out
alignof(double) = 8
alignof(double[2]) = 8
alignof(double complex) = 8
alignof(struct twodouble) = 4
% gcc -v
Using built-in specs.
Target: i486-linux-gnu
The first three are what I expected, but the last one has me quite
confused; how can a struct have less strict alignment than its
members?

It seems to me that this cannot be correct. It is permitted for a
struct to have stricter alignment than it's member's types, but not
for it to be less strict.

So, compiler bug?

It seems obvious that, for array indexing to work, a struct's alignment
must be at least as strict as any of its members, but I can't find the
specific text in N1570 that says so.

Since x86 (I presume that is what this is) doesn't require any
alignment, it isn't so obvious that it is wrong. It does seem
unusual, though.

-- glen

 

[Keith Thompson]

Actually, that's precisely what double[2] is; and _Alignof(double[2])
probably would be 16 on such a platform.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

Ah - that's new, I think - I haven't had time to fully digest the
changes made in C2011. In principle the same requirement could have been
worded in earlier versions of the standard in terms of the alignment of
the type without mentioning _Alignof(), but I don't think that it was.
Am I correct?

Search for every occurrence of "alignment" in N1256, I see no explicit
statement about the alignment of array types (which is a bit
surprising).

But I think the *required* alignment for an array type was already the
same as the required alignment for the element type.

For example, I *think* this program, which treats "slices" of a
double[3] array as double[2] arrays, is strictly conforming in
both C99 and C11. If double[2] could have a stricter alignment
requirement than double, its behavior would be undefined under any
implementation that imposes such an alignment.

#include <stdio.h>

typedef double pair[2];

static void print(pair *p) {
printf("%g %g\n", (*p)[0], (*p)[1]);
}

int main(void) {
double arr[3] = { 10.0, 20.0, 30.0 };
pair *p0 = (pair*)&arr[0];
pair *p1 = (pair*)&arr[1];
print(p0);
print(p1);
}

 

[Tim Rentsch]

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

It might have made more sense for a complex type's alignment to be the
same as the alignment of a struct containing two members of the real
type -- but then that would in principle have permitted padding between
the members and/or after the second one (though no sane compiler is
likely to have such padding).

Just to be an asshole.. oh sorry, to play devil's advocate..
consider a 64-bit processor with cache lines of 4 64-bit
units, which is to say 4x8 = 32 bytes. On such a machine,
it might make sense to have structs aligned on 32-byte
boundaries, for performance reasons. Under these conditions
an implementation would be obliged to provide trailing
padding, so all structs would be a multiple of 32 bytes
in length. Not very likely perhaps, but not insane
either.

 

[Tim Rentsch]

Actually, that's precisely what double[2] is; and _Alignof(double[2])
probably would be 16 on such a platform.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

Ah - that's new, I think - I haven't had time to fully digest the
changes made in C2011. In principle the same requirement could
have been worded in earlier versions of the standard in terms of
the alignment of the type without mentioning _Alignof(), but I
don't think that it was. Am I correct?

Strictly speaking, no, but a more interesting question is since
_Alignof was mentioned specifically why not look it up in a more
up-to-date version of the Standard before responding, especially
knowing that one's knowledge of the 2011 standard (where _Alignof
is defined) is not really up to par yet?

 

[glen herrmannsfeldt]

(snip, someone wrote)

(snip)

Just to be an asshole.. oh sorry, to play devil's advocate..
consider a 64-bit processor with cache lines of 4 64-bit
units, which is to say 4x8 = 32 bytes. On such a machine,
it might make sense to have structs aligned on 32-byte
boundaries, for performance reasons. Under these conditions
an implementation would be obliged to provide trailing
padding, so all structs would be a multiple of 32 bytes
in length. Not very likely perhaps, but not insane
either.

Well, there are systems that require alignment (or copying
somewhere else and copying the result back) and ones where it
is just somewhat faster.

-- glen

 

[Tim Rentsch]

Actually, that's precisely what double[2] is; and
_Alignof(double[2]) probably would be 16 on such a platform.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

Ah - that's new, I think - I haven't had time to fully digest the
changes made in C2011. In principle the same requirement could have
been worded in earlier versions of the standard in terms of the
alignment of the type without mentioning _Alignof(), but I don't
think that it was. Am I correct?

Search for every occurrence of "alignment" in N1256, I see no
explicit statement about the alignment of array types (which is a
bit surprising).

But I think the *required* alignment for an array type was already
the same as the required alignment for the element type.

For example, I *think* this program, which treats "slices" of a
double[3] array as double[2] arrays, is strictly conforming in
both C99 and C11. If double[2] could have a stricter alignment
requirement than double, its behavior would be undefined under any
implementation that imposes such an alignment.

#include <stdio.h>

typedef double pair[2];

static void print(pair *p) {
printf("%g %g\n", (*p)[0], (*p)[1]);
}

int main(void) {
double arr[3] = { 10.0, 20.0, 30.0 };
pair *p0 = (pair*)&arr[0];
pair *p1 = (pair*)&arr[1];
print(p0);
print(p1);
}

If you mean the example program as part of an argument, it's
a circular argument. The program is strictly conforming if
and only if the alignment of double[2] must be the same as
the alignment of double. Saying the given program is strictly
conforming is just a sneaky way of begging the question.

I partly agree with your comment re alignment in C99/N1256, in the
sense that apparently there is an /expectation/ that alignment of
arrays must match the alignment of their elements. However, I
don't find any statement, or combination of statements, in
C99/N1256 that either requires or logically implies that such a
limitation must hold. This omission means some code that looks
reasonable might have undefined behavior. Consider for example
the following code fragment, accepted under C99 (and also C90):

int a23[2][3];
int a32[3][2];
int (*a)[];
int (*b)[2] = a32;
int (*c)[3] = a23;
a = a23;
b = a;
a = a32;
c = a;

Does this code have undefined behavior or not? In particular, are
the assignments to b and c okay, which wouldn't be allowed without
using 'a' as an intermediary? AFAICS the Standard doesn't require
the alignments of the types (int[2]) and (int[3]) to be the same.
(To simplify the discussion let's assume the alignment of (int[])
is the same as that of (int) - this doesn't change the question in
any significant way.) If indeed it is the case that the Standard
does not either require or logically imply that the alignments of
these two types must be the same, then an implementation is free
to make them different, which means the program has undefined
behavior. Furthermore such a possibility isn't that farfetched.
If we add a few lines

b[2][1] = 0;
c[1][2] = 0;

we still have acceptable standard C code (ie, does not require a
diagnostic), yet it certainly crosses into undefined behavior.
If we take the Standard at its word, then the alignments of the
types involved here are not constrained to have the same value,
and when they are different the semantics of pointer conversion
explicitly deems such conversions undefined behavior.

Let me say again that I think the Standard was written with the
expectation, and also is read by most people as meaning to imply,
that the alignment of array types will be the same as that of
their elements. However I don't find any text, either normative
or informative, in the Standard itself (ie, pre-C11) that supports
this supposition.

 

[James Kuyper]

On 03/29/2014 02:02 PM, Stephen Sprunk wrote:
....

It's not even permitted. As Keith cited, according to N1570 6.5.3.4p3,
_Alignof(double[2]) == _Alignof(double).

I've acknowledged that I missed that clause. The restriction it imposes
is new in C2011, even thought it could have been expressed in different
terms in previous versions of the standard.

There's nothing stopping the implementation from _delivering_ stricter
alignment than promised in order to make use of such instructions, but
there doesn't seem to be any way for it to promise to do so.

Alignment requirements are implementation-defined, which means that a
conforming implementation of C must come with documentation that
describes them. Prior to C2011, that documentation could have specified
that double[N] will have 16 byte alignment whenever N is even. Keith
postulates to the contrary, but I don't think it can easily be proven.

% ./a.out
alignof(double) = 8
alignof(double[2]) = 8
alignof(double complex) = 8
alignof(struct twodouble) = 4
% gcc -v
Using built-in specs.
Target: i486-linux-gnu
...

The first three are what I expected, but the last one has me quite
confused; how can a struct have less strict alignment than its
members?

It seems to me that this cannot be correct. It is permitted for a
struct to have stricter alignment than it's member's types, but not
for it to be less strict.

So, compiler bug?

It's been pointed out that the code provided says alignof(struct
twdouble). Since no struct with that name has been defined, it's an
incomplete type. I'm not sure what the specification of GNU C's
__alignof__() is, but I'm surprised that giving it an incomplete type
didn't result in an error message. I doubt that there's anything that
can be usefully guaranteed about it's result.

It seems obvious that, for array indexing to work, a struct's alignment
must be at least as strict as any of its members, but I can't find the
specific text in N1570 that says so.

There is no text that says so directly. It's something that can be
derived from what the standard says about arrays, the offsetof() macro
(which implies that the offset is a constant depending only upon the
struct definition, rather than being dependent upon which instance of
the struct is being referred to), and alignment requirements.

 

[Stephen Sprunk]

[...]
% cat foo.c
#include <stdio.h>
#define alignof(t) __alignof__(t)
struct twodouble { double x; double y; };

^

int main(void) {
printf("alignof(double) = %zu\n", alignof(double));
printf("alignof(double[2]) = %zu\n", alignof(double[2]));
printf("alignof(double complex) = %zu\n", alignof(double _Complex));
printf("alignof(struct twodouble) = %zu\n", alignof(struct
twdouble));

^ ?

They matched in what I compiled/ran; I changed the struct's name before
posting for clarity but made a typo.

S

 

[Eric Sosman]

On 03/29/2014 01:46 AM, Stephen Sprunk wrote:
[...]
% cat foo.c
#include <stdio.h>
#define alignof(t) __alignof__(t)
struct twodouble { double x; double y; }; ^

int main(void) {
printf("alignof(double) = %zu\n", alignof(double));
printf("alignof(double[2]) = %zu\n", alignof(double[2]));
printf("alignof(double complex) = %zu\n", alignof(double _Complex));
printf("alignof(struct twodouble) = %zu\n", alignof(struct
twdouble));

^ ?

They matched in what I compiled/ran; I changed the struct's name before
posting for clarity but made a typo.

Would it be too much trouble to ask to see the exact source
you actually compiled and run? The source as posted has at least
two problems: The twodouble/twdouble mismatch, and the use of
__alignof__ (compiler-specific magic? another typo? or what?).

 

[Keith Thompson]

On 03/29/2014 03:57 AM, Keith Thompson wrote:
...
Actually, that's precisely what double[2] is; and
_Alignof(double[2]) probably would be 16 on such a platform.

N1570 6.5.3.4p3:

The _Alignof operator yields the alignment requirement of its
operand type. The operand is not evaluated and the result is
an integer constant. When applied to an array type, the result
is the alignment requirement of the element type.

Ah - that's new, I think - I haven't had time to fully digest the
changes made in C2011. In principle the same requirement could have
been worded in earlier versions of the standard in terms of the
alignment of the type without mentioning _Alignof(), but I don't
think that it was. Am I correct?

Search for every occurrence of "alignment" in N1256, I see no
explicit statement about the alignment of array types (which is a
bit surprising).

But I think the *required* alignment for an array type was already
the same as the required alignment for the element type.

For example, I *think* this program, which treats "slices" of a
double[3] array as double[2] arrays, is strictly conforming in
both C99 and C11. If double[2] could have a stricter alignment
requirement than double, its behavior would be undefined under any
implementation that imposes such an alignment.

#include <stdio.h>

typedef double pair[2];

static void print(pair *p) {
printf("%g %g\n", (*p)[0], (*p)[1]);
}

int main(void) {
double arr[3] = { 10.0, 20.0, 30.0 };
pair *p0 = (pair*)&arr[0];
pair *p1 = (pair*)&arr[1];
print(p0);
print(p1);
}

If you mean the example program as part of an argument, it's
a circular argument. The program is strictly conforming if
and only if the alignment of double[2] must be the same as
the alignment of double. Saying the given program is strictly
conforming is just a sneaky way of begging the question.

It wasn't *quite* meant as an argument, more as a way to restate
the question in a perhaps clearer manner.

I *think* that C99 permits the kinds of access in this program (and
I'd be very surprised to see an implementation where it doesn't work)
but I haven't found wording that proves or disproves it.

[...]