Transduction benchmarks

01 transform: increment integer
03 transforms: Transduce with `map`+`filter`+`remove`, 1X
06 transforms: Transduce with `map`+`filter`+`remove`, 2X
12 transforms: Transduce with `map`+`filter`+`remove`, 4X

How do Brokvolli's transduce variants perform compared to Clojure's reduce, et al.?

Observations: The single-threaded variants perform similarly, while the multi-threaded variants are faster for large vectors and heavier computations.

See also:

• Addendum 1: Increased computations per element
• Addendum 2: Effect of partition size
• Addendum 3: Performance scaling with processors

Two of Brokvolli's goals are

1. Bring transduce's performance benefits to reduce-kv-style processing.
2. Extend fold's multi-threading performance benefits to both transduce and transduce-kv.

So let's run some benchmarks to see if we can objectively measure any performance improvements.

We'll define our benchmarks here. For each function, we'll test vectors increasing in length from one element to one‑million elements, by powers of ten. We'll arrange four different tests:

1. Increment each element, a pre-generated, random floating point number.
2. Increment, filter, and remove, 1× (three total operations).
3. Increment, filter, and remove, 2× (six total operations).
4. Increment, filter, and remove, 4× (twelve total operations).

For each test, we'll use the Criterium benchmarking library to measure the execution times of sixty repetitions of each condition. Benchmarks were run on three explicitly-pinned cores of my rusty desktop computer.

The functions under examination are as follows:

• clojure.core/reduce

• clojure.core/reduce-kv

• clojure.core/transduce

• brokvolli.single/transduce-kv

• brokvolli.multi/transduce

• brokvolli.multi/transduce-kv

• a naive sequence implementation

Overall, we observe that the execution times increase with increasing vector lengths. The results are indistinguishable when the vector contains one‑hundred or fewer elements. When the vectors grow longer and the processing stack is small (i.e., one or three transforms), the single-threaded functions tend to perform slightly faster. However, when the vector lengths approach one‑million elements and the processing stack involves more transforms, the multi-threaded variants (fold, multi/transduce, and multi/transduce-kv), offer improvements that scale roughly with the number of processors.

Brokvolli's multi-threaded transduce and transduce-kv may offer performance benefits over their single-threaded counterparts for large collection sizes and deep transformer stacks. For smaller collections or shallow transformer stacks, the single-threaded variants perform better, and present a simpler interface.