www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - C `restrict` keyword in D

reply Uknown <sireeshkodali1 gmail.com> writes:
In C, the `restrict` keyword implies that 2 or more pointer 
arguments in a function call do not point to the same data. This 
allows for some additional optimizations which were not possible 
before, finally making C as fast as Fortran.
e.g.
This is the new definition for memcpy in C99
void* memcpy(void *restrict dst, const void *restrict src, size_t 
n);

`dst` and `src` should never point to the same block of memory, 
and this is enforced by the programmer.

In D, it makes sense to add a similar functionality, that extends 
beyond just performance optimizations. It could potentially be 
used to better guarantee  safety of some code.
e.g. (from discussions about ref counting in D) :
void main()  safe
{
     auto arr = RCArray!int([0]);
     foo(arr, arr[0]);
}

void foo(ref RCArray!int arr, ref int val)  safe
{
     {
	auto copy = arr; //arr's (and copy's) reference counts are both 2
	arr = RCArray!int([]); // There is another owner, so arr
			       // forgets about the old payload
     } // Last owner of the array ('copy') gets destroyed and 
happily
       // frees the payload.
     val = 3; // Oops.
}

Here, adding `restrict` to foo's parameters like so :

void foo(restrict ref RCArray!int arr, restrict ref int val)

would make the compiler statically enforce the fact that neither 
references are pointing to the same data. This would cause an 
error in main, since arr[0] is from the same block of memory as 
arr.
The same would apply for pointers.

I just hope to have a nice discussion on this topic here.

Thanks!

Read more about `restrict` here : 
http://en.cppreference.com/w/c/language/restrict
Sep 02
next sibling parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 [...]

 void foo(ref RCArray!int arr, ref int val)  safe
 {
     {
 	auto copy = arr; //arr's (and copy's) reference counts are 
 both 2
 	arr = RCArray!int([]); // There is another owner, so arr
 			       // forgets about the old payload
     } // Last owner of the array ('copy') gets destroyed and 
 happily
       // frees the payload.
     val = 3; // Oops.
 }

 Here, adding `restrict` to foo's parameters like so :

 void foo(restrict ref RCArray!int arr, restrict ref int val)

 would make the compiler statically enforce the fact that 
 neither references are pointing to the same data. This would 
 cause an error in main, since arr[0] is from the same block of 
 memory as arr.
How does the compiler know which member of RCArray!int to check for pointing to the same memory chunk as val?
Sep 02
parent reply Uknown <sireeshkodali1 gmail.com> writes:
On Sunday, 3 September 2017 at 03:49:21 UTC, Moritz Maxeiner 
wrote:
 On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 [...]

 void foo(ref RCArray!int arr, ref int val)  safe
 {
     {
 	auto copy = arr; //arr's (and copy's) reference counts are 
 both 2
 	arr = RCArray!int([]); // There is another owner, so arr
 			       // forgets about the old payload
     } // Last owner of the array ('copy') gets destroyed and 
 happily
       // frees the payload.
     val = 3; // Oops.
 }

 Here, adding `restrict` to foo's parameters like so :

 void foo(restrict ref RCArray!int arr, restrict ref int val)

 would make the compiler statically enforce the fact that 
 neither references are pointing to the same data. This would 
 cause an error in main, since arr[0] is from the same block of 
 memory as arr.
How does the compiler know which member of RCArray!int to check for pointing to the same memory chunk as val?
If I understand C's version of restrict correctly, the pointers must not refer to the same block. So extending the same here, val should not be allowed to be a reference to any members of RCArray!int. This does seem to get get more confusing when the heap is involved as a member of a struct. e.g. void main() safe { struct HeapAsMember { int* _someArr; } HeapAsMember x; x._someArr = new int; void foo(restrict ref HeapAsMember x, restrict ref int val) safe { x._someArr = new int; val = 0; } foo(x, x._someArr[0]); } I feel that in this case, the compiler should throw an error, since val would be a reference to a member pointed to by _someArr, which is a member of x. Although, I wonder if such analysis would be feasible? This case is trivial, but there could be more complicated cases.
Sep 02
parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Sunday, 3 September 2017 at 06:11:10 UTC, Uknown wrote:
 On Sunday, 3 September 2017 at 03:49:21 UTC, Moritz Maxeiner 
 wrote:
 On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 [...]

 void foo(ref RCArray!int arr, ref int val)  safe
 {
     {
 	auto copy = arr; //arr's (and copy's) reference counts are 
 both 2
 	arr = RCArray!int([]); // There is another owner, so arr
 			       // forgets about the old payload
     } // Last owner of the array ('copy') gets destroyed and 
 happily
       // frees the payload.
     val = 3; // Oops.
 }

 Here, adding `restrict` to foo's parameters like so :

 void foo(restrict ref RCArray!int arr, restrict ref int val)

 would make the compiler statically enforce the fact that 
 neither references are pointing to the same data. This would 
 cause an error in main, since arr[0] is from the same block 
 of memory as arr.
How does the compiler know which member of RCArray!int to check for pointing to the same memory chunk as val?
If I understand C's version of restrict correctly, the pointers must not refer to the same block. So extending the same here, val should not be allowed to be a reference to any members of RCArray!int.
AFAICT that's not what's needed here for safety, though: RCArray will have a member (`data`, `store`, or something like that) pointing to the actual elements (usually on the heap). You essentially want `val` not to point into the same memory chunk as `data` points into, which is different from `val` not to point to a member of RCArray.
 This does seem to get get more confusing when the heap is 
 involved as a member of a struct.
 e.g.
 [...]
Right, that's essentially what an RCArray does, as well.
 I feel that in this case, the compiler should throw an error, 
 since val would be a reference to a member pointed to by 
 _someArr, which is a member of x. Although, I wonder if such 
 analysis would be feasible? This case is trivial, but there 
 could be more complicated cases.
The main issue I see is that pointers/references can change at runtime, so I don't think a static analysis in the compiler can cover this in general (which, I think, is also why the C99 keyword is an optimization hint only).
Sep 03
parent reply Uknown <sireeshkodali1 gmail.com> writes:
On Sunday, 3 September 2017 at 12:59:25 UTC, Moritz Maxeiner 
wrote:
 [...]
 The main issue I see is that pointers/references can change at 
 runtime, so I don't think a static analysis in the compiler can 
 cover this in general (which, I think, is also why the C99 
 keyword is an optimization hint only).
Well, I thought about it, I have to agree with you, as far as pointers go. There seems to be no simple way in which the compiler can safely ensure that the two restrict pointers point to the same data. But fir references, it seems trivial. In order to do so, RCArray would have to first annotate it's opIndex, opSlice and any other data returning member functions with the restrict keyword. e.g. struct RCArray(T) safe { private T[] _payload; /+some other functions needed to implement RCArray correctly+/ restrict ref T opIndex(size_t i) { //implimentation as usual return _payload[i]; } restrict ref T opIndex() { return _payload; } //opSlice and the rest defined similary } void main() safe { RCArray!int my_array; ... auto t = my_array[0];//error: my_array.opIndex(0) is defined as restrict //This essentialy prevents a second reference from existing in the same scope foo(arr, arr[0]); //error: call to foo introduces `restrict` data from the same container //into the scope of foo } void foo(ref RCArray!int arr, ref int val) safe { { auto copy = arr; //arr's (and copy's) reference counts are both 2 arr = RCArray!int([]); // There is another owner, so arr // forgets about the old payload } // Last owner of the array ('copy') gets destroyed and happily // frees the payload. val = 3;//No longer an issue! } This is now no longer like the C99 keyword in behaviour, but on the bright side, with one annotation to the return types, RCArray suddenly doesn't need to worry about escaped references. Also, no modifications would be needed to the foo function. This is potentially useful for other owning container types. The compiler could still use the information gainer from the restrict annotation for optimizations, although such optimizations would be much less aggressive than in C. Coming back to pointers, the only way I can see (short of bringing Rust's borrow checker to D) is to add additional annotations to function return values. The problem comes with code like this : int * foo() safe { static int[1] data; return &data[0]; } void main() { int * restrict p1 = foo(); int * restrict p2 = foo();//Should be error, but the compiler can't figure //this out without further annotations }
Sep 03
parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Sunday, 3 September 2017 at 15:39:58 UTC, Uknown wrote:
 On Sunday, 3 September 2017 at 12:59:25 UTC, Moritz Maxeiner 
 wrote:
 [...]
 The main issue I see is that pointers/references can change at 
 runtime, so I don't think a static analysis in the compiler 
 can cover this in general (which, I think, is also why the C99 
 keyword is an optimization hint only).
Well, I thought about it, I have to agree with you, as far as pointers go. There seems to be no simple way in which the compiler can safely ensure that the two restrict pointers point to the same data. But fir references, it seems trivial.
References are just non-null syntax for pointers that take addresses implicitly on function call. Issues not related to null that pertain to pointers translate to references, as any (non-null) pointer can be turned into a reference (and vice versa): --- void foo(int* a, bool b) { if (b) bar(a); else baz(*a); } void bar(int* a) {} void baz(ref int a) { bar(&a); } ---
 In order to do so, RCArray would have to first annotate it's 
 opIndex, opSlice and any other data returning member functions 
 with the restrict keyword. e.g.
 struct RCArray(T)  safe
 {
 	private T[] _payload;
 	/+some other functions needed to implement RCArray correctly+/
 	restrict ref T opIndex(size_t i) {
 		//implimentation as usual
 		return _payload[i];
 	}
 	restrict ref T opIndex() {
 		return _payload;
 	}
 	//opSlice and the rest defined similary
 }
 [...]
Note: There's no need to attribute the RCArray template as safe (other than for debugging when developing the template). The compiler will derive it for each member if they are indeed safe. W.r.t. the rest: I don't think treating references as different from pointers can be done correctly, as any pointers/references can be interchanged at runtime.
 Coming back to pointers, the only way I can see (short of 
 bringing Rust's borrow checker to D) is to add additional 
 annotations to function return values. The problem comes with 
 code like this :

 int * foo()  safe
 {
 	static int[1] data;
 	return &data[0];
 }
 void main()
 {
         int * restrict p1 = foo();
         int * restrict p2 = foo();//Should be error, but the 
 compiler can't figure
                                   //this out without further 
 annotations
 }
Dealing with pointer aliasing in a generic way is a hard problem :p
Sep 03
parent reply Uknown <sireeshkodali1 gmail.com> writes:
On Sunday, 3 September 2017 at 16:55:51 UTC, Moritz Maxeiner 
wrote:
 On Sunday, 3 September 2017 at 15:39:58 UTC, Uknown wrote:
 On Sunday, 3 September 2017 at 12:59:25 UTC, Moritz Maxeiner 
 wrote:
 [...]
 The main issue I see is that pointers/references can change 
 at runtime, so I don't think a static analysis in the 
 compiler can cover this in general (which, I think, is also 
 why the C99 keyword is an optimization hint only).
Well, I thought about it, I have to agree with you, as far as pointers go. There seems to be no simple way in which the compiler can safely ensure that the two restrict pointers point to the same data. But fir references, it seems trivial.
References are just non-null syntax for pointers that take addresses implicitly on function call. Issues not related to null that pertain to pointers translate to references, as any (non-null) pointer can be turned into a reference (and vice versa): --- void foo(int* a, bool b) { if (b) bar(a); else baz(*a); } void bar(int* a) {} void baz(ref int a) { bar(&a); } ---
Yes. But this is what makes them so useful. You don't have to worry about null dereferences.
 In order to do so, RCArray would have to first annotate it's 
 opIndex, opSlice and any other data returning member functions 
 with the restrict keyword. e.g.
 struct RCArray(T)  safe
 {
 	private T[] _payload;
 	/+some other functions needed to implement RCArray correctly+/
 	restrict ref T opIndex(size_t i) {
 		//implimentation as usual
 		return _payload[i];
 	}
 	restrict ref T opIndex() {
 		return _payload;
 	}
 	//opSlice and the rest defined similary
 }
 [...]
Note: There's no need to attribute the RCArray template as safe (other than for debugging when developing the template). The compiler will derive it for each member if they are indeed safe.
Indeed. I just wrote it to emphasize on the fact that its safe.
 W.r.t. the rest: I don't think treating references as different 
 from pointers can be done correctly, as any pointers/references 
 can be interchanged at runtime.
I'm not sure I understand how one could switch between pointers and refs at runtime. Could you please elaborate a bit or link to an example? Thanks.
 Coming back to pointers, the only way I can see (short of 
 bringing Rust's borrow checker to D) is to add additional 
 annotations to function return values. The problem comes with 
 code like this :

 int * foo()  safe
 {
 	static int[1] data;
 	return &data[0];
 }
 void main()
 {
         int * restrict p1 = foo();
         int * restrict p2 = foo();//Should be error, but the 
 compiler can't figure
                                   //this out without further 
 annotations
 }
Dealing with pointer aliasing in a generic way is a hard problem :p
Yep! I feel there's little point in discussing the introduction of a new keyword if it only works on returning `ref` and has none of the original optimization advantages C brought. On a side note, C99 added `inline` and `restrict`, 2 new keywords, without any worry of potentially breaking existing code. Normally they would have dded _Restrict and _Inline, and then #defined those.
Sep 03
parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Monday, 4 September 2017 at 02:43:48 UTC, Uknown wrote:
 On Sunday, 3 September 2017 at 16:55:51 UTC, Moritz Maxeiner 
 wrote:
 On Sunday, 3 September 2017 at 15:39:58 UTC, Uknown wrote:
 On Sunday, 3 September 2017 at 12:59:25 UTC, Moritz Maxeiner 
 wrote:
 [...]
 The main issue I see is that pointers/references can change 
 at runtime, so I don't think a static analysis in the 
 compiler can cover this in general (which, I think, is also 
 why the C99 keyword is an optimization hint only).
Well, I thought about it, I have to agree with you, as far as pointers go. There seems to be no simple way in which the compiler can safely ensure that the two restrict pointers point to the same data. But fir references, it seems trivial.
References are just non-null syntax for pointers that take addresses implicitly on function call. Issues not related to null that pertain to pointers translate to references, as any (non-null) pointer can be turned into a reference (and vice versa): --- void foo(int* a, bool b) { if (b) bar(a); else baz(*a); } void bar(int* a) {} void baz(ref int a) { bar(&a); } ---
Yes. But this is what makes them so useful. You don't have to worry about null dereferences.
Indeed, but it also means that - other than null dereferencing - pointer issues can by made into reference issues my dereferencing a pointer and passing that into a function that takes that parameter by reference.
 In order to do so, RCArray would have to first annotate it's 
 opIndex, opSlice and any other data returning member 
 functions with the restrict keyword. e.g.
 struct RCArray(T)  safe
 {
 	private T[] _payload;
 	/+some other functions needed to implement RCArray 
 correctly+/
 	restrict ref T opIndex(size_t i) {
 		//implimentation as usual
 		return _payload[i];
 	}
 	restrict ref T opIndex() {
 		return _payload;
 	}
 	//opSlice and the rest defined similary
 }
 [...]
Note: There's no need to attribute the RCArray template as safe (other than for debugging when developing the template). The compiler will derive it for each member if they are indeed safe.
Indeed. I just wrote it to emphasize on the fact that its safe.
 W.r.t. the rest: I don't think treating references as 
 different from pointers can be done correctly, as any 
 pointers/references can be interchanged at runtime.
I'm not sure I understand how one could switch between pointers and refs at runtime. Could you please elaborate a bit or link to an example? Thanks.
What I meant (and apparently poorly expressed) is that you can turn a pointer into a reference (as long as it's not null) and taking the address of a "ref" yields a pointer and as in my `foo` example in the above, which path is taken can change at runtime. You can, e.g. generate a reference to an object's member without the compiler being able to detect it by calculating the appropriate pointer and then dereferencing it.
Sep 03
next sibling parent Uknown <sireeshkodali1 gmail.com> writes:
On Monday, 4 September 2017 at 04:10:44 UTC, Moritz Maxeiner 
wrote:
 What I meant (and apparently poorly expressed) is that you can 
 turn a pointer into a reference (as long as it's not null) and 
 taking the address of a "ref" yields a pointer and as in my 
 `foo` example in the above, which path is taken can change at 
 runtime. You can, e.g. generate a reference to an object's 
 member without the compiler being able to detect it by 
 calculating the appropriate pointer and then dereferencing it.
I think I understand now. Thanks!
Sep 03
prev sibling parent reply ag0aep6g <anonymous example.com> writes:
On 09/04/2017 06:10 AM, Moritz Maxeiner wrote:
 Indeed, but it also means that - other than null dereferencing - pointer 
 issues can by made into reference issues my dereferencing a pointer and 
 passing that into a function that takes that parameter by reference.
Why "other than null dereferencing"? You can dereference a null pointer and pass it in a ref parameter. That doesn't crash at the call site, but only when the callee accesses the parameter: ---- int f(ref int x, bool b) { return b ? x : 0; } void main() { int* p = null; /* Syntactically a null dereference, but doesn't crash: */ f(*p, false); /* This crashes: */ f(*p, true); } ----
Sep 04
next sibling parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Monday, 4 September 2017 at 09:15:30 UTC, ag0aep6g wrote:
 On 09/04/2017 06:10 AM, Moritz Maxeiner wrote:
 Indeed, but it also means that - other than null dereferencing 
 - pointer issues can by made into reference issues my 
 dereferencing a pointer and passing that into a function that 
 takes that parameter by reference.
Why "other than null dereferencing"? You can dereference a null pointer and pass it in a ref parameter. That doesn't crash at the call site, but only when the callee accesses the parameter: [...]
Because I was ignorant and apparently wrong, thanks for the correction. Still, though, this is surprising to me, because this means taking the address of a parameter passed by reference (which is in your case is typed as an existing int) can be null. Is this documented somewhere (couldn't find it in the spec and it seems like a bug to me)?
Sep 04
next sibling parent reply ag0aep6g <anonymous example.com> writes:
On 09/04/2017 11:47 AM, Moritz Maxeiner wrote:
 Still, though, this is surprising to me, because this means taking the 
 address of a parameter passed by reference (which is in your case is 
 typed as an existing int) can be null. Is this documented somewhere 
 (couldn't find it in the spec and it seems like a bug to me)?
I'm only aware of this part of the spec, which doesn't say much about ref parameters: https://dlang.org/spec/function.html#parameters g++ accepts the equivalent C++ code and shows the same behavior. But, as far as I can tell, it's undefined behavior there, because dereferencing null has undefined behavior. In D, dereferencing a null pointer is expected to crash the program. It's allowed in safe code with that expectation. So it seems to have defined behavior that way. But if a dereferencing null must crash the program, shouldn't my code crash at the call site? Or is there an exception for ref parameters? Any way, the spec seems to be missing some paragraphs that clear all this up.
Sep 04
parent Moritz Maxeiner <moritz ucworks.org> writes:
On Monday, 4 September 2017 at 10:24:48 UTC, ag0aep6g wrote:
 On 09/04/2017 11:47 AM, Moritz Maxeiner wrote:
 Still, though, this is surprising to me, because this means 
 taking the address of a parameter passed by reference (which 
 is in your case is typed as an existing int) can be null. Is 
 this documented somewhere (couldn't find it in the spec and it 
 seems like a bug to me)?
I'm only aware of this part of the spec, which doesn't say much about ref parameters: https://dlang.org/spec/function.html#parameters g++ accepts the equivalent C++ code and shows the same behavior. But, as far as I can tell, it's undefined behavior there, because dereferencing null has undefined behavior. In D, dereferencing a null pointer is expected to crash the program. It's allowed in safe code with that expectation. So it seems to have defined behavior that way.
Yes, which is why I wrongly assumed that turning a null pointer into a reference would crash the program (as such references can't be tested for being null, you'd have to turn them back into a pointer to test).
 But if a dereferencing null must crash the program, shouldn't 
 my code crash at the call site? Or is there an exception for 
 ref parameters? Any way, the spec seems to be missing some 
 paragraphs that clear all this up.
Yes, that is what I meant by saying it looks like a bug to me. It really ought to crash at the call site imho; this would require injecting null checks at the call site when the argument is a pointer dereference.
Sep 04
prev sibling parent reply Johan Engelen <j j.nl> writes:
On Monday, 4 September 2017 at 09:47:12 UTC, Moritz Maxeiner 
wrote:
 On Monday, 4 September 2017 at 09:15:30 UTC, ag0aep6g wrote:
 On 09/04/2017 06:10 AM, Moritz Maxeiner wrote:
 Indeed, but it also means that - other than null 
 dereferencing - pointer issues can by made into reference 
 issues my dereferencing a pointer and passing that into a 
 function that takes that parameter by reference.
Why "other than null dereferencing"? You can dereference a null pointer and pass it in a ref parameter. That doesn't crash at the call site, but only when the callee accesses the parameter: [...]
Because I was ignorant and apparently wrong, thanks for the correction. Still, though, this is surprising to me, because this means taking the address of a parameter passed by reference (which is in your case is typed as an existing int) can be null. Is this documented somewhere (couldn't find it in the spec and it seems like a bug to me)?
LDC treats passing `null` to a reference parameter as UB. It doesn't matter when the program crashes after passing null to ref, exactly because it is UB. Because the caller has to do the dereferencing (semantically) you only have to do the null-check in the caller, and not in callee. This removes a ton of manual null-ptr checks from the code, and enables more optimizations too. For class parameters, they are pointers not references, as in: it is _not_ UB to pass-in `null`. Very unfortunate, because it necessitates null-ptr checks everywhere in the code, and hurts performance due to missed optimization opportunities. (The spec requires crashing on null dereferencing, but this spec bit is ignored by DMD and LDC, I assume in GDC too. Crashing on `null` dereferencing requires a null-check on every dereferencing through an unchecked pointer, because 0 might be a valid memory access, and also because ptr->someDataField is not going to lookup address 0, but 0+offsetof(someDataField) instead, e.g. potentially addressing a valid low address at 1000000, say.) - Johan
Sep 04
parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Monday, 4 September 2017 at 17:58:41 UTC, Johan Engelen wrote:
 On Monday, 4 September 2017 at 09:47:12 UTC, Moritz Maxeiner 
 wrote:
 On Monday, 4 September 2017 at 09:15:30 UTC, ag0aep6g wrote:
 On 09/04/2017 06:10 AM, Moritz Maxeiner wrote:
 Indeed, but it also means that - other than null 
 dereferencing - pointer issues can by made into reference 
 issues my dereferencing a pointer and passing that into a 
 function that takes that parameter by reference.
Why "other than null dereferencing"? You can dereference a null pointer and pass it in a ref parameter. That doesn't crash at the call site, but only when the callee accesses the parameter: [...]
Because I was ignorant and apparently wrong, thanks for the correction. Still, though, this is surprising to me, because this means taking the address of a parameter passed by reference (which is in your case is typed as an existing int) can be null. Is this documented somewhere (couldn't find it in the spec and it seems like a bug to me)?
LDC treats passing `null` to a reference parameter as UB. It doesn't matter when the program crashes after passing null to ref, exactly because it is UB.
Ok, that's good to know, though it'd be nice for this to be defined somewhere in the language spec.
 Because the caller has to do the dereferencing (semantically) 
 you only have to do the null-check in the caller, and not in 
 callee. This removes a ton of manual null-ptr checks from the 
 code, and enables more optimizations too.
Indeed, which is why I currently think the spec should state that this isn't UB, but has to crash at the call site.
 For class parameters, they are pointers not references, as in: 
 it is _not_ UB to pass-in `null`. Very unfortunate, because it 
 necessitates null-ptr checks everywhere in the code, and hurts 
 performance due to missed optimization opportunities.
Well, technically they are "class references". In any case, they don't require injecting null checks from the compiler in general, as using them in any way will be a null dereference (which the hardware&OS are required to turn into a crash).
 (The spec requires crashing on null dereferencing, but this 
 spec bit is ignored by DMD and LDC, I assume in GDC too.
 Crashing on `null` dereferencing requires a null-check on every 
 dereferencing through an unchecked pointer, because 0 might be 
 a valid memory access, and also because ptr->someDataField is 
 not going to lookup address 0, but 0+offsetof(someDataField) 
 instead, e.g. potentially addressing a valid low address at 
 1000000, say.)
It's not implemented as compiler checks because the "actual" requirement is "the platform has to crash on null dereference" (see the discussion in/around [1]). Essentially: "if your platform doesn't crash on null dereference, don't use D on it (at the very least not safe D)". The issue concerning turning a pointer into a reference parameter is that when reading the code it looks like the dereference is happening at the call site, while the resulting compiled executable will actually perform the (null) dereference inside the function on use of the reference parameter. That is why I think the null check should be injected at the call site, because depending on platform support for the crash will may yield the wrong result (if the reference parameter isn't actually used in the function, it won't crash, even though it *should*). [1] https://forum.dlang.org/post/udkdqogtrvanhbotdoik forum.dlang.org
Sep 04
parent reply Johan Engelen <j j.nl> writes:
On Monday, 4 September 2017 at 21:23:50 UTC, Moritz Maxeiner 
wrote:
 On Monday, 4 September 2017 at 17:58:41 UTC, Johan Engelen 
 wrote:
 (The spec requires crashing on null dereferencing, but this 
 spec bit is ignored by DMD and LDC, I assume in GDC too.
 Crashing on `null` dereferencing requires a null-check on 
 every dereferencing through an unchecked pointer, because 0 
 might be a valid memory access, and also because 
 ptr->someDataField is not going to lookup address 0, but 
 0+offsetof(someDataField) instead, e.g. potentially addressing 
 a valid low address at 1000000, say.)
It's not implemented as compiler checks because the "actual" requirement is "the platform has to crash on null dereference" (see the discussion in/around [1]). Essentially: "if your platform doesn't crash on null dereference, don't use D on it (at the very least not safe D)".
My point was that that is not workable. The "null dereference" is a D language construct, not something that the machine is doing. It's ridiculous to specify that reading from address 1_000_000 should crash the program, yet that is exactly what is specified by D when running this code (and thus null checks need to be injected in many places to be spec compliant): ``` struct S { ubyte[1_000_000] a; int b; } void main() { S* s = null; s.b = 1; } ``` -Johan
Sep 05
next sibling parent dukc <ajieskola gmail.com> writes:
On Tuesday, 5 September 2017 at 18:32:34 UTC, Johan Engelen wrote:
 My point was that that is not workable. The "null dereference" 
 is a D language construct, not something that the machine is 
 doing. It's ridiculous to specify that reading from address 
 1_000_000 should crash the program, yet that is exactly what is 
 specified by D when running this code (and thus null checks 
 need to be injected in many places to be spec compliant):

 ```
 struct S {
   ubyte[1_000_000] a;
   int b;
 }
 void main() {
    S* s = null;
    s.b = 1;
 }
 ```

 -Johan
Perhaps it should nullcheck exceptionally large types which may overflow the memory protected area, but not others?
Sep 05
prev sibling next sibling parent Moritz Maxeiner <moritz ucworks.org> writes:
On Tuesday, 5 September 2017 at 18:32:34 UTC, Johan Engelen wrote:
 On Monday, 4 September 2017 at 21:23:50 UTC, Moritz Maxeiner 
 wrote:
 On Monday, 4 September 2017 at 17:58:41 UTC, Johan Engelen 
 wrote:
 (The spec requires crashing on null dereferencing, but this 
 spec bit is ignored by DMD and LDC, I assume in GDC too.
 Crashing on `null` dereferencing requires a null-check on 
 every dereferencing through an unchecked pointer, because 0 
 might be a valid memory access, and also because 
 ptr->someDataField is not going to lookup address 0, but 
 0+offsetof(someDataField) instead, e.g. potentially 
 addressing a valid low address at 1000000, say.)
It's not implemented as compiler checks because the "actual" requirement is "the platform has to crash on null dereference" (see the discussion in/around [1]). Essentially: "if your platform doesn't crash on null dereference, don't use D on it (at the very least not safe D)".
My point was that that is not workable. The "null dereference" is a D language construct, not something that the machine is doing.
While "null dereference" is a language construct "null" is defined as actual address zero (like it's defined in C/C++ by implementation) and dereference means r/w from/to that virtual memory address, it is something the machine does: Namely, memory protection, because the page for address 0 is (usually) not mapped (and D requires it to not be mapped for safe to work), accessing it will lead to a page fault, which in turn leads to a segmentation fault and then program crash.
 It's ridiculous to specify that reading from address 1_000_000 
 should crash the program, yet that is exactly what is specified 
 by D when running this code (and thus null checks need to be 
 injected in many places to be spec compliant):

 ```
 struct S {
   ubyte[1_000_000] a;
   int b;
 }
 void main() {
    S* s = null;
    s.b = 1;
 }
 ```
In order to be spec compliant and correct a compiler would only need to inject null checks on dereferences where the size of the object being pointed to (in your example S.sizeof) is larger than the bottom virtual memory segment of the target OS (the one which no C compatible OS maps automatically and you also shouldn't map manually). The size of that bottom segment, however, is usually _deliberately_ large precisely so that buggy (C) programs crash on NULL dereference (even with structures as the above), so in practice, unless you invalidate assumptions about expected maximum structure sizes made by the OS, null dereferences can be assumed to crash.
Sep 05
prev sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tuesday, September 05, 2017 18:32:34 Johan Engelen via Digitalmars-d 
wrote:
 On Monday, 4 September 2017 at 21:23:50 UTC, Moritz Maxeiner

 wrote:
 On Monday, 4 September 2017 at 17:58:41 UTC, Johan Engelen

 wrote:
 (The spec requires crashing on null dereferencing, but this
 spec bit is ignored by DMD and LDC, I assume in GDC too.
 Crashing on `null` dereferencing requires a null-check on
 every dereferencing through an unchecked pointer, because 0
 might be a valid memory access, and also because
 ptr->someDataField is not going to lookup address 0, but
 0+offsetof(someDataField) instead, e.g. potentially addressing
 a valid low address at 1000000, say.)
It's not implemented as compiler checks because the "actual" requirement is "the platform has to crash on null dereference" (see the discussion in/around [1]). Essentially: "if your platform doesn't crash on null dereference, don't use D on it (at the very least not safe D)".
My point was that that is not workable. The "null dereference" is a D language construct, not something that the machine is doing. It's ridiculous to specify that reading from address 1_000_000 should crash the program, yet that is exactly what is specified by D when running this code (and thus null checks need to be injected in many places to be spec compliant): ``` struct S { ubyte[1_000_000] a; int b; } void main() { S* s = null; s.b = 1; } ```
dmd and the spec were written with the assumption that the CPU is going to segfault your program when you dereference a null pointer. In the vast majority of cases, that assumption holds. The problem of course is the case that you bring up where you're dealing with objects that are large enough that the CPU can't do that anymore. And as Moritz points out, all that's required to fix that is to insert null checks for those types. It shouldn't be necessary at all for the vast majority of types. The CPU already handles them correctly - at least on any x86-based system. I would expect any other modern CPU to do the same, but I'm not familiar enough with other such systems to know for sure. Regardless, there definitely should be no need to insert null checks all over the place in any x86-based code. At most, it's needed in a few places to deal with abnormally large objects. Regardless, for safe to do its job, the program does need to crash when dereferencing null. So, if the CPU can't do the checks like the spec currently assumes, then the compiler is going to need to insert the checks, and while that may hurt performance, I don't think that there's really any way around that while still ensuring that safe code does not corrupt memory or access memory that it's not supposed to. system code could skip it to get the full performance, but safe is stuck. - Jonathan M Davis
Sep 05
parent reply Johan Engelen <j j.nl> writes:
On Tuesday, 5 September 2017 at 22:59:12 UTC, Jonathan M Davis 
wrote:
 dmd and the spec were written with the assumption that the CPU 
 is going to segfault your program when you dereference a null 
 pointer. In the vast majority of cases, that assumption holds.
In my terminology, "dereference" is a language spec term. It is not directly related to what the CPU is doing. ``` struct S { void nothing() {} } void foo (S* s) { (*s).nothing(); //dereference must crash on null? } ``` If you call the `(*s)` a dereference, then you are agreeing with "my" dereference terminology. ( used the * for extra clarity; "s.nothing()" is the same.) In LDC, dereferencing a null ptr is UB. DMD is assuming the same, or something similar. Otherwise DMD wouldn't be able to optimize foo in this example to an empty body as it does currently. (go go null-checks everywhere) -Johan
Sep 06
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, September 06, 2017 19:40:16 Johan Engelen via Digitalmars-d 
wrote:
 On Tuesday, 5 September 2017 at 22:59:12 UTC, Jonathan M Davis

 wrote:
 dmd and the spec were written with the assumption that the CPU
 is going to segfault your program when you dereference a null
 pointer. In the vast majority of cases, that assumption holds.
In my terminology, "dereference" is a language spec term. It is not directly related to what the CPU is doing. ``` struct S { void nothing() {} } void foo (S* s) { (*s).nothing(); //dereference must crash on null? } ``` If you call the `(*s)` a dereference, then you are agreeing with "my" dereference terminology. ( used the * for extra clarity; "s.nothing()" is the same.) In LDC, dereferencing a null ptr is UB. DMD is assuming the same, or something similar. Otherwise DMD wouldn't be able to optimize foo in this example to an empty body as it does currently. (go go null-checks everywhere)
I would argue that if the dereferencing of the pointer is optimized out, then it is never dereferenced, and therefore, it doesn't need to crash. It's only if it's actually dereferenced that the crashing needs to occur, because that's what's need for safe to be safe. I can totally believe that the spec needs to be clearer about this, but I would definitely interpret it to mean that if the pointer is actually dereferenced, the program must crash and not that your code example must crash even if it's optimized. And I would be surprised if Walter meant anything else. He just isn't always good about writing the spec in a way that others agree that it means what he meant, and to be fair, it can be very hard to write things in an unambiguous way. Regardless, I don't see a problem here - or a need to insert a bunch of null checks. The spec should probably be clarified, but the only thing that I'm aware of that I would consider a hole in dereferencing null right now is the fact that it relies on the CPU to segfault the program in cases where the object is too large for that to occur - and in those cases, null checks really should be inserted. For objects that are small enough to trigger segfaults with null, null checks should not be necessary. - Jonathan M Davis
Sep 06
prev sibling parent Cecil Ward <d cecilward.com> writes:
On Monday, 4 September 2017 at 09:15:30 UTC, ag0aep6g wrote:
 On 09/04/2017 06:10 AM, Moritz Maxeiner wrote:
 That doesn't crash at the call site, but only when the callee 
 accesses the parameter:
That's just an observation based on a detail of a particular compiler implementation. It's simply not true in general but might appear that way in a particular case. Did you inspect the generated code? If the entire thing has been _inlined_ and properly optimised as decent modern compilers most definitely all do _when the correct switches are used_, then looking at the code there is no such thing as caller and callee - it's all just a stream of code.
Sep 06
prev sibling next sibling parent reply Dukc <ajieskola gmail.com> writes:
On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 In C, the `restrict` keyword implies that 2 or more pointer 
 arguments in a function call do not point to the same data.
I really don't see where the restrict keyword is needed at all, neither in C nor in D. If you want to imply to the compiler that there is no need to reload the pointed data between uses, just assign it to a local.
Sep 04
next sibling parent reply Johan Engelen <j j.nl> writes:
On Monday, 4 September 2017 at 14:28:14 UTC, Dukc wrote:
 On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 In C, the `restrict` keyword implies that 2 or more pointer 
 arguments in a function call do not point to the same data.
I really don't see where the restrict keyword is needed at all, neither in C nor in D. If you want to imply to the compiler that there is no need to reload the pointed data between uses, just assign it to a local.
It's need for auto-vectorization, for example. I would support an LDC PR for adding a magic UDA to be able to attach 'restrict' with C-semantics to function parameters. E.g. ``` // add restrict to parameters 1 and 2 void foo(int, int*, int*) restrict(1,2) ``` -Johan
Sep 04
parent reply Dukc <ajieskola gmail.com> writes:
On Monday, 4 September 2017 at 18:03:51 UTC, Johan Engelen wrote:
 It's need for auto-vectorization, for example.

 I would support an LDC PR for adding a magic UDA to be able to 
 attach 'restrict' with C-semantics to function parameters. E.g.
 ```
  // add restrict to parameters 1 and 2
 void foo(int, int*, int*)  restrict(1,2)
 ```
That probably explains it in case of c. But I still think that D might be able to do this better without language changes. This way (not compiler-checked for errors): ``` for(int i = 0; i < a.length; i+=8) { int[8] aVec = a[i .. i+8], bVec = b[i .. i+8], cVec; foreach(j; 0 .. 8) cVec[j] = aVec[j].foo(bVec[j]); c[i .. i+8] = cVec[]; } ``` Of course, if we want to support this we should construct a high-level library template that chooses the correct vector size for the platform, eliminates that outer for loop and handles uneven array lenghts.
Sep 05
parent reply Petar Kirov [ZombineDev] <petar.p.kirov gmail.com> writes:
On Tuesday, 5 September 2017 at 15:46:13 UTC, Dukc wrote:
 [..]

 Of course, if we want to support this we should construct a 
 high-level library template that chooses the correct vector 
 size for the platform, eliminates that outer for loop and 
 handles uneven array lenghts.
You mean like this: https://github.com/dlang/druntime/pull/1891?
Sep 06
parent reply Dukc <ajieskola gmail.com> writes:
On Wednesday, 6 September 2017 at 09:21:59 UTC, Petar Kirov 
[ZombineDev] wrote:
 On Tuesday, 5 September 2017 at 15:46:13 UTC, Dukc wrote:
 [..]

 Of course, if we want to support this we should construct a 
 high-level library template that chooses the correct vector 
 size for the platform, eliminates that outer for loop and 
 handles uneven array lenghts.
You mean like this: https://github.com/dlang/druntime/pull/1891?
No. I meant a function which, given an array, returns a range over that array which internally reads many elements at once from the array by copying them to a static array for handling. Then the compiler knows it can take advantage of optimizations like that pull request, because it knows static arrays can't overlap, even if the original arguments do. Of course the user should not call that function if the arrays do overlap, or if the loop body mutates other elements. See David Simcha's talk at DConf 13 at 37:30, that's the basic idea how I'm thinking the range would internally iterate. https://www.youtube.com/watch?v=yMNMV9JlkcQ&list=PLpISZoFBH1xtyA6uBsNyQH8P3lx92U64V&index=16
Sep 06
parent Dukc <ajieskola gmail.com> writes:
On Wednesday, 6 September 2017 at 17:30:44 UTC, Dukc wrote:
 See David Simcha's talk at DConf 13 at 37:30, that's the basic 
 idea how I'm thinking the range would internally iterate.
Correction: The outer loop would iterate in steps like that but the body would be different. It would each time copy elements into static array of length unroll.length (which in this case would be width of vector operations), let the user iterate over that and then assign it back to the original array.
Sep 08
prev sibling parent Uknown <sireeshkodali1 gmail.com> writes:
On Monday, 4 September 2017 at 14:28:14 UTC, Dukc wrote:
 On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 In C, the `restrict` keyword implies that 2 or more pointer 
 arguments in a function call do not point to the same data.
I really don't see where the restrict keyword is needed at all, neither in C nor in D. If you want to imply to the compiler that there is no need to reload the pointed data between uses, just assign it to a local.
You can see the second answer on this Stack overflow question[1]. It explains how `restrict` can be used in C to tell the compiler that there won't be any aliasing between two pointers, and the optimizations the compiler can do, given this knowledge. [1] https://stackoverflow.com/questions/745870/realistic-usage-of-the-c99-restrict-keyword#745877
Sep 05
prev sibling parent jmh530 <john.michael.hall gmail.com> writes:
On Sunday, 3 September 2017 at 03:04:58 UTC, Uknown wrote:
 I just hope to have a nice discussion on this topic here.

 Thanks!
You might find interesting the reference capabilities of Pony: https://tutorial.ponylang.org/capabilities/reference-capabilities.html So with respect to restrict, there are a few that might be relevant. iso - can only have one reference box - similar to const function parameters in D, can give out read-only views trn - sort of the reverse of const, it's like a write unique, you can write to, but other people cannot When I think of restrict, it's like telling the compiler that these two pointers don't overlap their data. By contrast, if you pass parameters to a function with these reference capabilities, then it would be providing the compiler slightly different information. If you pass iso, it tells the compiler that no other variable pointers to this variable. If you use box (const), you're telling the compiler that you won't modify it in this function. If you use trn, you're telling the compiler that this reference is the only way to modify the variable (i.e. another variable in the function cannot modify it). I'm not an expert on pony or anything, so I'm not sure how complicated this makes things with aggregate types.
Sep 04