Scala linked list stackoverflow

Question

Using scala I have added about 100000 nodes to a linked list. When I use the function length, for example mylist.length. I get a 'java.lang.StackOverflowError' error, is my list to big to process? The list is only string objects.

score 11 · Accepted Answer · answered Nov 12 '10 at 04:04

11

It appears the library implementation is not tail-recursive override def length: Int = if (isEmpty) 0 else next.length + 1. It seems like this is something that could be discussed on the mailing list to check if an enhancement ticket should be opened.

You can compute the length like this:

def length[T](l:LinkedList[T], acc:Int=0): Int =
  if (l.isEmpty) acc else length(l.tail, acc + 1)

answered Nov 12 '10 at 04:04

huynhjl

41,520
14
105
158

5

I'm all for an enhancement ticket. This method can be easily implemented in a non-recursive manner all the way back in `TraversableOnce`. I can even implement it in this comment line: `def length: Int = { var count = 0; foreach { _ => count += 1 }; count }`. Back on `LinearSeq`, it one can get even better performance by using a private helper method to make the original implementation fully tail recursive. IMHO, both approaches should be taken. Do you open it, or may I? – Daniel C. Sobral Nov 12 '10 at 10:43
@Daniel Please open it, as you can provide more suggestions than me, just like you did here. – huynhjl Nov 12 '10 at 13:57

score 1 · Answer 2 · answered Nov 12 '10 at 04:02

1

In Scala, computing the length of a List is an order n operation, therefore you should try to avoid it. You might consider switching to an Array, as that is a constant time operation.

answered Nov 12 '10 at 04:02

jimmyb

4,227
2
23
26

`Vector` is preferable to `Array` – Luigi Plinge Sep 03 '11 at 09:59

score 0 · Answer 3 · edited May 23 '17 at 12:00

0

You could try increasing the stack/heap size available to the JVM.

scala JAVA_OPTS="-Xmx512M -Xms16M -Xss16M" MyClass.scala

Where

-Xss<size>  maximum native stack size for any thread
-Xms<size>  set initial Java heap size
-Xmx<size>  set maximum Java heap size

This question has some more information.

See also this This Scala document.

edited May 23 '17 at 12:00

Community

1
1

answered Nov 12 '10 at 03:55

Jon McAuliffe

3,137
1
20
10

1

You mean `JAVA_OPTS="-Xmx512M -Xms16M -Xss16M" scala MyClass.scala`? My shell requires for JAVA_OPTS to be before the scala command. – huynhjl Nov 12 '10 at 04:51

score 0 · Answer 4 · answered Nov 12 '10 at 15:22

Can you confirm that you truly need to use the length method? It sounds like you might not be using the correct collection type for your use-case (hard to tell without any extra information). Lists are optimised to be mapped over using folds or a tail-recursive function.

Despite saying that, this is absolutely an oversight that can easily be fixed in the standard library with a tail-recursive function. Hopefully we can get it in time for 2.9.0.

Scala linked list stackoverflow

4 Answers4