3 ms·

It's interesting work but I really wonder if it's desirable. What real-world problems is this supposed to solve exactly? Making the compiler extra-clever about

by simias 8y ago

It's interesting work but I really wonder if it's desirable. What real-world problems is this supposed to solve exactly? Making the compiler extra-clever about detecting aliasing seems like a good recipe for having broken code appear to work correctly until it doesn't or getting strange behavior that's a pain to debug. Current aliasing rules are already a significant pain point in the C standard IMO, I personally don't want them to become even more complicated. The only concrete example given in the paper (having two contiguous objects and referencing the 2nd one through a pointer on the first one) is frankly contrived and I'm not sure how that can be considered reasonable or good code. The only time I could see myself writing code like that is when dealing with memory-mapped hardware registers at fixed addresses which would let me do funky pointer arithmetic, but in this scenario the pointer is usually tagged as volatile and sometimes accompanied by a memory barrier to make sure the compiler does the right thing. Note that if the programmers really wanted the code given in the paper to work correctly (i.e. changing y through an offset pointer from x) they could do it by adding a memory barrier such as asm volatile("": : :"memory"); after the *p = 11;. Is it elegant? Arguably not, but it seems like such a niche use to me that it seems like a fair compromise. It's also not standard C but if you're making such pointer gymnastics chances are you're already making assumptions about your environment that go beyond the standard. I much prefer Rust's approach of "mutable references never alias" and if the programmer really needs to share a reference they have to manually do the work by wrapping. Of course integrating that into C in a backward-compatible fashion doesn't seem very practical.

fooker 8y ago
>I much prefer Rust's approach of "mutable references never alias" This rules out a vast majority of fundamental algorithms. Jumping through hoops for getting simple logic working doesn't sound very desirable.
- simias 8y ago
  There's always unsafe. With generics you can always implement these fundamental algorithms once and for all in an unsafe block and then reuse that. No need to reimplement quicksort for every data type. But I'm not proposing to bring that to C (although it seems that generics are slowly creeping in by way of the macro system), I'm just saying that I think the changes proposed in this paper would make the language more complex without really making it easier to write C code 99% of the time.
- ekidd 8y ago
  >>I much prefer Rust's approach of "mutable references never alias" >This rules out a vast majority of fundamental algorithms. To be more precise, in Rust: - '&mut T' (a mutable reference to T) can never alias. - '(asterix) mut T' (a mutable pointer to T) can alias. The advantage is that you can write most production code with a mix of '&T' and '&mut T', which allows the compiler to assume no mutable aliases anywhere. But if you're building a doubly-linked list, then you can explicitly choose '(asterix) mut T'. (For other options, see https://rust-unofficial.github.io/too-many-lists/. https://rust-unofficial.github.io/too-many-lists/.) In practice, it depends a lot on the code you're writing. I've written tens of thousands of lines of production Rust without needing shared mutability. But if I were writing a traditional game or GUI toolkit, then I might miss shared mutability a lot more.
  - hedora 8y ago
    The & semantics sound like fortran’s semantics. How does the rust compiler know if two references passed in from calling code can alias or not? (I.e., what if I get the type annotations wrong?). In general, determining if two pointers can alias is equivalent to the halting problem. The default C way is “assume aliasing unless you can prove otherwise”. This seems safer and like less work to me.
    - wwright 8y ago
      Aliasing is checked in the calling code, not the callee. You’re not allow to create a mutable reference if another exists in the same scope. If you use “plain” safe Rust, there’s simply just no way to create alias mutable references unsafely. (The C default you refer to is at the compiler internals level. The Rust alias prevention we’re talking about is at the language level. C compilers will try to avoid generating code that will behave incorrectly in the presence of aliasing, but do nothing to prevent aliasing and the possible logic and thread safety issues caused by aliasing. Rust makes almost all of these cases disappear for the programmer.)
    - Ar-Curunir 8y ago
      The compiler ensures that you can only take one &mut reference at a time. You can have as many immutable `&` references as you want, because you can't change anything through those references (unless you do some unsafe trickery)
FrozenVoid 8y ago
> It's interesting work but I really wonder if it's desirable Aliasing pointers ruing performance of array/pointer access optimizations. https://en.wikipedia.org/wiki/Restrict https://en.wikipedia.org/wiki/Restrict
- simias 8y ago
  I'm aware of restrict and the problem it solves but that does that say about TFA? Are you proposing that restrict should be deprecated in favor of the mechanism proposed by the parent? The example in the paper linked is specifically a situation where the compiler does not normally catch the aliasing between two pointers which is the opposite of the problem "restrict" solves (i.e. a situation where the compiler emits code that assumes that two pointers can alias when in fact they do not).
pm215 8y ago
The programmers don't want the code in the paper to work correctly, though. What they want is for the C spec to rule it incorrect without also ruling a lot of existing working code to be invalid. Rust's approach is certainly easier to understand in some ways, but C is not Rust and you can't just change its semantics without considering the existing body of code.
- Animats 8y ago
  C needs an ownership model, but it's almost hopeless to retrofit one. This is a very limited proposal regarding some obscure aliasing problems. I looked at C and C++ ownership years ago. I had more limited goals than the Rust borrow checker. I was thinking in terms of permissions - read, write, delete, and keep, combined with reference counting. Keep permission means you can take a copy of a pointer and export it to a larger scope. Like passing in a pointer to an object to be added to a collection. The stored pointer will outlive the return from the function that added it to the collection. It "kept" it. If you pass a reference to an object without keep permission, the called function can't keep it. So the language does not have to increment the reference count. In fact, you don't even have to pass the reference count, just the raw object pointer. So objects passed by non-keep reference to a function incur no extra overhead. That's a very common case. "Keeping" is relatively rare. So you get reference count allocation without much overhead. Workable, but a dead end politically in C. Rust essentially makes all references "non-keep", unless you explicitly use reference counts.

by simias 8y ago

fooker 8y ago

>I much prefer Rust's approach of "mutable references never alias" This rules out a vast majority of fundamental algorithms. Jumping through hoops for getting simple logic working doesn't sound very desirable.

simias 8y ago
There's always unsafe. With generics you can always implement these fundamental algorithms once and for all in an unsafe block and then reuse that. No need to reimplement quicksort for every data type. But I'm not proposing to bring that to C (although it seems that generics are slowly creeping in by way of the macro system), I'm just saying that I think the changes proposed in this paper would make the language more complex without really making it easier to write C code 99% of the time.
ekidd 8y ago
>>I much prefer Rust's approach of "mutable references never alias" >This rules out a vast majority of fundamental algorithms. To be more precise, in Rust: - '&mut T' (a mutable reference to T) can never alias. - '(asterix) mut T' (a mutable pointer to T) can alias. The advantage is that you can write most production code with a mix of '&T' and '&mut T', which allows the compiler to assume no mutable aliases anywhere. But if you're building a doubly-linked list, then you can explicitly choose '(asterix) mut T'. (For other options, see https://rust-unofficial.github.io/too-many-lists/. https://rust-unofficial.github.io/too-many-lists/.) In practice, it depends a lot on the code you're writing. I've written tens of thousands of lines of production Rust without needing shared mutability. But if I were writing a traditional game or GUI toolkit, then I might miss shared mutability a lot more.
- hedora 8y ago
  The & semantics sound like fortran’s semantics. How does the rust compiler know if two references passed in from calling code can alias or not? (I.e., what if I get the type annotations wrong?). In general, determining if two pointers can alias is equivalent to the halting problem. The default C way is “assume aliasing unless you can prove otherwise”. This seems safer and like less work to me.
  - wwright 8y ago
    Aliasing is checked in the calling code, not the callee. You’re not allow to create a mutable reference if another exists in the same scope. If you use “plain” safe Rust, there’s simply just no way to create alias mutable references unsafely. (The C default you refer to is at the compiler internals level. The Rust alias prevention we’re talking about is at the language level. C compilers will try to avoid generating code that will behave incorrectly in the presence of aliasing, but do nothing to prevent aliasing and the possible logic and thread safety issues caused by aliasing. Rust makes almost all of these cases disappear for the programmer.)
  - Ar-Curunir 8y ago
    The compiler ensures that you can only take one &mut reference at a time. You can have as many immutable `&` references as you want, because you can't change anything through those references (unless you do some unsafe trickery)

FrozenVoid 8y ago

> It's interesting work but I really wonder if it's desirable Aliasing pointers ruing performance of array/pointer access optimizations. https://en.wikipedia.org/wiki/Restrict https://en.wikipedia.org/wiki/Restrict

simias 8y ago
I'm aware of restrict and the problem it solves but that does that say about TFA? Are you proposing that restrict should be deprecated in favor of the mechanism proposed by the parent? The example in the paper linked is specifically a situation where the compiler does not normally catch the aliasing between two pointers which is the opposite of the problem "restrict" solves (i.e. a situation where the compiler emits code that assumes that two pointers can alias when in fact they do not).

pm215 8y ago

The programmers don't want the code in the paper to work correctly, though. What they want is for the C spec to rule it incorrect without also ruling a lot of existing working code to be invalid. Rust's approach is certainly easier to understand in some ways, but C is not Rust and you can't just change its semantics without considering the existing body of code.

Animats 8y ago
C needs an ownership model, but it's almost hopeless to retrofit one. This is a very limited proposal regarding some obscure aliasing problems. I looked at C and C++ ownership years ago. I had more limited goals than the Rust borrow checker. I was thinking in terms of permissions - read, write, delete, and keep, combined with reference counting. Keep permission means you can take a copy of a pointer and export it to a larger scope. Like passing in a pointer to an object to be added to a collection. The stored pointer will outlive the return from the function that added it to the collection. It "kept" it. If you pass a reference to an object without keep permission, the called function can't keep it. So the language does not have to increment the reference count. In fact, you don't even have to pass the reference count, just the raw object pointer. So objects passed by non-keep reference to a function incur no extra overhead. That's a very common case. "Keeping" is relatively rare. So you get reference count allocation without much overhead. Workable, but a dead end politically in C. Rust essentially makes all references "non-keep", unless you explicitly use reference counts.