5 ms·
Not in the article, but I've read that the way C does pointers, a single address with length implicit, makes it hard for compilers to assert that 2 arrays don't
by woooooo 2y ago
Not in the article, but I've read that the way C does pointers, a single address with length implicit, makes it hard for compilers to assert that 2 arrays don't overlap/alias and this is an obstacle for generating SIMD instructions.
- 1718627440 2y agoNot really. Pointers from different allocations are guaranteed to never alias. If they do, it is UB.
- AnimalMuppet 2y agoRight, but the compiler in general has no way to know that pointers are from different allocations - especially several function calls away from the allocations, with some pointer arithmetic in between.
- 1718627440 2y agoYes, that is why restrict was introduced.
- bee_rider 2y agoIn general, the information as to whether or not the pointers will alias might not even be known, right? Like we could be compiling a library that will take in some pointers from the user.
- wayoverthecloud 2y agoIn C++ there is the align_alloc specificier. https://en.cppreference.com/w/c/memory/aligned_alloc https://en.cppreference.com/w/c/memory/aligned_alloc Not sure for C
- ryanpetrich 2y agoaligned_alloc is a C function. It doesn't help the compiler prove that two pointers can't alias. restrict is the keyword that does.
- bobmcnamara 2y agoThe compiler is allowed to assume the results of malloc and certain other allocation functions do not alias. Restrict does too.
- alkh 2y agoI thought you could simply add `restrict`[1] to indicate that only one pointer points to a specific object? Shouldn't this help? [1]https://en.cppreference.com/w/c/language/restrict https://en.cppreference.com/w/c/language/restrict
- aidenn0 2y agoYou can add that qualifier, but nothing will enforce that objects don't overlap. So you replaced slow correct code with fast incorrect code.
- TheNewAndy 2y agoIf you believed the pointers didn't alias and they actually did then you replaced slow incorrect code with fast incorrect code
- aidenn0 2y agoThat doesn't follow? If you replaced every call of memcpy with memmove (to use an example from the standard library), then your program is no less correct than it was before (and possibly more). The converse is that adding "restrict" qualifiers to existing functions can only make your program less correct, not more.
- ablob 2y agoIn this context it follows. If you believe the pointers dont alias (and want to use simd) then there should be no data-dependencies inbetween indices. (If there are data-dependencies it is quite likely that you have designed your algorithm to accomodate that, i.e. make it suitable for vectorised access. parallel prefix-sum would be an example of this). And without data-dependencies vectorized code is exactly equal to unvectorized code in all circumstances. If however, you do have data-dependencies, then your algorithm is wrong. Vectorizing can surface this error, while keeping it unvectorized may hide it. In my previous example (parallel prefix-sum) if you had a direct data-dependency to the previous index your program would've been wrong - regardless of vectorization. In short, while your statement is true in general, I believe that it is not applicable in the context of the discussion.
- drysine 2y agoThat's what the restrict type qualifier[0] is for. [0] https://en.cppreference.com/w/c/language/restrict https://en.cppreference.com/w/c/language/restrict
- bee_rider 2y agoWhen compiling a library, it is generally impossible for the compiler to know whether or not the pointers will be aliased, right? That decision is made after the library is already compiled.
- drwu 2y agoThe function declaration in the header file of the library can carry the required 'restrict'. It works for c++ invokers too, as most c++ compilers also support and check the __restrict__ for old plain pointer types.