Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #7040 > unrolled thread

packing a "variable length struct"

Back to article view | Back to comp.lang.c

Contents

  packing a "variable length struct" fishboy <j.j.fishbat@gmail.com> - 2011-06-27 02:46 -0700
    Re: packing a "variable length struct" Ian Collins <ian-news@hotmail.com> - 2011-06-27 22:48 +1200
    Re: packing a "variable length struct" Alexander Bartolich <alexander.bartolich@gmx.at> - 2011-06-27 11:01 +0000
      Re: packing a "variable length struct" James Kuyper <jameskuyper@verizon.net> - 2011-06-27 07:19 -0400
        Re: packing a "variable length struct" Shao Miller <sha0.miller@gmail.com> - 2011-06-27 14:12 -0400
          Re: packing a "variable length struct" Shao Miller <sha0.miller@gmail.com> - 2011-06-27 15:08 -0400
          Re: packing a "variable length struct" Alexander Bartolich <alexander.bartolich@gmx.at> - 2011-06-27 20:09 +0000
            Re: packing a "variable length struct" Shao Miller <sha0.miller@gmail.com> - 2011-06-27 17:45 -0400
    Re: packing a "variable length struct" Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-27 07:24 -0400
      Re: packing a "variable length struct" Keith Thompson <kst-u@mib.org> - 2011-06-27 09:06 -0700
        Re: packing a "variable length struct" BGB <cr88192@hotmail.com> - 2011-06-27 15:35 -0700
      Re: packing a "variable length struct" fishboy <j.j.fishbat@gmail.com> - 2011-06-30 23:54 -0700

#7040 — packing a "variable length struct"

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

[toc] | [next] | [standalone]

#7042

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

[toc] | [prev] | [next] | [standalone]

#7043

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

[toc] | [prev] | [next] | [standalone]

#7044

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

[toc] | [prev] | [next] | [standalone]

#7087

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.

[toc] | [prev] | [next] | [standalone]

#7091

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;
     }

[toc] | [prev] | [next] | [standalone]

#7094

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

[toc] | [prev] | [next] | [standalone]

#7104

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]'?

[toc] | [prev] | [next] | [standalone]

#7045

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

[toc] | [prev] | [next] | [standalone]

#7077

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.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#7109

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

[toc] | [prev] | [next] | [standalone]

#7343

Thanks for replying Eric

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

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web