[std-interval] Interval comparison operators

Wed May 31 20:25:57 PDT 2006

George Corliss wrote:
> I recall someone telling me that IEEE 754 NaN admits multiple bit patterns.
> Hence, rather than overloading NaN as we seem to be doing, we might have
> several NaNs, each with distinct meanings, all of which propagate as IEEE
> 754.  I suspect that is a BAD idea because propagation of different NaN bit
> patterns is probably not portable across hardware.

   While bit patterns in NaNs may vary (they are represented as all 1s
in the exponent, and a non-zero fraction,) there are really only 2
categories of NaN that we should rely on, or expect to see : One is a
"quiet" NaN, (MSB of fraction = 1) and a "signaling" NaN, (MSB of
fraction = 0).  I know of no portable functions other than std::isnan()
(defined in cmath) which simply detects if it's a NaN or not, so you
shouldn't even expect to differentiate between these two.  You are also
not allowed to expect that if you set some specific bit pattern in the
fraction, that it will be maintained.

   The quiet NaN simply propagates itself when used in a calculation.
The signaling NaN, on the other hand, may trigger a floating-point
exception or trap when it is used in a calculation.  In UN*X-like
environments, you can set or modify the signal handler for SIGFPE to
handle/log the error condition when a signaling NaN is used.

   Using signaling NaNs is often very good, or necessary to prevent a
program that uses NaN from silently lying to you.

   For example, if variable "x" is set to a quiet NaN for some reason,
adding to it simply propagates the NaN value and you may see it:

   // x contains quiet NaN
   double b;
   b = x + 1.0;    // Value of b is now NaN, "tainted" by operation with x.

   If you display b, you'll see that its value is NaN, and you'll know
something is wrong.  However, if you do a boolean comparison, your
results may be silently poisoned and you'll never know you were wrong.

   // x contains (quiet) NaN
   if (x < 1.0)
       ... do the unintended thing, silently
   else
       ... do another unintended thing, silently

   What is going to happen when that comparison is made?  You'll never
know that a NaN was used in the comparison, and all further results of
your program may be wrong, or at the very least, untrustable!  (One
would be rather surprised and shocked to see how many of these
comparisons and invalid uses of NaNs there were in a product I worked on
until I added signaling NaN behavior to help enforce correctness.)

   Thus, an implementation that uses NaN should probably use signaling
NaNs to indicate the error condition.  When a *signaling* NaN is used in
the calculations above, a SIGFPE signal is generated, and the program's
incorrect behavior can be noted.  It would be nicer to flag an
exception, as signal handlers don't give you much chance to recover, but
it's probably better than continuing to run for two more weeks and lying
about your results.

   If used in a simple isnan() test, a signaling NaN doesn't trigger
signal handlers (at least in compilers I've seen.)  So that doesn't slow
you down.  If used in mathematical expressions, it does.

> The standard should specify the syntax and semantics, but not the
> implementation.  However, it would be unwise to specify something whose best
> implementation is "too" expensive, whatever "too" is.  Much of this NaN
> discussion probably does not belong in the standard, although having it
> available for implementers in another form should be a big help in having
> the proposed standard accepted.  This discussion is VERY helpful in
> formulating a wise specification.

   A clever implementer will probably make use of NaN for indicating
certain conditions and making the coding simpler.  A smart proposal will
probably be written as if NaN were being used.

> It sounds to me as though reliance on the properties of IEEE 754 NaN buys us
> so many benefits, that we probably prefer to accept any performance penalty
> for now and add to the chorus for improved performance for any NaN
> processing in future hardware.
> 
> Does anyone have hard experimental data on the performance costs of NaN?

   I've used NaNs widely in some large simulation/modelling projects.
Using them often buys quite a bit of performance *improvement* in
less-obvious ways.  The most obvious improvement is that memory usage is
often greatly reduced.  For example, if you want to have a large array
of double values, and have some way of indicating that each initialized
or not, NaN is an obvious choice.  The other options would be to
initialize to some number (dangerous, as that number might show up in
regular calculations), or to keep a separate flag indicating whether the
number was initialized or not.  Due to memory alignment issues, even
adding a boolean flag to your structure or class might double memory usage.

   This improves cache locality, and reduces the nonlinear performance
issues when swapping to disk or slower main memory.

   As for hard experimental data, here's some runs for a sample that
just adds either valid numbers (1.0) to a running sum, or NaN to that
same sum (which you'd never really want to do.)

Linux x86_64, g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1)

-O0:
add1:                   6880000 ticks   Sum: 1e+09
addQNaN:                5940000 ticks   Sum: nan
addSNaN:                6140000 ticks   Sum: nan

-O1:
add1:                   5970000 ticks   Sum: 1e+09
addQNaN:                5990000 ticks   Sum: nan
addSNaN:                6010000 ticks   Sum: nan

-O2:
add1:                   5800000 ticks   Sum: 1e+09
addQNaN:                5810000 ticks   Sum: nan
addSNaN:                5840000 ticks   Sum: nan

-O3:
add1:                   1830000 ticks   Sum: 1e+09
addQNaN:                1840000 ticks   Sum: nan
addSNaN:                1830000 ticks   Sum: nan

   In short, using NaNs in calculations don't make your program
significantly slower.  A real-world program would involve more memory
usage, and use of NaNs would possibly make it faster due to improved
cache locality.

   Program here:

   http://futureboy.us/temp/NaN.cc

-- 
  Alan Eliasen                 |  "When trouble is solved before it
  eliasen at mindspring.com       |    forms, who calls that clever?"
  http://futureboy.us/         |              --Sun Tzu