3 ms·

> and is even faster (compiler is free to do the additions in any order) Is that actually true? I'm not even sure how hypothetically removing ordering requirem

> and is even faster (compiler is free to do the additions in any order) Is that actually true? I'm not even sure how hypothetically removing ordering requirements would help you extract performance, let alone any compilers that could do anything with that today. Unless the standard library were to auto-parallelize the reduction, but I doubt they'd do that because the overhead of starting threads would be quite costly for anything but the absolute largest ranges since C++ doesn't have a thread pool sitting idly for you (not to mention that the docs for the function don't mention any thread safety requirements for the BinaryOp and Init which would be required for any such optimization).

im3w1l 2y ago
I think relaxing the ordering requirement let's you use simd something like this (semi-pseudo code) (a, b, c, d) = (0, 0, 0, 0); for(int i = 0; i < n; i += 4) { (a, b, c, d) += (arr[i], arr[i+1], arr[i+2], arr[i+3]); } return a + b + c + d;
- mjcohen 2y ago
  What if n is not a multiple of 4? There is a trick I can't recall at the moment for handling this with a case statement on n mod 4 at the end to wrap this up.
  - jbboehr 2y ago
    I assume you're thinking of: https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device
- vlovich123 2y ago
  Are you sure that the compiler doesn’t autovectorize a simple loop into this form anyway? This is kind of the defacto scenario for that pass.
  - im3w1l 2y ago
    This transformation is only legal if order of summation doesn't matter. So the compiler can do it for ints, but not floats.
    - vlovich123 2y ago
      Applying std::reduce to floats would be a similarly bad idea for having the compiler do it, except people will write it without thinking. Of course, people always struggle with writing correct floating point so I doubt it makes things better or worse, but it’s conceptually the library equivalent of -fast-math (which coincidentally would also auto-vectorize the loop but can impact more than just that).
      - im3w1l 2y ago
        Using fast math in one particular expression is way different and less risky than doing it globally.
zarathustreal 2y ago
You answered the question yourself..can you at least edit your comment so you won’t confuse otherwise correctly oriented computer science practitioners? The commutative property is fundamental to understanding algebraic structures and fast parallel processing. If a binary operation is commutative over a given set then, yes, a proper compiler will parallelize it. No, it will not necessarily use OS threads directly one to one, that’s usually not a consideration even for a naive approach.
a_t48 2y ago
The linked page has benchmarks - I'd have to go dig into godbolt to see why it's faster. The standard library can actually auto-parallelize, but you have to opt in (see the ExecutionPolicy argument). Edit: I don't know how to dig into the actual implementation of std::reduce on godbolt - it's not inlined. I think the sibling comment has it right though - one can do adds of four at a time with whatever SIMD extensions are available.

im3w1l 2y ago

I think relaxing the ordering requirement let's you use simd something like this (semi-pseudo code) (a, b, c, d) = (0, 0, 0, 0); for(int i = 0; i < n; i += 4) { (a, b, c, d) += (arr[i], arr[i+1], arr[i+2], arr[i+3]); } return a + b + c + d;

mjcohen 2y ago
What if n is not a multiple of 4? There is a trick I can't recall at the moment for handling this with a case statement on n mod 4 at the end to wrap this up.
- jbboehr 2y ago
  I assume you're thinking of: https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device
vlovich123 2y ago
Are you sure that the compiler doesn’t autovectorize a simple loop into this form anyway? This is kind of the defacto scenario for that pass.
- im3w1l 2y ago
  This transformation is only legal if order of summation doesn't matter. So the compiler can do it for ints, but not floats.
  - vlovich123 2y ago
    Applying std::reduce to floats would be a similarly bad idea for having the compiler do it, except people will write it without thinking. Of course, people always struggle with writing correct floating point so I doubt it makes things better or worse, but it’s conceptually the library equivalent of -fast-math (which coincidentally would also auto-vectorize the loop but can impact more than just that).
    - im3w1l 2y ago
      Using fast math in one particular expression is way different and less risky than doing it globally.

zarathustreal 2y ago

You answered the question yourself..can you at least edit your comment so you won’t confuse otherwise correctly oriented computer science practitioners? The commutative property is fundamental to understanding algebraic structures and fast parallel processing. If a binary operation is commutative over a given set then, yes, a proper compiler will parallelize it. No, it will not necessarily use OS threads directly one to one, that’s usually not a consideration even for a naive approach.

a_t48 2y ago

The linked page has benchmarks - I'd have to go dig into godbolt to see why it's faster. The standard library can actually auto-parallelize, but you have to opt in (see the ExecutionPolicy argument). Edit: I don't know how to dig into the actual implementation of std::reduce on godbolt - it's not inlined. I think the sibling comment has it right though - one can do adds of four at a time with whatever SIMD extensions are available.