www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - this(this) must be cheap and O(1)

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
We've had a long-standing question on whether D should cater to 
arbitrarily costly copy constructor. C++ and its standard library do 
allow such, at a great cost in complexity of the standard library and 
user code.

Taking a stand on this issue in D has long haunted Walter and myself. I 
think I have reached the point where I can argue convincingly that D 
should go for the following design:

1. You may not define this(this), and the object will be copied memberwise.

2. You may  disable this(this), and the object will not be copyable. The 
language must define under what circumstances such objects are usable. 
The library must define how it interacts with such objects.

3. You may define this(this), in which case the standard library is free 
to assume it is cheap, constant-complexity, and non-failing.

This means that objects with large state would need to use things like 
COW and/or reference counting.

The main argument for this design is that expensive constructors are a 
hidden, unescapable, and cross-cutting cost. Essentially every 
expensive-to-copy type C++ ever defines comes with the caveat that you 
should AVOID copying it. This leads to the simple notion that at best 
you should avoid defining expensive-to-copy types in the first place. 
(As I read in a book: only the man on the street and the great general 
can think of obviously good strategies.)

(Anecdote - I was working on slides for a C++ course for people coming 
from other languages. One slide pointed out that reasonably-written C++ 
code maps straightforwardly to fast code, with ONE exception - the 
hidden cost of copy constructors and destructors. It would be progress 
to eliminate that exception.)

I'd go as far as requiring this(this) to be nothrow, but perhaps it 
would be best to see whether that is a necessity.

Anyhow, this is what I think "sendero luminoso" is for D: a world in 
which objects are free to prevent copying altogether (an important 
category of designs) or define liability-free, unlimited copying 
(another important category of designs). Types that allow copying but do 
an arbitrary amount of work are a design D is willing to shun, in wake 
of C++'s poor experience with such. No type should have hidden copying 
costs that influence complexity and performance of complex operations.


Destroy.

Andrei
Sep 24 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, September 24, 2011 02:29:52 Andrei Alexandrescu wrote:

 We've had a long-standing question on whether D should cater to
 arbitrarily costly copy constructor. C++ and its standard library do
 allow such, at a great cost in complexity of the standard library and
 user code.
 
 Taking a stand on this issue in D has long haunted Walter and myself. I
 think I have reached the point where I can argue convincingly that D
 should go for the following design:
 
 1. You may not define this(this), and the object will be copied memberwise.
 
 2. You may  disable this(this), and the object will not be copyable. The
 language must define under what circumstances such objects are usable.
 The library must define how it interacts with such objects.
 
 3. You may define this(this), in which case the standard library is free
 to assume it is cheap, constant-complexity, and non-failing.
 
 This means that objects with large state would need to use things like
 COW and/or reference counting.
 
 The main argument for this design is that expensive constructors are a
 hidden, unescapable, and cross-cutting cost. Essentially every
 expensive-to-copy type C++ ever defines comes with the caveat that you
 should AVOID copying it. This leads to the simple notion that at best
 you should avoid defining expensive-to-copy types in the first place.
 (As I read in a book: only the man on the street and the great general
 can think of obviously good strategies.)
 
 (Anecdote - I was working on slides for a C++ course for people coming
 from other languages. One slide pointed out that reasonably-written C++
 code maps straightforwardly to fast code, with ONE exception - the
 hidden cost of copy constructors and destructors. It would be progress
 to eliminate that exception.)
 
 I'd go as far as requiring this(this) to be nothrow, but perhaps it
 would be best to see whether that is a necessity.
 
 Anyhow, this is what I think "sendero luminoso" is for D: a world in
 which objects are free to prevent copying altogether (an important
 category of designs) or define liability-free, unlimited copying
 (another important category of designs). Types that allow copying but do
 an arbitrary amount of work are a design D is willing to shun, in wake
 of C++'s poor experience with such. No type should have hidden copying
 costs that influence complexity and performance of complex operations.


I'd say that I have to agree, though I think that we'll definitely need to look 
into whether this(this) should be able to legimately throw or not. It seems 
like it could easily be the case that we could reasonably require that it be 
nothrow, and it seems that it could easily be the case that that's too 
restrictive. pure is in the same boat, I think. And if we can require those, 
it makes me wonder if we could require  safe as well. But I fear that there's 
going to be some reason why some or all of those are unreasonable to require.

By the way, does this mean that we'll be able to get rid of moveFront and its 
compatriots? - since if I understand correctly, the only reason that the 
moveXXX functions exist for ranges is to deal with the case where copying 
isn't cheap.

- Jonathan M Davis
Sep 24 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 2:40 AM, Jonathan M Davis wrote:

 By the way, does this mean that we'll be able to get rid of moveFront and its
 compatriots? - since if I understand correctly, the only reason that the
 moveXXX functions exist for ranges is to deal with the case where copying
 isn't cheap.


Depends on whether we want to support ranges of uncopyable objects.

Andrei
Sep 24 2011
prev sibling next sibling parent reply Trass3r <un known.com> writes:
 This means that objects with large state would need to use things like 
 COW and/or reference counting.


Isn't an expensive-to-copy type supposed to be a class anyway?


 I'd go as far as requiring this(this) to be nothrow, but perhaps it 
 would be best to see whether that is a necessity.


Don't memory allocations prevent a function from being nothrow?
Then this would make it impossible to properly wrap an array in a struct.
Sep 24 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, September 24, 2011 07:30:56 Trass3r wrote:

 This means that objects with large state would need to use things like
 COW and/or reference counting.


 
 Isn't an expensive-to-copy type supposed to be a class anyway?


That would be one of the arguments for insisting that struct copying be cheap. 
But in C++ (where there is no significant difference between classes and 
structs), you can put a class on the stack and it is _not_ necessarily cheap 
to copy. Andrei is suggesting that we _not_ follow that, but rather that we 
assume that structs can be copied in O(1), which means that user-defined types 
which would be expensive to copy either need to use stuff like reference 
counting and COW, or they need to be classes. But unless we make such an 
assumption/requirement, then there isn't necessarily an expectation that 
expensive-to-copy types would be classes.


 I'd go as far as requiring this(this) to be nothrow, but perhaps it
 would be best to see whether that is a necessity.


 
 Don't memory allocations prevent a function from being nothrow?
 Then this would make it impossible to properly wrap an array in a struct.


nothrow guarantees that no Throwables derived from Exception are thrown from a 
function. OutOfMemoryError is an Error, and Error is _not_ derived from 
Exception. Errors are expected to be non-recoverable and aren't really meant 
to be caught.

So, nothrow has _no_ effect on memory allocations. If it did, nothrow would be 
pretty useless.

- Jonathan M Davis
Sep 24 2011
parent Trass3r <un known.com> writes:
 nothrow guarantees that no Throwables derived from Exception are thrown from a 
 function. OutOfMemoryError is an Error, and Error is _not_ derived from 
 Exception. Errors are expected to be non-recoverable and aren't really meant 
 to be caught.
 
 So, nothrow has _no_ effect on memory allocations. If it did, nothrow would be 
 pretty useless.


Thx for the explanation.
Sep 24 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 6:30 AM, Trass3r wrote:

 This means that objects with large state would need to use things like
 COW and/or reference counting.


 Isn't an expensive-to-copy type supposed to be a class anyway?


Well not always - see BigInt.


 I'd go as far as requiring this(this) to be nothrow, but perhaps it
 would be best to see whether that is a necessity.


 Don't memory allocations prevent a function from being nothrow?


A nothrow function may allocate memory, but allocating inside this(this) 
would be a faux pas.


 Then this would make it impossible to properly wrap an array in a struct.


COW would help there.


Andrei
Sep 24 2011
parent reply Trass3r <un known.com> writes:
 Isn't an expensive-to-copy type supposed to be a class anyway?


 
 Well not always - see BigInt.


True.


 A nothrow function may allocate memory, but allocating inside this(this) 
 would be a faux pas.


So I can't .dup inside this(this)?
Even the example in the docs does so:
http://www.d-programming-language.org/struct.html#StructPostblit
Sep 24 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 10:14 AM, Trass3r wrote:

 Isn't an expensive-to-copy type supposed to be a class anyway?


 Well not always - see BigInt.


 True.


 A nothrow function may allocate memory, but allocating inside this(this)
 would be a faux pas.


 So I can't .dup inside this(this)?


You can't.


 Even the example in the docs does so:
 http://www.d-programming-language.org/struct.html#StructPostblit


That needs changing.


Andrei
Sep 24 2011
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Will we be disallowed from calling extern(C) functions as well? (I
hope not since CairoD has to use the postblit to call C functions to
update an internal reference count.)
Sep 24 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 1:24 PM, Andrej Mitrovic wrote:

 Will we be disallowed from calling extern(C) functions as well? (I
 hope not since CairoD has to use the postblit to call C functions to
 update an internal reference count.)


As long as it's understood that the function has constant complexity and 
reasonable actual cost, extern(C) has no different regime.

Andrei
Sep 24 2011
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/24/2011 4:30 AM, Trass3r wrote:

 Don't memory allocations prevent a function from being nothrow?


No. The decision was made early on that out of memory are non-recoverable 
exceptions. Nothrow only pertains to recoverable exceptions.

The reasons are:

1. nothrow would be fairly useless if memory allocation could throw

2. in my experience, applications cannot realistically recover from out of 
memory. The best they can do is shut themselves down sanely
Sep 24 2011
parent "dame" <damesureurnotme yousuck.gov> writes:
Walter Bright wrote:

"would be fairly useless"

What is fair? What is fairly? What is useless? I'll bite on that and 
pose, equivalently,

Who is fair? Who is fairly? Who is useless?

(Sometimes it takes "an Andrei" to "figure it out").

What's the answer to those?
Sep 24 2011
prev sibling next sibling parent dsimcha <dsimcha yahoo.com> writes:
Vote++.  I have little experience in C++, but two things have convinced 
me that arbitrary cost copying is butt ugly and not worth the cost:

1.  The debacle of adding moveFront()/moveBack()/moveAt()/more bugs to 
std.range/std.algorithm last year.

2.  How well reference counting semantics have worked on Cristi's GSoC 
project, which I mentored.

On 9/24/2011 3:29 AM, Andrei Alexandrescu wrote:

 We've had a long-standing question on whether D should cater to
 arbitrarily costly copy constructor. C++ and its standard library do
 allow such, at a great cost in complexity of the standard library and
 user code.

 Taking a stand on this issue in D has long haunted Walter and myself. I
 think I have reached the point where I can argue convincingly that D
 should go for the following design:

 1. You may not define this(this), and the object will be copied memberwise.

 2. You may  disable this(this), and the object will not be copyable. The
 language must define under what circumstances such objects are usable.
 The library must define how it interacts with such objects.

 3. You may define this(this), in which case the standard library is free
 to assume it is cheap, constant-complexity, and non-failing.

 This means that objects with large state would need to use things like
 COW and/or reference counting.

 The main argument for this design is that expensive constructors are a
 hidden, unescapable, and cross-cutting cost. Essentially every
 expensive-to-copy type C++ ever defines comes with the caveat that you
 should AVOID copying it. This leads to the simple notion that at best
 you should avoid defining expensive-to-copy types in the first place.
 (As I read in a book: only the man on the street and the great general
 can think of obviously good strategies.)

 (Anecdote - I was working on slides for a C++ course for people coming
 from other languages. One slide pointed out that reasonably-written C++
 code maps straightforwardly to fast code, with ONE exception - the
 hidden cost of copy constructors and destructors. It would be progress
 to eliminate that exception.)

 I'd go as far as requiring this(this) to be nothrow, but perhaps it
 would be best to see whether that is a necessity.

 Anyhow, this is what I think "sendero luminoso" is for D: a world in
 which objects are free to prevent copying altogether (an important
 category of designs) or define liability-free, unlimited copying
 (another important category of designs). Types that allow copying but do
 an arbitrary amount of work are a design D is willing to shun, in wake
 of C++'s poor experience with such. No type should have hidden copying
 costs that influence complexity and performance of complex operations.


 Destroy.

 Andrei
Sep 24 2011
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-09-24 07:29:52 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 We've had a long-standing question on whether D should cater to 
 arbitrarily costly copy constructor. C++ and its standard library do 
 allow such, at a great cost in complexity of the standard library and 
 user code.
 
 Taking a stand on this issue in D has long haunted Walter and myself. I 
 think I have reached the point where I can argue convincingly that D 
 should go for the following design:
 
 1. You may not define this(this), and the object will be copied memberwise.
 
 2. You may  disable this(this), and the object will not be copyable. 
 The language must define under what circumstances such objects are 
 usable. The library must define how it interacts with such objects.
 
 3. You may define this(this), in which case the standard library is 
 free to assume it is cheap, constant-complexity, and non-failing.
 
 This means that objects with large state would need to use things like 
 COW and/or reference counting.


Seems like a perfectly reasonable policy. Go ahead.



 I'd go as far as requiring this(this) to be nothrow, but perhaps it 
 would be best to see whether that is a necessity.


Perhaps I am missing the point. What would be gained by forcing 
this(this) to be nothrow?


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Sep 24 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 9:31 PM, Michel Fortin wrote:

 Perhaps I am missing the point. What would be gained by forcing
 this(this) to be nothrow?


It further frees the standard library to cater for the throwing case.

Andrei
Sep 24 2011
next sibling parent "dame" <damesureurnotme yousuck.gov> writes:
Andrei Alexandrescu wrote:

"It further frees"
Sep 24 2011
prev sibling next sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-09-25 02:52:47 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 On 9/24/11 9:31 PM, Michel Fortin wrote:

 Perhaps I am missing the point. What would be gained by forcing
 this(this) to be nothrow?


 
 It further frees the standard library to cater for the throwing case.


Concretely, what does it simplifies?

Does it only simplifies the documentation of algorithms? … in that most 
algorithms doing copies should mention that throwing during copy may 
leave some mutated data structure in some kind of a half processed 
state. I don't think that would surprise anyone.

That said, I would certainly recommend not throwing inside this(this), 
but I don't think this recommendation should be enforced by the 
language. I think forcing it to be nothrow would encourage people to 
silently ignore exceptions with try {…} catch (…) {}. Unless you catch 
all exceptions like that, nothrow will prevent you from calling many 
functions which could be reasonable to call otherwise, such as writeln, 
or from incrementing a reference counter checking for overflow.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Sep 25 2011
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
Le 25/09/2011 04:52, Andrei Alexandrescu a écrit :

 On 9/24/11 9:31 PM, Michel Fortin wrote:

 Perhaps I am missing the point. What would be gained by forcing
 this(this) to be nothrow?


 It further frees the standard library to cater for the throwing case.

 Andrei


If I understand, what is explained in this thread is things that the 
standard lib can assume concerning this(this) ?

So, in the end, I'm not disallowed to have an expensive this(this), but 
I should expect that the standard lib will not behave optimally in this 
case ?

Or are we talking about some modification/restriction in the language ?
Sep 25 2011
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 25/09/11 7:37 PM, deadalnix wrote:

 Le 25/09/2011 04:52, Andrei Alexandrescu a écrit :

 On 9/24/11 9:31 PM, Michel Fortin wrote:

 Perhaps I am missing the point. What would be gained by forcing
 this(this) to be nothrow?


 It further frees the standard library to cater for the throwing case.

 Andrei


 If I understand, what is explained in this thread is things that the
 standard lib can assume concerning this(this) ?

 So, in the end, I'm not disallowed to have an expensive this(this), but
 I should expect that the standard lib will not behave optimally in this
 case ?

 Or are we talking about some modification/restriction in the language ?


I believe it's just the library. There's no way the language could 
reasonably enforce it anyway.

It probably just means Phobos will do more copies than C++ would for 
example.
Sep 25 2011
parent deadalnix <deadalnix gmail.com> writes:
Le 25/09/2011 21:02, Peter Alexander a écrit :

 On 25/09/11 7:37 PM, deadalnix wrote:

 Le 25/09/2011 04:52, Andrei Alexandrescu a écrit :

 On 9/24/11 9:31 PM, Michel Fortin wrote:

 Perhaps I am missing the point. What would be gained by forcing
 this(this) to be nothrow?


 It further frees the standard library to cater for the throwing case.

 Andrei


 If I understand, what is explained in this thread is things that the
 standard lib can assume concerning this(this) ?

 So, in the end, I'm not disallowed to have an expensive this(this), but
 I should expect that the standard lib will not behave optimally in this
 case ?

 Or are we talking about some modification/restriction in the language ?


 I believe it's just the library. There's no way the language could
 reasonably enforce it anyway.

 It probably just means Phobos will do more copies than C++ would for
 example.


The language could enforce that this(this) had to be nothrowor whatever. 
Or make it a warning (warning : this(this) should be a nothrow function).

For the complexity, it is hard to come up with something at the laguage 
level.
Sep 25 2011
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 24 Sep 2011 03:29:52 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 We've had a long-standing question on whether D should cater to  
 arbitrarily costly copy constructor. C++ and its standard library do  
 allow such, at a great cost in complexity of the standard library and  
 user code.

 Taking a stand on this issue in D has long haunted Walter and myself. I  
 think I have reached the point where I can argue convincingly that D  
 should go for the following design:

 1. You may not define this(this), and the object will be copied  
 memberwise.

 2. You may  disable this(this), and the object will not be copyable. The  
 language must define under what circumstances such objects are usable.  
 The library must define how it interacts with such objects.

 3. You may define this(this), in which case the standard library is free  
 to assume it is cheap, constant-complexity, and non-failing.

 This means that objects with large state would need to use things like  
 COW and/or reference counting.

 The main argument for this design is that expensive constructors are a  
 hidden, unescapable, and cross-cutting cost. Essentially every  
 expensive-to-copy type C++ ever defines comes with the caveat that you  
 should AVOID copying it. This leads to the simple notion that at best  
 you should avoid defining expensive-to-copy types in the first place.  
 (As I read in a book: only the man on the street and the great general  
 can think of obviously good strategies.)

 (Anecdote - I was working on slides for a C++ course for people coming  
 from other languages. One slide pointed out that reasonably-written C++  
 code maps straightforwardly to fast code, with ONE exception - the  
 hidden cost of copy constructors and destructors. It would be progress  
 to eliminate that exception.)

 I'd go as far as requiring this(this) to be nothrow, but perhaps it  
 would be best to see whether that is a necessity.

 Anyhow, this is what I think "sendero luminoso" is for D: a world in  
 which objects are free to prevent copying altogether (an important  
 category of designs) or define liability-free, unlimited copying  
 (another important category of designs). Types that allow copying but do  
 an arbitrary amount of work are a design D is willing to shun, in wake  
 of C++'s poor experience with such. No type should have hidden copying  
 costs that influence complexity and performance of complex operations.


 Destroy.


I'm fine with this, as long as it's not language-enforced, but just an  
expectation.  Because there are sometimes reasons to break the rules.

For example, you have said it's a faux pas to allocate memory inside a  
postblit, but what if your "allocation" routine only allocates a pool on  
the first call, and uses the pool for all the other allocations?  Or  
guarantees to allocate at most once every 1000 postblits?  It's difficult  
to make such guarantees generically, but within the context of a specific  
application, it's quite easy to prove.

I don't know if we need to enforce nothrow, but probably the easiest way  
to find a case where you *need* to throw is to enforce nothrow, and see  
what fallout we have ;)

-Steve
Sep 26 2011
parent Trass3r <un known.com> writes:
 I'm fine with this, as long as it's not language-enforced, but just an  
 expectation.  Because there are sometimes reasons to break the rules.

 For example, you have said it's a faux pas to allocate memory inside a  
 postblit, but what if your "allocation" routine only allocates a pool on  
 the first call, and uses the pool for all the other allocations?  Or  
 guarantees to allocate at most once every 1000 postblits?  It's  
 difficult to make such guarantees generically, but within the context of  
 a specific application, it's quite easy to prove.

 I don't know if we need to enforce nothrow, but probably the easiest way  
 to find a case where you *need* to throw is to enforce nothrow, and see  
 what fallout we have ;)

 -Steve


+1
Sep 26 2011