Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster asin() was hiding in plain sight

16bpp.net

Post reply on HN
Print view View original

71–80 of 140 posts

Re: Faster asin() was hiding in plain sight

#71

Post by boothby »

exmadscientist wrote: post #67
boothby wrote: post #63

Earlier quoted context omitted.

Thinking about speed like this used to be necessary in C and C++ but these days you should feel free to write the most legible thing (Horner's form) and let the compiler find the optimal code for it (probably similar to Horner's form but broken up to have a shallower dependency chain). But if you're writing in an interpreted language that doesn't have a good JIT, or for a platform with a custom compiler, it might be…

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.

Re: Faster asin() was hiding in plain sight

#72

Post by eska »

boothby wrote: post #63
Sesse__ wrote: post #51

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)

Thinking about speed like this used to be necessary in C and C++ but these days you should feel free to write the most legible thing (Horner's form) and let the compiler find the optimal code for it (probably similar to Horner's form but broken up to have a shallower dependency chain). But if you're writing in an interpreted language that doesn't have a good JIT, or for a platform with a custom compiler, it might be…

The compiler is often not allowed to rearrange such operations due to a change in intermediate results. So one would have to activate something like fastmath for this code, but that’s probably not desired for all code, so one has to introduce a small library, and so on. Debug builds may be using different compilation flags, and suddenly performance can become terrible while debugging. Performance can also tank because a new compiler version optimizes differently, etc. So in general I don’t think this advice is true.

Re: Faster asin() was hiding in plain sight

#73

Post by def-pri-pub »

adampunk wrote: post #6

We love to leave faster functions languishing in library code. The basis for Q3A’s fast inverse square root had been sitting in fdlibm since 1986, on the net since 1993: https://www.netlib.org/fdlibm/e_sqrt.c

Funny enough that fdlimb implementation of asin() did come up in my research. I believe it might have been more performant in the past. But taking a quick scan of `e_asin.c`, I see it doing something similar to the Cg asin() implementation (but with more terms and more multiplications, which my guess is that it's slower). I think I see it also taking more branches (which could also lead to more of a slowdown).

Re: Faster asin() was hiding in plain sight

#74

Post by def-pri-pub »

glitchc wrote: post #22

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…

You'd be surprised how it actually is worth the effort, even just a 1% improvement. If you have the time, this is a great talk to listen to: https://www.youtube.com/watch?v=kPR8h4-qZdk

For a little toy ray tracer, it is pretty measly. But for a larger corporation (with a professional project) a 4% speed improvement can mean MASSIVE cost savings.

Some of these tiny improvements can also have a cascading effect. Imagining finding a +4%, a +2% somewhere else, +3% in neighboring code, and a bunch of +1%s here and there. Eventually you'll have built up something that is 15-20% faster. Down the road you'll come across those optimizations which can yield the big results too (e.g. the +25%).

Re: Faster asin() was hiding in plain sight

#75

Post by scottlamb »

boothby wrote: post #63
Sesse__ wrote: post #51

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)

Thinking about speed like this used to be necessary in C and C++ but these days you should feel free to write the most legible thing (Horner's form) and let the compiler find the optimal code for it (probably similar to Horner's form but broken up to have a shallower dependency chain). But if you're writing in an interpreted language that doesn't have a good JIT, or for a platform with a custom compiler, it might be…

Probably for ints unconditionally. For floats in Sesse__'s example without `-ffast-math`, I count 10 muls, 2 muladds, 1 add. With `-ffast-math`, 1 mul, 3 muladds. https://godbolt.org/z/dPrbfjzEx>

Re: Faster asin() was hiding in plain sight

#76

Post by def-pri-pub »

scottlamb wrote: post #27
TimorousBestie wrote: post #16

Earlier quoted context omitted.

I don’t know much about raytracing but it’s probably tricky to orchestrate all those asin calls so that the input and output memory is aligned and contiguous. My uneducated intuition is that there’s little regularity as to which pixels will take which branches and will end up requiring which asin calls, but I might be wrong.

I'd expect it to come down to data-oriented design: SoA (structure of arrays) rather than AoS (array of structures). I skimmed the author's source code, and this is where I'd start: https://github.com/define-private-public/PSRayTracing/blob/8... Instead of an `_objects`, I might try for a `_spheres`, `_boxes`, etc. (Or just `_lists` still using the virtual dispatch but for each list, rather than each object.) The `as…

When I was working on this project, I was trying to restrict myself to the architecture of the original Ray Tracing in One Weekend book series. I am aware that things are not as SIMD friendly and that becomes a major bottle neck. While I am confident that an architectural change could yield a massive performance boost, it's something I don't want to spend my time on.

I think it's also more fun sometimes to take existing systems and to try to optimize them given whatever constraints exist. I've had to do that a lot in my day job already.

Re: Faster asin() was hiding in plain sight

#77

Post by def-pri-pub »

stephencanon wrote: post #66
def-pri-pub wrote: post #55

Earlier quoted context omitted.

Wait, what? Do you have a resource I could read up on about that? That is moderately concerning if your math isn't portable across chips.

When Intel specced the rsqrt[ps]s and rcp[ps]s instructions ~30 years ago, they didn't fully specify their behavior. They just said their relative error is "smaller than 1.5 * 2⁻¹²," which someone thought was very clever because it gave them leeway to use tables or piecewise linear approximations or digit-by-digit computation or whatever was best suited to future processors. Since these are not IEEE 754 correctly-rou…

Thanks!

Re: Faster asin() was hiding in plain sight

#78

Post by cmovq »

eska wrote: post #65
Sesse__ wrote: post #51

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 problem with Horner’s scheme is that it creates a long chain of data dependencies, instead of making full use of all execution units. Usually you’d want more of a binary tree than a chain.

Not in this case because the dependencies are the same:

Naive: https://godbolt.org/z/Gzf1KM9Tc

Horner's: https://godbolt.org/z/jhvGqcxj1

Re: Faster asin() was hiding in plain sight

#80

Post by def-pri-pub »

cmovq wrote: post #58

> After all of the above work and that talk in mind, I decided to ask an LLM. Impressive that an LLM managed to produce the answer from a 7 year old stack overflow answer all on its own! [1] This would have been the first search result for “fast asin” before this article was published. [1]: https://stackoverflow.com/a/26030435

I did see that, but isn't the vast majority of that page talking about acos() instead?
Post reply on HN