Allow scala collection in 2.13 be lazy by default (or at least op fusion)


#1

A big part of scala 2.13 goes with the collection redesign. It was decided that the redesigned should be as near as possible than the current collection (see https://groups.google.com/forum/#!msg/scala-debate/Z1YH_0Hgu5A/yqhTddk6AQAJ).
Still, one of the big selling point of the redesigned was that with the new collection, lazy collection and operation fusion should just work (ie: that .view should be usable, contrary to present situation). In fact, AFAIK, the design is so that immutable collection are view by default and the strict evaluation is forced on operation (https://www.scala-lang.org/blog/2017/11/28/view-based-collections.html).

I would really, really, really love to be able to specify that for all my project, the lazy behavior is the one by default, and the complicated one that makes performance horrible as soon as you have big collections in prod and a couple of filter/map/flatMap/goupBy applied would be the one needing a special word.
I’m in no way a pure FP extremist. I work on Rudder, which as you can see by yourself, is very far from pure FP. But we do use almost only immutable collections, with lots of map/filter/etc on them, because it’s way simpler to understand what’s going on.
But without operation fusion, and collection with some millions of elements, the performance hit is huge on any chain of transformation.
Now, I can try to teach all my colleagues to always ever write view before any map or for comprehension, but this is extremelly error prone. And really, it’s just the kind of thing that the language handle for you.
And it would make me so sad.

On the other hand, we are totaly ok to make special hand waving when we need a strict semantic for some exceptionnal reason. We even have a couple of arrays lying in the code for some very perf sensitive hot spot. But that’s the exception. Most of the code is boring business code with a O(disk & network access), except when the CPU and the carbage collector go mad for excess of copy of big collection.

All that being said, and even if I know that the default behavior for scala collection won’t change (that was made clear by Martin, several times), can we at least get a compiler option to automatically get lazy collection everywhere? Or even just operation fusion (in fact, I can live with stream and lazylist when I need lazyness beyond the scope of operation fusion, at least if the fusion is between chained app function).

And for the record, as it was asked by @julienrf, I don’t have the least capacity to make a PR for that - but I’m able to open a comment here.

Edit: all that was written with the assumption that View has operation fusion… But then @julienrf pointed to https://github.com/scala/collection-strawman/pull/144 and now I’m not quite so sure… Has it?


#2

When I’m dealing with very performance sensitive code I do .iterator and works most of the times as I rarely reuse the intermediate results of big chains.

I know this comment is not related to the main premise of your thread, but I still want to make this remark in case others don’t know how useful iterators can prove to be (using views in the old design is most of the times unnecessary). Of course, the use of iterators still requires some awareness on the programmers side.


#3

I’d like to comment on a few points:

Views have been completely reimplemented and except in the obvious case of terminal operations (such as foreach, fold, to and also groupBy), they will not anymore evaluate more elements than what you have iterated (or this is a bug, please report it!). So, that’s in that sense that the new views are usable (but yes, there is still the .view tax).

Indeed, transformation operations applied to strict collections (ie. everything except LazyList and View) immediately return a new collection.

What would you expect, more precisely? Type signatures of transformation operations should always return a View, or should we keep returning List, Vector, etc. for un-evaluated collections? The first option is probably easy to implement as a compiler plugin: just rewrite calls to transformation operations such that they are preceded by .view. IMHO the second option is hard to implement (maybe you can by using a runtime proxy…) but anyway it should not by provided by the standard library because that would completely change the meaning of List[A] (and all the other strict collection types) and the lazy behavior would be so different that it would be too dangerous to keep using the same types (and that’s the reason why we sticked to strict transformation operations in the new design).

Side note: a lazy implementation of groupBy does not really make sense: you have to compute the whole result in order to iterate on the first element anyway.

I expect that, most of the time, programs are not bounded by collections usage. And I would even say that that’s our target: we want to provide decent performance that should fit most of the use cases. For performance critical cases, maybe the standard collections are not the right tool?

I’m not sure what you mean by “operation fusion”. Transforming a view returns another view that “remembers” that the transformation operation has to be applied when a terminal operation is eventually called. So, chaining transformation operations has no overhead such that “a complete collection is built at each point of the chain of transformation”.

However, this discussion remembers me that there is still a small overhead that could be optimized. Indeed, although no intermediate collection is computed, the chain of transformation operations forms a stack of indirections: each transformed view creates its own Iterator that computes the transformed elements based on the elements of the previous view, and so on. It is possible to remove these levels of indirections by fusing some operations. For instance, when we call .filter(p).filter(q) on a view, instead of creating one view for each .filter call, we can create a single view applying first p and then q. This optimization is actually implemented, although I haven’t measured its impact. We could follow the same approach to fuse consecutive flatMap and map calls applied to views.


#4

The second one. The first one is not much better than forcing the team to use view everywhere. If the convention is to have View in all signature (or Iterator for that matter), I won’t be asking for it.
The switch of semantic is actually what I’m looking for. I don’t want it to be the default for all scala, I very clearly understood that discussing that option is verboten. But for the scope of a project, totally managed by the same team, it does totally make sense to have a set of convention (for ex indentation, etc). Compiler option are among that, even some that change the semantic (for ex -Ypartial-unification).

I’m not talking about performance critical hot spot. I’m talking about pevasive usage of immutable scala collection with for expression (map/filter/flatmap). The obvious hot spot are optimized, the problem is the pervasive churned in memory and GC implied by what is the totally standard use of scala, as taught in PiS and coursera, for prod usage.

I want to be able to write things like that:

def myBusinessFunction1(input: Set[ADT1]): List[List[ADT2]] = { input.map(...).filter(...).etc }
def myBusinessFunction2(input: List[List[ADT2]]): List[ADT3] = { input.map(...).filter(...).etc }

res = for { a <- myBusinessFunction1(input); b <- myBusinessFunction2(a); c <- b } yield etc 

And being able to decompose a map in two or thee map if it makes the understanding of the step eaisier to read, or refactoring the boundaries of function, or adding a filter somewher, without having to wonder if it will double the time, memory and GC spent in processing that collection. Little things add up. A lot, in the case of collection.

Now, if you are telling that scala collection should be avoid in the general production case because they are not fit for usage where collection are not tiny, or mutable, or when map/filter/flatMap are used, ok. The message is clear, and the community will know that there is an deep need to build an immutable collection framework that does not behave horribly when used in what I thought was the normal way of using scala.

Yes, that. I’m really not at the level of optimization you are talking in the second paragraph. More just “don’t blow up with a heap space exception because I added a filter”

Edit: changed “urgent” by “deep”, as the urgency is somehow 10 years late.


#5

Unfortunately, I’m afraid that what you want to have (a switch between two semantics for the same type signatures) is impossible to achieve correctly (or you will fall down into the same caveats as the 2.12.x views, which are unpredictable!).

I understand well your use case and in 2.13 the only price to pay to achieve what you want is to explicitly write .view everywhere you want to insert a transformation boundary. Unfortunately, unless someone comes up with a brilliant idea to manage the backward compatibility, I don’t think we will change the current “strict transformations by-default” policy.

That being said, I think view transformers can be one of the tools you are looking for to “build an immutable collection framework that does not behave horribly for chaining transformations of large collections”.


#6

I don’t think this is true. And also I think you overestimate the pros of using views. They do have drawbacks in some cases too, and choosing whether to evaluate an intermediate transformation result or not can not be yes everytime or no everytime. Typically, if you traverse, consume or reuse a view multiple times, then the cost of the transformation operation applied to each individual element is multiplied by the number of time the view is reused. If running that transformation operation is more expensive than building a resulting collection once, then it’s better to go with a strict evaluation. This decision really has to be taken on a case by case analysis.

Just to illustrate what I’ve said with code, in case I’m not clear:

def myBusinessFunction(xs: List[Thing]) = {
  val ys = xs.map(f)
  val zs = ys.map(g)
  (ys ++ zs).to(Set)
}

In myBusinessFunction, I reuse the ys value two times, a first time to compute zs and a second time in the returned expression. If transformations were all lazy, the elements of ys would be computed twice. If the f function is expensive, it’s better to evaluate it once and to use an intermediate collection to store ys.
On the other hand, with the current state where transformations are all strict, the definition of zs causes the evaluation of an intermediate List, which can be undesirable if there are lots of elements.
So, with that use case, there is no simple rule to apply: you sometimes want to have lazy transformations, and sometimes want to have strict transformations:

def myBusinessFunction(xs: List[Thing]) = {
  val ys = xs.map(f) // keep it strict because I want to compute it only once
  val zs = ys.view.map(g) // make it lazy because I don’t want to compute an intermediate structure
  (ys ++ zs).to(Set)
}

Note that another option for ys would have been to use a LazyList, which has lazy transformations but memoizes its elements so that they are not computed more than once:

val ys = xs.iterator.map(f).to(LazyList)

I think this example shows that both strict and lazy evaluation are useful and have their pros and cons: lazy transformations don’t create intermediate structures, but you have to take care of the cost of computing each element, eventually resulting from the chain of transformations, and you might want to insert strict boundaries here and there, to not perform unnecessary computations…


#7

Oh, there’s no memoïzation on views in the general case? Interesting. Is there an explanation somewhere of the explanation for that? (likely some cost, in complexity or memory, but I would like to better understand the rationnals).

And still… You force on us the default to strict, even if in our common scenario, your counter example is an oddity (ie: imagine that in the owerhelming cases, our transformation are cheap, or we very rarelly use the same collection for several branches of culculus, or just the balance is so far in one direction that we would be ok to add some strict in chosen places than lots of views).

Oh, maybe it can be a different import? Like we have scala.collection.mutable, scala.collection.immutable, we could have scala.collection.lazy? The name overlapping already exists (Map versus Map and other), so there is precedent.


#8

If the language was lazy (or had some special support for it), I don’t think that would happen. Wasn’t planned an annotation/mark for functions/methods to signal compiler they are pure, so larger range of optimizations (automatic memoization) may be deployed?


#9

Memoization also comes up with its cons. For instance, it’s easy to have memory leaks. If you want memoization you should use a LazyList.


#10

Yes. And I forgot that you live with the assumption that effects can happen and their operationnal semantic be relevant in the context of immutable collection transformation.


#11

I’m not sure where you got that impression from, discussing stuff is always fine, it’s just that you’ll need to convince a lot of people to make a radical change.

The least compiler options we have that affect semantics, the better. Hopefully the few that we have now will be phased out. They create endless problem: when looking at a piece of Scala code I need to know which “dialect” of the language is being used, which might be set by something as subtle as a compiler flag in a build file in an sbt plugin I happen to depend upon. Furthermore, if I depend on multiple Scala libraries, each of these libraries may have chosen a different dialect, don’t you think that will lead to compatibility nightmares?


#12

Excuse me… But are you serious? The topic was discussed in 2008 with 2.8 collection redesigned, then with Paul’s psp, then again with the strawman proposal, and Martin Odersky was so clear about that need that he wrote a dedicated post to specify the scope. All of the outcomes were quite clear and consistent: scala collection are stricts with no operation fusion.

If a decade of consistant signals is not to be accounted for getting an impression, I’m not sure about what could be.

(and that was exactly what I wanted to avoid to bring on that topic. I thought that that part of the subject was closed)

edit: typos


#13

I can understand that, even if it seems that other ecosystem are growing ok with an ecosystem like that. Clearly not the panacea. But ok, here also the body of information is consistent.
So, what about a scala.collection.lazy ? From prior art, it allows to use the same names (List, Set etc) with a vastly different semantic (immutable versus mutable) and let people decide considering their use cases and project-based usage conventions, without impacting Scala default flavor. Would it be considered acceptable?

With that, we could have a set of lazy data structures with their very specific optimized use case (“lazy data structures must be used with pure code only”, for ex), with their own performance caracteristics (“you gain operation fusion and memoïzation, but might have funny space behavior”).

edit: typos


#14

All of the outcomes were quite clear and consistent: scala collection are stricts with no operation fusion.

All I’m saying is no one is forbidding you from debating alternatives, it’ll just be a tall order to actually change something like that.

So, what about a scala.collection.lazy ?

That’s already more reasonable and could be discussed, but also comes with its own set of pitfalls: if some libraries use scala.collection.lazy and others use the regular collections, then composing them requires adding a bunch of conversions everywhere (I’m reminded of lazy ByteString vs strict ByteString in Haskell). In any case since we’re now talking about a purely library-based solution, maybe the best thing to do would be to actually implement this as its own independent library ? If it proves widely successful it can then be merged into the standard library.


#15

Is that true? I feared it could be seen as a violation of the CoC (trolling or the like), and that’s why I was very careful to explain that it was not what I was looking for.

AFAIK, from an architectural point of view, 2.13 is already like that: everything is based on view, so the lazy package is already in the design of the redesign, and the same goes for conversion (ie view and I don’t remember what was kept for lazy -> strict, break or force or something else ?)

Of course, and independant library could be made. But it seems either quite hard to do and maintain, and quite core of scala. Not that it’s impossible (it happened in java and rust and others). But in that case, we are coming back to one of my first messages: scala core will not implement that, and the community is in charge of making it happens.


#16

If it’s done in good faith it’s not a violation of the CoC, that would be crazy.

As always, you need someone to care enough to actually implement it and then maintain it. What you’re proposing would significantly increase the API footprint of the standard library, and also require a lot of documentation to not confuse people. The discussion in this thread makes me think that the exact semantics of lazy collections are not even completely clear yet. At the very least someone would have to do a prototype. The other issue is that we’re now already at the end of the 2.13 development cycle and feature freeze for the library has already been declared (https://www.scala-lang.org/blog/2018/06/05/collections-feature-freeze.html).


#17

How an external person can judge my good faith? Especially on the internet, with all the risk of missing the tone of a comment which was intended to be helpfull and was interpreted as an attack? I mean, there is precedent where some topic were mark with a hot iron as dangerous to talk about and just evoquing them in the right time was interpreted as trolling. I wanted to be on the safe side.

(just for the record, I’ve been talking on diverse channel about that topic since a long time ago. @julienrf and I met at Scala.io and discussed it last year for example).

That’s very clear, thank you.


#18

Unfortunately, that’s not simple.

The collections framework (which defines the usual map, flatMap, filter, etc. operations) assumes nothing about the way concrete collections will evaluate transformation operations: it can be strict or non-strict. Therefore, in the framework, the implementation of transformation operations is based on views, which are non-strict, but the last word goes to concrete collection implementations, which can force the view (or not) to produce the final result of each transformation operation. That crucial operation is implemented in the companion object of concrete collections, its name is from.

Given this framework, is it easy to implement your suggestion? Let’s try to see how would scala.collection.lzy.List look like. Currently, a List[A] can either be Nil, or Cons (aka ::). How could we implement List.from in a way that doesn’t evaluate the source collection? For reference, the current implementation is equivalent to the following:

object List extends IterableFactory[List] {
  def from[A](source: IterableOnce[A]): List[A] =
    source.iterator.foldRight(Nil)(_ :: _) // consume the source and put its elements into a list
}

So, how could we not consume the source immediately? We would need a third constructor for List (in addition to Nil and Cons). For instance:

sealed trait List[+A] extends LinearSeq[A] with LinearSeqOps[A, List, List[A]] {
  def head: A
  def tail: List[A]
}
case object Nil extends List[Nothing] {
  def head = sys.error("head of Nil")
  def tail = sys.error("tail of Nil")
}
case class Cons[+A](head: A, tail: List[A]) extends List[A]
final class Lazily[+A](source: Iterator[A]) extends List[A] {
  lazy val head = source.next()
  lazy val tail = {
    head // be sure that the head has been evaluated so that the iterator is in the correct state
    new Lazily(source)
  }
}
object List extends IterableFactory[List] {
  def from[A](source: IterableOnce[A]): List[A] = new Lazily(source.iterator)
}

First, for end-users this would be very painful because pattern matching on lists would require to deal with three cases.

But also, each concrete collection type would have to implement its own Lazily constructor. The case of List is probably the easiest one because it’s a linear data structure that naturally fits with the linear consumption of an Iterator. But what about Array?

class Lazily[A](source: Iterator[A]) extends Array[A] {
  def apply(idx: Int): A = source.drop(idx).next()
}

Indexed access becomes O(n) on a lazy array!

I think this example shows that the new collections framework is definitely not designed for your request. But if you have ideas to implement your proposal, I’m open to it (but that won’t happen for 2.13…)!


#19

Thanks.