Skip to content

Commit b4118e0

Browse files
nchammasdongjoon-hyun
authored andcommitted
[SPARK-45599][CORE][3.5] Use object equality in OpenHashSet
### What changes were proposed in this pull request? This is a backport of fcc5dbc / #45036 with a tweak so that it works on Scala 2.12. ### Why are the changes needed? This is a correctness bug fix. The original fix against `master` suppresses a warning category that doesn't exist on certain versions of Scala 2.13 and 2.12, and the exact versions are [not documented anywhere][1]. To be safe, this backport simply suppresses all warnings instead of just `other-non-cooperative-equals`. It would be interesting to see if `-Wconf:nowarn` complains, since the warning about non-cooperative equals itself is also not thrown on all versions of Scala, but I don't think that's a priority. [1]: scala/scala#8120 (comment) ### Does this PR introduce _any_ user-facing change? Yes. ### How was this patch tested? CI + added tests. ### Was this patch authored or co-authored using generative AI tooling? No. Closes #45296 from nchammas/SPARK-45599-OpenHashSet. Authored-by: Nicholas Chammas <[email protected]> Signed-off-by: Dongjoon Hyun <[email protected]>
1 parent cbf25fb commit b4118e0

17 files changed

Lines changed: 268 additions & 3 deletions

File tree

‎core/src/main/scala/org/apache/spark/util/collection/OpenHashSet.scala‎

Lines changed: 13 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,17 @@ class OpenHashSet[@specialized(Long, Int, Double, Float) T: ClassTag](
126126
this
127127
}
128128

129+
/**
130+
* Check if a key exists at the provided position using object equality rather than
131+
* cooperative equality. Otherwise, hash sets will mishandle values for which `==`
132+
* and `equals` return different results, like 0.0/-0.0 and NaN/NaN.
133+
*
134+
* See: https://issues.apache.org/jira/browse/SPARK-45599
135+
*/
136+
@annotation.nowarn
137+
private def keyExistsAtPos(k: T, pos: Int) =
138+
_data(pos) equals k
139+
129140
/**
130141
* Add an element to the set. This one differs from add in that it doesn't trigger rehashing.
131142
* The caller is responsible for calling rehashIfNeeded.
@@ -146,8 +157,7 @@ class OpenHashSet[@specialized(Long, Int, Double, Float) T: ClassTag](
146157
_bitset.set(pos)
147158
_size += 1
148159
return pos | NONEXISTENCE_MASK
149-
} else if (_data(pos) == k) {
150-
// Found an existing key.
160+
} else if (keyExistsAtPos(k, pos)) {
151161
return pos
152162
} else {
153163
// quadratic probing with values increase by 1, 2, 3, ...
@@ -181,7 +191,7 @@ class OpenHashSet[@specialized(Long, Int, Double, Float) T: ClassTag](
181191
while (true) {
182192
if (!_bitset.get(pos)) {
183193
return INVALID_POS
184-
} else if (k == _data(pos)) {
194+
} else if (keyExistsAtPos(k, pos)) {
185195
return pos
186196
} else {
187197
// quadratic probing with values increase by 1, 2, 3, ...

‎core/src/test/scala/org/apache/spark/util/collection/OpenHashMapSuite.scala‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -249,4 +249,34 @@ class OpenHashMapSuite extends SparkFunSuite with Matchers {
249249
map(null) = null
250250
assert(map.get(null) === Some(null))
251251
}
252+
253+
test("SPARK-45599: 0.0 and -0.0 should count distinctly; NaNs should count together") {
254+
// Exactly these elements provided in roughly this order trigger a condition where lookups of
255+
// 0.0 and -0.0 in the bitset happen to collide, causing their counts to be merged incorrectly
256+
// and inconsistently if `==` is used to check for key equality.
257+
val spark45599Repro = Seq(
258+
Double.NaN,
259+
2.0,
260+
168.0,
261+
Double.NaN,
262+
Double.NaN,
263+
-0.0,
264+
153.0,
265+
0.0
266+
)
267+
268+
val map1 = new OpenHashMap[Double, Int]()
269+
spark45599Repro.foreach(map1.changeValue(_, 1, {_ + 1}))
270+
assert(map1(0.0) == 1)
271+
assert(map1(-0.0) == 1)
272+
assert(map1(Double.NaN) == 3)
273+
274+
val map2 = new OpenHashMap[Double, Int]()
275+
// Simply changing the order in which the elements are added to the map should not change the
276+
// counts for 0.0 and -0.0.
277+
spark45599Repro.reverse.foreach(map2.changeValue(_, 1, {_ + 1}))
278+
assert(map2(0.0) == 1)
279+
assert(map2(-0.0) == 1)
280+
assert(map2(Double.NaN) == 3)
281+
}
252282
}

‎core/src/test/scala/org/apache/spark/util/collection/OpenHashSetSuite.scala‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -269,4 +269,43 @@ class OpenHashSetSuite extends SparkFunSuite with Matchers {
269269
assert(pos1 == pos2)
270270
}
271271
}
272+
273+
test("SPARK-45599: 0.0 and -0.0 are equal but not the same") {
274+
// Therefore, 0.0 and -0.0 should get separate entries in the hash set.
275+
//
276+
// Exactly these elements provided in roughly this order will trigger the following scenario:
277+
// When probing the bitset in `getPos(-0.0)`, the loop will happen upon the entry for 0.0.
278+
// In the old logic pre-SPARK-45599, the loop will find that the bit is set and, because
279+
// -0.0 == 0.0, it will think that's the position of -0.0. But in reality this is the position
280+
// of 0.0. So -0.0 and 0.0 will be stored at different positions, but `getPos()` will return
281+
// the same position for them. This can cause users of OpenHashSet, like OpenHashMap, to
282+
// return the wrong value for a key based on whether or not this bitset lookup collision
283+
// happens.
284+
val spark45599Repro = Seq(
285+
Double.NaN,
286+
2.0,
287+
168.0,
288+
Double.NaN,
289+
Double.NaN,
290+
-0.0,
291+
153.0,
292+
0.0
293+
)
294+
val set = new OpenHashSet[Double]()
295+
spark45599Repro.foreach(set.add)
296+
assert(set.size == 6)
297+
val zeroPos = set.getPos(0.0)
298+
val negZeroPos = set.getPos(-0.0)
299+
assert(zeroPos != negZeroPos)
300+
}
301+
302+
test("SPARK-45599: NaN and NaN are the same but not equal") {
303+
// Any mathematical comparison to NaN will return false, but when we place it in
304+
// a hash set we want the lookup to work like a "normal" value.
305+
val set = new OpenHashSet[Double]()
306+
set.add(Double.NaN)
307+
set.add(Double.NaN)
308+
assert(set.contains(Double.NaN))
309+
assert(set.size == 1)
310+
}
272311
}

‎sql/core/src/test/resources/sql-tests/analyzer-results/ansi/array.sql.out‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -747,3 +747,17 @@ select array_prepend(array(CAST(NULL AS String)), CAST(NULL AS String))
747747
-- !query analysis
748748
Project [array_prepend(array(cast(null as string)), cast(null as string)) AS array_prepend(array(CAST(NULL AS STRING)), CAST(NULL AS STRING))#x]
749749
+- OneRowRelation
750+
751+
752+
-- !query
753+
select array_union(array(0.0, -0.0, DOUBLE("NaN")), array(0.0, -0.0, DOUBLE("NaN")))
754+
-- !query analysis
755+
Project [array_union(array(cast(0.0 as double), cast(0.0 as double), cast(NaN as double)), array(cast(0.0 as double), cast(0.0 as double), cast(NaN as double))) AS array_union(array(0.0, 0.0, NaN), array(0.0, 0.0, NaN))#x]
756+
+- OneRowRelation
757+
758+
759+
-- !query
760+
select array_distinct(array(0.0, -0.0, -0.0, DOUBLE("NaN"), DOUBLE("NaN")))
761+
-- !query analysis
762+
Project [array_distinct(array(cast(0.0 as double), cast(0.0 as double), cast(0.0 as double), cast(NaN as double), cast(NaN as double))) AS array_distinct(array(0.0, 0.0, 0.0, NaN, NaN))#x]
763+
+- OneRowRelation

‎sql/core/src/test/resources/sql-tests/analyzer-results/ansi/literals.sql.out‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -692,3 +692,10 @@ org.apache.spark.sql.catalyst.ExtendedAnalysisException
692692
"fragment" : "-x'2379ACFe'"
693693
} ]
694694
}
695+
696+
697+
-- !query
698+
select -0, -0.0
699+
-- !query analysis
700+
Project [0 AS 0#x, 0.0 AS 0.0#x]
701+
+- OneRowRelation

‎sql/core/src/test/resources/sql-tests/analyzer-results/array.sql.out‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -747,3 +747,17 @@ select array_prepend(array(CAST(NULL AS String)), CAST(NULL AS String))
747747
-- !query analysis
748748
Project [array_prepend(array(cast(null as string)), cast(null as string)) AS array_prepend(array(CAST(NULL AS STRING)), CAST(NULL AS STRING))#x]
749749
+- OneRowRelation
750+
751+
752+
-- !query
753+
select array_union(array(0.0, -0.0, DOUBLE("NaN")), array(0.0, -0.0, DOUBLE("NaN")))
754+
-- !query analysis
755+
Project [array_union(array(cast(0.0 as double), cast(0.0 as double), cast(NaN as double)), array(cast(0.0 as double), cast(0.0 as double), cast(NaN as double))) AS array_union(array(0.0, 0.0, NaN), array(0.0, 0.0, NaN))#x]
756+
+- OneRowRelation
757+
758+
759+
-- !query
760+
select array_distinct(array(0.0, -0.0, -0.0, DOUBLE("NaN"), DOUBLE("NaN")))
761+
-- !query analysis
762+
Project [array_distinct(array(cast(0.0 as double), cast(0.0 as double), cast(0.0 as double), cast(NaN as double), cast(NaN as double))) AS array_distinct(array(0.0, 0.0, 0.0, NaN, NaN))#x]
763+
+- OneRowRelation

‎sql/core/src/test/resources/sql-tests/analyzer-results/group-by.sql.out‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1196,3 +1196,22 @@ Aggregate [c#x], [(c#x * 2) AS d#x]
11961196
+- Project [if ((a#x < 0)) 0 else a#x AS b#x]
11971197
+- SubqueryAlias t1
11981198
+- LocalRelation [a#x]
1199+
1200+
1201+
-- !query
1202+
SELECT col1, count(*) AS cnt
1203+
FROM VALUES
1204+
(0.0),
1205+
(-0.0),
1206+
(double('NaN')),
1207+
(double('NaN')),
1208+
(double('Infinity')),
1209+
(double('Infinity')),
1210+
(-double('Infinity')),
1211+
(-double('Infinity'))
1212+
GROUP BY col1
1213+
ORDER BY col1
1214+
-- !query analysis
1215+
Sort [col1#x ASC NULLS FIRST], true
1216+
+- Aggregate [col1#x], [col1#x, count(1) AS cnt#xL]
1217+
+- LocalRelation [col1#x]

‎sql/core/src/test/resources/sql-tests/analyzer-results/literals.sql.out‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -692,3 +692,10 @@ org.apache.spark.sql.catalyst.ExtendedAnalysisException
692692
"fragment" : "-x'2379ACFe'"
693693
} ]
694694
}
695+
696+
697+
-- !query
698+
select -0, -0.0
699+
-- !query analysis
700+
Project [0 AS 0#x, 0.0 AS 0.0#x]
701+
+- OneRowRelation

‎sql/core/src/test/resources/sql-tests/inputs/array.sql‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -177,3 +177,7 @@ select array_prepend(CAST(null AS ARRAY<String>), CAST(null as String));
177177
select array_prepend(array(), 1);
178178
select array_prepend(CAST(array() AS ARRAY<String>), CAST(NULL AS String));
179179
select array_prepend(array(CAST(NULL AS String)), CAST(NULL AS String));
180+
181+
-- SPARK-45599: Confirm 0.0, -0.0, and NaN are handled appropriately.
182+
select array_union(array(0.0, -0.0, DOUBLE("NaN")), array(0.0, -0.0, DOUBLE("NaN")));
183+
select array_distinct(array(0.0, -0.0, -0.0, DOUBLE("NaN"), DOUBLE("NaN")));

‎sql/core/src/test/resources/sql-tests/inputs/group-by.sql‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -264,3 +264,18 @@ FROM (
264264
GROUP BY b
265265
) t3
266266
GROUP BY c;
267+
268+
-- SPARK-45599: Check that "weird" doubles group and sort as desired.
269+
SELECT col1, count(*) AS cnt
270+
FROM VALUES
271+
(0.0),
272+
(-0.0),
273+
(double('NaN')),
274+
(double('NaN')),
275+
(double('Infinity')),
276+
(double('Infinity')),
277+
(-double('Infinity')),
278+
(-double('Infinity'))
279+
GROUP BY col1
280+
ORDER BY col1
281+
;

0 commit comments

Comments
 (0)