digitalmars.D - What functions can be called on a shared struct that's implicitly
- =?ISO-8859-1?Q?Simen_Kj=E6r=E5s?= (36/36) Nov 03 2013 Consider:
- deadalnix (2/22) Nov 03 2013 It is because a imply a pass b value, when b a pass by reference.
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (13/42) Nov 04 2013 Indeed. That's why I wrote that one line further down. That's not the
- deadalnix (5/52) Nov 04 2013 You are trying to solve a non problem here. s is not shared in
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (23/27) Nov 04 2013 I believe we're talking past each other here. Perhaps a better example:
- deadalnix (3/36) Nov 04 2013 Any read of arr in fuzz won't be sequentially consistent, so it
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (39/78) Nov 05 2013 Thank you, that's what I wanted to hear. I don't agree though.
- deadalnix (6/41) Nov 05 2013 No, that mean that read and write for ALL processor are done in
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (38/50) Nov 05 2013 I believe you are thinking of strict consistency[0][1], not sequential
- deadalnix (27/51) Nov 05 2013 Yes, that is what sequential consistency is. It require both the
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (20/74) Nov 05 2013 Indeed not. That's why I've argued that it should depend only on the
- deadalnix (5/9) Nov 05 2013 Calling member function is a pass by reference. The reference is
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (19/27) Nov 06 2013 Turned my brain back on again this morning, and things became more
- Maxim Fomin (13/46) Nov 04 2013 Why should method call invole copy? This breaks lots of
- =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= (12/26) Nov 04 2013 The idea was that it's basically an optimization. The type system
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
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
On 04.11.2013 06:53, deadalnix wrote:On Sunday, 3 November 2013 at 21:55:22 UTC, Simen Kjærås wrote: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? -- SimenConsider: 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 04 2013
On Monday, 4 November 2013 at 08:14:57 UTC, Simen Kjærås wrote:On 04.11.2013 06:53, 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.On Sunday, 3 November 2013 at 21:55:22 UTC, Simen Kjærås wrote: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? -- SimenConsider: 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 04 2013
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
On Monday, 4 November 2013 at 09:34:52 UTC, Simen Kjærås wrote:On 04.11.2013 09:46, deadalnix wrote: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.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
On 04.11.2013 20:52, deadalnix wrote:On Monday, 4 November 2013 at 09:34:52 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. 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? -- SimenOn 04.11.2013 09:46, deadalnix wrote: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.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 05 2013
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
On 05.11.2013 20:03, deadalnix wrote:On Tuesday, 5 November 2013 at 17:37:26 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." In essence, what I propose is a behavior equivalent to that the function fuzz finish (essentially) instantaneously.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.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
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.No making a copy is fine and the case where you pass by value (you make a copy) do indeed work as expected.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.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
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.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).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.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.No making a copy is fine and the case where you pass by value (you make a copy) do indeed work as expected.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.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? -- SimenI 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
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
On 06.11.2013 04:59, deadalnix wrote:On Wednesday, 6 November 2013 at 03:07:08 UTC, Simen Kjærås wrote: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. -- SimenI 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 06 2013
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 scenesWhy 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
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.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.(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.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. -- Simenand 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?
Nov 04 2013