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

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.

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

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).

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