Ieee arithmetic

Revision as of 14:22, 9 February 2010 by Manus (Talk | contribs)

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.

Information.png Note: This is an EiffelStudio specific extension to potentially help the ECMA standard committee in making a reasonable decision on the semantic of NaN.

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 5.068s 6.25s 9.32s
METH2 6.495s 6.47s 11.57s
METH3 6.448s 7.35s 12.31s
METH4 6.424s 8.80s 12.31s
METH5 6.832s 7.73s 11.46s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 5.242s 6.24s 9.32s
METH2 5.464s 5.17s 9.62s
METH3 5.308s 5.48s 9.26s
METH4 6.428s 8.80s 12.31s
METH5 5.384s 5.49s 9.32s

Testing for 100% NaN values

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

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.777s 6.24s 9.25s
METH2 5.440s 5.17s 9.92s
METH3 6.266s 7.32s 16.48s
METH4 5.560s 8.80s 12.44s
METH5 7.413s 8.34s 15.74s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 6.889s 6.24s 9.31s
METH2 6.914s 7.01s 13.36s
METH3 6.405s 7.01s 14.64s
METH4 6.068s 8.80s 12.07s
METH5 6.880s 7.83s 13.47s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 7.553s 6.24s 9.31s
METH2 6.672s 6.73s 12.25s
METH3 8.997s 7.23s 13.47s
METH4 6.250s 8.80s 12.00s
METH5 8.063s 7.76s 12.55s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 5.029s 6.24s 9.32s
METH2 6.556s 6.59s 11.74s
METH3 6.437s 7.29s 12.82s
METH4 6.327s 8.80s 12.06s
METH5 6.800s 7.73s 12.22s


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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.749s 4.42s 8.60s
METH2 6.358s 7.30s 10.85s
METH3 6.109s 6.82s 11.45s
METH4 6.112s 6.83s 10.48s
METH5 6.355s 8.56s 10.90s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.757s 4.40s 8.50s
METH2 4.736s 7.28s 10.84s
METH3 6.114s 6.80s 11.21s
METH4 6.102s 7.10s 10.48s
METH5 6.344s 8.57s 10.72s

Testing for 100% NaN values

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

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.753s 4.41s 8.60s
METH2 7.366s 8.34s 12.13s
METH3 6.284s 7.31s 15.18s
METH4 5.570s 6.82s 14.08s
METH5 6.993s 8.56s 11.03s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.745s 4.41s 8.50s
METH2 6.949s 7.82s 11.57s
METH3 6.346s 7.09s 13.10s
METH4 6.023s 7.11s 11.88s
METH5 6.838s 8.56s 10.72s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.812s 4.41s 8.50s
METH2 6.633s 7.54s 11.20s
METH3 7.324s 6.96s 12.07s
METH4 6.050s 7.10s 11.04s
METH5 6.595s 8.55s 11.03s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
METH1 4.761s 4.41s 8.50s
METH2 6.472s 7.37s 10.99s
METH3 6.159s 6.83s 11.59s
METH4 6.084s 7.10s 10.76s
METH5 6.440s 8.56s 10.71s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
NAN1 3.671s 3.81s 6.56s
NAN2 4.071s 3.98s 6.11s
NAN3 4.514s 4.12s 6.38s
NAN4 4.881s 8.28s 10.96s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
NAN1 3.665s 3.73s 6.48s
NAN2 4.071s 4.17s 6.12s
NAN3 4.517s 4.12s 6.18s
NAN4 4.886s 8.28s 10.71s

Testing for 100% NaN values

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

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
NAN1 3.362s 3.76s 6.55s
NAN2 4.071s 3.99s 6.18s
NAN3 5.176s 5.66s 8.82s
NAN4 4.880s 8.28s 10.96s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
NAN1 3.527s 3.74s 6.48s
NAN2 4.072s 3.99s 6.09s
NAN3 5.011s 4.87s 7.78s
NAN4 4.894s 8.28s 10.71s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
NAN1 3.568s 3.75s 6.48s
NAN2 4.073s 3.99s 6.09s
NAN3 4.752s 4.46s 6.74s
NAN4 4.880s 8.27s 10.83s

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:

Method used VC++ 2005 x64 gcc 4.4.1 x64 Sun cc 5.9 x64
NAN1 3.633s 3.77s 6.47s
NAN2 4.084s 3.98s 6.09s
NAN3 4.621s 4.29s 7.20s
NAN4 4.879s 8.29s 10.89s