www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Passing an in parameter and aliasing

reply renoX <renosky free.fr> writes:
I'm not sure whether to post this in D.learn or not, but here's my issue:

What happens when you have a function f(in T array[], inout T x)
and that x is in fact an element of the array?

AFAIK, there are three possibilities:
1- the compiler detect the incompatibility and complain, that's nice for 
the programmer but real hard work for the compiler and it's impossible 
to catch all the problems for the compiler.

2- the array is modified when x is modified, which can leads to bug 
depending on the compiler and its optimization level: hopefully this 
would be a rare bug, but very hard to catch.
And if parameter passing is by default as constants, then maybe the bug 
won't be so rare.

3- the array is copied which reduce performance is this is done by default.

So which way is-it supposed to be?

Regards,
renoX
May 23 2007
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"renoX" <renosky free.fr> wrote in message 
news:f328ns$1f1q$1 digitalmars.com...

 I'm not sure whether to post this in D.learn or not, but here's my issue:

 What happens when you have a function f(in T array[], inout T x)
 and that x is in fact an element of the array?

 AFAIK, there are three possibilities:
 1- the compiler detect the incompatibility and complain, that's nice for 
 the programmer but real hard work for the compiler and it's impossible to 
 catch all the problems for the compiler.

 2- the array is modified when x is modified, which can leads to bug 
 depending on the compiler and its optimization level: hopefully this would 
 be a rare bug, but very hard to catch.
 And if parameter passing is by default as constants, then maybe the bug 
 won't be so rare.

 3- the array is copied which reduce performance is this is done by 
 default.

 So which way is-it supposed to be?


It works like 2 right now.  3 is just impractical for most cases.  1 can be 
put in manually:

void func(int[] a, ref int x)
in
{
    assert(&x < a.ptr || &x >= (a.ptr + a.length), "x can't be a member of 
a");
}
body
{
    x = 5;
    writefln(a);
    fflush(stdout); // without this, the assertion confusingly gets printed 
first
}

void main()
{
    int[] a = ([1, 2, 3]).dup;
    int x = 0;

    func(a, x);
    func(a, a[0]);
}

You could probably wrap that ugly expression into a mixin or something.
May 23 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Jarrett Billingsley wrote:

 "renoX" <renosky free.fr> wrote in message 
 news:f328ns$1f1q$1 digitalmars.com...

 I'm not sure whether to post this in D.learn or not, but here's my issue:

 What happens when you have a function f(in T array[], inout T x)
 and that x is in fact an element of the array?

 AFAIK, there are three possibilities:
 1- the compiler detect the incompatibility and complain, that's nice for 
 the programmer but real hard work for the compiler and it's impossible to 
 catch all the problems for the compiler.

 2- the array is modified when x is modified, which can leads to bug 
 depending on the compiler and its optimization level: hopefully this would 
 be a rare bug, but very hard to catch.
 And if parameter passing is by default as constants, then maybe the bug 
 won't be so rare.

 3- the array is copied which reduce performance is this is done by 
 default.

 So which way is-it supposed to be?


 
 It works like 2 right now.  3 is just impractical for most cases.  1 can be 
 put in manually:
 
 void func(int[] a, ref int x)
 in
 {
     assert(&x < a.ptr || &x >= (a.ptr + a.length), "x can't be a member of 
 a");
 }


The thing with this is it may catch the error but it doesn't help the 
compiler generate more optimized code.  The C99 'restrict' keyword does, 
though.  I suppose the compiler could be smart enough to deduce 
'restrict' semantics are in effect from the assert message above.  That 
would be pretty neat.

Linky (top google hit for 'C99 restrict keyword'): 
http://www.cellperformance.com/mike_acton/2006/05/demystifying_the_restrict_keyw.html


--bb
May 23 2007
parent reply renoX <renosky free.fr> writes:
Bill Baxter a écrit :

 Jarrett Billingsley wrote:

 "renoX" <renosky free.fr> wrote in message 
 news:f328ns$1f1q$1 digitalmars.com...

 I'm not sure whether to post this in D.learn or not, but here's my 
 issue:

 What happens when you have a function f(in T array[], inout T x)
 and that x is in fact an element of the array?

 AFAIK, there are three possibilities:
 1- the compiler detect the incompatibility and complain, that's nice 
 for the programmer but real hard work for the compiler and it's 
 impossible to catch all the problems for the compiler.

 2- the array is modified when x is modified, which can leads to bug 
 depending on the compiler and its optimization level: hopefully this 
 would be a rare bug, but very hard to catch.
 And if parameter passing is by default as constants, then maybe the 
 bug won't be so rare.

 3- the array is copied which reduce performance is this is done by 
 default.

 So which way is-it supposed to be?


 It works like 2 right now.  3 is just impractical for most cases.  1 
 can be put in manually:

 void func(int[] a, ref int x)
 in
 {
     assert(&x < a.ptr || &x >= (a.ptr + a.length), "x can't be a 
 member of a");
 }


 
 The thing with this is it may catch the error but it doesn't help the 
 compiler generate more optimized code.  The C99 'restrict' keyword does, 
 though.  I suppose the compiler could be smart enough to deduce 
 'restrict' semantics are in effect from the assert message above.  That 
 would be pretty neat.


Well, if I understood correctly Jarrett Billingsley's answer, the 
semantic on 'in' is the same as 'restrict': the fastest as the compiler 
will be free to optimize but the most fragile from programmers point of 
view because if you violate the restrict restriction the result is 
unpredictable (no bug, a bug depending on optimization flags, fun!)

Sure, it'd be nice if the compiler was able to do this kind of 
optimization without the in|restrict hint but this is hard.

renoX
May 25 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
renoX wrote:

 Bill Baxter a écrit :



 The thing with this is it may catch the error but it doesn't help the 
 compiler generate more optimized code.  The C99 'restrict' keyword 
 does, though.  I suppose the compiler could be smart enough to deduce 
 'restrict' semantics are in effect from the assert message above.  
 That would be pretty neat.


 
 Well, if I understood correctly Jarrett Billingsley's answer, the 
 semantic on 'in' is the same as 'restrict': the fastest as the compiler 
 will be free to optimize but the most fragile from programmers point of 
 view because if you violate the restrict restriction the result is 
 unpredictable (no bug, a bug depending on optimization flags, fun!)
 
 Sure, it'd be nice if the compiler was able to do this kind of 
 optimization without the in|restrict hint but this is hard.


The 'in' parameter type does nothing currently.  Leaving it off is the 
same as putting it in.  So I don't believe it acts like 'restrict'.  I 
certainly don't remember reading anywhere in the spec that D assumes all 
'in' array parameters are unaliased.  That would be a big break from 
C/C++ if it were so, so I think the spec would go out of its way to 
point out the difference.

--bb
May 25 2007
parent reply Dave <Dave_member pathlink.com> writes:
Bill Baxter wrote:

 renoX wrote:

 Bill Baxter a écrit :


 

 The thing with this is it may catch the error but it doesn't help the 
 compiler generate more optimized code.  The C99 'restrict' keyword 
 does, though.  I suppose the compiler could be smart enough to deduce 
 'restrict' semantics are in effect from the assert message above.  
 That would be pretty neat.


 Well, if I understood correctly Jarrett Billingsley's answer, the 
 semantic on 'in' is the same as 'restrict': the fastest as the 
 compiler will be free to optimize but the most fragile from 
 programmers point of view because if you violate the restrict 
 restriction the result is unpredictable (no bug, a bug depending on 
 optimization flags, fun!)

 Sure, it'd be nice if the compiler was able to do this kind of 
 optimization without the in|restrict hint but this is hard.


 
 The 'in' parameter type does nothing currently.  Leaving it off is the 
 same as putting it in.  So I don't believe it acts like 'restrict'.  I 


That's right (verifiable through the asm).


 certainly don't remember reading anywhere in the spec that D assumes all 
 'in' array parameters are unaliased.  That would be a big break from 
 C/C++ if it were so, so I think the spec would go out of its way to 
 point out the difference.
 


I believe that's part of the overall justification for the new for 2.0 'in',
which will mean 'scope 
const final' for any type of reference parameter (correct me if I'm wrong
Walter). Then the 
optimizer will be free to do its thing with those references, w/o any
complicated pointer analysis 
or runtime checking.

IIUC, the compiler front-end will do it's best to enforce it (unlike C's
'restrict') and I believe 
it won't be as easy to cast away like C++'s 'const&'.

If so that'd be pretty cool, because it would make D competitive with Fortran
in this regard.

Toward the end of the thread on this over in d.D.announce, it looks like 'in'
will be the default 
parameter (so 'foo(int[] array){}' would be the same as 'foo(in int[]
array){}'). I'm hoping that's 
the case -- at least given a try first for 2.0 anyway.


 --bb
May 25 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Dave wrote:

 Bill Baxter wrote:

 renoX wrote:

 Bill Baxter a écrit :



 The thing with this is it may catch the error but it doesn't help 
 the compiler generate more optimized code.  The C99 'restrict' 
 keyword does, though.  I suppose the compiler could be smart enough 
 to deduce 'restrict' semantics are in effect from the assert message 
 above.  That would be pretty neat.


 Well, if I understood correctly Jarrett Billingsley's answer, the 
 semantic on 'in' is the same as 'restrict': the fastest as the 
 compiler will be free to optimize but the most fragile from 
 programmers point of view because if you violate the restrict 
 restriction the result is unpredictable (no bug, a bug depending on 
 optimization flags, fun!)

 Sure, it'd be nice if the compiler was able to do this kind of 
 optimization without the in|restrict hint but this is hard.


 The 'in' parameter type does nothing currently.  Leaving it off is the 
 same as putting it in.  So I don't believe it acts like 'restrict'.  I 


 
 That's right (verifiable through the asm).
 

 certainly don't remember reading anywhere in the spec that D assumes 
 all 'in' array parameters are unaliased.  That would be a big break 
 from C/C++ if it were so, so I think the spec would go out of its way 
 to point out the difference.


 
 I believe that's part of the overall justification for the new for 2.0 
 'in', which will mean 'scope const final' for any type of reference 
 parameter (correct me if I'm wrong Walter). Then the optimizer will be 
 free to do its thing with those references, w/o any complicated pointer 
 analysis or runtime checking.
 
 IIUC, the compiler front-end will do it's best to enforce it (unlike C's 
 'restrict') and I believe it won't be as easy to cast away like C++'s 
 'const&'.
 
 If so that'd be pretty cool, because it would make D competitive with 
 Fortran in this regard.


I don't think Walter has said that 'in' as 'scope const final' is going 
to imply no aliasing.  I think it's kind of an orthogonal concern.

Say you have a vector difference function:

     void sub(mutable float[] ret, in float[] a, in float[] b) {
         for(size_t i=1; i<ret.length; i++) {
            ret[i] = a[i] - b[i];
         }
     }

Should you expect this to fail?
     float[10] c;
     for(i=0; i<=10; i++) c[i]=i;
     sub(c[0..9],c[1..$],c[0..9]);

Looking at the loop it should be fine.  It should calc
         c[0] = c[1] - c[0];
         c[1] = c[2] - c[1];
         c[2] = c[3] - c[2];
         ...
and leave you with c[0..9] containing all 1's.
But a smarty pants compiler might decide for some reason that it's 
faster to rewrite the loop as:
        memcpy(ret,a,float.sizeof*a.length);
        for (i=0;i<N;i++) { ret[i] -= b[i]; }

That's a fine transformation if b and ret are distinct.  But it isn't 
fine when b and ret are aliased.

That's the reason why C doesn't have restrict as default. The thinking 
is that whatever the compiler does under the hood, the result should be 
output that looks exactly like if you really did run the C code on a C 
virtual machine in the exact order written.  Even if users get tricky 
with inputs and do things that are guaranteed to give incorrect results, 
it should still give the "exact" incorrect result.  It really is a 
separate issue from whether the parameter can be modified or not.

That's C's philosophy anyway.  And I haven't heard anything from Walter 
that sounded to me like D was taking a different approach.  I think a 
'restrict' type keyword probably is the best way to handle it in a 
C-like language.  Most code doesn't need the performance boost as much 
as it needs predictability and reliability.  Aliasing bugs can also be 
very tricky to debug because things might work great on your computer 
but only fail on some other machine when compiled with SSE3 instructions 
and -03 optimizations.  So it makes sense for performance critical code 
to declare in a visible way that it's placing some restrictions on the 
kind of inputs that will work.

So I think D could still use a separate restrict-like keyword.  But I 
think it could be made a little more user friendly than C's by allowing 
it to apply to a whole function rather than having to say 'restrict' 
'restrict' 'restrict' for every single parameter.

--bb
May 25 2007
next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Bill Baxter skrev:

 Dave wrote:

 [restrict]


 That's C's philosophy anyway.  And I haven't heard anything from Walter 
 that sounded to me like D was taking a different approach.  I think a 
 'restrict' type keyword probably is the best way to handle it in a 
 C-like language.  Most code doesn't need the performance boost as much 
 as it needs predictability and reliability.  Aliasing bugs can also be 
 very tricky to debug because things might work great on your computer 
 but only fail on some other machine when compiled with SSE3 instructions 
 and -03 optimizations.  So it makes sense for performance critical code 
 to declare in a visible way that it's placing some restrictions on the 
 kind of inputs that will work.
 
 So I think D could still use a separate restrict-like keyword.  But I 
 think it could be made a little more user friendly than C's by allowing 
 it to apply to a whole function rather than having to say 'restrict' 
 'restrict' 'restrict' for every single parameter.


Here is an old thread about "noalias, restrict, and Fortran optimizations":

http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=D&artnum=28215&header

/Oskar
May 26 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Oskar Linde wrote:

 Bill Baxter skrev:

 Dave wrote:

 [restrict]


 That's C's philosophy anyway.  And I haven't heard anything from 
 Walter that sounded to me like D was taking a different approach.  I 
 think a 'restrict' type keyword probably is the best way to handle it 
 in a C-like language.  Most code doesn't need the performance boost as 
 much as it needs predictability and reliability.  Aliasing bugs can 
 also be very tricky to debug because things might work great on your 
 computer but only fail on some other machine when compiled with SSE3 
 instructions and -03 optimizations.  So it makes sense for performance 
 critical code to declare in a visible way that it's placing some 
 restrictions on the kind of inputs that will work.

 So I think D could still use a separate restrict-like keyword.  But I 
 think it could be made a little more user friendly than C's by 
 allowing it to apply to a whole function rather than having to say 
 'restrict' 'restrict' 'restrict' for every single parameter.


 
 Here is an old thread about "noalias, restrict, and Fortran optimizations":
 
 http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=D
artnum=28215&header 


Thanks for that.  Here's a few follow-up posts I found ... that news 
interfaces doesn't seem to have a "threaded" view, so finding the rest 
of the thread isn't easy.

http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=D&artnum=28236
http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=D&artnum=28372
http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=D&artnum=28377
http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=D&artnum=28379

Last thing I see from Walter is musing about making everything noalias 
with a way to turn that off.  My problem with that is most code doesn't 
need it, and it would be confusing for users not expecting it to find 
out that a[i] = b[i] - c[i]; doesn't always execute exactly as 
a[i]=b[i]-c[i].    Walter's right that the vast majority of code doesn't 
rely on C-like non-restrict behavior.  But I'd counter that the vast 
majority of code also doesn't need it.  Better to put something 
potentially dangerous as an option usable by people who know what 
they're doing rather than making it the default.

Anyway, generating optimized code is probably at least 2 years away from 
being anywhere near a priority for Walter.  :-)  [he says hoping he 
turns out to be wrong]

--bb
May 26 2007
prev sibling next sibling parent renoX <renosky free.fr> writes:
Thinking about it, you're right, but the hard thing is as always when 
you have func(in int[]array, int* p) that the programmer must not assume 
that array is unchanged because of the 'in' mode, it can be modified by 
the pointer reference (to prevent this the variable declaration must be 
change, the function parameter passing is not enough).

int f[1];
int* p=&f[0];
func(f,p)

func(in int[]array, int* p)
{
	*p = 1;
	/* here array[0] is 1 not 0 in this case */
}


renoX
PS: I couldn't read the thread linked by oskar linde as the web 
interface doesn't thread correctly the posts.
May 26 2007
prev sibling parent Dave <Dave_member pathlink.com> writes:
Bill Baxter wrote:

 Dave wrote:

 Bill Baxter wrote:

 renoX wrote:

 Bill Baxter a écrit :



 The thing with this is it may catch the error but it doesn't help 
 the compiler generate more optimized code.  The C99 'restrict' 
 keyword does, though.  I suppose the compiler could be smart enough 
 to deduce 'restrict' semantics are in effect from the assert 
 message above.  That would be pretty neat.


 Well, if I understood correctly Jarrett Billingsley's answer, the 
 semantic on 'in' is the same as 'restrict': the fastest as the 
 compiler will be free to optimize but the most fragile from 
 programmers point of view because if you violate the restrict 
 restriction the result is unpredictable (no bug, a bug depending on 
 optimization flags, fun!)

 Sure, it'd be nice if the compiler was able to do this kind of 
 optimization without the in|restrict hint but this is hard.


 The 'in' parameter type does nothing currently.  Leaving it off is 
 the same as putting it in.  So I don't believe it acts like 
 'restrict'.  I 


 That's right (verifiable through the asm).


 certainly don't remember reading anywhere in the spec that D assumes 
 all 'in' array parameters are unaliased.  That would be a big break 
 from C/C++ if it were so, so I think the spec would go out of its way 
 to point out the difference.


 I believe that's part of the overall justification for the new for 2.0 
 'in', which will mean 'scope const final' for any type of reference 
 parameter (correct me if I'm wrong Walter). Then the optimizer will be 
 free to do its thing with those references, w/o any complicated 
 pointer analysis or runtime checking.

 IIUC, the compiler front-end will do it's best to enforce it (unlike 
 C's 'restrict') and I believe it won't be as easy to cast away like 
 C++'s 'const&'.

 If so that'd be pretty cool, because it would make D competitive with 
 Fortran in this regard.


 
 I don't think Walter has said that 'in' as 'scope const final' is going 
 to imply no aliasing.  I think it's kind of an orthogonal concern.
 


I haven't seen any direct mention of it by Walter either. But whether or not
it's orthogonal may 
depend on what he meant by "const - the function will not attempt to change the
contents of what is 
referred to" in his post over in d.D.announce.

 From Walter's original post, the description for "const" can be taken in
either way as I read it. 
The most strict interpretation being "It is an error for the function to change
the contents of a 
reference passed via 'in'" (which would mean 'in' is also like C's 'restrict'
to a function consumer).

I think the usage of the example you gave is pretty rare but agree it may
occasionally lead to hard 
to find bugs if the function developer doesn't check for overlap or make all of
the parameters 
'mutable' (one of which they should if 'in' also implies 'restrict').

But programmer expectations (i.e.: knowing that a bug could be caused by mixing
mutable and const 
parameters in D [like your example]) could mitigate that problem quite a bit by
making that type of 
bug less likely and time consuming to find, because they would know where to
look and what to avoid 
as long as 'in' is documented well.

- Dave


 Say you have a vector difference function:
 
     void sub(mutable float[] ret, in float[] a, in float[] b) {
         for(size_t i=1; i<ret.length; i++) {
            ret[i] = a[i] - b[i];
         }
     }
 
 Should you expect this to fail?
     float[10] c;
     for(i=0; i<=10; i++) c[i]=i;
     sub(c[0..9],c[1..$],c[0..9]);
 
 Looking at the loop it should be fine.  It should calc
         c[0] = c[1] - c[0];
         c[1] = c[2] - c[1];
         c[2] = c[3] - c[2];
         ...
 and leave you with c[0..9] containing all 1's.
 But a smarty pants compiler might decide for some reason that it's 
 faster to rewrite the loop as:
        memcpy(ret,a,float.sizeof*a.length);
        for (i=0;i<N;i++) { ret[i] -= b[i]; }
 
 That's a fine transformation if b and ret are distinct.  But it isn't 
 fine when b and ret are aliased.
 
 That's the reason why C doesn't have restrict as default. The thinking 
 is that whatever the compiler does under the hood, the result should be 
 output that looks exactly like if you really did run the C code on a C 
 virtual machine in the exact order written.  Even if users get tricky 
 with inputs and do things that are guaranteed to give incorrect results, 
 it should still give the "exact" incorrect result.  It really is a 
 separate issue from whether the parameter can be modified or not.
 
 That's C's philosophy anyway.  And I haven't heard anything from Walter 
 that sounded to me like D was taking a different approach.  I think a 
 'restrict' type keyword probably is the best way to handle it in a 
 C-like language.  Most code doesn't need the performance boost as much 
 as it needs predictability and reliability.  Aliasing bugs can also be 
 very tricky to debug because things might work great on your computer 
 but only fail on some other machine when compiled with SSE3 instructions 
 and -03 optimizations.  So it makes sense for performance critical code 
 to declare in a visible way that it's placing some restrictions on the 
 kind of inputs that will work.
 
 So I think D could still use a separate restrict-like keyword.  But I 
 think it could be made a little more user friendly than C's by allowing 
 it to apply to a whole function rather than having to say 'restrict' 
 'restrict' 'restrict' for every single parameter.
 
 --bb
May 26 2007