alignment/zero length arrays

[Bill Pursell]

I have a program that does most of its work traversing
a bunch of lists. The lists contain a void *, and I spent
some time today replacing the void *'s with a copy
of the data at the end of the structure as a zero length
array. The performance improvement that resulted by
avoiding the need to dereference the ptr was substantial,
but it has left me with an uncertain feeling. In particular,
changing an assignment caused the output to change,
and I'm not happy about it. The change that I think
should not have any affect is:

struct foo *f;
f = (struct foo *)&list_element->zdata;

becomes

struct foo f;
f = *(struct foo *)&list_element->zdata;

This is better described with the full program below.
My question is: 1) Are the final 3 assignments in this program
reliable?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct foo {
int x,y,z;
};
struct list_el {
void *data;
/* other stuff that throws off alignment */
/* gnu extension...*/
char zdata[] __attribute__((aligned(8)));
};

extern void * xmalloc(size_t s);

int
main(void)
{
struct list_el *L;
struct foo orig = {0,1,2};
struct foo *copy_ptr;
struct foo copy;

L = xmalloc(sizeof *L + sizeof orig);
L->data = &orig;
memcpy(&L->zdata, &orig, sizeof orig);

copy_ptr = (struct foo *)L->data;

copy_ptr = (struct foo *)&L->zdata;

copy = *(struct foo*)&L->zdata;

return EXIT_SUCCESS;
}

[Barry Schwarz]

On 25 Aug 2006 11:28:07 -0700, "Bill Pursell" <bi**********@gmail.com>
wrote:

>I have a program that does most of its work traversing
a bunch of lists. The lists contain a void *, and I spent
some time today replacing the void *'s with a copy
of the data at the end of the structure as a zero length
array. The performance improvement that resulted by
avoiding the need to dereference the ptr was substantial,
but it has left me with an uncertain feeling. In particular,
changing an assignment caused the output to change,
and I'm not happy about it. The change that I think
should not have any affect is:

We would have to see your real code to discuss this. For example, do
you reuse the struct?

>
struct foo *f;
f = (struct foo *)&list_element->zdata;

This sets pointer f to point to the data in your element.

>
becomes

struct foo f;
f = *(struct foo *)&list_element->zdata;

This copies the data from your element to the structure f.

>
This is better described with the full program below.
My question is: 1) Are the final 3 assignments in this program
reliable?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct foo {
int x,y,z;
};
struct list_el {
void *data;
/* other stuff that throws off alignment */
/* gnu extension...*/
char zdata[] __attribute__((aligned(8)));

The first part of this is a syntax error. (You could achieve the
intended result with [1].) The second part is non-standard. It also
begs the question how do you know 8 is the proper alignment.

>};

extern void * xmalloc(size_t s);

int
main(void)
{
struct list_el *L;
struct foo orig = {0,1,2};
struct foo *copy_ptr;
struct foo copy;

L = xmalloc(sizeof *L + sizeof orig);

You don't provide xmalloc but I will assume it does the obvious.

L->data = &orig;
memcpy(&L->zdata, &orig, sizeof orig);

copy_ptr = (struct foo *)L->data;

The cast is superfluous. data is a void* which can be implicitly
converted to any other object pointer type.

In answer to your question, data contains the address of a struct foo.
copy_ptr is a pointer to struct foo. It is reliable to assign such an
address to such a pointer. The conversion to void* (three statements
prior) and from void* (here) are well defined.

>
copy_ptr = (struct foo *)&L->zdata;

This is "reliable" only if zdata is properly aligned to a struct foo.

>
copy = *(struct foo*)&L->zdata;

This also is "reliable" only if zdata is properly aligned.

>
return EXIT_SUCCESS;
}

Remove del for email

[Bill Pursell]

Barry Schwarz wrote:

On 25 Aug 2006 11:28:07 -0700, "Bill Pursell" <bi**********@gmail.com>
wrote:

I have a program that does most of its work traversing
a bunch of lists. The lists contain a void *, and I spent
some time today replacing the void *'s with a copy
of the data at the end of the structure as a zero length
array. The performance improvement that resulted by
avoiding the need to dereference the ptr was substantial,
but it has left me with an uncertain feeling. In particular,
changing an assignment caused the output to change,
and I'm not happy about it. The change that I think
should not have any affect is:

We would have to see your real code to discuss this. For example, do
you reuse the struct?

struct foo *f;
f = (struct foo *)&list_element->zdata;

This sets pointer f to point to the data in your element.

becomes

struct foo f;
f = *(struct foo *)&list_element->zdata;

This copies the data from your element to the structure f.

This is better described with the full program below.
My question is: 1) Are the final 3 assignments in this program
reliable?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct foo {
int x,y,z;
};
struct list_el {
void *data;
/* other stuff that throws off alignment */
/* gnu extension...*/
char zdata[] __attribute__((aligned(8)));

The first part of this is a syntax error. (You could achieve the
intended result with [1].) The second part is non-standard. It also
begs the question how do you know 8 is the proper alignment.

What's the syntax error? Is [] a gnu extension, and I should instead
use [0]? gcc happily compiled with -Wall -pedantic -std=c99
Does zdata need to
have size 1? I'd rather avoid giving it any space, since I'm using
the data structure somewhat flexibly. ie, the structure is
defined with:

#define declare_list_of_(x) struct list_el_##x {\
x data;\
/* more stuff */\
char zdata [];\
}

typedef void *vp
declare_list_of(int);
declare_list_of(vp);
etc...

The list of int won't use the zdata field, so there's no
point allocating space for it.

(Note, the "more stuff" includes function pointers
for manipulating the lists, so they contain more references
to x in the argument lists. I'm not really sure I like this
set up, as I can see it quickly becoming unweildy.)

<snip>

>

L->data = &orig;
memcpy(&L->zdata, &orig, sizeof orig);

copy_ptr = (struct foo *)L->data;

The cast is superfluous. data is a void* which can be implicitly
converted to any other object pointer type.

Yeah, I was just trying to make all the assignments symmetric
to try to clarify what I'm having a problem with.

>
In answer to your question, data contains the address of a struct foo.
copy_ptr is a pointer to struct foo. It is reliable to assign such an
address to such a pointer. The conversion to void* (three statements
prior) and from void* (here) are well defined.

copy_ptr = (struct foo *)&L->zdata;

This is "reliable" only if zdata is properly aligned to a struct foo.

So the alignment issue is really the heart of the quesion. You
asked above how I know that 8 is the correct alignment, and
the answer is that I don't. Currently, I'm providing an API
that allows a function to do:
array_of_int *a;
array_of_float *b;
array_of_vp *c;
struct foo f = {1,2,3};

a = abc_create_array( /* some args */, INT).i;
b = abc_create_array( /* some args */, FLOAT).f;
c = abc_create_array( /* some args */, VOID_PTR).vp;
a->insert(a, 5);
b->insert(b,5.0);
c->insert(c, &f);

Where abc_create_array returns a
union {
array_of_int *i;
array_of_float *f;
array_of_vp *vp;
};
I'd like to modify the API to do:
d = abc_create_array( /* some args */, VAR, sizeof f).vp;
d->insert(d, &f)

Where the assignment to d copies the data into the
array rather than merely adding the pointer. So I don't
know the alignment, but in the particular instance I'm
doing, the data I'm inserting is 4 floats. I'll try
setting the alignment to 16, but I don't think it should
matter, since the current setup has sizeof( struct list_el) == 32.
(ie, the zero length array is already aligned on a 32 byte
boundary)

Can the structure be aligned portably? I only know how
to do it except by relying on gcc's aligned attribute.

--
Bill Pursell

[Michael Mair]

Bill Pursell schrieb:

Barry Schwarz wrote:

>>On 25 Aug 2006 11:28:07 -0700, "Bill Pursell" <bi**********@gmail.com>
wrote:

>>>I have a program that does most of its work traversing
a bunch of lists. The lists contain a void *, and I spent
some time today replacing the void *'s with a copy
of the data at the end of the structure as a zero length
array. The performance improvement that resulted by
avoiding the need to dereference the ptr was substantial,
but it has left me with an uncertain feeling. In particular,
changing an assignment caused the output to change,
and I'm not happy about it. The change that I think
should not have any affect is:

We would have to see your real code to discuss this. For example, do
you reuse the struct?

>>>struct foo *f;
f = (struct foo *)&list_element->zdata;

This sets pointer f to point to the data in your element.

>>>becomes

struct foo f;
f = *(struct foo *)&list_element->zdata;

This copies the data from your element to the structure f.

>>>This is better described with the full program below.
My question is: 1) Are the final 3 assignments in this program
reliable?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct foo {
int x,y,z;
};

struct list_el {
void *data;
/* other stuff that throws off alignment */
/* gnu extension...*/
char zdata[] __attribute__((aligned(8)));

The first part of this is a syntax error. (You could achieve the
intended result with [1].) The second part is non-standard. It also
begs the question how do you know 8 is the proper alignment.

What's the syntax error? Is [] a gnu extension, and I should instead
use [0]? gcc happily compiled with -Wall -pedantic -std=c99

No, this is perfectly standard C99, c.f. 6.7.2.1.
Note that -- if we assume for one moment that the __attribute__....
is not present -- gcc got the following wrong in the past:
sizeof(struct list_el) == offsetof(struct list_el, zdata)
&&
sizeof(struct list_el) == offsetof(struct list_el_2, zdata)
where
struct list_el_2 {
void *data;
/* other stuff that throws off alignment */
/* gnu extension...*/
char zdata[1];
};
I have no current gcc on my machine but in past C99 status
documents, there was a link to some thread where the gcc
people debated the wisdom of these semantics and seemed ready
to decide to ignore the standard.

Does zdata need to
have size 1? I'd rather avoid giving it any space, since I'm using
the data structure somewhat flexibly. ie, the structure is
defined with:

#define declare_list_of_(x) struct list_el_##x {\
x data;\
/* more stuff */\
char zdata [];\
}

Note: If you want to use zdata for something which has nothing
to do with strings, then make that "unsigned char zdata[];".
char is for characters, unsigned char for everything where you
want one byte in its full representation.

typedef void *vp
declare_list_of(int);
declare_list_of(vp);
etc...

The list of int won't use the zdata field, so there's no
point allocating space for it.

(Note, the "more stuff" includes function pointers
for manipulating the lists, so they contain more references
to x in the argument lists. I'm not really sure I like this
set up, as I can see it quickly becoming unweildy.)

I think this is a question of its own.

>
<snip>

>> L->data = &orig;
memcpy(&L->zdata, &orig, sizeof orig);

copy_ptr = (struct foo *)L->data;

The cast is superfluous. data is a void* which can be implicitly
converted to any other object pointer type.

Yeah, I was just trying to make all the assignments symmetric
to try to clarify what I'm having a problem with.

I did not understand what you want in your OP and still do not
know where your exact problem lies. All the unnecessary casts
contributed to the impression "maybe he does not know what he
wants".

>>In answer to your question, data contains the address of a struct foo.
copy_ptr is a pointer to struct foo. It is reliable to assign such an
address to such a pointer. The conversion to void* (three statements
prior) and from void* (here) are well defined.

>> copy_ptr = (struct foo *)&L->zdata;

This is "reliable" only if zdata is properly aligned to a struct foo.

So the alignment issue is really the heart of the quesion. You
asked above how I know that 8 is the correct alignment, and
the answer is that I don't. Currently, I'm providing an API
that allows a function to do:
array_of_int *a;
array_of_float *b;
array_of_vp *c;
struct foo f = {1,2,3};

a = abc_create_array( /* some args */, INT).i;
b = abc_create_array( /* some args */, FLOAT).f;
c = abc_create_array( /* some args */, VOID_PTR).vp;
a->insert(a, 5);
b->insert(b,5.0);
c->insert(c, &f);

Where abc_create_array returns a
union {
array_of_int *i;
array_of_float *f;
array_of_vp *vp;
};
I'd like to modify the API to do:
d = abc_create_array( /* some args */, VAR, sizeof f).vp;
d->insert(d, &f)

Where the assignment to d copies the data into the
array rather than merely adding the pointer.

Hmmm, I am too tired and caffeine-deprived at the moment for
sound judgement but I don't like it at first glance.

So I don't
know the alignment, but in the particular instance I'm
doing, the data I'm inserting is 4 floats. I'll try
setting the alignment to 16, but I don't think it should
matter, since the current setup has sizeof( struct list_el) == 32.
(ie, the zero length array is already aligned on a 32 byte
boundary)

Can the structure be aligned portably? I only know how
to do it except by relying on gcc's aligned attribute.

No. Otherwise, you could provide a portable malloc().
It is not possible to do this for each and every
possible type. What you _can_ do is
union zdata_ {
unsigned char zdata[1]; /* zdata itself */
/* alignment providers: */
float f[1]; double d[1]; long double ld[1];
long l[1]; void *pv[1]; void **ppv[1]; int *pi[1];
/* missing: pointers to struct, long long etc */
....
};
struct list_el {
x data;
/*stuff*/
union zdata_ zdata[];
};
This is, of course, unspeakably ugly and not guaranteed to
work on each and every implementation. Usually, long, (long long,
int_max_t,) double, long double, void * and maybe int (*)()
are enough.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.