scalamonadsfunctorscalacscala-compiler

Does the Scala compiler try to reduce object creation between several sequential maps and flatmaps


This is a question about the Scala compiler.

Let's say I have a List, and that I transform that list through several maps and flatMaps.

val myList = List(1,2,3,4,5)

val transformed = myList.map(_+1).map(_*2).flatmap(x=>List(x-1,x,x+1))

Let's say I transform it some more.

val moreTransformed = transformed.map(_-2).map(_/5).flatMap(x=>List(x/2,x*2))

My question can be divided into two parts

  1. When generating the val for transformed, does the underlying Java bytecode create the intermediate lists? I am referring to the successive calls to map and flatMap in the computation of transformed. Can the Scala compiler compose these calls into a single flatMap? If I was operating on a list of objects, this would entail creation of fewer intermediate objects. If the compiler is naive and simply creates the intermediate objects, that could potentially result in considerable overhead for computations that involve long chains of map and flatMap.

  2. Let us say that of the two vals created above, I only use moreTransformed (the second val) in further computation. That is, I only use transformed (the first val) in the calculation of moreTransformed and nowhere else. Is the Scala compiler smart enough not to create the List for transformed and to compute only moreTransformed? Is it smart enough to compose all the functions in transformed and moreTransformed so that only a single List, the value of moreTransformed, is produced?


Solution

  • It doesn't matter how smart the compiler is, it must still conform to what the language specifies.

    In this case the language says that each map/flatMap operation must appear to complete before the next one starts. So the compiler can only perform the optimisations that you mention if it can guarantee that the behaviour will be the same.

    In the specific case of the example in the question, the compiler knows what is in myList, and the functions that are applied have very clear semantics. The compiler could theoretically optimise this and pre-compute the results without doing anything at run time.

    In the more general case the compiler will not know what is in myList and the operations will have a chance of failing. In this case the compiler has no choice but to execute each operation in turn. That is the only way to guarantee the correct results according to the language.


    Note that the Scala code is usually executed in a JVM with a JIT compiler, and that is where much of the optimisation is done. The sequential map calls will be converted into sequential loops in the bytecode and in some circumstances the JIT compiler may be able to combine those loops into a single loop. However this optimisation cannot be done if there is anything in the loop with a side effect, including object allocation.