1

Alexander Stepanov stated in talks and interviews that his realization that eventually lead him to generic programming and the Standard Template Library, was from the case of the parallel reduction algorithm.

Why isn't there parallel_reduction(begin,end,associativeop) in the STL? Or something that could easily be turned into it with an operator overload (inner_product does only one pass and accumulate does the operations asymetrically). I could not even find such in the SGI-version, nor in the numeric section.

Examples of what I am thinking:

parallel reduction of [a,b,c,d,e,f,g,h] with binary operator ~ is

((a ~ b) ~ (c ~ d)) ~ ((e ~ f) ~ (g ~ h))

as opposed to accumulate

(((((((a+b)+c)+d)+e)+f)+g)+h)

and with inner_product you can get only

(a*e)+(b*f)+(c*g)+(d*h)

if I am not mistaken.

user1358
  • 341
  • 1
  • 7
  • Doesn't that imply that the argument is a 2^N element range? Other STL algorithms all work on any input, even `std::accumulate` on an empty range. – MSalters Apr 04 '14 at 15:58
  • @MSalters: no, eg: ((a ~ b) ~ (c ~ d)) ~ ((e ~ f) ~ g) is still not the same as ((((((a+b)+c)+d)+e)+f)+g) – user1358 Apr 04 '14 at 16:07
  • @MSalters: you simply leave the "remaining" to the "next round" – user1358 Apr 04 '14 at 16:08
  • @MSalters: for empty range, it would return identity element, just as accumulate – user1358 Apr 04 '14 at 16:09
  • You've got my curiosity piqued on this one. Looked up the original interview. Notably he was using this to make the point that [algorithms are defined on algebraic structures](http://www.stlport.org/resources/StepanovUSA.html), not that this was a crucial algorithm in and of itself. The biggest barrier I can think of is, "How do you store the intermediate variables efficiently?" With accumulate, you just need one. But here it seems like you need more than one. (?) I don't think the STL does this type of allocation, and reuse in this case would be a little odd, perhaps? Intel TBB has it. – J Trana May 21 '14 at 05:38

0 Answers0