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

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

Padding between char array/VLA in struct?

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

Contents

  Padding between char array/VLA in struct? Ian Pilcher <arequipeno@gmail.com> - 2021-08-02 12:48 -0500
    Re: Padding between char array/VLA in struct? James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-08-02 14:07 -0400
      Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 11:25 -0700
        Re: Padding between char array/VLA in struct? James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-08-02 19:21 -0400
    Re: Padding between char array/VLA in struct? Bart <bc@freeuk.com> - 2021-08-02 19:11 +0100
      Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 11:27 -0700
        Re: Padding between char array/VLA in struct? Bart <bc@freeuk.com> - 2021-08-02 20:43 +0100
          Re: Padding between char array/VLA in struct? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2021-08-02 13:11 -0700
            Re: Padding between char array/VLA in struct? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2021-08-02 13:18 -0700
            Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 13:31 -0700
              Re: Padding between char array/VLA in struct? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2021-08-02 19:50 -0700
                Re: Padding between char array/VLA in struct? David Brown <david.brown@hesbynett.no> - 2021-08-04 14:01 +0200
          Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 13:19 -0700
          Re: Padding between char array/VLA in struct? BGB <cr88192@gmail.com> - 2021-08-03 10:40 -0500
            Re: Padding between char array/VLA in struct? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2021-08-03 09:10 -0700
              Re: Padding between char array/VLA in struct? BGB <cr88192@gmail.com> - 2021-08-03 12:52 -0500
                Re: Padding between char array/VLA in struct? BGB <cr88192@gmail.com> - 2021-08-04 12:05 -0500
    Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 11:12 -0700
      Re: Padding between char array/VLA in struct? Bart <bc@freeuk.com> - 2021-08-02 19:23 +0100
        Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 13:15 -0700
    Re: Padding between char array/VLA in struct? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2021-08-02 11:32 -0700
    Re: Padding between char array/VLA in struct? Ian Pilcher <arequipeno@gmail.com> - 2021-08-02 13:59 -0500
      Re: Padding between char array/VLA in struct? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-08-02 12:47 -0700
        Re: Padding between char array/VLA in struct? Ian Pilcher <arequipeno@gmail.com> - 2021-08-02 15:27 -0500
          Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 13:36 -0700
          Re: Padding between char array/VLA in struct? antispam@math.uni.wroc.pl - 2021-08-02 21:52 +0000
      Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-02 13:22 -0700
        Re: Padding between char array/VLA in struct? Manfred <noname@add.invalid> - 2021-08-04 17:01 +0200
          Re: Padding between char array/VLA in struct? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-08-04 10:11 -0700

Page 1 of 2  [1] 2  Next page →

#162195 — Padding between char array/VLA in struct?

Given the following:

   struct foo {
       /* other members */
       char prefix[PREFIX_SIZE];
       char name[];
   };

Is there any circumstance in which the compiler is permitted to insert
padding between the 'prefix' and 'name' members?

I'm 99% sure than the answer is no, but I've been unable to track down
the actual rules anywhere.

-- 
========================================================================
Ian Pilcher                                         arequipeno@gmail.com
-------- "I grew up before Mark Zuckerberg invented friendship" --------
========================================================================

[toc] | [next] | [standalone]

#162196

On 8/2/21 1:48 PM, Ian Pilcher wrote:
> Given the following:
> 
>    struct foo {
>        /* other members */

Note: this is a VLA unless PREFIX_SIZE is a macro that expands to an
integer constant expression.

>        char prefix[PREFIX_SIZE];

This is NOT a VLA - it is a flexible array member:

>        char name[];
>    };
> 
> Is there any circumstance in which the compiler is permitted to insert
> padding between the 'prefix' and 'name' members?
> 
> I'm 99% sure than the answer is no, but I've been unable to track down
> the actual rules anywhere.

"There may be unnamed padding within a structure object, but not at its
beginning." (6.7.2.1p15).

Thus, the only restriction on such padding is that it can't be at the
beginning. I know of no other restrictions on the presence, the size, or
the location of any such padding.

There are some relevant special rules covering flexible array members,
but they don't revoke the permission give by 6.7.2.1p15 to have such
padding:

"... when a . (or ->) operator has a left operand that is
(a pointer to) a structure with a flexible array member and the right
operand names that member, it behaves as if that member were replaced
with the longest array (with the same element type) that would not make
the structure larger than the object being accessed; the offset of the
array shall remain that of the flexible array member, even if this would
differ from that of the replacement array." (6.7.2.1p18)

Since the replacement array would be allowed to have padding that
separates it from the prefix array, then that is also permitted for the
flexible array member.

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

#162200

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> On 8/2/21 1:48 PM, Ian Pilcher wrote:
>> Given the following:
>> 
>>    struct foo {
>>        /* other members */
>
> Note: this is a VLA unless PREFIX_SIZE is a macro that expands to an
> integer constant expression.
>
>>        char prefix[PREFIX_SIZE];

This cannot be a VLA because VLAs are not allowed as struct or union members.

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

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

#162215

On 8/2/21 2:25 PM, Keith Thompson wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>> On 8/2/21 1:48 PM, Ian Pilcher wrote:
>>> Given the following:
>>>
>>>    struct foo {
>>>        /* other members */
>>
>> Note: this is a VLA unless PREFIX_SIZE is a macro that expands to an
>> integer constant expression.
>>
>>>        char prefix[PREFIX_SIZE];
> 
> This cannot be a VLA because VLAs are not allowed as struct or union members
You're right - I suspected that the thing he incorrectly thought was a
VLA was "name", but I wanted to cover the possibility that it was
"prefix". In my haste, I mentioned only one of the reasons (and the less
important one, to boot), why it wouldn't be one.

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

#162197

On 02/08/2021 18:48, Ian Pilcher wrote:
> Given the following:
> 
>    struct foo {
>        /* other members */
>        char prefix[PREFIX_SIZE];
>        char name[];
>    };
> 
> Is there any circumstance in which the compiler is permitted to insert
> padding between the 'prefix' and 'name' members?
> 
> I'm 99% sure than the answer is no, but I've been unable to track down
> the actual rules anywhere.
> 

I think only for alignment purposes. And there is no need when name has 
char[] type. With int name[], then possibly.

BTW there is no VLA here unless PREFIX_SIZE is not a compile-time 
expression (and I'm not sure even then).

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

#162201

Bart <bc@freeuk.com> writes:
> On 02/08/2021 18:48, Ian Pilcher wrote:
>> Given the following:
>>    struct foo {
>>        /* other members */
>>        char prefix[PREFIX_SIZE];
>>        char name[];
>>    };
>> Is there any circumstance in which the compiler is permitted to
>> insert
>> padding between the 'prefix' and 'name' members?
>> I'm 99% sure than the answer is no, but I've been unable to track
>> down
>> the actual rules anywhere.
>
> I think only for alignment purposes. And there is no need when name
> has char[] type. With int name[], then possibly.

Compilers are unlikely to insert padding other than for alignment
purposes, but the standard doesn't make that restriction.  A conforming
compiler can add as much padding as it likes between members or after
the last member (if the last member isn't a flexible array member, which
it is in this case).

> BTW there is no VLA here unless PREFIX_SIZE is not a compile-time
> expression (and I'm not sure even then).

If PREFIX_SIZE is not a compile time expression, it's a constraint
violation.  Struct and union member cannot be VLAs.  (Also, VLA support
is optional as of C11.)

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

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

#162204

On 02/08/2021 19:27, Keith Thompson wrote:
> Bart <bc@freeuk.com> writes:

>> BTW there is no VLA here unless PREFIX_SIZE is not a compile-time
>> expression (and I'm not sure even then).
> 
> If PREFIX_SIZE is not a compile time expression, it's a constraint
> violation.  Struct and union member cannot be VLAs.  (Also, VLA support
> is optional as of C11.)
> 

This program works on gcc, tcc and lccwin:

#include <stdio.h>
int main(void) {
     int n=100;
     typedef struct{int xx[n];} S;

     S a;

     printf("sizeof(S) = %d\n",(int)sizeof(S));
}

The output is respectively 400, 8 and 32.

It fails with DMC, clang, msvc and bcc (but the last two don't support 
VLAs anyway).

The mind boggles as to how it's implemented, for example with static, 
auto and heap-allocated arrays of S, or with linked lists using S nodes, 
or when S itself contains structs with such VLAs.

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

#162206

On 8/2/2021 12:43 PM, Bart wrote:
>>
> 
> This program works on gcc, tcc and lccwin:
> 
> #include <stdio.h>
> int main(void) {
>      int n=100;
>      typedef struct{int xx[n];} S;
> 
>      S a;
> 
>      printf("sizeof(S) = %d\n",(int)sizeof(S));
> }
> 
> The output is respectively 400, 8 and 32.
> 
> It fails with DMC, clang, msvc and bcc (but the last two don't support 
> VLAs anyway).

It will fail in GCC as well if you run it in `-pedantic` mode.

> The mind boggles as to how it's implemented, for example with static, 
> auto and heap-allocated arrays of S, or with linked lists using S nodes, 
> or when S itself contains structs with such VLAs.

There's nothing mind-boggling about how it is implemented once you 
realize that this is allowed for trailing array member only. This GCC 
extension is a hybrid of "flexible array member" memory layout and VLA 
semantics.

-- 
Best regards,
Andrey Tarasevich

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

#162208

On 8/2/2021 1:11 PM, Andrey Tarasevich wrote:
> 
> There's nothing mind-boggling about how it is implemented once you 
> realize that this is allowed for trailing array member only. This GCC 
> extension is a hybrid of "flexible array member" memory layout and VLA 
> semantics.
> 

An interesting experiment that immediately comes to mind

   int n=100;
   typedef struct{ int xx[n]; } S;

   S a;
   int i = 0;

   printf("%zu\n", sizeof(*(++i, &a.xx)));
   printf("%d\n", i);

   printf("%zu\n", sizeof(*(++i, &a)));
   printf("%d\n", i);

outputs

   400
   1
   400
   1

which indicates that GCC perceives `a.xx` as an entity having variably 
modified type (a VLA), but doesn't dare to go as far as treating the 
struct type itself as a variably modified type.

-- 
Best regards,
Andrey Tarasevich

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

#162212

Andrey Tarasevich <andreytarasevich@hotmail.com> writes:
> On 8/2/2021 12:43 PM, Bart wrote:
>>>
>> This program works on gcc, tcc and lccwin:
>> #include <stdio.h>
>> int main(void) {
>>      int n=100;
>>      typedef struct{int xx[n];} S;
>>      S a;
>>      printf("sizeof(S) = %d\n",(int)sizeof(S));
>> }
>> The output is respectively 400, 8 and 32.
>> It fails with DMC, clang, msvc and bcc (but the last two don't
>> support VLAs anyway).
>
> It will fail in GCC as well if you run it in `-pedantic` mode.
>
>> The mind boggles as to how it's implemented, for example with
>> static, auto and heap-allocated arrays of S, or with linked lists
>> using S nodes, or when S itself contains structs with such VLAs.
>
> There's nothing mind-boggling about how it is implemented once you
> realize that this is allowed for trailing array member only. This GCC 
> extension is a hybrid of "flexible array member" memory layout and VLA
> semantics.

No, gcc's extension appears to allow VLAs as struct members.  This
compiles and runs without error and, as expected, prints different
values when it's executed again after more than a second:

#include <stdio.h>
#include <time.h>
#include <stddef.h>
int main(void) {
    const int size = time(NULL) % 10 + 10;
    struct s {
        char s0[size];
        char s1[size];
        char s2[size];
    };

    struct s obj;

    printf("sizeof obj = %zu\n", sizeof obj);
    printf("%zu %zu %zu\n",
           offsetof(struct s, s0),
           offsetof(struct s, s1),
           offsetof(struct s, s2));
}

(I didn't find this extension in gcc's documentation, but I didn't look
very hard.)

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

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

#162216

On 8/2/2021 1:31 PM, Keith Thompson wrote:
> 
> No, gcc's extension appears to allow VLAs as struct members.  This
> compiles and runs without error and, as expected, prints different
> values when it's executed again after more than a second:
> 
> #include <stdio.h>
> #include <time.h>
> #include <stddef.h>
> int main(void) {
>      const int size = time(NULL) % 10 + 10;
>      struct s {
>          char s0[size];
>          char s1[size];
>          char s2[size];
>      };
> 
>      struct s obj;
> 
>      printf("sizeof obj = %zu\n", sizeof obj);
>      printf("%zu %zu %zu\n",
>             offsetof(struct s, s0),
>             offsetof(struct s, s1),
>             offsetof(struct s, s2));
> }
> 
> (I didn't find this extension in gcc's documentation, but I didn't look
> very hard.)
> 

Oh, indeed... I missed that. Thank you for pointing it out.

Interestingly, when GCC has to deal with a bunch of independent VLAs

   char s0[n0];
   char s1[n1];
   char s2[n2];

in the generated code it typically implements them as simple individual 
`char *` pointers, pointing into memory allocated by `alloca`-like 
mechanism.

But once they are bundled into a struct

   struct s
   {
     char s0[n0];
     char s1[n1];
     char s2[n2];
   } obj;

GCC no longer has a luxury of implementing each array as an individual 
pointer. It wants to maintain a flat memory layout for a struct object, 
which forces it to generate code that allocates a memory buffer of size 
`n0+n1+n2` and then use arithmetic on-the-fly to locate each individual 
array in that buffer, e.g. to locate the beginning of `s2` it has to 
calculate `n0+n1`.

In other words, the latter implementation does not come "for free": it 
is markedly different from the former.

-- 
Best regards,
Andrey Tarasevich

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

#162224

On 03/08/2021 04:50, Andrey Tarasevich wrote:
> On 8/2/2021 1:31 PM, Keith Thompson wrote:
>>
>> No, gcc's extension appears to allow VLAs as struct members.  This
>> compiles and runs without error and, as expected, prints different
>> values when it's executed again after more than a second:
>>
>> #include <stdio.h>
>> #include <time.h>
>> #include <stddef.h>
>> int main(void) {
>>      const int size = time(NULL) % 10 + 10;
>>      struct s {
>>          char s0[size];
>>          char s1[size];
>>          char s2[size];
>>      };
>>
>>      struct s obj;
>>
>>      printf("sizeof obj = %zu\n", sizeof obj);
>>      printf("%zu %zu %zu\n",
>>             offsetof(struct s, s0),
>>             offsetof(struct s, s1),
>>             offsetof(struct s, s2));
>> }
>>
>> (I didn't find this extension in gcc's documentation, but I didn't look
>> very hard.)

<https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html>


>>
> 
> Oh, indeed... I missed that. Thank you for pointing it out.
> 
> Interestingly, when GCC has to deal with a bunch of independent VLAs
> 
>   char s0[n0];
>   char s1[n1];
>   char s2[n2];
> 
> in the generated code it typically implements them as simple individual
> `char *` pointers, pointing into memory allocated by `alloca`-like
> mechanism.

There is a significant difference between VLA's and alloca, AFAIUI -
memory from alloca is deallocated at the end of the function, while for
a VLA it can be deallocated at the end of the VLA's lifetime (the
containing block).  But in each case, you have an "alloca-like
mechanism" - generally a simple manipulation of the cpu stack pointer.

> 
> But once they are bundled into a struct
> 
>   struct s
>   {
>     char s0[n0];
>     char s1[n1];
>     char s2[n2];
>   } obj;
> 
> GCC no longer has a luxury of implementing each array as an individual
> pointer. It wants to maintain a flat memory layout for a struct object,
> which forces it to generate code that allocates a memory buffer of size
> `n0+n1+n2` and then use arithmetic on-the-fly to locate each individual
> array in that buffer, e.g. to locate the beginning of `s2` it has to
> calculate `n0+n1`.
> 
> In other words, the latter implementation does not come "for free": it
> is markedly different from the former.
> 

All of n0, n1 and n2 must be known at the time the struct is declared,
and the sizes of the VLA's remain constant even if the variables n0, n1
and n2 are later changed.

So in the first case, the compiler might make three "char *" pointers
with a known relation between them (as they are all allocated on the
stack at the same time).  In the second case, it could make one "struct
s *" pointer and use that with known offsets to access the individual
arrays.  In each case, the addresses and the data known to the compiler
are the same.  There is likely to be no significant difference in
implementation between the two, as the compiler will mix and match
multiple pointers with pointers plus offset, according to what is most
efficient at the time.

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

#162209

Bart <bc@freeuk.com> writes:
> On 02/08/2021 19:27, Keith Thompson wrote:
>> Bart <bc@freeuk.com> writes:
>
>>> BTW there is no VLA here unless PREFIX_SIZE is not a compile-time
>>> expression (and I'm not sure even then).
>> If PREFIX_SIZE is not a compile time expression, it's a constraint
>> violation.  Struct and union member cannot be VLAs.  (Also, VLA support
>> is optional as of C11.)
>
> This program works on gcc, tcc and lccwin:
>
> #include <stdio.h>
> int main(void) {
>     int n=100;
>     typedef struct{int xx[n];} S;
>
>     S a;
>
>     printf("sizeof(S) = %d\n",(int)sizeof(S));
> }
>
> The output is respectively 400, 8 and 32.
>
> It fails with DMC, clang, msvc and bcc (but the last two don't support
> VLAs anyway).

To be a bit clearer, defining a struct member as a VLA is a constraint
violation.  A conforming C compiler must diagnose it.  It can then
proceed to generate code for it -- or a non-conforming compiler (such as
gcc by default) can do anything it likes.

> The mind boggles as to how it's implemented, for example with static,
> auto and heap-allocated arrays of S, or with linked lists using S
> nodes, or when S itself contains structs with such VLAs.

gcc's extension does not include support for static structs with VLA
members.  The other cases don't strike me as particularly difficult,
though of course they require a bit more work than for structs whose
size is known at compile time.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

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

#162217

On 8/2/2021 2:43 PM, Bart wrote:
> On 02/08/2021 19:27, Keith Thompson wrote:
>> Bart <bc@freeuk.com> writes:
> 
>>> BTW there is no VLA here unless PREFIX_SIZE is not a compile-time
>>> expression (and I'm not sure even then).
>>
>> If PREFIX_SIZE is not a compile time expression, it's a constraint
>> violation.  Struct and union member cannot be VLAs.  (Also, VLA support
>> is optional as of C11.)
>>
> 
> This program works on gcc, tcc and lccwin:
> 
> #include <stdio.h>
> int main(void) {
>      int n=100;
>      typedef struct{int xx[n];} S;
> 
>      S a;
> 
>      printf("sizeof(S) = %d\n",(int)sizeof(S));
> }
> 
> The output is respectively 400, 8 and 32.
> 
> It fails with DMC, clang, msvc and bcc (but the last two don't support 
> VLAs anyway).
> 

This will not likely work correctly in my compiler either, unless a 
special case provision were made for the last member in a struct (the 
expression would be ignored in this case).


> The mind boggles as to how it's implemented, for example with static, 
> auto and heap-allocated arrays of S, or with linked lists using S nodes, 
> or when S itself contains structs with such VLAs.

FWIW: My compiler (BGBCC) also supports VLAs, though only for local 
variables and similar. In these contexts, they effectively decay into 
pointers, and are transformed into an "alloca()" call.

Potentially, a static or global VLA could be transformed into creative 
use of "realloc" or similar, or a wrapper around realloc, eg:
   void __vla_globalvla(void **rptr, size_t *rsz, size_t newsz);

Which then resizes the array to be bigger if the new size exceeds the 
old size, and would probably be called (potentially repeatedly) by any 
function which tries to access such an array.


But, as can be noted, my compiler doesn't do anything too fancy to 
support "alloca()"; in effect this gets turned by the compiler into a 
special runtime call for "call malloc() and then add the returned 
pointer to a linked list", and then in the epilog a function call is 
added to free anything that was added to the list.

I also make no claim that multidimensional VLAs "actually work"...


Note that for normal functions with arrays, the compiler may also add 
special guard tokens, and then trigger a breakpoint on function return 
if these don't match their expected values. This partly helps detect if 
an array overrun has occurred, but may also help detect cases where the 
stack-pointer got messed up or similar.

...



My compiler also recently added lambdas, which effectively make use of 
the same mechanism as "alloca()" (though does use a different runtime 
call so that the returned memory can be marked as executable).

The spec for lambdas more-or-less follows the C23 proposal, but there is 
an alternate syntax as well which allows for (among other things), 
creating lambdas with an unbounded lifespan (though with the restriction 
that they will leak memory unless manually freed).

In this case, the lambda is basically a struct, with the first 32-bytes 
(at present) reserved for setting up the registers and calling into the 
function body (the current stub uses 28 bytes).

The encodings used for the stub is slightly conservative, but using a 
few newer encodings, it could be possible to cram it down to 12 bytes. 
However, the encodings in question are not currently part of the 
"baseline" ISA, and in practice this isn't likely to make much real 
difference on either performance or memory footprint.

...

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

#162218

On 8/3/2021 8:40 AM, BGB wrote:
> 
> FWIW: My compiler (BGBCC) also supports VLAs, though only for local 
> variables and similar. In these contexts, they effectively decay into 
> pointers, and are transformed into an "alloca()" call.
> ...
> But, as can be noted, my compiler doesn't do anything too fancy to 
> support "alloca()"; in effect this gets turned by the compiler into a 
> special runtime call for "call malloc() and then add the returned 
> pointer to a linked list", and then in the epilog a function call is 
> added to free anything that was added to the list.
> 
> I also make no claim that multidimensional VLAs "actually work"...
> ...

It appears that the amount of effort you spent implementing your 
pseudo-VLA would be quite sufficient to implement the standard-compliant 
VLA. You just needed to channel that effort slightly differently. Which 
makes one wonder why you decided to eschew the standard semantics...

-- 
Best regards,
Andrey Tarasevich

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

#162219

On 8/3/2021 11:10 AM, Andrey Tarasevich wrote:
> On 8/3/2021 8:40 AM, BGB wrote:
>>
>> FWIW: My compiler (BGBCC) also supports VLAs, though only for local 
>> variables and similar. In these contexts, they effectively decay into 
>> pointers, and are transformed into an "alloca()" call.
>> ...
>> But, as can be noted, my compiler doesn't do anything too fancy to 
>> support "alloca()"; in effect this gets turned by the compiler into a 
>> special runtime call for "call malloc() and then add the returned 
>> pointer to a linked list", and then in the epilog a function call is 
>> added to free anything that was added to the list.
>>
>> I also make no claim that multidimensional VLAs "actually work"...
>> ...
> 
> It appears that the amount of effort you spent implementing your 
> pseudo-VLA would be quite sufficient to implement the standard-compliant 
> VLA. You just needed to channel that effort slightly differently. Which 
> makes one wonder why you decided to eschew the standard semantics...
> 

Partly it was because this was what seemed easier, and also allowed 
doing pretty much all of the VLA stuff to be handled in the front-end 
(things like lambdas are also handled in the frontend, as are many 
operations involving "variant" types, *1, ...).

With the ABI design, variable-sized stack frames would have added more 
complexity relative to fixed-size stack frames (there is no frame 
pointer or similar in this case, and everything on-stack is referenced 
using fixed displacements relative to the stack pointer, and 
prolog/epilog adjustments use fixed offsets, ...).


Note that this is generally for a target where:
   I am using 128K as the default stack size;
     (Except for interrupt handlers, which use an 8K stack).
   The target is (or assumes) No-MMU operation;
   The RAM space is typically measured in MB.

Using malloc ends up preferable for larger memory allocations (VLAs or 
large stack arrays), since it isn't bound by the stack-size limit, and 
doesn't assume spending inordinate amounts of RAM on the program stacks.

Though, a few cases exist where the total RAM is measured in KB (and the 
heap is just sorta wedged between ".bss" and the stack).


*1: The variant types are a non-standard extension which add dynamic 
type-checking via tagged pointers; and turns pretty much every operation 
on these types into a function call into the runtime.

...

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

#162231

On 8/3/2021 12:52 PM, BGB wrote:
> On 8/3/2021 11:10 AM, Andrey Tarasevich wrote:
>> On 8/3/2021 8:40 AM, BGB wrote:
>>>
>>> FWIW: My compiler (BGBCC) also supports VLAs, though only for local 
>>> variables and similar. In these contexts, they effectively decay into 
>>> pointers, and are transformed into an "alloca()" call.
>>> ...
>>> But, as can be noted, my compiler doesn't do anything too fancy to 
>>> support "alloca()"; in effect this gets turned by the compiler into a 
>>> special runtime call for "call malloc() and then add the returned 
>>> pointer to a linked list", and then in the epilog a function call is 
>>> added to free anything that was added to the list.
>>>
>>> I also make no claim that multidimensional VLAs "actually work"...
>>> ...
>>
>> It appears that the amount of effort you spent implementing your 
>> pseudo-VLA would be quite sufficient to implement the 
>> standard-compliant VLA. You just needed to channel that effort 
>> slightly differently. Which makes one wonder why you decided to eschew 
>> the standard semantics...
>>
> 
> Partly it was because this was what seemed easier, and also allowed 
> doing pretty much all of the VLA stuff to be handled in the front-end 
> (things like lambdas are also handled in the frontend, as are many 
> operations involving "variant" types, *1, ...).
> 

Also, decaying to a pointer type is easier from a semantics POV, since 
fully dealing with VLAs in the type-system would be a lot more 
complicated than:
   int foo[n];
effectively decaying into:
   int *foo;
Even if the simple case falls on its face if someone tries to write:
   int bar[m][n];
Or similar.


Closest one can really handle the latter case is to decay it into 
multiple levels of indirection, so for:
   int bar[m][n];
   i=bar[x][y];
Might become, say:
   int *bar;
   i=((int ***)bar)[-1][x][y];

Or, a memory blob pointing to the start of the lowest level array, 
preceded by a pointer to the top level array, and followed by a number 
of array indirection pointers, ...

With the type-system still needing to remember that it was a VLA, and 
its number of indirection levels, ...

But, this latter case falls into "there be dragons here" territory.


> With the ABI design, variable-sized stack frames would have added more 
> complexity relative to fixed-size stack frames (there is no frame 
> pointer or similar in this case, and everything on-stack is referenced 
> using fixed displacements relative to the stack pointer, and 
> prolog/epilog adjustments use fixed offsets, ...).
> 
> 
> Note that this is generally for a target where:
>    I am using 128K as the default stack size;
>      (Except for interrupt handlers, which use an 8K stack).
>    The target is (or assumes) No-MMU operation;
>    The RAM space is typically measured in MB.
> 
> Using malloc ends up preferable for larger memory allocations (VLAs or 
> large stack arrays), since it isn't bound by the stack-size limit, and 
> doesn't assume spending inordinate amounts of RAM on the program stacks.
> 
> Though, a few cases exist where the total RAM is measured in KB (and the 
> heap is just sorta wedged between ".bss" and the stack).
> 

This does assume that the malloc is fast enough to not have a 
significant adverse effect on performance, which seems to generally be 
true in this case.


In the average case, most of the cost time into mapping the size to a 
"size index" and then retrieving an item from a free-list corresponding 
to this index. If one is repeatedly allocating and freeing objects of 
the same size, this case works out reasonably fast.

It could be made faster if one could precalculate this index in the 
compiler, but this would still be is N/A for VLAs.

The size-index is essentially a specialized 8-bit microfloat (E5.F3), 
which stores the size in a rounded-up form (relative to an 8-byte unit 
size), eg:
     0,   8,  16,  24,  32,  40,  48,  56,  //E=0, Step=8
    64,  72,  80,  88,  96, 104, 112, 120,  //E=1, Step=8
   128, 144, 160, 176, 192, 208, 224, 240,  //E=2, Step=16
   256, 288, 320, 352, 384, ...             //E=3, Step=32
   ...

For small objects, a cell-based allocator can be used, which allocates 
the object as runs of 8-byte cells using an allocation bitmap.

For medium objects, the allocator can use linked-lists of memory blocks.
For large objects, the allocator might use memory pages instead.


> 
> *1: The variant types are a non-standard extension which add dynamic 
> type-checking via tagged pointers; and turns pretty much every operation 
> on these types into a function call into the runtime.
> 

FWIW: Given the nature of dynamic tags, there is no way to make them 
particularly fast. The compiler does optimize for a few cases where it 
knows the tag layout, but given pretty much every operation requires a 
sort of dynamic dispatch, it is not viable to do this inline.

For most of it though, the compiler just sort of treats it as-if one had 
written it out as a bunch of function calls.

In this case, a scheme is used where 64-bit tagged-references are used 
with the tag bits in the high-order bits (can encode "fixnum" and 
"flonum" types using 62 bits, with 48 bit available for pointers).


As noted, I also have a few features from the C23 proposals lists.

Lambdas:
   int (*fn)(int x);
   int i, j;
   fn = [=](int x)->int { return(x*j); };

Currently only supports capture by value, and an extension syntax:
   fn = __function(int x):int { return(x*j); };


Which differs slightly in that it supports unbounded lifespan (my 
understanding of regarding the proposal being that it only supports 
automatic lifespan, and doesn't provide any notation to specify dynamic 
/ heap-allocated lambdas). Implicitly, capture-by-value does not care 
if/when the original stack-frame that created it is destroyed (this 
would be as bigger issue for capture-by-reference though).



Variable-sized integers:
   _BitInt( 96) li;  //96-bit integer (padded to 128 bits)
   _BitInt(192) lj;  //192 bits (padded to 256 bits)
   _BitInt(384) lk;  //384 bits
For sizes <= 128 bits, falling back to a corresponding integer type.

For sizes larger than 128 bits, padding to a multiple of 128 bits, and 
implementing most operations via runtime calls.
In terms of the implementation, they have behavior partway between 
structs and array (they have struct-like semantics, but in terms of the 
type-system are represented more like a special sub-type of an array of 
128-bit elements).

Note that 128-bit integers can at-least be semi-competently handled in 
the base ISA in this case, so many operations can be handled inline 
(more so if the use of 128-bit ALU operations is enabled in the compiler).


No support yet for "_Generic", but partly this is because I have yet to 
run into many cases where using it "makes sense".

Support for features from newer standards is a bit cherry-picked though, 
mostly "stuff that seemed useful" (along with features which overlap 
with my own custom language).

...

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

#162198

Ian Pilcher <arequipeno@gmail.com> writes:
> Given the following:
>
>   struct foo {
>       /* other members */
>       char prefix[PREFIX_SIZE];
>       char name[];
>   };
>
> Is there any circumstance in which the compiler is permitted to insert
> padding between the 'prefix' and 'name' members?
>
> I'm 99% sure than the answer is no, but I've been unable to track down
> the actual rules anywhere.

I'm 99% sure the answer is "always".

Compilers typically insert padding only when it's necessary to meet
alignment requirements, but compilers are allowed to insert arbitrary
padding between members.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

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

#162199

On 02/08/2021 19:12, Keith Thompson wrote:
> Ian Pilcher <arequipeno@gmail.com> writes:
>> Given the following:
>>
>>    struct foo {
>>        /* other members */
>>        char prefix[PREFIX_SIZE];
>>        char name[];
>>    };
>>
>> Is there any circumstance in which the compiler is permitted to insert
>> padding between the 'prefix' and 'name' members?
>>
>> I'm 99% sure than the answer is no, but I've been unable to track down
>> the actual rules anywhere.
> 
> I'm 99% sure the answer is "always".
> 
> Compilers typically insert padding only when it's necessary to meet
> alignment requirements, but compilers are allowed to insert arbitrary
> padding between members.
> 

But not for no reason, surely? And not when #pragma pack(1) is in effect.

And whatever padding might be inserted, the same rules must be in effect 
across all compilers for that platform, otherwise functions in modules 
and in external libraries created with mixed compilers can't call each 
other.

Since I am familiar with duplicating with layout of C structs from 
outside the language, to the extent of also duplicating the algorithms 
for alignment and padding, this would be an impossible task if 
effectively random padding could be inserted.

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

#162207

Bart <bc@freeuk.com> writes:
> On 02/08/2021 19:12, Keith Thompson wrote:
>> Ian Pilcher <arequipeno@gmail.com> writes:
>>> Given the following:
>>>
>>>    struct foo {
>>>        /* other members */
>>>        char prefix[PREFIX_SIZE];
>>>        char name[];
>>>    };
>>>
>>> Is there any circumstance in which the compiler is permitted to insert
>>> padding between the 'prefix' and 'name' members?
>>>
>>> I'm 99% sure than the answer is no, but I've been unable to track down
>>> the actual rules anywhere.
>> I'm 99% sure the answer is "always".
>> Compilers typically insert padding only when it's necessary to meet
>> alignment requirements, but compilers are allowed to insert arbitrary
>> padding between members.
>
> But not for no reason, surely? And not when #pragma pack(1) is in effect.

Yes, for no reason.

To be clear, I was talking about what the C standard permits.

The standard says that padding may be inserted between members.  It says
nothing about what reasons a compiler must have for doing so.  A
compiler that inserts unneeded padding "for no reason" would likely be a
poor compiler, but it would not violate the standard.

#pragma pack is non-standard.

> And whatever padding might be inserted, the same rules must be in
> effect across all compilers for that platform, otherwise functions in
> modules and in external libraries created with mixed compilers can't
> call each other.

Requirements on alignment and structure layout are typically imposed by
ABIs, not by the C standard.  The standard has some requirements for
struct layout (you can read the relevant section yourself if you're
interested), but those requirements do not include any restrictions on
the size of padding.

> Since I am familiar with duplicating with layout of C structs from
> outside the language, to the extent of also duplicating the algorithms 
> for alignment and padding, this would be an impossible task if
> effectively random padding could be inserted.

ABIs.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web