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

Groups > comp.std.c > #1627 > unrolled thread

VLAs use less stack

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

Contents

  VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-08-31 12:58 +0200
    Re: VLAs use less stack Marc <marc.glisse@gmail.com> - 2012-08-31 14:10 +0000
      Re: VLAs use less stack Marc <marc.glisse@gmail.com> - 2012-08-31 14:13 +0000
      Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-08-31 18:09 +0200
      Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-08-31 18:14 +0200
      Re: VLAs use less stack John Nagle <nagle@animats.com> - 2012-09-01 12:24 -0700
        Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-09-01 22:57 +0200
        Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-09-01 22:59 +0200
    Re: VLAs use less stack Keith Thompson <kst-u@mib.org> - 2012-08-31 11:42 -0700
      Re: VLAs use less stack Marc <marc.glisse@gmail.com> - 2012-09-01 10:18 +0000
        Re: VLAs use less stack Rui Maciel <rui.maciel@gmail.com> - 2012-09-01 19:18 +0100
          Re: VLAs use less stack Marc <marc.glisse@gmail.com> - 2012-09-01 19:19 +0000
          Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-09-01 23:01 +0200
        Re: VLAs use less stack Keith Thompson <kst-u@mib.org> - 2012-09-01 11:36 -0700
          Re: VLAs use less stack Marc <marc.glisse@gmail.com> - 2012-09-01 19:05 +0000
      Re: VLAs use less stack jgk@panix.com (Joe keane) - 2012-09-02 16:56 +0000
        Re: VLAs use less stack Keith Thompson <kst-u@mib.org> - 2012-09-02 14:22 -0700
          Re: VLAs use less stack jgk@panix.com (Joe keane) - 2012-09-04 00:39 +0000
            Re: VLAs use less stack Jens Gustedt <jens.gustedt@loria.fr> - 2012-09-04 10:28 +0200
              Re: VLAs use less stack John Nagle <nagle@animats.com> - 2012-09-04 11:31 -0700
            Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-09-04 17:02 +0200
        Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-09-02 23:28 +0200
        Re: VLAs use less stack Keith Thompson <kst-u@mib.org> - 2012-09-02 14:37 -0700
          Re: VLAs use less stack John Nagle <nagle@animats.com> - 2012-09-02 15:45 -0700
            Re: VLAs use less stack Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2012-09-04 00:03 +0200
    Re: VLAs use less stack jgk@panix.com (Joe keane) - 2012-09-01 16:09 +0000
      Re: VLAs use less stack Keith Thompson <kst-u@mib.org> - 2012-09-01 11:45 -0700
      Re: VLAs use less stack jacob navia <jacob@spamsink.net> - 2012-09-01 23:05 +0200

Page 1 of 2  [1] 2  Next page →

#1627 — VLAs use less stack

In many cases, when needing a buffer the programmer has to use

#define MAXDATA	1024
int fn(int datasiz)
{
     char fullPath[MAXDATA];
}

using the worst possible case as the normal case. Most datasets will be
much smaller but you HAVE to use the biggest possible.

Now, if you use VLAs you could write:
int fn(int datasiz)
{
     char fullPath[datasiz];
}

using in the average case much less stack than above.

Critics to VLAs would say that this opens the door to an unlimited use
of the stack, what in the above example is true. But it is NOT true that
this is impossible to avoid:

int fn(size_t datasiz)
{
     char databuf[datasiz<1000?datasiz:1];
     char *p;
     int result;

     if (datasiz >= 1000) {
         p = malloc(datasiz);
	if (p == NULL {/*error handler here */
              return EXIT_FAILURE;
         }
     }
     else p = & databuf[0];
     // Use p here
     if (datasiz>=1000) free(p);
     return result;
}

Here we have the best path: In MOST cases we will use a cheap stack
allocation. In the few cases where the data size is exceptionally big
we use the more costly heap allocation. We can handle an unbounded
amount of data.

It would be nice if we would put this examples in a visible part of the 
internet...

(If you agree of course)


Essentially the myth that VLAs are UNBOUNDED must be debunked. They can
be bounded!

jacob

[toc] | [next] | [standalone]

#1628

jacob navia  wrote:

> In many cases, when needing a buffer the programmer has to use
> 
> #define MAXDATA	1024
> int fn(int datasiz)
> {
>      char fullPath[MAXDATA];
> }
> 
> using the worst possible case as the normal case. Most datasets will be
> much smaller but you HAVE to use the biggest possible.
> 
> Now, if you use VLAs you could write:
> int fn(int datasiz)
> {
>      char fullPath[datasiz];
> }
> 
> using in the average case much less stack than above.

I doubt 1024 is really an issue. In an embedded device where it would be
an issue, you probably wouldn't want a malloc call either.

> Critics to VLAs would say that this opens the door to an unlimited use
> of the stack, what in the above example is true. But it is NOT true that
> this is impossible to avoid:
> 
> int fn(size_t datasiz)
> {
>      char databuf[datasiz<1000?datasiz:1];
>      char *p;
>      int result;
> 
>      if (datasiz >= 1000) {
>          p = malloc(datasiz);
> 	if (p == NULL {/*error handler here */
>               return EXIT_FAILURE;
>          }
>      }
>      else p = & databuf[0];
>      // Use p here
>      if (datasiz>=1000) free(p);
>      return result;
> }
> 
> Here we have the best path: In MOST cases we will use a cheap stack
> allocation. In the few cases where the data size is exceptionally big
> we use the more costly heap allocation. We can handle an unbounded
> amount of data.
> 
> It would be nice if we would put this examples in a visible part of the 
> internet...

It is far from original. This is used for instance for temporaries in
GMP (with alloca instead of VLAs, so they even save 1000 bytes when
malloc is called). It is a variant on the small string optimization. And
in many cases, VLAs won't win much compared to a small fixed buffer with
a malloc fallback. You can also use a different allocator than malloc
for allocations where you know the deallocation order will be the
reverse of the allocation order, or if you accept to never deallocate,
or only deallocate things all at once, etc.

> Essentially the myth that VLAs are UNBOUNDED must be debunked. They can
> be bounded!

Sure, anything can be used properly. The question is whether it
encourages / helps proper use.

See also the C++ dynarray proposal.

PS: I don't have a clear opinion on VLA, I just don't think that this is
such a strong argument in their favor. And being unbounded isn't the
only drawback of VLAs either.

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

#1629

Marc  wrote:

> (with alloca instead of VLAs, so they even save 1000 bytes when
> malloc is called).

Oups, 1 byte (+ possible overhead), not 1000, sorry.

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

#1630

Le 31/08/12 16:10, Marc a écrit :
> I doubt 1024 is really an issue. In an embedded device where it would be
> an issue, you probably wouldn't want a malloc call either.

Of course the "1024" stands for SOME_LIMIT !
In a PC it would be (1024*1024) probably...

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

#1631

Le 31/08/12 16:10, Marc a écrit :
> It is far from original. This is used for instance for temporaries in
> GMP (with alloca instead of VLAs, so they even save 1000 bytes when
> malloc is called). It is a variant on the small string optimization. And
> in many cases, VLAs won't win much compared to a small fixed buffer with
> a malloc fallback.

I am not claiming any copyright for the above code so if it is not
original it just doesn't matter.

If GMP uses alloca, this just confirms to the usefulness of this, since
alloca isn't a standard function.

You say "A small fixed buffer with a malloc fallback"... Well, why you
are so keen of that "fixed" part?

Why can't the user just allocate EXACTLY what it needs, not more not
less?


Imagine a malloc where you can allocate only two sizes: BIG and SMALL.

Nice isn't it?

"Just allocate SMALL, and if doesn't work, then you go BIG."

VLAs are an improvement.

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

#1642

On 8/31/2012 7:10 AM, Marc wrote:
> jacob navia  wrote:
>> Critics to VLAs would say that this opens the door to an unlimited use
>> of the stack, what in the above example is true. But it is NOT true that
>> this is impossible to avoid:
...
> 
> PS: I don't have a clear opinion on VLA, I just don't think that this is
> such a strong argument in their favor. And being unbounded isn't the
> only drawback of VLAs either.

   This is really an OS and architecture issue.  The problem is not
running out of memory for stack space; it's running out of address
space for it.  Most machines today have the heap and stack in the
same address space, and C assumes such a model.  So at some point,
there's a conflict between address space assigned to the heap
and address space assigned to the stack. Linux usually limits
stack growth to 12MB.

   Then there's threading, which often results in many threads
sharing the same limited stack address space.

   There's also an assumption in some operating systems that the
stack will grow "slowly".  Under Windows (NT to date),
stack growth is triggered by a page fault in the next 4K
block beyond the current stack allocation.  Allocating,
but not using, a block bigger than 4K on the stack can
result in a program abort if the next stack access is
in a block other than the immediately next block.  See

https://bugzilla.mozilla.org/show_bug.cgi?id=644900
http://support.microsoft.com/kb/100775

This may be why Microsoft doesn't support VLAs
in C.

				John Nagle

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

#1644

Le 01/09/12 21:24, John Nagle a écrit :
>     There's also an assumption in some operating systems that the
> stack will grow "slowly".  Under Windows (NT to date),
> stack growth is triggered by a page fault in the next 4K
> block beyond the current stack allocation.  Allocating,
> but not using, a block bigger than 4K on the stack can
> result in a program abort if the next stack access is
> in a block other than the immediately next block.  See
>
> https://bugzilla.mozilla.org/show_bug.cgi?id=644900
> http://support.microsoft.com/kb/100775
>
> This may be why Microsoft doesn't support VLAs
> in C.

This is just not true.

suppose:

int fn(void)
{
	int table[1024+1];
}

This program would crash because the stack exceeds 4096 bytes.

But it doesn't even in Microsoft compiler. In my compiler system
I make a loop 'touching" stack pages at function entry. Of course
that loop is not user visible. Microsoft does a similar thing.

This problem was solved around 1995...

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

#1645

Le 01/09/12 21:24, John Nagle a écrit :
>   So at some point,
> there's a conflict between address space assigned to the heap
> and address space assigned to the stack. Linux usually limits
> stack growth to 12MB.

Yes. And in this times of byte inflation 12MB is considered "minuscule".

AWFUL...

Windows 3.1 had 64K stack, and we developed good applications there.

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

#1632

jacob navia <jacob@spamsink.net> writes:
> In many cases, when needing a buffer the programmer has to use
>
> #define MAXDATA	1024
> int fn(int datasiz)
> {
>      char fullPath[MAXDATA];
> }
>
> using the worst possible case as the normal case. Most datasets will be
> much smaller but you HAVE to use the biggest possible.

How common is that in practice?  In the absence of VLAs, if you don't
know in advance how big the buffer needs to be, isn't it more common to
use malloc() (and possibly realloc())?

> Now, if you use VLAs you could write:
> int fn(int datasiz)
> {
>      char fullPath[datasiz];
> }
>
> using in the average case much less stack than above.
>
> Critics to VLAs would say that this opens the door to an unlimited use
> of the stack, what in the above example is true.

Which, as you know, means that you can't detect, much less handle, an
allocation failure.  (Just clarifying.)

>                                                  But it is NOT true that
> this is impossible to avoid:
>
> int fn(size_t datasiz)
> {
>      char databuf[datasiz<1000?datasiz:1];
>      char *p;
>      int result;
>
>      if (datasiz >= 1000) {
>          p = malloc(datasiz);
> 	if (p == NULL {/*error handler here */
>               return EXIT_FAILURE;
>          }
>      }
>      else p = & databuf[0];
>      // Use p here
>      if (datasiz>=1000) free(p);
>      return result;
> }
>
> Here we have the best path: In MOST cases we will use a cheap stack
> allocation. In the few cases where the data size is exceptionally big
> we use the more costly heap allocation. We can handle an unbounded
> amount of data.
>
> It would be nice if we would put this examples in a visible part of the 
> internet...
>
> (If you agree of course)
>
>
> Essentially the myth that VLAs are UNBOUNDED must be debunked. They can
> be bounded!

Interesting idea.  But I wonder how often it's really worthwhile
in practice.  In terms of code complexity, it offers no advantage
over using malloc/free uconditionally; you still have to make sure
you call free() if the buffer was allocated with malloc(), so you
lose that advantage of VLAs.

The only advantage it offers over using malloc/free unconditionally
is that it avoids the overhead of the malloc and free calls for
small buffers.  Are malloc and free really expensive enough for
this to be a worthwhile optimization?  The tradeoff is likely to
vary from one system to another.  (I'm not trying to imply that
it's *not* worthwhile; I haven't measured it myself, and I'm asking
because I honestly don't know.)

Note that if you're using a compiler that doesn't support VLAs
(because it's pre-C99, or because it's a C11 compiler that defines
__STDC_NO_VLA__), you can still do something similar using a
fixed-sized array.  It's slightly more wasteful of "stack" space
(which is the point you're making), but with a small enough fixed
size it could be reasonable.  One good use case is reading lines
of text, where most lines are expected to be short but you want to
handle arbitrarily long lines.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#1636

Keith Thompson  wrote:

> The only advantage it offers over using malloc/free unconditionally
> is that it avoids the overhead of the malloc and free calls for
> small buffers.  Are malloc and free really expensive enough for
> this to be a worthwhile optimization?  The tradeoff is likely to
> vary from one system to another.  (I'm not trying to imply that
> it's *not* worthwhile; I haven't measured it myself, and I'm asking
> because I honestly don't know.)

I have to side with Jacob here, malloc and free are expensive enough to
make very complicated optimizations worthwile, sadly. I have seen a
number of programs where more than half the running time was spent in
malloc+free (and sometimes much more than half).

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

#1638

Marc wrote:

> I have to side with Jacob here, malloc and free are expensive enough to
> make very complicated optimizations worthwile, sadly. I have seen a
> number of programs where more than half the running time was spent in
> malloc+free (and sometimes much more than half).

Wouldn't a memory pool help with that?


Rui Maciel

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

#1643

Rui Maciel  wrote:

> Marc wrote:
> 
>> I have to side with Jacob here, malloc and free are expensive enough to
>> make very complicated optimizations worthwile, sadly. I have seen a
>> number of programs where more than half the running time was spent in
>> malloc+free (and sometimes much more than half).
> 
> Wouldn't a memory pool help with that?

There are many ways to avoid the slow generic malloc, but they depend on
your use case. Memory pools can be great like they can be useless. Just
switching your malloc implementation can already have dramatic
consequences (a factor 3 in runtime, or in memory use, or in lock
contention, or...).

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

#1646

Le 01/09/12 20:18, Rui Maciel a écrit :
> Marc wrote:
>
>> I have to side with Jacob here, malloc and free are expensive enough to
>> make very complicated optimizations worthwile, sadly. I have seen a
>> number of programs where more than half the running time was spent in
>> malloc+free (and sometimes much more than half).
>
> Wouldn't a memory pool help with that?
>
>
> Rui Maciel
>

Of course it would help.

As it would help to use the standard container
"growable buffer" proposed in the C Containers Library.

:-)

But all those things need initializing, setting up, etc.
Stack allocation in most cases, backed by a malloc allocation
is an atractive alternative.

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

#1639

Marc <marc.glisse@gmail.com> writes:
> Keith Thompson  wrote:
>> The only advantage it offers over using malloc/free unconditionally
>> is that it avoids the overhead of the malloc and free calls for
>> small buffers.  Are malloc and free really expensive enough for
>> this to be a worthwhile optimization?  The tradeoff is likely to
>> vary from one system to another.  (I'm not trying to imply that
>> it's *not* worthwhile; I haven't measured it myself, and I'm asking
>> because I honestly don't know.)
>
> I have to side with Jacob here, malloc and free are expensive enough to
> make very complicated optimizations worthwile, sadly. I have seen a
> number of programs where more than half the running time was spent in
> malloc+free (and sometimes much more than half).

Ok.

But your use of the phrase "side with" implies that I've taken
sides against jacob.  I haven't; I merely asked some questions.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#1641

Keith Thompson  wrote:

> But your use of the phrase "side with" implies that I've taken
> sides against jacob.  I haven't; I merely asked some questions.

Sorry for the misunderstanding, I meant "I agree with", didn't mean to
fight anyone...

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

#1649

In article <lnsjb2ucn5.fsf@nuthaus.mib.org>,
Keith Thompson  <kst-u@mib.org> wrote:
>How common is that in practice?  In the absence of VLAs, if you don't
>know in advance how big the buffer needs to be, isn't it more common to
>use malloc() (and possibly realloc())?

That is the only way to handle the general case.

fixed-size array: fails at some point (can check for this)
and variable-size array: fails at some point (can't check for this)

>Interesting idea.  But I wonder how often it's really worthwhile
>in practice.  In terms of code complexity, it offers no advantage
>over using malloc/free uconditionally; you still have to make sure
>you call free() if the buffer was allocated with malloc(), so you
>lose that advantage of VLAs.

It is useful.  It's simply profiling.  If you find too much time spent
in malloc and free, fix it somehow...  This is one way.

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

#1651

jgk@panix.com (Joe keane) writes:
> In article <lnsjb2ucn5.fsf@nuthaus.mib.org>,
> Keith Thompson  <kst-u@mib.org> wrote:
>>How common is that in practice?  In the absence of VLAs, if you don't
>>know in advance how big the buffer needs to be, isn't it more common to
>>use malloc() (and possibly realloc())?
>
> That is the only way to handle the general case.
>
> fixed-size array: fails at some point (can check for this)
> and variable-size array: fails at some point (can't check for this)

I was referring to *just* using malloc(), realloc(), and free(),
even for small allocations, as opposed to falling back to malloc()
for large buffers.

If you're going to be using malloc() for some cases, your code
will be simpler if you use malloc() for all cases.  My question
is whether the (presumed) greater efficiency of a hybrid approach
makes up for the greater code complexity.

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#1659

In article <lnd324glvw.fsf@nuthaus.mib.org>,
Keith Thompson  <kst-u@mib.org> wrote:
>I was referring to *just* using malloc(), realloc(), and free(),
>even for small allocations, as opposed to falling back to malloc()
>for large buffers.

So we are clear:

a. fixed-size array only
b. variable-size array only
c. malloc and free only
d. fixed-size array with malloc and free backup
e. variable-size array with malloc and free backup

Options 'a' and 'b' are easy: they don't work.

Option 'c' is 'better', it works, except it may be slow.  Generally
speaking i prefer code that is slow to code that doesn't work.

Option 'd' is 'better'.

But you shouldn't bother with it unless you have some reason to think
it's needed, either some evidence, or the fact that it has proven useful
in some other situation, such that it would be less time to code it that
way in the first place, rather than test it and find that it's a problem
and then fix it.

I don't think that 'e' really buys you a lot versus 'd'.

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

#1660

Am 04.09.2012 02:39, schrieb Joe keane:
> In article <lnd324glvw.fsf@nuthaus.mib.org>,
> Keith Thompson  <kst-u@mib.org> wrote:
>> I was referring to *just* using malloc(), realloc(), and free(),
>> even for small allocations, as opposed to falling back to malloc()
>> for large buffers.
> 
> So we are clear:
> 
> a. fixed-size array only
> b. variable-size array only
> c. malloc and free only
> d. fixed-size array with malloc and free backup
> e. variable-size array with malloc and free backup
> 
> Options 'a' and 'b' are easy: they don't work.
> 
> Option 'c' is 'better', it works, except it may be slow.  Generally
> speaking i prefer code that is slow to code that doesn't work.
> 
> Option 'd' is 'better'.
> 
> But you shouldn't bother with it unless you have some reason to think
> it's needed, either some evidence, or the fact that it has proven useful
> in some other situation, such that it would be less time to code it that
> way in the first place, rather than test it and find that it's a problem
> and then fix it.
> 
> I don't think that 'e' really buys you a lot versus 'd'.

It really would depend on the use pattern. If the function is
recursive and the average size of the allocation is small, say some
value x, this could be worth doing. You could put the cut off at 10*x
and the malloc case would appear "almost never", by still having a
stack use of x on average, instead of 10*x. Then you could go deeper
into recursion and maybe even more important the cache behavior could
be a bit better.

But I agree that these are a lot of hypothesis.

Jens

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

#1662

On 9/4/2012 1:28 AM, Jens Gustedt wrote:
> Am 04.09.2012 02:39, schrieb Joe keane:
>> In article <lnd324glvw.fsf@nuthaus.mib.org>,
>> Keith Thompson  <kst-u@mib.org> wrote:
>>> I was referring to *just* using malloc(), realloc(), and free(),
>>> even for small allocations, as opposed to falling back to malloc()
>>> for large buffers.
>>
>> So we are clear:
>>
>> a. fixed-size array only
>> b. variable-size array only
>> c. malloc and free only
>> d. fixed-size array with malloc and free backup
>> e. variable-size array with malloc and free backup

   One could argue for doing e) within the implementation,
rather than in user code.  In compilers targeted to Windows,
the compiler already has to be aware of the 4K at a time
stack growth limitation.  So there's already compiler
special casing for big arrays on the stack.

   The correct action to take is defined by the platform.
If you're on a 64-bit platform with gigabytes of allowed
stack address space, there's no reason not to put big arrays
on the stack.  If you're on an embedded machine where the
stack is in limited SRAM but the heap is in DRAM, you never
want to put a large array on the stack.

   An argument against doing this in the compiler is that
it requires destructor-like unwinding actions at block exit,
which C++ handles but C normally avoids.

			John Nagle

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web