challenge #2: implement the varargs_reduce metafunction

[Andrei Alexandrescu (See Website For Email)]

janderson wrote:
> Andrei Alexandrescu (See Website for Email) wrote:
>> My previous post defines max by availing itself of a metafunction called
>> varargs_reduce. Your challenge is to define it. varargs_reduce takes an
>> alias which it assumes is a function of two arguments, and it defines a
>> vararg function that applies that alias repeatedly, similarly to the
>> reduce primitive that is present in functional languages. Again, for
>> background on functional reduce, see e.g.:
>>
>> http://www.joelonsoftware.com/items/2006/08/01.html
>>
>> Define varargs_reduce to deduce the result type properly, and to 
>> generate code as efficient as possible.
>>
>>
>> Andrei
> 
> 
> While your at it.  What about a multi-threaded version?   ie Each 
> function that is called is placed on one of 4 threads.

That's a good point, and goes right to the core of my solution, which 
(similarly to Bruno Medeiros') arranges operations in an optimal way for 
superscalar evaluation, e.g. max(a, b, c, d) is expanded not to:

max2(max2(max2(a, b), c), d)

but instead to:

max2(max2(a, b), max2(c, d))

The number of operations is the same but in the latter case there is 
logaritmically less dependency between partial results. When max2 
expands into a primitive comparison, the code is easy prey for a 
superscalar machine to execute in parallel.

This won't count in a great deal of real code, but the fact that this 
will go in the standard library warrants the thought. Besides, the fact 
that the language makes it so easy, we can actually think of such 
subtlety, is very encouraging.


Andrei