Alignment of foo[1][1][1][1]

[Shao Miller]

Suppose I have type 'foo' and:

sizeof (foo) == 16
alignof (foo) == 2

Suppose I have type 'foo[1][1][1][1]' and:

sizeof (foo[1][1][1][1]) == 16

Can:

alignof (foo[1][1][1][1]) == 4

? I'd like to think not, but is it prohibited? If I do:

typedef foo bar[1][1][1][1];
bar * my_bar = malloc(sizeof *bar);
foo * my_foo = (foo *) my_bar;

certainly 'my_bar' points to an object whose alignment satisfies type
'foo'. But what about the other way around?

typedef foo bar[1][1][1][1];
foo * my_foo = malloc(sizeof *foo);
bar * my_bar = (bar *) my_foo;

'my_foo' could point to an object aligned for '2', but if the alignment
requirement for 'bar' is '4', then the behaviour is undefined.

With a size of '16', array elements would always satisfy both alignment
requirements.

My guess is that no implementation does this, but again: How about
Standard-wise?

 

[Shao Miller]

Suppose I have type 'foo' and:

sizeof (foo) == 16
alignof (foo) == 2

Suppose I have type 'foo[1][1][1][1]' and:

sizeof (foo[1][1][1][1]) == 16

Can:

alignof (foo[1][1][1][1]) == 4

? I'd like to think not, but is it prohibited? If I do:

typedef foo bar[1][1][1][1];
bar * my_bar = malloc(sizeof *bar);
foo * my_foo = (foo *) my_bar;

certainly 'my_bar' points to an object whose alignment satisfies type
'foo'. But what about the other way around?

typedef foo bar[1][1][1][1];
foo * my_foo = malloc(sizeof *foo);
bar * my_bar = (bar *) my_foo;

'my_foo' could point to an object aligned for '2', but if the alignment
requirement for 'bar' is '4', then the behaviour is undefined.

With a size of '16', array elements would always satisfy both alignment
requirements.

My guess is that no implementation does this, but again: How about
Standard-wise?

Erm, pretend I didn't use 'malloc', there. That's besides the point.

 

[Harald van Dijk]

My guess is that no implementation does this,

Perhaps not for arrays of length 1, but it could be a sensible
decision to require the same alignment as an int for
char[sizeof(int)]. And on my system, the natural alignment for long
long is 8 bytes, but the compiler aligns them to 4 bytes mainly to
avoid changing the ABI. It could be a sensible future decision to keep
that alignment for long long, but align arrays of long long to 8
bytes, if the cost of the ABI change would be acceptably small for
arrays. (Not that I think that is going to happen, but still...)

but again: How about
Standard-wise?

I don't think the standard says anything about it, which in this case
means implementors are given the freedom to use whatever alignment
works best for them.

 

[lawrence.jones]

Suppose I have type 'foo' and:

sizeof (foo) == 16
alignof (foo) == 2

Suppose I have type 'foo[1][1][1][1]' and:

sizeof (foo[1][1][1][1]) == 16

Can:

alignof (foo[1][1][1][1]) == 4

? I'd like to think not, but is it prohibited?

I'm afraid it's hard to say. The problem is that there are at least two
potentially different kinds of alignment requirements, which I'll call
the *necessary* alignment and the *preferred* alignment. The necessary
alignment is the alignment required by the underlying hardware and the
implementation's code generation in order for things to work correctly.
The preferred alignment may be stricter and is what the implementation
actually uses, typically for performance reasons. For example, on a
typical linearly addressed machine that allows unaligned accesses, the
necessary alignment for all types is 1, but implementations almost
always use an alignment equal to the size for the fundamental data
types.

The C Standard requires that any object be usable as if it were an array
with a single element. Thus, the necessary alignment of an array cannot
be stricter than the necessary alignment of its element type. However,
there certainly are implementations that align arrays more strictly than
their element type for performance reasons, and I wouldn't be surprised
to find some that do the same for structure types (although I've never
encountered one).

The Standard says that _Alignof() returns the "required" alignment, but
it's not clear exactly what "required" means in this context. Is it the
necessary alignment, the preferred alignment, or maybe even something in
between?

 

[Harald van Dijk]

The C Standard requires that any object be usable as if it were an array
with a single element.  Thus, the necessary alignment of an array cannot
be stricter than the necessary alignment of its element type.

In n1256, the only relevant wording regarding treating arbitrary
objects as arrays that I can find is this:

"For the purposes of these operators, a pointer to an object that is
not an element of an
array behaves the same as a pointer to the first element of an array
of length one with the
type of the object as its element type." (for the + - < <= > >= ==
and != operators)

which does not suggest to me that objects behave as arrays of length 1
in other aspects. Am I overlooking something?

 

[Tim Rentsch]

Suppose I have type 'foo' and:

sizeof (foo) == 16
alignof (foo) == 2

Suppose I have type 'foo[1][1][1][1]' and:

sizeof (foo[1][1][1][1]) == 16

Can:

alignof (foo[1][1][1][1]) == 4

? I'd like to think not, but is it prohibited? [snip]

No, it's conforming. An array must be aligned at least as
strictly as its elements, but the converse doesn't hold,
even for arrays of length 1. The alignments for types (foo)
and (foo[1]) don't have to be the same, even though in any
sane implementation they will be.

 

[Tim Rentsch]

Suppose I have type 'foo' and:

sizeof (foo) == 16
alignof (foo) == 2

Suppose I have type 'foo[1][1][1][1]' and:

sizeof (foo[1][1][1][1]) == 16

Can:

alignof (foo[1][1][1][1]) == 4

? I'd like to think not, but is it prohibited?

I'm afraid it's hard to say. The problem is that there are at least two
potentially different kinds of alignment requirements, which I'll call
the *necessary* alignment and the *preferred* alignment. The necessary
alignment is the alignment required by the underlying hardware and the
implementation's code generation in order for things to work correctly.
The preferred alignment may be stricter and is what the implementation
actually uses, typically for performance reasons. For example, on a
typical linearly addressed machine that allows unaligned accesses, the
necessary alignment for all types is 1, but implementations almost
always use an alignment equal to the size for the fundamental data
types.

The C Standard requires that any object be usable as if it were an array
with a single element. Thus, the necessary alignment of an array cannot
be stricter than the necessary alignment of its element type.

You mean this the other way around - the alignment of an array
type must be at least as strict as the element type, and may
in fact be more strict. The requirement you mention is in
reference to element and array objects, not types; it doesn't
bear on the issue of alignment of array types, because the
pointers involved always point to an element of the array in
question, ie, they are of element type, not array type [*].

[*] With the understanding that the element type may itself be
a (different) array type, but that doesn't change the point.

However,
there certainly are implementations that align arrays more strictly than
their element type for performance reasons, and I wouldn't be surprised
to find some that do the same for structure types (although I've never
encountered one).

The Standard says that _Alignof() returns the "required" alignment, but
it's not clear exactly what "required" means in this context. Is it the
necessary alignment, the preferred alignment, or maybe even something in
between?

Surely the meaning of _Alignof() is meant to coincide with what
is necessary for conversion of a pointer to the type in question.
So for example,

char *stuff = malloc( _Alignof (T) + sizeof (T) );
... verify the malloc succeeded ...

T *displaced = (T*) (stuff + _Alignof (T));

must work on a conforming implementation. It's also possible
some lesser values would work, but _Alignof (T) must be
/guaranteed/ to work, since otherwise having _Alignof would be of
no value.

(I think it goes without saying that _Alignof also must be such
that the alignments of members if T is a struct or union type, or
elements if T is an array type, will each have their individual
requirements satisfied -- meaning they can be accessed normally
and their addresses will work when converted to their respective
types. The alignment of a struct type must take into account the
alignments of its members, etc.)

 

[lawrence.jones]

You mean this the other way around - the alignment of an array
type must be at least as strict as the element type, and may
in fact be more strict.

No, I meant exactly what I said. You're either missing the distinction
I was trying to draw between the necessary and preferred alignments or
you're conflating them.

The requirement you mention is in
reference to element and array objects, not types; it doesn't
bear on the issue of alignment of array types, because the
pointers involved always point to an element of the array in
question, ie, they are of element type, not array type [*].

But a pointer to an array must compare equal to a pointer to the first
element (when converted to a common type, of course), which isn't
possible in general unless the necessary alignments are the same. The
preferred alighments can differ as you said above.

 

[Shao Miller]

In n1256, the only relevant wording regarding treating arbitrary
objects as arrays that I can find is this:

"For the purposes of these operators, a pointer to an object that is
not an element of an
array behaves the same as a pointer to the first element of an array
of length one with the
type of the object as its element type." (for the + -< <=> >= ==
and != operators)

which does not suggest to me that objects behave as arrays of length 1
in other aspects. Am I overlooking something?

Do you mean such as the cast concern of the original post? That seems
like a slippery slope. :S

 

[Harald van Dijk]

Do you mean such as the cast concern of the original post?  That seems
like a slippery slope. :S

In what way? I don't see any downsides to disallowing

int i = 0;
++(*(int(*)[1])&i)[0];

If you need an array, do this:

int i[1] = { 0 };
++i[0];

If you don't need an array, do this:

int i = 0;
++i;

Do you have a real example where it would be useful for you to
reinterpret a non-array as an array (beyond what the standard already
permits)?

 

[Shao Miller]

You mean this the other way around - the alignment of an array
type must be at least as strict as the element type, and may
in fact be more strict.

No, I meant exactly what I said. You're either missing the distinction
I was trying to draw between the necessary and preferred alignments or
you're conflating them.

The requirement you mention is in
reference to element and array objects, not types; it doesn't
bear on the issue of alignment of array types, because the
pointers involved always point to an element of the array in
question, ie, they are of element type, not array type [*].

But a pointer to an array must compare equal to a pointer to the first
element (when converted to a common type, of course), which isn't
possible in general unless the necessary alignments are the same. The
preferred alighments can differ as you said above.

If I understand you correctly, "necessary alignment" is that which is
involved in the "correctly aligned" bit of pointer conversions and
"preferred alignment" would be where an implementation causes

int ia[100];

to happen to land.

Regardless of which of these '_Alignof' uses, if we have:

/* ...foo established... */
typedef foo a_1_1_foo[1][1];

char * cp = malloc(sizeof (a_1_1_foo) * 10);
/* Assume success */
cp += _Alignof (foo);

'cp' now theoretically points to an object which could have type 'foo'.
But how can we say whether it points to a 'foo', a 'foo[1]', a
'foo[1][1]', a 'foo[1][1][1]', etc.? The "points to an object that is
not an element of an array" doesn't really seem determinable.

/* Correctly aligned conversion? */
a_1_1_foo * test = (void *) cp;

Or is that "jumping too far?"

foo * step1 = (void *) cp;

Yes, 'step1' is correctly aligned.

foo (* step2)[1] = (void *) step1;

Yes, 'step1' didn't point to an element, so it is treated as though it
pointed to the sole element of an array. This urges that 'foo[1]' has
the same alignment requirement as 'foo'.

a_1_1_foo * step3 = (void *) step2;

Hmm... 'step2' doesn't point to an element of an array according to its
type, but it "came from" a pointer which points to an element of an
array object (perhaps)... It strikes me as being similar to a
containing 'struct' (or 'union') with a single member, where the
alignment requirement of the 'struct' is stricter than the member.

 

[Shao Miller]

Do you mean such as the cast concern of the original post? That seems
like a slippery slope. :S

In what way? I don't see any downsides to disallowing

int i = 0;
++(*(int(*)[1])&i)[0];

If you need an array, do this:

int i[1] = { 0 };
++i[0];

If you don't need an array, do this:

int i = 0;
++i;

Those examples cover "static" and "automatic" arrays. What about
"allocated" or even working within "allocated" space with manual
alignment accounting?

Do you have a real example where it would be useful for you to
reinterpret a non-array as an array (beyond what the standard already
permits)?

Actually yes, this thread was prompted by a suggestion I'd made to
someone else in another thread. They wanted an "opaque type" which
would be effectively compatible (non-Standardese) with the actual type.
That is, to pretend that one type was two different types:

void foo_func(foo * my_foo);
void bar_func(bar * my_bar);

I'd suggested the arbitrary:

typedef foo bar[1][1][1];

Now you cannot accidentally do:

foo * some_foo_ptr = ...;
bar_func(some_foo_ptr);

Even though internally, 'bar_func' might very well simply convert its
parameter to a 'foo *' type. That conversion was the original cause of
alignment concern, here.

An advantage to such an obfuscation, in my opinion, is that there can be
no padding concerns while copying or iterating through an array of such
types -- sizeof (bar) == sizeof (foo); contrast with 'struct's and
'union's (however unlikely).

 

[Harald van Dijk]

Actually yes, this thread was prompted by a suggestion I'd made to
someone else in another thread.  They wanted an "opaque type" which
would be effectively compatible (non-Standardese) with the actual type.
  That is, to pretend that one type was two different types:

   void foo_func(foo * my_foo);
   void bar_func(bar * my_bar);

I'd suggested the arbitrary:

   typedef foo bar[1][1][1];

Which will be problematic if any bar parameter is to be passed by
value as a function argument. But depending on the meaning of foo/bar,
this might not matter.

Now you cannot accidentally do:

   foo * some_foo_ptr = ...;
   bar_func(some_foo_ptr);

But the more common solution of a struct that you yourself mention:

typedef struct { int data; } foo;
typedef struct { int data; } bar;

works just as well.

Even though internally, 'bar_func' might very well simply convert its
parameter to a 'foo *' type.  That conversion was the original cause of
alignment concern, here.

Distinct unnamed structure types with identical definition are
effectively required to have the same size, representation and
alignment.

An advantage to such an obfuscation, in my opinion, is that there can be
no padding concerns while copying or iterating through an array of such
types -- sizeof (bar) == sizeof (foo); contrast with 'struct's and
'union's (however unlikely).

With the structure definitions above, sizeof(foo) == sizeof(bar). The
reasoning is simple: both are compatible with the same struct { int
data; } defined in a different translation unit.

 

[Shao Miller]

Actually yes, this thread was prompted by a suggestion I'd made to
someone else in another thread. They wanted an "opaque type" which
would be effectively compatible (non-Standardese) with the actual type.
That is, to pretend that one type was two different types:

void foo_func(foo * my_foo);
void bar_func(bar * my_bar);

I'd suggested the arbitrary:

typedef foo bar[1][1][1];

Which will be problematic if any bar parameter is to be passed by
value as a function argument. But depending on the meaning of foo/bar,
this might not matter.

Agreed. And you're right, the discussion partner was interested in
pointer parameters only.

But the more common solution of a struct that you yourself mention:

typedef struct { int data; } foo;
typedef struct { int data; } bar;

works just as well.

'foo' and 'bar' needn't be the same size as 'int'. Their post gave me
the impression that they already had interface functions for pointers to
the "inner type," so I sensed that it was "too late" for the strategy
you show above. So I'm assuming that there is already a library and the
request is towards adding a newer piece.

I don't recall if the original "inner type" was a scalar, aggregate or
union, but could try to find the thread again (it was near the original
post of this thread, likely).

Distinct unnamed structure types with identical definition are
effectively required to have the same size, representation and
alignment.

And the path to that conclusion (in the Standard) strikes me as being
rather round-about, if I recall that path correctly. Heheheh.

With the structure definitions above, sizeof(foo) == sizeof(bar). The
reasoning is simple: both are compatible with the same struct { int
data; } defined in a different translation unit.

Yeahbut what if it's too late and we want 'int' and 'foo' (following
your example) to be similar?

 

[Lauri Alanko]

'foo' and 'bar' needn't be the same size as 'int'. Their post gave me
the impression that they already had interface functions for pointers to
the "inner type," so I sensed that it was "too late" for the strategy
you show above. So I'm assuming that there is already a library and the
request is towards adding a newer piece.

No, the design of the library hasn't been fixed yet.

The problem with the above solution is not that it requires choosing a
particular representation, but that it requires _exposing_ that
representation in a public header. I'd like to avoid that as far as
possible, and that's why I like pointers to incomplete structs or,
failing that, struct wrappers for void pointers.


Lauri

 

[Harald van Dijk]

Actually yes, this thread was prompted by a suggestion I'd made to
someone else in another thread.  They wanted an "opaque type" which
would be effectively compatible (non-Standardese) with the actual type..
   That is, to pretend that one type was two different types:
    void foo_func(foo * my_foo);
    void bar_func(bar * my_bar);

[...]
   typedef struct { int data; } foo;
   typedef struct { int data; } bar;

[...]
I don't recall if the original "inner type" was a scalar, aggregate or
union, but could try to find the thread again (it was near the original
post of this thread, likely).

<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
6dc9ae4aad35bd89>

It was a struct. Not only that, but it is the simplest form of what
would be class inheritance in other languages. For that, my preference
would be

typedef struct IntDict {
Dict base;
} IntDict;

Since the conversion only needs to go one way (except for
intdict_new), the theoretical objection of Dict and IntDict having
different sizes, representations, and/or alignments does not apply.
And for the one exception, either dict_new can be made to return a
maximally aligned pointer, or intdict_new can be the single exception
that is not implemented as a wrapper method.

Yeahbut what if it's too late and we want 'int' and 'foo' (following
your example) to be similar?

Then my suggestions aren't guaranteed to work. Neither is foo[1][1][1]
[1].

 

[Tim Rentsch]

No, I meant exactly what I said. You're either missing the distinction
I was trying to draw between the necessary and preferred alignments or
you're conflating them.

I didn't either miss or misunderstand the distinction between
necessary and preferred alignment, nor was I conflating them.
The statement made - "the necessary alignment of an array cannot
be stricter than the necessary alignment of its element type" -
is wrong. The implication in the other direction holds but not
this direction. So, for example, an implementation which has
sizeof (int) == 4 could easily have the NA for 'int' be 1, but
the NA for 'int [1]' be 4 -- this might be done, eg, to
accommodate a special format for 'int (*)[]' pointers, or to
simplify the design of a vector processing unit that works with
arrays but not individual elements. It's easy to devise an
implementation along these lines, and have it be conforming.

Let's re-examine the first statement in the initial reasoning:

In fact the C Standard does not have such a requirement. What it
does have is a requirement that _pointers_ to non-array objects
behave just like pointers to _elements_ that are in an array
object, and this holds only for the purposes of several operators
(those being binary +/-, the relation operators, and the equality
operators). Importantly, an operation not covered under this
provision is conversion. We can take the address of an array, and
converting that address to a pointer to the array's element type
must succeed; that implies the NA of the array must be at least
as strict as the NA of its elements. However, if we take the
address of an ordinary scalar, there is no guarantee that the
pointer-to-scalar address can be converted into a pointer-to-array
type; the lack of guarantee for such conversions is what allows
arrays to be more strictly aligned than their elements.

The requirement you mention is in
reference to element and array objects, not types; it doesn't
bear on the issue of alignment of array types, because the
pointers involved always point to an element of the array in
question, ie, they are of element type, not array type [*].

But a pointer to an array must compare equal to a pointer to the first
element (when converted to a common type, of course), which isn't
possible in general unless the necessary alignments are the same.
[snip re: preferred alignments]

The relationship decribed here is correct only when dealing with
an actual array; an object that is not an element of an array
can't have its address converted to a pointer-to-array type
without potentially crossing over into undefined behavior.

Reasoning as outlined above, the necessary guarantees here are
always possible if the NA of an array is at least as restrictive
as the NA of the array's elements. They don't have to be equal.

 

[Shao Miller]

No, the design of the library hasn't been fixed yet.

D'oh! Of course "discussion partner" == Lauri Alanko. You always have
interesting things to discuss. Sorry about forgetting. I have to
start using the favourite attribute in this news-reader.

The problem with the above solution is not that it requires choosing a
particular representation, but that it requires _exposing_ that
representation in a public header. I'd like to avoid that as far as
possible, and that's why I like pointers to incomplete structs or,
failing that, struct wrappers for void pointers.

Ah, so the array obfuscation doesn't work either, then. You don't want
your API users to be able to use 'sizeof' on the base type, period.

Regardless of that, the array alignment business of this thread is still
a bit odd.

 

[Shao Miller]

Actually yes, this thread was prompted by a suggestion I'd made to
someone else in another thread. They wanted an "opaque type" which
would be effectively compatible (non-Standardese) with the actual type.
That is, to pretend that one type was two different types:

void foo_func(foo * my_foo);
void bar_func(bar * my_bar); [...]
typedef struct { int data; } foo;
typedef struct { int data; } bar;

[...]
I don't recall if the original "inner type" was a scalar, aggregate or
union, but could try to find the thread again (it was near the original
post of this thread, likely).

<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
6dc9ae4aad35bd89>

Oops, yes. That was it. Thanks.

It was a struct. Not only that, but it is the simplest form of what
would be class inheritance in other languages. For that, my preference
would be

typedef struct IntDict {
Dict base;
} IntDict;

Sure.

Since the conversion only needs to go one way (except for
intdict_new), the theoretical objection of Dict and IntDict having
different sizes, representations, and/or alignments does not apply.
And for the one exception, either dict_new can be made to return a
maximally aligned pointer, or intdict_new can be the single exception
that is not implemented as a wrapper method.

The originally specified functions do suggest that it'd be one way. I'd
quite forgotten that Lauri Alanko was intent on not exposing any
structure definitions.

Yeahbut what if it's too late and we want 'int' and 'foo' (following
your example) to be similar?

Then my suggestions aren't guaranteed to work. Neither is foo[1][1][1]
[1].

Agreed! It'd still be interesting if someone dug up some bits of
Standard which, when put together, lead to the conclusion that an
array's alignment requirements cannot be more strict than the base type.
I'm not sure we'll see that.

 

[Shao Miller]

I didn't either miss or misunderstand the distinction between
necessary and preferred alignment, nor was I conflating them.
The statement made - "the necessary alignment of an array cannot
be stricter than the necessary alignment of its element type" -
is wrong. The implication in the other direction holds but not
this direction. So, for example, an implementation which has
sizeof (int) == 4 could easily have the NA for 'int' be 1, but
the NA for 'int [1]' be 4 -- this might be done, eg, to
accommodate a special format for 'int (*)[]' pointers, or to
simplify the design of a vector processing unit that works with
arrays but not individual elements. It's easy to devise an
implementation along these lines, and have it be conforming.

[...]

In fact the C Standard does not have such a requirement. What it
does have is a requirement that _pointers_ to non-array objects
behave just like pointers to _elements_ that are in an array
object, and this holds only for the purposes of several operators
(those being binary +/-, the relation operators, and the equality
operators). Importantly, an operation not covered under this
provision is conversion. We can take the address of an array, and
converting that address to a pointer to the array's element type
must succeed; that implies the NA of the array must be at least
as strict as the NA of its elements. However, if we take the
address of an ordinary scalar, there is no guarantee that the
pointer-to-scalar address can be converted into a pointer-to-array
type; the lack of guarantee for such conversions is what allows
arrays to be more strictly aligned than their elements.

[...]

The relationship decribed here is correct only when dealing with
an actual array; an object that is not an element of an array
can't have its address converted to a pointer-to-array type
without potentially crossing over into undefined behavior.

Reasoning as outlined above, the necessary guarantees here are
always possible if the NA of an array is at least as restrictive
as the NA of the array's elements. They don't have to be equal.

I was pondering this, just now:

int i = 1;
int * ip = &i;
++ip;

So here 'ip' behaves as if it points into (where "into" includes "one
past") an array with one element. But indeed I agree, that doesn't mean
that it _is_ such an array. An example with "allocated" storage given
elsethread.

However, an unfortunate consequence of this "freedom" seems to be that
it is, in general, not safe to re-interpret arrays as having different
dimensions by using array types. One might expect that one could:

typedef int a_5_by_5[5][5];
a_5_by_5 array = {0};
typedef int a_flat_5_by_5[sizeof (a_5_by_5) / sizeof (int)];
a_flat_5_by_5 * flat_array_ptr = (void *) &array;

But that doesn't seem to be the case. :S Of course, using:

int * ip = array[0];

and iteration should be fine.