Difference between revisions of "Ieee arithmetic"

(Testing for 10% NaN values and 90% non-NaN values)
(Made table more compact)
Line 126: Line 126:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 162: Line 162:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 198: Line 198:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 234: Line 234:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 270: Line 270:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 306: Line 306:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 344: Line 344:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 380: Line 380:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 416: Line 416:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 452: Line 452:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 488: Line 488:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 524: Line 524:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''METH1'''
 
| '''METH1'''
Line 563: Line 563:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''NAN1'''
 
| '''NAN1'''
Line 594: Line 594:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''NAN1'''
 
| '''NAN1'''
Line 625: Line 625:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''NAN1'''
 
| '''NAN1'''
Line 656: Line 656:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''NAN1'''
 
| '''NAN1'''
Line 687: Line 687:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''NAN1'''
 
| '''NAN1'''
Line 718: Line 718:
 
{| class="wikitable"
 
{| class="wikitable"
 
| '''Method used'''
 
| '''Method used'''
| '''Timing VC++ 2005 x64'''
+
| '''VC++ 2005 x64'''
| '''Timing gcc 4.4.1 x64'''
+
| '''gcc 4.4.1 x64'''
| '''Timing Sun cc 5.9 x64'''
+
| '''Sun cc 5.9 x64'''
 
|-
 
|-
 
| '''NAN1'''
 
| '''NAN1'''

Revision as of 09:51, 5 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 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.

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
METH2 6.358s
METH3 6.109s
METH4 6.112s
METH5 6.355s

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
METH2 4.736s
METH3 6.114s
METH4 6.102s
METH5 6.344s

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
METH2 7.366s
METH3 6.284s
METH4 5.570s
METH5 6.993s

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
METH2 6.949s
METH3 6.346s
METH4 6.023s
METH5 6.838s

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
METH2 6.633s
METH3 7.324s
METH4 6.050s
METH5 6.595s

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
METH2 6.472s
METH3 6.159s
METH4 6.084s
METH5 6.440s

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