[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c

packing a "variable length struct"

j.j.fishbat

6/27/2011 9:46:00 AM

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
11 Answers

Ian Collins

6/27/2011 10:49:00 AM

0

On 06/27/11 09:46 PM, fishboy wrote:
> 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;

--
Ian Collins

Alexander Bartolich

6/27/2011 11:02:00 AM

0

fishboy wrote:
> 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.

--
host -t mx moderators.isc.org

James Kuyper

6/27/2011 11:19:00 AM

0

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

Eric Sosman

6/27/2011 11:25:00 AM

0

On 6/27/2011 5:46 AM, fishboy wrote:
> [...]
> 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.

--
Eric Sosman
esosman@ieee-dot-org.invalid

Keith Thompson

6/27/2011 4:06:00 PM

0

Eric Sosman <esosman@ieee-dot-org.invalid> writes:
> On 6/27/2011 5:46 AM, fishboy wrote:
>> [...]
>> 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.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.ne...
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Shao Miller

6/27/2011 6:13:00 PM

0

On 6/27/2011 07:19, James Kuyper wrote:
> 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

6/27/2011 7:09:00 PM

0

On 6/27/2011 14:12, Shao Miller wrote:
> On 6/27/2011 07:19, James Kuyper wrote:
>>
>> 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!
>...
> 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

6/27/2011 8:10:00 PM

0

Shao Miller wrote:
> On 6/27/2011 07:19, James Kuyper wrote:
>> 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.

--
host -t mx moderators.isc.org

Shao Miller

6/27/2011 9:46:00 PM

0

On 6/27/2011 16:09, Alexander Bartolich wrote:
> Shao Miller wrote:
>> On 6/27/2011 07:19, James Kuyper wrote:
>>> 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]'?

cr88192

6/27/2011 10:35:00 PM

0

On 6/27/2011 9:06 AM, Keith Thompson wrote:
> Eric Sosman<esosman@ieee-dot-org.invalid> writes:
>> On 6/27/2011 5:46 AM, fishboy wrote:
>>> [...]
>>> 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...