packing a "variable length struct"

[fishboy]

Hi all,

I'm implementing a performance critical algorithm which contains a
"variable length struct", by which I mean

typedef stuct
{
int level;
long index;
} A_t

typedef struct
{
A_t meta;
double *centres;
} B_t

where the length of the centres array in B_t will be decided at
runtime.

[yes, I know that this is a fixed sized struct, that's why the quotes]

I have millions of these B_t which I would like to put through a
generic FIFO
(generic in the qsort() sense, using void*, explicit object sizes and
memcpy())
so it would be nice if I could "pack" the metadata and the centres
into a single
block of memory and push those blocks into the FIFO, thus avoiding
handling
the millions of mallocs() for the centres separately.

I'm thinking of something like (here n is the centres' array size)

B_t *B = some_function(n);

size_t szA = sizeof(A_t),
szC = n*sizeof(double);
void *buffer = malloc(szA + szC);

memcpy(buffer, &(B->meta), szA);
memcpy(buffer+szA, B->centres, szC);

for the packing.

Is this standards conforming? (C99 if it makes a difference)

Thanks in advance!

Jim

 

[Ian Collins]

Hi all,

I'm implementing a performance critical algorithm which contains a
"variable length struct", by which I mean

typedef stuct
{
int level;
long index;
} A_t

typedef struct
{
A_t meta;
double *centres;
} B_t

where the length of the centres array in B_t will be decided at
runtime.

[yes, I know that this is a fixed sized struct, that's why the quotes]

I have millions of these B_t which I would like to put through a
generic FIFO
(generic in the qsort() sense, using void*, explicit object sizes and
memcpy())
so it would be nice if I could "pack" the metadata and the centres
into a single
block of memory and push those blocks into the FIFO, thus avoiding
handling
the millions of mallocs() for the centres separately.

I'm thinking of something like (here n is the centres' array size)

B_t *B = some_function(n);

size_t szA = sizeof(A_t),
szC = n*sizeof(double);
void *buffer = malloc(szA + szC);

memcpy(buffer,&(B->meta), szA);
memcpy(buffer+szA, B->centres, szC);

for the packing.

Is this standards conforming? (C99 if it makes a difference)

The idiomatic approach is to use the "struct hack" which is formalised
in C99 to declare your struct:

typedef struct
{
A_t meta;
double centres[];
} B_t;

 

[Alexander Bartolich]

I'm implementing a performance critical algorithm which contains a
"variable length struct", by which I mean

typedef stuct
{
int level;
long index;
} A_t

typedef struct
{
A_t meta;
double *centres;
} B_t

The usual setup for "packed" structures is to completely omit the
pointer, i.e. declare

typedef struct
{
A_t meta;
double centres[1];
} B_t;

then allocate sufficient memory and access the array "centres" beyond
its bounds. With C99 you can make the code better reflect your intentions
by declaring a flexible array, i.e.

double centres[];

[...]
B_t *B = some_function(n);

size_t szA = sizeof(A_t),
szC = n*sizeof(double);
void *buffer = malloc(szA + szC);

You seem to be creating an instance of B_t, but your code does not
reflect your intentions. It is then no wonder that your code contains
a mistake. Have a look at this line

B_t* buffer = malloc(sizeof(B_t) + n*sizeof(double));

and ask yourself whether the amount of allocated memory is the same.

memcpy(buffer, &(B->meta), szA);
memcpy(buffer+szA, B->centres, szC);

This code does not work. What value do you expect the pointer "centres"
in your buffer to have?

Is this standards conforming? (C99 if it makes a difference)

Apart from the bug: your code invokes undefined behavior all over the
place. Nevertheless it is a common optimization. For example the ancient
library "Numerical Recipes" uses this technique.

 

[James Kuyper]

On 06/27/2011 07:01 AM, Alexander Bartolich wrote:
....

pointer, i.e. declare

typedef struct
{
A_t meta;
double centres[1];
} B_t;

then allocate sufficient memory and access the array "centres" beyond
its bounds.

You should note, however, that while this technique works with most
(?all) C compilers, any program that uses it has undefined behavior.

 

[Eric Sosman]

[...]
void *buffer = malloc(szA + szC);

memcpy(buffer,&(B->meta), szA);
memcpy(buffer+szA, B->centres, szC);

In addition to the points others have made, note that
arithmetic on `void*' (more generally, on any `incomplete_type*')
is forbidden. Pointer arithmetic takes into account the size of
the thing pointed to; if the size is unknown, as for `void*', the
arithmetic cannot be performed.

 

[Keith Thompson]

[...]
void *buffer = malloc(szA + szC);

memcpy(buffer,&(B->meta), szA);
memcpy(buffer+szA, B->centres, szC);

In addition to the points others have made, note that
arithmetic on `void*' (more generally, on any `incomplete_type*')
is forbidden. Pointer arithmetic takes into account the size of
the thing pointed to; if the size is unknown, as for `void*', the
arithmetic cannot be performed.

And if you use gcc in its default mode, it won't warn you about this;
gcc supports void* arithmetic as a non-conforming extension.

 

[Shao Miller]

On 06/27/2011 07:01 AM, Alexander Bartolich wrote:
...

pointer, i.e. declare

typedef struct
{
A_t meta;
double centres[1];
} B_t;

then allocate sufficient memory and access the array "centres" beyond
its bounds.

You should note, however, that while this technique works with most
(?all) C compilers, any program that uses it has undefined behavior.

Bounds checking as undefined behaviour? Say it ain't so!

When you have 'centres[index]', it's akin to '*(centres + index)'.
Neither of these involves the '&' or 'sizeof' operators. 'centres' then
undergoes a conversion to a 'double *'-typed value.

Now please tell me: Does that pointer point into a 'double[1]' or into
allocated memory (with no declared type) suitable for 'double[any]' and
where a 'double *' could be involved in establishing the effective type?

The meaning of "bounds" is my least favourite ambiguity in C.

 

[Shao Miller]

Bounds checking as undefined behaviour? Say it ain't so!
...
The meaning of "bounds" is my least favourite ambiguity in C.

Here's another "fun" bound-checking implementation check:

/**** Identify insane bounds-checking */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* An array type with 'char' elements */
typedef char a_10char[10];

char * test_ptr_merge(char * p, a_10char * qa) {
typedef unsigned char * bp;
char * q, * result;
bp pi, qi, ri, re;

q = *qa;
/* 'q' now points to first element */

pi = (bp)&p; qi = (bp)&q; ri = (bp)&result;
re = ri + sizeof result;
while (ri < re)
/* Defect Report #260: "Provenance" */
*ri++ = *pi++ & *qi++;
pi = (bp)&p; qi = (bp)&q; ri = (bp)&result;
while (ri < re)
if (*ri != *pi++ || *ri++ != *qi++)
return (void *) 0;
return result;
}

int main(void) {
void * vp;
char * cp, * test;
a_10char * ap;

/* 15 bytes */
vp = malloc(sizeof *ap + 5);
if (!vp) {
puts("Out of memory!");
return EXIT_FAILURE;
}

cp = vp;
ap = vp;
/*
* 'cp' and 'ap' now both point to the
* same memory, which still has no
* effective type.
*/

test = test_ptr_merge(cp, ap);
if (!test) {
puts("Test showed insanity.");
return EXIT_FAILURE;
}

/* What bounds apply to use of 'test'? */
strcpy(test, "0123456789ABCD");
puts(test);

free(test);
return EXIT_SUCCESS;
}

 

[Alexander Bartolich]

On 06/27/2011 07:01 AM, Alexander Bartolich wrote:
...

pointer, i.e. declare

typedef struct
{
A_t meta;
double centres[1];
} B_t;

then allocate sufficient memory and access the array "centres" beyond
its bounds.

You should note, however, that while this technique works with most
(?all) C compilers, any program that uses it has undefined behavior.

Bounds checking as undefined behaviour? Say it ain't so!

Imagine a platform where the address range reachable by index/offset
registers is smaller than the address range covered by size_t.

Exhibit 1: Intel 8086, running in 16-bit mode, memory model "Huge".
Exhibit 2: The Atmel AVR, a contemporary 8-bit microcontroller.

The compiler can generate much more efficient code if it assumes that
the array will not be accessed beyond its bounds.

 

[Shao Miller]

On 06/27/2011 07:01 AM, Alexander Bartolich wrote:
...
pointer, i.e. declare

typedef struct
{
A_t meta;
double centres[1];
} B_t;

then allocate sufficient memory and access the array "centres" beyond
its bounds.

You should note, however, that while this technique works with most
(?all) C compilers, any program that uses it has undefined behavior.

Bounds checking as undefined behaviour? Say it ain't so!

Imagine a platform where the address range reachable by index/offset
registers is smaller than the address range covered by size_t.

Where does 'size_t' come into things? Or even 'ptrdiff_t', though you
didn't bring it up.

Are you suggesting that there are values of 'size_t' for which 'malloc'
might return a null pointer value? I can certainly agree to that.

Exhibit 1: Intel 8086, running in 16-bit mode, memory model "Huge".
Exhibit 2: The Atmel AVR, a contemporary 8-bit microcontroller.

The compiler can generate much more efficient code if it assumes that
the array will not be accessed beyond its bounds.

Sure. What bothers me is that Standard text including "bounds"[footnote
94] and "not an element of an array"[6.5.6p7] and "array
object"[6.3.2.1p3, 6.5.2.1p2, 6.5.2.1p3, 6.5.2.1p4, 6.5.9p6, etc.] and
"same array object"[6.5.6p8, 6.5.6p9, 6.5.8p5, 6.5.8p6] appear to lead
to some challenges.

If we use "effective type"[6.5p6] to determine if something is or is not
an "array object," that's fine. But then for:

#include <stdlib.h>
#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct {
int level;
long index;
} A_t;

typedef struct {
A_t meta;
double centres[1];
} B_t;

int main(void) {
void * vp;
char * finder;
B_t * foo;
double (* dbl_arr_ptr)[6];
double * dbl_ptr;

/* Certainly room for a 'double[6]' */
vp = malloc(sizeof *foo + sizeof (double[5]));
assert(vp);

/* Find 'centres' */
finder = vp;
finder += offsetof(B_t, centres);

/* Pretend a 'double[6]' is there */
dbl_arr_ptr = (void *) finder;

/* Establish the effective type */
1[*dbl_arr_ptr] = 3.14159;

/* Pretend we have a 'B_t' at 'vp' */
foo = vp;

/* Point one past 'centres' */
dbl_ptr = foo->centres + 1;

printf("We have: %f\n", *dbl_ptr);

free(foo);
return 0;
}

Does the 'printf' line invoke undefined behaviour? What does 'dbl_ptr'
point to? Is it one past the single-element 'centres' array or is it
the second element of an object with effective type 'double[6]'?

 

[BGB]

[...]
void *buffer = malloc(szA + szC);

memcpy(buffer,&(B->meta), szA);
memcpy(buffer+szA, B->centres, szC);

In addition to the points others have made, note that
arithmetic on `void*' (more generally, on any `incomplete_type*')
is forbidden. Pointer arithmetic takes into account the size of
the thing pointed to; if the size is unknown, as for `void*', the
arithmetic cannot be performed.

And if you use gcc in its default mode, it won't warn you about this;
gcc supports void* arithmetic as a non-conforming extension.

and many who use GCC fail to realize that this is an extension...

 

[fishboy]

Thanks for replying Eric

     In addition to the points others have made, note that
arithmetic on `void*' (more generally, on any `incomplete_type*')
is forbidden.  

Ah, I suspected that I was guilty of some kind of badness.

I implemented the above (which compiles and runs fine on
gcc/linux/intel) and also the "millions of mallocs" method
I was hoping to avoid, and both run at the same speed.
So I'll use the latter and stay legal .

Thanks again for your help


Jim