"Steven Schveighoffer" <schveiguy yahoo.com> writes:

An interesting situation, the current compiler happily will compile pure  
functions that accept shared data.

I believed when we relaxed purity rules, shared data should be taboo for  
pure functions, even weak-pure ones.  Note that at least at the time, Don  
agreed with me: http://forum.dlang.org/post/i7d60m$2smf$1 digitalmars.com

Now, technically, there's nothing really *horrible* about this, I mean you  
can't really have truly shared data inside a strong-pure function.  Any  
data that's marked as 'shared' will not be shared because a strong-pure  
function cannot receive any shared data.

So if you then were to call a weak-pure function that had shared  
parameters from a strong-pure function, you simply would be wasting cycles  
locking or using a memory-barrier on data that is not truly shared.  I  
don't really see a compelling reason to have weak-pure functions accept  
shared data explicitly.

*Except* that template functions which use IFTI have good reason to be  
able to be marked pure.

For example:

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

Now, we have a template function that we know only will affect i, and the  
compiler enforces that.

But what happens here?

shared int x;

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

here, T == shared int.

One solution (if shared isn't allowed on pure functions) is, don't mark  
inc pure, let it be inferred.  But then we are losing the contract to have  
the compiler help us enforce purity.

I'll also point out that inc isn't a valid function for data that is  
actually shared: ++i is not atomic.  So disallowing shared actually helps  
us in this regard, by refusing to compile a function that would be  
dangerous when used on shared data.

The compiler *currently* however, will simply compile this just fine.

I'm strongly leaning towards this being a bug, and needs to be fixed in  
the compiler.

Some background of why this got brought up:  
https://github.com/D-Programming-Language/druntime/pull/147

Opinions?

-Steve

=?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <alex lycus.org> writes:

On 06-06-2012 23:39, Steven Schveighoffer wrote:
 An interesting situation, the current compiler happily will compile pure
 functions that accept shared data.

 I believed when we relaxed purity rules, shared data should be taboo for
 pure functions, even weak-pure ones. Note that at least at the time, Don
 agreed with me: http://forum.dlang.org/post/i7d60m$2smf$1 digitalmars.com

 Now, technically, there's nothing really *horrible* about this, I mean
 you can't really have truly shared data inside a strong-pure function.
 Any data that's marked as 'shared' will not be shared because a
 strong-pure function cannot receive any shared data.

 So if you then were to call a weak-pure function that had shared
 parameters from a strong-pure function, you simply would be wasting
 cycles locking or using a memory-barrier on data that is not truly
 shared. I don't really see a compelling reason to have weak-pure
 functions accept shared data explicitly.

 *Except* that template functions which use IFTI have good reason to be
 able to be marked pure.

 For example:

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

 Now, we have a template function that we know only will affect i, and
 the compiler enforces that.

 But what happens here?

 shared int x;

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

 here, T == shared int.

 One solution (if shared isn't allowed on pure functions) is, don't mark
 inc pure, let it be inferred. But then we are losing the contract to
 have the compiler help us enforce purity.

 I'll also point out that inc isn't a valid function for data that is
 actually shared: ++i is not atomic. So disallowing shared actually helps
 us in this regard, by refusing to compile a function that would be
 dangerous when used on shared data.

Man, shared is such a mess.

(I'm going to slightly hijack a branch of your thread because I think we 
need to address the below concerns before we can make this decision 
properly.)

We need to be crystal clear on what we're talking about here. Usually, 
people refer to shared as being supposed to insert memory barriers. 
Others call operations on shared data atomic.

(And of course, neither is actually implemented in any compiler, and I 
doubt they ever will be.)

A memory barrier is what the x86 sfence, lfence, and mfence instructions 
represent. They simply make various useful guarantees about ordering of 
loads and stores. Nothing else.

Atomic operations are what the lock prefix is used for, for example the 
lock add operation, lock cmpxchg, etc. These operate on the most recent 
value at whatever memory location is being operated on, i.e. caches are 
circumvented.

Memory barriers and atomic operations are not the same thing, and we 
should avoid conflating them. Yes, they can be used together to write 
low-level, lock-free data structures, but the use of one does not 
include the other automatically.

(At this point, I probably don't need to point out how x86-biased and 
unportable shared is.....)

So, my question to the community is: What should shared *really* mean?

I don't think that having shared imply memory barriers is going to be 
terribly useful to anyone. In fact, I don't know how the compiler would 
even determine where to efficiently insert memory barriers. And 
*actually*, I think memory barriers is really not what people mean at 
*all* when they refer to shared's effect on code generation. I think 
what people *really* want is atomic operations.

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. Of course, it gets a little more 
complex if you use the result of the ++ operation afterwards, but it's 
still not impossible to do atomically. What can *not* be done is doing 
the increment and loading the result in one purely atomic instruction 
(and I suspect this is what you may have been referring to). It's worth 
pointing out that most atomic operations can be implemented with a spin 
lock (which is exactly what core.atomic does for most binary 
operations), so while it cannot be done with an x86 instruction, it can 
be achieved through such a mechanism, and most real world atomic APIs do 
this (see InterlockedIncrement in Windows for example).

Further, if shared is going to be useful at all, stuff like this *has* 
to be atomic, IMO.

I'm still of the opinion that bringing atomicity and memory barriers 
into the type system is a horrible can of worms that we should never 
have opened, but now shared is there and we need to make up our minds 
already.

 The compiler *currently* however, will simply compile this just fine.

 I'm strongly leaning towards this being a bug, and needs to be fixed in
 the compiler.

 Some background of why this got brought up:
 https://github.com/D-Programming-Language/druntime/pull/147

 Opinions?

 -Steve

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

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 6/6/12 6:01 PM, Alex Rønne Petersen wrote:
 (And of course, neither is actually implemented in any compiler, and I
 doubt they ever will be.)

Why do you doubt shared semantics will be implemented?

Andrei

=?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <alex lycus.org> writes:

On 07-06-2012 03:07, Andrei Alexandrescu wrote:
 On 6/6/12 6:01 PM, Alex Rønne Petersen wrote:
 (And of course, neither is actually implemented in any compiler, and I
 doubt they ever will be.)

 Why do you doubt shared semantics will be implemented?

 Andrei

I think there are two fundamental issues making implementation difficult 
and unlikely to happen:

1) The x86 bias (I replied to your other post wrt this).
2) The overall complexity of generating correct code for shared.

If we ignore the portability issues that I pointed out in my other 
reply, point (1) is irrelevant. I'm fairly certain the shared semantics 
that people expect can be implemented just fine at ISA level on x86 
without dirty hacks like locks. But if we do care about portability 
(which we ***really*** should - ARM and PowerPC, for example, are 
becoming increasingly important!), then we need to reconsider shared 
very carefully.

The thing about (2) is that literally every operation on shared data has 
to be special-cased in the compiler. This adds a crazy amount of 
complexity, since there are basically two code paths for every single 
part of the code generation phase: the unshared path and the shared 
path. This is mostly caused by the fact that shared is transitive and 
can be applied to virtually any type. But even if we ignore that 
complexity, we have the problem of certain operations that cannot be 
atomic (even though they may look like it):

* Would you expect an array indexing operation (where the array slice is 
shared) to index the array atomically? Would you expect the read of the 
value at the calculated memory location to be atomic?
* Would you expect a slicing operation to be atomic? (Slicing something 
involves reading two words of memory which cannot be done atomically 
even on x86.)
* Would you expect 'in' to be atomic? (It can only really, kinda-sorta 
be if you use locks inside the AA implementation...)

etc.

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

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 6/6/12 8:32 PM, Alex Rønne Petersen wrote:
 On 07-06-2012 03:07, Andrei Alexandrescu wrote:
 On 6/6/12 6:01 PM, Alex Rønne Petersen wrote:
 (And of course, neither is actually implemented in any compiler, and I
 doubt they ever will be.)

 Why do you doubt shared semantics will be implemented?

 Andrei

 I think there are two fundamental issues making implementation difficult
 and unlikely to happen:

 1) The x86 bias (I replied to your other post wrt this).
 2) The overall complexity of generating correct code for shared.

 If we ignore the portability issues that I pointed out in my other
 reply, point (1) is irrelevant. I'm fairly certain the shared semantics
 that people expect can be implemented just fine at ISA level on x86
 without dirty hacks like locks. But if we do care about portability
 (which we ***really*** should - ARM and PowerPC, for example, are
 becoming increasingly important!), then we need to reconsider shared
 very carefully.

Agreed. I don't think (1) is irrelevant but I don't see it an impossible 
obstacle.

 The thing about (2) is that literally every operation on shared data has
 to be special-cased in the compiler.

Yes, like for volatile (no code motion etc) plus barriers.

 This adds a crazy amount of
 complexity, since there are basically two code paths for every single
 part of the code generation phase: the unshared path and the shared
 path. This is mostly caused by the fact that shared is transitive and
 can be applied to virtually any type. But even if we ignore that
 complexity, we have the problem of certain operations that cannot be
 atomic (even though they may look like it):

 * Would you expect an array indexing operation (where the array slice is
 shared) to index the array atomically? Would you expect the read of the
 value at the calculated memory location to be atomic?
 * Would you expect a slicing operation to be atomic? (Slicing something
 involves reading two words of memory which cannot be done atomically
 even on x86.)
 * Would you expect 'in' to be atomic? (It can only really, kinda-sorta
 be if you use locks inside the AA implementation...)

Operations with shared data are intentionally very limited. Indexing, 
slicing, and "in" should not compile for shared arrays and associative 
arrays.


Andrei

=?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <alex lycus.org> writes:

On 07-06-2012 04:00, Andrei Alexandrescu wrote:
 On 6/6/12 8:32 PM, Alex Rønne Petersen wrote:
 On 07-06-2012 03:07, Andrei Alexandrescu wrote:
 On 6/6/12 6:01 PM, Alex Rønne Petersen wrote:
 (And of course, neither is actually implemented in any compiler, and I
 doubt they ever will be.)

 Why do you doubt shared semantics will be implemented?

 Andrei

 I think there are two fundamental issues making implementation difficult
 and unlikely to happen:

 1) The x86 bias (I replied to your other post wrt this).
 2) The overall complexity of generating correct code for shared.

 If we ignore the portability issues that I pointed out in my other
 reply, point (1) is irrelevant. I'm fairly certain the shared semantics
 that people expect can be implemented just fine at ISA level on x86
 without dirty hacks like locks. But if we do care about portability
 (which we ***really*** should - ARM and PowerPC, for example, are
 becoming increasingly important!), then we need to reconsider shared
 very carefully.

 Agreed. I don't think (1) is irrelevant but I don't see it an impossible
 obstacle.

 The thing about (2) is that literally every operation on shared data has
 to be special-cased in the compiler.

 Yes, like for volatile (no code motion etc) plus barriers.

 This adds a crazy amount of
 complexity, since there are basically two code paths for every single
 part of the code generation phase: the unshared path and the shared
 path. This is mostly caused by the fact that shared is transitive and
 can be applied to virtually any type. But even if we ignore that
 complexity, we have the problem of certain operations that cannot be
 atomic (even though they may look like it):

 * Would you expect an array indexing operation (where the array slice is
 shared) to index the array atomically? Would you expect the read of the
 value at the calculated memory location to be atomic?
 * Would you expect a slicing operation to be atomic? (Slicing something
 involves reading two words of memory which cannot be done atomically
 even on x86.)
 * Would you expect 'in' to be atomic? (It can only really, kinda-sorta
 be if you use locks inside the AA implementation...)

 Operations with shared data are intentionally very limited. Indexing,
 slicing, and "in" should not compile for shared arrays and associative
 arrays.

Are you suggesting that we define shared such that any 'basic' operation 
that can't be atomic on the target architecture is disallowed? Or that 
we figure out the lowest common denominator and go with that?

 Andrei

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

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

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

=?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <alex lycus.org> writes:

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.

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

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.

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

"Mehrdad" <wfunction hotmail.com> writes:

Funny, I always imagined 'shared' was just a type constructor 
like 'const'... meant to help you check the correctness of your 
code.

Not that it would actually /do/ something for you at runtime...

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

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.

 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.

 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.


Andrei

=?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <alex lycus.org> writes:

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

Manu <turkeyman gmail.com> writes:

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

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

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

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

On Wed, 06 Jun 2012 19:01:59 -0400, Alex R=C3=B8nne 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) f=
or  =

no reason.

So since a PAS function cannot usefully be optimized (much better to wri=
te  =

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 f=
or  =

one thing!)

-Steve

Artur Skawina <art.08.09 gmail.com> writes:

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 

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

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

Artur Skawina <art.08.09 gmail.com> writes:

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

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

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

Artur Skawina <art.08.09 gmail.com> writes:

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

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

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

Artur Skawina <art.08.09 gmail.com> writes:

On 06/07/12 21:55, Steven Schveighoffer wrote:
 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. 

Actually, *value* return types shouldn't prevent the function from being pure.
But
there is not much point in returning them as shared, other than to avoid
explicit
casts, something that would better solved with some kind of 'unique' class.


 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.

We clearly agree completely; this is exactly what I'm saying in the paragraph
you
quoted below. What i'm *also* saying is that the 'incorrectness' of it is
harmless
in practice - so I'm not sure that it should be forbidden, and handled specially
(which would be necessary in the inferred-purity cases).


 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.

Having a type that allows operators that are either illegal or wrongly
implemented
is not a problem specific to pure functions. My argument is that 'shared int' as
a type is worthless and should never appear in real code. The 'Atomic!int'
example
was not made up - it is a real template used in my code that only allows legal
operations. That first 'inc' example would end up using

      pragma(attribute, always_inline) void opOpAssign(string op:"+")(size_t n)
{
         asm { "lock add"~opsuffix~" %1, %0 #ATOMIC_ADD" : "+m" data : "ir"
n*unitsize ; }
      }

and work correctly. I don't think it makes sense to worry about using built-in
types marked as shared directly, that is not likely to do the right thing; in
fact
using shared(T) should probably be forbidden for every T that can not guarantee
every operation on it to be correct and always safe.

(oh, and that opOpAssign is intentionally not marked as pure, but I should
probably
check what the compiler does; when i wrote it, I was assuming that the shared
'this',
shared 'data' and lack of outputs would make it do the right thing)


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

Exactly, see above. That's why you never access "raw" shared data - you always
wrap it.
("access" meaning read and/or write, passing refs around is fine)
Problem solved.


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

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

Are you saying that 

   auto f(T)(T v) { return v+v; } 

should be inferred as impure when used with a shared(T), but (weakly) pure
otherwise?

artur

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

On Thu, 07 Jun 2012 17:36:45 -0400, Artur Skawina <art.08.09 gmail.com>  
wrote:

 On 06/07/12 21:55, Steven Schveighoffer wrote:
 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.

 Actually, *value* return types shouldn't prevent the function from being  
 pure. But
 there is not much point in returning them as shared, other than to avoid  
 explicit
 casts, something that would better solved with some kind of 'unique'  
 class.

Right, what I meant was, returning a shared reference.  For example, if a  
pure function allocated memory and returned it as a shared pointer, that  
would make it non-optimizable pure (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.

 We clearly agree completely; this is exactly what I'm saying in the  
 paragraph you
 quoted below. What i'm *also* saying is that the 'incorrectness' of it  
 is harmless
 in practice - so I'm not sure that it should be forbidden, and handled  
 specially
 (which would be necessary in the inferred-purity cases).

I have given you an example of where it is harmful.  There is benefit in  
being able to say "since I marked this function pure, I know I don't have  
to deal with threading."  It allows you to eliminate possible  
multi-threading mistakes from whole swaths of code, especial generic code  
which accepts a myriad of types.

You know there are a ton of generic functions in phobos that don't check  
*at all* whether shared data is being given to them?  Simply marking them  
pure (which should be viable for most functions) would eliminate that  
worry.

 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.

 Having a type that allows operators that are either illegal or wrongly  
 implemented
 is not a problem specific to pure functions. My argument is that 'shared  
 int' as
 a type is worthless and should never appear in real code. The  
 'Atomic!int' example
 was not made up - it is a real template used in my code that only allows  
 legal
 operations. That first 'inc' example would end up using

       pragma(attribute, always_inline) void opOpAssign(string  
 op:"+")(size_t n) {
          asm { "lock add"~opsuffix~" %1, %0 #ATOMIC_ADD" : "+m" data :  
 "ir" n*unitsize ; }
       }

 and work correctly. I don't think it makes sense to worry about using  
 built-in
 types marked as shared directly, that is not likely to do the right  
 thing; in fact
 using shared(T) should probably be forbidden for every T that can not  
 guarantee
 every operation on it to be correct and always safe.

I would be in favor of that.  Right now the huge benefit of shared is what  
you can assume on stuff that's *not* marked as shared.  Using actual  
shared types is very cumbersome and difficult to understand.

Giving shared more useful and robust meaning would be a huge benefit.

 (oh, and that opOpAssign is intentionally not marked as pure, but I  
 should probably
 check what the compiler does; when i wrote it, I was assuming that the  
 shared 'this',
 shared 'data' and lack of outputs would make it do the right thing)

marking it as pure is like putting static on a class.  It will achieve  
nothing.

 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.

 Exactly, see above. That's why you never access "raw" shared data - you  
 always wrap it.
 ("access" meaning read and/or write, passing refs around is fine)
 Problem solved.

Let's not forget the main benefit of pure -- to allow optimization.   
Marking something as optimizable that *can never be* optimized or be a  
part of *any* optimizable function serves no purpose.

Let's not forget a secondary benefit of pure -- dispatchability (probably  
a better term for this).  If I know there's no shared data involved, I can  
dispatch a pure function to another worker thread without worry of races,  
especially a strong-pure function, but it's quite easy to prove validity  
for a weak-pure function.

If shared is involved, the second aspect goes out the window.

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

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

 Are you saying that

    auto f(T)(T v) { return v+v; }

 should be inferred as impure when used with a shared(T), but (weakly)  
 pure
 otherwise?

You are saying two different things here...
f's purity depends on the expression (v + v)'s purity.  And the level of  
purity (weak or strong) depends on the level of (v + v)'s purity.  IF v +  
v is strong-pure (such as int + int), then f is strong-pure.  If v + v is  
weak-pure, f is weak pure.  If v + v is not pure, then f is not pure.   
That is how it works today.

What I'm saying is, shared just shouldn't be allowed to be any part of  
pure.  So if T is defined as shared int, even though it actually makes no  
sense whatsoever for your example, f will be unpure.

That's another aspect of shared that needs to be addressed -- type  
inference for shared expressions.

for instance:

shared int x, y;

auto z = x + y;

What type should z be?  Right now it's shared, but that makes *no* sense,  
because z is not shared until you share it.  Why should auto opt-in to  
something it doesn't have to?

Likewise with IFTI, f(x) should probably equate to f!int(x) (in which case  
it *would* be pure)

-Steve

Artur Skawina <art.08.09 gmail.com> writes:

On 06/08/12 00:42, Steven Schveighoffer wrote:
 On Thu, 07 Jun 2012 17:36:45 -0400, Artur Skawina <art.08.09 gmail.com> wrote:
 
 On 06/07/12 21:55, Steven Schveighoffer wrote:
 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.

 Actually, *value* return types shouldn't prevent the function from being pure.
But
 there is not much point in returning them as shared, other than to avoid
explicit
 casts, something that would better solved with some kind of 'unique' class.

 
 Right, what I meant was, returning a shared reference.  For example, if a pure
function allocated memory and returned it as a shared pointer, that would make
it non-optimizable pure (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.

 We clearly agree completely; this is exactly what I'm saying in the paragraph
you
 quoted below. What i'm *also* saying is that the 'incorrectness' of it is
harmless
 in practice - so I'm not sure that it should be forbidden, and handled
specially
 (which would be necessary in the inferred-purity cases).

 
 I have given you an example of where it is harmful.  There is benefit in being
able to say "since I marked this function pure, I know I don't have to deal
with threading."  It allows you to eliminate possible multi-threading mistakes
from whole swaths of code, especial generic code which accepts a myriad of
types.
 
 You know there are a ton of generic functions in phobos that don't check *at
all* whether shared data is being given to them?  Simply marking them pure
(which should be viable for most functions) would eliminate that worry.

I can see certain generic functions being useful when working with shared data
too.
Yes, they can be used incorrectly, but I'd expect anybody working with shared to
know what they're doing. I see your point, but I'm not convinced that this
reason
alone is enough to also disallow legal uses (and, no, I don't think I've ever
used
'shared' in this way with phobos, nor can I think of "legal" examples right
now).


 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.

 Exactly, see above. That's why you never access "raw" shared data - you always
wrap it.
 ("access" meaning read and/or write, passing refs around is fine)
 Problem solved.

 
 Let's not forget the main benefit of pure -- to allow optimization.  Marking
something as optimizable that *can never be* optimized or be a part of *any*
optimizable function serves no purpose.

That's why I'm saying it's a NOOP. Forbidding it can avoid certain type of
bugs, yes, but I'd argue that the real cause of these bugs is accessing
shared data in unsafe ways at all - disallowing this /just/ in pure functions
does not seem like much of an improvement.


 Let's not forget a secondary benefit of pure -- dispatchability (probably a
better term for this).  If I know there's no shared data involved, I can
dispatch a pure function to another worker thread without worry of races,
especially a strong-pure function, but it's quite easy to prove validity for a
weak-pure function.
 
 If shared is involved, the second aspect goes out the window.

Hmm. Not necessarily, if shared is done right. But I don't think these types
of optimizations really work in practice, except when explicitly requested
(by annotating the code in some way, so that the compiler knows where
applying them makes sense).


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

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

 Are you saying that

    auto f(T)(T v) { return v+v; }

 should be inferred as impure when used with a shared(T), but (weakly) pure
 otherwise?

 
 You are saying two different things here...

I meant T to be a reference type, should have been more explicit about that,
sorry.

 f's purity depends on the expression (v + v)'s purity.  And the level of
purity (weak or strong) depends on the level of (v + v)'s purity.  IF v + v is
strong-pure (such as int + int), then f is strong-pure.  If v + v is weak-pure,
f is weak pure.  If v + v is not pure, then f is not pure.  That is how it
works today.
 
 What I'm saying is, shared just shouldn't be allowed to be any part of pure. 
So if T is defined as shared int, even though it actually makes no sense
whatsoever for your example, f will be unpure.

I agree, that is the sane approach. 

Well, at least with the current 'shared' definition, which implies C-style
'volatile' (which i think should be a separate attribute, there are cases 
where it's not necessary).
And a function with no refs in the signature should not be prevented from
being pure, except when it accesses global state, but that's obvious.


 That's another aspect of shared that needs to be addressed -- type inference
for shared expressions.
 
 for instance:
 
 shared int x, y;
 
 auto z = x + y;
 
 What type should z be?  Right now it's shared, but that makes *no* sense,
because z is not shared until you share it.  Why should auto opt-in to
something it doesn't have to?

Yep, but there is no good solutions to that right now. I know, "polysemous",
but that would *not* solve the problem, at least not w/o the type of 'z'
remaining in that state until it is actually used.
But now we're reinventing 'uniq' again. :)


 Likewise with IFTI, f(x) should probably equate to f!int(x) (in which case it
*would* be pure)

Hmm, shared(T) should never implicitly convert to (T), it *is* safe when
T==int, but the loss of type info could cause problems. If you meant f(z),
then yes that would work, but 'z' remaining in that polysemous state would
be even better.


Hmm, the remaining question seems to be whether

   auto f(T)(T v) pure { return v+v; }

should accept a "shared" T or not.

And I actually think that it shouldn't, for any reasonable interpretation
of function purity. Except D's "weak" purity combined with the ill-defined
shared semantics complicates things and makes the answer less obvious.
I'm starting to feel like I'm playing the devil's advocate here. :)


artur

dennis luehring <dl.soluz gmx.net> writes:

We clearly agree completely; this is exactly what I'm saying in the paragraph
you
quoted below. What i'm*also*  saying is that the 'incorrectness' of it is
harmless
in practice - so I'm not sure that it should be forbidden, and handled specially
(which would be necessary in the inferred-purity cases).





but it makes no sense to cripple an feature like pure half-way - pure is 
clean and well defined (still not perfect) - but you talking about 
making it very stupid and sensless "'incorrectness' of it is harmless
in practice" ... "Yes, they can be used incorrectly, but I'd expect 
anybody working with shared to know what they're doing" - no they don't 
- sorry, haven't you any real experience in the threading world or why 
don't you see the problems introdcing shared in pure

=?ISO-8859-15?Q?Alex_R=F8nne_Petersen?= <alex lycus.org> writes:

On 08-06-2012 09:00, dennis luehring wrote:
We clearly agree completely; this is exactly what I'm saying in


 the paragraph you
quoted below. What i'm*also* saying is that the 'incorrectness' of


 it is harmless
in practice - so I'm not sure that it should be forbidden, and


 handled specially
(which would be necessary in the inferred-purity cases).





 but it makes no sense to cripple an feature like pure half-way - pure is
 clean and well defined (still not perfect) - but you talking about
 making it very stupid and sensless "'incorrectness' of it is harmless
 in practice" ... "Yes, they can be used incorrectly, but I'd expect
 anybody working with shared to know what they're doing" - no they don't
 - sorry, haven't you any real experience in the threading world or why
 don't you see the problems introdcing shared in pure

Without taking either side, I'm just gonna point out that this post is 
very incomprehensible and doesn't seem to bring any actual argument to 
the table.

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

Artur Skawina <art.08.09 gmail.com> writes:

On 06/08/12 09:00, dennis luehring wrote:
We clearly agree completely; this is exactly what I'm saying in the paragraph
you
quoted below. What i'm*also*  saying is that the 'incorrectness' of it is
harmless
in practice - so I'm not sure that it should be forbidden, and handled specially
(which would be necessary in the inferred-purity cases).





 
 but it makes no sense to cripple an feature like pure half-way - pure is clean
and well defined (still not perfect) - but you talking about making it very
stupid and sensless "'incorrectness' of it is harmless
 in practice" ...

Marking a function that takes a pointer or reference which is not immutable
does *not*
make it pure, it only allows it to be called from another pure function, that's
all.
That's how D implements purity - if you think that's wrong and/or misleading, I
agree,
but that's how it is.
'int f(shared T*)' can be tagged as pure, but can *never* actually be pure,
because its
caller can never be pure. That's why allowing it to be "pure" is harmless, even
if it
looks "incorrect" to have pure functions dealing with shared. It's a
consequence of D's
current purity model, and, yes, it is confusing.

 "Yes, they can be used incorrectly, but I'd expect anybody working with shared
to know what they're doing" - no they don't - sorry, haven't you any real
experience in the threading world or why don't you see the problems introdcing
shared in pure

The only way to (relatively) safely deal with raw (ie builtin) shared types it
to
treat 'shared' as the D equivalent of C's 'volatile'. Anything else won't
correctly,
and, no, it can't be made to work, attempting that would make 'shared' even less
useful.

Shared data in pure code makes no sense, yes. D's "pure" is not the same as
sanely
defined "pure", however.

artur

"Jonathan M Davis" <jmdavisProg gmx.com> writes:

On Thursday, June 07, 2012 10:43:04 Steven Schveighoffer wrote:
 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!)

But what does it matter if a PAS function can be called from a strongly pure 
function? If it can't be called from a strongly pure function anyway, then you 
don't have to worry about shared being used in a strongly pure function 
regardless of whether pure is permitted in weakly pure functions.

However, if shared is banned from pure functions, then you can't mark any 
function which would otherwise be pure as pure. As it stands, you can have

auto func(T)(T stuff) pure {}

where if you pass it non-shared, it can be used in a strongly pure function 
with all of its benefits, _and_ you can call it with shared (in which case, it 
can't be called in a strongly pure function, but that doesn't mean that 
function isn't useful). If shared were not permitted in pure functions, then 
you'd have to do

auto func(T)(T stuff) {}

in which case, func could be used with impure, non-shared stuff, which the 
previous signature prevented. To avoid that, you have to duplicate the 
function - one version for shared and one without.

In addition, if you have a PAS function, it has the guarantee that it won't 
access anything mutable that wasn't passed to it. If you make PAS illegal, 
then there is _no_ way to have that guarantee for shared.

I don't see how allowing shared in pure functions costs us _anything_. No, 
such a function can't be used in a strongly pure function, but you still have 
the guarantee about mutable globals (which is definitely worth something), and 
you avoid having to duplicate the function for shared vs non-shared. And since 
it _can't_ be called from a strongly pure function, you don't have to worry 
about the fact that multiple calls to such a function can result in different 
return values due to another thread altering the variable.

As far as I can tell, making PAS functions illegal just makes life harder and 
buys us nothing. Strongly pure is where the optimization benefits of shared 
are, and PAS functions don't prevent that at all - they just can't gain from 
it.

It seems like your issue with PAS stems primarily from the idea that such a 
weakly pure function can't be called from a strongly pure function, and I 
don't see why that's really a problem - particularly given that that's not 
pure's only benefit and is arguably the _smaller_ of its benefits given how 
rarely it can actually be applied.

- Jonathan M Davis