Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Appending a large collection to a ListSet causes a StackOverflowError #3822

Closed
scabug opened this issue Sep 2, 2010 · 5 comments
Closed
Assignees

Comments

@scabug
Copy link

scabug commented Sep 2, 2010

I wanted to create a large ListSet, which goes quite wrong when using the ++ operator as the following code would demonstrate:

import scala.collection.immutable._
import scala.collection.mutable._

val numbers = new MutableList[Int]()
for(number <- 2 to 1999999) {
        numbers += number
}
var workingNumbers = new ListSet[Int]() ++ numbers

The stack trace looks like the following:

java.lang.StackOverflowError
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
(about 1,000 more of the above)

@scabug
Copy link
Author

scabug commented Sep 2, 2010

Imported From: https://issues.scala-lang.org/browse/SI-3822?orig=1
Reporter: Sean Parsons (seanparsons)

@scabug
Copy link
Author

scabug commented Sep 3, 2010

@paulp said:
Looks like somebody failed the tailrec test. But even with that fixed the code runs for approximately an eternity. Not so sure about the wisdom of adding 1999999 elements to a data structure with an O(n) add.

@scabug
Copy link
Author

scabug commented Sep 3, 2010

Sean Parsons (seanparsons) said:
But I'm guessing it will fail with well under 2,000 however? Much as that may still not be an amazing use of it.

I stumbled on it while trying to come up with a nice implementation of the Sieve of Eratosthenes technique where I planned to filter immutable collections by replacing them repeatedly.

Is there any scope for me adding some more unit tests around the collections framework to detect issues like this in the future?

@scabug
Copy link
Author

scabug commented Sep 4, 2010

@paulp said:
Replying to [comment:3 seanparsons]:

But I'm guessing it will fail with well under 2,000 however? Much as that may still not be an amazing use of it.

Not that low. More importantly, it's unnecessary. Post-patch:

scala> import scala.collection.immutable._ 
import scala.collection.immutable._

scala> new ListSet[Int] ++ (2 to 1999999)  
res0: scala.collection.immutable.ListSet[Int] = Set(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 1...
scala> res0 filter (x => x > 1000000  && x < 1000005)
res1: scala.collection.immutable.ListSet[Int] = Set(1000004, 1000003, 1000002, 1000001)

Is there any scope for me adding some more unit tests around the collections framework to detect issues like this in the future?

I say a prayer along those lines most nights. There is always talk about such things but so far everyone who shows much interest is derailed by the realities.

@scabug
Copy link
Author

scabug commented Sep 17, 2010

@paulp said:
(In r23020) Some tweaks to ListSet to make it less pathological in its outlook.
We can see some modest improvements in run time and answer quality
via the enclosed test case:

// with this patch: 2.250s elapsed, assertions pass.
// without this patch: 51.441s elapsed, and it's a mercy killing:
java.lang.StackOverflowError
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)
at scala.collection.immutable.ListSet$$Node.contains(ListSet.scala:117)

Closes #3822, review by community.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants