To start, let’s take a look at the following code:

def process(xs: => Traversable[Int]) = xs.map(_ + 10).filter(_ % 3 == 0).map(_ * 2)

`process`

function is just a chain of transformations on the given `Traversable`

. Each of these transformations will create an intermediate traversable to be passed to the next transformation function. Given `xs = Array(1, 2, 5)`

, the manual tracing output would be:

1 is increased by 10 so transferred to 11 2 is increased by 10 so transferred to 12 5 is increased by 10 so transferred to 15 11 is filtered out because it is not a multiple of 3 12 is kept because it is a multiple of 3 15 is kept because it is a multiple of 3 12 is multiplied by 2 so transferred to 24 15 is multiplied by 2 so transferred to 30

In imperative programming style, this computation can be done “easily” with a `while`

loop which transform each element of `xs`

to the final desired value in one go. So no intermediate traversable will be created and this means less memory allocation. In this case, the manual tracing output would be:

1 is increased by 10 so transferred to 11 11 is filtered out because it is not a multiple of 3 2 is increased by 10 so transferred to 12 12 is kept because it is a multiple of 3 12 is multiplied by 2 so transferred to 24 5 is increased by 10 so transferred to 15 15 is kept because it is a multiple of 3 15 is multiplied by 2 so transferred to 30

How can we keep the compositional style (composing higher order functions like `map`

, `filter`

etc.) but without creating intermediate results to use memory more efficiently?

This can be achieved by using *non-strict* data structures. Non-strict (or lazy) data structures defer a computation until it is needed. In Scala, *Stream* is an implementation of non-strict sequence. Here is a simplified version of `Stream`

implementation:

trait Stream[+A] case class Cons[+A](head: A, tail: () => Stream[A]) extends Stream[A] case object Empty extends Stream[Nothing]

As seen above, the main difference between Stream and other strict sequences such as `List`

is that the `tail`

is a function instead of a strict value. So, tail is not being evaluated until it is forced. Let’s play with our Stream data structure to see how it works.

First, let’s create a convenient `apply`

function

object Stream { def apply[A](xs: A*): Stream[A] = if (xs.isEmpty) Empty else Cons(xs.head, () => apply(xs.tail:_*)) }

Now let’s add a simple version of `map`

and `filter`

to our `Stream`

trait.

trait Stream[+A] { def map[B](f: A => B): Stream[B] = this match { case Empty => Empty case Cons(h, t) => Cons(f(h), () => t().map(f)) } def filter(f: A => Boolean): Stream[A] = this match { case Empty => Empty case Cons(h, t) => if (f(h)) Cons(h, () => t().filter(f)) else t().filter(f) } }

Now, let’s partially trace our motivating example:

Stream(1, 2, 5).map(_ + 10).filter(_ % 3 == 0).map(_ * 2)

Upon the invocation of the first `map`

, `Stream(1, 2, 5)`

is matched with the second `case`

(line 4) so `Cons(11, function0)`

is created. `function0`

notation denotes on a function which if it is invoked, it calls `map(_ + 10)`

on the tail of the original stream. Next, `filter`

function is invoked on the result of the first step which was `Cons(11, function0)`

. So it is matched with the second `case`

(line 9). Since 11 is not a multiple of 3, it should be filtered out so `else`

branch is executed. Therefore, `function0`

is invoked to be evaluated. So we enter again in the `map`

function and again we match to the second case (line 4) and `Cons(12, function1)`

is created. Upon executing `filter`

on this intermediate result, it is again matched to the second case (line 9) but this time, since 12 is a multiple of 3, it is not filtered out (line 11). So `Cons(12, function2)`

is created. Now, `map(_ * 2)`

will be executed on this intermediate result and so on so forth.

As you see:

- Intermediate results are type of
`Stream`

which only has its head evaluated and the rest is not evaluated. - The order of the transformations is the same as
`while`

loop.

This is why sometimes streams are referred as **first-class loops** [1]. It seems that we should use this first-class loop instead of strict collections whenever we have a chain of transformations. Is it true?

To answer this question, I benchmarked Scala standard `Stream`

against `Array`

from both memory and throughput aspects. The benchmark source code can be found here.

For memory usage comparison, I implemented `MemoryUsage`

application and monitored the memory usage of different approaches with VisualVM.

I increased the size of data to 50 million elements to make the result more visible in VisualVM. Here is the result:

As seen, applying the aforementioned chain of transformations on `Array`

needs considerably bigger heap size. However, when the size of data is smaller, the differences is less tangible. But memory usage is just one side of the coin. What about throughput?

Stream data structure heavily uses memoizing. This means that functions that are passed to the constructor are cached in `lazy val`

s to prevent being re-computed. Although lazy values have been designed exactly for this purpose, comparing to `val`

s, they have worse performance. So we can expect that the throughput of stream transformations is less than arrays (or generally strict collections). To experiment this, I did a micro-benchmark using jmh and sbt-jmh. I chose `Array`

and `Stream`

with 10000 elements with the following benchmark setup:

sbt "run -i 5 -wi 5 -f1 -t1 \"StreamingBenchmark\""

And here is the result:

[info] [info] # Run complete. Total time: 00:00:20 [info] [info] Benchmark Mode Cnt Score Error Units [info] StreamingBenchmark.streaming thrpt 5 880.009 ± 75.244 ops/s [info] StreamingBenchmark.strictProcessing thrpt 5 4078.819 ± 276.049 ops/s

As seen, given the previously mentioned transformation chain, `Stream`

throughput is around 4 times less than `Array`

throughput.

### Conclusion

Although `Stream`

s eliminate intermediate collections upon transformations, it has considerably less throughput comparing `Array`

(of course `Array`

is optimised for traversing but I also executed the benchmark against other strict data structures like `Vector`

and `List`

and in all cases `Stream`

has worse performance but with different ratios). `Stream`

and other non-strict data types are great data structures but they should be used when their characteristics are really needed.

[1]. Chiusano P. and Bjarnason R. (2015). *Functional Programming in Scala* by Manning

Thanks a lot. Really useful post!

LikeLike