On 07-06-2012 03:55, Andrei Alexandrescu wrote:
> On 6/6/12 8:19 PM, Alex Rønne Petersen wrote:
>> On 07-06-2012 03:11, Andrei Alexandrescu wrote:
>>> On 6/6/12 6:01 PM, Alex Rønne Petersen wrote:
>>>> (At this point, I probably don't need to point out how x86-biased and
>>>> unportable shared is.....)
>>>
>>> I confess I'll need that spelled out. How is shared biased towards x86
>>> and nonportable?
>>>
>>> Thanks,
>>>
>>> Andrei
>>
>> The issue lies in its assumption that the architecture being targeted
>> supports atomic operations and/or memory barriers at all. Some
>> architectures plain don't support these, others do, but for certain data
>> sizes like 64-bit ints, they don't, etc. x86 is probably the
>> architecture that has the best support for low-level memory control as
>> far as atomicity and memory barriers go.
>
> Actually x86 is one of the more forgiving architectures (most code works
> even when written without barriers). Indeed we assume the target
> architecture supports double-word atomic load.

And if cent/ucent ever get implemented (which does seem likely, although they're low-prio), we'll have to assume 128-bit too. Here Be Dragons. ;)

>
>> The problem is that shared is supposed to guarantee that operations on
>> shared data *always* obeys whatever atomicity/memory barrier rules we
>> end up defining for it (obviously we don't want generated code to have
>> different semantics across architectures due to subtle issues like the
>> lack of certain operations in the ISA). Right now, based on what I've
>> read in the NG and on mailing lists, people seem to assume that shared
>> will provide full-blown x86-level atomicity and/or memory barriers.
>> Providing these features on e.g. ARM is a pipe dream at best (for
>> instance, ARM has no atomic load for 64-bit values).
>
> http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html mentions that
> there is a way to implement atomic load for 64-bit values.

You learn something new every day! When we did research for MCI's atomic intrinsics, we didn't notice these instructions on ARM. Thanks for the link.

This covers most significant architectures today, but I'm still worried about e.g. Super-H, Alpha, SPARC, MIPS, and others that are listed on http://dlang.org/version.html (I think that at least SPARC lacks double-word atomic load/store).

>
>> All this being said, shared could probably be implemented with plain old
>> locks on these architectures if correctness is the only goal. But, from
>> a more pragmatic point of view, this would completely butcher
>> performance and adds potential for deadlocks, and all other issues
>> associated with thread synchronization in general. We really shouldn't
>> have such a core feature of the language fall back to a dirty hack like
>> this on low-end/embedded architectures (where performance of this kind
>> of stuff is absolutely critical), IMO.
>
> That's how C++'s atomic<T> does things, by the way. But I sympathize
> with your viewpoint that there should be no hidden locks. We could
> define shared to refuse compilation on odd machines, and THEN provide an
> atomic template with the expected performance of a lock.

That may be a reasonable approach. But if we do this, I think we need to revisit the core.atomic API, since it unnecessarily requires the shared qualifier for some things (just because shared overall isn't useful on a target architecture doesn't mean that e.g. a 32-bit atomic load can't be done on it).

>
>
> Andrei
>

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org

On 7 June 2012 04:55, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org>wrote:

> We could define shared to refuse compilation on odd machines, and THEN provide an atomic template with the expected performance of a lock.
>

*sigh* .. my biggest pet peeve with the D community.
ARM and PPC are not 'odd', ARM is the most common consumer architecture in
the world. PPC powers all current gaming consoles and other entertainment
devices.
x86, is only used in PC's, which are losing market share to phones,
tablets, and games devices at a fast and accelerating rate. Even ARM
netbooks/laptops are starting to appear.

I'd really like to see a mental shift within the D community where ARM was recognised as a 1st class architecture, and factored into EVERY technical decision, potentially with higher priority than x86 even. The performance and efficiency requirements of arm and ppc devices is virtually always much higher than that demanded of x86, and the architectures are slower to begin with, so they have more to lose.

One could argue features should be designed to be as efficient as possible for ARM, and architectural work-arounds should be applied to the x86 implementation. x86 users won't notice, arm users will.

</endrant> ;)

On 6/7/12 9:13 AM, Manu wrote:
> On 7 June 2012 04:55, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org
> <mailto:SeeWebsiteForEmail@erdani.org>> wrote:
>
>     We could define shared to refuse compilation on odd machines, and
>     THEN provide an atomic template with the expected performance of a lock.
>
>
> *sigh* .. my biggest pet peeve with the D community.
> ARM and PPC are not 'odd'

I agree. I didn't mean to qualify ARM/PPC as odd.

Andrei

On Wed, 06 Jun 2012 19:01:59 -0400, Alex Rønne Petersen <alex@lycus.org> wrote:


> Steven, in your particular case, I don't agree entirely. The operation can be atomic quite trivially by implementing inc() like so (for the shared int case):
>
> void inc(ref shared int i) pure nothrow
> {
>      // just pretend the compiler emitted this
>      asm
>      {
>          mov EDX, i;
>          lock;
>          inc [EDX];
>      }
> }
>
> But I may be misunderstanding you.

I think you are.  I understand the implementation is not correct for shared, and that actually is my point.  The current compiler lets you do the wrong thing without complaint.  Given that the shared version of the function needs to be written differently than the unshared version, we gain nothing but bugs by allowing pure functions that operate on shared.

In essence, a pure-accepting-shared (PAS) function is not realistically useful from a strong-pure function.  A strong-pure function will have no ties to shared data, and while it may be able to create data that could potentially be shared, it can't actually share it!  So a PAS function being called from a strong-pure function is essentially doing extra work (even if it's not implemented, the expectation is it will be some day) for no reason.

So since a PAS function cannot usefully be optimized (much better to write an unshared version, it's more accurate), and must be written separately from the unshared version, I see no good reason to allow shared in pure functions ever.  I think we gain a lot by not allowing it (more sanity for one thing!)

-Steve

On 06/07/12 16:43, Steven Schveighoffer wrote:
> I understand the implementation is not correct for shared, and that actually is my point.  The current compiler lets you do the wrong thing without complaint.  Given that the shared version of the function needs to be written differently than the unshared version, we gain nothing but bugs by allowing pure functions that operate on shared.
> 
> In essence, a pure-accepting-shared (PAS) function is not realistically useful from a strong-pure function.  A strong-pure function will have no ties to shared data, and while it may be able to create data that could potentially be shared, it can't actually share it!  So a PAS function being called from a strong-pure function is essentially doing extra work (even if it's not implemented, the expectation is it will be some day) for no reason.
> 
> So since a PAS function cannot usefully be optimized (much better to write an unshared version, it's more accurate), and must be written separately from the unshared version, I see no good reason to allow shared in pure functions ever.  I think we gain a lot by not allowing it (more sanity for one thing!)

While it's true that "shared" inside pure functions doesn't _look_ right, can you think
of a case where it is actually wrong, given the pure model currently in use?
Would inferring templated functions as impure if they access (and not just reference)
shared data help?

IOW, a function marked as pure that deals with shared data can not be "truly" pure, and can not be called from a "really" pure function (as that one would have to handle shared, so it couldn't be pure either) - so does it make sense to add new restrictions now, and not delay this until the "pure" model is improved?

artur

On Thu, 07 Jun 2012 11:55:32 -0400, Artur Skawina <art.08.09@gmail.com> wrote:

> On 06/07/12 16:43, Steven Schveighoffer wrote:
>> I understand the implementation is not correct for shared, and that actually is my point.  The current compiler lets you do the wrong thing without complaint.  Given that the shared version of the function needs to be written differently than the unshared version, we gain nothing but bugs by allowing pure functions that operate on shared.
>>
>> In essence, a pure-accepting-shared (PAS) function is not realistically useful from a strong-pure function.  A strong-pure function will have no ties to shared data, and while it may be able to create data that could potentially be shared, it can't actually share it!  So a PAS function being called from a strong-pure function is essentially doing extra work (even if it's not implemented, the expectation is it will be some day) for no reason.
>>
>> So since a PAS function cannot usefully be optimized (much better to write an unshared version, it's more accurate), and must be written separately from the unshared version, I see no good reason to allow shared in pure functions ever.  I think we gain a lot by not allowing it (more sanity for one thing!)
>
> While it's true that "shared" inside pure functions doesn't _look_ right, can you think
> of a case where it is actually wrong, given the pure model currently in use?
> Would inferring templated functions as impure if they access (and not just reference)
> shared data help?

I contend it would make marking a template as pure more useful -- you can with one keyword ban all use of shared via template parameters on a template function, given that it does not properly protect shared data from races.  You can do the same with template constraints, but it's unnecessary boilerplate, only there because the compiler incorrectly allows PAS functions.  Unless you plan to implement a shared version, in which case there's no less or more code.

> IOW, a function marked as pure that deals with shared data can not be "truly" pure, and
> can not be called from a "really" pure function (as that one would have to handle shared,
> so it couldn't be pure either) - so does it make sense to add new restrictions now, and
> not delay this until the "pure" model is improved?

To what improvements do you refer?  I think what is currently in place is sound design, with incomplete or buggy implementation.

-Steve

On 06/07/12 18:45, Steven Schveighoffer wrote:
> On Thu, 07 Jun 2012 11:55:32 -0400, Artur Skawina <art.08.09@gmail.com> wrote:
> 
>> On 06/07/12 16:43, Steven Schveighoffer wrote:
>>> I understand the implementation is not correct for shared, and that actually is my point.  The current compiler lets you do the wrong thing without complaint.  Given that the shared version of the function needs to be written differently than the unshared version, we gain nothing but bugs by allowing pure functions that operate on shared.
>>>
>>> In essence, a pure-accepting-shared (PAS) function is not realistically useful from a strong-pure function.  A strong-pure function will have no ties to shared data, and while it may be able to create data that could potentially be shared, it can't actually share it!  So a PAS function being called from a strong-pure function is essentially doing extra work (even if it's not implemented, the expectation is it will be some day) for no reason.
>>>
>>> So since a PAS function cannot usefully be optimized (much better to write an unshared version, it's more accurate), and must be written separately from the unshared version, I see no good reason to allow shared in pure functions ever.  I think we gain a lot by not allowing it (more sanity for one thing!)
>>
>> While it's true that "shared" inside pure functions doesn't _look_ right, can you think
>> of a case where it is actually wrong, given the pure model currently in use?
>> Would inferring templated functions as impure if they access (and not just reference)
>> shared data help?
> 
> I contend it would make marking a template as pure more useful -- you can with one keyword ban all use of shared via template parameters on a template function, given that it does not properly protect shared data from races.

"not properly protecting shared data from races" is as language issue, it's not specific to pure functions or templates. (Note: this does not mean that "shared" currently does too little; it in fact does too much, but that's a completely different issue)

This

   shared Atomic!int x;

   void main() { x.inc(); };

will do the right thing, even with your "void inc(T)(ref T i) pure" template. Yes, it's not actually pure, but that won't be problem in practice because it takes a mutable reference as input. You are proposing to disallow this.


>> IOW, a function marked as pure that deals with shared data can not be "truly" pure, and can not be called from a "really" pure function (as that one would have to handle shared, so it couldn't be pure either) - so does it make sense to add new restrictions now, and not delay this until the "pure" model is improved?
> 
> To what improvements do you refer?  I think what is currently in place is sound design, with incomplete or buggy implementation.

As far as it relates to this i don't see a problem - except for the "const shared" case, which does not really make sense - the compiler has to assume another thread could have mutated the data, so it cannot take advantage of the fact that this thread did not. But I guess it could be useful for statically ensuring that an implementation does not modify a r/o view of shared data. In every other case the function can't be really pure.

The main improvement needed is real purity for functions that not only take value inputs but also const references (including pointers, which then need similar treatment inside such functions).

artur

On Thu, 07 Jun 2012 13:46:43 -0400, Artur Skawina <art.08.09@gmail.com> wrote:

> On 06/07/12 18:45, Steven Schveighoffer wrote:
>> On Thu, 07 Jun 2012 11:55:32 -0400, Artur Skawina <art.08.09@gmail.com> wrote:
>>
>>> On 06/07/12 16:43, Steven Schveighoffer wrote:
>>>> I understand the implementation is not correct for shared, and that actually is my point.  The current compiler lets you do the wrong thing without complaint.  Given that the shared version of the function needs to be written differently than the unshared version, we gain nothing but bugs by allowing pure functions that operate on shared.
>>>>
>>>> In essence, a pure-accepting-shared (PAS) function is not realistically useful from a strong-pure function.  A strong-pure function will have no ties to shared data, and while it may be able to create data that could potentially be shared, it can't actually share it!  So a PAS function being called from a strong-pure function is essentially doing extra work (even if it's not implemented, the expectation is it will be some day) for no reason.
>>>>
>>>> So since a PAS function cannot usefully be optimized (much better to write an unshared version, it's more accurate), and must be written separately from the unshared version, I see no good reason to allow shared in pure functions ever.  I think we gain a lot by not allowing it (more sanity for one thing!)
>>>
>>> While it's true that "shared" inside pure functions doesn't _look_ right, can you think
>>> of a case where it is actually wrong, given the pure model currently in use?
>>> Would inferring templated functions as impure if they access (and not just reference)
>>> shared data help?
>>
>> I contend it would make marking a template as pure more useful -- you can with one keyword ban all use of shared via template parameters on a template function, given that it does not properly protect shared data from races.
>
> "not properly protecting shared data from races" is as language issue, it's not
> specific to pure functions or templates. (Note: this does not mean that "shared"
> currently does too little; it in fact does too much, but that's a completely
> different issue)
>
> This
>
>    shared Atomic!int x;
>
>    void main() { x.inc(); };
>
> will do the right thing, even with your "void inc(T)(ref T i) pure" template.

Right, but if you want to handle shared too, just don't mark inc as pure.  There isn't any advantage to marking it pure.  The compiler will infer pure when it should.  Since pure functions (in the proposed fixed compiler) cannot handle shared data, there is no need to mark inc pure, it can always be called from a pure function.

Note that the above, while correct, is not a condition of shared.  That it *can* be made to work isn't a factor of inc.

But I can specify inc is pure, and if shared data isn't allowed, inc can be *sure* it's not going to be abused.  It's entirely possible to look at the inc function, and reason that it can't be used to make a race bug (assuming someone doesn't deliberately sabotage the increment operator on a type by casting away pure).

> Yes, it's not actually pure, but that won't be problem in practice because it
> takes a mutable reference as input. You are proposing to disallow this.

I'm not proposing disallowing mutable references, just shared references.

>>> IOW, a function marked as pure that deals with shared data can not be "truly" pure, and
>>> can not be called from a "really" pure function (as that one would have to handle shared,
>>> so it couldn't be pure either) - so does it make sense to add new restrictions now, and
>>> not delay this until the "pure" model is improved?
>>
>> To what improvements do you refer?  I think what is currently in place is sound design, with incomplete or buggy implementation.
>
> As far as it relates to this i don't see a problem - except for the "const shared"
> case, which does not really make sense - the compiler has to assume another thread
> could have mutated the data, so it cannot take advantage of the fact that this
> thread did not. But I guess it could be useful for statically ensuring that an
> implementation does not modify a r/o view of shared data. In every other case the
> function can't be really pure.
>
> The main improvement needed is real purity for functions that not only take value
> inputs but also const references (including pointers, which then need similar
> treatment inside such functions).

pure functions that take immutable arguments can be optimized for purity already.  I agree there are optimizations that could be enabled that aren't, but that doesn't make those uses invalid usages of purity.  Shared can be also lumped in there, but my contention is that there's no usefulness in that construct.

-Steve

On 06/07/12 20:29, Steven Schveighoffer wrote:
> On Thu, 07 Jun 2012 13:46:43 -0400, Artur Skawina <art.08.09@gmail.com> wrote:
> 
>> On 06/07/12 18:45, Steven Schveighoffer wrote:
>>> On Thu, 07 Jun 2012 11:55:32 -0400, Artur Skawina <art.08.09@gmail.com> wrote:
>>>
>>>> On 06/07/12 16:43, Steven Schveighoffer wrote:
>>>>> I understand the implementation is not correct for shared, and that actually is my point.  The current compiler lets you do the wrong thing without complaint.  Given that the shared version of the function needs to be written differently than the unshared version, we gain nothing but bugs by allowing pure functions that operate on shared.
>>>>>
>>>>> In essence, a pure-accepting-shared (PAS) function is not realistically useful from a strong-pure function.  A strong-pure function will have no ties to shared data, and while it may be able to create data that could potentially be shared, it can't actually share it!  So a PAS function being called from a strong-pure function is essentially doing extra work (even if it's not implemented, the expectation is it will be some day) for no reason.
>>>>>
>>>>> So since a PAS function cannot usefully be optimized (much better to write an unshared version, it's more accurate), and must be written separately from the unshared version, I see no good reason to allow shared in pure functions ever.  I think we gain a lot by not allowing it (more sanity for one thing!)
>>>>
>>>> While it's true that "shared" inside pure functions doesn't _look_ right, can you think
>>>> of a case where it is actually wrong, given the pure model currently in use?
>>>> Would inferring templated functions as impure if they access (and not just reference)
>>>> shared data help?
>>>
>>> I contend it would make marking a template as pure more useful -- you can with one keyword ban all use of shared via template parameters on a template function, given that it does not properly protect shared data from races.
>>
>> "not properly protecting shared data from races" is as language issue, it's not specific to pure functions or templates. (Note: this does not mean that "shared" currently does too little; it in fact does too much, but that's a completely different issue)
>>
>> This
>>
>>    shared Atomic!int x;
>>
>>    void main() { x.inc(); };
>>
>> will do the right thing, even with your "void inc(T)(ref T i) pure" template.
> 
> Right, but if you want to handle shared too, just don't mark inc as pure.  There isn't any advantage to marking it pure.  The compiler will infer pure when it should.  Since pure functions (in the proposed fixed compiler) cannot handle shared data, there is no need to mark inc pure, it can always be called from a pure function.
> 
> Note that the above, while correct, is not a condition of shared.  That it *can* be made to work isn't a factor of inc.
> 
> But I can specify inc is pure, and if shared data isn't allowed, inc can be *sure* it's not going to be abused.  It's entirely possible to look at the inc function, and reason that it can't be used to make a race bug (assuming someone doesn't deliberately sabotage the increment operator on a type by casting away pure).
> 
>> Yes, it's not actually pure, but that won't be problem in practice because it takes a mutable reference as input. You are proposing to disallow this.
> 
> I'm not proposing disallowing mutable references, just shared references.

I know, but if a D function marked as "pure" takes a mutable ref (which a shared
one has to be assumed to be), it won't be treated as really pure for optimization
purposes (yes, i'm deliberately trying to avoid "strong" and "weak"). And any caller
will have to obtain this shared ref either from a mutable argument or global state.
Hence that "pure" function with shared inputs will *never* actually be pure.
So I'm wondering what would be the gain from banning shared in weakly pure functions
(Ugh, you made me use that word after all ;) ).
AFAICT you're proposing to forbid something which currently is a NOOP. And the change
could have consequences for templated functions or lambdas, where "pure" is inferred.

artur

On Thu, 07 Jun 2012 15:16:20 -0400, Artur Skawina <art.08.09@gmail.com> wrote:

> On 06/07/12 20:29, Steven Schveighoffer wrote:

>> I'm not proposing disallowing mutable references, just shared references.
>
> I know, but if a D function marked as "pure" takes a mutable ref (which a shared
> one has to be assumed to be), it won't be treated as really pure for optimization
> purposes (yes, i'm deliberately trying to avoid "strong" and "weak").

However, a mutable pure function can be *inside* an optimizable pure function, and the optimizable function can still be optimized.

A PAS function (pure accepting shared), however, devolves to a mutable pure function.  That is, there is zero advantage of having a pure function take shared vs. simply mutable TLS.

There is only one reason to mark a function that does not take all immutable or value type arguments as pure -- so it can be called inside a strong-pure function.  Otherwise, it's just a normal function, and even marked as pure will not be optimized.  You gain nothing else by marking it pure.

So let's look at two cases.  I'll re-state my example, in terms of two overloads, one which takes shared int and one which takes just int (both of which do the right thing):

void inc(ref int t) pure;
{
  ++t;
}

void inc(ref shared(int) t) pure
{
  atomicOp!"++"(t);
}

Now, let's define a strong-pure function that uses inc:

int slowAdd(int x, int y) pure
{
   while(y--) inc(x);
   return x;
}

I think we can both agree that inc *cannot* be optimized away, and that we agree slowAdd is *fully pure*.  That is, slowAdd *can* be optimized away, even though its call to inc cannot.

Now, what about a strong-pure function using the second (shared) form?  A strong pure function has to have all parameters (and return types) that are immutable or implicitly convertable to immutable.

I'll re-define slowAdd:

int slowAddShared(int x, int y) pure
{
   shared int sx = x;
   while(y--) inc(sx);
   return sx;
}

We can agree for the same reason the original slowAdd is strong-pure, slowAddShared is strong-pure.

But what do we gain by being able to declare sx shared?  We can't return it as shared, or slowAddShared becomes weak-pure.  We can't share it while inside slowAddShared, because we have no outlet for it, and we cannot access global variables.  In essence, marking sx as shared does *nothing*.  In fact, it does worse than nothing -- we now have to contend with shared for data that actually is *provably* unshared.  In other words, we are wasting cycles doing atomic operations instead of straight ops on a shared type.  Not only that, but because there are no outlets, declaring *any* data as shared while inside a strong-pure function is useless, no matter how we define any PAS functions.

So if shared is useless inside a strong-pure function, and the only point in marking a non-pure-optimizable function as pure is so it can be called within a strong-pure function, then pure is useless as an attribute on a function that accepts or returns shared data.  *Every case* where you use such a function inside a strong-pure function is incorrect.

But *mutable* data accepting functions *are* useful, because it allows us to modularize pure functions.  For example, sort can be (and should be) pure.  Instead of implementing a functional-style sort, or manually sorting data inside a strong-pure function, we can simply call sort, and it acts as a component of a strong-pure function, fully optimizable based on pure optimization rules.


> And any caller
> will have to obtain this shared ref either from a mutable argument or global state.
> Hence that "pure" function with shared inputs will *never* actually be pure.
> So I'm wondering what would be the gain from banning shared in weakly pure functions

What is to gain is clarity, and more control over parameter types in generic code.

If shared is banned, than:

void inc(T)(ref T t) pure { ++t; }

*always* does the right thing.  As the author of inc, I am done.  I don't need template constraints or documentation, or anything else, and I don't need to worry about users abusing my function.  The compiler will enforce nobody uses this on shared data, which would require an atomic operation.

> (Ugh, you made me use that word after all ;) ).

I did nothing of the sort :)

> AFAICT you're proposing to forbid something which currently is a NOOP.

It's not a NOOP, marking something as shared means you need special handling.  You can't call most functions or methods with shared data.  And if you do handle shared data, it's not just "the same" as unshared data -- you need to contend with data races, memory barriers, etc.  Just because it's marked shared doesn't mean everything about it is handled.

> And the change
> could have consequences for templated functions or lambdas, where "pure" is inferred.

I would label those as *helpful* and *positive* consequences ;)

-Steve