Take the 2-minute tour ×

Consider the following Set benchmark:

import scala.collection.immutable._

object SetTest extends App {
  def time[a](f: => a): (a,Double) = {
    val start = System.nanoTime()
    val result: a = f
    val end = System.nanoTime()
    (result, 1e-9*(end-start))

  for (n <- List(1000000,10000000)) {
    println("n = %d".format(n))
    val (s2,t2) = time((Set() ++ (1 to n)).sum)
    println("sum %d, time %g".format(s2,t2))

Compiling and running produces

tile:scalafab% scala SetTest
n = 1000000
sum 1784293664, time 0.982045
n = 10000000

I.e., Scala is unable to represent a set of 10 million Ints on a machine with 8 GB of memory. Is this expected behavior? Is there some way to reduce the memory footprint?

share|improve this question
If I remember right, by default, Java uses much less than the total available memory. –  Ken Wayne VanderLinde Aug 20 '11 at 18:58
The Int values are all being boxed there I believe. @specialized to the rescue? Also could use fold to count and only use stream vs. forcing entire evaluation of 1 to n sequence (required in the ++), but that is different semantics in some cases (not here) :) –  user166390 Aug 20 '11 at 19:02
++ should be using Range.foreach, so there should be no sequence expansion going on. How would one use @specialized here? –  Geoffrey Irving Aug 20 '11 at 19:07
specialized is no use here unless you write your own set library. –  Rex Kerr Aug 20 '11 at 19:10
@Geoffrey Irving How can the elements live in the new set without expansion? –  user166390 Aug 20 '11 at 19:10
show 1 more comment

3 Answers

up vote 10 down vote accepted

Generic immutable sets do take a lot of memory. The default is for only 256M heap, which leaves only 26 bytes per object. The hash trie for immutable sets generally takes one to two hundred bytes per object an extra 60 or so bytes per element. If you add -J-Xmx2G on your command line to increase the heap space to 2G, you should be fine.

(This level of overhead is one reason why there are bitsets, for example.)

share|improve this answer
One of the reasons I like functional programming is that it demonstrates that immutable collections can be faster and more memory efficient, if designed to take advantage of their immutability (eg. by sharing memory) –  Ken Wayne VanderLinde Aug 20 '11 at 19:13
@Ken Wayne VanderLinde - Sure. But sometimes you just want one big un-shared set, so you either need more memory, or a reasonably implemented HashSet. –  Rex Kerr Aug 20 '11 at 19:16
Hash tries take O(n log c) time, but only O(n) space, where c is either the size of a machine word or n (I'm not sure what arity the trie is). –  Geoffrey Irving Aug 20 '11 at 19:20
To confirm: c is the size of a machine word. –  Geoffrey Irving Aug 20 '11 at 19:31
@Geoffrey Irving - Oops, you're right; it is a hash trie in the trie-in-a-hash-table-like-structure sense, not in the i-have-hash-values-in-a-trie sense. Fixed. –  Rex Kerr Aug 20 '11 at 19:34
show 5 more comments

I'm not that familiar with Scala, but here's what I think is happening:

First off, the integers are being stored on the heap (as the must be, since the data structure is stored on the heap). So we are talking about available heap memory, not stack memory at all (just to clarify the validity of what I'm about to say next).

The real kicker is that Java's default heap size is pretty small - I believe its only 128 megabytes (this is probably an really old number, but the point is that the number exists, and it's quite small).

So it's not that your program uses too much memory - it's more like Java just doesn't give you enough in the first place. There is a solution, though: the minimum and maximum heap sizes can be set with the -Xms and -Xmx command line options. They can be used like:

java -Xms32m -Xmx128m MyClass   (starts MyClass with a minimum heap of 32 megabytes, maximum of 128 megabytes)

java -Xms1g -Xmx3g MyClass (executes MyClass with a minimum heap of 1 gigabytes, maximum of 3 gigabytes)

If you use an IDE, there are probably options in there to change the heap size as well.

share|improve this answer
add comment

This should always overflow. Holding such large values is not required in this case. If you want to sum use an iterator or a range.

val (s2,t2) = time( (1 to n).sum)

The above line completes in a second with no overflow.

You can always increase memory allocation using other answers.

share|improve this answer
I think the OP is deliberately creating big Sets, just to test their performance. If he cared about efficiency, he could write val (s2,t2) = time( (n * (n+1)) / 2) –  Malvolio Aug 20 '11 at 20:59
Yep. That's why it's called a "Set benchmark". –  Geoffrey Irving Aug 21 '11 at 6:10
add comment

Your Answer


