Scala's toList function appears to be slow

Question

I was under the impression that calling seq.toList() on an immutable Seq would be making a new list which is sharing the structural state from the first list. We're finding that this could be really slow and I'm not sure why. It is just sharing the structural state, correct? I can't see why it'd be making an n-time copy of all the elements when it knows they'll never change.

Answer 1

Sharing structural state is possible for particular operations on particular data structures.

With the List data structure in Scala, my understanding is that every element refers to the next, starting from the head through the tail, so a singly linked list.

From a structural state sharing perspective, consider the restrictions placed on this from the internal data structure perspective. Adding an element to the head of a List (X) effectively creates a new list (X') with the new element as the head of X' and the old list (X) as the tail. For this particular operation, internal state can be shared completely.

The same operation above can be applied to create a new List (X'), with the new element as the head of X' and any element from X as the tail, as long as you accept that the tail will be the element you choose from X, plus all additional elements it already has in it's data structure.

When you think about it logically, each data structure has an internal structure that allows some operations to be performed with simple shared internal structure and other operations requiring more invasive and costly computations.

The key from my perspective here is having an understanding of the constraints placed on the operations by the internal data structure itself.

For example, consider the same operations above on a doubly linked list data structure and you will see that there are quite different restrictions.

Personally, I find drawing out an understanding of the internal structure can be helpful in understanding the consequences of particular operations.

In the case of the toList operation on an arbitrary sequence, with no knowledge of the arbitrary sequences internal data structure, one has to therefore assume O(n). List.toList has the obvious performance advantage of already being a list.

Answer 2

A List in Scala is a particular data structure: instances of :: each containing a value, followed by Nil at the end of the chain.

If you toList a List, it will take O(1) time. If you toList on anything else then it must be converted into a List, which involves O(n) object allocations (all the :: instances).

So you have to ask whether you really want a scala.collection.immutable.List. That's what toList gives you.