You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@spark.apache.org by andrewor14 <gi...@git.apache.org> on 2014/02/21 04:17:40 UTC
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
GitHub user andrewor14 opened a pull request:
https://github.com/apache/incubator-spark/pull/624
External spilling - fix Int.MaxValue hash code collision bug
The original poster of this bug is @guojc, who opened a PR that preceded this one at https://github.com/apache/incubator-spark/pull/612.
ExternalAppendOnlyMap uses key hash code to order the buffer streams from which spilled files are read back into memory. When a buffer stream is empty, the default hash code for that stream is equal to Int.MaxValue. This is, however, a perfectly legitimate candidate for a key hash code. When reading from a spilled map containing such a key, a hash collision may occur, in which case we attempt to read from an empty stream and throw NoSuchElementException.
The fix is to maintain the invariant that empty buffer streams are never added back to the queue to be considered. This guarantees that we never read from an empty buffer stream, ever again.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/andrewor14/incubator-spark spilling-bug
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-spark/pull/624.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #624
----
commit 21c1a39ebe7d0f10519621f3ef54aa6e89c08441
Author: Andrew Or <an...@gmail.com>
Date: 2014-02-21T02:04:27Z
Add hash collision tests to ExternalAppendOnlyMapSuite
As of now, the test "spilling with hash collisions using the Int.MaxValue key" fails.
Fixing this behavior is the main goal of this PR.
commit c11f03b6e6e82617a826dc3acbd09a52760f143b
Author: Andrew Or <an...@gmail.com>
Date: 2014-02-21T02:58:18Z
Fix Int.MaxValue hash collision bug in ExternalAppendOnlyMap
The solution is to maintain the invariant that mergeHeap contains only non-empty
StreamBuffer's at the time next() is called.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35695580
Merged build triggered.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by pwendell <gi...@git.apache.org>.
Github user pwendell commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35793996
Hmm... github API having issues so it'll have to wait.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35794056
Merged build finished.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35701667
Merged build finished.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35701669
All automated tests passed.
Refer to this link for build results: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/12791/
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by pwendell <gi...@git.apache.org>.
Github user pwendell commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35793977
Thanks @andrewor14 I'll merge this.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35793074
Merged build triggered.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by pwendell <gi...@git.apache.org>.
Github user pwendell commented on a diff in the pull request:
https://github.com/apache/incubator-spark/pull/624#discussion_r9958856
--- Diff: core/src/main/scala/org/apache/spark/util/collection/ExternalAppendOnlyMap.scala ---
@@ -323,13 +327,12 @@ private[spark] class ExternalAppendOnlyMap[K, V, C](
private case class StreamBuffer(iterator: Iterator[(K, C)], pairs: ArrayBuffer[(K, C)])
extends Comparable[StreamBuffer] {
- def minKeyHash: Int = {
- if (pairs.length > 0){
- // pairs are already sorted by key hash
- pairs(0)._1.hashCode()
- } else {
- Int.MaxValue
- }
+ def isEmpty = pairs.isEmpty
+
+ // Invalid if there are no more pairs in this stream
--- End diff --
nit: but maybe put this comment above the assert line rather than the function?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35697469
Merged build finished.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by pwendell <gi...@git.apache.org>.
Github user pwendell commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35776248
@andrewor14 Looks good to me. This adds a few function calls in the `next` path... would you mind doing some local regression testing just to make sure there are no regressions? I doubt there are but if you did a local test I'd feel better about it before merging in into 0.9.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35701666
Merged build finished.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by pwendell <gi...@git.apache.org>.
Github user pwendell commented on a diff in the pull request:
https://github.com/apache/incubator-spark/pull/624#discussion_r9959040
--- Diff: core/src/main/scala/org/apache/spark/util/collection/ExternalAppendOnlyMap.scala ---
@@ -302,12 +304,14 @@ private[spark] class ExternalAppendOnlyMap[K, V, C](
mergedBuffers += newBuffer
}
- // Repopulate each visited stream buffer and add it back to the merge heap
+ // Repopulate each visited stream buffer and add it back to the queue if it is non-empty
mergedBuffers.foreach { buffer =>
- if (buffer.pairs.length == 0) {
+ if (buffer.isEmpty) {
buffer.pairs ++= getMorePairs(buffer.iterator)
}
- mergeHeap.enqueue(buffer)
+ if (!buffer.isEmpty) {
--- End diff --
shouldn't this just be an `else`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35699760
Merged build triggered.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35695581
Merged build started.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35699761
Merged build started.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by aarondav <gi...@git.apache.org>.
Github user aarondav commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35705443
Thanks @guojc and @andrewor14! LGTM. Maybe @pwendell wants to take a look as well?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35699690
Merged build triggered.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35697471
One or more automated tests failed
Refer to this link for build results: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/12790/
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35699691
Merged build started.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by andrewor14 <gi...@git.apache.org>.
Github user andrewor14 commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35792355
@pwendell I did a couple of tests locally and found a very slight speed-up with the latest commit, which replaces the usages of ```isEmpty``` and ```size``` with ```length```. More details are included in the commit message but I think this is ready for merge.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/incubator-spark/pull/624
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by pwendell <gi...@git.apache.org>.
Github user pwendell commented on a diff in the pull request:
https://github.com/apache/incubator-spark/pull/624#discussion_r9958879
--- Diff: core/src/main/scala/org/apache/spark/util/collection/ExternalAppendOnlyMap.scala ---
@@ -323,13 +327,12 @@ private[spark] class ExternalAppendOnlyMap[K, V, C](
private case class StreamBuffer(iterator: Iterator[(K, C)], pairs: ArrayBuffer[(K, C)])
extends Comparable[StreamBuffer] {
- def minKeyHash: Int = {
- if (pairs.length > 0){
- // pairs are already sorted by key hash
- pairs(0)._1.hashCode()
- } else {
- Int.MaxValue
- }
+ def isEmpty = pairs.isEmpty
+
+ // Invalid if there are no more pairs in this stream
--- End diff --
ah nvm, after thinking more I guess it's better where it is
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: External spilling - fix Int.MaxValue...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35701668
All automated tests passed.
Refer to this link for build results: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/12792/
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35794057
All automated tests passed.
Refer to this link for build results: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/12806/
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---
[GitHub] incubator-spark pull request: [SPARK-1113] External spilling - fix...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/incubator-spark/pull/624#issuecomment-35793075
Merged build started.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastructure@apache.org or file a JIRA ticket with INFRA.
---