[spark] branch master updated: [SPARK-26953][CORE][TEST] Test TimSort for ArrayIndexOutOfBoundsException
This is an automated email from the ASF dual-hosted git repository.
srowen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new 2d2fb34 [SPARK-26953][CORE][TEST] Test TimSort for
ArrayIndexOutOfBoundsException
2d2fb34 is described below
commit 2d2fb34b93a55af7e45191c8974bb55a0ed76e87
Author: Maxim Gekk
AuthorDate: Sun Feb 24 17:37:32 2019 -0600
[SPARK-26953][CORE][TEST] Test TimSort for ArrayIndexOutOfBoundsException
## What changes were proposed in this pull request?
In the PR, I propose to test the input showed at the end of the article:
https://arxiv.org/pdf/1805.08612.pdf . The difference of the test and paper's
test is type of array. This test allocates arrays of bytes instead of array of
ints.
## How was this patch tested?
New test is added to `SorterSuite`.
Closes #23856 from MaxGekk/timsort-bug-fix.
Authored-by: Maxim Gekk
Signed-off-by: Sean Owen
---
.../apache/spark/util/collection/SorterSuite.scala | 129 +
1 file changed, 129 insertions(+)
diff --git
a/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
b/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
index a14fb76..35a369e 100644
--- a/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
+++ b/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
@@ -74,6 +74,103 @@ class SorterSuite extends SparkFunSuite with Logging {
(0 to data.length - 2).foreach(i => assert(data(i) <= data(i + 1)))
}
+ test("java.lang.ArrayIndexOutOfBoundsException in TimSort") {
+// scalastyle:off
+val runLengths = Array(76405736, 74830360, 1181532, 787688, 1575376,
2363064, 3938440, 6301504,
+ 1181532, 393844, 15753760, 1575376, 787688, 393844, 1969220, 3150752,
1181532,787688, 5513816, 3938440,
+ 1181532, 787688, 1575376, 18116824, 1181532, 787688, 1575376, 2363064,
3938440,787688, 26781392, 1181532,
+ 787688, 1575376, 2363064, 393844, 4332284, 1181532, 787688, 1575376,
12209164,1181532, 787688, 1575376,
+ 2363064, 787688, 393844, 4726128, 1575376, 787688, 1969220, 76405758,
53168940,1181532, 787688, 1575376,
+ 2363064, 3938440, 1575376, 787688, 393844, 10633788, 1181532, 787688,
1575376,2363064, 4332284, 1181532,
+ 787688, 1575376, 12996852, 1181532, 787688, 1575376, 2363064, 393844,
17329136,1575376, 787688, 393844,
+ 1969220, 3150752, 1181532, 393844, 7483036, 1575376, 787688, 1969220,
2756908,1181532, 787600, 76405780,
+ 38202802, 114608494, 66, 44, 88, 176, 352, 704, 1408, 2816, 5632, 11264,
22528,45056, 90112, 180224,
+ 360448, 720896, 1441792, 2883584, 5767168, 11387222, 22495132, 319836,
213224,426448, 639672, 1066120,
+ 1705792, 426448, 213224, 106612, 4584316, 426448, 213224, 106612,
533060,106612, 852896, 426448, 213224,
+ 1599180, 1172732, 319836, 213224, 426448, 5223988, 319836, 213224,
426448,639672, 1066120, 319836, 213224,
+ 7782676, 426448, 213224, 533060, 746284, 213224, 1705792, 319836,
213224,426448, 639672, 2238852, 426448,
+ 213224, 106612, 2345464, 426448, 213224, 106612, 533060, 106612,
852896,426448, 213224, 106612, 22921602,
+ 15245516, 319836, 213224, 426448, 639672, 1172732, 319836, 213224,
426448,3304972, 319836, 213224, 426448,
+ 639672, 213224, 1279344, 426448, 213224, 533060, 3838032, 319836,
213224,426448, 639672, 213224, 106612,
+ 5330600, 319836, 213224, 426448, 639672, 1066120, 213224, 2345464,
426448,213224, 106612, 533060, 106612,
+ 852896, 426448, 213224, 106524, 22921624, 11460724, 34382260, 66, 44,
88, 176,352, 704, 1408, 2816, 5632,
+ 11264, 22528, 45056, 90112, 180224, 360448, 720896, 1001792, 1783584,
2649020,6739370, 102630, 68420,
+ 136840, 205260, 342100, 547360, 102630, 68420, 1436820, 102630, 68420,
136840,205260, 342100, 547360,
+ 102630, 68420, 136840, 205260, 68420, 34210, 1607870, 102630, 68420,
136840,205260, 342100, 68420, 34210,
+ 2428910, 102630, 68420, 136840, 205260, 34210, 410520, 102630, 68420,
136840,1094720, 102630, 68420,
+ 136840, 205260, 68420, 34210, 444730, 136840, 68420, 34210, 171050,
34210,6876232, 4618350, 102630, 68420,
+ 136840, 205260, 34210, 342100, 136840, 68420, 34210, 992090, 102630,
68420,136840, 205260, 68420, 342100,
+ 205260, 102630, 68420, 1163140, 102630, 68420, 136840, 205260, 68420,
1607870,102630, 68420, 136840,
+ 205260, 342100, 34210, 684200, 136840, 68420, 171050, 239470, 102630,
68332,6876254, 3438028, 10314194, 66,
+ 44, 88, 176, 352, 704, 1408, 2816, 5632, 11264, 22528, 45056, 90112,
180224,360448, 500896, 840554,
+ 2018720, 32736, 21824, 43648, 65472, 21824, 10912, 141856, 43648, 21824,
10912,54560, 10912, 425568, 43648,
+ 21824, 54560, 76384, 21824, 10912, 185504, 32736, 21824, 43648, 65472,
[spark] branch master updated: [SPARK-26953][CORE][TEST] Test TimSort for ArrayIndexOutOfBoundsException
This is an automated email from the ASF dual-hosted git repository.
srowen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new 2d2fb34 [SPARK-26953][CORE][TEST] Test TimSort for
ArrayIndexOutOfBoundsException
2d2fb34 is described below
commit 2d2fb34b93a55af7e45191c8974bb55a0ed76e87
Author: Maxim Gekk
AuthorDate: Sun Feb 24 17:37:32 2019 -0600
[SPARK-26953][CORE][TEST] Test TimSort for ArrayIndexOutOfBoundsException
## What changes were proposed in this pull request?
In the PR, I propose to test the input showed at the end of the article:
https://arxiv.org/pdf/1805.08612.pdf . The difference of the test and paper's
test is type of array. This test allocates arrays of bytes instead of array of
ints.
## How was this patch tested?
New test is added to `SorterSuite`.
Closes #23856 from MaxGekk/timsort-bug-fix.
Authored-by: Maxim Gekk
Signed-off-by: Sean Owen
---
.../apache/spark/util/collection/SorterSuite.scala | 129 +
1 file changed, 129 insertions(+)
diff --git
a/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
b/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
index a14fb76..35a369e 100644
--- a/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
+++ b/core/src/test/scala/org/apache/spark/util/collection/SorterSuite.scala
@@ -74,6 +74,103 @@ class SorterSuite extends SparkFunSuite with Logging {
(0 to data.length - 2).foreach(i => assert(data(i) <= data(i + 1)))
}
+ test("java.lang.ArrayIndexOutOfBoundsException in TimSort") {
+// scalastyle:off
+val runLengths = Array(76405736, 74830360, 1181532, 787688, 1575376,
2363064, 3938440, 6301504,
+ 1181532, 393844, 15753760, 1575376, 787688, 393844, 1969220, 3150752,
1181532,787688, 5513816, 3938440,
+ 1181532, 787688, 1575376, 18116824, 1181532, 787688, 1575376, 2363064,
3938440,787688, 26781392, 1181532,
+ 787688, 1575376, 2363064, 393844, 4332284, 1181532, 787688, 1575376,
12209164,1181532, 787688, 1575376,
+ 2363064, 787688, 393844, 4726128, 1575376, 787688, 1969220, 76405758,
53168940,1181532, 787688, 1575376,
+ 2363064, 3938440, 1575376, 787688, 393844, 10633788, 1181532, 787688,
1575376,2363064, 4332284, 1181532,
+ 787688, 1575376, 12996852, 1181532, 787688, 1575376, 2363064, 393844,
17329136,1575376, 787688, 393844,
+ 1969220, 3150752, 1181532, 393844, 7483036, 1575376, 787688, 1969220,
2756908,1181532, 787600, 76405780,
+ 38202802, 114608494, 66, 44, 88, 176, 352, 704, 1408, 2816, 5632, 11264,
22528,45056, 90112, 180224,
+ 360448, 720896, 1441792, 2883584, 5767168, 11387222, 22495132, 319836,
213224,426448, 639672, 1066120,
+ 1705792, 426448, 213224, 106612, 4584316, 426448, 213224, 106612,
533060,106612, 852896, 426448, 213224,
+ 1599180, 1172732, 319836, 213224, 426448, 5223988, 319836, 213224,
426448,639672, 1066120, 319836, 213224,
+ 7782676, 426448, 213224, 533060, 746284, 213224, 1705792, 319836,
213224,426448, 639672, 2238852, 426448,
+ 213224, 106612, 2345464, 426448, 213224, 106612, 533060, 106612,
852896,426448, 213224, 106612, 22921602,
+ 15245516, 319836, 213224, 426448, 639672, 1172732, 319836, 213224,
426448,3304972, 319836, 213224, 426448,
+ 639672, 213224, 1279344, 426448, 213224, 533060, 3838032, 319836,
213224,426448, 639672, 213224, 106612,
+ 5330600, 319836, 213224, 426448, 639672, 1066120, 213224, 2345464,
426448,213224, 106612, 533060, 106612,
+ 852896, 426448, 213224, 106524, 22921624, 11460724, 34382260, 66, 44,
88, 176,352, 704, 1408, 2816, 5632,
+ 11264, 22528, 45056, 90112, 180224, 360448, 720896, 1001792, 1783584,
2649020,6739370, 102630, 68420,
+ 136840, 205260, 342100, 547360, 102630, 68420, 1436820, 102630, 68420,
136840,205260, 342100, 547360,
+ 102630, 68420, 136840, 205260, 68420, 34210, 1607870, 102630, 68420,
136840,205260, 342100, 68420, 34210,
+ 2428910, 102630, 68420, 136840, 205260, 34210, 410520, 102630, 68420,
136840,1094720, 102630, 68420,
+ 136840, 205260, 68420, 34210, 444730, 136840, 68420, 34210, 171050,
34210,6876232, 4618350, 102630, 68420,
+ 136840, 205260, 34210, 342100, 136840, 68420, 34210, 992090, 102630,
68420,136840, 205260, 68420, 342100,
+ 205260, 102630, 68420, 1163140, 102630, 68420, 136840, 205260, 68420,
1607870,102630, 68420, 136840,
+ 205260, 342100, 34210, 684200, 136840, 68420, 171050, 239470, 102630,
68332,6876254, 3438028, 10314194, 66,
+ 44, 88, 176, 352, 704, 1408, 2816, 5632, 11264, 22528, 45056, 90112,
180224,360448, 500896, 840554,
+ 2018720, 32736, 21824, 43648, 65472, 21824, 10912, 141856, 43648, 21824,
10912,54560, 10912, 425568, 43648,
+ 21824, 54560, 76384, 21824, 10912, 185504, 32736, 21824, 43648, 65472,
