Concerns with dynamic arrays

[Nicol Bolas]

N3532 lays out a proposal for including a dynamic array type in C++ called `dynarray`. A "dynamic array" is an array who's length is fixed, but is only provided at runtime, rather than static arrays that have compile-time array lengths.

The big selling point of `dynarray`, and the reason it exists, is so that we can have stack-based arrays with runtime-determined sizes. Instead of taking the C99 approach of allowing this:

int size = 5;
Type arr[size];

We would instead allow this:

int size = 5;
dynarray<Type> arr(size);

The dynamic array proposal allows (but does not require) that `arr` in the above case be allocated on the stack. The dynamic array is only allowed to be allocated on the stack when the array itself is on the stack; if you were to do `new dynarray<Type>`, you would have a heap-allocated array.

I do have some concerns about this though. One is purely functional and easily resolved: `dynarray` should have a constructor that can use default-initialization of its array elements instead of value-initialization. But this should be true of all standard library containers and warrants a full proposal. Another is the lack of allocator support when not using stack memory; again, relatively easily resolved.

The main issue is this:

dynarray<Type> GetArray(int size)
{
  dynarray<Type> arr(size);
  //Fill in arr with stuff.
  return arr;
}

unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(GetArray(12));

So... what happens here? Assuming that elision works in this case, `dynarray`, we have a non-trivial problem. The `dynarray` being heap-allocated is going to have to heap-allocate its own memory. But the `dynarray` being stack allocated, the return value from `GetArray`, will stack-allocate its memory. Which means that it's contents will have to be copied into the heap-allocated `dynarray`.

And there is nothing that we can do about that. That's the problem.

It should be possible to create a `dynarray` on the stack which is required to use heap-allocated memory. Therefore, we can be certain that any such `dynarray` instance can be cheaply moved into another `dynarray` instance.

It should be the user's choice to use `dynarray` as a fixed-size `vector`, with all of the move characteristics of that class. Sometimes the user wants stack allocation for a fixed-size array; and sometimes they don't. We shouldn't leave that to chance; we should have some way of enforcing it.

Alternatively, if the user can't have that choice, then we need a fixed-size `vector` class that does have the move characteristics of `vector`, but without the resizing. In that case, `dynarray` should only be able to be used on the stack, not as class members or with `new` and such. The user should be able to choose; this choice can either come from `dynarray` itself, or it can come from picking which class to use.

But the current half-state, where you can't explicitly choose for an automatic variable to be heap-allocated, is not good.

[Marc]

Le mercredi 3 avril 2013 03:32:33 UTC+2, Nicol Bolas a écrit :

The main issue is this:

dynarray<Type> GetArray(int size)
{
  dynarray<Type> arr(size);
  //Fill in arr with stuff.
  return arr;
}

unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(GetArray(12));

So... what happens here? Assuming that elision works in this case, `dynarray`, we have a non-trivial problem. The `dynarray` being heap-allocated is going to have to heap-allocate its own memory. But the `dynarray` being stack allocated, the return value from `GetArray`, will stack-allocate its memory. Which means that it's contents will have to be copied into the heap-allocated `dynarray`.

Could you clarify your example? As far as I understand, with copy elision, there is no stack dynarray here. arr is constructed in the return value, which can't be on the stack.
(it would help to have an implementation to play with)

[Nicol Bolas]

Well, there's the question of whether copy elision can even work with `dynarray`. But beyond that, how is this not a stack object? You can elide the copy from `arr` into the return value, but you can't elide the copy construction from the return value into the `new` expression.

And if the `new` construction is somehow elided, then feel free to turn it into this:

dynarray<Type> arr = GetArray(12);
unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(std::move(arr));

The point is that I want to be able to have some way of ensuring that no copying happens in this case. If that were a `vector<Type>`, I would know that there would be no copying.

[Olaf van der Spek]

Op woensdag 3 april 2013 12:20:35 UTC+2 schreef Nicol Bolas het volgende:

Well, there's the question of whether copy elision can even work with `dynarray`. But beyond that, how is this not a stack object? You can elide the copy from `arr` into the return value, but you can't elide the copy construction from the return value into the `new` expression.

And if the `new` construction is somehow elided, then feel free to turn it into this:

dynarray<Type> arr = GetArray(12);
unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(std::move(arr));

The point is that I want to be able to have some way of ensuring that no copying happens in this case. If that were a `vector<Type>`, I would know that there would be no copying.

 Sounds like a unique_array<> or shared_array<> would be a better match for your use case. 

[Nicol Bolas]

Considering that those classes don't exist, and there are no proposals to add them, no they wouldn't. More importantly, there's no reason why we need such things if we're going to get a `dynarray` type that can be used anywhere.

[Marc]

Le mercredi 3 avril 2013 12:20:35 UTC+2, Nicol Bolas a écrit :

On Tuesday, April 2, 2013 11:53:07 PM UTC-7, Marc wrote:

Le mercredi 3 avril 2013 03:32:33 UTC+2, Nicol Bolas a écrit :

The main issue is this:

dynarray<Type> GetArray(int size)
{
  dynarray<Type> arr(size);
  //Fill in arr with stuff.
  return arr;
}

unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(GetArray(12));

So... what happens here? Assuming that elision works in this case, `dynarray`, we have a non-trivial problem. The `dynarray` being heap-allocated is going to have to heap-allocate its own memory. But the `dynarray` being stack allocated, the return value from `GetArray`, will stack-allocate its memory. Which means that it's contents will have to be copied into the heap-allocated `dynarray`.

Could you clarify your example? As far as I understand, with copy elision, there is no stack dynarray here. arr is constructed in the return value, which can't be on the stack.
(it would help to have an implementation to play with)

Well, there's the question of whether copy elision can even work with `dynarray`.

I think an implementation would help decide that.
 

But beyond that, how is this not a stack object? You can elide the copy from `arr` into the return value,

Note that when you elide this copy, the object that remains is the return value, not the local variable, so it would be conceivable that it uses the dynamic allocation and not the stack allocation.
 

but you can't elide the copy construction from the return value into the `new` expression.

move construction, no?

The point is that I want to be able to have some way of ensuring that no copying happens in this case. If that were a `vector<Type>`, I would know that there would be no copying.

Then use vector<Type>? If there was a perfect solution, we could modify vector. Since there are compromises to make, we end up with vector and dynarray that make some different choices.

Having a constructor dynarray(vector&&) might help with what you want to achieve (modulo some allocator issues). But it looks like you would be happy with simply duplicating some constructors (or giving them an extra parameter) so the user can influence the compiler's choice? Seems easy enough.

Note that I am not saying dynarray is a good or bad way to get alloca/VLA-like memory, I didn't think long enough about it.

[Olaf van der Spek]

On Thu, Apr 4, 2013 at 2:29 AM, Nicol Bolas <jmck...@gmail.com> wrote:
>> Sounds like a unique_array<> or shared_array<> would be a better match
>> for your use case.
>
>
> Considering that those classes don't exist, and there are no proposals to
> add them, no they wouldn't. More importantly, there's no reason why we need
> such things if we're going to get a `dynarray` type that can be used
> anywhere.

T read_file(str_ref);

What should T be if read_file returns the memory mapped data of a file?
My vote would be for shared_data / shared_array<unsigned char>



--
Olaf

[Olaf van der Spek]

On Thu, Apr 4, 2013 at 8:53 AM, Marc <marc....@gmail.com> wrote:
>> But beyond that, how is this not a stack object? You can elide the copy
>> from `arr` into the return value,
>
>
> Note that when you elide this copy, the object that remains is the return
> value, not the local variable, so it would be conceivable that it uses the
> dynamic allocation and not the stack allocation.

The return value is passed as an argument to the constructor, it's not
put directly on the heap.



--
Olaf

[Jeffrey Yasskin]

The *address* of the return value is passed as an argument to the
function, and if you look at the assembly generated for, say

std::vector<int> foo();
void* bar() {
return new std::vector<int>(foo());
}

you won't see a call to any vector copy or move constructors.

[Olaf van der Spek]

So this first does the new (allocation) and then passes the address on
the heap to foo() (for return value optimization)?
If it doesn't, how does it construct the vector on the heap without
moving or copying?

--
Olaf

[Jeffrey Yasskin]

Exactly. And it calls a matching operator delete if an exception's thrown.

> If it doesn't, how does it construct the vector on the heap without
> moving or copying?
>
> --
> Olaf
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.
> Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
>
>

[DeadMG]

I don't believe that would be legal under the current elision rules. 

[Lawrence Crowl]

On 4/3/13, Nicol Bolas <jmck...@gmail.com> wrote:
> On Tuesday, April 2, 2013 11:53:07 PM UTC-7, Marc wrote:
> > Le mercredi 3 avril 2013 03:32:33 UTC+2, Nicol Bolas a écrit :
> > > The main issue is this:
> > >
> > > dynarray<Type> GetArray(int size)
> > > {
> > > dynarray<Type> arr(size);
> > > //Fill in arr with stuff.
> > > return arr;
> > > }
> > >
> > > unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(GetArray(12));
> > >
> > > So... what happens here? Assuming that elision works in this
> > > case, `dynarray`, we have a non-trivial problem. The `dynarray`
> > > being heap-allocated is going to have to heap-allocate its own
> > > memory. But the `dynarray` being stack allocated, the return
> > > value from `GetArray`, will stack-allocate its memory. Which

> > > means that it's contents will have to be *copied* into the

> > > heap-allocated `dynarray`.
> >
> > Could you clarify your example? As far as I understand,
> > with copy elision, there is no stack dynarray here. arr is
> > constructed in the return value, which can't be on the stack.
> > (it would help to have an implementation to play with)
>
> Well, there's the question of whether copy elision can even
> work with `dynarray`. But beyond that, how is this not a stack
> object? You can elide the copy from `arr` into the return value,
> but you can't elide the copy construction from the return value
> into the `new` expression.
>
> And if the `new` construction is somehow elided, then feel free
> to turn it into this:
>
> dynarray<Type> arr = GetArray(12);
> unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(std::move(arr));
>
> The point is that I want to be able to have some way of
> ensuring that no copying happens in this case. If that were a
> `vector<Type>`, I would know that there would be no copying.

The problem here is that you cannot just 'move the pointer' when
the contents are on the stack. If you want the capability to move
the contents only when they are in the heap, you need to deal with
two effects.

First, you need to make the move operations detect when the
contents are on the stack. This makes the implementation of the
move system-dependent, something the current proposal does not
require. Indeed, the current proposal can be implemented with a
simple library and a small pattern-match on constructor calls in
the compiler. Adding a move of a different flavor would complicate
the implementation considerably.

Second, in the stack case, the move operation would still need to do
an element by element copy or move. That is, you are guaranteed to
at least have an O(n) iteration. If the element operation throws,
then the dynarray move may potentially throw, which is not good.
We could conditionally implement the move operations, but then you
would never 'know' that there would be no copying in your example.
(Presuming your example is Type as template parameter.)

Is there any lasting harm in not providing move in the initial
release?

--
Lawrence Crowl

[Nicol Bolas]

Yes. I need a fixed, runtime-sized array that has guaranteed reasonable move behavior (and moving each element is not "reasonable move behavior"). If `dynarray` cannot provide that, then we need an alternative that can.

And more to the point, if `dynarray` can't provide that... why would you ever use `dynarray` for anything other than a stack-based array that you will never move? At which point, we can then have errors for when you try to make it a global or a class member or allocate it on the heap.

So if what you're saying is true, then we need two classes: one for stack-based fixed-sized arrays, and one for heap-based fixed-sized arrays.

[Paul Tessier]

It seems there's a need for a fixed size array container, and a separate stack based allocator.  The stack allocator should prevent container copying and moving.  To achieve that would require changes to allocator_traits, without breaking standard behaviour.

When I say the allocator would prevent container copying, I mean to the same allocator type.  Copying form/to a stack allocator to/from a heap allocator makes sense, moving does not.

I'm all for a fixed size array container, then we can eliminate the need for new[]/delete[].  A stack based allocator, might have more uses than just a stack based array.  Splitting the concerns seems more achievable to me.

[Daniel Krügler]

2013/4/5 Paul Tessier <pher...@gmail.com>

It seems there's a need for a fixed size array container, [..]. 

Isn't this what std::array is intended for? (Sorry if I missed that you meant something differently with "a fixed size array container").

- Daniel

 

[Olaf van der Spek]

That's fixed at compile-time, we're looking for fixed at run-time.

[Nicol Bolas]

On Friday, April 5, 2013 5:08:41 AM UTC-7, Paul Tessier wrote:

It seems there's a need for a fixed size array container, and a separate stack based allocator.  The stack allocator should prevent container copying and moving.  To achieve that would require changes to allocator_traits, without breaking standard behaviour.

When I say the allocator would prevent container copying, I mean to the same allocator type.  Copying form/to a stack allocator to/from a heap allocator makes sense, moving does not.

I'm all for a fixed size array container, then we can eliminate the need for new[]/delete[].  A stack based allocator, might have more uses than just a stack based array.  Splitting the concerns seems more achievable to me.

The problem is that all other containers can grow arbitrarily large. This works against stack allocation. Now, perhaps the idea is that the allocator will allocate from the stack once, and if you try again it goes to heap memory. But ultimately, I think allowing this for other classes is likely to fail. How would it work for any of the node-based containers, for example? They tend to allocate nodes one at a time.

[Paul Tessier]

Agreed, but anyone explicitly using a stack allocator, or similar structure must already know the cost and potential down falls.  Creating multiple stack arrays has the same chance of failure. All structures using a stack allocator are expected to have limited lifetime and small size.

Basically, you do something like this, you better know what you are doing.

[Nicol Bolas]

On Friday, April 5, 2013 8:19:58 AM UTC-4, Nicol Bolas wrote:

On Friday, April 5, 2013 5:08:41 AM UTC-7, Paul Tessier wrote:

It seems there's a need for a fixed size array container, and a separate stack based allocator.  The stack allocator should prevent container copying and moving.  To achieve that would require changes to allocator_traits, without breaking standard behaviour.

When I say the allocator would prevent container copying, I mean to the same allocator type.  Copying form/to a stack allocator to/from a heap allocator makes sense, moving does not.

I'm all for a fixed size array container, then we can eliminate the need for new[]/delete[].  A stack based allocator, might have more uses than just a stack based array.  Splitting the concerns seems more achievable to me.

The problem is that all other containers can grow arbitrarily large. This works against stack allocation. Now, perhaps the idea is that the allocator will allocate from the stack once, and if you try again it goes to heap memory. But ultimately, I think allowing this for other classes is likely to fail. How would it work for any of the node-based containers, for example? They tend to allocate nodes one at a time.

On Friday, April 5, 2013 5:27:33 AM UTC-7, Paul Tessier wrote: 

Agreed, but anyone explicitly using a stack allocator, or similar structure must already know the cost and potential down falls.  Creating multiple stack arrays has the same chance of failure. All structures using a stack allocator are expected to have limited lifetime and small size.

Basically, you do something like this, you better know what you are doing.

It's not a question of knowing what you're doing or not. It's a question of what it means to deallocate memory from a stack after you've allocated memory from farther down the stack. These are things that the specification is going to have to specify.

Also, don't overestimate the user. People see "stack allocator" and they will think "free performance!" and start piling on. So let's not assume that people are certain of the consequences of using these.

[Paul Tessier]

I just believe it would be harder to formalize a stack allocated array vs a stack allocator, which could be constructed from stack allocated arrays, which internally would need to have some form of an internal formal stack allocator.  Just formalizing a stack allocator might be easier, especially since an allocator just returns a naked array anyway ( which is beyond me, why no RAII? ).

The point about users is well taken.  I only meant that anyone willing to fiddle with the stack is already risking a lot.  Are there any systems that automatically extend the stack on exhaustion?

[Lawrence Crowl]

On 4/5/13, Nicol Bolas <jmck...@gmail.com> wrote:
> On Thursday, April 4, 2013 7:10:36 PM UTC-7, Lawrence Crowl wrote:
> > Is there any lasting harm in not providing move in the initial
> > release?
>
> Yes. I need a fixed, runtime-sized array that has guaranteed
> reasonable move behavior (and moving each element is not
> "reasonable move behavior"). If `dynarray` cannot provide that,

> then we need an alternative that *can*.

For data structures like this, and for concurrent data structures,
we get into the situation where small changes in interface can have
significant effects on implementation performance. I'm wondering how
we are going to manage the consequential complexity. Ideas welcome.

> And more to the point, if `dynarray` can't provide that... why

> would you * ever* use `dynarray` for anything other than a

> stack-based array that you will never move? At which point, we
> can then have errors for when you try to make it a global or a
> class member or allocate it on the heap.

Move semantics only helps when your abstraction is implemented as
a handle and separately allocated data chunk. If the dynarray is
in the data chunk, it need never be moved directly. As for why
you would use it for anything else, well sometimes you want type
compatibility.

> So if what you're saying is true, then we need two classes:
> one for stack-based fixed-sized arrays, and one for heap-based
> fixed-sized arrays.

Sounds reasonable.

--
Lawrence Crowl

[Mikhail Semenov]

Why don't we introduce simple dynamic arrays in objects, which can be allocated in the same place as the objects (stack or heap) they belong to?

For example, like this:

class A
{
   double x[];
public:     
    A(std::size_t n):x(n) {}
   ...  
};

[Marshall Clow]

What is sizeof(A) ?

-- Marshall

Marshall Clow Idio Software <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki

[Marshall Clow]

On Apr 20, 2013, at 8:49 AM, Mikhail Semenov <mikhailse...@gmail.com> wrote:

On Saturday, April 20, 2013 4:23:49 PM UTC+1, Marshall wrote:

On Apr 20, 2013, at 4:21 PM, Mikhail Semenov <mikhailse...@gmail.com> wrote: 

> Why don't we introduce simple dynamic arrays in objects, which can be allocated in the same place as the objects (stack or heap) they belong to? 
> For example, like this: 
> class A 
> { 
>    double x[]; 
> public:       
>     A(std::size_t n):x(n) {} 
>    ...   
> }; 

What is sizeof(A) ? 

To be honest, I don't care what sizeof(a) will be for a dynamically allocated array. But if you want a formal definition, then the same

as in

void f(double a[]);

 

which will be the size of the pointer (in most cases 4 or 8 depending on the system).

Let me try again.

If I write:

A foo[10];

How big is foo?   How would the compiler allocate space on the stack/globals/wherever for foo?

How many elements are there in foo[3] ? Is that what you want? How would you change that?

[Mikhail Semenov]

By default, in this case the default constructor would be undefined. The used has to provide it if they want:

 

 class A 
{ 
    double x[]; 
public:

     A():x(50) {}       

     A(std::size_t n):x(n) {} 
    ...   
}; 

 

 

On Wednesday, April 24, 2013 5:51:52 AM UTC+1, Marshall wrote:

On Apr 20, 2013, at 8:49 AM, Mikhail Semenov <mikhailse...@gmail.com> wrote:

On Saturday, April 20, 2013 4:23:49 PM UTC+1, Marshall wrote:

On Apr 20, 2013, at 4:21 PM, Mikhail Semenov <mikhailse...@gmail.com> wrote: 

> Why don't we introduce simple dynamic arrays in objects, which can be allocated in the same place as the objects (stack or heap) they belong to? 
> For example, like this: 
> class A 
> { 
>    double x[]; 
> public:       
>     A(std::size_t n):x(n) {} 
>    ...   
> }; 

What is sizeof(A) ? 

To be honest, I don't care what sizeof(a) will be for a dynamically allocated array. But if you want a formal definition, then the same

as in

void f(double a[]);

 

which will be the size of the pointer (in most cases 4 or 8 depending on the system).

Let me try again.

If I write:

A foo[10];

How big is foo?   How would the compiler allocate space on the stack/globals/wherever for foo?

How many elements are there in foo[3] ? Is that what you want? How would you change that?

-- Marshall

Marshall Clow     Idio Software   <mailto:mc...@gmail.com>

[Jonathan Wakely]

On Wednesday, April 24, 2013 6:54:38 PM UTC+1, Mikhail Semenov wrote:

By default, in this case the default constructor would be undefined. The used has to provide it if they want:

 

 class A 
{ 
    double x[]; 
public:

     A():x(50) {}       
     A(std::size_t n):x(n) {} 
    ...   
}; 

That doesn't answer the question, you're missing the point.  In C++ sizeof(A) must be a compile-time constant, so it cannot depend on constructor parameters.

Array access depends on all objects of the same type having the same fixed-size, for pointer arithmetic to work.

[Mikhail Semenov]

Jonathan,

 

I repeat my point: the value is the same as in

void f(double x[]);

which is the size of the pointer.

 

x[] works a bit similar to a constant reference to memory space which is allocated on the stack during construction.

It's not really part of the class. If yoy ask about sizeof(A): it will be always the same. The allocated array is not part of it.

There should be a difference between x[] and x[100]: the first is a refrence to memory; the second is an array itself. But both

can be converted to pointers.

 

Regards,

Mikhail.

 

[corn...@google.com]

On Thursday, April 25, 2013 12:09:42 PM UTC+2, Mikhail Semenov wrote:

Jonathan,

 

I repeat my point: the value is the same as in

void f(double x[]);

which is the size of the pointer.

But here, x *is* a pointer. But if you have a class A containing a VLA, and you write

A a(arguments, to, determine, stack, size);

should a be a pointer? Or just that sizeof should report it as one? 

[Mikhail Semenov]

To clarify, I think I have to explain it formally. The following definition

class A 
{ 

public:
    double x[]; 

     A():x(50) {}       
     A(std::size_t n):x(n) {} 
    ...   
}; 

 

is functionally equivalent to

class A
{
public:
    double *const x;
    A():x(new double[50]) {}
    A(unsigned n):x(new double[n]) {}
    ~A() { delete [] x;}
 };

 

The only difference is that double x[] can be allocated on the stack of the object of class A is allocated on the stack.

 

 

--

[Lawrence Crowl]

On 4/26/13, Mikhail Semenov <mikhailse...@gmail.com> wrote:
> To clarify, I think I have to explain it formally. The following
> definition
>
> class A
> {
> public:
> double x[];
> A():x(50) {}
> A(std::size_t n):x(n) {}
> ...
> };

The declaration of x is illegal. Quoting from N3497, "An array of
runtime bound shall only be used as the type of a local object with
automatic storage duration."

You can use dynarray instead.

class A
{
public:
std::dynarray<double> x;

A():x(50) {}
A(std::size_t n):x(n) {}
...
};

> is functionally equivalent to
>
> class A
> {
> public:

> double * const x;

> A():x(new double[50]) {}
> A(unsigned n):x(new double[n]) {}
> ~A() { delete [] x;}
> };

With dynarray, it would be something more like

class A
{
public:
std::pair<double *, size_t> x;
A():x(new double[50], 50) {}
A(unsigned n):x(new double[n], n) {}
~A() { delete [] x.first;}
};

> The only difference is that double x[] can be allocated on the
> stack of the object of class A is allocated on the stack.

That much is true of dynarray, though pragmatically, the constructor
of A will likely need to be inlined.

--
Lawrence Crowl

[Mikhail Semenov]

Hello Lawrence,

 

Thank you for this. I was just trying to suggest a simpler syntax for "dynamic arrays".

I am aware that x[] is illegal in classes.

 

Regards,

Mikhail.

 

 

 

[Michał Dominiak]

Your "simpler syntax":

1) is more confusing than dynarray - x is a pointer, not an array!

2) is not searchable in most web search engines (while dynarray is)

3) does not carry information about size (while dynarray does)

Cheers,

Michał Dominiak

[Mikhail Semenov]

Will I have the same "efficiency" in debug mode as for the STL vectors?

Here are some benchmarks for the code that reverses an array of 10,000,000 elements:

 

test              | Microsoft VS2012 | GCC 4.8.1 (g++)
vector (indexed)  |  1.112 sec.      | 0.126 sec.
vector+iterators  |  21.878 sec.     | 0.363 sec.
standard pointers |  0.042  sec.     | 0.046 sec.

 

The file is attached.

Most of the code people run during development is in debug mode.

 

Enjoy!

 

Mikhail

[Daniel Krügler]

2013/4/28 Mikhail Semenov <mikhailse...@gmail.com>:

> Will I have the same "efficiency" in debug mode as for the STL vectors?

This depends on a concrete implementation, of-course. The standard
does not mandate any such modes.

> Here are some benchmarks for the code that reverses an array of 10,000,000
> elements:
>
> test | Microsoft VS2012 | GCC 4.8.1 (g++)
> vector (indexed) | 1.112 sec. | 0.126 sec.
> vector+iterators | 21.878 sec. | 0.363 sec.
> standard pointers | 0.042 sec. | 0.046 sec.
>
> The file is attached.
> Most of the code people run during development is in debug mode.

Maybe, but keep in mind that a Standard specification doesn't prevent
an implementation to add such debug modes also to the built-in runtime
arrays, so this example really doesn't demonstrate a weakness of the
providing std::dynarray via a Library implementation versus a built-in
technique. Furthermore, existing implementations can typically be
controlled to not perform any such checking even in debug mode at all.

These are really no arguments against Library-provided features, this
is all about quality of implementation. You should discuss such things
in vendor-specific newsgroups.

- Daniel

[Nicol Bolas]

On Sunday, April 28, 2013 5:58:19 AM UTC-7, Mikhail Semenov wrote:

Will I have the same "efficiency" in debug mode as for the STL vectors?

Here are some benchmarks for the code that reverses an array of 10,000,000 elements:

 

test              | Microsoft VS2012 | GCC 4.8.1 (g++)
vector (indexed)  |  1.112 sec.      | 0.126 sec.
vector+iterators  |  21.878 sec.     | 0.363 sec.
standard pointers |  0.042  sec.     | 0.046 sec.

 

The file is attached.

Most of the code people run during development is in debug mode.

You know, you can turn off all of the debugging stuff in Microsoft's standard library with #defines, right?

[Mikhail Semenov]

Nicol,

 

Yes if I use the following options for Microsoft VC++:

(1) Use option "program database" /Z7 instead of /ZI "edit and continue".

(2) All options -> SDL -> NO /-sdl

(3) #define _ITERATOR_DEBUG_LEVEL 0

I will get much better figures:

vector (indexed) 0.121 sec.
vector+iterators 0.717
standard pointers 0.041

My point is that it is still slower than pointers.  If I run a system simulator in a debug mode (which I often do), it runs not as fast as I would like.

Another issue (maybe small issue) is that in VS2012  a vector's element v[i] is not displayed during debugging:

you have to write v.operator[](i). 

 

Anyway, since the dynamic arrays have been approved by the Committee we have to live with it.

 

Regards,

Mikhail

 

P.S. By the way, similar issues applies to some other STL features. Although bind is fast in the release mode, it's rather slow

in the debug mode.

[Dominic Burghuber]

On Wednesday, April 3, 2013 2:32:33 AM UTC+1, Nicol Bolas wrote:

N3532 lays out a proposal for including a dynamic array type in C++ called `dynarray`. A "dynamic array" is an array who's length is fixed, but is only provided at runtime, rather than static arrays that have compile-time array lengths.

The big selling point of `dynarray`, and the reason it exists, is so that we can have stack-based arrays with runtime-determined sizes. Instead of taking the C99 approach of allowing this:

int size = 5;
Type arr[size];

We would instead allow this:

int size = 5;
dynarray<Type> arr(size);

The dynamic array proposal allows (but does not require) that `arr` in the above case be allocated on the stack. The dynamic array is only allowed to be allocated on the stack when the array itself is on the stack; if you were to do `new dynarray<Type>`, you would have a heap-allocated array. for me. But it isn't mandated by the standard (for fear of causing complex a lot of work for compiler implementers it seems - given that in the proposal it mentions implementation as a separate library rather than deeper integration to provide for stack allocation).

I'm looking at the runtime-sized array proposals & I really want to use dynarray in my code base, but proposing to rely on QoI seems is way to wishy-washy & indeterminate to go ahead and do so. If there is no guaranteed benefit to dynarray users when dynarray utilises heap allocation, as opposed to just controlling a vector during usage, then the big stack-usage selling point is really what a run-time sized array is all about.

If there are requirements satisfied by a heap using dynarray that can't be satisfied by a vector, then there could legitimately be 2 separate types as suggested (one guaranteed to utilise the underlying stack and the other utilising the heap & movable). It's the stack-utilising runtime-sized arrays that considerably offer what vector can't.

std::dynarray to language runtime arrays shouldbe what std::array is to raw ("C-style") arrays - a wrapper exposing an API providing better safety, convenience of use, & consistent integration with the rest of the library (iterators, algorithms, etc.). Just standardised arrays whose elements have automatic storage duration, sized at runtime, integrating well with the rest of the library. Guaranteed so to be relied upon.

[DeadMG]

dynarray will never be a first-class citizen of the rest of the library. It will forever be endowed with numerous special cases.

[Lawrence Crowl]

On 5/31/13, Dominic Burghuber <dmb.you...@googlemail.com> wrote:
> I'm looking at the runtime-sized array proposals & I really
> want to use dynarray in my code base, but proposing to rely on
> QoI seems is way to wishy-washy & indeterminate to go ahead and
> do so. If there is no guaranteed benefit to dynarray users when
> dynarray utilises heap allocation, as opposed to just controlling
> a vector during usage, then the big stack-usage selling point is
> really what a run-time sized array is all about.

It is also about knowing that the size will not change. If you
want to create a shadow array, then it is very handy to know that
the size cannot change because if you do not know that, then you
need an additional communcation channel.

> If there are requirements satisfied by a heap using dynarray that
> can't be satisfied by a vector, then there could legitimately
> be 2 separate types as suggested (one guaranteed to utilise the
> underlying stack and the other utilising the heap & movable). It's
> the stack-utilising runtime-sized arrays that considerably offer
> what vector can't.

As above. But also, if the dynarray is allocated on the heap,
then its storage cannot be allocated on the stack. So the choice
of implementation must be present. Prohibiting dynarray from being
heap allocated has some undesireable consequences.

> std::dynarray to language runtime arrays shouldbe what std::array
> is to raw ("C-style") arrays - a wrapper exposing an API providing
> better safety, convenience of use, & consistent integration with
> the rest of the library (iterators, algorithms, etc.). Just
> standardised arrays whose elements have automatic storage
> duration, sized at runtime, integrating well with the rest of
> the library. Guaranteed so to be relied upon.

A guarantee here would be counter-productive. First, it delays
the time until the feature is available. Second, in multi-threaded
environments, stack size is often heavily constrained and defined
by the "high water mark" in any thread. You want the permission
to shift the occasional extra-large allocation to the heap in order
to get enough threads into the available memory.

If on-stack allocation is important to you, let your vendor know.

--
Lawrence Crowl

[Dominic Burghuber]

On Friday, May 31, 2013 9:26:09 PM UTC+1, Lawrence Crowl wrote:

It is also about knowing that the size will not change.  If you  want to create a shadow array, then it is very handy to know that  the size cannot change because if you do not know that, then you  need an additional communication channel.

I don't know what a dynamically allocated dynarray could give me that std::vector can't. I can manage (constrain usage of) a vector in a way that I ensure the size will not change. I've also seen it said that it may be portable to other types (std::vector is also contiguous & just as portable to other types, including across an ABI). Plus I can also move & copy it around without worrying it may be on the stack, adjust it's backing store and reuse it somewhere completely elsewhere, etc., etc. dynarray seems pretty limited in that respect (due to constraints it may be on the stack).

Are any gains of dynarray when utilising dynamic storage (vs std::vector) all dependent on the QoI? Is there anything with a std::dynarray that can't be done in using (including how you manage) a std::vector? Other than you "may" get an optimisation (i.e. possible stack usage depending on implementation) when used as an automatic variable.
 

But also, if the dynarray is allocated on the heap, then its storage cannot be allocated on the stack.  So the choice of implementation must be present.  Prohibiting dynarray from being heap allocated has some undesireable consequences.

I understand, like new-ing std::array. It's more that an implementation of dynarray may dynamically allocate its elements underneath the hood, not that the container itself can reside in dynamic memory. I'm desiring automatic lifetime allocation of elements, fully understanding that actual stack memory is implementation defined, but that if I'm ever going to get it then for that chance I need a guarantee that the container be allocating its elements with automatic lifetime within the container itself (& as an aside - probably a new thread off a platform's main app thread).
 

> std::dynarray to language runtime arrays shouldbe what std::array
> is to raw ("C-style") arrays - a wrapper exposing an API providing
> better safety, convenience of use, & consistent integration with
> the rest of the library (iterators, algorithms, etc.). Just
> standardised arrays whose elements have automatic storage
> duration, sized at runtime, integrating well with the rest of
> the library. Guaranteed so to be relied upon.

A guarantee here would be counter-productive.  First, it delays
the time until the feature is available.  

 

 Ok, but as you know, once standardised there is next to no chance of changing something like this without breaking code. Is this some kind of phasing in strategy? If so will it be mandatory eventually? I've not seen that before with C++ standards!

 

Second, in multi-threaded environments, stack size is often heavily constrained and defined
by the "high water mark" in any thread.

You would expect users to be sensible in any usage of a stack-allocated array, & test their code. Just like usage with raw arrays or std::array when not part of a dynamic allocation.
 

You want the permission to shift the occasional extra-large allocation to the heap in order to get enough threads into the available memory.

I was going to do that for my prototype dynarray implementation. In that if the specified element count on construction * sizeof(T) is a certain size, switch from a private allocation function utilising alloca /_alloca to a different private allocation function for new-ing memory. But as yet I didn't bother because I can just use a vector in such a case (& again I don't see the benefits that dynarray gives me in that case vs vector).
 

If on-stack allocation is important to you, let your vendor know.

It would be nice and speedy for small arrays in tight spaces. Its the guaranteed automatic duration of elements to the container that I was hoping dynarray could give me & also language runtime-sized arrays with automatic duration.

Am I missing something (i.e. something isn't clicking about what is proposed yet)? Should the proposal be fully ratified internationally, am I just wanting something I can't ever know for sure I'm going to get via the proposed?

Thank you,

[Dominic Burghuber]

To clarify, I'm just looking for that real sweet spot between std::array & std::vector, so I can data-drive my code, read that data & determine at runtime what size I want my fixed-size, containers to be. For anything that might grow there's std::vector, or others. And for those fixed size containers I want them then just like array (elements in a continguous block, allocated however I choose to allocate the container, whether automatically or dynamically, not choosen for me by an implementation allocating the backing store dynamically). I was hoping the standard would mandate that.

[Nevin Liber]

On May 31, 2013, at 6:34 PM, Dominic Burghuber
<dmb.you...@googlemail.com> wrote:

> Plus I can also move & copy [vector] around without worrying it may be on the stack,

The problem is, you cannot. You have to ensure that the lifetime of
the storage is at least as long as all copies of the vector. Dynarray
solves this.
--
Nevin ":-)" Liber
<mailto:ne...@eviloverlord.com>
(847) 691-1404
(sent from my iPad)

[Nicol Bolas]

On Friday, May 31, 2013 4:34:02 PM UTC-7, Dominic Burghuber wrote:

On Friday, May 31, 2013 9:26:09 PM UTC+1, Lawrence Crowl wrote:

It is also about knowing that the size will not change.  If you  want to create a shadow array, then it is very handy to know that  the size cannot change because if you do not know that, then you  need an additional communication channel.

I don't know what a dynamically allocated dynarray could give me that std::vector can't. I can manage (constrain usage of) a vector in a way that I ensure the size will not change.

Only if your code is the only code that touches that object. If you hand a non-const `std::vector` off to code you don't control, there's no way that you can guarantee that someone won't change the size.

Having a dynamically allocated array who's size guarantee-ably cannot be changed after construction is a good thing. Someone mentioned that it could be done as a "container adapter" wrapper over std::vector, which would also facilitate move support into and out of it.

 

Are any gains of dynarray when utilising dynamic storage (vs std::vector) all dependent on the QoI? Is there anything with a std::dynarray that can't be done in using (including how you manage) a std::vector? Other than you "may" get an optimisation (i.e. possible stack usage depending on implementation) when used as an automatic variable.

Yes; that's the point.

The alternatives are these: a dynarray class which cannot be stack allocated, a dynarray class which must be stack allocated, or what we have now. The first one doesn't actually solve the problem of wanting stack-allocated memory inside other objects.

The second one is terrible, because when a particular system will prevent stack allocation is implementation-dependent. Some systems might allow you to stack allocate a 30,000 integers; some might not. You would have to have two different code-paths for every use of dynarray: one for if it works, and one for if it doesn't.

So the third one is the only viable alternative: allow the implementation to define when it will be stack allocated, but design the interface so that we always assume it is (thus no move support).

[Róbert Dávid]

The second one is terrible, because when a particular system will prevent stack allocation is implementation-dependent. Some systems might allow you to stack allocate a 30,000 integers; some might not. You would have to have two different code-paths for every use of dynarray: one for if it works, and one for if it doesn't.

I'm not sure it is actually that terrible how it sounds to you - it's the same thing when you want to have a std::array<int, 30000> - some systems might allow you to do that, some might not, and you will have two different code-paths..

For me, dynarray<int> arr(n); is to int arr[n]; what array<int, 10> arr; is to int arr[10]; So dynarray should behave exactly like array, with the exact same benefits and drawbacks it has - including move support! (meaning moving elements into the new container). Every dynarray example should behave exactly how array works, with adding the actual size to the type, so your example in the first post should work exactly the same as:

template<int size>
array<Type, size> GetArray()
{
  array<Type, size> arr
  //Fill in arr with stuff.
  return arr;
}

unique_ptr<array<Type, 12>> arrPtr = new array<Type, 12>(GetArray<12>());

Everyone knows what is happening here, why should the case with dynarray be any different. (*khm* make_unique *khm*)

Moving on, the case of runtime-const-size stack-allocated container is a different beast, dynarray should not try to solve it by its own, but unique_ptr<dynarray<T>> is what one needs in this case; the same way how unique_ptr<array<T, n>> works for a compile-time-size stack allocated arrays. The interface might be a bit wonky due to the pointer semantics though, but it's not that bad, you just have to use (*unique_ptr_to_dynarray_of_int)[42]; instead of vector_of_int[42];

Regards, Robert

[Lawrence Crowl]

On 6/2/13, Róbert Dávid <lrd...@gmail.com> wrote:
> > The second one is terrible, because when a particular system
> > will prevent stack allocation is implementation-dependent. Some
> > systems might allow you to stack allocate a 30,000 integers;
> > some might not. You would have to have two different code-paths
> > for every use of dynarray: one for if it works, and one for if
> > it doesn't.
>
> I'm not sure it is actually that terrible how it sounds to you
> - it's the same thing when you want to have a std::array<int,
> 30000> - some systems might allow you to do that, some might not,
> and you will have two different code-paths.

Writing two different code paths in source code is a programming
burden. If those two paths can be handled by the compiler,
everyone wins.

> For me, dynarray<int> arr(n); is to int arr[n]; what
> array<int, 10> arr; is to int arr[10];

Okay so far.

> So dynarray should behave exactly like array,

But you cannot put int arr[n] inside a struct. So, there is a
pretty fundamental restriction we would like to avoid with dynarray.

> with the exact same benefits and drawbacks it has - including move
> support! (meaning moving elements into the new container). Every
> dynarray example should behave exactly how array works, with
> adding the actual size to the type, so your example in the first
> post should work exactly the same as:
>
> template<int size>
> array<Type, size> GetArray()
> {
> array<Type, size> arr
> //Fill in arr with stuff.
> return arr;
> }
>
> unique_ptr<array<Type, 12>> arrPtr
> = new array<Type, 12>(GetArray<12>());
>
> Everyone knows what is happening here, why should the case with
> dynarray be any different. (*khm* make_unique *khm*)

We could reasonably add move construction to dynarray, but not move
assignment. The reason is that move assignment would potentially
change the size, which we do not permit by design.

> Moving on, the case of runtime-const-size stack-allocated
> container is a different beast, dynarray should not try to solve
> it by its own, but unique_ptr<dynarray<T>> is what one needs in
> this case; the same way how unique_ptr<array<T, n>> works for
> a compile-time-size stack allocated arrays. The interface might
> be a bit wonky due to the pointer semantics though, but it's not
> that bad, you just have to use
>
> (*unique_ptr_to_dynarray_of_int)[42]; instead of vector_of_int[42];

I fail to understand how adding unique_ptr in here helps us get
stack allocation.

--
Lawrence Crowl

[Nicol Bolas]

On Sunday, June 2, 2013 4:32:14 PM UTC-7, Róbert Dávid wrote:

The second one is terrible, because when a particular system will prevent stack allocation is implementation-dependent. Some systems might allow you to stack allocate a 30,000 integers; some might not. You would have to have two different code-paths for every use of dynarray: one for if it works, and one for if it doesn't.

I'm not sure it is actually that terrible how it sounds to you - it's the same thing when you want to have a std::array<int, 30000> - some systems might allow you to do that, some might not, and you will have two different code-paths..

There's a really big difference here. If it won't let me do `std::array<int, 30000>`, the compiler will tell me. I will know before my application ships. Therefore, I will not need different code-paths; I will simply change my code for the lowest-common-denominator compiler.

That's not the case for `dynarray`. Not unless you can ensure the execution of all of your code in every reasonable configuration on every expected system.
 

For me, dynarray<int> arr(n); is to int arr[n]; what array<int, 10> arr; is to int arr[10];

Well, there's your problem: that's not what dynarray is for. It's wrong to blame a class for not doing something that it's not trying to do. Rather than trying to convert a class into being what you think it ought to be, you should be asking for a class that has the particular features you want it to have.

Moving on, the case of runtime-const-size stack-allocated container is a different beast, dynarray should not try to solve it by its own, but unique_ptr<dynarray<T>> is what one needs in this case; the same way how unique_ptr<array<T, n>> works for a compile-time-size stack allocated arrays.

No it does not. `unqiue_ptr<array<>>` does not allocate anything on the stack. `array<>` is only allocated on the stack if it is allocated on the stack, and `unique_ptr` cannot store stack-allocated objects. So if you want to create a `unique_ptr<array<>>`, you're going to have to heap allocate that `array`.

[Róbert Dávid]

2013. június 3., hétfő 11:49:07 UTC+2 időpontban Nicol Bolas a következőt írta:

On Sunday, June 2, 2013 4:32:14 PM UTC-7, Róbert Dávid wrote:

The second one is terrible, because when a particular system will prevent stack allocation is implementation-dependent. Some systems might allow you to stack allocate a 30,000 integers; some might not. You would have to have two different code-paths for every use of dynarray: one for if it works, and one for if it doesn't.

I'm not sure it is actually that terrible how it sounds to you - it's the same thing when you want to have a std::array<int, 30000> - some systems might allow you to do that, some might not, and you will have two different code-paths..

There's a really big difference here. If it won't let me do `std::array<int, 30000>`, the compiler will tell me. I will know before my application ships. Therefore, I will not need different code-paths; I will simply change my code for the lowest-common-denominator compiler.

No it doesn't. I just tested it on MSVC11.3 and ICC 2013.3 on Windows 8 and GCC 4.6.1 and on Ubuntu 11.10. None of them told me this is bad, all dies only at runtime:

#include <array>
int main()
{
  std::array<int, 100*1000*1000> a;
  return 0;
}

 

For me, dynarray<int> arr(n); is to int arr[n]; what array<int, 10> arr; is to int arr[10];

Well, there's your problem: that's not what dynarray is for. It's wrong to blame a class for not doing something that it's not trying to do. Rather than trying to convert a class into being what you think it ought to be, you should be asking for a class that has the particular features you want it to have.

I beg your pardon, are you saying I cannot use dynarray<int> arr(n) instead of int arr[n], unlike how I can use array<int, 10> instead of int[10]?? What is the point of dynarray then?
 

Moving on, the case of runtime-const-size stack-allocated container is a different beast, dynarray should not try to solve it by its own, but unique_ptr<dynarray<T>> is what one needs in this case; the same way how unique_ptr<array<T, n>> works for a compile-time-size stack allocated arrays.

No it does not. `unqiue_ptr<array<>>` does not allocate anything on the stack. `array<>` is only allocated on the stack if it is allocated on the stack, and `unique_ptr` cannot store stack-allocated objects. So if you want to create a `unique_ptr<array<>>`, you're going to have to heap allocate that `array`.

Oh my god, sorry, this is a big time mistype, I should not write these mails at 1:30 am.. I meant a heap allocated container. Heap heap heap.

Regards, Robert

[Daniel Krügler]

2013/6/3 Róbert Dávid <lrd...@gmail.com>:

>
> No it doesn't. I just tested it on MSVC11.3 and ICC 2013.3 on Windows 8 and
> GCC 4.6.1 and on Ubuntu 11.10. None of them told me this is bad, all dies
> only at runtime:
> #include <array>
> int main()
> {
> std::array<int, 100*1000*1000> a;
> return 0;
> }

That's correct, there is no requirement that this is diagnosed during
compile/link time.

- Daniel

[Nicol Bolas]

On Monday, June 3, 2013 4:05:47 AM UTC-7, Róbert Dávid wrote:

2013. június 3., hétfő 11:49:07 UTC+2 időpontban Nicol Bolas a következőt írta:

On Sunday, June 2, 2013 4:32:14 PM UTC-7, Róbert Dávid wrote:

The second one is terrible, because when a particular system will prevent stack allocation is implementation-dependent. Some systems might allow you to stack allocate a 30,000 integers; some might not. You would have to have two different code-paths for every use of dynarray: one for if it works, and one for if it doesn't.

I'm not sure it is actually that terrible how it sounds to you - it's the same thing when you want to have a std::array<int, 30000> - some systems might allow you to do that, some might not, and you will have two different code-paths..

There's a really big difference here. If it won't let me do `std::array<int, 30000>`, the compiler will tell me. I will know before my application ships. Therefore, I will not need different code-paths; I will simply change my code for the lowest-common-denominator compiler.

No it doesn't. I just tested it on MSVC11.3 and ICC 2013.3 on Windows 8 and GCC 4.6.1 and on Ubuntu 11.10. None of them told me this is bad, all dies only at runtime:

#include <array>
int main()
{
  std::array<int, 100*1000*1000> a;
  return 0;
}

 

Fair enough.
 

For me, dynarray<int> arr(n); is to int arr[n]; what array<int, 10> arr; is to int arr[10];

Well, there's your problem: that's not what dynarray is for. It's wrong to blame a class for not doing something that it's not trying to do. Rather than trying to convert a class into being what you think it ought to be, you should be asking for a class that has the particular features you want it to have.

I beg your pardon, are you saying I cannot use dynarray<int> arr(n) instead of int arr[n], unlike how I can use array<int, 10> instead of int[10]?? What is the point of dynarray then?

The point of `dynarray` is to be a runtime-fixed-size allocated array of values, which can be allocated on the stack or heap. That this might let you replace any particular use of `int arr[n]` with `dynarray<int> arr(n)` is a side issue, and any deficiencies in that regard should not necessarily count against it (unless they are unnecessary deficiencies). The main purpose of the class is to be able to have it select stack vs. heap allocation based on non-local factors.

If anything, `dynarray` is for when you can't use `int[n]`, such as in struct definitions and such. That it also happens to work when you could use it is a nice bonus, not the reason for its existence.

Moving on, the case of runtime-const-size stack-allocated container is a different beast, dynarray should not try to solve it by its own, but unique_ptr<dynarray<T>> is what one needs in this case; the same way how unique_ptr<array<T, n>> works for a compile-time-size stack allocated arrays.

No it does not. `unqiue_ptr<array<>>` does not allocate anything on the stack. `array<>` is only allocated on the stack if it is allocated on the stack, and `unique_ptr` cannot store stack-allocated objects. So if you want to create a `unique_ptr<array<>>`, you're going to have to heap allocate that `array`.

Oh my god, sorry, this is a big time mistype, I should not write these mails at 1:30 am.. I meant a heap allocated container. Heap heap heap.

OK, so std::vector. We already have that; just don't resize it. Admittedly, it would be nice to have a vector-like container that would not allow resizing. But it would just be std::vector without certain members.

[Róbert Dávid]

The main purpose of the class is to be able to have it select stack vs. heap allocation based on non-local factors.

Alright. So it is not an std::array, that has dynamic size? Why is it called dynarray then?

It feels like this class wants to do way too much - I don't have a tool that always allocates data on stack, if I wanted to take responsibility for that. (Of course the new C-style dynamic array is one - but that doesn't have begin()/end(), so cannot use stl algorithms on it, not possible for a library to check for out of range indexing, etc.) If there is a need to have a standard library tool for automatic stack vs. heap selection, then there should be a class to do this selection (what dynarray is now), wrapping / building on std::dynamic_stack_array and/or std::vector (or std::dynamic_heap_array)

Regards, Robert

[Daniel Krügler]

2013/6/3 Róbert Dávid <lrd...@gmail.com>:

>
> Alright. So it is not an std::array, that has dynamic size? Why is it called
> dynarray then?

The "dyn" standards for "dynamically allocated", not for resizable.
There was quite amount of discussion of the naming choice, but in the
end "dynarray" won.

> It feels like this class wants to do way too much - I don't have a tool that
> always allocates data on stack, if I wanted to take responsibility for that.

I'm not sure what you are trying to express here.

- Daniel

[Róbert Dávid]

2013. június 3., hétfő 16:23:11 UTC+2 időpontban Daniel Krügler a következőt írta:

2013/6/3 Róbert Dávid <lrd...@gmail.com>:
>
> Alright. So it is not an std::array, that has dynamic size? Why is it called
> dynarray then?

The "dyn" standards for "dynamically allocated", not for resizable.
There was quite amount of discussion of the naming choice, but in the
end "dynarray" won.

Noone questioned that, you are just suggesting that I should not consider std::dynarray as an std::array that has "dynamic", aka non-compile-time size.
 

> It feels like this class wants to do way too much - I don't have a tool that
> always allocates data on stack, if I wanted to take responsibility for that.

I'm not sure what you are trying to express here.

What should I use when I want a runtime-size array that is definitely stack allocated? Is there any other option than doing it C-style?

Regards, Robert

[Daniel Krügler]

2013/6/3 Róbert Dávid <lrd...@gmail.com>:

>
> 2013. június 3., hétfő 16:23:11 UTC+2 időpontban Daniel Krügler a következőt
> írta:
>>
>> 2013/6/3 Róbert Dávid <lrd...@gmail.com>:
>> >
>> > Alright. So it is not an std::array, that has dynamic size? Why is it
>> > called
>> > dynarray then?
>>
>> The "dyn" standards for "dynamically allocated", not for resizable.
>> There was quite amount of discussion of the naming choice, but in the
>> end "dynarray" won.
>
> Noone questioned that, you are just suggesting that I should not consider
> std::dynarray as an std::array that has "dynamic", aka non-compile-time
> size.

I'm not suggesting anything, I was just trying to respond to your question.

>> > It feels like this class wants to do way too much - I don't have a tool
>> > that
>> > always allocates data on stack, if I wanted to take responsibility for
>> > that.
>>
>> I'm not sure what you are trying to express here.
>
> What should I use when I want a runtime-size array that is definitely stack
> allocated? Is there any other option than doing it C-style?

You should be aware, that there is no guarantee that a array with
runtime-bound will allocate from the stack (8.3.4 p4):

"If the size of the array exceeds the size of the memory available for
objects with automatic storage duration,
the behavior is undefined. It is unspecified whether a global
allocation function (3.7.4) is invoked to
obtain storage for the array."

Of-course, implementations usually *will* allocate from the stack. The
same idea exists for std::dynarray except that it guarantees to allow
you to create also objects of this type with storage durations
different from automatic ones (in which case stack allocation won't be
possible). Still, it will be q.o.i whether an implementation allocates
memory from the stack for either runtime-bound arrays or std::dynarray
objects.

- Daniel

[Róbert Dávid]

You should be aware, that there is no guarantee that a array with
runtime-bound will allocate from the stack (8.3.4 p4):

"If the size of the array exceeds the size of the memory available for
objects with automatic storage duration,
the behavior is undefined. It is unspecified whether a global
allocation function (3.7.4) is invoked to
obtain storage for the array."

That says, allocate from the stack (rather, 'automatic storage', as there is no concept of stack in the standard), or UD. There is nothing about possibility of allocating on heap instead (ok, technically UD covers it, but it is also allows it to launch nuclear missiles). It does guarantee to allocate on stack when there is enough memory.

Regards, Robert

[Daniel Krügler]

2013/6/4 Róbert Dávid <lrd...@gmail.com>:

It doesn't, please read the wording a second time. The wording just
says that it is unspecified whether a global allocation function will
be used, which grants an implementation the freedom to use operator
new to get the memory for the runtime array. In particular the
wording does *not* say, which conditions are the right ones to call
operator new. It could be each time.

- Daniel

[Nicol Bolas]

No it doesn't. It specifically allows for the possibility of using "a global allocation function" regardless of the size of the allocation. Yes, that is "unspecified" (meaning that it is allowed), but it doesn't require exceeding a memory threshold to invoke it. It doesn't say "if you exceed the memory limits, a global allocation function can be used." It simply says "a global allocation function can be used."

So stack allocation is certainly not guaranteed, regardless of whether there is enough memory or not.

[DeadMG]

What I'm curious about is the performance case. The entire justification for all of this is based on the performance benefits of stack allocation, but I'm curious as to how rigorously these benefits were checked and what evidence was submitted to show that the performance of stack allocation was so desirable.

[Nicol Bolas]

On Tuesday, June 4, 2013 9:36:54 AM UTC-7, DeadMG wrote:

What I'm curious about is the performance case. The entire justification for all of this is based on the performance benefits of stack allocation, but I'm curious as to how rigorously these benefits were checked and what evidence was submitted to show that the performance of stack allocation was so desirable.

Since the cost of stack allocation is essentially just the cost of moving the stack pointer, it's pretty hard for heap allocation to beat that. How much that cost actually matters depends on a great many factors. But really, just put a five-element std::vector<int> in a tight loop that does nothing but re-initialize the 5 elements every frame, and compare it to the performance of a std::array<int, 5>. People uses std::array for these same benefits for compile-time sizes; it's simply a matter of wanting those benefits for runtime sizes.

[DeadMG]

That's not really the same thing. The vector uses the most general-purpose heap allocator possible. You can get much, much tighter timings with a more specific allocator.

Also, I checked the implementation of alloca in Visual Studio, and it's a lot more expensive than you'd think- something about stack pointer alignment and checking and stuff. I had plenty of success getting competitive performance with a choice heap allocator- as in, within the inaccuracies of the test, they were the same speed.

[Zhihao Yuan]

On Tue, Apr 2, 2013 at 9:32 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> I do have some concerns about this though. One is purely functional and
> easily resolved: `dynarray` should have a constructor that can use
> default-initialization of its array elements instead of
> value-initialization.

Agreed. I think it's OK for dynarray and make_unique share
a `default_initialize` tag.

> But this should be true of all standard library
> containers and warrants a full proposal.

Some of the containers are node-based. std::vector has
`.reserve()`, which is even better.

> Another is the lack of allocator
> support when not using stack memory; again, relatively easily resolved.

?? dynarray has allocator-aware constructors. See:

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3662.html

and N3690.

> The main issue is this:
>
> dynarray<Type> GetArray(int size)
> {
> dynarray<Type> arr(size);

> //Fill in arr with stuff.
> return arr;
> }
>

> unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(GetArray(12));

dynarray's move is O(n), as well as std::array.

> It should be the user's choice to use `dynarray` as a fixed-size `vector`,
> with all of the move characteristics of that class.

... It's not the purpose of dynarray. But it might be useful...

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

[Lawrence Crowl]

Calling alloca is a not what the compiler should do. It should
modify the stack pointer directly.

--
Lawrence Crowl

[DeadMG]

It would have to perform essentially the same work. alloca is basically a language primitive anyway that's just named like a function.

[Lawrence Crowl]

On 6/4/13, Zhihao Yuan <lic...@gmail.com> wrote:
> On Tue, Apr 2, 2013 at 9:32 PM, Nicol Bolas <jmck...@gmail.com> wrote:
>> I do have some concerns about this though. One is purely functional and
>> easily resolved: `dynarray` should have a constructor that can use
>> default-initialization of its array elements instead of
>> value-initialization.
>
> Agreed. I think it's OK for dynarray and make_unique share
> a `default_initialize` tag.
>
>> But this should be true of all standard library
>> containers and warrants a full proposal.
>
> Some of the containers are node-based. std::vector has
> `.reserve()`, which is even better.
>
>> Another is the lack of allocator
>> support when not using stack memory; again, relatively easily resolved.
>
> ?? dynarray has allocator-aware constructors. See:
>
> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3662.html
>
> and N3690.

There was some debate over whether the allocator should apply to
the storage block (when not allocated on the stack) and the elements
or just the elements alone.

>
>> The main issue is this:
>>
>> dynarray<Type> GetArray(int size)
>> {
>> dynarray<Type> arr(size);
>> //Fill in arr with stuff.
>> return arr;
>> }
>>
>> unique_ptr<dynarray<Type>> arrPtr = new dynarray<Type>(GetArray(12));
>
> dynarray's move is O(n), as well as std::array.
>
>> It should be the user's choice to use `dynarray` as a fixed-size
>> `vector`,
>> with all of the move characteristics of that class.
>
> ... It's not the purpose of dynarray. But it might be useful...
>
> --
> Zhihao Yuan, ID lichray
> The best way to predict the future is to invent it.
> ___________________________________________________
> 4BSD -- http://4bsd.biz/
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
>
>
>


--
Lawrence Crowl

[Lawrence Crowl]

On 6/4/13, DeadMG <wolfei...@gmail.com> wrote:

> It would have to perform essentially the same work. alloca is basically a
> language primitive anyway that's just named like a function.

The compiler knows more, and can avoid checks and return-pointer
futzing that might happen in alloca. Of course, one can inline and then
the analysis gets murky.

--
Lawrence Crowl

[DeadMG]

How could alloca possibly operate if it wasn't inlined? The stack pointer would simply be adjusted right back when the function returns.

But in a more general case, what I'm saying is, a comparison to alloca is pretty much all we've got since there is no implementation for dynarray right now. And it's not very compelling to hear that it should be faster than a naive std::vector, because that's not what dynarray is competing against. It's competing against a bunch of specialized allocators which offer very similar allocation semantics and speed to alloca, but don't have most or all of the horrible pitfalls.

For a feature whose inclusion brings a bunch of pitfalls by it's very nature, and whose inclusion is justified exclusively by performance, I find it extremely odd that (as far as I can tell) there are no benchmarks, no discussion of real implementations, no comparison to alternatives (actual alternatives, not global operator new, but a specialized allocator), no anything. I got ripped for this stuff with N3575 and rightly so. I read the paper and was present in Bristol for that meeting.

[Chris Jefferson]

On 05/06/13 03:38, DeadMG wrote:
> How could alloca possibly operate if it wasn't inlined? The stack
> pointer would simply be adjusted right back when the function returns.
>
> But in a more general case, what I'm saying is, a comparison to alloca
> is pretty much all we've got since there is no implementation for
> dynarray right now. And it's not very compelling to hear that it
> should be faster than a naive std::vector, because that's not what
> dynarray is competing against. It's competing against a bunch of
> specialized allocators which offer very similar allocation semantics
> and speed to alloca, but don't have most or all of the horrible pitfalls

Competing against std::vector is exactly what I feel dynarray should be
competing against. I can certainly produce code, if you want it, where
variable-sized arrays in gcc massively outperform std::vector.

Where are these 'bunch of specialized allocators'? Making a comparision
against some nebulus "super-optimised code" is not useful. Comparing
against specialized allocators is not a fair comparision in my opinion,
unless you also intend to bring those up for standardisation.

Chris

[DeadMG]

Er, I did submit N3575. It's a billion miles away from ready, but I certainly do intend to bring them up for Standardisation. Also, just because the other options are not yet Standard does not mean that he should not compare them, since they certainly could be included instead of dynarray to improve memory allocation performance. Also, why not just run the alloca code in release mode and the vector in debug mode whilst you're at it? You can't compare "Code I optimized using Technique X" and "Unoptimized code" to find that X is worth including over Technique Y.

What I'm saying is that if you have a feature whose inclusion is improved performance, then you should have proof on hand that it does improve performance against realistic competitors.

[Chris Jefferson]

I assuming this is a reply to my message.

std::vector is the standard way which I, and I think everyone else(?)
has suggested users get a block of runtime-variable size memory since
C++ began. Suggesting std::vector is equivalent to "unoptimized code" is
extremely disturbing, does this mean one of the most fundamental classes
in the standard library is not fit for purpose?

Could you please suggest an allocator which I could use as a replacement
for my use of alloca? I am happy to try such a thing, and report back on
the performance I achieve.

Chris

[DeadMG]

It is the least optimized code, not because std::vector is slow or poorly implemented, but because it solves a different problem. std::vector solves the problem of "Allocate some memory, some time, with some size, then deallocate at some time in the future". Alloca solves the problem of "Allocate some small memory, but deallocate at a very fixed time in the future, with a fixed ordering w.r.t. other allocations from this source.". It is much akin to suggesting that arbitrary-precision integers are unoptimized for operations whose values are fixed at needing less than 64bits- the more constrained version will easily cope and is much faster. That's not to say that arbitrary-precision integers are poorly optimized, but that you're using them in the wrong circumstances.

As for an allocator to replace alloca, I don't have the code to hand (will look in a sec) but have a look at memory region/memory arena allocators. They have similar constraints to alloca and operate on much the same principle as the stack, but the memory comes from the heap. Strangely enough, it turns out that the cost of "Just subtract from the stack pointer" is pretty much the same as "Just subtract from the heap pointer". Of course, there are a few niggles each way, and I'm not going to argue that an arena is a replacement for dynamic stack allocation in every single case, ever. But what I am saying is that it should be considered, rather than assumed.

[Lawrence Crowl]

On 6/4/13, DeadMG <wolfei...@gmail.com> wrote:

> How could alloca possibly operate if it wasn't inlined? The stack
> pointer would simply be adjusted right back when the function
> returns.

The saved stack pointer is on the stack, so you simply write a
little assembly that edits the saved value. It does require a
suitably friendly calling convention.

> But in a more general case, what I'm saying is, a comparison
> to alloca is pretty much all we've got since there is no
> implementation for dynarray right now. And it's not very compelling
> to hear that it should be faster than a naive std::vector,
> because that's not what dynarray is competing against. It's
> competing against a bunch of specialized allocators which offer
> very similar allocation semantics and speed to alloca, but don't
> have most or all of the horrible pitfalls.

The problem is that to get the speed, you'd need an allocator with
LIFO properties. But since vectors can be resized, it won't work
with those in general, only in specific use cases.

> For a feature whose inclusion brings a bunch of pitfalls by it's
> very nature, and whose inclusion is justified exclusively by
> performance,

Not exclusively by performance. It also places an invariant on
the size of the array. This invariant can be exploited to avoid
worrying that a subroutine changes the size of a vector. Indeed,
I have code that uses dynarray for that purpose.

> I find it extremely odd that (as far as I can tell) there are no
> benchmarks, no discussion of real implementations, no comparison
> to alternatives (actual alternatives, not global operator new,
> but a specialized allocator), no anything. I got ripped for this
> stuff with N3575 and rightly so. I read the paper and was present
> in Bristol for that meeting.

I think that is partly for two reasons. First, the technology that
goes into implementing dynarray is old. It is a rather unsuprising
compiler optimization. Second, it is a compiler optimization,
and that means there is a much higher bar in doing the testing than
with library changes.

--
Lawrence Crowl

[Lawrence Crowl]

It is probably fairly safe to say that most code will not use an
explicit allocator. For that code, the performance issue remains.
If we can do something simple, we should.

Going further, using a dynarray in source gives you more confidence
in the applicability of special allocators than does vector precisely
because its size will not change.

--
Lawrence Crowl

[Olaf van der Spek]

Op zaterdag 8 juni 2013 00:52:23 UTC+2 schreef Lawrence Crowl het volgende:

> For a feature whose inclusion brings a bunch of pitfalls by it's
> very nature, and whose inclusion is justified exclusively by
> performance,

Not exclusively by performance.  It also places an invariant on
the size of the array.  This invariant can be exploited to avoid
worrying that a subroutine changes the size of a vector.  Indeed,
I have code that uses dynarray for that purpose.

Wouldn't (mutable) array ref / (iterator) range be a better type for such an argument?

 

[DeadMG]

The problem is that to get the speed, you'd need an allocator with 
LIFO properties.  But since vectors can be resized, it won't work 
with those in general, only in specific use cases. 

There's nothing more general about "You can't resize your dynamically-sized container because I allocated off the LIFO allocator which is the stack" compared to "You can't resize your dynamically-sized container because I allocated off the LIFO allocator which is on the heap". Resizing a vector would work, it just wouldn't work as well as not resizing it, but that's nothing new. In fact, for some of the smaller sizes, the arena can probably still beat new. One of the many, many ways in which "LIFO heap" is a lot more flexible and general than alloca. Not to mention that, as Olaf says, non-resizability is a different issue really- and we already have tools or proposals that could be used for this, like array_ref.

I think that is partly for two reasons.  First, the technology that 
goes into implementing dynarray is old.  It is a rather unsuprising 
compiler optimization.  Second, it is a compiler optimization, 
and that means there is a much higher bar in doing the testing than 
with library changes. 

If it's readily done, then why are there no sample implementations, like a Clang fork, for example? You can't say that dynarray's performance is incomparable to alloca, and then say you can't implement dynarray (even though it's supposedly non-problematic to implement), and that the performance is obviously justified.

Just for reference, I checked alloca for VS2012 again, and it is maybe 15-20 instructions or so. Some stuff I don't understand about control registers. Not just sub esp.

[Lawrence Crowl]

On 6/7/13, Olaf van der Spek <olafv...@gmail.com> wrote:
> Op 8 juni 2013 schreef Lawrence Crowl het volgende:

In this case, no, because I'm allocating an array to match the size
of an existing array. Those arrays need to have the same size for
the duration of the pairing.

It seems to me that an array_ref is still vulnerable to an underlying
vector changing size.

--
Lawrence Crowl

[Lawrence Crowl]

On 6/8/13, DeadMG <wolfei...@gmail.com> wrote:
> > The problem is that to get the speed, you'd need an allocator with
> > LIFO properties. But since vectors can be resized, it won't work
> > with those in general, only in specific use cases.
>
> There's nothing more general about "You can't resize your
> dynamically-sized container because I allocated off the LIFO
> allocator which is the stack" compared to "You can't resize your
> dynamically-sized container because I allocated off the LIFO
> allocator which is on the heap".

True, but the issue isn't the implementation, but the distinction
between "if you call the resize function unexpectedly the code
breaks" and "there is no resize function to call so you cannot make
that mistake".

I am not arguing that one cannot write correct code with vector
an a LIFO allocator, just that a restriction in the type makes the
intent clearer and correct code more likely.

> Resizing a vector would work, it just wouldn't work as well as
> not resizing it, but that's nothing new. In fact, for some of
> the smaller sizes, the arena can probably still beat new. One of
> the many, many ways in which "LIFO heap" is a lot more flexible
> and general than alloca. Not to mention that, as Olaf says,

> non-resizability is a different issue really - and we already have

> tools or proposals that could be used for this, like array_ref.

I do not see how taking a reference to a vector prevents the vector
from changing size.

> > I think that is partly for two reasons. First, the technology
> > that goes into implementing dynarray is old. It is a rather
> > unsuprising compiler optimization. Second, it is a compiler
> > optimization, and that means there is a much higher bar in
> > doing the testing than with library changes.
>
> If it's readily done, then why are there no sample implementations,
> like a Clang fork, for example? You can't say that dynarray's
> performance is incomparable to alloca, and then say you can't
> implement dynarray (even though it's supposedly non-problematic
> to implement), and that the performance is obviously justified.

Sun's compiler had a somewhat similar feature ten years ago.
Isn't that sufficient evidence of implementability? No one has
argued that the implementation is difficult.

> Just for reference, I checked alloca for VS2012 again, and it
> is maybe 15-20 instructions or so. Some stuff I don't understand
> about control registers. Not just sub esp.

I am not familiar with that plaform, but on other platforms
allocating from the stack can be as little as one instruction.
Typically, though, you will have a few more to compute the size,
which is common to all allocation mechanisms.

--
Lawrence Crowl

[Mikhail Semenov]

I am just wondering, why cannot the compiler decide for simple cases of std::vector, how to allocate it. Surely if a vector is allocated at the beginning of the block, not changed and not passed anywhere, it can be allocated on the stack and destroyed on exit from the block. Then we would not need another data structure. Or is it to much to ask of the compile: "You are free to use the best allocator you can. I don't care" ? 

[Mikhail Semenov]

First-allocation preference can be used for vectors (proper notation can be sorted out later):

std::vector<double> a(std::on_stack, 100);

std::vector<double> b(std::on_heap, 10000);

 

The user can explicitly state which type of allocation is preferred. If later the vector is re-allocated, the heap can be used. In this case, we don't impose any restrictions on the structure we are dealing with. But behind the scenes, if we want move an on-stack vector, copy will be used (at least in most  cases).

 

 

 

 

[Ville Voutilainen]

Why wouldn't I do that with a polymorphic allocator instead of adding yet another constructor signature to vector?

[Mikhail Semenov]

>Why wouldn't I do that with a polymorphic allocator instead of adding yet another constructor signature to vector?

I had mentioned that the exact notation could be sorted out later. If polymorphic allocators could solve the problem easily let them do it. The exact mechanism or syntax is not the point.

[Nevin Liber]

-1.

Take the following case:

vector<int> VectorFactory()
{
    vector<int> vi(std::on_stack, 100);
    return vi;
}

struct S
{
    vector<int> vi;
    S() : vi(VectorFactory()) {}
};

unique_ptr<S> SFactory()
{
    return unique_ptr<S>(new S);
}

Now I have a heap object referring to possibly released stack space.  Ugh.

Remember, this is for the standard, not your own personal code base.  Copy, move and RVO better work correctly and as expected, and shouldn't require developers to "be careful" when using the class.

The lifetime of stack space (the duration of your stack frame) is fundamentally different than the lifetime of heap space (the duration of your program).  Combining the two is tricky.  dynarray gets this correct with no programmer intervention.  Your solution does not.
--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Mikhail Semenov]

>vector<int> VectorFactory()
>{
>    vector<int> vi(std::on_stack, 100);
>    return vi;
>}

My point was that when this happens the vi is copied into the heap: no move should be performed here!

(In older days, it was just a copy into a new place; in C++11, it is a move;

but if we allow stack-heap allocation, when we do copy from stack to heap, not move).

The point is: we should not allow on-stack vectors to move.

 

 

[Ville Voutilainen]

If that's the point, we have gone seriously astray. If you want to achieve efficient allocation,

use a pool allocator for which the pool lives longer than the allocator, and don't do things
that destroy the pool and let the allocator using such pools escape the scope of the pool.

[Nevin Liber]

1.  Are you seriously suggesting removing vector's move constructor?
2.  Even if move was disabled, this is still broken, because you don't know if RVO will be used or not.

I don't see any way to shoehorn this into vector, without significantly complicating both its implementation and its use.

[Mikhail Semenov]

 

>1.  Are you seriously suggesting removing vector's move constructor?
>2.  Even if move was disabled, this is still broken, because you don't know if RVO will be used or not.

>I don't see any way to shoehorn this into vector, without significantly complicating both its implementation and its use.

 

I am not suggesting to remove anything. I am suggesting to add an internal flag (on_stack) that is set to true when the allocation is on the stack,

and false otherwise.  The move constructor will look like this (I have attached the full example of a simple class vect -- vector of double):

 

    vect(vect&& x)
    {
        if (x.on_stack)
        {
            v = new double[x.length];
            on_stack = false;
            length = x.length;
            memcpy(v,x.v, sizeof(double)*x.length);// only for demostration
            x.release(); // from stack       
        }
        else
        {
            v = x.v;
            length = x.length;
            x.v = nullptr;
            x.length = 0;
            on_stack = false;
        }
    }

 

The compiled program works both in Visual C++ 2012 and GCC 4.7.2, 4.8.0. It's interesting GCC already optimises the code.

 

Imagine a situation with dynamic arrays: they cannot be easily copied. You start using them then you realise you have to extend, you have to change to vectors. With vectors you can change the constructor,

leaving the other code intact.

 

 

 

[Nevin Liber]

On 11 June 2013 13:56, Mikhail Semenov <mikhailse...@gmail.com> wrote:

 

>1.  Are you seriously suggesting removing vector's move constructor?
>2.  Even if move was disabled, this is still broken, because you don't know if RVO will be used or not.

>I don't see any way to shoehorn this into vector, without significantly complicating both its implementation and its use.

 

I am not suggesting to remove anything. I am suggesting to add an internal flag (on_stack) that is set to true when the allocation is on the stack,

and false otherwise. 

As I wrote in (2) above, I don't see how that works correctly when RVO is involved, since no copy or move is actually executed.  Could you elaborate?

If you want to write your own fragile allocator and fragile containers which does this for your users, go right ahead.  But I am strongly against this kind of change to either the standard allocator or standard containers.

Imagine a situation with dynamic arrays: they cannot be easily copied.

dynarray can be very easily copied.

[Mikhail Semenov]

>2.  Even if move was disabled, this is still broken, because you don't know if RVO will be used or not.

The return value optimisation will work, if you follow standard rules of defining move or copy. I don't see the point in mixing various array containers.

Below is a quote from the standard when RVO performs.

 

"When certain criteria are met, an implementation is allowed to omit the copy/move construction of a class
object, even if the constructor selected for the copy/move operation and/or the destructor for the object
have side effects. In such cases, the implementation treats the source and target of the omitted copy/move
operation as simply two different ways of referring to the same object, and the destruction of that object
occurs at the later of the times when the two objects would have been destroyed without the optimization."

 

In other words,  either destruction happens at a later time for object (the time should be the same for both objects), or RVO will not be performed.

How can an object be destroyed later, if it is on the stack? Another issue is that the standard allows different allocators anyway, they should work.

[Nevin Liber]

On 11 June 2013 15:00, Mikhail Semenov <mikhailse...@gmail.com> wrote:

>2.  Even if move was disabled, this is still broken, because you don't know if RVO will be used or not.

The return value optimisation will work,

And give you a dangling reference to stack memory, which is just not possible with the C++11 standard containers using the standard allocator.  Look at my example again.

 

How can an object be destroyed later, if it is on the stack?

You tell us; it's your suggestion that we allow the standard containers with the standard allocator to be that fragile.

Another issue is that the standard allows different allocators anyway, they should work.

They do work because if the user has a custom allocator, it is their job to ensure that the lifetime of the storage is at least as long as the lifetime of all containers which use that storage.  That would be a change (and a horrible one IMO) to put that burden on all users of standard containers using the standard allocator.

[Mikhail Semenov]

>And give you a dangling reference to stack memory, which is just not possible with the C++11 standard containers using the standard >allocator.  Look at my example again.

 

No dangling reference: the stack will be cleared.

>They do work because if the user has a custom allocator, it is their job to ensure that the lifetime of the storage is at least as long as the >lifetime of all containers which use that storage.  That would be a change (and a horrible one IMO) to put that burden on all users of >standard containers using the standard allocator.

 

To be honest, I lost you point here. You mean that if different allocators are used, memory handling will be inefficient. I thick we are talking about the optimisation issues here. Don't optimise then!. There is enough efficiency in using move. If it is difficult for the compiler to do the optimisation then don't do it. Your unique pointer is using move: what's the problem.

 

Look at my move code: if it's originally allocated on the stack: you copy; by what is on the stack you destroy (and assign nullptr to the pointer). If it is allocated on the heap you move. What is the problem? The compiler is only allowed to do what is legal. There is no problem in designing your own containers.

 

 

[Mikhail Semenov]

>Look at my example again.

 

For your information, I put your example into the sample code that I attached before.

It does not have any leaks (all the allocated memory is correctly destroyed). But it behaves slightly differently in VC++ depending on the optimization level. Again it does nothing wrong with the code.

 

Since I am not really using stack, but LIFO allocation, in the optimized code it uses this LIFO memory,

ignoring the heap. The same happens in GCC. But this is another issue. If such optimisation is not

a good idea, I thick the standard can be changed to enforce the rules.

 

 

 

 

 

[Nevin Liber]

On 11 June 2013 16:20, Mikhail Semenov <mikhailse...@gmail.com> wrote:

>They do work because if the user has a custom allocator, it is their job to ensure that the lifetime of the storage is at least as long as the >lifetime of all containers which use that storage.  That would be a change (and a horrible one IMO) to put that burden on all users of >standard containers using the standard allocator.

 

To be honest, I lost you point here. You mean that if different allocators are used, memory handling will be inefficient.

No. I mean if different allocators are used, the copy/move constructors/assignment may lead to nasty runtime bugs if you are not handling the lifetime of the storage correctly.  This cannot happen when containers use the standard allocator.

 

I thick we are talking about the optimisation issues here.

We are talking about correctness with respect to legal C++ optimizations.

 

Don't optimise then!.

Huh?  Even if I would want to (and I most certainly don't), compilers are not required to give me options to turn off copy/move elision.

 

 Look at my move code: if it's originally allocated on the stack: you copy; by what is on the stack you destroy (and assign nullptr to the pointer). If it is allocated on the heap you move. What is the problem?

Your move constructor *will not be executed* if the move is elided.

 

The compiler is only allowed to do what is legal.

It is doing something legal. 

-- 

[Lawrence Crowl]

On 6/9/13, Mikhail Semenov <mikhailse...@gmail.com> wrote:
> I am just wondering, why cannot the compiler decide for simple
> cases of std::vector, how to allocate it. Surely if a vector is
> allocated at the beginning of the block, not changed and not passed
> anywhere, it can be allocated on the stack and destroyed on exit
> from the block. Then we would not need another data structure. Or
> is it to much to ask of the compile: "You are free to use the
> best allocator you can. I don't care" ?

The compiler is always free to apply the as-if rule. The problem
is that compiler writers need some evidence that they will find
enough gain to do the analysis to find that the rule applies. The
harder the analysis, the more gain one needs to match it.

--
Lawrence Crowl

[Mikhail Semenov]

Lawrence,

My basic concern about dynamic arrays is that if I define some functions, like that:
std::vector<double> f(const std::vector<double>& a, const std::vector<double>& b);

(and there will be lot's of them in the program),
I won't be able to apply them to similar dynamic arrays: they are different types.

On the other hand,  if I use vectors only, I will be able to apply them.

The solution will be either to avoid dynamic arrays or write templates.

As I've shown in my (quickly patched up) example, there is no problem to allow vectors to provide two kinds of allocation: on the stack or on the heap. Once you start moving/coping/extending, the on-stack data changes to the on-heap one. I used my own stack in the example, but I think using a program stack won't be a problem.

I compiled my example using three different compilers (and in different modes): there was no problem.  I understand it's only a small test, but I think the concept is correct.

Mikhail.

[Martinho Fernandes]

On Wed, Jun 12, 2013 at 10:18 AM, Mikhail Semenov <mikhailse...@gmail.com> wrote:

Lawrence,

My basic concern about dynamic arrays is that if I define some functions, like that:
std::vector<double> f(const std::vector<double>& a, const std::vector<double>& b);

(and there will be lot's of them in the program),
I won't be able to apply them to similar dynamic arrays: they are different types.

On the other hand,  if I use vectors only, I will be able to apply them.

The solution will be either to avoid dynamic arrays or write templates.

Unsurprisingly, if you want generic code, you need to use the generic code facilities.

As I've shown in my (quickly patched up) example, there is no problem to allow vectors to provide two kinds of allocation: on the stack or on the heap. Once you start moving/coping/extending, the on-stack data changes to the on-heap one. I used my own stack in the example, but I think using a program stack won't be a problem.

Judging from the response such example generated, I would think it failed to show any of what you claim it did.

I compiled my example using three different compilers (and in different modes): there was no problem.  I understand it's only a small test, but I think the concept is correct.

Your test is not testing what it should. It tests that you can write to some place in memory and read the same values from it immediately afterwards. That's meaningless. As C++ programmers we all know about undefined behaviour.

Your test is also more complex than it needs to be. Just make the member variables of the vect class public and test this instead:

vect VectorFactory()
{
    vect vi(true, 100);
    return vi;
}

int main()
{
    vect v = VectorFactory();
    std::cout << std::boolalpha << v.on_stack << std::endl;
}

I get a "true" output with both clang and GCC.

Martinho

[Martinho Fernandes]

On Wed, Jun 12, 2013 at 10:34 AM, Martinho Fernandes <martinho....@gmail.com> wrote:

I get a "true" output with both clang and GCC.

I want to make this clear.

A "true" output means the copy or move constructors that were supposed be saving the day were not called, as some other people mentioned in this conversation. Had this been the actual call stack and not a fake one, v would now be holding memory in a dead stack frame below the current one.

Martinho

[Olaf van der Spek]

On Wed, Jun 12, 2013 at 10:18 AM, Mikhail Semenov
<mikhailse...@gmail.com> wrote:

>> Lawrence,
>>
>> My basic concern about dynamic arrays is that if I define some functions,
>> like that:
>> std::vector<double> f(const std::vector<double>& a, const
>> std::vector<double>& b);
>>
>> (and there will be lot's of them in the program),
>> I won't be able to apply them to similar dynamic arrays: they are
>> different types.
>>
>> On the other hand, if I use vectors only, I will be able to apply them.
>>
>> The solution will be either to avoid dynamic arrays or write templates.

No, the solution is to use range<double*> or array_ref<double>
const vector& (and most of the time) const string& are unnecessarily
restrictive.