Dinamic array without malloc - Can be done?

[Fernando D. Bozzo]

From the beginning of my course I'm looking a way to define an array with a number of elements based on some other variable which I don't know, but without using the dynamic memory space (with malloc)

May be I have a conceptual error here, but just in case I did prefer to ask.

I want to do something like this:

len = (some calculated length that can vary in every execution);
char myArray[len];


I've tryied this way, but didn't compile. My aim is not needing to free() it later, but that this array get cleared as all other auto variables.


Thanks.-

[BartC]

It should work; did you put the code inside a function? Eg:

int main(void) {
int len=rand()+100;
char myArray[len];

printf("%d\n",(int)sizeof(myArray));

}

The array is allocated on the stack and is deallocated at a matching "}".

(This is a C 'VLA'.)

--
Bartc

[James R. Kuyper]

In C90, all arrays were required to have a length that was an integer
constant expression. In C99, this was changed for arrays with no linkage
and either block scope or function prototype scope, unless they had
static or thread storage duration (6.7.6.2p2). An array whose length is
not a constant, or whose element type does not have a known constant
size, is referred to as a Variable Length Array (VLA) (6.7.6.2p4). In
C2011, support for VLAs was made optional - if they are not supported,
the implementation must pre#define __STDC_NO_VLA__ to a value of 1.

I've just given you a lot of jargon: integer constant expression,
linkage, block scope, function prototype scope, static storage duration,
thread storage duration, known constant size. I did that because I
normally try to be as precise as possible - each of those terms has a
precisely defined meaning in the C standard, which might be
significantly different from what you'd expect from ordinary English
usage. For example, not all constant expressions with integer type
qualify as integer constant expressions.
I don't expect you, as a newbie, to know all of those terms, but I'm not
sure which ones need explaining. If you have any question about any of
those terms, let me know, and I can explain them in more detail.

What this all means is that if the code you give above won't compile,
you're probably either using a C90 compiler, or a C2011 compiler that
has __STDC_NO_VLA__ pre#defined to a value of 1.

[fir]

it is also possible that when you declare big static
array like

char table[200*1024*1024];

some systems (like windows) will only attach physical memory 'on touch' i mean if you will be using only
first 10% of it rest will not really be physically
allocked/consumed
(sadly i dont know the details (best would be to get practical method of checking which pages are allocked
and which adress space is hanging unattached)

[fir]

i should rethink the limits of this method.. do you know them maybe? (many arrays could be used in function body?
each one freely resized? etc)

[fir]

more see probably in msdn (i was reading there like 5 years ago and i dont exactly remember the details - if i will got a time to read there i could do some summary here later)

[Richard Heathfield]

On 15/01/17 16:45, Fernando D. Bozzo wrote:
> From the beginning of my course I'm looking a way to define an array
> with a number of elements based on some other variable which I don't
> know, but without using the dynamic memory space (with malloc)

My preference here would be to use malloc.

Nevertheless, from C99 onwards you can use variable-length arrays.

> len = (some calculated length that can vary in every execution);
> char myArray[len];

That looks like legal C99 to me.

> I've tryied this way, but didn't compile. My aim is not needing to
> free() it later, but that this array get cleared as all other auto
> variables.

Then you may not have a C99 compiler.

Why don't you want to use malloc?

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[fir]

W dniu niedziela, 15 stycznia 2017 18:29:39 UTC+1 użytkownik fir napisał:

note btw by the advantages and disadvantages of this (quite interesting) solution:

- youre sure thet no memory will be moved (ADV)

- youre consuming logical range (DISADV)

- you got no clasic c api to control this (DISADV)

- if you would want controll this not much will
be needed sorta like two functions

attach(char* begin, char* end);
detach(char* begin, char* end);

and if you will have that, the underlying operations
are more lightweight and strict than those below
malloc/ralloc/free (ADV)

[in general for sure i would like to go into that;
yet specially it may allow thinking even more on
underlying paging system and do some cheap tricks ;c)

[fir]

yet probably there could be mentioned that if system
wendors (mean like intel/microsoft) would redefine
paging system it probably could be possible to resize
all arraus freely
(im talking probably coz im not sure if todays paging
hardware is able to do that with not bigger changes
but probably only some small would be needed - im not sure
though)

i mean when today pages are all build in linear common
space tehere would be a need that each array would open
its own 'orthogonal' space and in such adressing like tab[i] i would be adressing (from 0 to end) this orthogonal space named tab

you could have one horisontal ram space and a number of
vertical ones for arrays.. im not sure though if it would bring big convenience or efficiency improvements (maybe some, i dont know, but at least it seem an option to me)

[Fernando D. Bozzo]

El domingo, 15 de enero de 2017, 18:50:39 (UTC+1), Richard Heathfield escribió:
<snip>

> Why don't you want to use malloc?
>

Hi Richard, the reason is just to simplify the garbage collection automatically, and not needing to free() manually at some point. If I could use some mechanism like try/catch then this could not be a problem, but without it it makes more difficult to manage the flow of a program.

May be is the little practice I have until now, but for small arrays (<1MB) could be a good idea.

[Fernando D. Bozzo]

El domingo, 15 de enero de 2017, 17:53:57 (UTC+1), Bart escribió:
<snip>

>
> It should work; did you put the code inside a function? Eg:
>
> int main(void) {
> int len=rand()+100;
> char myArray[len];
>
> printf("%d\n",(int)sizeof(myArray));
>
> }
>
> The array is allocated on the stack and is deallocated at a matching "}".
>
> (This is a C 'VLA'.)
>
> --
> Bartc

Ok, I've re-tested again (last time was 3-4 days ago and I can't remember how exactly I did) and it works:


int len = strlen(argv[1]);
char myArray[len];
printf("myArray: len=%i\n", len);
myArray[0] = 'A';
myArray[1] = '\0';
int len2 = strlen(myArray);
printf("myArray: len2=%i\n", len2);
myArray[0] = 'A';
myArray[1] = 'B';
myArray[2] = 'C';
myArray[3] = '\0';
len2 = strlen(myArray);
printf("myArray: len2=%i\n", len2);


Even I can define an initial length and do whatever I need inside it, like changing the '\0' termination of the string, between the initial limits.

Thanks Bart!

[Fernando D. Bozzo]

Thanks for the highly detailed technical info James. I don't understand all of it now, but surely I will do it more over time.

Last part is very clear. I'm using Ubuntu Linux 64 bits and the clang compiler, and in my recent test it did work ok.

[Fernando D. Bozzo]

El domingo, 15 de enero de 2017, 18:29:39 (UTC+1), fir escribió:
<snip>

> >
> it is also possible that when you declare big static
> array like
>
> char table[200*1024*1024];
>
> some systems (like windows) will only attach physical memory 'on touch' i mean if you will be using only
> first 10% of it rest will not really be physically
> allocked/consumed
> (sadly i dont know the details (best would be to get practical method of checking which pages are allocked
> and which adress space is hanging unattached)

I'm trying to stay between the size of the stack (I think it's 8 MB? on Ubuntu), so I never use large arrays with this VLAs.

[fir]

on windows stack size is contained as a field in binary (in exe file), you may set this size in compiler comandline option

i always forget the details on this as this may vary betwean compiler and maybe also system/os versions

you could probably set bigger than 8 MB (even probably 100
(500?) MB would go and probably os will respect that

[i made only tests on winxp longer time ago it was afair
1 or 2 MB by default but i could set it bigger]

(afaik though stack is in this way special that it has
some trep based resizing system - same or close as in those
big static array case i mentioned above , i mean eben if you set stack to 8 MB only some pages are attached (like say 128 kB) it will only attached on touch (and probably deatachhed if stack pointer gets back - thus im not sure if
frequent resizes will not suffer form this attaching/deattaching penalty [but im not sure as to
this, so treat this info as ;unchecked ;C ]
array

[Jean-Marc Bourguet]

You can change it with ulimit and change the default in
/etc/security/limits.conf.

The true reason for avoiding big stack usage is when you start to do
multi-thread programming. Each thread has its stack and allowing it's
difficult to allocate them if they have to be huge. (BTW, their size is
controlled in another way)

Yours,

--
Jean-Marc

[Richard Heathfield]

On 15/01/17 18:38, Fernando D. Bozzo wrote:
> El domingo, 15 de enero de 2017, 18:50:39 (UTC+1), Richard Heathfield
> escribió: <snip>
>> Why don't you want to use malloc?
>
> Hi Richard, the reason is just to simplify the garbage collection
> automatically, and not needing to free() manually at some point.

Okay. (Personally, I don't find this to be a big deal.)

Since you seem not to have access to VLAs, I'm going to dare to suggest
a non-ISO function: alloca() (or _alloca() under Visual Studio).

This works just like malloc, except that it automagically frees the
memory when the calling function returns, which is what would have
happened anyway with your char arr[len] code, so it would seem to be
exactly what you're asking for.

This is not, however, an ISO C function. If I understand the rules
correctly, I must therefore now hand in my "comp.lang.c - Purist And
Proud Of It" badge for a two-week penalty period.

[Chad]

firs is a wannabe programmer who only stick to MS Windows.

[Barry Schwarz]

Why do you think the garbage collection performed when the VLA is
destroyed is any simpler then the garbage collection performed when
allocated memory is freed? Are you aware that you cannot extend (or
shrink) a VLA while the size of an allocated array can be adjusted by
realloc?

Since the "stack" is usually smaller than the "heap", using a VLA in a
recursive function can lead to problems sooner than using malloc.

I am curious how the choice of allocation method can affect the flow
of your program. Could you give an example. I realize that one
approach calls malloc which is outside your code. But I'm pretty
certain the code generated by the definition of the VLA will do a lot
of processing unrelated to any executable statements you have coded.
It may even call malloc for you.

The frequently cited quote about premature optimization springs
unbidden to mind.

--
Remove del for email

[fir]

you have also alloca function, it allocks area on stack and dont need to be freed, [it is said to be faster than malloc/free in some cases]

i never used it yet though (same as vla) but could eventually try it (it seem to be eventually more general than vla as you could alloca in loop (not sure as to vla made in loop), no resiza and frea though) (not sure if vla allows to change size after creation, probably not so alloca seem to be maybe a bit more raw and maybe general vla)

[Ben Bacarisse]

Richard Heathfield <r...@cpax.org.uk> writes:

> On 15/01/17 16:45, Fernando D. Bozzo wrote:
>> From the beginning of my course I'm looking a way to define an array
>> with a number of elements based on some other variable which I don't
>> know, but without using the dynamic memory space (with malloc)
>
> My preference here would be to use malloc.
>
> Nevertheless, from C99 onwards you can use variable-length arrays.

Maybe. The 'onwards' is in doubt since they are optional in C11. You
may be right in that any compiler that supports them in C99 will
probably do so indefinitely, but that's not quite the same thing.

<snip>
--
Ben.

[Ben Bacarisse]

"Fernando D. Bozzo" <fdb...@gmail.com> writes:

>> On 01/15/2017 11:45 AM, Fernando D. Bozzo wrote:

<snip>

>> > I want to do something like this:
>> >
>> > len = (some calculated length that can vary in every execution);
>> > char myArray[len];

<snip>
> ... I'm using Ubuntu Linux 64 bits and the clang

> compiler, and in my recent test it did work ok.

VLAs almost certainly work then. You need to ask for -std=c99 (or
-std=c11) but if that fails you would have to post the error message.
Something else might be wrong.

--
Ben.

[BartC]

On 15/01/2017 18:42, Fernando D. Bozzo wrote:
> El domingo, 15 de enero de 2017, 17:53:57 (UTC+1), Bart escribió:
> <snip>
>>
>> It should work; did you put the code inside a function? Eg:
>>
>> int main(void) {
>> int len=rand()+100;
>> char myArray[len];
>>
>> printf("%d\n",(int)sizeof(myArray));

> Ok, I've re-tested again (last time was 3-4 days ago and I can't remember how exactly I did) and it works:
>
>
> int len = strlen(argv[1]);
> char myArray[len];
> printf("myArray: len=%i\n", len);

Displaying sizeof(myArray) is more useful confirmation. Otherwise this
line will give a result even if the char myArray line didn't exist.

> myArray[0] = 'A';
> myArray[1] = '\0';

This assumes that len is at least two. And below, that it is a least 4.
But len can be 0 or 1.

> int len2 = strlen(myArray);
> printf("myArray: len2=%i\n", len2);
> myArray[0] = 'A';
> myArray[1] = 'B';
> myArray[2] = 'C';
> myArray[3] = '\0';

--
Bartc

[fir]

wouldnt

add esp, size

just work? (in reality it could be more sub but i say add for simplicity)

[David Brown]

I wonder why C11 made VLA's optional? Does anyone know of a compiler
that supports all or most of C99 /except/ VLA's? There are certainly
compilers that support most of C99 but not complex numbers, or whose
floating point arithmetic is not quite according to IEC 60559. But
VLA's are not at all difficult to support in a compiler, especially if
the compiler already has alloca() or a similar function.

[Keith Thompson]

BartC <b...@freeuk.com> writes:
> On 15/01/2017 18:42, Fernando D. Bozzo wrote:

[...]

>> myArray[0] = 'A';
>> myArray[1] = '\0';
>
> This assumes that len is at least two. And below, that it is a least 4.
> But len can be 0 or 1.

C does not permit array of length 0, though some compilers may support
them as an extension. For a non-VLA, defining a 0-length array is a
constraint violation; for a VLA, it's undefined behavior (which a
compiler might warn about if it has enough information).

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Keith Thompson]

"James R. Kuyper" <james...@verizon.net> writes:
[...]

> What this all means is that if the code you give above won't compile,
> you're probably either using a C90 compiler, or a C2011 compiler that
> has __STDC_NO_VLA__ pre#defined to a value of 1.

Are there any such compilers?

[Keith Thompson]

Richard Heathfield <r...@cpax.org.uk> writes:
[...]

> Since you seem not to have access to VLAs, I'm going to dare to suggest
> a non-ISO function: alloca() (or _alloca() under Visual Studio).

It turns out the OP does have access to VLAs.

> This works just like malloc, except that it automagically frees the
> memory when the calling function returns, which is what would have
> happened anyway with your char arr[len] code, so it would seem to be
> exactly what you're asking for.
>
> This is not, however, an ISO C function. If I understand the rules
> correctly, I must therefore now hand in my "comp.lang.c - Purist And
> Proud Of It" badge for a two-week penalty period.

alloca() is neither ISO C nor POSIX, though it's supported on a lot of
Unix-like systems.

Be aware that if an alloca() call causes stack overflow, the behavior is
undefined. The same is true for defining a VLA. Then again, the same
is true for an old-style constant-length array. If you use a VLA to
avoid allocating more memory than you need for a local array, you
probably haven't introduced any additional risk. If a VLA might be
bigger than a constant-length array would have been, you have no way to
deal with stack overflow.

Another limitation: You can't have an alloca() call in the argument list
for a function call.

[supe...@casperkitty.com]

On Sunday, January 15, 2017 at 2:33:25 PM UTC-6, David Brown wrote:
> I wonder why C11 made VLA's optional? Does anyone know of a compiler
> that supports all or most of C99 /except/ VLA's? There are certainly
> compilers that support most of C99 but not complex numbers, or whose
> floating point arithmetic is not quite according to IEC 60559. But
> VLA's are not at all difficult to support in a compiler, especially if
> the compiler already has alloca() or a similar function.

The Keil/ARM compilers for embedded systems implement VLAs using
malloc/free. Unless the linker has been configured to reserve space
for the heap, however, calls to malloc() will die (freestanding
implementations aren't required to support malloc, and for most
embedded systems no purpose would be served by doing so). Because
the Standard does not specify any cases in which an attempt to
create a VLA cannot invoke UB, such behavior is conforming. On
the other hand, it would be more helpful if implementations that are
not going to use malloc() could instead arrange to have any attempts
to build programs using VLAs fail with compiler or link failures.

[James R. Kuyper]

On 01/15/2017 03:46 PM, Keith Thompson wrote:
> "James R. Kuyper" <james...@verizon.net> writes:
> [...]
>> What this all means is that if the code you give above won't compile,
>> you're probably either using a C90 compiler, or a C2011 compiler that
>> has __STDC_NO_VLA__ pre#defined to a value of 1.
>
> Are there any such compilers?

I presume that you're referring only to the last clause of that sentence
- C90 compilers are ubiquitous.

You should know me by now - I know a lot about what the standard allows
and requires, but I'm not well-informed about which particular compilers
take advantage of those allowances, or fail to meet those requirements.
The only C compiler I know well from recent personal experience is gcc.
It's been six years since I last had access to a machine with the IRIX C
compiler installed, about 20 years since I had access to the Microsoft C
compiler, and 27 years since I had access to the VMS C compiler - those
are the four C compilers I've used most recently.

[supe...@casperkitty.com]

On Sunday, January 15, 2017 at 2:51:04 PM UTC-6, Keith Thompson wrote:
> alloca() is neither ISO C nor POSIX, though it's supported on a lot of
> Unix-like systems.

The alloca() macro/intrinsic/whatever has poorly-defined semantics which
severely limit the situations where it can be used safely. Things would
have been much better if there had been a corresponding freea() intrinsic,
and code was required to freea() blocks in reverse order of allocation,
and before a function returned. Since an implementation could have
achieved the required semantics simply by aliasing alloca() and freea()
to malloc() and free(), though doing so would forego potentially-useful
optimizations]. As it is, alloca() was a hack that was easy to implement
with some compilers, but would require a lot more work to implement
usefully on others.

[James R. Kuyper]

On 01/15/2017 03:33 PM, David Brown wrote:
...

> I wonder why C11 made VLA's optional?

I haven't seen a 2011 version of the C Rationale, so I can't be sure -
but I imagine it's because somebody complained about the difficulty of
supporting VLAs, and the committee decided to accommodate their complaint.
The oldest message I could find using Google Groups that mentions
__STDC_NO_VLA__, was part of a 2010 thread in which Chris Hills said:

> For several years I have been saying that some C99 features would be
> dropped in the next standard and no one believed me. It all stemmed
> from the discussions at the end of the WG14 meeting in April 2007.

During the entire year after April 2007, i found only two threads on
comp.std.c, and four on comp.lang.c, that mentioned VLAs, and none of
those threads mentioned those discussions.

> ... Does anyone know of a compiler
> that supports all or most of C99 /except/ VLA's? ...

During one of the threads I mentioned above, Kenneth Brody said:
> I don't use VLAs, as many [most?] of the compilers I use don't
> support it,

He didn't say whether any of those compilers supported any other C99
features.

[James R. Kuyper]

On 01/15/2017 04:34 PM, James R. Kuyper wrote:
> On 01/15/2017 03:33 PM, David Brown wrote:
> ...
>> I wonder why C11 made VLA's optional?
>
> I haven't seen a 2011 version of the C Rationale, so I can't be sure -
> but I imagine it's because somebody complained about the difficulty of
> supporting VLAs, and the committee decided to accommodate their complaint.
> The oldest message I could find using Google Groups that mentions
> __STDC_NO_VLA__, was part of a 2010 thread in which Chris Hills said:
>
>> For several years I have been saying that some C99 features would be
>> dropped in the next standard and no one believed me. It all stemmed
>> from the discussions at the end of the WG14 meeting in April 2007.
>
> During the entire year after April 2007, i found only two threads on
> comp.std.c, and four on comp.lang.c, that mentioned VLAs, and none of
> those threads mentioned those discussions.

I just found the relevant document:
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1460.htm>

[Siri Cruise]

In article <01610cdf-e6ca-47ac...@googlegroups.com>,

"Fernando D. Bozzo" <fdb...@gmail.com> wrote:

So the first step is to look up your particular compiler's documentation and/or
identify your compiler and version. Some of these things just require some extra
options given to the compiler. I had a similar problem with declarations in for
statements until I learned gcc and lvm require you tell it the language version.

--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.
'I desire mercy, not sacrifice.'
Free the Amos Yee one.
Yeah, too bad about your so-called life. Ha-ha.

[Fernando D. Bozzo]

El domingo, 15 de enero de 2017, 21:13:48 (UTC+1), Ben Bacarisse escribió:

Hi Ben:

It's working beautifuly :)

I'm using -std=c11

Thanks!

[Fernando D. Bozzo]

Hi Bart:

Yes, I know that is not really ok, but just was a quick test to see if works.
At the command line I've make sure that the input have at least 4-5 chars in the parameter.

Thanks.-

[Fernando D. Bozzo]

El domingo, 15 de enero de 2017, 20:22:59 (UTC+1), Jean-Marc Bourguet escribió:

Thanks Jean for the tip.-

[Fernando D. Bozzo]

El domingo, 15 de enero de 2017, 20:53:40 (UTC+1), Barry Schwarz escribió:
> On Sun, 15 Jan 2017 10:38:17 -0800 (PST), "Fernando D. Bozzo"

Hi Barry, of course I can get more detail!

I'm doing a practice on which I have to "fix" a copy of apache 2.2 (http://httpd.apache.org/docs/2.2/mod/core.html) that have some methods taked out, and I must to reprogram them following some directions given in the course (validations and the like).

One of those methods is the "parse" method, that receives the input line that I need to parse, something like:

GET /public/cat.html HTTP/1.1


So the VLAs I'm using are to make some string operations on a copy of this line to get back into parts (command, path, file and Http version)

As you can see, the size of data is small, can't be more than a couple of 100s chars, and that's why I didn't want to use malloc. I reserve the use of dynamic memory for when I really need a big size, but for less than 8 MB I think that is a waste of time and make the modifications a little more complicated than what I need.

I have a long background in OOP which is very useful to understand the most on programming, but I'd never programmed at so low level... and I'm liking it :)

[Chris M. Thomasson]

On 1/15/2017 8:45 AM, Fernando D. Bozzo wrote:
> From the beginning of my course I'm looking a way to define an array with a number of elements based on some other variable which I don't know, but without using the dynamic memory space (with malloc)
>

> May be I have a conceptual error here, but just in case I did prefer to ask.

>
> I want to do something like this:
>
> len = (some calculated length that can vary in every execution);
> char myArray[len];
>
>

> I've tryied this way, but didn't compile. My aim is not needing to free() it later, but that this array get cleared as all other auto variables.
>
>
> Thanks.-

FWIW, here is a little crude example of using a scoped stack based
region allocation scheme for creating a dynamic memory like mimic for a
diverse set of algorithms:

crude hacky (wrt alignment) code:

http://pastebin.com/raw/f37a23918
(pastebin link without ads, notice the raw?)

https://groups.google.com/forum/#!original/comp.lang.c++/7oaJFWKVCTw/sSWYU9BUS_QJ

Hope this can help out a bit. ;^o

[Fernando D. Bozzo]

Hi Chris, I've make it work. VLAs work ok for me now. Don't know how I've tested it some days ago, but I surely did typed or defined something wrong.

Very thanks for your links!

[supe...@casperkitty.com]

On Sunday, January 15, 2017 at 5:32:12 PM UTC-6, Fernando D. Bozzo wrote:
> One of those methods is the "parse" method, that receives the input line that I need to parse, something like:
>
> GET /public/cat.html HTTP/1.1
>
>
> So the VLAs I'm using are to make some string operations on a copy of this line to get back into parts (command, path, file and Http version)
>
> As you can see, the size of data is small, can't be more than a couple of 100s chars, and that's why I didn't want to use malloc. I reserve the use of dynamic memory for when I really need a big size, but for less than 8 MB I think that is a waste of time and make the modifications a little more complicated than what I need.

Unless a function is deeply nested or recursive, there isn't going to be
much difference between allocating objects that may take up to 200 bytes
on the stack, versus allocating exactly 200 bytes, unless the cases where
the nesting is deeper coincide with those where the objects are smaller.
I more common situations, the reverse would be the case (with larger
objects requiring more levels of recursion to process).

Using fixed-sized arrays is almost certainly going to be faster if
adequate stack space exists to handle the maximum sizes, and may well
end up having a lower worst-case stack space requirement as well. On
some systems there may be good usage cases for VLAs, but the minimum
size to make VLA usage really worthwhile on some systems may be larger
than the size to make them blow up on others.

[Keith Thompson]

"James R. Kuyper" <james...@verizon.net> writes:

But it gives no specific information about why VLAs were made
optional, other than saying that complex arithmetic and VLAs were
"Two of the largest additions to C99".

Perhaps it would have made more sense to make VLAs (and perhaps
complex numbers?) optional for freestanding implementations, but
mandatory for hosted implementations. (In C99, all conforming
implementations must support complex numbers, but freestanding
implementations needn't support <complex.h>.) Making threading
and atomics optional strikes me as more reasonable, particularly
since they were first introduced in C11.

Complex numbers are an interesting case. In C99, complex types are
mandatory, but the <complex.h> header is required only for hosted
implementations. That meant that a freestanding implementation must
support the types _Complex float, _Complex double, and _Complex
long double, but without <complex.h> there's no portable way to
specify the value of i.

[Chris M. Thomasson]

Excellent news. :^)

> Don't know how I've tested it some days ago, but I surely did typed or defined something wrong.

Well, shi% happens.

> Very thanks for your links!

No problem. FWIW, the region allocator can derive space for different
sized objects. It should be able to be converted into a more standard
form wrt max_align_t, alignas, alignof, c11... ;^)

[Keith Thompson]

The whole point of alloca() is that you don't have to deallocate the
memory. Requiring freea() calls in a particular order would defeat that
purpose. What happens if a program doesn't call freea()?

[Keith Thompson]

"Fernando D. Bozzo" <fdb...@gmail.com> writes:

[...]

> I'm doing a practice on which I have to "fix" a copy of apache 2.2 (http://httpd.apache.org/docs/2.2/mod/core.html) that have some methods taked out, and I must to reprogram them following some directions given in the course (validations and the like).

[...]

Please limit your lines to less than 80 columns, preferably less than
72, by inserting hard line breaks if necessary. It makes your text
easier to read. I see you're using Google Groups, but many newsreaders
either don't wrap long lines, or wrap them but not necessarily on word
boundaries.

[BartC]

On 15/01/2017 23:32, Fernando D. Bozzo wrote:

> I'm doing a practice on which I have to "fix" a copy of apache 2.2 (http://httpd.apache.org/docs/2.2/mod/core.html) that have some methods taked out, and I must to reprogram them following some directions given in the course (validations and the like).
>
> One of those methods is the "parse" method, that receives the input line that I need to parse, something like:
>
> GET /public/cat.html HTTP/1.1
>
>
> So the VLAs I'm using are to make some string operations on a copy of this line to get back into parts (command, path, file and Http version)
>
> As you can see, the size of data is small, can't be more than a couple of 100s chars, and that's why I didn't want to use malloc. I reserve the use of dynamic memory for when I really need a big size, but for less than 8 MB I think that is a waste of time and make the modifications a little more complicated than what I need.

It's no longer clear whether you need what is normally called a dynamic
array. The array declared here:

void fn (void){
char buffer[1000];
}

has a fixed size but is dynamic in that the 1000 bytes aren't allocated
until the function is called.

As supercat said, you might be able to get away with just allocating a
buffer with a fixed upper limit. Then you don't need to get involved
with VLAs. But you will need to check you don't exceed the limit that is
set.

With input line handling, there is always the possibility that people
may type in very long lines, or more likely they could redirect input to
come from a file, perhaps a binary file, that could give 100M bytes of
input without a line break.

In that case, a VLA that can adapt /might/ be better, but if the stack
size is 8MB, and the line that is submitted is more 8M characters, that
can cause a crash. And it's difficult to test for that before the VLA is
declared, as there is no easy way of finding out how much stack is left.

Here malloc would be better as, first, it can have access to GB of data,
and second you can check for an error return.

But for processing short lines like your example, a safer way is to use
a fixed-size array, or to use a VLA but first check the length is
unlikely to cause a problem. However, if there is only 512 bytes of
stack left, and your limit is 1024 bytes, both will crash!

--
Bartc

[supe...@casperkitty.com]

On Sunday, January 15, 2017 at 6:22:07 PM UTC-6, Keith Thompson wrote:
> The whole point of alloca() is that you don't have to deallocate the
> memory. Requiring freea() calls in a particular order would defeat that
> purpose. What happens if a program doesn't call freea()?

That's a pretty useless advantage compared with the speed boost on
some implementations compared with malloc/free.

Implementations may promise to automatically release the storage, and
it would be helpful to have a standard macro to indicate that promise,
but code which balanced calls to alloca() and freea() could be more
easily adapted to existing implementations than code which required
the compiler to perform an automatic freeing operation.

Absent a promise, returning from a function without freeing the storage
would invoke UB.

The semantics of setjmp/longjmp would be a bit more complicated, but
could be resolved cleanly with a marka/rewinda pair with the semantics
that marka would return an opaque object, and invoking rewinda upon that
object would deallocate everything that was alloca'ed since it was marked.
An implementation could promise that setjmp/longjmp would automatically
free up anything that had been alloca'ed but for implementations that did
not do so code would have to either limit use of alloca between setjmp
and longjmp, or else bracket the call and "return through" setjmp with
calls to marka and rewinda. While it would be desirable to have
implementations take care of that automatically, some implementations may
not be able to do so without breaking ABI compatibility with other code
using setjmp/longjmp.

[Tim Rentsch]

Keith Thompson <ks...@mib.org> writes:

> In C99, complex types are mandatory, but the <complex.h> header
> is required only for hosted implementations. That meant that a
> freestanding implementation must support the types _Complex
> float, _Complex double, and _Complex long double, but without
> <complex.h> there's no portable way to specify the value of i.

What isn't portable about this?

typedef _Complex float Zfloat;

Zfloat
imaginary_unit(){
return (union {float f[2]; Zfloat z;}){ {0,1} }.z;
}

[Tim Rentsch]

supe...@casperkitty.com writes:

> [...]

> the Standard does not specify any cases in which an attempt to

> create a VLA cannot invoke UB, [...]

Evaluating a declaration that includes a VLA declarator (with a
positive extent) is no more or less undefined behavior than
calling a function or entering a block that declares automatic
variables.

[Tim Rentsch]

Keith Thompson <ks...@mib.org> writes:

> Richard Heathfield <r...@cpax.org.uk> writes:
> [...]
>> Since you seem not to have access to VLAs, I'm going to dare to suggest
>> a non-ISO function: alloca() (or _alloca() under Visual Studio).
>
> It turns out the OP does have access to VLAs.
>
>> This works just like malloc, except that it automagically frees the
>> memory when the calling function returns, which is what would have
>> happened anyway with your char arr[len] code, so it would seem to be
>> exactly what you're asking for.
>>
>> This is not, however, an ISO C function. If I understand the rules
>> correctly, I must therefore now hand in my "comp.lang.c - Purist And
>> Proud Of It" badge for a two-week penalty period.
>
> alloca() is neither ISO C nor POSIX, though it's supported on a lot of
> Unix-like systems.
>
> Be aware that if an alloca() call causes stack overflow, the behavior is

> undefined. [...]

Isn't any call to alloca() undefined behavior, in the sense that
the Standard uses the term, no matter how much (or how little)
memory is asked for?

[Tim Rentsch]

Keith Thompson <ks...@mib.org> writes:

> "James R. Kuyper" <james...@verizon.net> writes:
> [...]
>> What this all means is that if the code you give above won't compile,
>> you're probably either using a C90 compiler, or a C2011 compiler that
>> has __STDC_NO_VLA__ pre#defined to a value of 1.
>
> Are there any such compilers?

A C11 implementation that supports VLA's could provide a compiler
option that would disable them and define __STDC_NO_VLA__ to 1.
Such an option might even be useful, to check a non-VLA version
of C11 code, or to comply with an external requirement that VLA's
not be used.

[Keith Thompson]

OK, no *clean* portable way.

[Keith Thompson]

Yes, but that doesn't answer my question.

[David Brown]

On 16/01/17 05:37, Tim Rentsch wrote:
> Keith Thompson <ks...@mib.org> writes:
>
>> "James R. Kuyper" <james...@verizon.net> writes:
>> [...]
>>> What this all means is that if the code you give above won't compile,
>>> you're probably either using a C90 compiler, or a C2011 compiler that
>>> has __STDC_NO_VLA__ pre#defined to a value of 1.
>>
>> Are there any such compilers?
>
> A C11 implementation that supports VLA's could provide a compiler
> option that would disable them and define __STDC_NO_VLA__ to 1.

As a sample point, gcc can effectively disable VLA's with "-Werror=vla".
But it does not define __STDC_NO_VLA__.

> Such an option might even be useful, to check a non-VLA version
> of C11 code, or to comply with an external requirement that VLA's
> not be used.
>

I am at a loss to imagine a case where it would be useful to have a
non-VLA version of C11 code, unless there really exist compilers that
support C11 except VLA's. Otherwise, apparently the only use of the
"feature" of __STDC_NO_VLA__ is to test code when that "feature" is present!

[Ian Collins]

On 01/16/17 09:05 PM, David Brown wrote:
>
> I am at a loss to imagine a case where it would be useful to have a
> non-VLA version of C11 code, unless there really exist compilers that
> support C11 except VLA's. Otherwise, apparently the only use of the
> "feature" of __STDC_NO_VLA__ is to test code when that "feature" is present!

I would cite embedded code where one has to be able to determine stack
use through static analysis. Or were you thinking of two versions of
the same code, one with and one without VLAs?

--
Ian

[Fernando D. Bozzo]

El lunes, 16 de enero de 2017, 1:57:29 (UTC+1), Keith Thompson escribió:

> "Fernando D. Bozzo" writes:
> [...]
> > I'm doing a practice on which I have to "fix" a copy of apache 2.2 (http://httpd.apache.org/docs/2.2/mod/core.html) that have some methods taked out, and I must to reprogram them following some directions given in the course (validations and the like).
> [...]
>
> Please limit your lines to less than 80 columns, preferably less than
> 72, by inserting hard line breaks if necessary. It makes your text
> easier to read. I see you're using Google Groups, but many newsreaders
> either don't wrap long lines, or wrap them but not necessarily on word
> boundaries.
>

Hi Keith:

I will try to format manually, sorry. And yes, I'm using Google Groups

[David Brown]

Certainly one might want to avoid VLA's in embedded code - or anywhere
else where you are trying to limit or analyse stack usage. Compiler
flags to warn on VLA's, or large stack frames, can be useful there.

But Tim was, I believe, talking about code such as:

#ifndef __STDC_NO_VLA__
// Code using VLA's
#else
// Code using malloc, alloca, or something else
#endif


I am wondering where you would use such code.

I can understand using somewhat more refined tests, perhaps based on
what you know of the limits to the sizes of the array:

#ifdef USE_VLA_FOR_THIS_BIT_OF_CODE
// Code using VLA's
#else
// Code using malloc, alloca, or something else
#endif


And certainly run-time choices might make sense:

if (size < limit) {
// Code using VLA's
} else {
// Code using malloc, alloca, or something else
}


However, if no real-world compilers actually fail to support VLAs, and
therefore none define __STDC_NO_VLA__ normally, then code with
conditional compilation based on that symbol is not going to be useful.

[David Brown]

On 15/01/17 22:10, supe...@casperkitty.com wrote:

> On Sunday, January 15, 2017 at 2:51:04 PM UTC-6, Keith Thompson wrote:
>> alloca() is neither ISO C nor POSIX, though it's supported on a lot of
>> Unix-like systems.
>

> The alloca() macro/intrinsic/whatever has poorly-defined semantics which
> severely limit the situations where it can be used safely. Things would
> have been much better if there had been a corresponding freea() intrinsic,
> and code was required to freea() blocks in reverse order of allocation,
> and before a function returned. Since an implementation could have
> achieved the required semantics simply by aliasing alloca() and freea()
> to malloc() and free(), though doing so would forego potentially-useful
> optimizations]. As it is, alloca() was a hack that was easy to implement
> with some compilers, but would require a lot more work to implement
> usefully on others.
>

alloca (and VLAs) has three key advantages over malloc. First, it is
fast. Secondly, it is as space-efficient as possible. Thirdly, you
don't need to deallocate it - it is automatically deallocated at the end
of the block. A key /disadvantage/ is that you don't have the
flexibility to re-order your allocations and deallocations - this is
strictly stack ordering.

By having a "freea()" function, you would lose the benefit of automatic
deallocation. And unless your freea() function were to be completely
useless, you would need to deal with varied orders of alloca() and
freea(). That means tracking allocations - leading to ram space and
time overhead, as well as code space, not unlike malloc().

Basically, your idea would completely spoil the whole point of alloca()
and give you something not much faster than malloc(), while being far
less flexible.

[David Brown]

On 15/01/17 21:51, Keith Thompson wrote:
> Richard Heathfield <r...@cpax.org.uk> writes:
> [...]
>> Since you seem not to have access to VLAs, I'm going to dare to suggest
>> a non-ISO function: alloca() (or _alloca() under Visual Studio).
>
> It turns out the OP does have access to VLAs.
>
>> This works just like malloc, except that it automagically frees the
>> memory when the calling function returns, which is what would have
>> happened anyway with your char arr[len] code, so it would seem to be
>> exactly what you're asking for.
>>
>> This is not, however, an ISO C function. If I understand the rules
>> correctly, I must therefore now hand in my "comp.lang.c - Purist And
>> Proud Of It" badge for a two-week penalty period.
>

> alloca() is neither ISO C nor POSIX, though it's supported on a lot of
> Unix-like systems.
>

> Be aware that if an alloca() call causes stack overflow, the behavior is

> undefined. The same is true for defining a VLA. Then again, the same
> is true for an old-style constant-length array. If you use a VLA to
> avoid allocating more memory than you need for a local array, you
> probably haven't introduced any additional risk. If a VLA might be
> bigger than a constant-length array would have been, you have no way to
> deal with stack overflow.

Stack overflow can occur in many ways - local arrays (VLA or constant
size) is perhaps a common one, but uncontrolled recursion is probably
high on the list. You can also get a stack overflow with just one
function call too many, or one local variable too many - that may be
rare on big machines, but it does happen in small embedded systems. And
stack overflow behaviour is undefined in the C standards, and even if
you have an OS or hardware that defines the behaviour, the definition is
usually "something bad happens" !

IMHO, alloca and VLA are no worse than many other things in C - you
simply have to know what you are doing and be sure you are doing things
properly, such as checking the size before allocation.

>
> Another limitation: You can't have an alloca() call in the argument list
> for a function call.
>

That makes it different from (most) other functions, but I doubt if it
is going to be an issue in practice. Alloca is certainly a somewhat
special function.

[David Brown]

On 15/01/17 20:53, Barry Schwarz wrote:
> On Sun, 15 Jan 2017 10:38:17 -0800 (PST), "Fernando D. Bozzo"
> <fdb...@gmail.com> wrote:
>
>> El domingo, 15 de enero de 2017, 18:50:39 (UTC+1), Richard
>> Heathfield escribió: <snip>
>>> Why don't you want to use malloc?
>>>
>>
>>
>> Hi Richard, the reason is just to simplify the garbage collection
>> automatically, and not needing to free() manually at some point. If
>> I could use some mechanism like try/catch then this could not be a
>> problem, but without it it makes more difficult to manage the flow
>> of a program.
>>
>> May be is the little practice I have until now, but for small
>> arrays (<1MB) could be a good idea.
>
> Why do you think the garbage collection performed when the VLA is
> destroyed is any simpler then the garbage collection performed when
> allocated memory is freed?

Perhaps he thinks it is the case, because it is true? It is easier for
the programmer - you just end the block, rather than having to free the
pointer. It is more efficient at run-time in the code - allocation is
typically just adding/subtracting a size value to the stack pointer, and
deallocation is reversing that operation (if it is needed at all - often
that will be combined with the rest of the function epilogue).

> Are you aware that you cannot extend (or
> shrink) a VLA while the size of an allocated array can be adjusted
> by realloc?

I am sure he is aware that a VLA is not the same thing as using malloc.

>
> Since the "stack" is usually smaller than the "heap", using a VLA in
> a recursive function can lead to problems sooner than using malloc.
>
> I am curious how the choice of allocation method can affect the flow
> of your program. Could you give an example. I realize that one
> approach calls malloc which is outside your code. But I'm pretty
> certain the code generated by the definition of the VLA will do a
> lot of processing unrelated to any executable statements you have
> coded. It may even call malloc for you.

It is highly unlikely that using a VLA will call malloc. (It is not
impossible - someone mentioned that this is done on some 8051 compilers.
But there we are talking about very limited processors with no decent
data stack support.)

>
> The frequently cited quote about premature optimization springs
> unbidden to mind.
>

I wonder if you know what VLA's actually are.

[David Brown]

That is simply nonsense.

It is rare that Fir posts anything the makes sense, but in this thread
he actually did so - allocating a local array on the stack is basically
nothing more than an adjustment of the stack pointer. It does not
matter significantly whether that adjustment is of a fixed size known at
compile time, or a value calculated at run-time.

[David Brown]

On 16/01/17 09:37, Fernando D. Bozzo wrote:
> El lunes, 16 de enero de 2017, 1:57:29 (UTC+1), Keith Thompson
> escribió:

>> Please limit your lines to less than 80 columns, preferably less
>> than 72, by inserting hard line breaks if necessary. It makes your
>> text easier to read. I see you're using Google Groups, but many
>> newsreaders either don't wrap long lines, or wrap them but not
>> necessarily on word boundaries.
>>
>
>
> Hi Keith:
>
> I will try to format manually, sorry. And yes, I'm using Google
> Groups
>

Google groups is useful if you need to search the history of groups, or
very occasionally visit a group. But if you are using Usenet regularly,
you really should get a proper newsreader and a proper news account.
There are many possibilities here, and a discussion is way off-topic for
the group. But one popular combination that is completely free and
works on any system is Thunderbird for the newsreader, and
news.eternal-september.org as the newsserver. Once you try these, you
will never want to touch Google Groups again, and other people reading
your posts will be happier.

[Fernando D. Bozzo]

Hi David:

I use Google Groups a lot, because I'm
in many groups, and I prefer mobility.
I use them at home, at work and even
when taking the bus or train on the
mobile or tablet.

[Alla _]

On Sunday, January 15, 2017 at 7:45:57 PM UTC+3, Fernando D. Bozzo wrote:
> From the beginning of my course I'm looking a way to define an array with a number of elements based on some other variable which I don't know, but without using the dynamic memory space (with malloc)

<snip>
Could you, please, share what course are you taking?

[Fernando D. Bozzo]

Yeah, sure: CS50, at edX ;-)

[Alla _]

On Monday, January 16, 2017 at 12:50:39 PM UTC+3, Fernando D. Bozzo wrote:
> Yeah, sure: CS50, at edX ;-)

Oh ) I sensed it could be the one ) How did you find this group? )
I am now doing my final project, and I have chosen to do it in C.
Beware - some people here don't think it's a good course )

[Fernando D. Bozzo]

Well, I use a lot of groups on Google Groups, so I just searched for
C-related ones and found just this one with activity, and found to on the web that this is a legendary one with great people, so I get in.

I don't care what others think about this course, and given what I'd read
about it before taking it, and the link you provided
(https://paw.princeton.edu/article/computer-languages-clarity-key) makes
clear that it's a course not focused on the higher skills devs, but on the
ones that are new to C and Computer Science.

A course on which the same Davin Malan, ex-student of legendary Kernighan,
is one of the Professors, can't be bad, and more given the special interest
that this people put in teaching in a way very close to the students.

I'm really enjoying it, and I'm in week 7 with the practice on the apache
server "fix", which I've almost done :)

Don't know yet about what will be my final project, but thinking on it :/

[BartC]

But the adjustment isn't done at entry to a function with all the other
fixed-size objects (or not at all if a conventional stack frame is not
used).

It's done separately after executing some code (calculating the length
of the array). If it's in a loop, it can mean deallocating the space,
and then allocating a new offset, each time around.

Furthermore, on some implementations such as gcc on x86, it can mean
calling a function (__chkstk_ms()) to check the allocation isn't so
large that it exceeds the stack guard page. This is not needed if it
knows the local array will not be a beyond a certain size (I think 4KB
or less total stack allocation within a function).

--
Bartc

[Richard Heathfield]

I have a bad feeling about this...

Alla, do you not realise that there seem to be quite a few people here
in clc who are impatiently awaiting the time when you stop doing C
courses, so that they can get on with teaching you C?

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[Alla _]

Yes, it is the best course ever, especially because of all those people working
on it - David, Rob, and others; truly outstanding staff, exceptional learning
experience, and what's very important these guys do care about every single
student, and there are tens of thousands of us taking the course, if not hundreds
already. I was also amazed to read the article I have posted here. A lot can be
said on all this, but I do feel we are very lucky to have an opportunity to take
the course.
Also thanks to this course I have found this group - a gold mine of exceptional
professionals. So, please, don't say you don't care - heed to every word people
tell you here; if they do say something, they know what they are saying; even if you hear
something not pleasant (though I don't think you will), it's nothing compared to
being able to get advices from fellows here; it just all depends
on a personal character, but we are all different and that's good )))
I believe you have some prior experience in CS. I was minus 100%, knew nothing
at all.
As to final projects, people tend to do something amazing - apps, games, etc.
I have decided to opt out of this, and do something more practical in terms of
getting a deeper knowledge of C because I love the language.
As to apache, I have huge problems now with my local one. Can't figure out why
it doesn't work. But I better stop discussing these issues here, these are not
C related, and I will be fairly chastised for doing so.
Happy you have found this group. Good luck with the course )

[Alla _]

On Monday, January 16, 2017 at 2:36:50 PM UTC+3, Richard Heathfield wrote:
> On 16/01/17 09:47, Alla _ wrote:
> > On Sunday, January 15, 2017 at 7:45:57 PM UTC+3, Fernando D. Bozzo wrote:
> >> From the beginning of my course I'm looking a way to define an array with a number of elements based on some other variable which I don't know, but without using the dynamic memory space (with malloc)
> > <snip>
> > Could you, please, share what course are you taking?
>
> I have a bad feeling about this...
>
> Alla, do you not realise that there seem to be quite a few people here
> in clc who are impatiently awaiting the time when you stop doing C
> courses, so that they can get on with teaching you C?
>

Richard, I don't do any more courses, truly. It's still that same one,
but I am done with course itself; I am writing (very very slowly) the final
project, and as you see I have chosen the C one, and do it step by step
learning good habits. I am doing my best.
I have asked Fernando only because I was somehow sure it's this
course, so I was curious. I am truly not seeking for any courses. Please,
believe me.

[Fernando D. Bozzo]

El lunes, 16 de enero de 2017, 12:40:57 (UTC+1), Alla _ escribió:
> [...] So, please, don't say you don't care - heed to every word people
> tell you here [...]

I think you did misinterpret what I said:
> I don't care what others think about this course [...]

It only applies to this in particular, not to everything else!

I really appreciate all the guidance found here, and take seriously all
the suggestions and comments.

--

[Alla _]

Just out of curiosity - you can skip this if you don't want to reply. Why are
you now learning about C if you are at pset7? By this time you are done with
C based on course's material.

[Fernando D. Bozzo]

Because it's not enough with the course
materials, and I like to read info on
more sites, know the history behind and
ask the questions I can't found clear
enough.
Odds are asking on Stackoverflow and here.

[David Brown]

On 16/01/17 12:28, BartC wrote:
> On 16/01/2017 09:19, David Brown wrote:
>> On 16/01/17 01:01, supe...@casperkitty.com wrote:
>
>>> Using fixed-sized arrays is almost certainly going to be faster if
>>> adequate stack space exists to handle the maximum sizes, and may
>>> well end up having a lower worst-case stack space requirement as
>>> well. On some systems there may be good usage cases for VLAs, but
>>> the minimum size to make VLA usage really worthwhile on some systems
>>> may be larger than the size to make them blow up on others.
>>>
>>
>> That is simply nonsense.
>>
>> It is rare that Fir posts anything the makes sense, but in this thread
>> he actually did so - allocating a local array on the stack is basically
>> nothing more than an adjustment of the stack pointer. It does not
>> matter significantly whether that adjustment is of a fixed size known at
>> compile time, or a value calculated at run-time.
>
> But the adjustment isn't done at entry to a function with all the other
> fixed-size objects (or not at all if a conventional stack frame is not
> used).

Why do you think adjustment is done at entry to a function for
fixed-size objects? Adjustment /may/ be done on entry, but it may be
done later. For some targets, adjustment may be done as needed while
storing something on the stack (a "push" instruction). If a function
has an "early exit" path as an alternative to another path that uses
more of a stack frame, then it might well postpone the allocation until
it was needed. Modern compilers with inter-procedural optimisations
have long since lost the neat divisions of object-code "functions"
matching source-code functions. There are many possibilities beyond the
simple case of "allocate everything at function entry".

And no matter where the stack adjustment is made, it is /still/ no more
than an instruction or two.

>
> It's done separately after executing some code (calculating the length
> of the array). If it's in a loop, it can mean deallocating the space,
> and then allocating a new offset, each time around.

It could mean that, yes - though you would not normally allocated and
deallocate memory inside a fast loop. But again, you are just adding or
subtracting a value to the stack pointer - a "call" to alloca or a
creation of a VLA is an extremely cheap operation.

>
> Furthermore, on some implementations such as gcc on x86, it can mean
> calling a function (__chkstk_ms()) to check the allocation isn't so
> large that it exceeds the stack guard page. This is not needed if it
> knows the local array will not be a beyond a certain size (I think 4KB
> or less total stack allocation within a function).
>

You mean "gcc on windows", not "gcc on x86".

Yes, it is possible that __chkstk_ms() might be called more times than
necessary with a VLA than it would with fixed-size allocations, because
the compiler may not know an upper bound on the size for the VLA. It is
unlikely to be a big issue, because __chkstk_ms() is a fast function on
average. And of course you can usually tell the compiler about the
limits for the VLA sizes (which you should know, to use them safely).

[Ben Bacarisse]

Richard Heathfield <r...@cpax.org.uk> writes:
<snip>

> Alla, do you not realise that there seem to be quite a few people here
> in clc who are impatiently awaiting the time when you stop doing C
> courses, so that they can get on with teaching you C?

I don't think Alla_ is taking any C courses.

--
Ben.

[BartC]

On 16/01/2017 13:29, David Brown wrote:

> On 16/01/17 12:28, BartC wrote:

>> But the adjustment isn't done at entry to a function with all the other
>> fixed-size objects (or not at all if a conventional stack frame is not
>> used).
>
> Why do you think adjustment is done at entry to a function for
> fixed-size objects? Adjustment /may/ be done on entry, but it may be
> done later.

If that is a lot of code that has to be executed before the VLA size is
determined, then it is reasonable to assume that any allocations for the
local variables are involved are done separately. Whether the earlier
allocations are done at the actual function entry point or not, or are
not done at all, is just nit-picking on your part.

>> Furthermore, on some implementations such as gcc on x86, it can mean
>> calling a function (__chkstk_ms()) to check the allocation isn't so
>> large that it exceeds the stack guard page. This is not needed if it
>> knows the local array will not be a beyond a certain size (I think 4KB
>> or less total stack allocation within a function).
>>
>
> You mean "gcc on windows", not "gcc on x86".

Why wouldn't gcc not on Windows not use such a function? And why doesn't
gcc use the same fast method on Windows?

(As I understand it, it allows Windows programs to commit a large stack
size without needing to allocate the memory until needed. There is
already a mechanism to grow the stack automatically if it increases by
small increments, but not if it skips one or more VM pages. So how does
gcc on Linux for example manage it? Or does it have to allocate the
maximum stack size right from the start?)

> Yes, it is possible that __chkstk_ms() might be called more times than
> necessary with a VLA than it would with fixed-size allocations, because
> the compiler may not know an upper bound on the size for the VLA. It is
> unlikely to be a big issue, because __chkstk_ms() is a fast function on
> average.

Nevertheless, it is an extra function call.

I create one benchmark which ran twice as fast with a fixed size array
as using a VLA of the same size (I knew it was the same; the compiler
didn't). On Linux however which apparently doesn't use chkstk, it was
only 10% faster.

> And of course you can usually tell the compiler about the
> limits for the VLA sizes (which you should know, to use them safely).

You can't use them safely if you don't know what recursion depth is
likely. BTW what does the compiler actually check the VLA size against
the limits at runtime? If so this is no longer one or two instructions.

--
Bartc

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 7:29:34 AM UTC-6, David Brown wrote:
> Why do you think adjustment is done at entry to a function for
> fixed-size objects? Adjustment /may/ be done on entry, but it may be
> done later. For some targets, adjustment may be done as needed while
> storing something on the stack (a "push" instruction). If a function
> has an "early exit" path as an alternative to another path that uses
> more of a stack frame, then it might well postpone the allocation until
> it was needed. Modern compilers with inter-procedural optimisations
> have long since lost the neat divisions of object-code "functions"
> matching source-code functions. There are many possibilities beyond the
> simple case of "allocate everything at function entry".

On most platforms, allocating everything at function entry will be a
reasonably efficient approach that will be usable in all cases that don't
involve VLAs. Other approaches may not be usable in all cases, but may be
more efficient in those cases where they are usable.

In the absence of variable length arrays, the worst-case cost for allocating
local variables would on many platforms be one instructions on entry and one
on exit if a frame pointer is not used, or three on entry and two on exit if
a frame pointer is used. These costs are generally independent of the number
of variables to be allocated or their lifetimes. While implementations may
create variables with shorter lifetimes in cases where that would improve
efficiency, they generally avoid doing anything that would be less efficient
than allocating space for all variables at function entry and cleaning them
all up at function exit.

In cases where a frame pointer would be needed with or without a VLA, the
cost of a block with a VLA might be as low as two instructions on entry and
one on exit, but in the more typical cases where a frame pointer wouldn't
be needed in the absence of a VLA, maintaining the frame pointer will cost
an extra two instructions on entry and one on exit.

As for telling the compiler about size limits for the VLA, how would one be
expected to go about that?

[Richard Heathfield]

That's a blessing. :-)

Courses, then, C or otherwise. I mean, of course, the kinds of courses
that are driving Alla's C studies faster than is good for her.

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 3:09:03 AM UTC-6, David Brown wrote:
> It is highly unlikely that using a VLA will call malloc. (It is not
> impossible - someone mentioned that this is done on some 8051 compilers.
> But there we are talking about very limited processors with no decent
> data stack support.)

It is also done on current Keil compilers for the ARM (which is hadly what
I would call a "very limited processor with no decent data stack support").
Whether that is better or worse than trying to allocate the arrays on the
stack would depend upon usage patterns, though the design does mean that a
request to allocate more space than is available is more likely to result
in a hard fault than in arbitrary data corruption. Neither failure is good,
of course, but in an embedded system the former is often much preferable to
the latter.

[David Brown]

On 16/01/17 16:41, BartC wrote:
> On 16/01/2017 13:29, David Brown wrote:
>> On 16/01/17 12:28, BartC wrote:
>
>>> But the adjustment isn't done at entry to a function with all the other
>>> fixed-size objects (or not at all if a conventional stack frame is not
>>> used).
>>
>> Why do you think adjustment is done at entry to a function for
>> fixed-size objects? Adjustment /may/ be done on entry, but it may be
>> done later.
>
> If that is a lot of code that has to be executed before the VLA size is
> determined, then it is reasonable to assume that any allocations for the
> local variables are involved are done separately. Whether the earlier
> allocations are done at the actual function entry point or not, or are
> not done at all, is just nit-picking on your part.

/All/ considerations about when the allocation is done are nit-picking
with regard to the time spent (late allocation can be a good thing in
saving stack space overall). The actual allocation on the stack is
pretty much "free", whether it is a VLA or a constant size allocation.

>
>>> Furthermore, on some implementations such as gcc on x86, it can mean
>>> calling a function (__chkstk_ms()) to check the allocation isn't so
>>> large that it exceeds the stack guard page. This is not needed if it
>>> knows the local array will not be a beyond a certain size (I think 4KB
>>> or less total stack allocation within a function).
>>>
>>
>> You mean "gcc on windows", not "gcc on x86".
>
> Why wouldn't gcc not on Windows not use such a function? And why doesn't
> gcc use the same fast method on Windows?

The function is only needed on Windows, where you only have a single
spare 4 KB or 8 KB virtual page beyond the current stack. On Linux, you
have (by default) 8 MB virtual memory for the stack - it's all available
(modulo memory over-commit issues) for use when you want it. In both
Linux and Windows you need to ask for a bigger stack if you want to
exceed the default limits (1 MB on Windows, 8 MB on Linux).

The clue here is in the name - __chkstk_ms - "check stack Microsoft".

>
> (As I understand it, it allows Windows programs to commit a large stack
> size without needing to allocate the memory until needed. There is
> already a mechanism to grow the stack automatically if it increases by
> small increments, but not if it skips one or more VM pages. So how does
> gcc on Linux for example manage it? Or does it have to allocate the
> maximum stack size right from the start?)

On Windows, the system only allocates a single /virtual/ page beyond the
current stack end. That gets a physical page when it is touched, and
another virtual page is allocated (up to a limit which I believe is 1 MB
on Windows - I guess a program can change that if it wants to). If a
program tries to touch a stack page more than the next page down without
forcing the physical allocation for the pages along the way, you get a
fault.

On Linux, the system allocates 8 MB virtual space for the stack straight
away. Physical pages are mapped whenever a virtual page is touched.

The Linux method is more efficient and saves having an equivalent of
__chkstk_ms calls, but it relies on overcommit to avoid wasting real memory.

>
>> Yes, it is possible that __chkstk_ms() might be called more times than
>> necessary with a VLA than it would with fixed-size allocations, because
>> the compiler may not know an upper bound on the size for the VLA. It is
>> unlikely to be a big issue, because __chkstk_ms() is a fast function on
>> average.
>
> Nevertheless, it is an extra function call.

Yes, unless it can be inlined (it doesn't do much - just touches memory
every 4K or 8K until the the target size has been reached) and may not
be needed if the compiler knows a limit on the allocation size.

>
> I create one benchmark which ran twice as fast with a fixed size array
> as using a VLA of the same size (I knew it was the same; the compiler
> didn't). On Linux however which apparently doesn't use chkstk, it was
> only 10% faster.

Without any more information, it is hard to guess the details here.

>
>> And of course you can usually tell the compiler about the
>> limits for the VLA sizes (which you should know, to use them safely).
>
> You can't use them safely if you don't know what recursion depth is
> likely.

You can't use /any/ recursion safely unless you know the recursion
depth. You can't use /any/ function calls, or any local variables,
safely unless you know you are not going to exceed the stack limits.
VLAs are no different from fixed size allocations here, except that you
might need to think a little more to be sure of your limits for VLAs.

> BTW what does the compiler actually check the VLA size against
> the limits at runtime? If so this is no longer one or two instructions.
>

If a compiler implements stack size checking, then it probably does. If
the compiler does not implement stack size checking, then it will not
check the size of VLAs.

gcc has a number of flags that can be used for tracing stack usage at
compile time or run time, if that is what you mean by "the" compiler.

[David Brown]

The reason a compiler might not allocate all of a function's possible
frame at the start is that different paths through the function may have
different stack usage. If the function calls other functions, it is a
good thing if it avoids wasting stack space before making the next call.
For small stack frames, this usually does not matter - for big frames,
it can be relevant and it is worth spending a few more instructions to
reduce the overall stack usage.

>
> In cases where a frame pointer would be needed with or without a VLA, the
> cost of a block with a VLA might be as low as two instructions on entry and
> one on exit, but in the more typical cases where a frame pointer wouldn't
> be needed in the absence of a VLA, maintaining the frame pointer will cost
> an extra two instructions on entry and one on exit.
>
> As for telling the compiler about size limits for the VLA, how would one be
> expected to go about that?
>

if (n >= 200) __builtin_unreachable();
char a[n];

or

if (n >= 200) return 0;
char a[n];

or

if (n >= 200) n = 200;
char a[n];

or

if (n >= 200) exit(1);
char a[n];

Take your pick.

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 2:56:27 AM UTC-6, David Brown wrote:
> alloca (and VLAs) has three key advantages over malloc. First, it is
> fast. Secondly, it is as space-efficient as possible. Thirdly, you
> don't need to deallocate it - it is automatically deallocated at the end
> of the block. A key /disadvantage/ is that you don't have the
> flexibility to re-order your allocations and deallocations - this is
> strictly stack ordering.

A bigger disadvantage is that it is unusable even in many cases where stack
ordering would be fine. If a loop needed to create a temporary variable-
length object whose length is computed within the loop, that could easily
be handled with alloca/freea; the only way to accomplish that without a
freea() intrinsic is to move the inside of the loop into another function
and prevent the compiler from inlining it. Even with the added cost of a
function call that approach would likely be cheaper than using malloc/free,
but it would be rather brittle. Further, if the compiler decides to inline
the function stack use could easily skyrocket.

> By having a "freea()" function, you would lose the benefit of automatic
> deallocation. And unless your freea() function were to be completely
> useless, you would need to deal with varied orders of alloca() and
> freea(). That means tracking allocations - leading to ram space and
> time overhead, as well as code space, not unlike malloc().

Implementations that support alloca() typically reserve two registers for
use as a stack pointer and frame pointer. On entry to each function that
uses alloca(), the compiler generates:

*((unsigned char*)__stack_pointer) = frame_pointer;
__stack_pointer -= sizeof frame_pointer;
__frame_pointer = __stack_pointer;

and on exit the compiler generates:

__stack_pointer = frame_pointer;

The alloc intrinsic is simply:

void *temp = __stack_pointer;
__stack_pointer -= [[alignment-adjusted size]];
return temp;

If the __freea() intrinsic accepted arguments for the pointer and size, then
it could on frame-pointer-based implementations be processed as simply:

__stack_pointer += [[alignment-adjusted size]];

In many cases, pre-existing logic to deal with multiple consecutive writes
to the same register would be able to eliminate even the minimal cost of
freea(). Further, if a compiler knew that all calls to the allocate and
free intrinsics were balanced, it could in many cases eliminate the code
that would be required to save and restore the frame pointer.

> Basically, your idea would completely spoil the whole point of alloca()
> and give you something not much faster than malloc(), while being far
> less flexible.

To the contrary, it would provide a feature which would often have less
overhead than alloca() while being far more flexible, and also allowing
code using it to be usable on more machines, if not all [on some platforms
it may be expensive to guarantee the behavior in cases where code performs
a setjmp(), alloca(), and longjmp(), without having freed up the temporary
allocation first; if support for that usage case was optional, code which
used balanced pair of stack-allocate/stack-free functions could be run
without changes on any platform. Further, even platforms that would normally
do the allocations on the stack could easily provide an option to use the
heap instead if the required object sizes grew large enough that the stack
was no longer usable. Adapting code which uses alloca() without a freeing
function would be much more difficult.

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 10:31:23 AM UTC-6, David Brown wrote:
> > As for telling the compiler about size limits for the VLA, how would one be
> > expected to go about that?
> >
>
> if (n >= 200) __builtin_unreachable();
> char a[n];

That's the approach that's least likely to result in extra generated code,
but __builtin_unreachable() is a non-standard extension.

> if (n >= 200) return 0;
> char a[n];
> or
>

> if (n >= 200) exit(1);
> char a[n];

If the function's specifications require defined behavior for out-of-range
values, a compiler might be able to use the bounds-check code to infer
a maximum array size. If inputs could never actually get that large for
reasons the compiler doesn't know about, such constructs would force the
compiler to generate extra code. Perhaps the cost of the useless extra code
might be less than the averted cost of code saved by letting the compiler
replace the char a[n] with char a[200], but that still doesn't seem like a
great approach.

> if (n >= 200) n = 200;
> char a[n];

Even if compilers would be allowed to skip the conditional check if they
treat the array as having a fixed size of 200, do you think many would
skip the check?

[Keith Thompson]

I've replied with some suggestions by e-mail.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Keith Thompson]

David Brown <david...@hesbynett.no> writes:
[...]
> IMHO, alloca and VLA are no worse than many other things in C - you
> simply have to know what you are doing and be sure you are doing things
> properly, such as checking the size before allocation.
[...]

I agree, mostly. But alloca and VLAs make it easier (relative to
fixed-size arrays) to overflow the stack by accidentally allocating a
very large chunk of memory. Given:

{
size_t n = some_computation;
double vla[n];
}

it can be arbitrarily difficult to avoid overflow, and to perform static
analysis of how much the stack can grow.

The solution, as with most things, is "be careful".

[Chris M. Thomasson]

[...]

FWIW, I remember using alloca to pad thread local storage in
hyperthreaded intel processors a while back. I will try to find the code.

IIRC, there was a problem wrt threads stacks interfering with each other
(false sharing) in hyper thread setup. alloca would "fix" the problem by
moving them apart such that the deadly sharing on per-thread contexts
could be avoided.

[Chris M. Thomasson]

Fwiw, here is the code:

http://webpages.charter.net/appcore/appcore/src/ac_thread_c.html

If interested at all, please take a look at the following function:

(notice the call to alloca?)
____________________________________________
void* AC_CDECL
prv_thread_entry
( void *state )
{
int ret;
void *uret;
ac_thread_t *_this = state;

ret = pthread_setspecific
( g_tls_key,
_this );
if ( ret ) { assert( ! ret ); abort(); }

if ( _this->id < 64 )
{
AC_OS_ALLOCA( 2048 * _this->id );
uret = _this->fp_entry( (void*)_this->state );
}

else
{
uret = _this->fp_entry( (void*)_this->state );
}

return uret;
}
____________________________________________

IIRC, this hardcore alloca hack-around-the-problem, was suggested to me
by an Intel paper that I cannot seem to find right now. I remember
reading it, wrt the fact that they noticed the sharing problem in early
hyperthreaded processors, and this alloca hack-in-the-box thing "fixes
it". Heck IIRC, I used the extra space in alloca to store some static
things that did not mind being destroyed at scope end.

Ahh hell, this was back in 2005, using msvc 6.0 and its crazy dinkumware
and nasty c++ template oddities.

[Chris M. Thomasson]

On 1/16/2017 3:28 AM, BartC wrote:
> On 16/01/2017 09:19, David Brown wrote:
>> On 16/01/17 01:01, supe...@casperkitty.com wrote:
>
>>> Using fixed-sized arrays is almost certainly going to be faster if
>>> adequate stack space exists to handle the maximum sizes, and may
>>> well end up having a lower worst-case stack space requirement as
>>> well. On some systems there may be good usage cases for VLAs, but
>>> the minimum size to make VLA usage really worthwhile on some systems
>>> may be larger than the size to make them blow up on others.
>>>
>>
>> That is simply nonsense.
>>
>> It is rare that Fir posts anything the makes sense, but in this thread
>> he actually did so - allocating a local array on the stack is basically
>> nothing more than an adjustment of the stack pointer. It does not
>> matter significantly whether that adjustment is of a fixed size known at
>> compile time, or a value calculated at run-time.
>
> But the adjustment isn't done at entry to a function with all the other
> fixed-size objects (or not at all if a conventional stack frame is not
> used).
>
> It's done separately after executing some code (calculating the length
> of the array). If it's in a loop, it can mean deallocating the space,
> and then allocating a new offset, each time around.

Deallocating the "some" space and atomically realigning the pointers.

Wow, this reminds me of when I was programming servers in winnt using
IOCP. Re/deallocating wrt going into dropping "slow/timedout
connections" in panic mode wrt too many clients, (back then I could
handle around 60,000 loaded and live (active) connections) on winnt.

Actually, this brings back a database like mutex based technique that
can atomically lock multiple records/objects, at once, akin to lock
based transactional memory IIRC, the deadlock avoiding locking pattern
can be outfitted with rwlocks instead of mutex...

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 1:25:21 PM UTC-6, Chris M. Thomasson wrote:
> Actually, this brings back a database like mutex based technique that
> can atomically lock multiple records/objects, at once, akin to lock
> based transactional memory IIRC, the deadlock avoiding locking pattern
> can be outfitted with rwlocks instead of mutex...

If two threads tried to use the same LIFO memory manager and one thread
were holding some LIFO-managed storage when the second thread acquired
some of its own, the first thread would not be able to release its
storage until the second thread released its storage. Not a particularly
nice arrangement.

A much better arrangement would be for each thread to have its own
independent LIFO memory manager. Provided that the system supported
some efficient means of declaring "thread-static" variables, such an
approach would eliminate the need for any kind of locking or other
coordination.

[Chris M. Thomasson]

On 1/16/2017 12:28 PM, supe...@casperkitty.com wrote:
> On Monday, January 16, 2017 at 1:25:21 PM UTC-6, Chris M. Thomasson wrote:
>> Actually, this brings back a database like mutex based technique that
>> can atomically lock multiple records/objects, at once, akin to lock
>> based transactional memory IIRC, the deadlock avoiding locking pattern
>> can be outfitted with rwlocks instead of mutex...
>
> If two threads tried to use the same LIFO memory manager and one thread
> were holding some LIFO-managed storage when the second thread acquired
> some of its own, the first thread would not be able to release its
> storage until the second thread released its storage. Not a particularly
> nice arrangement.

LIFO atomic stack is still in IBM Principles of Operation. Very nice.

http://www-01.ibm.com/support/docview.wss?uid=isg26480faec85f44e2385256d5200627dee&aid=1

Under Multi programming and Multiprocessing A-43
-> Free Pool Manipulation A-48
Also, check out PLO. A-50

>
> A much better arrangement would be for each thread to have its own
> independent LIFO memory manager.

Agreed!

> Provided that the system supported
> some efficient means of declaring "thread-static" variables, such an
> approach would eliminate the need for any kind of locking or other
> coordination.

fwiw, I remember getting permission to post this diagram:

http://webpages.charter.net/appcore/vzoom/msgsys.pdf

[Robert Wessel]

That sounds like the old P4 64KB aliasing issue. Basically the cache
design allowed/caused excessive conflicts if data items were exactly a
multiple of 64KB apart. This had nothing in particular to do with
hyperthreading, although if you had two threads running simultaneously
with stacks aligned the "right" way (not uncommon, given how many OS's
allocate stack address space), you'd hit that aliasing issue, and
cause cache thrashing (since the two threads on the one core share the
same cache).

[David Brown]

On 16/01/17 17:35, supe...@casperkitty.com wrote:
> On Monday, January 16, 2017 at 2:56:27 AM UTC-6, David Brown wrote:
>> alloca (and VLAs) has three key advantages over malloc. First, it is
>> fast. Secondly, it is as space-efficient as possible. Thirdly, you
>> don't need to deallocate it - it is automatically deallocated at the end
>> of the block. A key /disadvantage/ is that you don't have the
>> flexibility to re-order your allocations and deallocations - this is
>> strictly stack ordering.
>
> A bigger disadvantage is that it is unusable even in many cases where stack
> ordering would be fine. If a loop needed to create a temporary variable-
> length object whose length is computed within the loop, that could easily
> be handled with alloca/freea; the only way to accomplish that without a
> freea() intrinsic is to move the inside of the loop into another function
> and prevent the compiler from inlining it. Even with the added cost of a
> function call that approach would likely be cheaper than using malloc/free,
> but it would be rather brittle. Further, if the compiler decides to inline
> the function stack use could easily skyrocket.
>

I can't follow what you mean here. Can you give a rough example?

[David Brown]

On 16/01/17 18:22, Keith Thompson wrote:
> David Brown <david...@hesbynett.no> writes:
> [...]
>> IMHO, alloca and VLA are no worse than many other things in C - you
>> simply have to know what you are doing and be sure you are doing things
>> properly, such as checking the size before allocation.
> [...]
>
> I agree, mostly. But alloca and VLAs make it easier (relative to
> fixed-size arrays) to overflow the stack by accidentally allocating a
> very large chunk of memory. Given:
>
> {
> size_t n = some_computation;
> double vla[n];
> }
>
> it can be arbitrarily difficult to avoid overflow, and to perform static
> analysis of how much the stack can grow.

Certainly it is easier to overflow the stack when using a feature that
lets you make big allocations. But you would never write:

{
size_t n = some_computation;
char* p = malloc(n);
}

without knowing about some_computation and its limits. The same applies
to alloca or VLA's - the difference is that you might want to be sure
your limits are below 1 MB or so for VLA's, while you might be happy
with GB limits for your malloc's. But the principle is the same.

>
> The solution, as with most things, is "be careful".
>

We've got to earn our living somehow!

[David Brown]

On 16/01/17 17:48, supe...@casperkitty.com wrote:
> On Monday, January 16, 2017 at 10:31:23 AM UTC-6, David Brown wrote:
>>> As for telling the compiler about size limits for the VLA, how would one be
>>> expected to go about that?
>>>
>>
>> if (n >= 200) __builtin_unreachable();
>> char a[n];
>
> That's the approach that's least likely to result in extra generated code,
> but __builtin_unreachable() is a non-standard extension.
>

Correct. Compilers often have something equivalent - use a macro for
portability, with a fall-back to "exit(1)" or something like that.

>> if (n >= 200) return 0;
>> char a[n];
>> or
>>
>> if (n >= 200) exit(1);
>> char a[n];
>
> If the function's specifications require defined behavior for out-of-range
> values, a compiler might be able to use the bounds-check code to infer
> a maximum array size. If inputs could never actually get that large for
> reasons the compiler doesn't know about, such constructs would force the
> compiler to generate extra code.

A call to exit() is unlikely to use much code - a couple of
instructions, perhaps. And in cases where a couple of instructions is
relevant, you are probably working on a small embedded system with a
specific compiler, and a compiler-specific __builtin_unreachable() will
be fine.

> Perhaps the cost of the useless extra code
> might be less than the averted cost of code saved by letting the compiler
> replace the char a[n] with char a[200], but that still doesn't seem like a
> great approach.
>
>> if (n >= 200) n = 200;
>> char a[n];
>
> Even if compilers would be allowed to skip the conditional check if they
> treat the array as having a fixed size of 200, do you think many would
> skip the check?
>

I don't think compilers /would/ treat the array as having a fixed size
of 200 - though I think they certainly /could/ do so and give correct
code. But using the fixed size would mean you miss out on the benefits
of saving stack space, so it is unlikely that a compiler would do that.

[David Brown]

On 16/01/17 17:08, supe...@casperkitty.com wrote:
> On Monday, January 16, 2017 at 3:09:03 AM UTC-6, David Brown wrote:
>> It is highly unlikely that using a VLA will call malloc. (It is not
>> impossible - someone mentioned that this is done on some 8051 compilers.
>> But there we are talking about very limited processors with no decent
>> data stack support.)
>
> It is also done on current Keil compilers for the ARM (which is hadly what
> I would call a "very limited processor with no decent data stack support").

That surprises me. However, my limited experience of Keil for the 8051
does not inspire confidence in the quality of their tools, and my
understanding is that ARM is moving from Keil's tools to clang for the
"official" ARM compiler (as well as giving enormous support to gcc for ARM).

If I choose to use a VLA or alloca() instead of malloc(), it is because
I think a stack-based allocation is a better choice. I can understand
the compiler generating a malloc-like call on a target that basically
does not have a data stack, but not for the ARM. It is like asking for
"x * y" and finding the compiler generates a loop that adds "x" together
"y" times. Technically, it may be correct code - but it is far from
what I want.

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 5:22:06 PM UTC-6, David Brown wrote:

> On 16/01/17 17:35, supercat wrote:
> > A bigger disadvantage is that it is unusable even in many cases where stack
> > ordering would be fine. If a loop needed to create a temporary variable-
> > length object whose length is computed within the loop, that could easily
> > be handled with alloca/freea; the only way to accomplish that without a
> > freea() intrinsic is to move the inside of the loop into another function
> > and prevent the compiler from inlining it. Even with the added cost of a
> > function call that approach would likely be cheaper than using malloc/free,
> > but it would be rather brittle. Further, if the compiler decides to inline
> > the function stack use could easily skyrocket.
>
> I can't follow what you mean here. Can you give a rough example?

Sure. Consider the code:

void process_file_records(FILE *f)
{
uint16_t record_size;
while(fread(&record_size, 2, 1, f) && record_size)
{
void *dat = malloc(record_size);
if (!dat) exit(-1);
fread(dat, 1, record_size, f);
process_record(dat, record_size);
free(dat);
more_stuff_not_needing_dat();
}
}

If "process_record" never keeps a copy of "dat", the storage identified by
the pointer won't have to outlive the function, and code will never destroy
anything other than the most recent live object created. Such code would
thus be a good candidate for alloca if there were a balancing freea
available. The only way for such code to take advantage of alloca,
however, would be to pull all the logic that handles each record into its
own function which would allocate stack storage shortly after entry, and
release that storage when it exits.

void do_stuff_with_one_record(FILE *f, uint16_t record_size)
{
void *dat = alloca(record_size);
if (!dat) exit(-1);
fread(dat, 1, record_size, f);
process_record(dat, record_size);
}

void process_file_records(FILE *f)
{
uint16_t record_size;
while(fread(&record_size, 2, 1, f) && record_size)
{
do_stuff_with_one_record(f, record_size);
more_stuff_not_needing_dat();
}
}

That would work, but it's not a great subdivision of functionality between
the two functions. Worse, if a compiler decides to inline the call to
do_stuff_with_one_record, the storage reserved by the inner function's
call to alloca() may not get released until after the outer function
returns, meaning that all of the records from the input data stream would
need to fit on the stack *simultaneously*. Oops.

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 5:35:21 PM UTC-6, David Brown wrote:

> On 16/01/17 17:08, supercat wrote:
> > It is also done on current Keil compilers for the ARM (which is hadly what
> > I would call a "very limited processor with no decent data stack support").
>
> That surprises me. However, my limited experience of Keil for the 8051
> does not inspire confidence in the quality of their tools, and my
> understanding is that ARM is moving from Keil's tools to clang for the
> "official" ARM compiler (as well as giving enormous support to gcc for ARM).

What complaints to you have about the 8051 Keil? To be sure, it processes
a non-standard dialect of C because such a dialect is a better fit for the
target than a conforming dialect could be, but I'd rather have a compiler
implement a useful dialect than a conforming-but-useless one.

For most compilers I use, I can think of at least one bug that I've
encountered. The Keil is one of four I can think of for which none
come to mind (as compared with CCS compiler for the PIC which miscomputed
jump targets, HiTech compiler for the PIC which mis-set banking bits,
MPW compiler for the Macintosh which miscomputed stack frame sizes between
32K and 64K, Turbo C for the PC whose floating-point formatting is buggy,
gcc which optimizes out memmove() even in cases where its presence is needed
to make code have defined behavior, and then uses the lack of the memmove as
a basis for treating code as having Undefined Behavior, clang which doesn't
recognize aliasing of objects accessed through unions, etc.)

What don't you like about it?

[David Brown]

On 17/01/17 01:23, supe...@casperkitty.com wrote:
> On Monday, January 16, 2017 at 5:22:06 PM UTC-6, David Brown wrote:
>> On 16/01/17 17:35, supercat wrote:
>>> A bigger disadvantage is that it is unusable even in many cases where stack
>>> ordering would be fine. If a loop needed to create a temporary variable-
>>> length object whose length is computed within the loop, that could easily
>>> be handled with alloca/freea; the only way to accomplish that without a
>>> freea() intrinsic is to move the inside of the loop into another function
>>> and prevent the compiler from inlining it. Even with the added cost of a
>>> function call that approach would likely be cheaper than using malloc/free,
>>> but it would be rather brittle. Further, if the compiler decides to inline
>>> the function stack use could easily skyrocket.
>>
>> I can't follow what you mean here. Can you give a rough example?
>
> Sure. Consider the code:
>
> void process_file_records(FILE *f)
> {
> uint16_t record_size;
> while(fread(&record_size, 2, 1, f) && record_size)
> {
> void *dat = malloc(record_size);
> if (!dat) exit(-1);
> fread(dat, 1, record_size, f);
> process_record(dat, record_size);
> free(dat);
> more_stuff_not_needing_dat();
> }
> }
>

I see what you mean. I suspect the compiler can make some optimisations
in such code if it knows it is safe to free the alloca space, but it
probably can't do that here.

But just use VLA's. They are deallocated at the end of their scope.

[supe...@casperkitty.com]

On Monday, January 16, 2017 at 7:04:40 PM UTC-6, David Brown wrote:
> I see what you mean. I suspect the compiler can make some optimisations
> in such code if it knows it is safe to free the alloca space, but it
> probably can't do that here.

The compiler could only optimize if it knew how the called function would use
the pointer. Otherwise, if the code didn't explicitly free the alloca()
storage a compiler would have to assume that any called function it couldn't
see into might save a copy of the passed-in pointer, thus allowing it to be
reused during the execution of any other opaque function that gets called
prior to the return of the function calling alloca().

> But just use VLA's. They are deallocated at the end of their scope.

Their semantics aren't as bad as a free-less alloca(), but some uses of
temporary storage would require lifetimes that don't line up very well with
code block structures. For example, parsers may benefit from being able to
use a logical stack to keep track of nested structures without having to use
recursive function calls.

[David Brown]

On 17/01/17 02:27, supe...@casperkitty.com wrote:
> On Monday, January 16, 2017 at 7:04:40 PM UTC-6, David Brown wrote:
>> I see what you mean. I suspect the compiler can make some optimisations
>> in such code if it knows it is safe to free the alloca space, but it
>> probably can't do that here.
>
> The compiler could only optimize if it knew how the called function would use
> the pointer. Otherwise, if the code didn't explicitly free the alloca()
> storage a compiler would have to assume that any called function it couldn't
> see into might save a copy of the passed-in pointer, thus allowing it to be
> reused during the execution of any other opaque function that gets called
> prior to the return of the function calling alloca().

Correct.

>
>> But just use VLA's. They are deallocated at the end of their scope.
>
> Their semantics aren't as bad as a free-less alloca(), but some uses of
> temporary storage would require lifetimes that don't line up very well with
> code block structures. For example, parsers may benefit from being able to
> use a logical stack to keep track of nested structures without having to use
> recursive function calls.
>

The world is not perfect.

I have already said why I think a "freea()" function would be a bad
idea, and I have not changed my mind. I can agree that it might make a
few kinds of functions slightly neater or more efficient if it existed,
but I don't see it being worth the disadvantages.