9
$\begingroup$

First of all, hope I've found the right forum for this question, if I haven't please pass me on to one which would fit better.

Out of curiosity from an argument with someone who may or may not be more into CPUs than I am. We were arguing about the performance of floating point operations on modern CPUs. Is there any source showing hard-ware performances regarding typical functions such as exp, sin, cos on modern processors?

And in particular : can brute force computation compete with tabulation for these functions?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ what exactly do you mean by brute force computation? $\endgroup$
    – GoHokies
    Commented Dec 16, 2015 at 16:10
  • $\begingroup$ That is a good question. I guess I mean without storing and retreiving data from some pre-computed table of values. $\endgroup$
    – mathreadler
    Commented Dec 16, 2015 at 16:20
  • 3
    $\begingroup$ I think that FPU hardware uses some small tables internally for speeding up some functions (e.g. SIN/COS computed by interpolating a pre-computed table). $\endgroup$
    – BrunoLevy
    Commented Dec 16, 2015 at 17:55
  • 1
    $\begingroup$ There is a source, however, the built-in sin/cos/etc are rarely used. $\endgroup$
    – user555045
    Commented Dec 16, 2015 at 18:33

1 Answer 1

Reset to default
14
$\begingroup$

In the 1980's era Intel 80x86 architecture, there was a scalar floating point unit that had instructions like FSIN, FCOS, etc. for computing functions like sin and cos. These functions were implemented in microcode and might take 100's of CPU cycles to execute.

Later, Intel added Streaming SIMD Extensions (SSE) which gave the processor parallel floating point units that could be used to perform floating point operations on multiple operands in parallel. The SSE instruction set includes basic arithmetic operations (+,-,*,/,sqrt), but the SSE instruction set does not include instructions for functions like sin and cos. SSE has gone through several versions over the decades with additional instructions and more floating point registers.

Although the older instructions are still in the architecture, the SSE floating point units are extremely fast. In practice the SSE instructions are now used almost exclusively for floating point arithmetic with heavily optimized library routines used to compute functions like sin and cos. These routines will typically compute the function values by evaluating polynomial or rational function approximations of the functions. Sometimes a small table is used to select which polynomial is used for different ranges of input values.

Since floating point computation are extremely fast compared to memory accesses, and because a very large table would be required to hold all of the possible values for these functions, straight forward table lookup could not reasonably compete with this approach.

See this stackexchange question for more information and links to some specific implementations:

https://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math-functions

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ As you say, x87 80bit floating point is still there in hardware. fmul actually is as fast as mullss (SSE Scalar Single-precision). Actually using x87 is slower because it uses a stack model for its registers, so extra instructions to manipulate the stack are needed. And of course, SSE mulps (Packed Single-precision) does four FP multiplies in the same time that mulss does one. (Or eight with AVX). agner.org/optimize for x86 instruction latency/throughput /execution port tables, and very nice writeups of CPU internals which @mathreadler might find interesting. $\endgroup$
    – Peter Cordes
    Commented Dec 16, 2015 at 19:00
  • 3
    $\begingroup$ @PeterCordes I'll chip in that the transcendental instructions are no longer used for other reasons besides speed. The x87's internal π is only 66 bits when it should have been 128+ bits; This means that fsin applied to long double values near π gives less than 4 bits of precision due to catastrophic cancellation in range reduction. Thus, the instructions are unusable in an IEEE-754-compliant context. Therefore, range reduction must be done in SSE, and might as well do the rest there too. $\endgroup$
    – Iwillnotexist Idonotexist
    Commented Dec 16, 2015 at 19:36
  • $\begingroup$ Wow. Oh the energy spent on it all. It truly is fascinating. All that effort. Such complex machines. It's both beautiful and fascinating to study. Wonderful answer. Thank you. $\endgroup$
    – mathreadler
    Commented Dec 16, 2015 at 21:33
  • 1
    $\begingroup$ @gnasher729 I don't understand. The precision of sin(), cos(), tan() is actually important in many applications; IEEE-754 recommends that they be accurate to 1 unit-in-the-last-place; and there is a body of algorithms for accurate modulo reduction. Mark Glisse, a contributor to SO, GCC, glibc and libm, came to this same conclusion years ago. $\endgroup$
    – Iwillnotexist Idonotexist
    Commented Dec 17, 2015 at 0:39
  • 1
    $\begingroup$ @gnasher729: Close to $2\pi$, computing the sine is actually quite easy because you only need a few Taylor expansion terms. 66 bits is also plenty good enough because double precision has only 53 bits of accuracy anyway. Your argument about long double doesn't apply because there is no such thing as long double any more on the SSE side -- if your compiler offers this, then it's all software emulated. $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 18, 2015 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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