5 ms·

> 40x faster trigonometry: Speed-up standard library functions like std::sin in just 3 lines of code. Huh, ok, let's see how... * By limiting the expansi

> 40x faster trigonometry: Speed-up standard library functions like std::sin in just 3 lines of code. Huh, ok, let's see how... * By limiting the expansion to a few * terms, we can approximate `sin(x)` as: * * sin(x) ≈ x - (x^3)/3! + (x^5)/5! * * This reduces the computational cost but comes with reduced accuracy. I see. "reduced accuracy" is an understatement. It's just horrifically wrong for inputs outside the range of [-2, 2] https://www.wolframalpha.com/input?i=plot+sin+x%2C+x+-+%28x%5E3%29%2F6+%2B+%28x%5E5%29+%2F+120 https://www.wolframalpha.com/input?i=plot+sin+x%2C+x+-+%28x%... It cannot handle a single interval of a sin wave, much less the repeating nature? What an absolutely useless "optimization"

readams 2y ago
My small angle sin function is even faster: sin(x) = x
Analemma_ 2y ago
This is kind of a dumb objection. If your sine function has good accuracy in [-pi/2, pi/2], you can compute all other values by shifting the argument and/or multiplying the result by -1.
- SkiFire13 2y ago
  But then you have to include this in the benchmark and it will no longer be 40x faster.
  - dzaima 2y ago
    There are a bunch of real situations where you can assume the input will be in a small range. And while reducing from [-pi;pi] or [-2*pi;2*pi] or whatever is gonna slow it down somewhat, I'm pretty sure it wouldn't be too significant, compared to the FP arith. (and branching on inputs outside of even that expanded target expected range is a fine strategy realistically)
    - kllrnohj 2y ago
      > branching on inputs outside of the target expected range is a fine strategy realistically branches at this scale are actually significant, and so will drastically impact being able to achieve 40x faster as claimed
      - dzaima 2y ago
        That's only if they're unpredictable; sure, perhaps on some workload it'll be unpredictable whether the input to sin/cos is grater than 2*pi, but I'm pretty sure on most it'll be nearly-always a "no". Perhaps not an optimization to take in general, but if you've got a workload where you're fine with 0.5% error, you can also spend a couple seconds thinking about what range of inputs to handle in the fast path. (hence "target expected range" - unexpected inputs getting unexpected branches isn't gonna slow down things if you've calibrated your expectations correctly; edited my comment slightly to make it clearer that that's about being out of the expanded range, not just [-pi/2,pi/2])
        kllrnohj 2y ago
        Assuming an even distribution over a single iteration of sin, that is [0,pi], this will have a ~30% misprediction rate. That's not rare.
        dzaima 2y ago
        I'm of course not suggesting branching in cases where you expect a 30% misprediction rate. You'd do branchless reduction from [-2*pi;2*pi] or whatever you expect to be frequent, and branch on inputs with magnitude greater than 2*pi if you want to be extra sure you don't get wrong results if usage changes. Again, we're in a situation where we know we can tolerate a 0.5% error, we can spare a bit of time to think about what range needs to be handled fast or supported at all.
        kllrnohj 2y ago
        Those reductions need to be part of the function being benchmarked, though. Assuming a range limitation of [-pi,pi] even would be reasonable, there's certainly cases where you don't need multiple revolutions around a circle. But this can't even do that, so it's simply not a substitute for sin, and claiming 40x faster is a sham
- dzaima 2y ago
  At pi/2 that approximation gets you 1.0045, i.e. half a percent off, so it's not particularly good at that. (still could be sufficient for some uses though; but not the best achievable even with that performance)
- TimorousBestie 2y ago
  Good argument reduction routines are not exactly easy for a novice to write, so I think this is a valid objection.
- kubav027 2y ago
  At least do not name the function "sin". One former game dev works in my company and he is using similar tricks all the time. It makes code so hard to read and unless you are computing "sin" a lot speedup is not measurable.
  - deleted 2y ago
    [deleted]
ashvardanian 2y ago
You can always get more accuracy by expanding those 3 lines to handle more of the Taylor components… but it’s important to remember that this is still educational material. You can find more complete examples in my SimSIMD (https://github.com/ashvardanian/SimSIMD https://github.com/ashvardanian/SimSIMD), but they also often assume that at a certain part of a kernel, a floating point number is guaranteed to be in a certain range. This can greatly simplify the implementation for kernels like Atan2. For general-purpose inputs, go to SLEEF (https://sleef.org https://sleef.org). Just remember that every large, complicated optimization starts with a small example.
- kllrnohj 2y ago
  > but it’s important to remember that this is still educational material. Then it should be educating on the applicability and limitations of things like this instead of just saying "reduced accuracy" and hoping the reader notices the massive issues? Kinda like the ffast-math section does.
- pclmulqdq 2y ago
  No. Do not use Taylor series approximations in your real code. They are slow and inaccurate. You can do much, much better with some basic numerical analysis. Chebyshev and Remez approximations will give you more bang for your buck every time.
- jcranmer 2y ago
  Educational material that misinforms its readers isn't educational, and it's insanely counterproductive. People have already ragged on you for doing Taylor approximation, and I'm not the best expert on the numerical analysis of implementing transcendental functions, so I won't pursue that further. But there's still several other unaddressed errors in your trigonometric code: * If your function is going to omit range reduction, say so upfront. Saying "use me to get a 40× speedup because I omit part of the specification" is misleading to users, especially because you should assume that most users are not knowledgeable about floating-point and thus they aren't even going to understand they're missing something without you explicitly telling them! * You're doing polynomial evaluation via `x * a + (x * x) * b + (x * x * x) * c` which is not the common way of doing so, and also, it's a slow way of doing so. If you're trying to be educational, do it via the `((((x * c) * x + b) * x) + a) * x` technique--that's how it's done, that's how it should be done. * Also, doing `x / 6.0` is a disaster for performance, because fdiv is one of the slowest operations you can do. Why not do `x * (1.0 / 6.0)` instead? * Doing really, really dumb floating-point code and then relying on -ffast-math to make the compiler unpick your dumbness is... a bad way of doing stuff. Especially since you're recommending people go for it for the easy speedup and saying absolutely nothing about where it can go catastrophically wrong. As Simon Byrne said, "Friends don't let friends use -ffast-math" (and the title of my explainer on floating-point will invariably be "Floating Point, or How I Learned to Start Worrying and Hate -ffast-math").
pclmulqdq 2y ago
Oof this is bad. If you're going to ask people to approximate, use a Chebyshev approximation please. You will do sin(x) faster than this and more accurately.
meindnoch 2y ago
And it's not even using the Horner scheme for evaluating the polynomial.
boricj 2y ago
It's not useless if it's good enough for the problem at hand. Kaze Emanuar has two entire videos dedicated to optimizing sin() on the Nintendo 64 and he's using approximations like this without issues in his homebrew: - https://www.youtube.com/watch?v=xFKFoGiGlXQ - https://www.youtube.com/watch?v=hffgNRfL1XY
- pclmulqdq 2y ago
  I came to these videos expecting someone else pushing Taylor series, but this video series was surprisingly good in terms of talking about hacking their way through some numerical analysis. These videos started with Taylor series, but did not end there. They came up with some hacky but much better polynomial approximations, which are respectable. Production math libraries also use polynomial approximations. They just don't use Taylor series approximations.

readams 2y ago

My small angle sin function is even faster: sin(x) = x

Analemma_ 2y ago

This is kind of a dumb objection. If your sine function has good accuracy in [-pi/2, pi/2], you can compute all other values by shifting the argument and/or multiplying the result by -1.

SkiFire13 2y ago
But then you have to include this in the benchmark and it will no longer be 40x faster.
- dzaima 2y ago
  There are a bunch of real situations where you can assume the input will be in a small range. And while reducing from [-pi;pi] or [-2*pi;2*pi] or whatever is gonna slow it down somewhat, I'm pretty sure it wouldn't be too significant, compared to the FP arith. (and branching on inputs outside of even that expanded target expected range is a fine strategy realistically)
  - kllrnohj 2y ago
    > branching on inputs outside of the target expected range is a fine strategy realistically branches at this scale are actually significant, and so will drastically impact being able to achieve 40x faster as claimed
    - dzaima 2y ago
      That's only if they're unpredictable; sure, perhaps on some workload it'll be unpredictable whether the input to sin/cos is grater than 2*pi, but I'm pretty sure on most it'll be nearly-always a "no". Perhaps not an optimization to take in general, but if you've got a workload where you're fine with 0.5% error, you can also spend a couple seconds thinking about what range of inputs to handle in the fast path. (hence "target expected range" - unexpected inputs getting unexpected branches isn't gonna slow down things if you've calibrated your expectations correctly; edited my comment slightly to make it clearer that that's about being out of the expanded range, not just [-pi/2,pi/2])
      - kllrnohj 2y ago
        Assuming an even distribution over a single iteration of sin, that is [0,pi], this will have a ~30% misprediction rate. That's not rare.
        dzaima 2y ago
        I'm of course not suggesting branching in cases where you expect a 30% misprediction rate. You'd do branchless reduction from [-2*pi;2*pi] or whatever you expect to be frequent, and branch on inputs with magnitude greater than 2*pi if you want to be extra sure you don't get wrong results if usage changes. Again, we're in a situation where we know we can tolerate a 0.5% error, we can spare a bit of time to think about what range needs to be handled fast or supported at all.
        kllrnohj 2y ago
        Those reductions need to be part of the function being benchmarked, though. Assuming a range limitation of [-pi,pi] even would be reasonable, there's certainly cases where you don't need multiple revolutions around a circle. But this can't even do that, so it's simply not a substitute for sin, and claiming 40x faster is a sham
dzaima 2y ago
At pi/2 that approximation gets you 1.0045, i.e. half a percent off, so it's not particularly good at that. (still could be sufficient for some uses though; but not the best achievable even with that performance)
TimorousBestie 2y ago
Good argument reduction routines are not exactly easy for a novice to write, so I think this is a valid objection.
kubav027 2y ago
At least do not name the function "sin". One former game dev works in my company and he is using similar tricks all the time. It makes code so hard to read and unless you are computing "sin" a lot speedup is not measurable.
- deleted 2y ago
  [deleted]

ashvardanian 2y ago

You can always get more accuracy by expanding those 3 lines to handle more of the Taylor components… but it’s important to remember that this is still educational material. You can find more complete examples in my SimSIMD (https://github.com/ashvardanian/SimSIMD https://github.com/ashvardanian/SimSIMD), but they also often assume that at a certain part of a kernel, a floating point number is guaranteed to be in a certain range. This can greatly simplify the implementation for kernels like Atan2. For general-purpose inputs, go to SLEEF (https://sleef.org https://sleef.org). Just remember that every large, complicated optimization starts with a small example.

kllrnohj 2y ago
> but it’s important to remember that this is still educational material. Then it should be educating on the applicability and limitations of things like this instead of just saying "reduced accuracy" and hoping the reader notices the massive issues? Kinda like the ffast-math section does.
pclmulqdq 2y ago
No. Do not use Taylor series approximations in your real code. They are slow and inaccurate. You can do much, much better with some basic numerical analysis. Chebyshev and Remez approximations will give you more bang for your buck every time.
jcranmer 2y ago
Educational material that misinforms its readers isn't educational, and it's insanely counterproductive. People have already ragged on you for doing Taylor approximation, and I'm not the best expert on the numerical analysis of implementing transcendental functions, so I won't pursue that further. But there's still several other unaddressed errors in your trigonometric code: * If your function is going to omit range reduction, say so upfront. Saying "use me to get a 40× speedup because I omit part of the specification" is misleading to users, especially because you should assume that most users are not knowledgeable about floating-point and thus they aren't even going to understand they're missing something without you explicitly telling them! * You're doing polynomial evaluation via `x * a + (x * x) * b + (x * x * x) * c` which is not the common way of doing so, and also, it's a slow way of doing so. If you're trying to be educational, do it via the `((((x * c) * x + b) * x) + a) * x` technique--that's how it's done, that's how it should be done. * Also, doing `x / 6.0` is a disaster for performance, because fdiv is one of the slowest operations you can do. Why not do `x * (1.0 / 6.0)` instead? * Doing really, really dumb floating-point code and then relying on -ffast-math to make the compiler unpick your dumbness is... a bad way of doing stuff. Especially since you're recommending people go for it for the easy speedup and saying absolutely nothing about where it can go catastrophically wrong. As Simon Byrne said, "Friends don't let friends use -ffast-math" (and the title of my explainer on floating-point will invariably be "Floating Point, or How I Learned to Start Worrying and Hate -ffast-math").

pclmulqdq 2y ago

Oof this is bad. If you're going to ask people to approximate, use a Chebyshev approximation please. You will do sin(x) faster than this and more accurately.

meindnoch 2y ago

And it's not even using the Horner scheme for evaluating the polynomial.

boricj 2y ago

It's not useless if it's good enough for the problem at hand. Kaze Emanuar has two entire videos dedicated to optimizing sin() on the Nintendo 64 and he's using approximations like this without issues in his homebrew: - https://www.youtube.com/watch?v=xFKFoGiGlXQ - https://www.youtube.com/watch?v=hffgNRfL1XY

pclmulqdq 2y ago
I came to these videos expecting someone else pushing Taylor series, but this video series was surprisingly good in terms of talking about hacking their way through some numerical analysis. These videos started with Taylor series, but did not end there. They came up with some hacky but much better polynomial approximations, which are respectable. Production math libraries also use polynomial approximations. They just don't use Taylor series approximations.