Entries by Daniel Fischer

In school, we learned that x - y = 0 is true if, and only if, x = y. In computing, we learned that we can only store so many accurate digits in a fixed-size register. For example, a register that is 8 bits wide can store exactly 256 different values. If we want to represent negative and positive values, there are a number of ways to express that, but we'll still only get 256 different individual values. The way computers typically do it will give us values from -128 to +127.

Now we might want to represent real numbers like 1.5. There's no way to get more than 256 different values from 8 bits, but we could agree that there's a decimal point, and it is always before the last digit. Instead of -128 to +127, we get -12.8 to 12.7. We traded in range for accuracy. Sometimes, range is more important than accuracy. In such a case, we could pretend that the decimal point is always one digit to the right of the last digit we store, giving us a range from -1280 to 1270. Our range got boosted, but we lost accuracy: We can no longer store numbers like 1234, even though it is in the range of our type. This is adequately refered to as fixed point arithmetics.

Now, how do we get both range, and accuracy? Instead of putting the decimal point in a fixed location, we could instead store its position together with the actual number. This is called floating point arithmetics. For example, we could say that we use 2 bits for the position of the decimal point, and 6 bits for the actual number. The way computers really do it is a bit more complex and is defined in IEEE 754.

IEEE 754 contains one detail that might not be obvious. Floating point numbers are represented by a sign bit, an exponent to a fixed and previously agreed-upon base, and a mantissa. However, the mantissa isn't just a number that is shifted left or right based on the exponent. Instead, it is defined that the mantissa is a number between including 1, and excluding 2. Since this means there's always one digit before the decimal point that can only be 1, the part that is stored is only the digits after the decimal point. A number stored like this is called a normal number.

For simplicity, let's assume a similar system based on base 10. Let's say we can store the sign, exponents from -2 to +2, and we have room for a mantissa of three digits. This will let us express numbers from -1.999 * 10 ^ -2 to + 1.999 * 10 ^ 2. We can express x = 0.012 as 1.2 * 10 ^ -2 and y = 0.0105 as 1.05 * 10 ^ -2.

However, we can't represent x - y = 0.0015! Normalising it and writing it as 1.5 * 10 ^ -3 fails to satisfy the condition we agreed upon previously that we would only have exponents from -2 to +2. We'll have to live with it and just accept that the result of this computation is smaller than the smallest allowed number that we can represent, and replace it with zero. But x and y aren't equal!

This is a terrible situation for scientists, and thus, a solution was quickly found. Basically, it goes like this: We sacrifice one of our possible exponent values, and use it instead to indicate that the number we represent isn't normalised as agreed upon before, and smaller than the smallest possible normalised number. Such a number is called a denormal number.

You might wonder where the lesson is - after all, the problem seems to be solved. By introducing denormals, we fixed our condition from the first paragraph, and now it holds again for all x and y that can be represented individually.

In theory, all major platforms of today support denormals. In practice, many CPUs don't handle them in hardware, but instead trap to some software implementation. Implementing floating point operations in software can be rather slow. Programmers, however, don't like their programs running slowly and tell compilers to optimise. Compilers for CPUs that trap when denormals occur know that they're slow, and therefore, optimise by turning of denormals altogether. Instead, results of calculations that can't be normalised are flushed to zero.

For example, on Itanium CPUs, the x - y operation can be slower by orders of magnitude if the result is a denormal as compared to the same operation when the result can be expressed as a normal number. Here's some (rather simple) code to try this if you have access to an Itanium box. Compile with gcc, without optimisation, once with -DSMALL, once without, and then compare the run time. It's not a proper benchmark, but should be sufficient to show the problem.

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 int main() {
 5   double x, *y;
 6   y = &x;
 7 
 8   #ifdef SMALL
 9   double a = pow(2,-1022) + pow(2,-1023);
10   double b = pow(2,-1022);
11   #else
12   double a = pow(2,-122) + pow(2,-123);
13   double b = pow(2,-122);
14   #endif
15 
16   int i = 0;
17   for(i=0; i<10000000; ++i) {
18     *y = a - b;
19   }
20 
21   return 0;
22 }

However, the vendor compiler for Itanium, Intel's icc, knows about this. When you use -O3 with icc on ia64, it enables flush to zero mode, which results in all denormal results to be flushed to zero. Use the same compiler on x86_64 and it won't, because x86_64 can handle denormals faster. It's still measurable, but not as much of a problem.

I saw this problem in a test case that expected a denormal number as a result, and therefore failed (only) on ia64 with optimisation. It's still possible to get icc to optimise without enabling flush to zero mode, by specifically disabling it with the -no-ftz flag.

It should be an offense to rely on the size of a given type in C to be the same across different platforms. Still, certain assumptions appear to be fairly common. One of them is the value of sizeof(long). I think we've gotten over the idea that long and int are the same size now that 64 bit platforms are becoming more and more common. However, occassionally I still encounter a similar misconception: That the sizes of long and any pointer type are the same.

 1 #include <stdio.h>
 2 #define S(X) printf(#X " %d\n", sizeof(X))
 3 
 4 int main() {
 5   S(int *);
 6   S(long);
 7   return 0;
 8 }

This snippet will tell you that both a long and a pointer to int are of size 4 on most 32 bit platforms, and that both are of size 8 on most 64 bit platforms. There is one notable platform where this isn't the case. When compiled with Visual Studio's cl.exe on 64 bit Windows, the size of the pointer will be 8, but the size of the long will be 4.

According to the C standard, this is perfectly legal. In reality, I've seen variables of type long used to store pointers, or anything else that fits into a long on one of the other platforms. Please stop doing that, it's wrong, and it will break on Windows.

Let's say you're writing a function that accepts a pointer to an int.

 1 void do_stuff_with_int(int *p) {
 2   /* ... */
 3 }

Later, you notice that the doing stuff operation doesn't depend on signedness at all, and decide that you want to use your function with unsigned int too. Just passing a pointer to an unsigned int will cause a warning. How would you get rid of it in a clean way? Easy, use a union.

 1 typedef union {
 2   int *si;
 3   unsigned int *ui;
 4 } signed_or_unsigned_int_pointer;

Now you have a type that can both contain a pointer to an int, or a pointer to an unsigned int. Wouldn't it be convenient if you could use your shiny new type to indicate that do_stuff_with_int() really can accept both types? That's where gcc's transparent_union attribute comes in. (Some other compilers also support this.)

 1 typedef union {
 2   int *si;
 3   unsigned int *ui;
 4 } signed_or_unsigned_int_pointer
 5 __attribute__((transparent_union));
 6 
 7 void do_stuff_with_int(signed_or_unsigned_int_pointer p) {
 8   /* ... */
 9 }
10 
11 int main() {
12   int a = 0;
13   unsigned int b = 0;
14 
15   do_stuff_with_int(&a);
16   do_stuff_with_int(&b);
17 
18   return 0;
19 }

Now, what's the catch? You can only use transparent_union with unions that contain only types with the same representation. In other words, they need to be the same size. You can't, for example, use it with a 32-bit int and a 64-bit integer, in which case gcc will generate a warning. And lots of errors later on, because you're not passing unions to your function, but any one of their constituent types, which isn't allowed without transparent_union.

And now, the reason why this post is related to portability:

 1 typedef union {
 2   int an_int;
 3   long a_long;
 4 } int_union
 5 __attribute__((transparent_union));

The transparent_union attribute will be ignored on most 64 bit platforms.

Treating int and long as the same type is a beginner's mistake. But what about this code?

 1 typedef union {
 2   int volatile *i;
 3   unsigned int volatile *u;
 4 } int_union
 5 __attribute__((transparent_union));

Should work, shouldn't it?

Turns out it doesn't. That is, it works in most places. It even works on Mac OS X. Unless you build for the 64-bit PowerPC CPU. In that case, the attribute is ignored, even though the two types are still the same size. This only seems to happen on ppc64. On all three other architectures currently supported by Mac OS X, it works.

 1 $ gcc -c t.c -arch ppc
 2 $ gcc -c t.c -arch ppc64
 3 t.c:6: warning: 'transparent_union' attribute ignored
 4 $ gcc -c t.c -arch i386 
 5 $ gcc -c t.c -arch x86_64