Scala collections behaviour. Slow adding to list

Question

I have a code below. It prints time of List filling. When circles = 1000000 the output is 300 ms When circles = 1000000*10 the output is around 7000 ms. But intuitively I've expected that it should be 300 * 10. Scaladoc says adding element to List is O(1). Why does it behave like that?

val random = new Random()
var ints: List[Int] = List()

val start = System.currentTimeMillis();

val circles = 1000000
for (i <- 1 to circles) {
  ints = random.nextInt.signum :: ints
}

println(System.currentTimeMillis() - start);

if I use constant instead of random the results are 156 ms and 5300 for circles = 1000000 and circles = 1000000*10

Answer 1

What you're measuring here is how fast is JVM memory management. The slowest part of your algorithm is memory allocation for new list elements. I would assume that the slowdown can be because your heap size is initially not big enough to handle all elements and therefore it needs to grow which is relatively slow.

What are the Xms and Xmx parameters when starting JVMs?

Try to increase Xms so that initial heap size is enough even for the larger list.

Answer 2

Your benchmark almost certainly isn't proving what you think it's proving. Benchmarking on the JVM isn't as simple as writing some code, running it once, and seeing how long it took — not by a long shot. See such articles as:

• https://wikis.oracle.com/display/HotSpotInternals/MicroBenchmarks
• http://www.ibm.com/developerworks/java/library/j-benchmark1.html

A popular tool for running meaningful benchmarks on the JVM is Google Caliper. A nice Scala-specific tool is Rex Kerr's Thyme.