🚀 go-pugleaf

In article 41C67EA6@ecid.cig.mot.com,
Joe Walker <walkerjj@ecid.cig.mot.com> writes:
>Has allowing the following been considered?
>
>  int  length = strlen (some_string);
>  char buffer [ length ];
>
>I.E. allowing non const array sizing.

It is not supported by the C++ draft standard for the same reason it
is not supported by the C standard. It would mean in particular for auto
arrays that the size of the stack frame could not be known until a function
was entered, and could be different at each invocation. On some platforms
that is not a problem. On others it is difficult to implement, or forces
function calls to be much more expensive, or violates the ABI. For
static arrays, some object formats require the array size to be specified
at link time and not deferred until run time.

The standard could say that an implemention is allowed to simulate
variable-sized stack or static arrays by using the heap and automatically
deallocating the storage. IMHO that is not acceptable because in
portable code you would not know whether a declaration like
	char buffer[length];
could fail. It also could turn what looks like a simple declaration into
a heavy-weight operation.

You can get the effect you want by using an auto_ptr and heap allocation,
or by using an array class instead of a C-style array.

---
Steve Clamage, stephen.clamage@eng.sun.com
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

clamage@Eng.Sun.COM (Steve Clamage) writes:

>Joe Walker <walkerjj@ecid.cig.mot.com> writes:
>>Has allowing the following been considered?
>>
>>  int  length = strlen (some_string);
>>  char buffer [ length ];
>>
>>I.E. allowing non const array sizing.
>
>It is not supported by the C++ draft standard for the same reason it
>is not supported by the C standard.

The good news is that there is a quite significant chance that the next
C standard may include support for variable length arrays; if this happens,
the change is likely to propagate into C++ implementations.

>It would mean in particular for auto
>arrays that the size of the stack frame could not be known until a function
>was entered, and could be different at each invocation. On some platforms
>that is not a problem. On others it is difficult to implement, or forces
>function calls to be much more expensive, or violates the ABI.

But as you suggest below, on platforms for which stack allocation is
difficult, the compiler could simply allocate such arrays on the heap.
In any case, there is a very large variety of prior art in terms of
language implementations that support variable length arrays on a variety
of platforms.  For example, all Ada implementations support this.
So does GNU C.

>For static arrays, some object formats require the array size to be
>specified at link time and not deferred until run time.

Again, this problem could be easily solved by allocating such arrays
on the heap at program startup.

>The standard could say that an implemention is allowed to simulate
>variable-sized stack or static arrays by using the heap and automatically
>deallocating the storage.

I don't think the standard would need to say that.  An implementation
is already allowed to allocate whole stack frames on the heap if it
wants.  The standard should only specify the observable effects;
how various language constructs are implemented should be up to
the implementation.

>IMHO that is not acceptable because in
>portable code you would not know whether a declaration like
>	char buffer[length];
>could fail.

But that is *already* the case.  If you write a declaration like

	char buffer[50000];

it may fail, either at compile time or at run time.  Furthermore,
there is basically no way portable code can recover from such failures.

>It also could turn what looks like a simple declaration into
>a heavy-weight operation.

But that is already the case in C++.  A simple declaration may
invoke a constructor which can be a very heavy-weight operation.

>You can get the effect you want by using an auto_ptr and heap allocation,

You can't use an auto_ptr to point to an array.  You would have to write
an auto_array_ptr class.

>or by using an array class instead of a C-style array.

Both of those alternatives are less convenient and less efficient than
variable-length arrays would be.

--
Fergus Henderson             	WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au              	PGP: finger fjh@128.250.37.3
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In message <48t9t7$5c2@engnews1.eng.sun.com> - clamage@Eng.Sun.COM
(Steve Clamage) writes:
:>
:>In article 41C67EA6@ecid.cig.mot.com,
:>Joe Walker <walkerjj@ecid.cig.mot.com> writes:
:>>Has allowing the following been considered?
:>>
:>>  int  length = strlen (some_string);
:>>  char buffer [ length ];
:>>
:>>I.E. allowing non const array sizing.
:>
[...]
:>
:>The standard could say that an implemention is allowed to simulate
:>variable-sized stack or static arrays by using the heap and automatically
:>deallocating the storage. IMHO that is not acceptable because in
:>portable code you would not know whether a declaration like
:>	char buffer[length];
:>could fail. It also could turn what looks like a simple declaration into
:>a heavy-weight operation.

It would be a very strange machine which could not handle it.  We did it, 
trivally, in the 60's with quite ordinary machines, NO heavy weight operation.
Not any worse than running out of stack space at a procedure call with C now!
C and C++ ignored many of the very useful features of Fortran and Algol 
learned back then.  C and C++ are still a very high level assembly language
with an awful declaration syntax!

[...]
:>Steve Clamage, stephen.clamage@eng.sun.com
:

Ken Walter

* All the above is hearsay and the opinion of nobody in particular
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <DIHM2v.2Av@cadlab.it>, Alex Martelli <martelli@cadlab.it> wrote:
:>IMHO that is not acceptable because in
:>portable code you would not know whether a declaration like
:>	char buffer[length];
:>could fail.
:
:But that would be no different from the present situation!  I.e., in
:portable code you DO not know whether a declaration like
:	char buffer[16384];
:can fail; it depends on whether your current stack has space for
:it, on whether the OS can extend that stack dynamically for you,
:etc, etc.  And, if it does fail, there's no *portable* way to
:catch it, either.

The problem is more complex than this.  Imagine how unorthogonal it is
if you can make automatic array variable sized, but why then can't
an array in a class be made like this ? (Yes I know the reason, I'm
trying to point out the real problem).

eg.
  class Foo {
    const int X;
    int Bar[X];
  public:
    Foo() : X(10) { /* Array is size ten in here */ };
  };

I'm all for nifty features, but not at the expense of orthogonality.  You
then end up with nasty kludges.

There is *no* prior art for this.

:>You can get the effect you want by using an auto_ptr and heap allocation,
:
:auto_ptr does not handle builtin arrays, so how could it ever help here?
:If you new[] some memory, you cannot use the resulting pointer to an
:auto_ptr nor any other standards-supplied class -- you have to use a
:bare pointer, or roll-your-own -- in which latter case the following
:idea appears much more promising:
:

Why is there no auto_array_ptr in the DWP ? Is it an omission or a mistake ?

Regards,
	Rohan
-- 
----------------------------------------------------------------------------
rjl@iassf.easams.com.au	| All quotes can be attributed to my automated quote
Rohan Lenard            | writing tool.  Yours for just $19.95; and if you
+61-2-367-4555          | call now you'll get a free set of steak knives ...

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <9532616.4242@mulga.cs.mu.OZ.AU>,
Fergus Henderson <fjh@munta.cs.mu.OZ.AU> wrote:
> But as you suggest below, on platforms for which stack allocation is
> difficult, the compiler could simply allocate such arrays on the heap.
> In any case, there is a very large variety of prior art in terms of
> language implementations that support variable length arrays on a variety
> of platforms.  For example, all Ada implementations support this.
> So does GNU C.

I accept the prior-art argument and the usefulness argument.

But I don't accept this part: 'the compiler could simply allocate such
arrays on the heap.'

The compiler may have to use a hidden auto-pointer-like mechanism for
removing such arrays from the heap in cases of function returns,
longjmp, and exceptions.  I expect this would be reasonable for function
returns and exceptions.  But it would be new functionality for
'longjmp'.

I say 'may have to' because every processor I know can implement
variable-sized stack frames by subtracting an appropriate value from
the stack pointer at the appropriate time.  But what about processors I
don't know about?  Are there truly any processors in use which don't
support subtracting a computed value from the stack pointer?

Michael Chastain
mec@duracef.shout.net
Check out my cool trace-and-replay debugger:
ftp://tsx-11.mit.edu/pub/linux/sources/usr.bin/mec-0.3.tar.gz
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

mec@treflan.shout.net (Michael Elizabeth Chastain) writes:

>Fergus Henderson <fjh@munta.cs.mu.OZ.AU> wrote:
>> But as you suggest below, on platforms for which stack allocation is
>> difficult, the compiler could simply allocate such arrays on the heap.
[...]
>I accept the prior-art argument and the usefulness argument.
>
>But I don't accept this part: 'the compiler could simply allocate such
>arrays on the heap.'
>
>The compiler may have to use a hidden auto-pointer-like mechanism for
>removing such arrays from the heap in cases of function returns,
>longjmp, and exceptions.  I expect this would be reasonable for function
>returns and exceptions.  But it would be new functionality for
>'longjmp'.

OK, I agree that if you don't want memory leaks in the presence of longjmp(),
it is slightly more complicated.  But still not too hard.

One very simple way of doing it would be to allocate such arrays using
alloca(), and use Doug Gwyn's mostly portable public domain
implementation of alloca().  This is what GNU C does.  Here's an extract
from the comments in alloca.c in the gcc distribution:

|    The general concept of this implementation is to keep
|    track of all alloca-allocated blocks, and reclaim any
|    that are found to be deeper in the stack than the current
|    invocation.  This heuristic does not reclaim storage as
|    soon as it becomes invalid, but it will do so eventually.
| 
|    As a special case, alloca(0) reclaims storage without
|    allocating any.  It is a good idea to use alloca(0) in
|    your main control loop, etc. to force garbage collection.  */

So all you would need to do is allocate variable length arrays using
alloca(), and if you really need to recover memory ASAP, put a
call to alloca(0) in setjmp().

	#define setjmp(buf) (tmp = __setjmp(buf), alloca(0), tmp)

Another approach would be for the compiler to keep a linked list of all
the memory areas allocated for variable-length arrays.  When entering
the scope of a variable-length array, the compiler would allocate the
memory from the heap, and then insert a pointer to the memory at the
front of this linked list.  On exit, it would deallocate the memory and
remove the entry from the list.  Then in setjmp() it would save a
pointer to the front of the linked list, and in longjmp() it would
iterate down the list, deallocating the memory, until it reached the
link stored by setjmp().  This approach is actually pretty similar to how
Doug Gwyn's alloca() implementation works, except that it is (more) portable.

So for

	void foo(int n) {
		char s[n];	
		bar(s);
	}

the compiler could generate code equivalent to

	struct __link {
		void *ptr; __link *next;
		__link(void *p, __link *n) : ptr(p), next(n) {}
	} __list;

	void foo(int n) {
		char *s = new char[n];
		__list = new __link(s, __list);
		bar(s);
		__link *__old = __list;
		__list = __list->next;
		delete __old;
	}

setjmp(buf) would include `buf.link = __list;',
and longjmp(buf) would include

	while (__list != buf.link) {
		__link *__old = __list;
		__list = __list->next;
		delete __old;
	}

>I say 'may have to' because every processor I know can implement
>variable-sized stack frames by subtracting an appropriate value from
>the stack pointer at the appropriate time.  But what about processors I
>don't know about?  Are there truly any processors in use which don't
>support subtracting a computed value from the stack pointer?

The comments in Doug Gwyn's alloca() name "Gould's UTX/32" C
implementation, whatever that is, as being one for which this is not
possible.

But I think comercially significant machines for which this is not possible
are pretty thin on the ground these days, and in any case as demonstrated
above it is not difficult to implement variable length arrays even for such
machines without longjmp() causing any memory leaks.

--
Fergus Henderson             	WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au              	PGP: finger fjh@128.250.37.3
I will have little or no net access from Nov 30 until Dec 25.
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <9532616.4242@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU
(Fergus Henderson) writes:

    [Concerning  variable length arrays, and the compiler actually
	implementing them on the heap...]
|> I don't think the standard would need to say that.  An implementation
|> is already allowed to allocate whole stack frames on the heap if it
|> wants.  The standard should only specify the observable effects;
|> how various language constructs are implemented should be up to
|> the implementation.

Well, in C++, calling operator new() (or operator[] new()) is an
observable effect.  It should be clear that using these operators
is/is not allowed.  (It really doesn't matter which, as long as it is
clear.)

--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils, études et réalisations en logiciel orienté objet --
                -- A la recherche d'une activité dans une region francophone


[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Rohan Lenard asks:
> Why is there no auto_array_ptr in the DWP ? Is it an omission or a mistake ?

Neither.  The feeling in the committee was that that would be too close to
vector<>.  I.e. when you think you want an auto_array_ptr, consider using
a vector<> instead.  

Nathan Myers
myersn@roguewave.com

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <30BA28C5.50C6@netcom.com> you write:
>Rohan Lenard asks:
>> Why is there no auto_array_ptr in the DWP ? Is it an omission or a mistake ?
>
>Neither.  The feeling in the committee was that that would be too close to
>vector<>.  I.e. when you think you want an auto_array_ptr, consider using
>a vector<> instead.  

Which unfortunately is a bit sad, since there is a whole heap of code 
out there which would benefit from this immediately (without a significant
amount of rewrite).  Having to use vector of cause does impose a 
significant amount of rework - for little additional (on top of auto_ptr)
value :-(

Rohan

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Rohan Lenard asks:
>> Why is there no auto_array_ptr in the DWP ? Is it an omission or a mistake ?

Nathan Myers <ncm@netcom.com> writes:
>Neither.  The feeling in the committee was that that would be too close to
>vector<>.  I.e. when you think you want an auto_array_ptr, consider using
>a vector<> instead.  

In my humble opinion, this is a mistake; vector<> is a far bigger chunk of
code than auto_array_ptr<> and supports functionality beyond what a natural
auto_array_ptr would supply (the ability to extend the array by adding
more at the end, iterators, etc).  If there isn't a standard one, everyone
will roll their own.  Or worse: users will use auto_ptr inappropriately
since on many implementations delete will work OK on arrays of objects
that don't have destructors.

-- 
-- Joe Buck 	<jbuck@synopsys.com>	(not speaking for Synopsys, Inc)
Anagrams for "information superhighway":	Enormous hairy pig with fan
						A rough whimper of insanity

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

jbuck@Synopsys.COM (Joe Buck) wrote:
>
>Rohan Lenard asks:
>>> Why is there no auto_array_ptr in the DWP ? Is it an omission or a mistake ?
>
>Nathan Myers <ncm@netcom.com> writes:
>>Neither.  The feeling in the committee was that that would be too close to
>>vector<>.  I.e. when you think you want an auto_array_ptr, consider using
>>a vector<> instead.  
>
>In my humble opinion, this is a mistake; vector<> is a far bigger chunk of
>code than auto_array_ptr<> and supports functionality beyond what a natural
>auto_array_ptr would supply.

Actually, this need not be the case. If you _use_ a vector
"as if" it were a less kind of array type, the code
for the "extra" functionality won't be generated.
If the use is lexically restricted to a block, then
in theory a compiler could optimise vector to work exactly
like a dynamically allocated array.

Remember vector isn't really a template, it's a built in 
structuring tool of the C++ language just like 
"array" or "struct" is.

Don't expect this kind of optimisation right away -- 
we need stable working ISO C++ implementations first.


-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au



[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Nathan Myers <ncm@netcom.com> writes:
>>>....  The feeling in the committee was that that would be too close to
>>>vector<>.  I.e. when you think you want an auto_array_ptr, consider using
>>>a vector<> instead.  

John Max Skaller <maxtal@suphys.physics.su.oz.au> writes:
>>In my humble opinion, this is a mistake; vector<> is a far bigger chunk of
>>code than auto_array_ptr<> and supports functionality beyond what a natural
>>auto_array_ptr would supply.

jbuck@Synopsys.COM (Joe Buck) wrote:
>Actually, this need not be the case. If you _use_ a vector
>"as if" it were a less kind of array type, the code
>for the "extra" functionality won't be generated.

Rather, *some* of the code won't be generated.  In practice, you're
getting code and data you don't need, that slows down compilation
and occupies memory, because vectors must support the push_back
functionality (they need to grow).  auto_array_ptr<>, on the other
hand, doesn't impose such costs.

>Remember vector isn't really a template, it's a built in 
>structuring tool of the C++ language just like 
>"array" or "struct" is.

I'm not buying it, John.  That's just like saying stdio.h isn't really a
header file, since it's standard and C implementations could do various
kinds of magic when they see the string '#include <stdio.h>'.  But in
practice we still get compilers that work in the natural way.  And in
practice, vector is going to be a template for the next several years at
least.

>Don't expect this kind of optimisation right away -- 
>we need stable working ISO C++ implementations first.

Don't expect this kind of optimization for many years to come.
In any case, I'd advise against it: special-casing STL for improved
performance would mean templates stay inefficient.

-- 
-- Joe Buck 	<jbuck@synopsys.com>	(not speaking for Synopsys, Inc)


[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]