Sorting floating-point values, and NaN
Jonathan M Davis
jmdavisProg at gmx.com
Tue Nov 12 00:10:02 PST 2013
On Tuesday, November 12, 2013 05:41:55 Vladimir Panteleev wrote:
> double[] arr = [1, 2, 3, double.nan, 1, 2];
> assert(arr.isSorted);
> arr.sort();
>
> This code will fail with an assert error, but not the one on the
> second line. Rather, it will fail inside std.range, when sort
> calls assumeSorted, which checks elements in an order different
> than sort and isSorted.
>
> Here's a case where the odd way NaN interacts with generic code
> messes things up in an ugly way.
>
> This is concerning. It's very easy to overlook this while writing
> an application, and it can become a hidden vulnerability.
>
> We can't fix the operators... but, perhaps, we could define a
> safe default comparison predicate (e.g. std.algorithm.less) for
> use with sorting and related tasks? Aside from bitwise
> comparison, is it even possible to efficiently compare
> floating-point values in a way suitable for sorting?
The check could be special-cased for floating point values so that it takes NaN
into account, but NaN pretty much screws with everything. Once it's there,
pretty much anything involving math or comparisons is going to go bad. So, you
could argue that it's a bug in the program if sort is passed a NaN and that
the assertion in sort is therefore perfectly valid. You can't really sort
anything with NaN in it anyway.
- Jonathan M Davis
More information about the Digitalmars-d
mailing list