9e. Reductions

Introduction

Reductions are a computational technique for operations taking a collection as input and returning a single element as output. Such operations arise naturally in a wide range of contexts, such as when computing summary statistics (e.g., averages, variances, or maxima of collections).

The underlying technique involves iteratively applying an operation to pairs of elements, accumulating the results at each step until the final output is obtained. A classic example of reduction is the summation of all numeric elements in a vector. It arrives at the final result by applying the addition operator + to pairs of elements, iteratively updating the accumulated sum. This case is illustrated below.

x = rand(100)

foo(x) = sum(x)

48.447

x = rand(100)

function foo(x)
    output = 0.

    for i in eachindex(x)
        output = output + x[i]
    end

    return output
end

48.447

x = rand(100)

function foo(x)
    output = 0.
    
    for i in eachindex(x)
        output += x[i]
    end

    return output
end

48.447

The last tab implements the reduction via an update operator. These operators are frequently used in reductions because they streamline notation, rewriting expressions like x = x + a in the more compact form x += a.

The main benefit of reductions is that, by operating on scalars, they don't create memory allocations. This is particularly convenient when a vector must be transformed prior to aggregating the result. For instance, if you have to compute sum(log.(x)), a reduction would avoid the allocations of the intermediate vector log.(x).

Avoiding Memory Allocations through Reductions

One of the primary advantages of reductions is their avoidance of memory allocation, in particular for intermediate results.

To illustrate, consider the operation sum(log.(x)) for a vector x. Its computation involves two steps: transforming x into log.(x), and then summing the transformed elements. By default, broadcasting materializes its results, implying the internal creation of a new vector to store the values of log.(x). Consequently, the step results in memory allocations.

In many cases, however, only the scalar output matters, with the intermediate result being of no interest. In this context, computational strategies that obtain the final output while bypassing the allocation of log.(x) are preferred.

Reductions make this possible by defining a scalar output, which is iteratively updated by summing the transformed values of x. This means that each element of x is transformed by the logarithm, and the result is then immediately added to the accumulator. In this way, the storage of the intermediate vector log.(x) is entirely avoided. [note] In the section Lazy Operations, we'll explore an alternative approach. This is based on broadcasting and also avoids materializing intermediate results.

x = rand(100)

foo1(x) = sum(log.(x))

function foo2(x)
    output = 0.

    for i in eachindex(x)
        output += log(x[i])
    end

    return output
end

  315.584 ns (1 allocation: 896 bytes)

  296.119 ns (0 allocations: 0 bytes)

x = rand(100)

foo1(x) = prod(log.(x))

function foo2(x)
    output = 1.

    for i in eachindex(x)
        output *= log(x[i])
    end

    return output
end

  311.840 ns (1 allocation: 896 bytes)

  296.061 ns (0 allocations: 0 bytes)

x = rand(100)

foo1(x) = maximum(log.(x))

function foo2(x)
    output = -Inf

    for i in eachindex(x)
        output = max(output, log(x[i]))
    end

    return output
end

  482.602 ns (1 allocation: 896 bytes)

  374.961 ns (0 allocations: 0 bytes)

x = rand(100)

foo1(x) = minimum(log.(x))

function foo2(x)
    output = Inf
    
    for i in eachindex(x)
        output = min(output, log(x[i]))
    end

    return output
end

  487.156 ns (1 allocation: 896 bytes)

  368.502 ns (0 allocations: 0 bytes)

The "reduce" and "mapreduce" Functions

Beyond the specific cases discussed, reductions are applicable whenever a binary operation meets the necessary conditions for their implementation. To accommodate this generality, Julia provides the functions reduce and mapreduce.

The reduce function applies a binary operation directly to the elements of a collection, combining them into a single result. By contrast, mapreduce first transforms each element before applying the reduction.

It's worth remarking that reductions for sums, products, maximum, and minimum should still be implemented via their dedicated functions. This is because the methods in sum, prod, maximum, and minimum have been carefully optimized for their respective tasks, typically outperforming the general functions reduce and mapreduce. [note] The functions reduce and mapreduce are also convenient for packages that implement specialized versions of reductions. By simply defining these two functions, the package can then cover all possible reductions. For instance, the package Folds provides a multithreaded version of reductions via map and mapreduce.

Function "reduce"

The function reduce uses the syntax reduce(<function>,x), where <function> is a two-argument function.

x      = rand(100)

foo(x) = reduce(+, x)           #same output as sum(x)

  6.168 ns (0 allocations: 0 bytes)

x      = rand(100)

foo(x) = reduce(*, x)           #same output as prod(x)

  6.176 ns (0 allocations: 0 bytes)

x      = rand(100)

foo(x) = reduce(max, x)         #same output as maximum(x)

  167.905 ns (0 allocations: 0 bytes)

x      = rand(100)

foo(x) = reduce(min, x)         #same output as minimum(x)

  167.440 ns (0 allocations: 0 bytes)

Note that all the examples above could've been implemented as before, where we directly applied sum, prod, maximum and minimum.

Function "mapreduce"

The mapreduce function integrates map and reduce into a unified operation (hence its name). Thus, it applies a transformation via the function map before doing the reduction. Its syntax is mapreduce(<transformation>,<reduction>,x). To illustrate its use, we make use of a log transformation.

x      = rand(100)

foo(x) = mapreduce(log, +, x)       #same output as sum(log.(x))

  294.805 ns (0 allocations: 0 bytes)

x      = rand(100)

foo(x) = mapreduce(log, *, x)       #same output as prod(log.(x))

  294.618 ns (0 allocations: 0 bytes)

x      = rand(100)

foo(x) = mapreduce(log, max, x)     #same output as maximum(log.(x))

  579.808 ns (0 allocations: 0 bytes)

x      = rand(100)

foo(x) = mapreduce(log, min, x)     #same output as minimum(log.(x))

  577.505 ns (0 allocations: 0 bytes)

Note that, again, the examples could've been implemented directly through the functions sum, prod, maximum, and minimum as we did previously.

mapreduce can also be used with anonymous functions and functions with multiple arguments. Below, we illustrate these possibilities.

x = rand(100); y = rand(100)

foo(x,y) = mapreduce(a -> a[1] * a[2], +, zip(x,y))       #same output as sum(x .* y)

  29.165 ns (0 allocations: 0 bytes)

x = rand(100); y = rand(100)

foo(x,y) = mapreduce(a -> a[1] * a[2], *, zip(x,y))       #same output as prod(x .* y)

  48.221 ns (0 allocations: 0 bytes)

x = rand(100); y = rand(100)

foo(x,y) = mapreduce(a -> a[1] * a[2], max, zip(x,y))     #same output as maximum(x .* y)

  175.634 ns (0 allocations: 0 bytes)

x = rand(100); y = rand(100)

foo(x,y) = mapreduce(a -> a[1] * a[2], min, zip(x,y))     #same output as minimum(x .* y)

  166.995 ns (0 allocations: 0 bytes)

reduce or mapreduce?

mapreduce(<transformation>,<operator>,x) yields the same result as reduce(<operator>, map(<transformation>,x)). Despite this, mapreduce is preferred if the vector input must be transformed beforehand. The reason is that mapreduce avoids the internal memory allocations of the transformed vector, while map doesn't. This aspect is demonstrated below, where sum(2 .* x) is computed through a reduction.

x = rand(100)

foo(x) = mapreduce(a -> 2 * a, +, x)

  6.372 ns (0 allocations: 0 bytes)

x = rand(100)

foo(x) = reduce(+, map(a -> 2 * a, x))

  43.476 ns (1 allocation: 896 bytes)