4
$\begingroup$

In many resources/videos I see comments being made along the lines of "and we can see here that we have a logarithm/exponential so this will be an expensive computation to make." (such as with the sigmoid activation function for a NN). What is behind these statements?

A more specific example would be: what makes $e^{-x}$ so much different than something like $x^4$ or $4^x$ in a computer calculation?

$\endgroup$
5
  • $\begingroup$ Do it on paper yourself - with a pencil and no calculator. How long would it take you to do 123+456? Or 123x456? Long division - 123/456? How about a Log(123)? Or e^3, even? Computers need to perform the same number of steps humans do, more or less, to solve a given problem. $\endgroup$
    – J...
    May 3 at 14:46
  • $\begingroup$ @J. A rather dangerous simplification. By that logic dividing two doubles with 15 places should take much longer than dividing two shorter doubles. Computers use very different algorithms for virtually any arithmetic than what you'd do in your head (if you do mental arithmetic using a carry-lookahead adder kind of approach, hats off) and the intuition for how long something takes really doesn't work. $\endgroup$
    – Voo
    May 3 at 15:09
  • 3
    $\begingroup$ @Voo The comparison here is between operations, so let's not extrapolate wildly. Obviously it's a rough approximation, but I think by the time someone develops a cursory understanding of the required steps for the given algorithms then it becomes highly unsurprising that computing a logarithm requires much more work than a simple addition or multiplication. The argument about precision is specious because the computer always computes the same precision regardless of the ostensible "size" of the operands. I said "on paper" to enforce the notion that we're not using fast mental tricks. $\endgroup$
    – J...
    May 3 at 15:22
  • $\begingroup$ @J But the point is that computers don't do the same "on paper" algorithms humans use. So yes arguing that "computers work totally different than humans that's why size doesn't matter" is exactly my point. Or to take another example: Multiplication and division are on paper pretty similar, but a modern CPU can take up to 30 times longer to do integer division than multiplication. Then there are tricks computers can do that vastly improve performance of otherwise expensive operations (hi lookup tables in hardware for computing sine) and so on. $\endgroup$
    – Voo
    May 3 at 21:20
  • $\begingroup$ @Voo No, they don't, but it's a reasonably close first approximation that is useful for an order of magnitude estimate that is readily accessible to the intuitions of a trained mathematician. I'm not debating that the exact algorithms are different - multiplication can be easily paralleled on the die, division not. A 64-bit divide can be 4-7x slower than a 32-bit divide (on an x64 chip) where multiplication is the same speed for both, for example - sure, I get it. Getting 19-decimal places of a logarithm is still a beast of a problem, no matter how you slice it. $\endgroup$
    – J...
    May 3 at 23:10
19
$\begingroup$

To add to Lutz Lehmann's answer, you can look up the latency for the CPU instructions in this comprehensive table by Agner Fog. For example, on the Intel Ivy Bridge processors:

  • FADD / FSUB (floating point add and subtract) both take 3 cycles
  • FMUL (multiply) takes 5 cycles
  • FDIV (divide) takes 10-24 cycles
  • FYL2X ($y \cdot \log_2(x)$) takes 90-106 cycles
  • F2XM1 ($2^x - 1$) takes about 68 cycles

To calculate the exponential with a base other than 2, you have to use a combination of the FYL2X and F2XM1 instructions. In addition to the reasons that Lutz stated, the IEEE-754 standard has pretty stringent requirements for how accurately transcendental functions have to be evaluated -- correct to the last bit and correct rounding. For many applications, this level of accuracy is completely unnecessary, and people will use approximations in software that take far fewer cycles than the built-in hardware instructions take. For example, this blog post shows how to quickly calculate an approximation to the exponential function if you're willing to trade off some accuracy. I gather than in ML it's also quite common to use lower precision floating point numbers -- just 32, 16, or even 8 bits -- instead of the full 64.

$\endgroup$
10
  • $\begingroup$ One could also add the other direction of IEEE-754 compliance, many math libraries have software implementations for these functions as (some of) the FPU versions are deemed too unreliable. So one could also get a speed-up with potentially less accuracy by using direct calls to the FPU. $\endgroup$ May 2 at 7:12
  • 8
    $\begingroup$ Agner's instruction tables definitely give you the right order-of-magnitude intuition. However, these x87 instructions won't be used directly on modern architectures. In fact, I would be curious to know if you've ever seen a compiler emit an x87 instruction like FYL2X or F2XM1. I haven't. About the only time you're going to get this is if you have hand-written, carefully optimized assembly. Compilers use SSE and later instruction sets, not the legacy x87, in most cases. And complex math operations like this are going to result in calls to library functions anyway, not inline code. $\endgroup$
    – Cody Gray
    May 2 at 10:23
  • 1
    $\begingroup$ @CodyGray Yes I sort of assumed that the timings would be taken as a heuristic and not exactly but I didn't say so. The Compiler Explorer nicely illustrates your point. $\endgroup$ May 2 at 17:53
  • 1
    $\begingroup$ Re "the IEEE-754 standard has pretty stringent requirements for how accurately transcendental functions have to be evaluated -- correct to the last bit and correct rounding." IEEE-754 recommends a set of correctly-rounded math functions but does not require them. $\endgroup$
    – njuffa
    May 2 at 19:58
  • 1
    $\begingroup$ @MSalters "For some of the functions defined in IEEE754, I believe that there aren't even known, proven algorithms of bit-exact results over their whole range." That's nonsense. There might not be acceptably fast proven bit-exact algorithms, but there certainly are algorithms that give you bit-exact results for all of them. $\endgroup$
    – orlp
    May 3 at 10:11
11
$\begingroup$

$\exp$, $\sin$, $\tan$ and their inverse and otherwise related functions are transcendental, defined by an infinite power series. Meaning it takes some effort to evaluate uniformly good approximations. This is done via argument simplification using the properties of these functions, and polynomial approximations, or using quotients of polynomials à la Padé approximation (but again shifted toward some kind of uniform convergence).

So indeed a sigmoid $\frac1{1+e^{-x}}$ should take some more cycles than for instance $\frac{0.5+\max(0,x)}{1+|x|}$.

Power functions are evaluated via $x^y=\exp(y\log(x))$ or some wrapper that removes parts that are simpler to compute, thus especially for non-integer $y$ more expensive than the exponential function.

$\endgroup$
10
  • $\begingroup$ Depending on the hardware platform, the performance difference can be fairly small. I compared 1.0f / (1.0f + expf (-a)); and (0.5f + fmaxf (0.0f, a)) / (1.0f + fabsf (a)); using CUDA 11.1 on a Quadro P2000. Compiled with nvcc -o sigmoid_test.exe -arch=sm_61 -use_fast_math sigmoid_test.cu. The throughput of the former is $136 \cdot 10^{9}$ function calls per second, the throughput of the latter is $183 \cdot 10^{9}$ function calls per second. $\endgroup$
    – njuffa
    May 2 at 20:25
  • $\begingroup$ $\tan$ can not be defined by a power series at all, because of the discontinuities. And arguably $\exp$ and $\sin$ aren't, at least conceptually, defined by power series either, but by differential equations. (Which is why directly computing $e^x$ for random given $x$ is expensive, but then approximating it also for nearby $x'$ actually becomes much easier. Unfortunately, computers hardly make use of this fact.) $\endgroup$ May 3 at 9:34
  • $\begingroup$ @njuffa this is probably a result of pipelining of some sorts. The exponential version is still much more expensive, but most of that computation is done while something else happens (memory fetches, probably), therefore you don't see it. In the max / abs version, you still have the same memory issues, during which the actual processors just sit idle. I think if you tried an expression with more work on a single input field, you'd see more drastic differences. $\endgroup$ May 3 at 9:38
  • 1
    $\begingroup$ @leftaroundabout The main reason is that GPUs have dedicated hardware to compute exp2 and 1/x. This dedicated hardware is fast but not quite as fast as a regular FMA. Both implementations compile to five instructions for the sm_61 architecture used by the Quadro P2000, but the sigmoid is slower because it requires the special hardware twice (MUFU.EX2 and MUFU.RCP), while the alternative needs it only once (MUFU.RCP). $\endgroup$
    – njuffa
    May 3 at 9:57
  • 1
    $\begingroup$ @LutzLehmann The problem with rational approximations is not just the cost of division, but also increased error (rounding error from evaluation two polynomials and from the division). There are library source bases that carry forward design styles from the 1990s, while the field has progressed in the past 25 years. The last time I used a rational approximation for $2^{x}-1$ (F2XM1 instruction) was in the AMD Athlon processor ca. 1997. $\endgroup$
    – njuffa
    May 3 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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