Scala Seq vs List performance

Question

So I am a bit perplexed. I have a piece of code in Scala (the exact code is not really all that important). I had all my methods written to take Seq[T]. These methods are mostly tail recursive and use the Seq[T] as an accumulator which is fed initially like Seq(). Interestingly enough, when I swap all the signature with the concrete List() implementation, I am observing three fold improvement in performance.

Isn't it the case that Seq's default implementation is in fact an immutable List ? So if that is the case, what is really going on ?

`Seq` default implementation is actually of an `ArrayBuffer`, not a `List`. The use case you have is actually tailor-made for `List`s, since they are implemented tail-recursively. — Cyrille Corpet, Mar 21 '17 at 22:21
The default implementation of the default `Seq` is `List`. Could you show the code and how you call it? — Jasper-M, Mar 21 '17 at 22:41

score 4 · Answer 1 · answered Mar 22 '17 at 13:44

4

Calling Seq(1,2,3) and calling List(1,2,3) will both result in a 1 :: 2 :: 3 :: Nil. The Seq.apply method is just a very generic method that looks like this:

def apply[A](elems: A*): CC[A] = {
  if (elems.isEmpty) empty[A]
  else {
    val b = newBuilder[A]
    b ++= elems
    b.result()
  }
}

newBuilder is the thing that sort of matters here. That method delegates to scala.collection.immutable.Seq.newBuilder:

def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer

So the Builder for a Seq is a mutable.ListBuffer. A Seq gets constructed by appending the elements to the empty ListBuffer and then calling result on it, which is implemented like this:

def result: List[A] = toList

/** Converts this buffer to a list. Takes constant time. The buffer is
 *  copied lazily, the first time it is mutated.
 */
override def toList: List[A] = {
  exported = !isEmpty
  start
}

List also has a ListBuffer as Builder. It goes through a slightly different but similar building process. It is not going to make a big difference anyway, since I assume that most of your algorithm will consist of prepending things to a Seq, not calling Seq.apply(...) the whole time. Even if you did it shouldn't make much difference.

It's really not possible to say what is causing the behavior you're seeing without seeing the code that has that behavior.

answered Mar 22 '17 at 13:44

Jasper-M

14,966
2
26
37

According to your assumption that Seq.apply was just a List, and that it didn't make a big difference, you would actually be able to do something like that, right: val sequence: LinearSeq[_] = Seq() This should accordingly work since Seq is a List and List uses the LinearSeq trait. But it doesn't work and for this reason, it matters how you construct your sequences, especially if you need efficient tail access or tail recursive operations (i.e., methods performing iterations on the sequence). – matfax Mar 22 '17 at 21:10
No. `Seq()` returns a `List` but its static `return type` is `Seq`. That's why you can't assign it to a variable of type `LinearSeq`. Evaluate `Seq(1).getClass` and see what you get. – Jasper-M Mar 22 '17 at 21:29
But to be clear I do agree it's better to just use `List` if you want the performance characteristics of a `List`. – Jasper-M Mar 22 '17 at 21:35
I've just checked it with the debugger. I assumed Seq only to use the ListBuffer to build the sequence but not to process it and to use the less-optimized operations from Traversable, etc., but it turns out it actually accesses the optimized methods from the List and its traits. For all intents and purposes, you were completely right claiming List.apply to be replaceable with Seq.apply. You should always use the apply methods of the three Seq traits. There is no explanation for any performance deviations. – matfax Mar 22 '17 at 22:57

Scala Seq vs List performance

1 Answers1