7 ms·

Incrementing vectors

98 points by BeeOnRope 7y ago

totalperspectiv 7y ago
I'm trying to see if rustc does the same thing: https://godbolt.org/z/6WcYMf https://godbolt.org/z/6WcYMf but I am not good at reading this sort of thing. It looks like it has the same issue, but I didn't think rust had the type ambiguity that C++ does around u8 / char?
- totalperspectiv 7y ago
  rustc also doesn't vectorize it?
  - masklinn 7y ago
    It does if you use iterators as totalperspectiv did in their alternate version https://godbolt.org/z/JpwcRN https://godbolt.org/z/JpwcRN Because Rust bounds-checks indexes, which likely breaks LLVM's vectorisation (you'd have to reimplement vectorisation & vectorised bounds-checking in MIR for it to work I guess e.g. bounds-check the entire chunk before applying the vectorised operation).
- totalperspectiv 7y ago
  To answer both my own questions. Rust does not seem to have this same problem: https://godbolt.org/z/JpwcRN https://godbolt.org/z/JpwcRN But iterating over the loop with .iter_mut is different than iterating over 0..v.len(), which is interesting.
  - masklinn 7y ago
    I'm guessing its bounds-checking, though replacing v[i] += 1 by `*v.get_unchecked_mut(i) += 1` generates yet another bit of code (it seems to somewhat unroll the loop but stops there). Also you can use `-C target_cpu=native` and get AVX512 instructions on godbolt's.
- comex 7y ago
  Rust has no type-based aliasing restrictions at all. However, it does require references to be either unique or read-only, which means that it can automatically treat them as noalias (LLVM equivalent of __restrict). Unfortunately, this feature is disabled due to an LLVM bug: https://github.com/rust-lang/rust/issues/54878 https://github.com/rust-lang/rust/issues/54878 On the other hand, if you use the more idiomatic `&mut [u8]`, that passes the pointer and size by value, so it should avoid the issue. Edit: Using an iterator also avoids the problem, unlike in C++, because Rust iterators store their bounds within the iterator itself rather than calling iterable.end() on each iteration.
- lytigas 7y ago
  Regardless of what exactly rustc does right now, in the future Rust's strict aliasing rules will basically ensure Rust does this optimization in every possible case, because Rust reasons at compile time to ensure no mutable references ever alias. Things have been held up for a while on this LLVM bug, though[0]. [0] https://github.com/rust-lang/rust/issues/54878 https://github.com/rust-lang/rust/issues/54878
  - yoshuaw 7y ago
    Last I heard there's a fair chance that this might be implemented at the MIR level instead, allowing it to be unblocked from the LLVM bug.
heyiforgotmypwd 7y ago
More-so than the compiler, it depends on the design goals that are implemented in width and speed of the processor's registers, SIMD vector and conventional integer units. For x86, one could readily guess un/signed ints (32 & 64-bit) would be fast; un/signed 8/16-bit math is unlikely to be as fast. That hypothesis is backed-up by this article's data.
- tom_mellior 7y ago
  Did you read to the end? The final results show that in the end the computation on the vectors with 8-bit elements is 4x as fast (per element) as the computation on the vectors with 32-bit elements. EDIT ignore the following, I was mistaken: Infuriatingly the article doesn't benchmark signed 8-bit vectors. If the issue is due to the special aliasing properties of pointers to unsigned bytes, signed should just work really fast out of the box, without jumping through any hoops.
  - hoseja 7y ago
    Did you? it clearly states these aliasing rules apply to character types[0]. [0] https://travisdowns.github.io/blog/2019/08/26/vector-inc.html#fn:commoncom https://travisdowns.github.io/blog/2019/08/26/vector-inc.htm...
  - slavik81 7y ago
    The issue is due to the special properties of C character types, which include char, signed char and unsigned char. uint8_t and int8_t are not required to be character types, but they're typically implemented as typedefs of the char types, so they pick up the same properties. Here's the GCC bug discussing this problem: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66110 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66110
    - tom_mellior 7y ago
      Thanks. I misremembered C's rules as only unsigned char having this special property (as well as plain char if it's unsigned), but not signed char.
slavik81 7y ago
Ugh. Aliasing rules in C/C++ are very unfortunate, but it's hard to tighten the rules after the fact. Related: The Strict Aliasing Situation is Pretty Bad (2016) https://blog.regehr.org/archives/1307 https://blog.regehr.org/archives/1307
- pingyong 7y ago
  >but it's hard to tighten the rules after the fact. Depends on what you mean by tighten the rules. If you tighten the rules for the optimizer by simply allowing everything to alias, that should not introduce bugs into currently well formed programs. (Except that they might be slower.)
miga 7y ago
What about AVX? https://stackoverflow.com/questions/41086366/how-to-increment-a-vector-in-avx-avx2 https://stackoverflow.com/questions/41086366/how-to-incremen... `-mavx2`?
- stagger87 7y ago
  What about it?
amelius 7y ago
The essence: > That means that writes through uint8_t pointers are treated as potentially updating any memory of unknown provenance. So the compiler assumes that every increment v[i]++ potentially modifies size() and hence must recalculate size() every iteration. However, I think that a smart compiler would still be able to sort out that size() is not affected by such writes.
- gpderetta 7y ago
  how, without whole program compilation? edit: specifically for std vector, the implementer could somehow hardcode the knowledge that size can never alias with the buffer, but that would be ad hoc and won't extend to user defined containers, which seems suboptimal.
  - OskarS 7y ago
    std::vector is entirely defined in a header file (it has to be, it's a template), so whole program optimization (which is what I presume you mean?) doesn't enter into it. The entire definition of vector is within the same translation unit. I don't know enough about compiler optimization algorithms to say how trivial it would be to figure out these two things don't alias, but when you have a type with the magic property "this guy is allowed to alias ANYTHING", then I imagine it gets pretty tricky.
    - gpderetta 7y ago
      Definition of the type is not enough, the compiler need to track the origin of all pointer values, which means it needs to 'see', recursively, all callers of the function it is optimizing up to the point where the parameter objects were originally constructed, plus any function where a pointer to the object might potentially escape to (which might be potentially any function, if it escapes to the heap). And that might still not be enough: passing the vector by value still doesn't trigger the optimization in GCC and clang (but it does for a bare bone vector implementation, probably std vector itself ends up leaking its own internals). > when you have a type with the magic property "this guy is allowed to alias ANYTHING", then I imagine it gets pretty tricky. well, yes, that's the whole point of the article :)
gpderetta 7y ago
re Disappointment, the somewhat portable #pragma GCC ivdep in theory would help in a lot of cases. In this specific case, the compiler should be able to assume that a previous write cannot affect the next read from the size field, but it seems that neither GCC nor clang take advantage of it.
- BeeOnRope 7y ago
  > the compiler should be able to assume that a previous write cannot affect the next read from the size field, but it seems that neither GCC nor clang take advantage of it. Why? Good point about #pragma ivdep. I feel like the semantics of that one are a bit less than rigorous, but it's a useful tool.
  - gpderetta 7y ago
    Why they do not take advantage ov ivdep? I don't know. I thought it was because the size address was not a function of the iteration variable, but even by artificially adding the dependency (with a barebone vector implementation) does not seem to trigger the optimization.
    - BeeOnRope 7y ago
      I mean why "should [the compiler] be able to assume that a previous write cannot affect the next read from the size field"? It's not that the size field is a function of the iteration variable (i?) but that the previous write may have overwritten the size field, because the size field is located at some arbitrary place in memory, and the array backing the vector is located at some other arbitrary place and they may overlap (but only because the vector type is uint8_t/char - if it other than a char type the compiler can be sure they don't overlap because the size() fields are pointers which have a distinct type from uint32_t and are not subject to the "char aliasing loophole" rule).
      - gpderetta 7y ago
        sure, but ivdep is supposed to explicitly tells the compiler that there are no loop carried dependencies between iterations, so iteration i-1 couldn't possibly write to a memory location read by iteration i.
mihaitodor 7y ago
@BeeOnRope Regarding comments on the blog, have you considered using https://utteranc.es/ https://utteranc.es/? It stores them as GitHub issues. I think https://staticman.net/ https://staticman.net/ does something similar.
dragontamer 7y ago
Oh, its BeeOnRope. I was wondering who could have investigated this detail to such fine degree. No comments really, your blogpost seems to answer all my questions. Excellent work!

98 points by BeeOnRope 7y ago

I'm trying to see if rustc does the same thing: https://godbolt.org/z/6WcYMf https://godbolt.org/z/6WcYMf but I am not good at reading this sort of thing. It looks like it has the same issue, but I didn't think rust had the type ambiguity that C++ does around u8 / char?

totalperspectiv 7y ago
rustc also doesn't vectorize it?
- masklinn 7y ago
  It does if you use iterators as totalperspectiv did in their alternate version https://godbolt.org/z/JpwcRN https://godbolt.org/z/JpwcRN Because Rust bounds-checks indexes, which likely breaks LLVM's vectorisation (you'd have to reimplement vectorisation & vectorised bounds-checking in MIR for it to work I guess e.g. bounds-check the entire chunk before applying the vectorised operation).
totalperspectiv 7y ago
To answer both my own questions. Rust does not seem to have this same problem: https://godbolt.org/z/JpwcRN https://godbolt.org/z/JpwcRN But iterating over the loop with .iter_mut is different than iterating over 0..v.len(), which is interesting.
- masklinn 7y ago
  I'm guessing its bounds-checking, though replacing v[i] += 1 by `*v.get_unchecked_mut(i) += 1` generates yet another bit of code (it seems to somewhat unroll the loop but stops there). Also you can use `-C target_cpu=native` and get AVX512 instructions on godbolt's.
comex 7y ago
Rust has no type-based aliasing restrictions at all. However, it does require references to be either unique or read-only, which means that it can automatically treat them as noalias (LLVM equivalent of __restrict). Unfortunately, this feature is disabled due to an LLVM bug: https://github.com/rust-lang/rust/issues/54878 https://github.com/rust-lang/rust/issues/54878 On the other hand, if you use the more idiomatic `&mut [u8]`, that passes the pointer and size by value, so it should avoid the issue. Edit: Using an iterator also avoids the problem, unlike in C++, because Rust iterators store their bounds within the iterator itself rather than calling iterable.end() on each iteration.
lytigas 7y ago
Regardless of what exactly rustc does right now, in the future Rust's strict aliasing rules will basically ensure Rust does this optimization in every possible case, because Rust reasons at compile time to ensure no mutable references ever alias. Things have been held up for a while on this LLVM bug, though[0]. [0] https://github.com/rust-lang/rust/issues/54878 https://github.com/rust-lang/rust/issues/54878
- yoshuaw 7y ago
  Last I heard there's a fair chance that this might be implemented at the MIR level instead, allowing it to be unblocked from the LLVM bug.

heyiforgotmypwd 7y ago

More-so than the compiler, it depends on the design goals that are implemented in width and speed of the processor's registers, SIMD vector and conventional integer units. For x86, one could readily guess un/signed ints (32 & 64-bit) would be fast; un/signed 8/16-bit math is unlikely to be as fast. That hypothesis is backed-up by this article's data.

tom_mellior 7y ago
Did you read to the end? The final results show that in the end the computation on the vectors with 8-bit elements is 4x as fast (per element) as the computation on the vectors with 32-bit elements. EDIT ignore the following, I was mistaken: Infuriatingly the article doesn't benchmark signed 8-bit vectors. If the issue is due to the special aliasing properties of pointers to unsigned bytes, signed should just work really fast out of the box, without jumping through any hoops.
- hoseja 7y ago
  Did you? it clearly states these aliasing rules apply to character types[0]. [0] https://travisdowns.github.io/blog/2019/08/26/vector-inc.html#fn:commoncom https://travisdowns.github.io/blog/2019/08/26/vector-inc.htm...
- slavik81 7y ago
  The issue is due to the special properties of C character types, which include char, signed char and unsigned char. uint8_t and int8_t are not required to be character types, but they're typically implemented as typedefs of the char types, so they pick up the same properties. Here's the GCC bug discussing this problem: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66110 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66110
  - tom_mellior 7y ago
    Thanks. I misremembered C's rules as only unsigned char having this special property (as well as plain char if it's unsigned), but not signed char.

slavik81 7y ago

Ugh. Aliasing rules in C/C++ are very unfortunate, but it's hard to tighten the rules after the fact. Related: The Strict Aliasing Situation is Pretty Bad (2016) https://blog.regehr.org/archives/1307 https://blog.regehr.org/archives/1307

pingyong 7y ago
>but it's hard to tighten the rules after the fact. Depends on what you mean by tighten the rules. If you tighten the rules for the optimizer by simply allowing everything to alias, that should not introduce bugs into currently well formed programs. (Except that they might be slower.)

miga 7y ago

What about AVX? https://stackoverflow.com/questions/41086366/how-to-increment-a-vector-in-avx-avx2 https://stackoverflow.com/questions/41086366/how-to-incremen... `-mavx2`?

stagger87 7y ago
What about it?

amelius 7y ago

The essence: > That means that writes through uint8_t pointers are treated as potentially updating any memory of unknown provenance. So the compiler assumes that every increment v[i]++ potentially modifies size() and hence must recalculate size() every iteration. However, I think that a smart compiler would still be able to sort out that size() is not affected by such writes.

gpderetta 7y ago
how, without whole program compilation? edit: specifically for std vector, the implementer could somehow hardcode the knowledge that size can never alias with the buffer, but that would be ad hoc and won't extend to user defined containers, which seems suboptimal.
- OskarS 7y ago
  std::vector is entirely defined in a header file (it has to be, it's a template), so whole program optimization (which is what I presume you mean?) doesn't enter into it. The entire definition of vector is within the same translation unit. I don't know enough about compiler optimization algorithms to say how trivial it would be to figure out these two things don't alias, but when you have a type with the magic property "this guy is allowed to alias ANYTHING", then I imagine it gets pretty tricky.
  - gpderetta 7y ago
    Definition of the type is not enough, the compiler need to track the origin of all pointer values, which means it needs to 'see', recursively, all callers of the function it is optimizing up to the point where the parameter objects were originally constructed, plus any function where a pointer to the object might potentially escape to (which might be potentially any function, if it escapes to the heap). And that might still not be enough: passing the vector by value still doesn't trigger the optimization in GCC and clang (but it does for a bare bone vector implementation, probably std vector itself ends up leaking its own internals). > when you have a type with the magic property "this guy is allowed to alias ANYTHING", then I imagine it gets pretty tricky. well, yes, that's the whole point of the article :)

gpderetta 7y ago

re Disappointment, the somewhat portable #pragma GCC ivdep in theory would help in a lot of cases. In this specific case, the compiler should be able to assume that a previous write cannot affect the next read from the size field, but it seems that neither GCC nor clang take advantage of it.

BeeOnRope 7y ago
> the compiler should be able to assume that a previous write cannot affect the next read from the size field, but it seems that neither GCC nor clang take advantage of it. Why? Good point about #pragma ivdep. I feel like the semantics of that one are a bit less than rigorous, but it's a useful tool.
- gpderetta 7y ago
  Why they do not take advantage ov ivdep? I don't know. I thought it was because the size address was not a function of the iteration variable, but even by artificially adding the dependency (with a barebone vector implementation) does not seem to trigger the optimization.
  - BeeOnRope 7y ago
    I mean why "should [the compiler] be able to assume that a previous write cannot affect the next read from the size field"? It's not that the size field is a function of the iteration variable (i?) but that the previous write may have overwritten the size field, because the size field is located at some arbitrary place in memory, and the array backing the vector is located at some other arbitrary place and they may overlap (but only because the vector type is uint8_t/char - if it other than a char type the compiler can be sure they don't overlap because the size() fields are pointers which have a distinct type from uint32_t and are not subject to the "char aliasing loophole" rule).
    - gpderetta 7y ago
      sure, but ivdep is supposed to explicitly tells the compiler that there are no loop carried dependencies between iterations, so iteration i-1 couldn't possibly write to a memory location read by iteration i.

mihaitodor 7y ago

@BeeOnRope Regarding comments on the blog, have you considered using https://utteranc.es/ https://utteranc.es/? It stores them as GitHub issues. I think https://staticman.net/ https://staticman.net/ does something similar.

dragontamer 7y ago

Oh, its BeeOnRope. I was wondering who could have investigated this detail to such fine degree. No comments really, your blogpost seems to answer all my questions. Excellent work!