3 ms·

The code intentionally uses `y` to access stuff that it also accesses through `x`. Declaring `x` and `y` to be `restrict` was a promise that it wouldn't do tha

by xscott 5y ago

The code intentionally uses `y` to access stuff that it also accesses through `x`. Declaring `x` and `y` to be `restrict` was a promise that it wouldn't do that. > Does the standard not allow you to pass any pointers which could be aliased based on arbitrary pointer arithmetic With the right hackish arithmetic, all pointers could be aliased with pointer arithmetic in C. Using `restrict` says your code won't do that so the compiler can optimize more. > It seems very hard in general to know if two mutable references point to items in the same allocation. Yeah, and in the limit it's impossible for C. It's not the compiler's job to figure it out, it's the code's job to uphold the promise. It's different with Rust because you've got mutable/exclusive or immutable/shared promises from the borrow checker. And Rust doesn't let you dereference raw pointers outside of an unsafe block. It seems to me that mislabeling your pointers `restrict` in C is akin to doing reckless operations inside of `unsafe` blocks in Rust. In both cases, you told the compiler "trust me, I know what I'm doing".

hvdijk 5y ago
> With the right hackish arithmetic, all pointers could be aliased with pointer arithmetic in C. This is not true. The behaviour is undefined in C if pointer arithmetic results in crossing the beginning or end of an object. If we have int a, b;, then the behaviour is undefined if we do &b - &a even if we never use the result to try to reconstruct &b from &a. > Using `restrict` says your code won't do that so the compiler can optimize more. `restrict` covers objects modified through one pointer and accessed through another. It does not cover pointers that point to the same object in general; if only one is used to access the object, or if both are used only for reading, all is fine. (It's actually a little bit more complicated than I'm presenting here, but not in a way that's relevant right now.)
- xscott 5y ago
  Seems like we need a C compiler flag like "--acknowledge-reality", because the compilers for nearly 100% of the server, desktop, and mobile computers in the real world have flat address spaces and do allow arbitrary pointer arithmetic. Yes, it's technically UB. But which operation could any C compiler disallow in practice: converting from pointer to integer, arithmetic on integers, or converting from integer to pointer?
  - hvdijk 5y ago
    Sorry to disappoint, but the compilers for nearly 100% of the server, desktop, and mobile computers in the real world do not allow arbitrary pointer arithmetic. They cannot issue an error message for it because that is provably impossible to detect in the general case, but they do optimise on the basis that it does not happen, even if it breaks programs that try to make use of it. Consider this example for GCC: int a[2], b[2]; int offset(void) { return b - a; } int check(void) { return &a[1] + offset() == &b[1]; } The function check() is optimised by GCC to return zero at -O1 optimisation level or higher, because it reasons that no matter how offset() is implemented, either the addition is undefined, or the comparison results in false. (Note that GCC does this even in a few cases where it is unclear whether the optimisation is valid. The example I provided is slightly more complicated than I would have liked to avoid that issue; the optimisation is definitely valid in this example.)
    - deleted 5y ago
      [deleted]
    - xscott 5y ago
      I originally responded to your code, and you're right about it. That's not what I expected or would want to happen. However, your code doesn't actually address my comment about conversions and arithmetic. Where does this code code fail? int a[2], b[2]; uintptr_t x = (uintptr_t)a; uintptr_t y = (uintptr_t)b; uintptr_t offset = y - x; int* p = (int*)(x + offset); printf("b == p: %d\n", b==p); I didn't try _every_ compiler on Godbolt, but I didn't see it misbehave anywhere I did try. edit: changed to uintptr_t
      - spc476 5y ago
        There's nothing in the C standard that I could find that dictates that b[] has to follow directly after a[] in memory. That it works is just happenstance (or an implementation detail). The only place were order is maintained are fields in a structure definition.
        5y ago

by xscott 5y ago

hvdijk 5y ago

> With the right hackish arithmetic, all pointers could be aliased with pointer arithmetic in C. This is not true. The behaviour is undefined in C if pointer arithmetic results in crossing the beginning or end of an object. If we have int a, b;, then the behaviour is undefined if we do &b - &a even if we never use the result to try to reconstruct &b from &a. > Using `restrict` says your code won't do that so the compiler can optimize more. `restrict` covers objects modified through one pointer and accessed through another. It does not cover pointers that point to the same object in general; if only one is used to access the object, or if both are used only for reading, all is fine. (It's actually a little bit more complicated than I'm presenting here, but not in a way that's relevant right now.)

xscott 5y ago
Seems like we need a C compiler flag like "--acknowledge-reality", because the compilers for nearly 100% of the server, desktop, and mobile computers in the real world have flat address spaces and do allow arbitrary pointer arithmetic. Yes, it's technically UB. But which operation could any C compiler disallow in practice: converting from pointer to integer, arithmetic on integers, or converting from integer to pointer?
- hvdijk 5y ago
  Sorry to disappoint, but the compilers for nearly 100% of the server, desktop, and mobile computers in the real world do not allow arbitrary pointer arithmetic. They cannot issue an error message for it because that is provably impossible to detect in the general case, but they do optimise on the basis that it does not happen, even if it breaks programs that try to make use of it. Consider this example for GCC: int a[2], b[2]; int offset(void) { return b - a; } int check(void) { return &a[1] + offset() == &b[1]; } The function check() is optimised by GCC to return zero at -O1 optimisation level or higher, because it reasons that no matter how offset() is implemented, either the addition is undefined, or the comparison results in false. (Note that GCC does this even in a few cases where it is unclear whether the optimisation is valid. The example I provided is slightly more complicated than I would have liked to avoid that issue; the optimisation is definitely valid in this example.)
  - deleted 5y ago
    [deleted]
  - xscott 5y ago
    I originally responded to your code, and you're right about it. That's not what I expected or would want to happen. However, your code doesn't actually address my comment about conversions and arithmetic. Where does this code code fail? int a[2], b[2]; uintptr_t x = (uintptr_t)a; uintptr_t y = (uintptr_t)b; uintptr_t offset = y - x; int* p = (int*)(x + offset); printf("b == p: %d\n", b==p); I didn't try _every_ compiler on Godbolt, but I didn't see it misbehave anywhere I did try. edit: changed to uintptr_t
    - spc476 5y ago
      There's nothing in the C standard that I could find that dictates that b[] has to follow directly after a[] in memory. That it works is just happenstance (or an implementation detail). The only place were order is maintained are fields in a structure definition.
      - 5y ago