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