www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What functions can be called on a shared struct that's implicitly

reply =?ISO-8859-1?Q?Simen_Kj=E6r=E5s?= <simen.kjaras gmail.com> writes:
Consider:

module foo;

struct S {
     immutable(int)[] arr;
     void fuzz() const pure {
     }
}

void bar(S s) {
     s.fuzz();
}

void main() {
     shared S s;
     bar(s);   // a
     s.fuzz(); // b
}


In this case, the line marked 'a' works perfectly - it compiles and does 
what I'd expect it to.

However,the line marked 'b' does not compile - " non-shared const method 
foo.S.fuzz is not callable using a shared mutable object ".

The reason for this is that fuzz takes the 'this' pointer by reference, 
and so risks that another thread corrupt the internal state while it's 
working.

Seeing as line 'a' works, it seems safe for line 'b' to make a copy 
behind the scenes (structs in D are defined to have cheap copying, I 
seem to recall) and call fuzz on that copy - the type system claims that 
the call to fuzz cannot possibly change the state of the struct on which 
it is called.

With the state of 'shared' as it is, I'm unsure if this is a change that 
should be done - it seems perhaps better to wait for a true overhaul of 
the feature.

Where I specifically found a need for this is in attempting to fix bug 
11188[1]. While I have found a workaround, it's needed per function, and 
I'm pretty sure it'll break some specific other cases.

[1]: http://d.puremagic.com/issues/show_bug.cgi?id=11188

--
   Simen
Nov 03 2013
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Sunday, 3 November 2013 at 21:55:22 UTC, Simen Kjærås wrote:
 Consider:

 module foo;

 struct S {
     immutable(int)[] arr;
     void fuzz() const pure {
     }
 }

 void bar(S s) {
     s.fuzz();
 }

 void main() {
     shared S s;
     bar(s);   // a
     s.fuzz(); // b
 }


 In this case, the line marked 'a' works perfectly - it compiles 
 and does what I'd expect it to.

 However,the line marked 'b' does not compile - " non-shared 
 const method foo.S.fuzz is not callable using a shared mutable 
 object ".
It is because a imply a pass b value, when b a pass by reference.
Nov 03 2013
parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 04.11.2013 06:53, deadalnix wrote:
 On Sunday, 3 November 2013 at 21:55:22 UTC, Simen Kjærås wrote:
 Consider:

 module foo;

 struct S {
     immutable(int)[] arr;
     void fuzz() const pure {
     }
 }

 void bar(S s) {
     s.fuzz();
 }

 void main() {
     shared S s;
     bar(s);   // a
     s.fuzz(); // b
 }


 In this case, the line marked 'a' works perfectly - it compiles and 
 does what I'd expect it to.

 However,the line marked 'b' does not compile - " non-shared const 
 method foo.S.fuzz is not callable using a shared mutable object ".
It is because a imply a pass b value, when b a pass by reference.
Indeed. That's why I wrote that one line further down. That's not the point. The point is I have to jump through no hoops to get line a to compile - no 'assumeUnshared', no cast, no explicit copying. On that basis, I argue that line b could be made to work by silently creating a copy of s, because the call to fuzz is guaranteed not to change s. There may be problems with this that I have not considered. If you know of any, please do tell. I guess it might be conceivable that fuzz waits for a synchronization message (but is that really possible in a pure const function?), which will never happen for the copy, but is this even a case we want to support? -- Simen
Nov 04 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 4 November 2013 at 08:14:57 UTC, Simen Kjærås wrote:
 On 04.11.2013 06:53, deadalnix wrote:
 On Sunday, 3 November 2013 at 21:55:22 UTC, Simen Kjærås wrote:
 Consider:

 module foo;

 struct S {
    immutable(int)[] arr;
    void fuzz() const pure {
    }
 }

 void bar(S s) {
    s.fuzz();
 }

 void main() {
    shared S s;
    bar(s);   // a
    s.fuzz(); // b
 }


 In this case, the line marked 'a' works perfectly - it 
 compiles and does what I'd expect it to.

 However,the line marked 'b' does not compile - " non-shared 
 const method foo.S.fuzz is not callable using a shared 
 mutable object ".
It is because a imply a pass b value, when b a pass by reference.
Indeed. That's why I wrote that one line further down. That's not the point. The point is I have to jump through no hoops to get line a to compile - no 'assumeUnshared', no cast, no explicit copying. On that basis, I argue that line b could be made to work by silently creating a copy of s, because the call to fuzz is guaranteed not to change s. There may be problems with this that I have not considered. If you know of any, please do tell. I guess it might be conceivable that fuzz waits for a synchronization message (but is that really possible in a pure const function?), which will never happen for the copy, but is this even a case we want to support? -- Simen
You are trying to solve a non problem here. s is not shared in the first place, so you can start by fixing it here. Now, if S has some indirection, then it make sense to mark it as shared, but then the trick you propose won't work.
Nov 04 2013
parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 04.11.2013 09:46, deadalnix wrote:
 You are trying to solve a non problem here. s is not shared in the first
 place, so you can start by fixing it here.

 Now, if S has some indirection, then it make sense to mark it as shared,
 but then the trick you propose won't work.
I believe we're talking past each other here. Perhaps a better example: module foo; struct S { immutable(int)[] arr; void fuzz() const pure { } } void bar(S s) { s.fuzz(); } void main() { shared S* s = new shared S; bar(*s); // a s.fuzz(); // b } This example demonstrates the exact same behavior as before, and again I'm not doing a lot of anything special to get line a to compile. Now, I'm still of the opinion that the 'trick' I propose works - making a copy of s is cheap (as that's what the spec says about copying structs), s is implicitly castable to immutable, and the function to be called is guaranteed not to change s in any way. From all that, it seems safe to call fuzz on a shared S.
Nov 04 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 4 November 2013 at 09:34:52 UTC, Simen Kjærås wrote:
 On 04.11.2013 09:46, deadalnix wrote:
 You are trying to solve a non problem here. s is not shared in 
 the first
 place, so you can start by fixing it here.

 Now, if S has some indirection, then it make sense to mark it 
 as shared,
 but then the trick you propose won't work.
I believe we're talking past each other here. Perhaps a better example: module foo; struct S { immutable(int)[] arr; void fuzz() const pure { } } void bar(S s) { s.fuzz(); } void main() { shared S* s = new shared S; bar(*s); // a s.fuzz(); // b } This example demonstrates the exact same behavior as before, and again I'm not doing a lot of anything special to get line a to compile. Now, I'm still of the opinion that the 'trick' I propose works - making a copy of s is cheap (as that's what the spec says about copying structs), s is implicitly castable to immutable, and the function to be called is guaranteed not to change s in any way. From all that, it seems safe to call fuzz on a shared S.
Any read of arr in fuzz won't be sequentially consistent, so it would be incorrect to let you call fuzz on a shared object.
Nov 04 2013
parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 04.11.2013 20:52, deadalnix wrote:
 On Monday, 4 November 2013 at 09:34:52 UTC, Simen Kjærås wrote:
 On 04.11.2013 09:46, deadalnix wrote:
 You are trying to solve a non problem here. s is not shared in the first
 place, so you can start by fixing it here.

 Now, if S has some indirection, then it make sense to mark it as shared,
 but then the trick you propose won't work.
I believe we're talking past each other here. Perhaps a better example: module foo; struct S { immutable(int)[] arr; void fuzz() const pure { } } void bar(S s) { s.fuzz(); } void main() { shared S* s = new shared S; bar(*s); // a s.fuzz(); // b } This example demonstrates the exact same behavior as before, and again I'm not doing a lot of anything special to get line a to compile. Now, I'm still of the opinion that the 'trick' I propose works - making a copy of s is cheap (as that's what the spec says about copying structs), s is implicitly castable to immutable, and the function to be called is guaranteed not to change s in any way. From all that, it seems safe to call fuzz on a shared S.
Any read of arr in fuzz won't be sequentially consistent, so it would be incorrect to let you call fuzz on a shared object.
Thank you, that's what I wanted to hear. I don't agree though. Sequential consistence means reads and writes on one processor happen in the order they're written, possibly interleaved with reads and writes from other processors. I cannot see how this promise is broken by taking a copy on which you only do reads. Example (CPU 1 is running fuzz, CPU 2 is randomly mutating memory, or doing something worthwhile): | CPU 1 | CPU 2 ============================== 1 | read(arr) | write(arr) 2 | read(arr[0]) | read(arr) 3 | read(arr[1]) | write(arr[0]) Now, one sequentially consistent ordering of these operations would be: | CPU 1 | CPU 2 ============================== 1 | read(arr) | 2 | read(arr[0]) | 3 | read(arr[1]) | 4 | | write(arr) 5 | | read(arr) 6 | | write(arr[0]) Which is exactly what happens in the case of taking a copy. An equally valid ordering would of course be this: | CPU 1 | CPU 2 ============================== 1 | read(arr) | 2 | | write(arr) 3 | | read(arr) 4 | | write(arr[0]) 5 | read(arr[0]) | 6 | read(arr[1]) | In which case the results would potentially be different. However, the fact that other sequentially consistent orderings exist does not mean that the first is wrong. Can you please show an example of how copying does violate sequential consistency? -- Simen
Nov 05 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 5 November 2013 at 17:37:26 UTC, Simen Kjærås wrote:
 Thank you, that's what I wanted to hear. I don't agree though.

 Sequential consistence means reads and writes on one processor 
 happen in the order they're written, possibly interleaved with 
 reads and writes from other processors. I cannot see how this 
 promise is broken by taking a copy on which you only do reads.
No, that mean that read and write for ALL processor are done in order.
 Example (CPU 1 is running fuzz, CPU 2 is randomly mutating 
 memory, or doing something worthwhile):

   | CPU 1        | CPU 2
 ==============================
 1 | read(arr)    | write(arr)
 2 | read(arr[0]) | read(arr)
 3 | read(arr[1]) | write(arr[0])

 Now, one sequentially consistent ordering of these operations 
 would be:

   | CPU 1        | CPU 2
 ==============================
 1 | read(arr)    |
 2 | read(arr[0]) |
 3 | read(arr[1]) |
 4 |              | write(arr)
 5 |              | read(arr)
 6 |              | write(arr[0])

 Which is exactly what happens in the case of taking a copy.

 An equally valid ordering would of course be this:

   | CPU 1        | CPU 2
 ==============================
 1 | read(arr)    |
 2 |              | write(arr)
 3 |              | read(arr)
 4 |              | write(arr[0])
 5 | read(arr[0]) |
 6 | read(arr[1]) |

 In which case the results would potentially be different. 
 However, the fact that other sequentially consistent orderings 
 exist does not mean that the first is wrong.
Without sequential consistency, CPU1 can see the operation of CPU2 in the wrong order, as it won't ensure it is not working with outdated values.
Nov 05 2013
parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 05.11.2013 20:03, deadalnix wrote:
 On Tuesday, 5 November 2013 at 17:37:26 UTC, Simen Kjærås wrote:
 Thank you, that's what I wanted to hear. I don't agree though.

 Sequential consistence means reads and writes on one processor happen
 in the order they're written, possibly interleaved with reads and
 writes from other processors. I cannot see how this promise is broken
 by taking a copy on which you only do reads.
No, that mean that read and write for ALL processor are done in order.
I believe you are thinking of strict consistency[0][1], not sequential consistency[2][3]. In the former case, all reads are required to return the result of the last write to that address. In the case of sequential consistency, it is only necessary that each processor performs reads in the order they are issued, and that each processor sees the results of other processors' writes in the order in which they are issued. From Lamport's original paper[4] on the subject: "the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program." In essence, what I propose is a behavior equivalent to that the function fuzz finish (essentially) instantaneously.
 Without sequential consistency, CPU1 can see the operation of CPU2 in
 the wrong order,
Indeed. Now, as I have shown, making a copy makes sure no such thing will happen. Unless, as stated above, you mean strict consistency.
 as it won't ensure it is not working with outdated values.
Sequential consistency does not deal with absolutely outdated values, only relatively outdated ones. That is, processor A is allowed to ignore the actions of processor B until such a time that A feels like it. However, when A does, it need also take into account all other actions of processor B up until the time that processor B performed said action. I especially suggest you read reference [3], as it shows very well that two executions of the same sequentially consistent program may give different results. If you still disagree, I would love to be proven wrong. Please do include a diagram of program state changes, as descriptions can be hard to follow. (Also, I'm aware this might come off as aggressive. No offense is intended, and I *do* mean I'd love to be proven wrong, just in a way that I learn from it) [0]: http://en.wikipedia.org/wiki/Strict_consistency#Strict_consistency [1]: http://cs.gmu.edu/cne/modules/dsm/orange/strict_con.html [2]: http://en.wikipedia.org/wiki/Sequential_consistency [3]: http://www.e-reading.biz/chapter.php/143358/218/Tanenbaum_-_Distributed_operating_systems.html [4]: http://research.microsoft.com/en-us/um/people/lamport/pubs/multi.pdf -- Simen
Nov 05 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 6 November 2013 at 01:04:19 UTC, Simen Kjærås wrote:
 I believe you are thinking of strict consistency[0][1], not 
 sequential consistency[2][3].

 In the former case, all reads are required to return the result 
 of the last write to that address. In the case of sequential 
 consistency, it is only necessary that each processor performs 
 reads in the order they are issued, and that each processor 
 sees the results of other processors' writes in the order in 
 which they are issued.

 From Lamport's original paper[4] on the subject: "the result of 
 any execution is the same as if the operations of all the 
 processors were executed in some sequential order, and the 
 operations of each individual processor appear in this sequence 
 in the order specified by its program."
Yes, that is what sequential consistency is. It require both the writer and the reader to cooperate for this to happen. People often get confused by think the reader do not need to do anything special as the MOV instruction on x86 have the needed guarantee. Consider that thread a does : arr[0] = newvalue0 arr[1] = newvalue1 thread 2 could see newvalue1 but not newvalue0 is no sequential consistency is present. Note that it will happen to work on x86, because of the strong memory model of x86, but it is not something safe in the general case and something we should rely on in language specs.
 In essence, what I propose is a behavior equivalent to that the 
 function fuzz finish (essentially) instantaneously.
In this very specific case, the function does nothing, so it is safe. But we don't want to define rules that depend on the function implementation.
 Without sequential consistency, CPU1 can see the operation of 
 CPU2 in
 the wrong order,
Indeed. Now, as I have shown, making a copy makes sure no such thing will happen. Unless, as stated above, you mean strict consistency.
No making a copy is fine and the case where you pass by value (you make a copy) do indeed work as expected.
 I especially suggest you read reference [3], as it shows very 
 well that two executions of the same sequentially consistent 
 program may give different results.
I understand the difference. But as long as both require cooperation of the 2 threads, it doesn't change much to our discussion here. We also do not say that sequential consistency will magically make the program correct. Simply that sequential consistency is what D's shared qualifier ensure. If the shared is somehow elided like you propose, then the compiler wont issue the correct reads with the pure const function, and sequential consistency won't be ensured anymore. This is not acceptable as per spec, shared things are sequentially consistent.
Nov 05 2013
parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 06.11.2013 02:28, deadalnix wrote:
 On Wednesday, 6 November 2013 at 01:04:19 UTC, Simen Kjærås wrote:
 I believe you are thinking of strict consistency[0][1], not sequential
 consistency[2][3].

 In the former case, all reads are required to return the result of the
 last write to that address. In the case of sequential consistency, it
 is only necessary that each processor performs reads in the order they
 are issued, and that each processor sees the results of other
 processors' writes in the order in which they are issued.

 From Lamport's original paper[4] on the subject: "the result of any
 execution is the same as if the operations of all the processors were
 executed in some sequential order, and the operations of each
 individual processor appear in this sequence in the order specified by
 its program."
Yes, that is what sequential consistency is. It require both the writer and the reader to cooperate for this to happen. People often get confused by think the reader do not need to do anything special as the MOV instruction on x86 have the needed guarantee. Consider that thread a does : arr[0] = newvalue0 arr[1] = newvalue1 thread 2 could see newvalue1 but not newvalue0 is no sequential consistency is present. Note that it will happen to work on x86, because of the strong memory model of x86, but it is not something safe in the general case and something we should rely on in language specs.
 In essence, what I propose is a behavior equivalent to that the
 function fuzz finish (essentially) instantaneously.
In this very specific case, the function does nothing, so it is safe. But we don't want to define rules that depend on the function implementation.
Indeed not. That's why I've argued that it should depend only on the function definition (const, pure, and all arguments implicitly convertable to immutable).
 Without sequential consistency, CPU1 can see the operation of CPU2 in
 the wrong order,
Indeed. Now, as I have shown, making a copy makes sure no such thing will happen. Unless, as stated above, you mean strict consistency.
No making a copy is fine and the case where you pass by value (you make a copy) do indeed work as expected.
Then what are you even arguing? I'm asking if this is fine, and now it is? What are you saying is not fine, then? The whole idea here is that making a copy and operating on that does not violate SC (see diagram in earlier post), and thus that calling a const pure function on a type that's implicitly convertable to immutable and that only takes arguments that are implicitly convertable to immutable is safe to implement as making a copy and operating on that. I've asked you twice now to give an example of how this idea is wrong, and I've yet to see any evidence it is. It is of course not the case that operating on the shared value without copying is safe - that's why I argue that copying is good.
 I especially suggest you read reference [3], as it shows very well
 that two executions of the same sequentially consistent program may
 give different results.
I understand the difference. But as long as both require cooperation of the 2 threads, it doesn't change much to our discussion here. We also do not say that sequential consistency will magically make the program correct. Simply that sequential consistency is what D's shared qualifier ensure. If the shared is somehow elided like you propose, then the compiler wont issue the correct reads with the pure const function, and sequential consistency won't be ensured anymore. This is not acceptable as per spec, shared things are sequentially consistent.
I cannot for the life of me see how my suggestion violates SC, and you even seem to say it doesn't ("making a copy is fine"). Are you arguing about something other than what I'm arguing about? -- Simen
Nov 05 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 6 November 2013 at 03:07:08 UTC, Simen Kjærås wrote:
 I cannot for the life of me see how my suggestion violates SC, 
 and you even seem to say it doesn't ("making a copy is fine"). 
 Are you arguing about something other than what I'm arguing 
 about?
Calling member function is a pass by reference. The reference is shared. SO you can't call a pure const method on a shared object. You can pass a shared object by value to a function expecting a const (as long as it do not contains indirection and is copyable).
Nov 05 2013
parent =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 06.11.2013 04:59, deadalnix wrote:
 On Wednesday, 6 November 2013 at 03:07:08 UTC, Simen Kjærås wrote:
 I cannot for the life of me see how my suggestion violates SC, and you
 even seem to say it doesn't ("making a copy is fine"). Are you arguing
 about something other than what I'm arguing about?
Calling member function is a pass by reference. The reference is shared. SO you can't call a pure const method on a shared object. You can pass a shared object by value to a function expecting a const (as long as it do not contains indirection and is copyable).
Turned my brain back on again this morning, and things became more clear. The problem is in my claim that the type is convertable to immutable, which is not the case (since it ends up with a *reference to a mutable* array of immutable elements). Now, for the example I've asked for: struct S { immutable(int)[] arr; int fuzz() const pure { while (arr.length) {} return 3; } } However, the problem here is not one of sequential consistency. In fact, this function could copy arr.length to a local variable and enter an infinite loop, and still not violate sequential consistency. This would of course be useless, but still valid program behavior. -- Simen
Nov 06 2013
prev sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Sunday, 3 November 2013 at 21:55:22 UTC, Simen Kjærås wrote:
 Consider:

 module foo;

 struct S {
     immutable(int)[] arr;
     void fuzz() const pure {
     }
 }

 void bar(S s) {
     s.fuzz();
 }

 void main() {
     shared S s;
     bar(s);   // a
     s.fuzz(); // b
 }


 In this case, the line marked 'a' works perfectly - it compiles 
 and does what I'd expect it to.

 However,the line marked 'b' does not compile - " non-shared 
 const method foo.S.fuzz is not callable using a shared mutable 
 object ".

 The reason for this is that fuzz takes the 'this' pointer by 
 reference, and so risks that another thread corrupt the 
 internal state while it's working.

 Seeing as line 'a' works, it seems safe for line 'b' to make a 
 copy behind the scenes
Why should method call invole copy? This breaks lots of assumptions and it would be a pretty weird corner case.
 (structs in D are defined to have cheap copying, I seem to 
 recall)
Why? There is no restrictions on postblit, so copying may be cheap as well as arbitrary costly.
 and call fuzz on that copy - the type system claims that the 
 call to fuzz cannot possibly change the state of the struct on 
 which it is called.
Your problem may be solved pretty simple: pure fuzz(S s) { } and be happy with s.fuzz() operating and copy if you want so. Does it address your problem?
 With the state of 'shared' as it is, I'm unsure if this is a 
 change that should be done - it seems perhaps better to wait 
 for a true overhaul of the feature.
What shared means in D is not trivial question, I agree.
Nov 04 2013
parent =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 04.11.2013 11:28, Maxim Fomin wrote:
 Why should method call invole copy? This breaks lots of assumptions and
 it would be a pretty weird corner case.
The idea was that it's basically an optimization. The type system guarantees that there is no difference.
 (structs in D are defined to have cheap copying, I seem to recall)
Why? There is no restrictions on postblit, so copying may be cheap as well as arbitrary costly.
I do not have a reference handy, but Andrei or Walter has stated in the past that it is safe to assume that copying is cheap.
 and call fuzz on that copy - the type system claims that the call to
 fuzz cannot possibly change the state of the struct on which it is
 called.
Your problem may be solved pretty simple: pure fuzz(S s) { } and be happy with s.fuzz() operating and copy if you want so. Does it address your problem?
Not really. My specific problem is with std.math.abs and shared BigInt. Bug 11188 explains how it is not possible to call abs((shared BigInt).init). The reason for that is that the operator overloads are not marked shared. They are however both const and pure. As we know, operator overloads may not be defined outside the aggregate type. -- Simen
Nov 04 2013