Latest revision as of 14:25, 9 February 2010

We will present some of the trade-offs for computation of IEEE arithmetic for REAL_64 and REAL_32 as implemented in EiffelStudio when enabling the Total Order on REALs option where NaN is not an unordered value but a value less than all the other values (note that in some other frameworks, we have seen it defined as the largest value). In other words:

• NaN = NaN yields True
• NaN < x for all x but NaN

To best show the trade-offs we will start by showing some benchmark results.

Note: This is an EiffelStudio specific extension to potentially help the ECMA standard committee in making a reasonable decision on the semantic of NaN, You can also read the following blog entry from Bertrand Meyer on the same subject Reflexivity, and other pillars of civilization.

Benchmarks

The code

The code below defines an equality function as well as a comparison function. The test is divided in two parts, first the initialization and then the computation.

static EIF_NATURAL_64 to_raw_bits (EIF_REAL_64 d) {
	return *((EIF_NATURAL_64 *)&d);
}
 
static int eif_is_nan_bits (EIF_NATURAL_64 value) {
		/* Clear the sign mark. */
    EIF_NATURAL_64 jvalue = (value & ~RTU64C(0x8000000000000000));
		/* Ensure that it starts with 0x7ff and that the mantissa is not 0. */
    return (jvalue > RTU64C(0x7ff0000000000000));
}
 
static int eif_is_nan (EIF_REAL_64 v) {
	EIF_NATURAL_64 value = *((EIF_NATURAL_64 *)&v);
	value &= ~RTU64C(0x8000000000000000);
	return (value > RTU64C(0x7ff0000000000000));
}
 
static int eif_is_nan_real_64 (EIF_REAL_64 v) {
#ifdef NAN1
	return v != v;
#elif defined(NAN2)
	EIF_NATURAL_64 value = *((EIF_NATURAL_64 *)&v);
	value &= ~RTU64C(0x8000000000000000);
	return (value > RTU64C(0x7ff0000000000000));
#elif defined(NAN3)
	EIF_REAL_64 *l_v = &v;
	return ((*((EIF_NATURAL_64 *)(l_v)) & RTU64C(0x7FF0000000000000))==RTU64C(0x7FF0000000000000)) &&
	          (*((EIF_NATURAL_64 *)(l_v)) & RTU64C(0x000FFFFFFFFFFFFF));
#elif defined(NAN4)
#ifdef _WIN32
	return _isnan(v);
#else
	return isnan(v);
#endif
#endif
 
static int eif_equal_real_64 (EIF_REAL_64 d1, EIF_REAL_64 d2) {
#ifdef METH1
		/* Here the base comparison is IEEE arithmetic. */
	return (d1 == d2);
#elif defined(METH2)
		/* Conversion to perform comparison on the binary representation. */
	EIF_NATURAL_64 f1 = to_raw_bits(d1);
	EIF_NATURAL_64 f2 = to_raw_bits(d2);
	return (f1 == f2 ? 1 : (eif_is_nan_bits (f1) && eif_is_nan_bits(f2)));
#elif defined(METH3)
		/* Use IEEE arithmetic to compare and find out if we have NaNs. */
	return (d1 == d2 ? 1 : ((d1 != d1) && (d2 != d2)));
#elif defined (METH4)
		/* Pessimist case, we assume that we compare mostly NaNs. */
	return (d1 == d1 ? d1 == d2 : d2 != d2);
#elif defined(METH5)
		/* Use IEEE arithmetic to compare but use binary representation to
		 * find out if we have NaNs. */
	return (d1 == d2 ? 1 : (eif_is_nan (d1) && eif_is_nan(d2)));
#endif
}
 
static int eif_is_less_real_64 (EIF_REAL_64 d1, EIF_REAL_64 d2) {
#ifdef METH1
		/* Here the base comparison is IEEE arithmetic. */
	return d1 < d2;
#elif defined(METH2)
		/* Use IEEE arithmetic to compare but use binary representation to
		 * find out if we have NaNs. */
	return (d1 < d2 ? 1 : eif_is_nan(d1) && !eif_is_nan(d2));
#elif defined(METH3)
		/* Use IEEE arithmetic to compare and find out if we have NaNs. */
	return (d1 < d2 ? 1 : (d1 != d1) && (d2 == d2));
#elif defined(METH4)
		/* Pessimist case, we assume that we compare mostly NaNs. */
	return (d1 == d1 ? d1 < d2 : d2 == d2);
#elif defined(METH5)
		/* Variation on METH3 using a different order for comparison. */
	return (eif_is_nan(d1) ? !eif_is_nan(d2) : d1 < d2);
#endif
}
 
 
#define ARR_SIZE 100000
 
int main(void) {
	EIF_NATURAL_64 res, i;
	EIF_REAL_64 *d = (EIF_REAL_64 *) malloc (sizeof(EIF_REAL_64) * ARR_SIZE + 1);
 
		/* Initialization of `d'. */
	...
 
	for (i = 0; i <= 0x3FFFFFFF; i++) {
			/* Substitute comparison_function with what needs to be tested. */
		res = res + comparison_function (d [i % ARR_SIZE], d[(i - 1) % ARR_SIZE]);
	}
	printf ("%d\n", res);
}

The configuration

• On Windows XP 64-bit with a Intel Q9450 @ 3 GHz with VC++ 2005 using the following command line:

/O2 /GL /FD /MT /GS-

• On Linux Ubuntu 9.04 x64 with Intel Xeon E5420 @ 2.5 GHz with gcc 4.4.1 using the following command line:

-O3 -funroll-loops -lm

• On Solaris 10 x64 with AMD Opteron 248 @ 2.2 GHz with Sun C 5.9 using the following command line:

-xO5 -m64 -lm

Equality Testing

Testing for non-NaN values which are always different

The array is filled with non-NaN values which are always different, which gives the following results:

Testing for non-NaN values which are always the same

The array is filled with non-NaN values which are always the same, which gives the following results:

Testing for 100% NaN values

The array is filled with NaN values, which gives the following results:

Testing for 50% NaN values and 50% non-NaN values

The array is filled at 50% with NaN values and the rest with different values which gives the following results:

Testing for 25% NaN values and 75% non-NaN values

The array is filled at 25% with NaN values and the rest with different values which gives the following results:

Testing for 10% NaN values and 90% non-NaN values

The array is filled at 10% with NaN values and the rest with different values which gives the following results:

Less than Testing

Testing for non-NaN values which are always different

The array is filled with non-NaN values which are always different, which gives the following results:

Testing for non-NaN values which are always the same

The array is filled with non-NaN values which are always the same, which gives the following results:

Testing for 100% NaN values

The array is filled with NaN values, which gives the following results:

Testing for 50% NaN values and 50% non-NaN values

The array is filled at 50% with NaN values and the rest with different values which gives the following results:

Testing for 25% NaN values and 75% non-NaN values

The array is filled at 25% with NaN values and the rest with different values which gives the following results:

Testing for 10% NaN values and 90% non-NaN values

The array is filled at 10% with NaN values and the rest with different values which gives the following results:

IsNaN Testing

We are testing eif_is_nan_real_64 which has 4 different implementations: NAN1, NAN2, NAN3 and NAN4. As we can see in the results below, it is always best to check for NaN using the `x != x' yielding True pattern.

Testing for non-NaN values which are always different

The array is filled with non-NaN values which are always different, which gives the following results:

Testing for non-NaN values which are always the same

The array is filled with non-NaN values which are always the same, which gives the following results:

Testing for 100% NaN values

The array is filled with NaN values, which gives the following results:

Testing for 50% NaN values and 50% non-NaN values

The array is filled at 50% with NaN values and the rest with different values which gives the following results:

Testing for 25% NaN values and 75% non-NaN values

The array is filled at 25% with NaN values and the rest with different values which gives the following results:

Testing for 10% NaN values and 90% non-NaN values

The array is filled at 10% with NaN values and the rest with different values which gives the following results: