81–90 of 140 posts
Earlier quoted context omitted.
The common subexpression elimination (CSE) pass in compilers takes care of that.
Compilers cannot do this optimization for floating point [1] unless you're compiling with -ffast-math. In general, don't rely on compilers to optimize floating point sub-expressions. [1]: https://godbolt.org/z/8bEjE9Wxx
[flagged]
And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D (10 muls, 3 muladds) instead of the faster tmp = x * x; ((A * tmp + B) * tmp + C) * tmp + D (1 mul, 3 muladds)
[flagged]
And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D (10 muls, 3 muladds) instead of the faster tmp = x * x; ((A * tmp + B) * tmp + C) * tmp + D (1 mul, 3 muladds)
This line: > This amazing snippet of code was languishing in the docs of dead software, which in turn the original formula was scrawled away in a math textbook from the 60s. was kind of telling for me. I have some background in this sort of work (and long ago concluded that there was pretty much nothing you can do to improve on existing code, unless either you have some new specific hardware or domain constraint, or…
These are books that my uni courses never had me read. I'm a little shocked at times at how my degree program skimped on some of the more famous texts.
In physics grad school, professors would occasionally allude to it, and textbooks would cite it ... pretty often. So it's a thing anyone with postgraduate physics education should know exists, but you wouldn't ever be assigned it.
Earlier quoted context omitted.
And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D (10 muls, 3 muladds) instead of the faster tmp = x * x; ((A * tmp + B) * tmp + C) * tmp + D (1 mul, 3 muladds)
The reason for writing out all of the x multiplications like that is that I was hoping the compiler detect such a pattern perform an optimization for me. Mat Godbolt's "Advent of Compiler Optimizations" series mentions some of these cases where the compiler can do more auto-optimizations for the developer.
Earlier quoted context omitted.
You should never assume the compiler is allowed to reorder floating-point computations like it does with integers. Integer math is exact, within its domain. Floating-point math is not. The IEEE-754 standard knows this, and the compiler knows this.
Ah, fair point, it has been a while since I've needed fast inexact math. Though... they are allowed to cache common subexpressions, and my point about dependency chains is quite relevant on modern hardware. So x*x, x*x*x, etc may each be computed once. And since arithmetic operators are left-to-right associative, the rather ugly code, as written, is fast and not as wasteful as it appears.
This is incorrect, for exactly the reason you are citing: A * x * x * x * x = (((A * x) * x) * x) * x), which means that (x * x) is nowhere to be seen in the expression and cannot be factored out. Now, if you wrote x * x * x * x * A instead, _then_ the compiler could have done partial CSE against the term with B, although still not as much as you'd like.
Isn't the faster approach SIMD [edit: or GPU]? A 1.05x to 1.90x speedup is great. A 16x speedup is better! They could be orthogonal improvements, but if I were prioritizing, I'd go for SIMD first. I searched for asin on Intel's intrinsics guide. They have a AVX-512 instrinsic `_mm512_asin_ps` but it says "sequence" rather than single-instruction. Presumably the actual sequence they use is in some header file somewher…
I don't do much float work but I don't think there is a single regular sine instruction only old x87 float stack ones. I was curious what "sequence" would end up being but my compiler is too old for that intrinsic. Even godbolt didn't help for gcc or clang but it did reveal that icc produced a call https://godbolt.org/z/a3EsKK4aY
The 4% improvement doesn't seem like it's worth the effort. On a general note, instructions like division and square root are roughly equal to trig functions in cycle count on modern CPUs. So, replacing one with the other will not confer much benefit, as evidenced from the results. They're all typically implemented using LUTs, and it's hard to beat the performance of an optimized LUT, which is basically a multiplexer…
> The 4% improvement doesn't seem like it's worth the effort. People have gotten PhDs for smaller optimizations. I know. I've worked with them. > instructions like division and square root are roughly equal to trig functions in cycle count on modern CPUs. What's the x86-64 opcode for arcsin?
x86-64 had instructions for the exponential and logarithmic functions in Xeon Phi, but those instructions have been removed in Skylake Server and the later Intel or AMD CPUs with AVX-512 support.
However, instructions for trigonometric functions have no longer been added after Intel 80387, and those of 8087 and 80387 are deprecated.
The 4% improvement doesn't seem like it's worth the effort. On a general note, instructions like division and square root are roughly equal to trig functions in cycle count on modern CPUs. So, replacing one with the other will not confer much benefit, as evidenced from the results. They're all typically implemented using LUTs, and it's hard to beat the performance of an optimized LUT, which is basically a multiplexer…
> The 4% improvement doesn't seem like it's worth the effort. People have gotten PhDs for smaller optimizations. I know. I've worked with them. > instructions like division and square root are roughly equal to trig functions in cycle count on modern CPUs. What's the x86-64 opcode for arcsin?
Not required. ATAN and SQRTS(S|D) are sufficient, the half-angle approach in the article is the recommended way.
> People have gotten PhDs for smaller optimizations. I know. I've worked with them.
I understand the can, not sure about the should. Not trying to be snarky, we just seem to be producing PhDs with the slimmest of justifications. The bar needs to be higher.