4 ms·

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 education

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").
- Certhas 2y ago
  I don't know who the target audience is supposed to be, but who would be the type of person who tries to implement performance critical numerical codes but doesn't know the implications of Taylor expanding the sine function?
  - Const-me 2y ago
    > tries to implement performance critical numerical codes but doesn't know the implications of Taylor expanding the sine function? That would be me, I’m afraid. I know little about Taylor series, but I’m pretty sure it’s less than ideal for the use case. Here’s a better way to implement faster trigonometry functions in C++ https://github.com/Const-me/AvxMath/blob/master/AvxMath/AvxMathTrig.cpp#L64-L128 https://github.com/Const-me/AvxMath/blob/master/AvxMath/AvxM... That particular source file implements that for 4-wide FP64 AVX vectors.
    - deleted 2y ago
      [deleted]
  - ack_complete 2y ago
    There are lots of cases where you can get away with moderate accuracy. Rotating a lot of batched sprites would be one of them; could easily get away with a mediocre Taylor series approximation, even though it's leaving free accuracy on the table compared to minimax. But not having _range reduction_ is a bigger problem, I can't see many uses for a sin() approximation that's only good for half wave. And as others have said, if you need range reduction for the approximation to work in its intended use case, that needs to be included in the benchmark because you're going to be paying that cost relative to `std::sin()`.
  - jcranmer 2y ago
    People who found that sin is the performance bottleneck in their code and are trying to find way to speed it up. One of the big problems with floating-point code in general is that users are largely ignorant of floating-point issues. Even something as basic as "0.1 + 0.2 != 0.3" shouldn't be that surprising to a programmer if you spend about five minutes explaining it, but the evidence is clear that it is a shocking surprise to a very large fraction of programmers. And that's the most basic floating-point issue, the one you're virtually guaranteed to stumble across if you do anything with floating-point; there's so many more issues that you're not going to think about until you uncover them for the first time (e.g., different hardware gives different results).
creato 2y ago
I'd suggest simply adding `assert(-M_PI/2 <= x && x <= M_PI/2)` to your function. It won't slow down the code in optimized builds, and makes it obvious that it isn't designed to work outside that range even if people copy/paste the code without reading it or any comments. Also, it would be good to have even in a "production" use of a function like this, in case something outside that range reaches it by accident.
- ashvardanian 2y ago
  Yes, that’s a very productive suggestion! Feel free to open a PR, or I’ll just patch it myself in a couple of hours when I’m back to the computer. Thanks!

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").

Certhas 2y ago
I don't know who the target audience is supposed to be, but who would be the type of person who tries to implement performance critical numerical codes but doesn't know the implications of Taylor expanding the sine function?
- Const-me 2y ago
  > tries to implement performance critical numerical codes but doesn't know the implications of Taylor expanding the sine function? That would be me, I’m afraid. I know little about Taylor series, but I’m pretty sure it’s less than ideal for the use case. Here’s a better way to implement faster trigonometry functions in C++ https://github.com/Const-me/AvxMath/blob/master/AvxMath/AvxMathTrig.cpp#L64-L128 https://github.com/Const-me/AvxMath/blob/master/AvxMath/AvxM... That particular source file implements that for 4-wide FP64 AVX vectors.
  - deleted 2y ago
    [deleted]
- ack_complete 2y ago
  There are lots of cases where you can get away with moderate accuracy. Rotating a lot of batched sprites would be one of them; could easily get away with a mediocre Taylor series approximation, even though it's leaving free accuracy on the table compared to minimax. But not having _range reduction_ is a bigger problem, I can't see many uses for a sin() approximation that's only good for half wave. And as others have said, if you need range reduction for the approximation to work in its intended use case, that needs to be included in the benchmark because you're going to be paying that cost relative to `std::sin()`.
- jcranmer 2y ago
  People who found that sin is the performance bottleneck in their code and are trying to find way to speed it up. One of the big problems with floating-point code in general is that users are largely ignorant of floating-point issues. Even something as basic as "0.1 + 0.2 != 0.3" shouldn't be that surprising to a programmer if you spend about five minutes explaining it, but the evidence is clear that it is a shocking surprise to a very large fraction of programmers. And that's the most basic floating-point issue, the one you're virtually guaranteed to stumble across if you do anything with floating-point; there's so many more issues that you're not going to think about until you uncover them for the first time (e.g., different hardware gives different results).

creato 2y ago

I'd suggest simply adding `assert(-M_PI/2 <= x && x <= M_PI/2)` to your function. It won't slow down the code in optimized builds, and makes it obvious that it isn't designed to work outside that range even if people copy/paste the code without reading it or any comments. Also, it would be good to have even in a "production" use of a function like this, in case something outside that range reaches it by accident.

ashvardanian 2y ago
Yes, that’s a very productive suggestion! Feel free to open a PR, or I’ll just patch it myself in a couple of hours when I’m back to the computer. Thanks!