The reducers library (in the clojure.core.reducers namespace) has alternative implementations of map, filter, and other seq functions. These alternative functions are called reducers, and you can apply almost everything you know about seq functions to reducers. Just like seq functions, the purpose of reducers is to transform collections. For example, if you wanted to increment every number in a vector, filter out the even ones, and sum the numbers, the seq and reducer versions look virtually identical:

[[seq functions and reducers are identical in many ways]]

In both examples, (range 10) returns a seq of the numbers 0 through 9. In the first example, map is a seq function. In the second, r/map is a reducer. In both examples, map has the same purpsose: transforming an input collection to an output by applying a function to each element of the input. Reducers are just another means of transforming collections, and for the most part they’re used just like the seq functions you already know and love.

So why bother with them? Reducers are designed to perform better (often dramatically better) than seq functions under some circumstances by performing eager computation, eliminating intermediate collections and allowing parallelism.

In fact, as far as I can tell, parallelization is the main reason Rich Hickey, Lambda Whisperer added reducers to the language. The goal of executing collection transformations in parallel completely determined how reducers are designed, and even explains why we use the term reducers: reduce operations can be trivially parallellized (you’ll learn how by the end), and every collection transformation can be expressed in terms of reduce (there’s a big juicy math paper on that).

Thus, the reducers library is built around using reduce to transform collections, and it’s designed this way to make parallelization possible. Both eager computation and the elimination of intermediate collections are secondary - but useful - consequences of this design. (By the way: "elimination of intermediate collections" is a freaking mouthful, so I’m going to start using EIC).

Let’s look at these three strategies more closely. After that, I’ll out the rules for how to ensure that your code makes use of each of them, without going into much detail about why they work as they do. Last, I’ll also give some examples of reducers at work, showing how their performance compares to alternatives.

Understanding the reduce library’s three performance strategies - eager computation, EIC, and parallelism - will give you the rationale behind reducers, and that will help you understand their implementation later on. Plus, these ideas are pretty groovy in their own right. I know you’re eager to learn about eager computation, so let’s go!

You’ve seen how, for the most part, you can use reducers just like seq functions. For example, this produces the same result as the seq counterpart:

[[quick reducer example]]

There are a couple rules to keep in mind, though. First, if you want to make use of parallelism, you have to use the r/fold function with a foldable collection. r/fold is a parrallel implementation of reduce.

I need to explain parallelism a bit more before explaining what foldable means, but for now the relevant fact is that vectors and maps are the only foldable collections. So if you wrote code like this, you might expect it to run in parallel, but it wouldn’t:

[[only foldable collections can be parallelized]]

Lists aren’t foldable, so reducers can’t operate on them in parallel. Instead, the code falls back to serial reduce.

The second rule is that reducers actually don’t produce any collections. It’s awesome that r/map and r/filter compose without creating intermediate collections, but the catch is that they behave a little differently from seq functions. Here’s one way you could get tripped up:

[[sad broken bode]]

This happens because r/map and the other reducers don’t actually return a new collection. Instead, they return a reducible.

A reducible is like a recipe for how to produce a new collection, along with a reference to a source collection. In the above example, the recipe is "produce a new collection by incrementing each element each element of the source collection", and the source collection is the vector [1 2 3].

Another way to put it: a reducible is an elemental function, along with the collection whose elements you want to apply the function to.

And yet another way to put it: It’s as if you were one of Santa’s worker elves (or some other mythical creature of labor), and the foreman handed you a piece of paper with your instructions for the day: "Go to the plastic shed out back, get all the plastic lumps and turn them into toy whatevers to feed to the insatiable, gaping maw of consumerism."

If I then walked up to you and said, "give me the first of that piece of paper", you would look at me in confusion, because the request wouldn’t make any sense. The piece of paper is not a collection that you can take the first of. Similarly, when you tell Clojure (first (r/map inc [1 2 3])) it expresses its confusion with an exception because the request doesn’t make sense.

You might initially think you’re telling Clojure "give me the first element of the collection returned by r/map", but you’re actually saying "give me the first element of the reducible returned by r/map". A reducible is a recipe for how to transform a given collection, but it’s not a collection itself, so Clojure can’t fulfill your request.

This design decision to have functions like r/map return a reducible instead of a collection is what allows reducers to seamlessly compose, building up a single fused elemental function. I’ll explain exactly how this happens later in the article, and for now rely on the power of metaphor so that you’ll have a strong intuitive understanding of how it works.

But you need to get collections somehow. If you want to use reducer functions to produce another collection, you have to explicitly realize the result collection by calling r/foldcat or clojure.core/into. r/foldcat calls r/fold internally, and into calls reduce. Here are two examples:

[[successful reducer collection realization]]

(→> [1 2 3 4] (r/map inc) (r/foldcat) (first)) ; ⇒ 2 ---

You should use into when you want to explicitly specify the collection type. In the example above, you’re realizing the collection as a vector. into is serial.

r/foldcat executes parallelly (is that a word?) and returns a collection that acts pretty much like a vector. The collection is foldable, so you can use it with reducers in further parallel computations. It’s also seqable, like a vector, so you can call functions like first on it.

To summarize the rules:

Soooo now that you’ve spent all this time learning about reducers' performance strategies and how to use them, let’s wrap everything together by comparing reducer performance to seq functions. If I’ve done my job right, you won’t be surprised by the differences. If I haven’t done my job right, then, well…​ sorry?

To see the performance impact of these variables, we’re going to look at similar computations performed using r/fold (for parallelism and EIC), r/reduce (for EIC alone), and clojure.core/reduce as a baseline. We’ll also perform the computations on foldable collections (vectors) and on unfoldable collections (lazy seqs).

You can find the code for this section at …​ After doing the performance measurements for awhile, I wanted to make the process a bit less tedious, so I wrote the macro times and its helper functions pretty-time and runs-and-pauses to abstract the process of running a snippet multiple times, timing each run, averaging those time values, and usefully printing the result. This lets you do something like this:

[[times macro example]]

The code for times is the first thing to greet you, but I’m going to go over it here for fear that you would (justifiably) shake your first at me from behind your monitor for veering off topic.

Here are our first comparisons:

[[Comparing performance for computationally simple ops]]

(def snums (range 10000000)) ; <1> (def snumsv (vec snums))

(defn t1 [x] (times (r/fold + x) (r/reduce + x) (reduce + x)))

(defn t2 [x] (times (→> x (r/map inc) (r/fold +)) (→> x (r/map inc) (r/reduce +)) (→> x (map inc) (reduce +))))

(defn t3 [x] (times (→> x (r/filter even?) (r/map inc) (r/fold +)) (→> x (r/filter even?) (r/map inc) (r/reduce +)) (→> x (filter even?) (map inc) (reduce +)))) ---

First, we define two collections of numbers from 0 to 99,999,999. snums is an unfoldable seq and snumsv is a foldable vector.

Next, we define three functions, t1, t2, and t3. Each function takes a collection (we’ll use snums and snumsv), transforms it using r/fold, r/reduce, and reduce, and prints out how much time each transformation takes. Enough with the yik yak, let’s actually use them:

[[timing a simple reduce]]

(t1 snumsv) ; ⇒ " 59.15 (r/fold + x)" ; ⇒ " 164.32 (r/reduce + x)" ; ⇒ " 148.15 (reduce + x)" ---

When we call t1 with snums, the three reduction functions have roughly the same performance. Put another way: we don’t get any performance benefits from EIC or parallelism. This makes sense because we’re not doing a map, filter, or some other function that semantically returns a new collection. We’re also using the unfoldable snums, and in that case r/fold quietly degrades to r/reduce.

When we call t2 with snumsv, though, we see a significant speedup from r/fold. My computer has four cores, so ideally r/fold would take 25% as much time as the serial versions, but it’s rare to meet that ideal because parallelization has overhead costs.

Let’s see what happens when we have an intermediate transformation (map):

[[reduce with an intermediate transformation]]

Dayumn! The reducer versions take nearly fifty percent less time! There’s no difference between r/fold and r/reduce, though, becuase we’re not using a foldable collection. Here’s what happens when you change that:

[[reduce with an intermediate collection and foldable source]]

Here, r/fold is five times faster than reduce, thanks to EIC and parallelism. (Interestingly, it seems serial reduce takes a bit longer with vectors.)

What happens if you have two intermediate collections? This happens:

[[reduce with two intermediate collections]]

(t3 snumsv) " 71.96 (→> x (r/map inc) (r/filter even?) (r/fold +))" " 207.47 (→> x (r/map inc) (r/filter even?) (r/reduce +))" " 478.25 (→> x (map inc) (filter even?) (reduce +))" ---

TODO fix this paragraph, too wordy

When you call r/fold with a vector, it’s almost seven times faster. Not only that, reducer performance doesn’t dramatically degrade with more intermediate transformations as it does with the seq functions; adding the additional r/filter doesn’t seem to affect performance at all. I’m sure if we added a computationally intensive transformation then performance would naturally suffer, but it would be from the transformation and not the construction of an intermediate collection.

The reason we need to care about concurrent and parallel programming techniques is that computer hardware manufacturers have run into three fundamental limitations, imposed by physics, that won’t be overcome any time soon — if ever. Because of these limitations, we can no longer …​ The limitations are known as:

The Power Wall is a limitation on CPU clock speeds. You’ve probably noticed that clock speeds have barely inched forward over the last decade, compared to the rapid progress of previous decades where clock speeds followed Moore’s law and doubled every eighteen months. The reason for this near halt in progress is that chip designs have reached a point where increasing clock speed results in exponential increases in power consumption and heat, and no one wants to buy a computer that costs as much to run as a UNIVAC.

Even if clock speeds could be increased, the hardware would still have to contend with the Memory Wall, which is the extreme disparity between memory access time and CPU performance — CPUs can process instructions much faster than they can fetch them from main memory. Increasing clock speed would be like TODO analogy.

TODO mention this is why we need explicit parallel techniques TODO that the code we write is often serial even though it can be considered parallel

The final limitation, the Instruction-Level Parallelism (ILP) Wall is a limitation on the level of parallelism that can be extracted from serial (non-parallel) instructions. Much of the hullabaloo around parallelism has focused on the fact that we’re stuffing more cores into CPU’s, but in fact, even old-timey single-core machines have parallel aspects to their architectures and are capable of running serial instructions in parallel, to an extent. In fact, hardware can automatically parallelize serial instructions to an extent.

In an ideal world, hardware would be smart enough to automatically parallelize everything that can be parallelized, but the fact is they can’t, and it looks like there won’t be any significant improvements any time soon.

Because of these three limitations, chip manufacturers have focused on developing multi-core process instead of increasing clock speed. In order to get the most performance out of these processors, we have to structure our applications differently.

TODO explain the "task" abstraction

Concurrent and Parallel programming refer to the tools and techniques you use to program for multiple processors. Concurrency refers to a system’s ability to manage more than one task at a time, while parallelism refers to a system’s ability to execute more than one task at a time. From this perspective, parallelism is a sub-category of concurrency.

Programmers usually the term concurrency when referring to multiple, independent tasks with access to shared state. For example, TODO example. Parallelism usually refers to decomposing a collection of data into smaller chunks, processing those, and reassembling the results. In this situation, there’s no logical need for shared access to state. Of course, you have to keep track of all of the different computations.

TODO talk about threading and scheduling

Latency is the amount of time it takes to complete a task, and is what we usually care about most because it has the most direct impact on user experience. One example is network latency, or the amount of time it takes for a packet to reach its destination. If you’re measuring the amount of time it takes to open a file or execute a function or generate a report, those are all latency.

You can measure latency at any level of granularity. For example, if you make web sites you’ve probably measured the total time it takes to load a web page to decide if it needs optimization. At first, you only care about the "load the page" task as a whole. If you discover it’s too slow, then you can drill down to individual network requests to see what’s causing problems. Drilling down further, you might find that your SQL queries are taking a long time because your tables aren’t indexed properly, or something like that.

Most of this article focuses on how to effectively reduce latency with parallel programming.

Throughput is the number of tasks per second that your system can perform. Your web server, for example, might be able to complete 1,000 requests per second.

TODO EXPAND There’s a direct relationship between latency and throughput. Let’s say you’re running the world’s lousiest web server, and it can only handle one request per second. If a thousand people make a request to this server at the same time, then on average it will take 500 seconds to respond to a request.

Utilization is the degree to which a resource is used. It has two flavors, capacity-based utilization and time-based utilization. In this article we only care about the time-based flavor, which is a measure of how busy a resource is over a given unit of time. Specifically, we care about CPU utilization, which is the percentage of time that your CPU is doing work divided by some unit of time.

One of the challenges with parallel programming is figuring how to make efficient use of resources by ensuring that we reduce unnecesary CPU idle time. Later in the article, you’ll learn about techniques that help you do this, including the powerful Fork/Join framework.

TODO Speedup

There are three concurrent/parallel programming general strategies you can use to help improve performance: latency hiding, functional decomposition, and data parallelism. Guess what’s coming next! That’s right, I’m going to explain those things!

The work-span model is concerned with two aspects of a parallel algorithm: its work and its span. Work is the total number of tasks that need to be completed, and span is the length of the longest path of work that has to be done serially. Take a look at this diagram:

In the example on the left, the work is 9 because there are 9 tasks that need to be completed, and the span is 5 because there are 5 tasks that have to be performed serially.

The span describes the upper limit to the amount of speedup you can expect; past that, no amount of additional hardware will help your algorithm run faster.

The work-span model reveals an important difference between serial and parallel algorithms. With serial algorithms, performance is determined by the total amount of work that needs to be done; you improve performance by reducing work. By contrast, the parallel performance is determined by the span. In fact, with some algorithms you actually improve performance by performing more work. You can see this in the diagram for scan:

In the serial version of scan, there are 7 tasks. In the parallel version, there are 11, but the span is only 3, so the parallel version would complete before the serial version.

TODO explain "potential parallelism" The work-span model assumes an ideal machine where there are no costs involved in running tasks in parallel. If you tried to write your Clojure program as if there were no penalty for creating threads, then you’d quickly run into trouble. From Java Concurrency in Practice:

TODO mention that abundant threads leads to slowdown

TODO metaphor time, maybe group project in school Because threads are expensive, you might say to yourself, "No problem! I’ll just create one thread per thread core and divide the work among them." But that can cause load balancing problems. Imagine that you have four cores, and a map operation divided among threads A, B, C, and D. Now imagine that for some reason thread A is taking a signifanct amount of time on one of the map function applications. Threads B, C, and D have to just wait idly for A to finish.

So, in real programs, you’re concerned with balancing the need to limit thread creation, scheduling, and synchronization, and the need to balance the workload.

Some of the approaches available to deal with these concerns are thread management, granularity, parallel slack, and fusion. Let’s look at those.

The fork/join strategy works by recursively breaking down some task into subtasks until some base condition is met, and then adding those subtasks to a queue. Fork/join also involves combining the results of the subtask results. Fork/join refers to this process of splitting and combining.

You want to include all transformations in the base case, performing fusion. Tiling is handled through recursive decomposition.

Work stealing is interesting: the fork/join framework employes a double-ended queue (deque). The queue is sorted by task complexity. Each worker thread pulls from the least-complex end of its own queue. If a worker finishes, it "steals" work from the most-complex end of another worker.