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

Groups > comp.lang.c > #162231

Re: Padding between char array/VLA in struct?

Show all headers | View raw

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

...

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web