Ben Cooling wrote:
>
[...]
> If I write
>
>     void f( void )
>     {
>         char *p = new char[1000];
>
>         // use p
>
>         delete[] p;
>     }
>
> then can an implementation not use alloca (or equivalent) to allocate
> this memory?  This is a real question (not just a rhetorical assertion =).
> Obviously in real situations things get a little more complicated,
> but it could get more useful if a compiler could do this for (inlined)
> container ctors and dtors.


Your compiler must be sure, that '// use p' does not
 - throw an exeption,
 - reassign p, or
 - delete[] p.


Why not simply:

void f( size_t x )
{
  char p[x];
  // use p
}

This syntax is straight forward; It's obvious, that you must not write
++p or delete[] p.
I'd even like to define multi-dimensional arrays with runtime-defined
sizes.

If you ever need alloca() explicitly for something else than an array of
objects, you can get the effect via:

void f(size_t x)
{
  char buffer[x];
  void * p = &buffer; // instead of: p = alloca(x)

  // use p
}


And if a compiler does not support stack allocation, it can fall back to
generate code as in your example anyway.


Ralph

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Francis Glassborow wrote:
>
> In article <3B27FF4D.E73310F0@wizard.net>, James Kuyper Jr.
> <kuyper@wizard.net> writes
...
> >I don't see how that applies - the basic thing the ODR rule says says,
> >as it's name implies, is that there must be only one definition. When
> >the user provides a replacement function, as specified in 17.4.3.4, that
> >IS the one definition, as is made clear by 17.1.14.
>
> But the problem is how exactly the buitlin operator new and operator
> delete are provided. I do not think they are prohibited from being
> inlined in which case the user provide version will not be used in
> modules where the compiler is unaware of it.

I don't see how that would constitute a conforming implementation, given
the sections cited above.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <9g7599$7h7jf$1@ID-49767.news.dfncis.de>, Anthony Williams
<anthwil@nortelnetworks.com> writes
>Question: if I supply operator new[] and operator delete[] in one
>translation unit, are uses of new[] and delete[] in another translation unit
>guaranteed to use my functions, without explicitly declaring them?

I think not. I think you have a major implicit breach of the ODR.

Francis Glassborow      ACCU
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Anthony Williams wrote:
>
> Question: if I supply operator new[] and operator delete[] in one
> translation unit, are uses of new[] and delete[] in another translation unit
> guaranteed to use my functions, without explicitly declaring them?
>

operator new(size_t), operator delete(void*), operator new[](size_t),
and operator delete[](void*) are replaceable functions. If you supply
your own global versions they will be used throughout the program.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Francis Glassborow wrote:
>
> In article <9g7599$7h7jf$1@ID-49767.news.dfncis.de>, Anthony Williams
> <anthwil@nortelnetworks.com> writes
> >Question: if I supply operator new[] and operator delete[] in one
> >translation unit, are uses of new[] and delete[] in another translation unit
> >guaranteed to use my functions, without explicitly declaring them?
>
> I think not. I think you have a major implicit breach of the ODR.

I don't see how that applies - the basic thing the ODR rule says says,
as it's name implies, is that there must be only one definition. When
the user provides a replacement function, as specified in 17.4.3.4, that
IS the one definition, as is made clear by 17.1.14.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <3B27FF4D.E73310F0@wizard.net>, James Kuyper Jr.
<kuyper@wizard.net> writes
>> In article <9g7599$7h7jf$1@ID-49767.news.dfncis.de>, Anthony Williams
>> <anthwil@nortelnetworks.com> writes
>> >Question: if I supply operator new[] and operator delete[] in one
>> >translation unit, are uses of new[] and delete[] in another translation unit
>> >guaranteed to use my functions, without explicitly declaring them?
>>
>> I think not. I think you have a major implicit breach of the ODR.
>
>I don't see how that applies - the basic thing the ODR rule says says,
>as it's name implies, is that there must be only one definition. When
>the user provides a replacement function, as specified in 17.4.3.4, that
>IS the one definition, as is made clear by 17.1.14.

But the problem is how exactly the buitlin operator new and operator
delete are provided. I do not think they are prohibited from being
inlined in which case the user provide version will not be used in
modules where the compiler is unaware of it.

Francis Glassborow      ACCU
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de>, Andrei Alexandrescu wrote:
> MSVC defines a function, _alloca, that allows you to allocate memory right
> on the stack at runtime. The allocation consist of a simple adjustment of
> stack pointers so it's O(1). Upon exiting the function, the memory is
> released in O(1) as well.

This has been touched on elsewhere in this thread, but I'm still
a little confused.
If I write


    void f( void )
    {
        char *p = new char[1000];

 // use p

 delete[] p;
    }


then can an implementation not use alloca (or equivalent) to allocate
this memory?  This is a real question (not just a rhetorical assertion =).
Obviously in real situations things get a little more complicated,
but it could get more useful if a compiler could do this for (inlined)
container ctors and dtors.

Thanks,

Ben.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Ben Cooling" <pmysbrc@nott.ac.uk> wrote in message
news:slrn9ic9sm.lr.brc@localhost.localdomain...
> In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de>, Andrei Alexandrescu
wrote:
> > MSVC defines a function, _alloca, that allows you to allocate memory
right
> > on the stack at runtime. The allocation consist of a simple adjustment
of
> > stack pointers so it's O(1). Upon exiting the function, the memory is
> > released in O(1) as well.
>
> This has been touched on elsewhere in this thread, but I'm still
> a little confused.
> If I write
>
>
>     void f( void )
>     {
>         char *p = new char[1000];
>
> // use p
>
> delete[] p;
>     }
>
> then can an implementation not use alloca (or equivalent) to allocate
> this memory?

It could I guess, in very limited cases. As soon as you pass any pointer
expression involving p as an argument to a function or as a source in an
assignment to a variable visible outside f(), the compiler cannot use
alloca() anymore unless it does quite tired data-flow analysis and/or
inter-procedural analysis.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Tue, 12 Jun 2001 17:55:27 GMT, Ben Cooling <pmysbrc@nott.ac.uk> wrote:
> In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de>, Andrei Alexandrescu wrote:
> > MSVC defines a function, _alloca, that allows you to allocate memory right
> > on the stack at runtime. The allocation consist of a simple adjustment of
> > stack pointers so it's O(1). Upon exiting the function, the memory is
> > released in O(1) as well.
>
> This has been touched on elsewhere in this thread, but I'm still
> a little confused.
> If I write
>
>
>     void f( void )
>     {
>         char *p = new char[1000];
>
>  // use p
>
>  delete[] p;
>     }
>
>
> then can an implementation not use alloca (or equivalent) to allocate
> this memory?  This is a real question (not just a rhetorical assertion =).
> Obviously in real situations things get a little more complicated,
> but it could get more useful if a compiler could do this for (inlined)
> container ctors and dtors.

An implementation can only do this if it can determine that no code
executed during "// use p" sets p to 0 or tries to delete[] p. In
particular, if the memory's address is somehow passed to another
function, using alloca() will in general not be possible.
For example:

   // translation unit 1:

   void g(char &cr);

   void f( void )
   {
      char *p = new char[1000];
      ... do some stuff ...
      g(p[500]);
      ... do some other stuff ...
      delete[] p;
   }


   // translation unit 2:

   void g(char &cr)
   {
      ... do some stuff ...
      delete[] (&cr - 500);   // not allowed to crash at this point
      ... do some other stuff ...
   }


-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <yu99n17d7cv8.fsf@europa.research.att.com>, Andrew Koenig
<ark@research.att.com> wrote:
>Ben> If I write
>Ben>     void f( void )
>Ben>     {
>Ben>         char *p = new char[1000];
>Ben>         // use p
>Ben>         delete[] p;
>Ben>     }
>Ben> then can an implementation not use alloca (or equivalent) to allocate
>Ben> this memory?  This is a real question (not just a rhetorical assertion =).
>
>No, it can't.
>
>Consider:

Even though I figure it is OK as long as one does not write code that
somehow may jump past the delete[].

Or do you have any such examples as well?

-- Alloca always sets the life of the memory allocation to the function it
is allocated within, as it is the parameter stack the allocation is put
on.

So, if one writes code that somehow tries to extend that built in life
time, the code will fail.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Ben Cooling" <pmysbrc@nott.ac.uk> wrote in message
news:slrn9ic9sm.lr.brc@localhost.localdomain...
> In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de>, Andrei Alexandrescu
wrote:
> > MSVC defines a function, _alloca, that allows you to allocate memory
right
> > on the stack at runtime. The allocation consist of a simple adjustment
of
> > stack pointers so it's O(1). Upon exiting the function, the memory is
> > released in O(1) as well.
>
> This has been touched on elsewhere in this thread, but I'm still
> a little confused.
> If I write
>
>
>     void f( void )
>     {
>         char *p = new char[1000];
>
> // use p
>
> delete[] p;
>     }
>
>
> then can an implementation not use alloca (or equivalent) to allocate
> this memory?  This is a real question (not just a rhetorical assertion =).
> Obviously in real situations things get a little more complicated,
> but it could get more useful if a compiler could do this for (inlined)
> container ctors and dtors.

No, it can't. The user is free to supply their own version of operator new[]
and operator delete[], which they can expect to be called in all
circumstances.

Question: if I supply operator new[] and operator delete[] in one
translation unit, are uses of new[] and delete[] in another translation unit
guaranteed to use my functions, without explicitly declaring them?

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Leon Widdershoven" <l.widdershoven@fz-juelich.de> wrote in message
news:3B1E551E.635BF8B4@fz-juelich.de...
> If speed of memory allocation and deallocation is critical, what I
> suspect
> it is since you stress _alloca is O(1), you might wish to take a look at
> placement new.
> This allows you to allocate a big memory stack (uninitialized) for
> instance
> with new char[ very_much] and then allocate and deallocate all kinds of
> objects within this memory area.

That won't work because the very purpose is to occupy a reasonable amount of
memory and not "very_much". Placement new only helps creating objects, it
doesn't have anything to do with allocating memory.

> Or, alternatively, you can give time-critical classes which create and
> destroy
> instances all the time their own memory management, for instance a list
> of
> pre-allocated objects (allocated if the first instance is allocated) and
> use the next free object in the pool the next time. This saves some of
> the
> time of using the plain "new".

That's what good allocators do anyway.

> How this behaves in a threaded environment,  I don't know.

Each thread has its own stack, so alloca doesn't have any trouble with
threads.

> I think, with new, placement new, and memory management implementable in
> individual
> classes (operators new and delete) C++ at this moment already has quite
> a
> versatile memory 'subsystem'.

Not quite. There's no in-place memory expansion and shrinkage, there's no
efficient object movement without the co-operation of the user, alignment
computation is not portable... oh boy. It's quite bad actually.

> What would be the precise benefits of alloca?

Speed. But, as pointed out by Matt Austern, Bjarne Stroustrup, and (ahem)
yours truly, alloca's fatal flaw is that it's useless to developing and
using libraries because it must be called by the user.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Phil Edwards wrote:
>
> In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de> you write:
> > MSVC defines a function, _alloca, that allows you to allocate memory right
> > on the stack at runtime. The allocation consist of a simple adjustment of
> > stack pointers so it's O(1). Upon exiting the function, the memory is
> > released in O(1) as well.

If speed of memory allocation and deallocation is critical, what I
suspect
it is since you stress _alloca is O(1), you might wish to take a look at
placement new.
This allows you to allocate a big memory stack (uninitialized) for
instance
with new char[ very_much] and then allocate and deallocate all kinds of
objects within this memory area.
Or, alternatively, you can give time-critical classes which create and
destroy
instances all the time their own memory management, for instance a list
of
pre-allocated objects (allocated if the first instance is allocated) and
use the next free object in the pool the next time. This saves some of
the
time of using the plain "new".
How this behaves in a threaded environment,  I don't know. I suppose you
need
to have a lock while allocating, but then again, plain new also needs to
lock
when it is allocating memory.

I think, with new, placement new, and memory management implementable in
individual
classes (operators new and delete) C++ at this moment already has quite
a
versatile memory 'subsystem'.
What would be the precise benefits of alloca?
(I never used alloca, so in this respect please enlighten me, if you
wish).

Leon

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Vesa Karvonen" <vesa.karvonen@hNoOuSsPeAmMarque.fi> wrote in message
news:MUNP6.365$0d3.4092@read2.inet.fi...
> James Kuyper Jr. wrote:
> > Andrei Alexandrescu wrote:
> > ...
> > > There are people I know who cannot use vector because it's too slow,
> copies
> > > memory unnecessarily (and inefficiently), constructs values
> unnecessarily
> > > (and inefficiently) even when they are of primitive types and will be
> > > initialized by a low-level routine in the next step.
> >
> > That sounds like a defective implementation of (or perhaps a failure to
> > use?) vector::reserve().
>
> #if ANGRY_BUT_VALID_STATEMENTS_ALLOWED
>
> I can't use vector<> or just about any other standard container because
they
> are not quaranteed to free or deallocate any memory in their lifetime.

Is an object's destructor executed "during its lifetime"? The container
requirements (23.1 - table 65) read:

-------
(&a)->~X(); void linear
note: the destructor is applied
to every element of a; all the
memory is deallocated.
-------

-Dave



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

David Abrahams wrote:
>
> "Vesa Karvonen" <vesa.karvonen@hNoOuSsPeAmMarque.fi> wrote in message
> news:MUNP6.365$0d3.4092@read2.inet.fi...
> > James Kuyper Jr. wrote:
> > > Andrei Alexandrescu wrote:
> > > ...
> > > > There are people I know who cannot use vector because it's too slow,
> > copies
> > > > memory unnecessarily (and inefficiently), constructs values
> > unnecessarily
> > > > (and inefficiently) even when they are of primitive types and will be
> > > > initialized by a low-level routine in the next step.
> > >
> > > That sounds like a defective implementation of (or perhaps a failure to
> > > use?) vector::reserve().
> >
> > #if ANGRY_BUT_VALID_STATEMENTS_ALLOWED
> >
> > I can't use vector<> or just about any other standard container because
> they
> > are not quaranteed to free or deallocate any memory in their lifetime.
>
> Is an object's destructor executed "during its lifetime"?

I think not.  The object's lifetime ends when the destructor's
execution begins, just as its lifetime begins when its constructor
terminates normally (rather than by throwing an exception).
That's based on common usage though, rather than anything I've
read in the Standard.

-- James Dennett

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Wed, 30 May 2001 01:58:46 GMT, Bjarne Stroustrup <bs@research.att.com>=
 wrote:
[=B7=B7=B7]
> I see exactly one fundamental performance problem with vector: it alway=
s
> performs initialization. This can be a problem for people who want to
> use a vector to import a lot of POD from "elsewhere" - in that case, th=
e
> initialization is simply overhead. For most uses, the guaranteed
> initialization is a major advantage.
>=20
> I suspect that I'd rather try to find a good solution to that spceific
> problem  than starting to recommend a variety of incompatible,
> confusing, and generally lower-level solutions. IMO people spend too
> much time messing around with the lowest level of memory and allocation.

While that is probably true, IMHO C++ should provide those lower-level
mechanism in some way for those who (decide that they) need it. The
mechanism need not be inherently confusing. It is one prominent feature
of C++ (inherited from C) that it continues to expose the distinction
between storage space and the values mapped onto it (or vice versa),
and that it intertwines powerful abstractions with their transparent
mapping onto the lower-level machine model without forcing any
non-obligatory consessions or overhead with regard to the lower-level
model and the related efficiency considerations. Hence it should provide
sufficient facilities to fully handle this conceptual model. Placement
new() is one example where C++ was actually enhanced to better provider
such support. The fact that there is underlying "raw memory" should not
be viewed as a necessary evil, but instead should be accepted as a
rightful base concept that can legitimately be fully manipulated
whenever the programmer feels the need for doing so. While it is a good
thing that C++ tries to make life safe for the "regular" programming
tasks, this should not prevent the lower-level world to be manipulated
in a equally safe and standard manner.

With regard to VLAs, to pick an example, I don't think it's quite in the
spirit of C++ to say "ah, but heap allocation will be fast enough for
everyone". The programmer should be given the freedom (and the
facilities) to decide, not C++.

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9ec2qt$25uu5$1@ID-14036.news.dfncis.de...
: MSVC defines a function, _alloca, that allows you to allocate memory right
: on the stack at runtime. The allocation consist of a simple adjustment of
: stack pointers so it's O(1). Upon exiting the function, the memory is
: released in O(1) as well.
:
: C99 supports such variable-length stack allocation through variable length
: arrays (VLAs). I think this would be a interesting function to add to C++
: with a C++ flavor to it (guaranteed destruction and all). Better yet, it
: would be great if C++ offered the ability to allocate an array on the
caller
: function's stack, so you can create automatic objects that hold
: variable-length data without having to perform any access to the free
store.
: Wow that would be cool.
:
: Any thoughts?
:

Andrei,

I am pretty sure that you are aware of ways to achieve alloca-like behaviour
AND performance in some other ways. What comes to my mind is something like
this:

    - designate a linear chunk of memory for 'alloca' 'heap'
    - define a 'current pointer' there
    - define a class called e.g. Alloca
        - whose constructor advances the pointer by the desired amount of
memory
        - whose destructor restores the pointer
        - make it uncopyable and otherwise protected
        - add a conversion to void* (to return the 'old' pointer)
    - use it like this:
        {
        .....
        Alloca a (bytes_count);
        void* my_memory = a;
        // do whatever with this memory
        .....
        } // 'a's destructor called, pointer moved back

    - if appropriate, add some bells an whistles (paging, exceptions, array
templates, etc)

    - add it to YASTLI :-)

Radoslav Getov



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Vesa Karvonen" <vesa.karvonen@hNoOuSsPeAmMarque.fi> wrote in message
news:MUNP6.365$0d3.4092@read2.inet.fi...
> James Kuyper Jr. wrote:
> > Andrei Alexandrescu wrote:
> > ...
> > > There are people I know who cannot use vector because it's too slow,
> copies
> > > memory unnecessarily (and inefficiently), constructs values
> unnecessarily
> > > (and inefficiently) even when they are of primitive types and will be
> > > initialized by a low-level routine in the next step.
> >
> > That sounds like a defective implementation of (or perhaps a failure to
> > use?) vector::reserve().
>
> #if ANGRY_BUT_VALID_STATEMENTS_ALLOWED
>
> I can't use vector<> or just about any other standard container because
they
> are not quaranteed to free or deallocate any memory in their lifetime.

Is an object's destructor executed "during its lifetime"? The container
requirements (23.1 - table 65) read:

-------
(&a)->~X(); void linear
note: the destructor is applied
to every element of a; all the
memory is deallocated.
-------

-Dave





---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

James Dennett <jdennett@acm.org> writes:

| I think not.  The object's lifetime ends when the destructor's
| execution begins, just as its lifetime begins when its constructor
| terminates normally (rather than by throwing an exception).
| That's based on common usage though, rather than anything I've
| read in the Standard.

Actually, the Standard's words are 3.8/1

  [...]
  The lifetime of an object of type T ends when:
   - if T is a class type with a non-trivial destructor (12.4), the
     destructor call starts, or
   - the storage which the object occupies is reused or released.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"David Abrahams" <abrahams@mediaone.net> writes:

| "Vesa Karvonen" <vesa.karvonen@hNoOuSsPeAmMarque.fi> wrote in message
| news:MUNP6.365$0d3.4092@read2.inet.fi...
| > James Kuyper Jr. wrote:
| > > Andrei Alexandrescu wrote:
| > > ...
| > > > There are people I know who cannot use vector because it's too slow,
| > copies
| > > > memory unnecessarily (and inefficiently), constructs values
| > unnecessarily
| > > > (and inefficiently) even when they are of primitive types and will be
| > > > initialized by a low-level routine in the next step.
| > >
| > > That sounds like a defective implementation of (or perhaps a failure to
| > > use?) vector::reserve().
| >
| > #if ANGRY_BUT_VALID_STATEMENTS_ALLOWED
| >
| > I can't use vector<> or just about any other standard container because
| they
| > are not quaranteed to free or deallocate any memory in their lifetime.
|
| Is an object's destructor executed "during its lifetime"?

An object's lifetime ends precisely when its destructor execution starts.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <dilae3w6r6a.fsf@isolde.research.att.com>, Matthew Austern
<austern@research.att.com> wrote:
>I dislike alloca because it interacts poorly with libraries.  You have
>to use it in the highest level user code; you can't hide the details
>by wrapping alloca inside a function.  The reason: if you wrap alloca
>inside a utility function then memory is allocated in the utility
>function's stack frame, not the stack frame of whoever calls that
>utility function.  I suppose it might work if you could somehow
>guarantee that the function gets inlined, but (a) that's fragile; (b)
>there's no way to guarantee that a function will be inlined; and (c) I
>don't think anyone has clarified just how alloca interacts with
>inlining.)

One way might be to use more than one parameter stack: The constructor
uses its own local stack, but allocates on the "main" stack.

Probably an overkill if the idea is just to get alloca working with C++.

But if one cannot integrate stack allocation techniques into normal C++
programming styles, it is quite useless.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Radoslav Getov" <nospam@mai.com> wrote in message
news:tha2o9gq1ebvad@corp.supernews.com...
> I am pretty sure that you are aware of ways to achieve alloca-like
behaviour
> AND performance in some other ways. What comes to my mind is something
like
> this:
>
>     - designate a linear chunk of memory for 'alloca' 'heap'
>     - define a 'current pointer' there
>     - define a class called e.g. Alloca
>         - whose constructor advances the pointer by the desired amount of
> memory
>         - whose destructor restores the pointer

It's more complicated than that.  alloca space is associated
with a function, not a scope.  The alloca calls can happen
anywhere, e.g. in a loop.  The destructor is called once,
just before the function returns.  You have to write e.g.

  f() {
    AllocaSpace space;
    for (...) {
      void *p = space.alloca(bytes_count);
      ...
    }
    // ~AllocaSpace releases the memory
  }

or get the compiler to do that for you.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bjarne Stroustrup wrote:
>
> but is it too slow in practice? - and if so, how often for how many people?
>
> I see exactly one fundamental performance problem with vector: it always
> performs initialization. This can be a problem for people who want to
> use a vector to import a lot of POD from "elsewhere" - in that case, the
> initialization is simply overhead. For most uses, the guaranteed
> initialization is a major advantage.
>

Initialization is a problem if and only if you don't know your data by
the time you start to manipulate them. It's a poor design.

The "elswhere" is stable (keeps its data untouched as long as the
consumer wants) or unstable (the data are stored in a reusable buffer
that should be evacuated as soon as possible).

If it is stable, then write an iterator on it. No copy, no trouble.

If it is not stable, then the data will come into chunks of no more than
a given size (buffer size or so). Use deque<> if you need a random
access to them: you know how to configure them so that one and only one
copy of the data will take place, exactly like with C.

It is amazing how many people need to copy data from system buffers,
while most system API require user provided buffers.

IMO, data that cannot be initialized cannot be thought of.

--
Yannick de Kercadio
kercadio@limsi.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Al Grant wrote:

[...]

> It's more complicated than that.  alloca space is associated
> with a function, not a scope.

Then alloca is misdesigned IMHO. Atomatic foo ends at scope end.
Why should this rule be broken if foo == memory?

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Ross Smith wrote:
>
> "James Kuyper Jr." wrote:
> >
> > [ on reserve()+push_back() vs uninitialised allocation ]
> >
> > It's not appropriate for random initialization, I'll grant you. However,
> > I didn't expect that random initialization would be a common need for
> > that kind of application. push_back() should be just about as efficient
> > as any other possible method of filling in uninitialized memory, when
> > performing sequential initializations into reserved space. If you can
> > find any way to represent the initialization as an input iterator, an
> > insert() using an iterator range would be even more approrpriate.
>
> An example of the sort of situation I'm thinking of is initialising an
> image buffer with part of another image. This can be handled with a
> series of memcpys, one row at a time. In principle a series of
> push_backs can be optimised down to the same thing, but push_back (if
> not throughly optimised) has the overhead of checking the size and
> incrementing it each time, and I'm far from convinced that such
> sophisticated optimisation can be relied on, even in theory. Certainly
> present-day compilers are nowhere near it.

If you have another image, you should have begin and end pointers
for each chunk (possibly just as pointers into memory). Therefore
the correct thing to do is _not_ individual push_backs, but a
single insert at end.

>
> I did some quick benchmarks to check. These times are for copying 1 GB
> of data in 1 MB chunks (on a PIII/450, with maximum optimisation on all
> compilers):
>
>                            GCC 2.95.3  MSVC 6.0
> memcpy()                   15.7 s      16.0 s
> loop over push_back()      59.9 s      108.4 s
> copy() into back_inserter  60.3 s      105.7 s

This last one should IMHO get optimized by the std library.
It should even be quite simple to do so: If the destination is a
std::back_insert_iterator, then don't do the loop, but just call
the container's insert function.

That is, std::copy would have an overload

template<class Iter, class Container>
 void copy(Iter first, Iter last,
           back_insert_iterator<Container> out)
{
  Container& c = out.__get_container();
  c.insert(c.end(), first, last);
}

Of course I'd also expect vector::insert to have a specialized
version for random access iterators, which checks the capacity
and adjusts the size just once.

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." wrote:
>
> [ on reserve()+push_back() vs uninitialised allocation ]
>
> It's not appropriate for random initialization, I'll grant you. However,
> I didn't expect that random initialization would be a common need for
> that kind of application. push_back() should be just about as efficient
> as any other possible method of filling in uninitialized memory, when
> performing sequential initializations into reserved space. If you can
> find any way to represent the initialization as an input iterator, an
> insert() using an iterator range would be even more approrpriate.

An example of the sort of situation I'm thinking of is initialising an
image buffer with part of another image. This can be handled with a
series of memcpys, one row at a time. In principle a series of
push_backs can be optimised down to the same thing, but push_back (if
not throughly optimised) has the overhead of checking the size and
incrementing it each time, and I'm far from convinced that such
sophisticated optimisation can be relied on, even in theory. Certainly
present-day compilers are nowhere near it.

I did some quick benchmarks to check. These times are for copying 1 GB
of data in 1 MB chunks (on a PIII/450, with maximum optimisation on all
compilers):

                           GCC 2.95.3  MSVC 6.0
memcpy()                   15.7 s      16.0 s
loop over push_back()      59.9 s      108.4 s
copy() into back_inserter  60.3 s      105.7 s

(For the memcpy() test, the destination was allocated with new[]; for
the other two, it was a vector with space reserved but not initialised.)

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
        "Hungarian notation is the tactical nuclear weapon of
         source code obfuscation techniques." -- Roedy Green

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Mon, 28 May 2001 23:00:43 GMT Andrei Alexandrescu =CE=C1=D0=C9=D3=C1=CC:
>Quite frankly, I don't care much for alloca anymore, but just to confirm
>something: the static stack frame of any function is computed at compile
>time, which means 'a' above already has memory for it before the call to
>alloca().

No, you can't detect nesting level at compile time, so you can't determin=
e=20
at compile time if memory for whole stack is enough.

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <GDzzB0.Bpw@research.att.com>, bs@research.att.com (Bjarne
Stroustrup) wrote:
>> >bs@research.att.com (Bjarne Stroustrup) wrote:
>> > ...
>> >In case of alloca(), it also should be taken into account that it is a low
>> >level mechanism that doesn't directly support types with constructors and
>> >destructors, that it isn't exception safe, that there exist machine
>> >architectures with limited stack space, and that it imposes the burden of
>> >checking that an allocation succeeded on the individual programmer.
>>
>> I am not sure what can go wrong with exceptions here, because alloca is
>> just allocating memory on the parameter stack, which is unwound in the
>> case of a exception is thrown. So I do not see how memory leaks can occur.
>
>You are right, when mentioning exception safety, I was thinking of VLAs.
>Sorry.

Ha, ha. Gotcha! :-)

But seriously, I was thinking along the lines of making a more general
version of alloca(), more suitable for integration into C++. -- Perhaps
one can that way give more light to the problem whether it really is worth
having it in the C++ standard:

Then alloca comes with some severe limits, one cannot re-allocate memory,
and further, the allocation is temporary in nature.

Suppose one would want to amend that, then one ends up with a operator
new/delete pair which allocates memory on the parameter stack instead of
on the heap. In addition, if an object is living longer than the stack
allocation (for example, returned temporaries), it must be moved, probably
by the copy constructor.

The benefit of such a version of alloca is even less than the original
alloca. On the other hand, it might still be faster than putting objects
in the heap in some cases: If one does not make too many re-allocations,
allocations might be fast, and there is a way to avoid memory
fragmentation, namely to regularly let the functions expire.

On the other hand, one might achieve the same effect by writing a version
of operator new that writes into a reserved block of memory on the heap.
Then one can make a cleanup by killing off the whole block. (This is
essentially what the OS does when reserving a memory space to a whole
program.)

So then one is back to square one, writing better operator new/delete
pairs and the conservative GC question.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Ross Smith" <ross.s@ihug.co.nz> wrote in message
news:3B12F565.E36F85BE@ihug.co.nz...
> "James Kuyper Jr." wrote:
> >
> > [ on reserve()+push_back() vs uninitialised allocation ]
> >
> > It's not appropriate for random initialization, I'll grant you. However,
> > I didn't expect that random initialization would be a common need for
> > that kind of application. push_back() should be just about as efficient
> > as any other possible method of filling in uninitialized memory, when
> > performing sequential initializations into reserved space. If you can
> > find any way to represent the initialization as an input iterator, an
> > insert() using an iterator range would be even more approrpriate.
>
> An example of the sort of situation I'm thinking of is initialising an
> image buffer with part of another image. This can be handled with a
> series of memcpys, one row at a time. In principle a series of
> push_backs can be optimised down to the same thing, but push_back (if
> not throughly optimised) has the overhead of checking the size and
> incrementing it each time, and I'm far from convinced that such
> sophisticated optimisation can be relied on, even in theory. Certainly
> present-day compilers are nowhere near it.
>
> I did some quick benchmarks to check. These times are for copying 1 GB
> of data in 1 MB chunks (on a PIII/450, with maximum optimisation on all
> compilers):
>
>                            GCC 2.95.3  MSVC 6.0
> memcpy()                   15.7 s      16.0 s
> loop over push_back()      59.9 s      108.4 s
> copy() into back_inserter  60.3 s      105.7 s
>
> (For the memcpy() test, the destination was allocated with new[]; for
> the other two, it was a vector with space reserved but not initialised.)

Add a fourth test using vector.insert(blockStart,blockStart+blockSize) - I
would expect it to be nearer the memcpy times for a decent implementation.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Ross Smith wrote:
>
> "James Kuyper Jr." wrote:
> >
> > [ on reserve()+push_back() vs uninitialised allocation ]
> >
> > It's not appropriate for random initialization, I'll grant you. However,
> > I didn't expect that random initialization would be a common need for
> > that kind of application. push_back() should be just about as efficient
> > as any other possible method of filling in uninitialized memory, when
> > performing sequential initializations into reserved space. If you can
> > find any way to represent the initialization as an input iterator, an
> > insert() using an iterator range would be even more approrpriate.
>
> An example of the sort of situation I'm thinking of is initialising an
> image buffer with part of another image. This can be handled with a
> series of memcpys, one row at a time. In principle a series of
> push_backs can be optimised down to the same thing, but push_back (if
> not throughly optimised) has the overhead of checking the size and
> incrementing it each time, and I'm far from convinced that such
> sophisticated optimisation can be relied on, even in theory. Certainly
> present-day compilers are nowhere near it.

For that application, you should be able to use insert() with an
iterator range for each row. In that case, the size need only be updated
once per row.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Tue, 29 May 2001 12:40:56 GMT, Eugene Karpachov <jk@steel.orel.ru> wro=
te:
> Mon, 28 May 2001 23:00:43 GMT Andrei Alexandrescu =CE=C1=D0=C9=D3=C1=CC=
:
> >Quite frankly, I don't care much for alloca anymore, but just to confi=
rm
> >something: the static stack frame of any function is computed at compi=
le
> >time, which means 'a' above already has memory for it before the call =
to
> >alloca().
>=20
> No, you can't detect nesting level at compile time, so you can't determ=
ine=20
> at compile time if memory for whole stack is enough.

What he meant to say is that stack overflow doesn't usually occur at
inner blocks (within a function), because the stack frame containing the
storage vor variables oth the inner block are already allocated upon
entering the outer block (the function body). Therefore stack overflow
could only occur upon entering a function, and not upon entering some
block in the middle of a function.

While this is probably true for many implementations, it's nothing
mandated by the standard, and hence nothing to be relied upon.

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

bs@research.att.com (Bjarne Stroustrup) writes:

> I happen to think that alloca() is a low level hack that provides less
> performance benefit that people -without evidence - assume/claim. I have
> no doubt that people can find examples/implementations where alloca() - or
> VLAs - performs better than std::vector (after all, I did present one such
> case in my original message). However, for anyone to seriously argue for
> a change to the standard or even for a change in the way people write code,
> some form of evidence should be presented - not just arguments.

My complaint about alloca has nothing to do with performance.

I dislike alloca because it interacts poorly with libraries.  You have
to use it in the highest level user code; you can't hide the details
by wrapping alloca inside a function.  The reason: if you wrap alloca
inside a utility function then memory is allocated in the utility
function's stack frame, not the stack frame of whoever calls that
utility function.  I suppose it might work if you could somehow
guarantee that the function gets inlined, but (a) that's fragile; (b)
there's no way to guarantee that a function will be inlined; and (c) I
don't think anyone has clarified just how alloca interacts with
inlining.)

So you can't use alloca to write a container class whose constructor
allocates memory (or any other resource-acquisition-is-initialization
class that involves memory allocation), you can't use alloca to write
an STL allocator (I thought about this one for a long time before
convincing myself it couldn't be done), you can't use alloca inside a
function that returns a pointer to newly allocated memory.  Generic
code that's written to use arbitrary memory allocation policies can't
use alloca.

The problem is that when you're writing a utility component, you
really don't want "allocate this on my stack frame".  You want
something more like "allocate this on my parent's stack frame".  Or
maybe you want a language where stack frames are first class objects,
and where alloca would take a stack frame pointer as an argument.  But
this is starting to look pretty different from C++.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> IIRC this all comes from list's splice - a useful function that has
> trouble deallocating elements if you splice lists bearing different
> allocators. Are there other reasons for which allocators are forced
> not to store state and to be all equivalent?

If the allocator instances are not equivalent, then containers will have
store a reference to their allocator, which will be overhead. For
example, currently an empty std::vector can be stored in 3 words. With
your change, it will need 4 words. This cost will be incurred even by
people who never use the extra allocator functionality.

I'm not sure I see the relevance to the alloca() comparison, anyway.
Alloca() only has access to one, implicit memory space, namely the stack.
An allocator which uses a single static buffer would be no worse off. It
doesn't need extra per-instance state.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010529184022.31511A@brangdon.madasafish.com...
> andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > IIRC this all comes from list's splice - a useful function that has
> > trouble deallocating elements if you splice lists bearing different
> > allocators. Are there other reasons for which allocators are forced
> > not to store state and to be all equivalent?
>
> If the allocator instances are not equivalent, then containers will have
> store a reference to their allocator, which will be overhead. For
> example, currently an empty std::vector can be stored in 3 words. With
> your change, it will need 4 words. This cost will be incurred even by
> people who never use the extra allocator functionality.

Not if the compiler implements EBO and the implementer takes advantage of
it. Which is the case for many current compilers that I know.

> I'm not sure I see the relevance to the alloca() comparison, anyway.
> Alloca() only has access to one, implicit memory space, namely the stack.
> An allocator which uses a single static buffer would be no worse off. It
> doesn't need extra per-instance state.


True. My only point is that to make allocators useful they must be allowed
to store state.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <dilae3w6r6a.fsf@isolde.research.att.com>, Matthew Austern
<austern@research.att.com> wrote:

>My complaint about alloca has nothing to do with performance.
>
>...  You have
>to use it in the highest level user code; you can't hide the details
>by wrapping alloca inside a function.  The reason: if you wrap alloca
>inside a utility function then memory is allocated in the utility
>function's stack frame, not the stack frame of whoever calls that
>utility function.
...
>So you can't use alloca to write a container class whose constructor
>allocates memory (or any other resource-acquisition-is-initialization
>class that involves memory allocation), ...

Actually, I overlooked that aspect when thinking about alloca (so the
example I posted before is wrong): It means alloca has nothing to do in
normal C++ programming, as the normal way would be to wrap up such low
level functions in a container class.

The only reason alloca could be added then is because it is already in
use, and one want to make it easier to use already existing code.

As for the memory allocation technique, on the parameter stack, one should
then provide another function that can be used to wrap up in containers.
That is, if one cannot provide as efficient heap memory allocation
techniques.

Here is an example which I try to focus on right now:

Suppose one want a multi-precision integer that can compete as much as
possible in terms of speed with the integral types. Then for small
numbers, one want to use unboxed (no dynamic allocation) numbers, with an
overflow check. The overflow check, I am told, is always available on the
assembler level, but it is not available within C/C++. So without using
assembler or a C/C++ language extension, one is bound to spill some cycles
here.

Now, if there is an overflow, one has to switch to boxed (dynamic
allocation) numbers. But the dynamic allocation might still be small.
Therefore, one wants it to be as fast as possible, given that it is on
such a low level.

So if there is a speed gain in putting on the stack, one would want that.
On the other hand, the wrap should be a class "integer", and the user
should not have to know where the number is allocated, or have to deal
with life-time restrictions or any such.

One might replace this integer class with a string class instead.

Clearly, in such an example, it does not make any difference where the
memory allocation is done, only the overall speed. If one can do that
nearly as fast on the heap as on the stack, no stack allocation function
would be needed.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <GDyHrB.A2L@research.att.com>, bs@research.att.com (Bjarne
Stroustrup) wrote:
>remove.haberg@matematik.su.se (Hans Aberg) writes:
>
>> bs@research.att.com (Bjarne Stroustrup) wrote:
>> > ...
>> >I think people should think a little harder before they recommend stack
>> >allocation (or VLAs) on efficiency grounds.
>>
>> I think though that free store allocations can be fast under circumstances
>> when there is plenty of memory and memory is not fragmented. And one has
>> to add the times for deallocations as well: Fast allocation times may show
>> up as a beating on the deallocation times.
>>
>> So then the advantage of alloca might turn out to be more significant when
>> such factors are taken into account.
>
>It might, and it might not.
>
>My point is that people have to do better than conjecturing when they argue
>for additions to the standard.
>
>I happen to think that alloca() is a low level hack that provides less
>performance benefit that people -without evidence - assume/claim.

The original reason that I saw for introducing alloca is that it appears
in some libraries, like those of GNU, and further my non-GNU compiler has
alloca because it is even supplied by the OS.

So if this alloca is already present and in use, it would simplify to have
it in the standard.

As for the other aspect, performance benefit, is just another memory
allocation technique: I figure that the best thing for people that really
need optimization is to run the program at hand through a profiler, and
then choose the variation that gives the best performance.

>From that point of view perhaps alloca should viewed as just another
variation of "operator new" or an allocator, so it is easy to switch in a
program. One then does not get alloca itself, but a parameter stack
"operator new" or allocator, which would be better for use with C++ code.

Perhaps alloca is a C standard issue, and the non-alloca parameter stack
allocations is the C++ standard issue.

One application where parameter stack allocations might be preferred might
be a multiprecision numerics library, because the memory allocations will
take up so much time over the numerical operations.

>In case of alloca(), it also should be taken into account that it is a low
>level mechanism that doesn't directly support types with constructors and
>destructors, that it isn't exception safe, that there exist machine
>architectures with limited stack space, and that it imposes the burden of
>checking that an allocation succeeded on the individual programmer.

I am not sure what can go wrong with exceptions here, because alloca is
just allocating memory on the parameter stack, which is unwound in the
case of a exception is thrown. So I do not see how memory leaks can occur.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Sat, 26 May 2001 11:24:56 GMT Andrei Alexandrescu =CE=C1=D0=C9=D3=C1=CC:
>Interesting. You'd agree, however, that the test is not very conclusive.=
 The
>allocation pattern of your test program would make the day of any memory
>allocator writer: you simply allocate and deallocate the same memory siz=
e

BTW, it is the only pattern available with alloca().

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu <andrewalex@hotmail.com> wrote...
>
> I guess that on many architectures, programs know how much
> stack have allocated for them and so checking for availability
> is only one comparison away.

If you are in any danger of running out of stack space, then your
biggest risk is not omitting to check the call to alloca, it is
that the compiler almost certainly doesn't check for adequate stack
space when it sets up a frame.

   if (char* p=alloca(LOTS))
   {
      int a;
      // ...
   }

The alloca() may succeed, only for your program to crash when the
compiler starts using "a". Then again, you don't need to use alloca
to risk running out of stack space, so perhaps this whole question
is unimportant. Then again again, it is probably easier to discover
the maximum stack usage for a program that doesn't use alloca than
for one that does. By its nature, you will be using alloca because
you don't know at compile time how much space you will need.

My vote goes for the custom allocator suggested by Dave Harris in
a nearby post. Like alloca, it can be implemented in a handful of
instructions, though perhaps not quite as few. Unlike alloca, it
is not limited to the stack space of your program.

> Then, alloca can simply return zero.

Surely you mean throw std::bad_alloc()?
We don't actually want to have to check this return value, do we?






---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Mon, 28 May 2001 09:55:43 GMT, Eugene Karpachov <jk@steel.orel.ru> wro=
te:
> Sat, 26 May 2001 11:24:56 GMT Andrei Alexandrescu =CE=C1=D0=C9=D3=C1=CC=
:
> >Interesting. You'd agree, however, that the test is not very
> >conclusive. The allocation pattern of your test program would make
> >the day of any memory allocator writer: you simply allocate and
> >deallocate the same memory size
>=20
> BTW, it is the only pattern available with alloca().

Which may be mixed with allocations via new(), though. When using new()
instead of alloca(), additional new() allocations with random patterns
have to be taken into account.

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Gabriel Dos Reis" <dosreis@cmla.ens-cachan.fr> wrote in message
news:flk834yoza.fsf@sel.cmla.ens-cachan.fr...
> "Andrei Alexandrescu" <andrewalex@hotmail.com> writes:
>
> [...]
>
> | > vector is more general than a VLA, efficient, standard, and available
now.
> |
> | There are people I know who cannot use vector because it's too slow
>
> Is it too slow because of their particular implementation or is it
> because of vector inherent semantics?


It's slow in principle - does too many things.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Ross Smith wrote:
>
> "James Kuyper Jr." wrote:
> >
> > Ross Smith wrote:
> > >
> > > Recently I was working on some graphics code for which I ended up
> > > writing my own dynamic array class, essentially identical to vector
> > > except that the elements were left uninitialised by default. I needed it
> > > because the code was intended to deal with potentially quite large
> > > images (tens of megabytes), and the overhead of zero-initialising a
> > > newly allocated image buffer was unacceptable.
> >
> > Why didn't you just reserve() the space? That should have the same
> > effect.
>
> No it shouldn't. reserve() only guarantees no reallocation as long as
> the vector's size stays below the reserved value; it doesn't give you
> access to the reserved elements until you actually resize() the vector,
> or add them in some other way such as push_back(). Accessing the
> reserved elements immediately is cheating; it may work on some
> implementations, but it's not permitted by the standard.

It's not appropriate for random initialization, I'll grant you. However,
I didn't expect that random initialization would be a common need for
that kind of application. push_back() should be just about as efficient
as any other possible method of filling in uninitialized memory, when
performing sequential initializations into reserved space. If you can
find any way to represent the initialization as an input iterator, an
insert() using an iterator range would be even more approrpriate.

Of course the ideal would be if you can construct the vector<> directly
from a random-access iterator range; in that case you could rely on the
constructor itself to efficiently determine the amount of memory needed
simply by calling std::distance(first,last). However, that's such an
obvious solution that I've assumed there must be some reason why it's
infeasible in your application.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3B0FA378.39F283CC@wizard.net...
> > Andrei Alexandrescu wrote:
> > ...
> > > There are people I know who cannot use vector because it's too slow,
> copies
> > > memory unnecessarily (and inefficiently), constructs values
> unnecessarily
> > > (and inefficiently) even when they are of primitive types and will be
> > > initialized by a low-level routine in the next step.
> >
> > That sounds like a defective implementation of (or perhaps a failure to
> > use?) vector::reserve().
>
> That won't work. Do this with vector efficiently:
>
> 1. Make a vector of N bytes
> 2. Pass the address of the memory to some file API to read data into it
> 3. Perform some transformations on the data that can potentially increase
> data size
> 4. Pass the address of the memory to some socket function to write it out
>
> With vector you'll get an unnecessary initialization in step 1 that you
> can't get rid of, and a reallocation pessimization in step 3 that you cannot
> get rid of (the vector won't be expanded in place even though there might be
> available memory there).

Agreed; when you work with C-style interfaces that require pointers to
arrays, such as the file API and socket interface you describe, you may
be better off using more C-oriented approaches: malloc(), fread(),
realloc(), and your socket function, for example.

A more C++ oriented approach to that problem would construct an empty
vector, reserve() the required space, then insert() the data using an
input iterator and the count (which you've implied is known in advance).
If further size changes are likely to occur, either over-reserve() by
enough to cover the additions, or use deque<> instead of vector<>.
Finally, the socket interface would accept an output iterator range, as
an alternative to a pointer to an array. You could probably build
efficient C++ wrappers for the file API and the socket function to
support this approach, even if the file API and socket function can
neither be re-written nor bypassed.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bjarne Stroustrup wrote:
...
> There is no reason for vector not to know how to expand without copying
> when adjasent memory is available. However, I don't know if current
> implementations are as smart as realloc() in this - if not, they can easily
> be made so.

I'm not sure how a container could do this. The allocator interface
provides no way of knowing when adjacent memory is available, nor any
way to merge adjacent allocations.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
[...]
> (the vector won't be expanded in place even though there might be
> available memory there).

This has never bothered me because I have
never seen any data related to how much time realloc() saves
by expanding an existing non-zero length buffer to a larger size
in place without copying.

I know that it would be easy to come up with a test program
that would make realloc() look good.
But, my gut tells me that the time saved by realloc doing this in a
real application is tiny.  But, as I say, I have never seen
any data.  Does anyone have any data on this?

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <200105262215.AAA23472@brick.ens.fr>, Valentin.Bonnard@free.fr
(Valentin Bonnard) wrote:
>Hans Aberg wrote:
>
>[About alloca]
>> It should be possible to make a wrap doing this [using heap if alloca fails]
>
>Do you mean that you know how to wrap alloca ?

No, I do not see the details about how to wrap alloca itself, so I do not
know if it is possible to do it within current C++ or if there is a needed
extension to the language.

One can write classes behaving like this (pseudo-code):
  class A {
    void* mem_;
    bool on_heap_;
  public:
    A(size_t n) : on_heap_(false) {
      mem_ = alloca(n);
      if (mem_ == 0) {
        on_heap_ = true;
        mem_ = malloc(n);
      }
    }

    ~A() { if (on_heap_)  free(mem_); }
  };

If an automatic A is created within a function, its allocation is usable
within that function, and if the allocation was put on the heap, it will
be cleaned up. (I am not sure what happens with a global A object, but C++
compilers often use an initializer function, in which case alloca would
put the alloction in that functions parameter stack allocation.)

It would be nice to have a smart pointer behaving like this -- but that
one I do not see how to do.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Fri, 25 May 2001 22:49:34 GMT Dennis Yelle =CE=C1=D0=C9=D3=C1=CC:
>> >The problem with VLAs, on the other hand, is undefined behavior on st=
ack
>> >overflow.
>>=20
>> The same with constant-length arrays, and we can live with it.
>
>constructed.  Personally, I will be happy to pay this price.
>Does anyone think the price for checking for stack overflow is
>higher than the value of the benefits?

No, I think it's reasonable - check-and-allocate-or-throw.

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Sun, 27 May 2001 03:01:23 GMT Bjarne Stroustrup =CE=C1=D0=C9=D3=C1=CC:
>The definition of alloca() requires it to return 0 in case of stack exha=
ustion.
>At least a programmer can test (though many will forget). I do not know =
of
>a similar facility for VLAs.

They could throw, exactly as operator new() (which don't return 0 also).

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Ken Hagan wrote:
...
> > Then, alloca can simply return zero.
>
> Surely you mean throw std::bad_alloc()?
> We don't actually want to have to check this return value, do we?

The currently widely-available versions of alloca() do return a null
pointer which you do need to check. If C++ standardizes it, some
approach will be needed to accommodate existing code. Overloading with a
'nothrow' version, as with operator new(), won't have the desired
effect; the default would have to be the throwing version. Changing the
name would be the simplest way; the version with the changed name is the
one that would throw, rather than returning a null pointer.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Ken Hagan" <K.Hagan@thermoteknix.co.uk> wrote in message
news:9es0j5$r4c$1@neptunium.btinternet.com...
> Andrei Alexandrescu <andrewalex@hotmail.com> wrote...
> >
> > I guess that on many architectures, programs know how much
> > stack have allocated for them and so checking for availability
> > is only one comparison away.
>
> If you are in any danger of running out of stack space, then your
> biggest risk is not omitting to check the call to alloca, it is
> that the compiler almost certainly doesn't check for adequate stack
> space when it sets up a frame.
>
>    if (char* p=alloca(LOTS))
>    {
>       int a;
>       // ...
>    }
>
> The alloca() may succeed, only for your program to crash when the
> compiler starts using "a".

Quite frankly, I don't care much for alloca anymore, but just to confirm
something: the static stack frame of any function is computed at compile
time, which means 'a' above already has memory for it before the call to
alloca().

> My vote goes for the custom allocator suggested by Dave Harris in
> a nearby post. Like alloca, it can be implemented in a handful of
> instructions, though perhaps not quite as few. Unlike alloca, it
> is not limited to the stack space of your program.

Yeah, but then, the whole issue of equivalent allocators must be fixed in
the Standard. As currently defined, allocators can't do pretty much anything
interesting: they all must be equivalent to each other, and a container is
free to store or not to store them (yet, ahem, the recommendation is to
store it), etc.

IIRC this all comes from list's splice - a useful function that has trouble
deallocating elements if you splice lists bearing different allocators. Are
there other reasons for which allocators are forced not to store state and
to be all equivalent?

In my opinion the following steps could help allocators:

1. Functions that demand equivalent allocators should test for equivalence
and throw an exception for non-equivalent allocators.

2. Rebound allocators must be passed the original allocator upon
construction. That's because there has to be a way to pass the state of the
allocator around for different allocators. Example:

typedef std::map<int, float,
    less<int>, pool_allocator<float> > Map;
...
pool_allocator myAlloc(1024); // pool size
Map myMap(less<int>(), myAlloc);

Now we all know that the map won't use the original allocator - it will
rebind it to the pair type. But then there has to be a way to pass the state
of myAlloc to the allocator used internally by myMap. So allocator must
specify a template constructor that accepts an allocator of a different
type.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
>
> "Gabriel Dos Reis" <dosreis@cmla.ens-cachan.fr> wrote in message
> news:flk834yoza.fsf@sel.cmla.ens-cachan.fr...
> > "Andrei Alexandrescu" <andrewalex@hotmail.com> writes:
> >
> > [...]
> >
> > | > vector is more general than a VLA, efficient, standard, and available
> now.
> > |
> > | There are people I know who cannot use vector because it's too slow
> >
> > Is it too slow because of their particular implementation or is it
> > because of vector inherent semantics?
>
> It's slow in principle - does too many things.

That's qualifies as the second case - vector inherent semantics. Can you
give an example of the most significant way in which the
standard-required semantics slow things down? With a decent
implementation of both the compiler and the standard library, where are
the big time sinks in std::vector<> that your preferred version would
avoid?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> writes:

| "Gabriel Dos Reis" <dosreis@cmla.ens-cachan.fr> wrote in message
| news:flk834yoza.fsf@sel.cmla.ens-cachan.fr...
| > "Andrei Alexandrescu" <andrewalex@hotmail.com> writes:
| >
| > [...]
| >
| > | > vector is more general than a VLA, efficient, standard, and available
| now.
| > |
| > | There are people I know who cannot use vector because it's too slow
| >
| > Is it too slow because of their particular implementation or is it
| > because of vector inherent semantics?
|
|
| It's slow in principle - does too many things.

I'm willing to beleive you.  However, could you point to specific semantics
of std::vector which make it inherently slow?

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Bjarne Stroustrup" <bs@research.att.com> wrote in message
news:GDyHnu.9z1@research.att.com...
> I said "an answer" not "the answer" and I didn't claim it conclusive.
> However, this was the first data in this discussion, which I find typical
> in its reliance on assumptions, "common sense", and clever arguments
rather
> than data.

I agree with bringing data to back up one's statements. The trick is, it's
sometimes hard to produce conclusive data quickly.

> >  The
> > allocation pattern of your test program would make the day of any memory
> > allocator writer: you simply allocate and deallocate the same memory
size
> > again and again. A memory allocator that holds a cache of the last freed
> > block (for example, Loki's allocator does exactly that) would simply
mark
> > that block again as allocated and pass it back to the caller - an
operation
> > almost as quick as adjusting the stack pointer.
>
> Actually, that was *not* what I did. I used an allocation pattern that is
> particularly hard for certain allocators. I never allocated two objects of
> the same size, and I allocated objects of increasing size so that an
object
> would never fit into the space vacated by a previously deallocated object.
> This is a pattern that can cause maximum fragmentation.

Oops, I misread your test program, apologies.

> > But on the topic of memory allocation, I think, however, that it would
be
> > great to support the notion of reallocation in allocators, see thread
"Any
> > chance to standardize _expand?".
>
> I have yet to see arguments/data that would make me keen on that.

As I said, it's so hard to produce conclusive evidence. A good way is to
start from a real-world program that uses vectors quite some. Compile the
program enabling in-place reallocation. Then, recompile it disabling
in-place reallocation. Measure run times in both cases.

On the _expand topic, the issue shifts from the speed of the free store
allocator (that we were discussing in comparison to alloca's speed) to the
probability of finding an expandable block. (Everybody would agree that
copying data around is not desirable and, if avoided, can improve
peformance - so it's probability at stake here.) The probability of finding
space at the end of a memory block depends on the allocation strategy used.
This makes it even harder to collect evidence...

I personally believe that probability would be more than just a few percent
with many allocators and allocation trends, but then, I don't have any
experimental data at hand yet :o).


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

kuyper@wizard.net (James Kuyper Jr.) wrote (abridged):
> My understanding is that alloca() predates gcc by at least a couple
> of decades.

I suspect alloca() precedes C itself. It was probably implemented in B,
although I can't find a reference.

The even earlier language BCPL had a variant called aptovec(). This
allocated a variable-sized array, invoked a function on it, then
deallocated the array. This would be hard to write in a statically
type-checked language, but BCPL was untyped. I think B was statically
typed, so aptovec() may have become alloca() during the transition from
BCPL to B.

C++ is also statically type-checked, but its type system is more powerful
so we have an opportunity to go back to the future. We could write
aptovec() like:

    template <typename vec_t, typename fun_t, typename result_t=void>
    result_t aptovec( fun_t f, size_t size ) {
        vec_t *vec( new vect_t[size] );
        result_t result = f( vec );
        delete[] vec;
        return result;
    }

Obviously implementations which support stack allocation would use that
instead. Also obviously, the C++ version would ensure the memory was
freed even if f() throws an exception. That would also avoid the
infelicity with result (which probably isn't legal but ought to be in
the new standard).

I mention this in case aptovec() has any advantages over alloca(). I
suspect it doesn't, as in C++ we can use destructors for the cleanup.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Thu, 24 May 2001 19:09:03 GMT Niklas Matthies =CE=C1=D0=C9=D3=C1=CC:
>> I don't think that standardizing alloca() is a good idea; far better i=
s to
>> standardize just VLA. The problem with alloca() is alignment.
>
>It's not more a problem for alloca() as it is for malloc().

Yes, that is why I'm using operator new() but not malloc() :)

>The problem with VLAs, on the other hand, is undefined behavior on stack
>overflow.

The same with constant-length arrays, and we can live with it.

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Thu, 24 May 2001 19:41:23 GMT Nicola Musatti =CE=C1=D0=C9=D3=C1=CC:
>
>
>Eugene Karpachov wrote:
>[...]
>> Can new-ing memory be as fast as auto variable allocation?
>
>Not really, I'd say. To allocate an automatic variable you only have to

I think so too, so std::vector will be not as fast as VLA.

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010525041916.59825G@brangdon.madasafish.com...
> I mention this in case aptovec() has any advantages over alloca(). I
> suspect it doesn't, as in C++ we can use destructors for the cleanup.

It may have no advantages for the programmer but it is a
lot more implentable if you don't have a separate stack
pointer and frame pointer.  The allocation and deallocation
is entirely within aptovec().  The calling routine never
sees the allocated store at the same time as it has to
see its local variables.  There really is no comparison
with alloca().



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Eugene Karpachov wrote:
> Can new-ing memory be as fast as auto variable allocation?

Free store allocations may take up several tens of cycles. On my computer
I counted to about 80 cycles. Some say it may even take several hundreds
of cycles.

By contrast, an automatic object can be implemented as a piece of memory
in the function block that is copied onto the parameter stack before
executing. So it does not take up any extra time at all.

Then alloca() needs only to move the parameter stack pointer, but it does
not need any extra release time, as that is the same stack pointer that
should be moved when the function call expires.

When using say a two-space conservative GC, then allocation is fast,
because one simply stack allocates (in one of the two reserved array
spaces) until memory runs out, when all live data is copied over to the
other, free GC space. For this to work, one has to make use of memory
moveable data, or handles, which is slower than direct pointers, and in
addition the GC time makes the average allocation time longer.

As for new/malloc, that can be made fast if all the objects are of the
same size: One can make use of two singly linked lists, one for free and
one for used memory blocks, and it is fast to move a block between the two
lists. Further, one can reserve arrays for memory allocations of size 2^n,
n = n0, n0 + 1, ..., and get fast memory allocations this way. But it gets
complicated when one gets low on memory in one of the arrays reserved for
2^n blocks. So then you end up extra cycles to handle that.

So one ends up with a number of different memory techniques, all good for
different purposes: If you know something about the data you are using,
then considerable gains might be made.

Further, the right memory allocation technique might be a suitable hybrid.

As for the C++ standard, one can note that writing different memory
allocators is very technical, and in addition a lot of research is being
done about that these days, so users of C++ will probably want to have
access to that work in progress, but without having to bother too much
about going into the details except when absolutely needed for
optimizations.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Richard Herring" <rnh@gmrc.gecm.com> wrote in message
news:9ej3bn$6pd$2@miranda.gmrc.gecm.com...
> aptovec() took a count and a function pointer as arguments,
> bumped the stack pointer and then called the function,
> passing a pointer to the memory as the function argument.

No that's a different idea and _much_ easier to implement.
The problem with alloca() is the allocated memory stays
around for the duration of the function.  You can for
example put it in a loop.  How do you implement this
without use of the heap, if you have no separate stack
pointer and frame pointer?

As with local functions (and the rule on dynamic free
variables), BCPL did what was efficiently and portably
implementable and didn't do things that weren't.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Wed, 23 May 2001, Andrei Alexandrescu wrote:
>
> Anyway, it seems like the C99 standardization committee didn't care much
> about compatibility with C++. Anyone care to comment about that?

It's not that they didn't care, but that communication between the C
and C++ committees could have been better. A few people sit on both
committees, but it wasn't always obvious whether a change in C would
be cause problems in C++.

In addition, the standards are on quite different schedules. In the
case of the complex type, the C committee was finishing its work
before the C++ committee decided what it wanted to do about complex.
The result was an incompatibility that at best will be difficult to
resolve.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
>
> "Phil Edwards" <pedwards@dmapub.dma.org> wrote in message
> news:200105222249.SAA31330@dmapub.dma.org...
> > All the Unixes I've seen offer this as well (without the leading
> underscore),
> > although their documentation all take pains to point out that it's
> extremely
> > nonportable.  (Because we haven't standardized it yet, duh. :-)
>
> Cool!
>
> My dream is to be able to allocate variable-length objects (such as
> std::strings) on the stack when possible. Wow what a cool thing would be - a
> language that allows you to go THAT far with optimizing.

Given that std::string is a standard class, and therefore the compiler
can just *know* what it is about, it would even be possible to do that
optimization under the current standard.
Doing this right would however not be easy (if the string is extended
soon after, with an unpredictable number of characters, allocating
on the stack would be counter-productive: re-allocation is necessary
anyway, and the original allocation cannot be freed until all later
stack allocations are freed).

>
> That can be done with alloca() in conjunction with a feature that allows the
> constructor to detect whether it's called for an automatic object. Consider
> this fictional code:
>
> class string
> {
>     ...
>     string(const char*);
>     string(const char* s, void* memory = alloca(1 + strlen(s))) auto;
> };

That's exactly the bad version. While the compiler can do the analysis
(it knows the complete function), the constructor cannot.

Think of the following code:

void foo()
{
  std::string s1(some_1024_character_string());
  std::string s2(some_other_string());
  s1 += s2;
  ...
}

Now, s1 has to get re-allocated, and therefore you get 1024 bytes
of dead stack memory.

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Eugene Karpachov" <jk@steel.orel.ru> wrote in message
news:slrn9grnjn.g1.jk@localhost.localdomain...
Thu, 24 May 2001 19:09:03 GMT Niklas Matthies                      :
>> I don't think that standardizing alloca() is a good idea; far better is
to
>> standardize just VLA. The problem with alloca() is alignment.
>
>It's not more a problem for alloca() as it is for malloc().

Yes, that is why I'm using operator new() but not malloc() :)


I'm not sure I understand. If it's about alignment, malloc returns memory
properly aligned for any type.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Eugene Karpachov wrote:
>=20
> Thu, 24 May 2001 19:09:03 GMT Niklas Matthies =CE=C1=D0=C9=D3=C1=CC:
> >> I don't think that standardizing alloca() is a good idea; far better=
 is to
> >> standardize just VLA. The problem with alloca() is alignment.
> >
> >It's not more a problem for alloca() as it is for malloc().
>=20
> Yes, that is why I'm using operator new() but not malloc() :)
>=20
> >The problem with VLAs, on the other hand, is undefined behavior on sta=
ck
> >overflow.
>=20
> The same with constant-length arrays, and we can live with it.

Yes, we can, and we do, but:
Is there any reason we have to?
Is there any reason we should continue to do so?

Let's be realistic for a minute.
Under the current rules, if a C++ program has no recursion,
it is easy to test to see if it will overflow its stack.
When we add VLAs this will become almost impossible to test.
It seems to me that for a typical implementation the
test for stack overflow is just a single comparison for every
function call plus another single comparison for each VLA=20
constructed.  Personally, I will be happy to pay this price.
Does anyone think the price for checking for stack overflow is
higher than the value of the benefits?

Dennis Yelle
--=20
I am a computer programmer and I am looking for a job.
There is a link to my resume here: =20
http://table.jps.net/~vert/

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Steve Clamage <clamage@eng.sun.com> writes:

[...]

| In addition, the standards are on quite different schedules. In the
| case of the complex type, the C committee was finishing its work
| before the C++ committee decided what it wanted to do about complex.

But by the time they started work on complex arithmetics, there were
existing pratice about the name `clog'.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
>
> "Matt Seitz" <mseitz@yahoo.com> wrote in message
> news:jXUO6.13988$9D5.1253209@newsread2.prod.itd.earthlink.net...
> > "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
> > news:9eghmg$2sthd$1@ID-14036.news.dfncis.de...
> > > * You can't create/resize a vector without initializing all of its
> > elements,
> > > even though you will pass it to a function that fills it.
> >
> > What about:
> >     std::vector v(0);
> >     v.reserve(size_new);
> >     init_vector(&v);
>
> That won't work :o(.

Of course, init_vector would have to use push_back() (which then
would not re-allocate unless you reserved too little memory).
This way it _would_ work - assuming the function initializes the
elements in order.

But given that uninitialized allocation seems to be one of the
biggest demands for vector, what about allowing uninitialized
elements and adding class members to support them:

typedef (implementation defined) init_iterator;
   "Random access output iterator"; assumes the element it points
   to is uninitialized and initializes it on assignment.
   Allows only output, but otherwise behaves like a random access
   iterator (thus allowing you to initialize in different order).
   Output through this iterator to an already initialized element
   is undefined behaviour. There's a member function to get a normal
   iterator pointing to the same element.

init_iterator resize_uninitialized(size_type);
   Resize the vector, but don't initialize new members.
   Returns the first new member, or end(), if no new member
   was created

Of course, the user of the class is responsible for correctly
initializing the class. Using resize_uninitialized is asking
to allow shooting yourself into the foot.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <GDw910.IsK@research.att.com>, bs@research.att.com (Bjarne
Stroustrup) wrote:
>How many arrays do you have to allocate before stack allocation makes a
>significant advantage over free store allocation (implicit in std::vector)?
...
>To get an answer, I wrote two little programs. One using std::vector:
...
>and one using alloca():
...
>On the first machine, the alloca() version was 4 times faster than the vector
>one. I believe that's what many people expected.
>
>On the other machine, the alloca() version beat the vector version by only
>7% and 5% depending on which compiler I used. That's what I expected.
...
>I think people should think a little harder before they recommend stack
>allocation (or VLAs) on efficiency grounds.

I think though that free store allocations can be fast under circumstances
when there is plenty of memory and memory is not fragmented. And one has
to add the times for deallocations as well: Fast allocation times may show
up as a beating on the deallocation times.

So then the advantage of alloca might turn out to be more significant when
such factors are taken into account.

-- I am not an optimizing programmer myself, but when I tried to skim
through some of those GC research papers, I found that these issues are
quite complex: Somebody is saying that memory fragmentation is slowing
down traditional free store allocations and thus a conservative GC would
be better, and then somebody is making a study showing that this may not
always be the case and free store management can sometimes be just as
fast. And so on, back and forth.

So I would stay tuned for this research in progress, rather having a
strong opinion in favor of this or that memory allocation technique.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Christopher Eltschka" <celtschk@dollywood.itp.tuwien.ac.at> wrote in
message news:3B0EB71E.5DB55379@dollywood.itp.tuwien.ac.at...
> init_iterator resize_uninitialized(size_type);
>    Resize the vector, but don't initialize new members.
>    Returns the first new member, or end(), if no new member
>    was created

I think a better primitive for vector is force_size(size_type) which forces
the size of a vector to a specified value, which should not exceed current
capacity. That would allow apps to call reserve(), do some low-level
initialization, and finally call force_size() to make vector acknowledge the
newly initialized memory.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bjarne Stroustrup wrote:
>
> I think people should think a little harder before they recommend stack
> allocation (or VLAs) on efficiency grounds.
>
> I consider std::vector a better choice than either alloca() or VLAs.
>
> vector is more general than a VLA, efficient, standard, and available now.

>From my point of view, at least, the problem with vector isn't where the
allocation is done, but the overhead of initialisation.

Recently I was working on some graphics code for which I ended up
writing my own dynamic array class, essentially identical to vector
except that the elements were left uninitialised by default. I needed it
because the code was intended to deal with potentially quite large
images (tens of megabytes), and the overhead of zero-initialising a
newly allocated image buffer was unacceptable.

So I don't think we need alloca(), VLAs, or some other new kind of
dynamic array, but what I for one would really appreciate is simply
adding a new constructor to vector that allocates the array but doesn't
initialise it. (For POD elements only, of course. Allowing uninitialised
non-POD elements would cause problems when they were assigned to later.)

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
        "Hungarian notation is the tactical nuclear weapon of
         source code obfuscation techniques." -- Roedy Green

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Bjarne Stroustrup" <bs@research.att.com> wrote in message
news:GDw910.IsK@research.att.com...
> but free store allocation/deallocation can be quite fast, and some of the
> speed advantage of VLAs (and alloca()) caomes from the assumption that
they
> are allowed to overflow the stack without warning (a horrible "feature").

I don't know... I guess that on many architectures, programs know how much
stack have allocated for them and so checking for availability is only one
comparison away. Then, alloca can simply return zero (as you tested in your
sample programs).

> How many arrays do you have to allocate before stack allocation makes a
> significant advantage over free store allocation (implicit in
std::vector)?
>
> To get an answer, I wrote two little programs.

[snip programs for brevity]

Interesting. You'd agree, however, that the test is not very conclusive. The
allocation pattern of your test program would make the day of any memory
allocator writer: you simply allocate and deallocate the same memory size
again and again. A memory allocator that holds a cache of the last freed
block (for example, Loki's allocator does exactly that) would simply mark
that block again as allocated and pass it back to the caller - an operation
almost as quick as adjusting the stack pointer.

Concrete programs might have quite different memory allocation patterns,
which mean increasing trouble for the free store allocator - while alloca
will stay at the same speed.

> I think people should think a little harder before they recommend stack
> allocation (or VLAs) on efficiency grounds.
>
> I consider std::vector a better choice than either alloca() or VLAs.
>
> vector is more general than a VLA, efficient, standard, and available now.

There are people I know who cannot use vector because it's too slow, copies
memory unnecessarily (and inefficiently), constructs values unnecessarily
(and inefficiently) even when they are of primitive types and will be
initialized by a low-level routine in the next step. If C++ is to continue
to care about efficiency, it would be good to give those guys a chance.

It would be nice to have alloca around when you really need it, but it's a
bit too low level for my taste. The worst thing about alloca is that it's
useless to higher-level libraries because you must call it in client code -
you can't call a library function that in turn calls alloca on behalf of the
callee and does some more stuff. That makes alloca very unattractive. Then,
I find VLAs pretty weird with all their rules and runtime-evaluated sizeof,
they just don't seem at home within the language (either C or C++).

But on the topic of memory allocation, I think, however, that it would be
great to support the notion of reallocation in allocators, see thread "Any
chance to standardize _expand?".


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Ross Smith wrote:
>
> Bjarne Stroustrup wrote:
> >
> > I think people should think a little harder before they recommend stack
> > allocation (or VLAs) on efficiency grounds.
> >
> > I consider std::vector a better choice than either alloca() or VLAs.
> >
> > vector is more general than a VLA, efficient, standard, and available now.
>
> >From my point of view, at least, the problem with vector isn't where the
> allocation is done, but the overhead of initialisation.
>
> Recently I was working on some graphics code for which I ended up
> writing my own dynamic array class, essentially identical to vector
> except that the elements were left uninitialised by default. I needed it
> because the code was intended to deal with potentially quite large
> images (tens of megabytes), and the overhead of zero-initialising a
> newly allocated image buffer was unacceptable.

Why didn't you just reserve() the space? That should have the same
effect.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
...
> There are people I know who cannot use vector because it's too slow, copies
> memory unnecessarily (and inefficiently), constructs values unnecessarily
> (and inefficiently) even when they are of primitive types and will be
> initialized by a low-level routine in the next step.

That sounds like a defective implementation of (or perhaps a failure to
use?) vector::reserve().

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

James Kuyper Jr. wrote:
> Andrei Alexandrescu wrote:
> ...
> > There are people I know who cannot use vector because it's too slow,
copies
> > memory unnecessarily (and inefficiently), constructs values
unnecessarily
> > (and inefficiently) even when they are of primitive types and will be
> > initialized by a low-level routine in the next step.
>
> That sounds like a defective implementation of (or perhaps a failure to
> use?) vector::reserve().

#if ANGRY_BUT_VALID_STATEMENTS_ALLOWED

I can't use vector<> or just about any other standard container because they
are not quaranteed to free or deallocate any memory in their lifetime.
Because of this:

STANDARD CONTAINERS ARE NEXT TO USELESS FOR IMPLEMENTING DATA STRUCTURES.

Frankly, I do not trust the intellectual honesty of any person that says
otherwise. This design defect has already forced me to implement my own
containers.

It is possible to workaround this problem, for instance, by explicitly
copying, destroying and then reconstructing a container, but this is:
- error prone,
- difficult to make exception safe,
- a kludge.
Even this technique DOES NOT QUARANTEE THAT MEMORY USAGE IS MINIMAL.

#endif


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> writes:

[...]

| > vector is more general than a VLA, efficient, standard, and available now.
|
| There are people I know who cannot use vector because it's too slow

Is it too slow because of their particular implementation or is it
because of vector inherent semantics?

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> Concrete programs might have quite different memory allocation
> patterns, which mean increasing trouble for the free store allocator
> - while alloca will stay at the same speed.

If they are using alloca() their memory allocation patterns must be
stack-like, LIFO. We can write an overloaded operator new(), or an
allocator, to exploit this.

Then we could write calling code like:

    #include "lifo_heap.h"

    int f( int n ) {
        std::vector< int, lifo_allocator<int> > v( n );
        return v[0];
    }

It seems to me this should give most of the advantages of alloca(). If
lifo_allocator were standard, perhaps a smart implementation could
implement it in terms of alloca(), at least when used with other std
containers. That would avoid having 2 stacks per thread.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Vesa Karvonen wrote:
...
> I can't use vector<> or just about any other standard container because they
> are not quaranteed to free or deallocate any memory in their lifetime.

True. But the same is true of std::copy(). And before you say that
std::copy() has no need to allocate any memory, I'd just like to point
out that the standard does not prohibit it from allocating memory.
Nothing in the standard guarantees the quality of implementation of any
feature; there's nothing special about containers in this regard. It's
your responsibility to pressure implementors to provide adequate quality
in their implementations. If you have a problem with that division of
responsibility, you'd better switch to assembler, because you won't get
much in the way of relevant guarantees in any high-level language.

Now, if you point out that vector<> provides no way to tell a container
to shrink to fit, I have to agree, and I think that would be a
reasonable feature to add; it might be feasible to achieve that effect
simply by modifying the description of reserve().

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
>
> "Christopher Eltschka" <celtschk@dollywood.itp.tuwien.ac.at> wrote in
> message news:3B0EB71E.5DB55379@dollywood.itp.tuwien.ac.at...
> > init_iterator resize_uninitialized(size_type);
> >    Resize the vector, but don't initialize new members.
> >    Returns the first new member, or end(), if no new member
> >    was created
>
> I think a better primitive for vector is force_size(size_type) which forces
> the size of a vector to a specified value, which should not exceed current
> capacity. That would allow apps to call reserve(), do some low-level
> initialization, and finally call force_size() to make vector acknowledge the
> newly initialized memory.

I'm unclear about what "acknowledge the newly initialized memory" means.
Surely it's better to force the size of the allocation before the
initialization, rather than after? Doing it after means that all of the
newly initialized objects may need to be copied as a result of
reallocation.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B0FA378.39F283CC@wizard.net...
> Andrei Alexandrescu wrote:
> ...
> > There are people I know who cannot use vector because it's too slow,
copies
> > memory unnecessarily (and inefficiently), constructs values
unnecessarily
> > (and inefficiently) even when they are of primitive types and will be
> > initialized by a low-level routine in the next step.
>
> That sounds like a defective implementation of (or perhaps a failure to
> use?) vector::reserve().


That won't work. Do this with vector efficiently:

1. Make a vector of N bytes
2. Pass the address of the memory to some file API to read data into it
3. Perform some transformations on the data that can potentially increase
data size
4. Pass the address of the memory to some socket function to write it out

With vector you'll get an unnecessary initialization in step 1 that you
can't get rid of, and a reallocation pessimization in step 3 that you cannot
get rid of (the vector won't be expanded in place even though there might be
available memory there).

The sequence above is the core loop of a Web server. Step 3 is necessary for
server-side services such as macros, file inclusion, scropting, servlets,
etc.

The discussion strayed away from alloca(), however :o).

A note on efficiency. If C++ is to be increasingly targeted as a systems
programming language, efficiency must stay there. It's important. If we
ditch issues (that I consider serious) such as memory reallocation, then we
jeopardize one of C++'s core values.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hans Aberg wrote:

[About alloca]
> It should be possible to make a wrap doing this

Do you mean that you know how to wrap alloca ?

--
Valentin Bonnard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." wrote:
>
> Ross Smith wrote:
> >
> > Recently I was working on some graphics code for which I ended up
> > writing my own dynamic array class, essentially identical to vector
> > except that the elements were left uninitialised by default. I needed it
> > because the code was intended to deal with potentially quite large
> > images (tens of megabytes), and the overhead of zero-initialising a
> > newly allocated image buffer was unacceptable.
>
> Why didn't you just reserve() the space? That should have the same
> effect.

No it shouldn't. reserve() only guarantees no reallocation as long as
the vector's size stays below the reserved value; it doesn't give you
access to the reserved elements until you actually resize() the vector,
or add them in some other way such as push_back(). Accessing the
reserved elements immediately is cheating; it may work on some
implementations, but it's not permitted by the standard.

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
        "Hungarian notation is the tactical nuclear weapon of
         source code obfuscation techniques." -- Roedy Green

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <MUNP6.365$0d3.4092@read2.inet.fi>, Vesa Karvonen <vesa.karvo
nen@hNoOuSsPeAmMarque.fi> writes
>STANDARD CONTAINERS ARE NEXT TO USELESS FOR IMPLEMENTING DATA STRUCTURES.
>
>Frankly, I do not trust the intellectual honesty of any person that says
>otherwise.

Such attitudes prohibit rational debate. You make an assertion and then
deny others the right to disagree without being insulted. I think the
moderator should have bounced this posting.

>This design defect has already forced me to implement my own
>containers.

Something that we often have to do when we have a problem that does not
match normal requirements. Many of us use the standard containers
without difficulty because their resource allocation policy does not
interfere with what we want to do.

By the way, how do you think C programmers shrank dynamic arrays?


Francis Glassborow      ACCU
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9eghmg$2sthd$1@ID-14036.news.dfncis.de...
> * You can't create/resize a vector without initializing all of its
elements,
> even though you will pass it to a function that fills it.

What about:
    std::vector v(0);
    v.reserve(size_new);
    init_vector(&v);


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

jk@steel.orel.ru (Eugene Karpachov) writes:

| Wed, 23 May 2001 09:34:32 GMT Gabriel Dos Reis =CE=C1=D0=C9=D3=C1=CC:
| >the compiler will do what you mean.  And of course, __builtin_alloca
| >is the proof of concept Phil was talking about.  But that is just
|=20
| Not exactly; the (better) proof of concept is

Phil was talking about alloca().

--=20
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Thu, 24 May 2001 12:39:54 GMT, Eugene Karpachov <jk@steel.orel.ru> wrote:
> Wed, 23 May 2001 09:23:14 GMT Hans Aberg wrote:
>
> >The use of alloca is frequent in libraries like those of GNU, so I think
> >it is a good idea to standardize it, so one check for its presence and use
> >it when available.
>
> I don't think that standardizing alloca() is a good idea; far better is to
> standardize just VLA. The problem with alloca() is alignment.

It's not more a problem for alloca() as it is for malloc().
The problem with VLAs, on the other hand, is undefined behavior on stack
overflow. This should be avoided (possibly by a general facility for
catching stack overflows).

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <9egof8$25j$1@cam-news1.cambridge.arm.com>, Al Grant (tnarga@arm.REVERSE-NAME.com) wrote:
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3B0BAF32.6FAB4109@wizard.net...
> > Al Grant wrote:
> > > "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
> > > news:9ec2qt$25uu5$1@ID-14036.news.dfncis.de...
> > > > MSVC defines a function, _alloca, that allows you to allocate memory
> right
> > > > on the stack at runtime.
> > >
> > > gcc invented that.
> >
> > Can you support that claim? My understanding is that alloca() predates
> > gcc by at least a couple of decades.

> I guess you are right (did C itself predate gcc by a
> couple of decades?).  I was told it was a gcc-ism when
> I encountered it in GNU sources in the late 80s.

Well, the idea is present in BCPL's aptovec() function, so
it goes back at least to the early 70s.

aptovec() took a count and a function pointer as arguments,
bumped the stack pointer and then called the function,
passing a pointer to the memory as the function argument.

--
Richard Herring       |  <richard.herring@baesystems.com>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Eugene Karpachov wrote:
[...]
> Can new-ing memory be as fast as auto variable allocation?

Not really, I'd say. To allocate an automatic variable you only have to
move the stack pointer according to the variable size. I believe you
could write a very fast memory manager by using a very large static
array and use it as a stack.

In order to allocate memory you'd only move the pointer to the first
free byte and set some bookkeeping (e.g. a pointer to the previous block
and a mark to indicate that the current block is in use). Deallocation
would only mark the block as unused unless you are deallocating the most
recently allocated block; in this case you'd move the free memory
pointer in order to recover contiguous free blocks.

Many years ago I worked with a Pascal compiler that worked in a similar
way.

Best regards,
Nicola Musatti

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <slrn9gp2m5.ji.jk@localhost.localdomain>, jk@steel.orel.ru
(Eugene Karpachov) wrote:
>I don't think that standardizing alloca() is a good idea; far better is to
>standardize just VLA. The problem with alloca() is alignment.

I am not sure what you mean here: Does not alloca merely allocate on the
stack, but is free to choose alignment if needed.

>>But be aware of that alloca comes with some restrictions: The stack may
>>not be able to cope with large objects, and objects only live as long as
>>the function they were created within is executing.
>
>Yes, the same as with auto variables - it is just what we want, don't we?

Did you possibly forget the <ironic> markup here? :-)

I think these questions fall under the more general GC (garbage collector)
question, where one may make use of a mixture of techniques for memory
allocation:

I can think of say memory movable objects which first are allocated using
alloca, and if they persist when the function call expires, they are moved
to the heap.

And with a conservative GC in place, one could let a function return a
reference, and let the GC keep track of the lifetime.

Different types of applications will require different blends of memory
allocation techniques.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Matt Seitz" <mseitz@yahoo.com> wrote in message
news:jXUO6.13988$9D5.1253209@newsread2.prod.itd.earthlink.net...
> "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
> news:9eghmg$2sthd$1@ID-14036.news.dfncis.de...
> > * You can't create/resize a vector without initializing all of its
> elements,
> > even though you will pass it to a function that fills it.
>
> What about:
>     std::vector v(0);
>     v.reserve(size_new);
>     init_vector(&v);


That won't work :o(.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> * You can't create/resize a vector without initializing all of its
> elements, even though you will pass it to a function that fills it.

In principle you could turn that function into an iterator pair, and pass
it to the vector's constructor.

(This is something which could be easier if sequences were represented
explicitly by a single object, rather than a pair of objects.)

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010524221451.59825C@brangdon.madasafish.com...
> andrewalex@hotmail.com (Andrei Alexandrescu) wrote (abridged):
> > * You can't create/resize a vector without initializing all of its
> > elements, even though you will pass it to a function that fills it.
>
> In principle you could turn that function into an iterator pair, and pass
> it to the vector's constructor.

I agree, but not when you are dealing with sockets or other low-leve APIs or
stuff like that. And that's exactly the kind of cases when you do need as
much speed as it gets.

> (This is something which could be easier if sequences were represented
> explicitly by a single object, rather than a pair of objects.)

I don't mind much about that.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

> | For proof-of-concept and a working implementation, look at gcc.
> | Usually calls to alloca() are expanded inline (the compiler knows how to
> | generate code to extend the function stack, after all), and extensions like
> | function-local auto arrays have thus been in gcc for a long time.
>
> I know this is not the right place to discuss about a particular
> implementation, but I think some of Phil's comments need
> clarifications.

Yes, that should have been the builtin version, not the reserved version.
Thanks, Gaby.  Shame on me.  :-)


> However, if you say ___builtin_alloca then
> the compiler will do what you mean.  And of course, __builtin_alloca
> is the proof of concept Phil was talking about.

IIRC, it falls back on a call to the library version of alloca(), if it can't
figure out at compile time what to do.  (Don't have the sources to check;
maybe I'm thinking of the builtin math functions.)

If C++0x does recognize alloca(), I dearly hope that it allows the compiler
to perform this optimization.  Or at the least, permit alloca to be a macro
and/or a function.  Compiler vendors can define the macro to be _alloca
or _fast_alloca or __builtin_alloca, etc.


Phil

--
pedwards at disaster dot jaj dot com  |  pme at sources dot redhat dot com
devphil at several other less interesting addresses in various dot domains
The gods do not protect fools.  Fools are protected by more capable fools.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Al Grant" <tnarga@arm.REVERSE-NAME.com> wrote in message
news:9ed8vu$7ab$1@cam-news1.cambridge.arm.com...
> "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
[snip]

> And since you mention it, would it not be better for
> C++ to adopt C99 VLAs instead of something that looks
> like a function call but isn't?

>From what I've read, VLAs are not such a cool implementation. For example,
they have their sizeof evaluated at runtime and all kind of weird things
like that.

Anyway, it seems like the C99 standardization committee didn't care much
about compatibility with C++. Anyone care to comment about that?


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Bjarne Stroustrup" <bs@research.att.com> wrote in message
news:GDpL1s.9ov@research.att.com...
[snip]
> However, it is very hard to specify portably how much memory can be taken
> by alloca()  (in its various incarnations).

I guess the rule is, just call alloca and look whether it returns zero :o).
By the way, the free store doesn't provide with a means to specify how much
memory can be taken by new, either.

> I like std::vector. It's more general than alloca() and can be almost as
fast
> as variable-length arrays in most languages.

That's true. However, it's frustrating to be so close to have a facility
that would be optimal. I have this colleague who simply cannot use vector
because it's too slow:

* You can't create/resize a vector without initializing all of its elements,
even though you will pass it to a function that fills it.

* You can't reserve more memory for a vector without copying it all, even
when there is memory available on the free store right after it. It would be
ultrafast just to adjust the memory management structure.


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Wed, 23 May 2001 15:08:37 GMT, Andrei Alexandrescu <andrewalex@hotmail.com> wrote:
> "Al Grant" <tnarga@arm.REVERSE-NAME.com> wrote in message
> news:9ed8vu$7ab$1@cam-news1.cambridge.arm.com...
> > "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
> [snip]
>
> > And since you mention it, would it not be better for
> > C++ to adopt C99 VLAs instead of something that looks
> > like a function call but isn't?
>
> From what I've read, VLAs are not such a cool implementation. For
> example, they have their sizeof evaluated at runtime and all kind of
> weird things like that.
>
> Anyway, it seems like the C99 standardization committee didn't care
> much about compatibility with C++. Anyone care to comment about that?

How are VLAs "incompatible" with C++?
Or do you mean to say that no language features should have been
included into C99 that are not already covered by C++?

AFAICS, the standardization of C99 took care not to introduce any
gratuitous incompatibilities with C++. Nevertheless, the fact that some
feature isn't provided by C++, or would require adding large parts of
C++ to C to provide it in the same way as C++ does, was not seen as an
impediment to adding the feature to C in a way that was thought to be
sound for C.

How would you suggest that the functionality of VLAs should have been
integrated into C99 so that you would consider it to be "compatible"
with C++?

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B0BAF32.6FAB4109@wizard.net...
> Al Grant wrote:
> > "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
> > news:9ec2qt$25uu5$1@ID-14036.news.dfncis.de...
> > > MSVC defines a function, _alloca, that allows you to allocate memory
right
> > > on the stack at runtime.
> >
> > gcc invented that.
>
> Can you support that claim? My understanding is that alloca() predates
> gcc by at least a couple of decades.

I guess you are right (did C itself predate gcc by a
couple of decades?).  I was told it was a gcc-ism when
I encountered it in GNU sources in the late 80s.
So I mentioned to Richard Stallman that these GNU
sources couldn't be ported to the Draft Standard C
compiler I was using then and he said that all he was
bothered about was that GNU sources would compile under
gcc and anything else was a bonus.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Wed, 23 May 2001 09:34:32 GMT Gabriel Dos Reis =CE=C1=D0=C9=D3=C1=CC:
>the compiler will do what you mean.  And of course, __builtin_alloca
>is the proof of concept Phil was talking about.  But that is just

Not exactly; the (better) proof of concept is

int foo(const char *bar) {
        char baz[strlen(bar)];
        // ...
}

VLA's are better than *alloca() for the same reason as operator new() is
better than malloc().

>is the proof of concept Phil was talking about.  But that is just
>proof of concept on only those targets supported by GCC.

Which are numerous (I wonder if any commercial compiler have so many targ=
ets).

--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Wed, 23 May 2001 09:13:29 GMT Bjarne Stroustrup wrote:
>Actually, C99 doesn't guarantee stack allocation of VLAs. In particular, it
>is does not guarantee that a longjmp doesn't leak VLA memory.

But C++ *could* guarantee that - isn't it a better C than C? :)

>Anyone knows what the implementers are actually doing? Where are VLA elements
>stored?

For gcc for i86 they are stored in local stack frame like other auto
variables.

>and what happens when you ask for more than an implementation can
>supply?

The same thing as when you declare
int main() {
        char array[MAX_INT];
        array[0]=0;
}

- something like stack overflow and abort.


>I like std::vector. It's more general than alloca() and can be almost as fast
>as variable-length arrays in most languages.

Can new-ing memory be as fast as auto variable allocation?

--
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Wed, 23 May 2001 09:23:14 GMT Hans Aberg wrote:

>The use of alloca is frequent in libraries like those of GNU, so I think
>it is a good idea to standardize it, so one check for its presence and use
>it when available.

I don't think that standardizing alloca() is a good idea; far better is to
standardize just VLA. The problem with alloca() is alignment.

>>C99 supports such variable-length stack allocation through variable length
>>arrays (VLAs). I think this would be a interesting function to add to C++

>But be aware of that alloca comes with some restrictions: The stack may
>not be able to cope with large objects, and objects only live as long as
>the function they were created within is executing.

Yes, the same as with auto variables - it is just what we want, don't we?

--
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9ec2qt$25uu5$1@ID-14036.news.dfncis.de...
| MSVC defines a function, _alloca, that allows you to allocate memory right
| on the stack at runtime. The allocation consist of a simple adjustment of
| stack pointers so it's O(1). Upon exiting the function, the memory is
| released in O(1) as well.
|
| C99 supports such variable-length stack allocation through variable length
| arrays (VLAs). I think this would be a interesting function to add to C++
| with a C++ flavor to it (guaranteed destruction and all). Better yet, it
| would be great if C++ offered the ability to allocate an array on the caller
| function's stack, so you can create automatic objects that hold
| variable-length data without having to perform any access to the free store.
| Wow that would be cool.
|
| Any thoughts?
|
|
| Andrei

This is a great idea.  This could also extend to passing arrays by value to a
function.  I.e.

void f(auto int[]); // wu-hoo a use for "auto"!

// or fixed size...

void f(auto int[3]);

Either way, avoiding free-store allocation is *almost always* a good thing, and
it is often well known how large an array is at the point of call.  This would
be great:

void g(int argc, char* argv[]) {
    int stringLengths[argc]; // stack-allocation
    // etc.
}

You could also, more often than not, avoid types such as "int(*)[2]" instead of
"int[2][2]" and how annoying, though not overly difficult, it is to convert
between those two.

Paul Mensonides

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Mon, 21 May 2001 22:11:49 GMT Andrei Alexandrescu =CE=C1=D0=C9=D3=C1=CC:
>MSVC defines a function, _alloca, that allows you to allocate memory rig=
ht
>on the stack at runtime. The allocation consist of a simple adjustment o=
f
>stack pointers so it's O(1). Upon exiting the function, the memory is
>released in O(1) as well.

gcc does alloca and variable-length auto arrays too. It seems useful.

>with a C++ flavor to it (guaranteed destruction and all). Better yet, it
>would be great if C++ offered the ability to allocate an array on the ca=
ller
>function's stack, so you can create automatic objects that hold

It seems impossible. Either caller's and callee's stack frames must be in
different address spaces, or callee stack frame will be not deallocated -
both ways are inappropriate IMO.


--=20
jk

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de> you write:
> MSVC defines a function, _alloca, that allows you to allocate memory right
> on the stack at runtime. The allocation consist of a simple adjustment of
> stack pointers so it's O(1). Upon exiting the function, the memory is
> released in O(1) as well.

All the Unixes I've seen offer this as well (without the leading underscore),
although their documentation all take pains to point out that it's extremely
nonportable.  (Because we haven't standardized it yet, duh. :-)

For proof-of-concept and a working implementation, look at gcc.
Usually calls to alloca() are expanded inline (the compiler knows how to
generate code to extend the function stack, after all), and extensions like
function-local auto arrays have thus been in gcc for a long time.

(Unfortunately, such extensions are on by default, leading to a very
confused Phil when he tried to use function-local arrays as a student
under a different compiler, but that's a different rant.)


Phil

--
pedwards at disaster dot jaj dot com  |  pme at sources dot redhat dot com
devphil at several other less interesting addresses in various dot domains
The gods do not protect fools.  Fools are protected by more capable fools.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Phil Edwards" <pedwards@dmapub.dma.org> wrote in message
news:200105222249.SAA31330@dmapub.dma.org...
> All the Unixes I've seen offer this as well (without the leading
underscore),
> although their documentation all take pains to point out that it's
extremely
> nonportable.  (Because we haven't standardized it yet, duh. :-)

Cool!

My dream is to be able to allocate variable-length objects (such as
std::strings) on the stack when possible. Wow what a cool thing would be - a
language that allows you to go THAT far with optimizing.

That can be done with alloca() in conjunction with a feature that allows the
constructor to detect whether it's called for an automatic object. Consider
this fictional code:

class string
{
    ...
    string(const char*);
    string(const char* s, void* memory = alloca(1 + strlen(s))) auto;
};

Basically string's constructor would be overloaded for automatic and
non-automatic objects. The code is fictional because (1) auto can't qualify
a function, and (2) you can't use the arguments of a function in the default
arguments.

Oh well. You just can't stop *thinking* on what kind of expressivity you
need in the language to do all you want...


Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar/



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrei Alexandrescu wrote:
>
> MSVC defines a function, _alloca, that allows you to allocate memory right
> on the stack at runtime. The allocation consist of a simple adjustment of
> stack pointers so it's O(1). Upon exiting the function, the memory is
> released in O(1) as well.

alloca() long preceeds  C++. It predates even the C standard. According
to the C Rationale for section 7.20.3, it was not adopted into the C
standard because "Such a function is not efficiently implementable in a
variety of environments". Given the Standard C rules for reserved names,
it had to be re-named to _alloca(), but there's a lot of existing code
and libraries which use the older name.

> C99 supports such variable-length stack allocation through variable length
> arrays (VLAs). I think this would be a interesting function to add to C++

I think so too; I like the idea. Of course, "interesting" also means
"complicated". It turned out that VLAs produced a lot of complicated
issues in C99, which took a long time to figure out. I think there would
be even more trouble adding them to C++. Since C++ has std::vector<>, I
think there's less reason for putting up with that trouble then there
was in C99.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
news:9ec2qt$25uu5$1@ID-14036.news.dfncis.de...
> MSVC defines a function, _alloca, that allows you to allocate memory right
> on the stack at runtime.

gcc invented that.

> The allocation consist of a simple adjustment of
> stack pointers so it's O(1).

Even if the implemenation has a "stack pointer" it may
not be a simple adjustment.  Some alloca's have to
allocate off the heap and have the compiler insert
pseudo destructor calls to free the memory.  You can
do that in C++ without a modified compiler.

> C99 supports such variable-length stack allocation through variable length
> arrays (VLAs).

Really?  Does it say that VLAs must be on a "stack"?

And since you mention it, would it not be better for
C++ to adopt C99 VLAs instead of something that looks
like a function call but isn't?



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <9ec2qt$25uu5$1@ID-14036.news.dfncis.de>, "Andrei Alexandrescu"
<andrewalex@hotmail.com> wrote:
>MSVC defines a function, _alloca, that allows you to allocate memory right
>on the stack at runtime. The allocation consist of a simple adjustment of
>stack pointers so it's O(1). Upon exiting the function, the memory is
>released in O(1) as well.

The use of alloca is frequent in libraries like those of GNU, so I think
it is a good idea to standardize it, so one check for its presence and use
it when available.

>C99 supports such variable-length stack allocation through variable length
>arrays (VLAs). I think this would be a interesting function to add to C++
>with a C++ flavor to it (guaranteed destruction and all). Better yet, it
>would be great if C++ offered the ability to allocate an array on the caller
>function's stack, so you can create automatic objects that hold
>variable-length data without having to perform any access to the free store.
>Wow that would be cool.

I think it was said that compatibility with C99 was an important issue for
the next C++ standard.

But be aware of that alloca comes with some restrictions: The stack may
not be able to cope with large objects, and objects only live as long as
the function they were created within is executing.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Eugene Karpachov" <jk@steel.orel.ru> wrote in message
news:slrn9gjriq.ik.jk@localhost.localdomain...
>gcc does alloca and variable-length auto arrays too. It seems useful.

Oui :o).

>with a C++ flavor to it (guaranteed destruction and all). Better yet, it
>would be great if C++ offered the ability to allocate an array on the
caller
>function's stack, so you can create automatic objects that hold

It seems impossible. Either caller's and callee's stack frames must be in
different address spaces, or callee stack frame will be not deallocated -
both ways are inappropriate IMO.

Somehow I thought it can be implemented, but on second thought it seems it's
hard. I was thinking the callee can alter caller's stack without affecting
the caller.

Andrei

--
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar/



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Phil Edwards <pedwards@dmapub.dma.org> writes:

| For proof-of-concept and a working implementation, look at gcc.
| Usually calls to alloca() are expanded inline (the compiler knows how to
| generate code to extend the function stack, after all), and extensions like
| function-local auto arrays have thus been in gcc for a long time.

I know this is not the right place to discuss about a particular
implementation, but I think some of Phil's comments need
clarifications. In GCC, if you use `alloca' the compiler will look for
an ordinary third-party supplied alloca and give appropriate diagnostic
message if not found.  However, if you say ___builtin_alloca then
the compiler will do what you mean.  And of course, __builtin_alloca
is the proof of concept Phil was talking about.  But that is just
proof of concept on only those targets supported by GCC.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <GDpL1s.9ov@research.att.com>, bs@research.att.com (Bjarne
Stroustrup) wrote:
>> MSVC defines a function, _alloca, that allows you to allocate memory right
>> on the stack at runtime. The allocation consist of a simple adjustment of
>> stack pointers so it's O(1). Upon exiting the function, the memory is
>> released in O(1) as well.
>
>However, it is very hard to specify portably how much memory can be taken
>by alloca()  (in its various incarnations).

Is this needed?:

Does not alloca return 0 when it fails to find a memory allocation, so
that if it fails, one put an allocation on the heap instead?

It should be possible to make a wrap doing this automatically via an
automatic object, so that in case the allocation is made on the heap, it
is deleted when the function expires.

The uses of alloca I have seen are anyway this: Use alloca whenever
available and possible, otherwise use malloc & free substituting alloca.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Al Grant wrote:
>
> "Andrei Alexandrescu" <andrewalex@hotmail.com> wrote in message
> news:9ec2qt$25uu5$1@ID-14036.news.dfncis.de...
> > MSVC defines a function, _alloca, that allows you to allocate memory right
> > on the stack at runtime.
>
> gcc invented that.

Can you support that claim? My understanding is that alloca() predates
gcc by at least a couple of decades.

...
> > C99 supports such variable-length stack allocation through variable length
> > arrays (VLAs).
>
> Really?  Does it say that VLAs must be on a "stack"?

Not directly; however, they obey scope rules that make some kind of
stack a natural implementation.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

MSVC defines a function, _alloca, that allows you to allocate memory right
on the stack at runtime. The allocation consist of a simple adjustment of
stack pointers so it's O(1). Upon exiting the function, the memory is
released in O(1) as well.

C99 supports such variable-length stack allocation through variable length
arrays (VLAs). I think this would be a interesting function to add to C++
with a C++ flavor to it (guaranteed destruction and all). Better yet, it
would be great if C++ offered the ability to allocate an array on the caller
function's stack, so you can create automatic objects that hold
variable-length data without having to perform any access to the free store.
Wow that would be cool.

Any thoughts?


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]