Immutability and memory usage

user_7869491 0
Viewed 65

I was expecting extremely small increase in memory usage after adding an element to immutable Seq. Because new reference (val) can re-use memory allocate for already created val and an additional memory allocation would be required for the new element only. In other words I do not see a necessity for the defensive copy to be created (see here https://users.scala-lang.org/t/inquiry-on-immutabillity-of-objects-and-how-they-affect-memory/2340).

In reality, however, after adding one element memory usage increases to the same amount as creating completely new Seq. Below is a code snippet from the SBT project

object obj extends App {

  val n = 1000000

  def usedMem = {
    val runtime = Runtime.getRuntime
    runtime.totalMemory - runtime.freeMemory
  }

  val m1 = usedMem
  
  val ar = scala.collection.mutable.ArrayBuffer.fill(n)("hohohohoho")
  val m2 = usedMem
  println ("1 " + (m2-m1))

  val sq = Seq.fill(n)("hohohohoho")
  val m3 = usedMem
  println ("2 " + (m3-m2))

  val ar0 = ar :+ "yo"
  val m4 = usedMem
  println ("3 " + (m4-m3))

  val sq0 = sq :+ "yo"
  val m5 = usedMem
  println ("4 " + (m5-m4))

}

In the output we see that memory usage after step 2 and after step 4 increased by almost 24MB. I would expect very small increase after step 4 though.

1 4103816
2 23948288
3 4546184
4 23948600

Can someone explain this behaviour? Or alternatively how to see that memory is re-used for immutable objects.

Also I was quite surprised that memory usage for ArrayBuffer is much smaller than for Seq (4MB vs 24MB). Would be great to understand this difference as well.

immutability memory memory-management scala
1 Answers

That is because you are not using a proper data structure for the job.

Here: val sq = Seq.fill(n)("hohohohoho") you are creating a Seq but a Seq is an abstract type, and thus it has to pick a concrete implementation. And as of the day of writing such default is usually a List

And Lists can't share memory when appending, they have to copy everything (which means it is pretty slow too).

Now, what you may do is to use a data structure that is optimized to append, like Vector or cats Chain
You may also use List directly and prepend instead of append like:

val sq = List.fill(n)("hohohohoho")
val sq0 = "yo" :: sq

This is one of the reasons why I personally dislike Seq, it doesn't provide enough information to do anything useful with it.

user_41114040
Related