Hacker News Reader

Comment by vlovich123 | Hacker News Reader

> 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).

View on HN

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;

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.

I assume you're thinking of: https://en.wikipedia.org/wiki/Duff%27s_device

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.

This transformation is only legal if order of summation doesn't matter. So the compiler can do it for ints, but not floats.

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).

Using fast math in one particular expression is way different and less risky than doing it globally.

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.

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.

Reply on news.ycombinator.com