Managing unused `List`s in Scala

Scala have wealth of immutable structure.

I wondered how do Scala manage excessive allocation and deallocation of such objects. How does it look for existing sublists when, e.g. concatenating 1 to List(1,2,3). How does it track a certain List is not used, and allow the garbage collector to release it?

I would design it roughly like this

class List {
    private Map<Integer,WeakRef<List>> listCache;
    public List(Integer head,List tail) {...}
    public synchronized List prepend(Integer i) {
        if (listCache.get(i) != null) {
            if (listCache.get(i).get() == null) {
                listCache.put(i,new List(i,this));
            }
    }
}

How does Scala design that? Does it handle excessive allocations and deallocations well? What does it do about threading?

Answers


Scala doesn't manage the deallocation of these objects at all. They are created on the heap as normal JVM objects, and garbage collected by the JVM just like any other Java or Scala object. As the comments on your question point out, it doesn't re-use lists created from previous calls to List() - it is always a new object.

To clarify the situation with concatenating lists - in this case, the resulting List object does hold a reference to the two ends of the list, but it still isn't doing any special caching of previously used lists or anything like that.


Let's write a simple List class:

sealed abstract class MyList[+T] {
  def head: T
  def tail: MyList[T]
  def isEmpty: Boolean
  def prepend[T1 >: T](el: T1): MyList[T1]
}

object EmptyList extends MyList[Nothing] {
  def head: Nothing = throw new java.util.NoSuchElementException("head of an empty list")
  def tail: MyList[Nothing] = throw new UnsupportedOperationException("unsupported operation exception")
  def isEmpty = true
  def prepend[T1 >: Nothing](el: T1): MyList[T1] = new Cons(el, this)

  override def toString = "EmptyList"
}

final class Cons[+T](val head: T, val tail: MyList[T]) extends MyList[T] {
  def isEmpty = false
  def prepend[T1 >: T](el: T1): MyList[T1] = new Cons(el, this)

  override def toString = head + ", " + tail.toString
}

Lists in Scala work like that. Consider, then, the example you mentioned:

scala> val list = new Cons(1, new Cons(2, new Cons(3, EmptyList)))
list: Cons[Int] = 1, 2, 3, EmptyList

scala> val newList = list.prepend(1)
newList: MyList[Int] = 1, 1, 2, 3, EmptyList

So, questions:

  • Did we look up lists for reuse? No.
  • Did we reuse anything? Yes, we reused the list on which prepend was called.
  • How will it be garbage collected? Just like any object in the JVM: when nothing points to it, it will be collected.

Of course, if I create another list like this:

val list2 = list.prepend(1)

Then newList and list2 will share list but will be different lists even though they contain the same elements.

You might question (as was done in the comments) if this re-usability pattern is practical, or whether it brings any gains in real life, and the answer to that is that a lot of algorithms take advantage of it.

In fact, let me point out this question, in which the allegedly "slow" code was actually faster than the allegedly "fast" code as well as the alternatives suggested in the answers. The reason why the "slow" code was nothing of the sort is this very pattern of reuse.


Need Your Help

using std::sort and std::next_permutation

c++ algorithm

I have the following code which i wrote and works perfectly. I just have trouble understanding why it works. More specifically, why must we first sort the array in order to use std::next_permutatio...

Google Chrome canvas v5 setLineDash

google-chrome html5-canvas

Does anybody know since which version context.setLineDash([5]) is implemented in Google Chrome?

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.