comparison of floating point numbers vs. comparsion of Integers in C [closed]

Question

Does comparison of floating point numbers takes (considerably) longer time than comparison of Integers in C?

I just wrote a C program of heap sort to sort floating point numbers.

I am on ubuntu 14.04 and I used time command to check the time taken by this program for sorting 50, 5000 and 50000 random numbers and then I just changed all double to int and again checked time for 50, 5000 and 5000 numbers and statistics are as follows:

$ time ./heap 50 < input.txt 

real    0m0.003s
user    0m0.001s
sys 0m0.002s
$ time ./temp 50 < input.txt 

real    0m0.003s
user    0m0.001s
sys 0m0.002s
$ time ./heap 5000 < input.txt 

real    0m0.008s
user    0m0.007s
sys 0m0.002s
$ time ./temp 5000 < input.txt 

real    0m0.005s
user    0m0.004s
sys 0m0.001s
$ time ./heap 50000 < input.txt 

real    0m0.030s
user    0m0.028s
sys 0m0.002s
$ time ./temp 50000 < input.txt 

real    0m0.027s
user    0m0.026s
sys 0m0.002s
$ time ./heap 500000 < input.txt 

real    0m0.263s
user    0m0.259s
sys 0m0.003s
$ time ./temp 500000 < input.txt 

real    0m0.219s
user    0m0.216s
sys 0m0.003s

Here heap is the executable of floating point heapsort and temp is the executable of Integer number heapsort.

As we can see there is noticeable difference in running times? What is the reason? I can upload the codes if needed.

Answer 1

Timing your code like this doesn't say much.

1. There is overhead of bash's text interpreter
2. There is overhead of the kernel's program loader
3. There is overhead of the process itself (initialization and dylib linking)
4. The data read from the file is included in the timing (atoi and/or atof)
5. Did you use a AlmostEqual2sComplement method or just the == operator?

More about AlmostEqual2sComplement

Even if you would use a more precise timing, which should be included in the program. I would say that the difference is even larger. When we use two floating points, f1 = 2.25 + 2.75 and f2 = 2.5 + 2.5. Now a comparison like fp1 == fp2 will probably return false. Here an article on how to compare floating points. That means that you can't use a fp1 == fp2 in your benchmark and the AlmostEqual2sComplement() function you're looking for needs so many more instructions for a better comparison that the actual comparison between floating points is much more slower than comparing two integers.

Even if you want to keep using fp1 == fp2 the best answer to your question would be that it totally depends on the processor and compiler. Just a data comparison you need to make sure that both data items are equally in bit length. So when a float is 64-bit you'll need a 64-bit integer too. Then the == comparison could be equally fast in theory but again it depends on compiler and processor.

Answer 2

At the CPU level, integer and floating point operations are separate instructions.

An integer is a simple bit pattern where each bit represents a power of two or a sign bit. There are many microcode optimizations in modern CPUs (even on mobile devices) that make integer arithmetic and comparisons super fast.

Floating point operations and comparisons are more complex. The vast majority of modern CPUs that can handle floating point use the IEEE-754 standard. A floating point number (or double, or long double, the idea is the same) is more complex: it has both a mantissa and an exponent in addition to the sign bit. It also has special bit patterns that represent NaN (not a number), positive and negative infinity, as well as positive and negative zero.

What this means in practice is that even if a floating point compare or add or whatever other operation is a single CPU instruction, that instruction has a lot of work to do and will take several times longer than an integer operation. What is the result of "NaN < 4.5" or "7.0 < 7.0"? What about "1e-30 < 1e30"? The CPU has to be able to deal with the special "numbers" such as NaN and treat them correctly according to the spec. It also has to be able to deal with overflow or underflow situations where two numbers cannot realistically be used together due to limitations in the size of the exponent.

The circuits in the CPU have to be able to handle all of this which adds complexity, adds time to floating point processing, and means the program you wrote to sort floats will take longer.

---

Another thing that might be worth looking into (but is not strictly part of this answer) is to offload the floating point program to a GPU. Graphics processors rival CPUs here in 2014 for complexity and circuit size. They are highly parallel and highly optimized for floating point operations, since 3D graphics rely so heavily on floating point math.

Writing a program to sort floats using the GPU might be an interesting diversion and a good learning experience.

Answer 3

Generally, we would expect that FP operations are more expensive. Not to talk about doubles. That is because floats demand high-complexity operations. They also demand special caring in mathematic functions. They are an approximation of the number you want. So these functions do what they can do to achieve small errors.

Floating point arithmetic is implemented by the FPU. On CPUs that are in personal computers, FPU is advanced comparing to CPUs of embedded systems and other mobile devices (smartphones etc). And that is because floating point arithmetic isn't as power efficient as integer arithmetic.

So the conclusion here, considering that you work on a personal computer and from seeing your time deltas, the results are logical. If you'd run this program on a smartphone you would see a bigger delta in times.