Open devinrsmith opened 4 months ago
devinrsmith
commented
4 months ago Here's the conditions that cause the infinite loop:
lo = 4
hi = 5
searchValue = NaN
valuesToSearch = [-Infinity, NULL_DOUBLE, -0.0, Infinity, NaN]mid = 4
testValue = NaN
moveHi = trueThe infinite loop isn't in this inner layer; it's the combination of the inner and outer layer.
Note that valuesToSearch is not in order wrt DH comparisons; NULL_DOUBLE should be first if it were.
devinrsmith
commented
4 months ago /**
* Insert new valuesToInsert into this SSMS. The valuesToInsert to insert must be sorted, without duplicates.
*
* The valuesToInsert and counts chunks will be modified during this call, and the resulting chunks are undefined.
*
* @param valuesToInsert the valuesToInsert to insert
* @param counts the number of times each value occurs
* @return true if any new values were inserted
*/
boolean insert(WritableChunk<? extends Values> valuesToInsert, WritableIntChunk<ChunkLengths> counts);The valuesToInsert are being sorted in DoubleCompactKernel#compactAndCount using WritableDoubleChunk#sort(int, int), which is using java.util.Arrays#sort(double[], int, int) which does not sort according to DH sort order.
devinrsmith
commented
4 months ago It appears even if WritableDoubleChunk#sort(int, int) is "fixed" (it may be breaking some other implicit assumption somewhere else, TBD), DoubleSegmentedSortedMultiset#insertExistingIntoLeaf can get into an infinite loop.
Likely b/c DoubleSegmentedSortedMultiset is using
private static boolean eq(double lhs, double rhs) {
// region equality function
return lhs == rhs;
// endregion equality function
}w/ nextValue = NaN
devinrsmith
commented
4 months ago The sort order needs to be more clearly defined wrt CompactKernel#compactAndCount and SegmentedSortedMultiSet#insert; are one or both java array sorting order, DH sorting order, or a mix?
devinrsmith
commented
4 months ago WritableChunk explicitly declares Java's "primitive" defined ordering
/**
* Sort this chunk in-place using Java's primitive defined ordering.
* <p>
* Of note is that nulls or NaNs are not sorted according to Deephaven ordering rules.
*/
void sort();which is not technically true (since Arrays#sort is different than primitive ordering); and furthermore, WritableCharChunk applies a "fixup".
Potential infinite loop. Easy to reproduce, although the reproducer is not minimized yet.
results in spinning computation. Resulting stacktrace: