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.

Sign up for GitHub

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

Jump to bottom

flatMap is broken for parallel collections in 2.9.0 & 2.9.0-1 #4678

Closed
scabug opened this issue Jun 7, 2011 · 7 comments
Closed

flatMap is broken for parallel collections in 2.9.0 & 2.9.0-1 #4678

scabug opened this issue Jun 7, 2011 · 7 comments
Assignees
@axel22

Comments

@scabug
Copy link

scabug commented Jun 7, 2011

When the attached program below is run, it crashes with a horrific stack trace:

scala.collection.parallel.package$CompositeThrowable: Multiple exceptions thrown during a parallel computation: (java.lang.ArrayIndexOutOfBoundsException: 1074347069
. . .

at scala.collection.parallel.package$$anon$3.alongWith(package.scala:114)
at scala.collection.parallel.Tasks$Task$class.mergeThrowables(Tasks.scala:98)
at scala.collection.parallel.mutable.ParHashSetCombiner$FillBlocks.mergeThrowables(ParHashSet.scala:230)
at scala.collection.parallel.Tasks$Task$class.tryMerge(Tasks.scala:84)
at scala.collection.parallel.mutable.ParHashSetCombiner$FillBlocks.tryMerge(ParHashSet.scala:230)
at scala.collection.parallel.AdaptiveWorkStealingTasks$TaskImpl$class.internal(Tasks.scala:186)
at scala.collection.parallel.AdaptiveWorkStealingForkJoinTasks$TaskImpl.internal(Tasks.scala:509)
at scala.collection.parallel.AdaptiveWorkStealingTasks$TaskImpl$class.compute(Tasks.scala:164)
at scala.collection.parallel.AdaptiveWorkStealingForkJoinTasks$TaskImpl.compute(Tasks.scala:509)
at scala.concurrent.forkjoin.RecursiveAction.exec(RecursiveAction.java:147)
at scala.concurrent.forkjoin.ForkJoinTask.tryExec(ForkJoinTask.java:404)
at scala.concurrent.forkjoin.ForkJoinTask.join(ForkJoinTask.java:494)
at scala.collection.parallel.ForkJoinTasks$TaskImpl$class.sync(Tasks.scala:439)
at scala.collection.parallel.AdaptiveWorkStealingForkJoinTasks$TaskImpl.sync(Tasks.scala:509)
at scala.collection.parallel.ForkJoinTasks$class.executeAndWaitResult(Tasks.scala:487)
at scala.collection.parallel.ForkJoinTaskSupport.executeAndWaitResult(TaskSupport.scala:20)
at scala.collection.parallel.mutable.ParHashSetCombiner.parPopulate(ParHashSet.scala:145)
at scala.collection.parallel.mutable.ParHashSetCombiner.result(ParHashSet.scala:138)
at scala.collection.parallel.mutable.ParHashSetCombiner.result(ParHashSet.scala:116)
at scala.collection.parallel.ParIterableLike$$anonfun$flatMap$1$$anonfun$apply$3.apply(ParIterableLike.scala:513)
at scala.collection.parallel.ParIterableLike$$anonfun$flatMap$1$$anonfun$apply$3.apply(ParIterableLike.scala:513)
at scala.collection.parallel.ParIterableLike$$anon$13$$anon$4.map(ParIterableLike.scala:297)
at scala.collection.parallel.ParIterableLike$ResultMapping.leaf(ParIterableLike.scala:884)
at scala.collection.parallel.Tasks$Task$$anonfun$tryLeaf$1.apply$mcV$sp(Tasks.scala:66)
at scala.collection.parallel.Tasks$Task$class.tryLeaf(Tasks.scala:68)
at scala.collection.parallel.ParIterableLike$ResultMapping.tryLeaf(ParIterableLike.scala:879)
at scala.collection.parallel.AdaptiveWorkStealingTasks$TaskImpl$class.compute(Tasks.scala:164)
at scala.collection.parallel.AdaptiveWorkStealingForkJoinTasks$TaskImpl.compute(Tasks.scala:509)
at scala.concurrent.forkjoin.RecursiveAction.exec(RecursiveAction.java:147)
at scala.concurrent.forkjoin.ForkJoinTask.quietlyExec(ForkJoinTask.java:422)
at scala.concurrent.forkjoin.ForkJoinWorkerThread.mainLoop(ForkJoinWorkerThread.java:340)
at scala.concurrent.forkjoin.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:325)

Where the ellipses denote around 100 lines of exceptions. Playing with the N, and M values in the attached program affect the behavior. If they are both significantly smaller, then the program runs to completion and produces the expected results. I imagine there is some sort of error condition in the parallel logic, because, behind the scenes there are attempted accesses to outrageous array indices.
@scabug
Copy link
Author

scabug commented Jun 7, 2011

Imported From: https://issues.scala-lang.org/browse/SI-4678?orig=1
Reporter: Rob Patro (robp)
Affected Versions: 2.9.0
Attachments:

@scabug
Copy link
Author

scabug commented Jun 7, 2011

Rob Patro (robp) said:
Note that the exact same code behaves as expected if using sequential collections.

@scabug
Copy link
Author

scabug commented Jun 7, 2011

@dcsobral said:
Note that decreasing either N or M to 1400 is enough to get this code to work. I'd venture there's an Int wrap-around happening somewhere, or, perhaps, just a memory exaustion of some type being masked by the out of range errors.

@scabug
Copy link
Author

scabug commented Jun 7, 2011

Rob Patro (robp) said:
I've tested the same code replacing the mutable ParHashMap with an immutable ParMap, and this also solves the problem. I also ran this test on a fairly large server, and set the JVM heap space to 32Gb; the same error listed above occurs, so I'd wager against memory exhaustion. I'm not sure how the parallel hashset combiners work in the backend, so an Int wrap-around is possible, but it would have to be something that doesn't occur in the immutable ParMap case.

@scabug
Copy link
Author

scabug commented Jun 17, 2011

@axel22 said:
This is an issue with the sizeForThreshold method in FlatHashTables as far as I can tell - the integer load factor and it's denominator rounding causes an arithmetic overflow, so the target size for the hashtable array is miscomputed.

@scabug
Copy link
Author

scabug commented Jun 20, 2011

Commit Message Bot (anonymous) said:
(prokopec in r25112) Fixed an overflow which occurs in hashtable size computations. Fixes #4678.

No review.

@scabug scabug closed this as completed Jun 20, 2011
@scabug
Copy link
Author

scabug commented Feb 4, 2013

Dan Peebles (mysteriousdan) said:
What version was this fixed in? I'm encountering a very similar-looking issue:

scala> scala.util.Properties.versionString
res35: java.lang.String = version 2.9.1.final

scala> HashSet(1 to 100: _*).par.map(identity)
java.lang.ArrayIndexOutOfBoundsException: 256
        at scala.collection.parallel.mutable.ParFlatHashTable$ParFlatHashTableIterator.scan(ParFlatHashTable.scala:36)
        at scala.collection.parallel.mutable.ParFlatHashTable$ParFlatHashTableIterator.next(ParFlatHashTable.scala:53)
        at scala.collection.parallel.AugmentedIterableIterator$class.map2combiner(RemainsIterator.scala:115)
        at scala.collection.parallel.mutable.ParFlatHashTable$ParFlatHashTableIterator.map2combiner(ParFlatHashTable.scala:26)
        at scala.collection.parallel.ParIterableLike$Map.leaf(ParIterableLike.scala:971)
        at scala.collection.parallel.Tasks$Task$$anonfun$tryLeaf$1.apply$mcV$sp(Tasks.scala:66)
        at scala.collection.parallel.Tasks$Task$class.tryLeaf(Tasks.scala:68)
        at scala.collection.parallel.ParIterableLike$Map.tryLeaf(ParIterableLike.scala:968)
        at scala.collection.parallel.AdaptiveWorkStealingTasks$TaskImpl$class.internal(Tasks.scala:179)
        at scala.collection.parallel.AdaptiveWorkStealingForkJoinTasks$TaskImpl.internal(Tasks.scala:509)
        at scala.collection.parallel.AdaptiveWorkStealingTasks$TaskImpl$class.compute(Tasks.scala:164)
        at scala.collection.parallel.AdaptiveWorkStealingForkJoinTasks$TaskImpl.compute(Tasks.scala:509)
        at scala.concurrent.forkjoin.RecursiveAction.exec(RecursiveAction.java:147)
        at scala.concurrent.forkjoin.ForkJoinTask.quietlyExec(ForkJoinTask.java:422)
        at scala.concurrent.forkjoin.ForkJoinWorkerThread.mainLoop(ForkJoinWorkerThread.java:340)
        at scala.concurrent.forkjoin.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:325)

@scabug scabug added the critical label Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@axel22 axel22

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@axel22 @scabug