1

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.

  • 0.219s vs 0.263 is not a huge difference given other factors such as dj bazzie wazzie points out. Write a test program that first loads the array into memory then time just the sort routine. Use an array large enough that the longest case takes minutes or at least several seconds (but not large enough that the OS swaps pages) then draw conclusions from there. – deStrangis May 7 '14 at 12:58
  • Floats are designed so you can compare them as if there were int. (most significant bits on the left). – bokan Jan 23 '15 at 17:15
2

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.

  • Thanks a lot for your answer I will try AlmostEqual2sComplement method too! – Nullpointer May 6 '14 at 14:29
  • I don't see the OP's time differences as dramatic and can be explained mainly by points 1-4 above rather than in the CPU's ability to handle integers better than floating point numbers which, although existing, would be minimal compared to other factors. – deStrangis May 7 '14 at 12:30
  • A sorting routine can be made very efficient for floating point as long as you don't compare for equality and just use >, >= operators... OTOH if you use a stock sort() library routine and must provide a function that returns -1, 0 or 1 if the numbers are less than, equal or greater than, then you may be forced to compare for equality and are screwed. – deStrangis May 7 '14 at 12:34
  • A comparison between 2.25 + 2.75 and 2.5 + 2.5 will most certainly return that they are equal, unless your compiler is terribly broken. – gnasher729 Jul 1 '16 at 14:39
1

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.

  • @Nullpointer You should generally have in mind that anything that has to do with floating point arithmetic isn't inexpensive. Modern CPUs handle this successfully. Other architectures, such that of GPUs are immature to floating point operations, especially doubles. In most cases when you want performance instead of precision, you'll definitely use floats instead of doubles. – gon1332 May 6 '14 at 14:37
  • @gon1332, I'm not sure if floats actually perform better than doubles. Many FP CPUs operate on numbers internally in high precision then convert to lower precision for transfer. When I learned x86 FP assembly the book mentioned that "besides memory space, the only upside to using single precision performancewise is the educational value of learning that more precision is better" (quote from memory) – deStrangis May 7 '14 at 12:44
  • @deStrangis Yes, in x86 doubles may perform batter that floats. But in other systems, such GPUs, there will be a problem. Finally, for the OP, the time differences aren't dramatic. So, the only restriction as you already mentioned is the space, which will be doubled. – gon1332 May 7 '14 at 13:20
1

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.