4 ms·
> if we’re working with batches of points and willing to live with tiny errors, we can produce an atan2 approximation which is 50 times faster than the standard
by stephencanon 5y ago
> if we’re working with batches of points and willing to live with tiny errors, we can produce an atan2 approximation which is 50 times faster than the standard version provided by libc.
Which libc, though? I assume glibc, but it's frustrating when people talk about libc as though there were a single implementation. Each vendor supplies their own implementation, libc is just a common interface defined by the C library. There is no "standard version" provided by libc.
In particular, glibc's math functions are not especially fast--Intel's and Apple's math libraries are 4-5x faster for some functions[1], and often more accurate as well, for example (and both vendors provide vectorized implementations). Even within glibc versions, there have been enormous improvements over the last decade or so, and for some functions there are big performance differences depending on whether or not -fno-math-errno is specified. (I would also note that atan2 has a lot of edge cases, and more than half the work in a standards-compliant libc is in getting those edge cases with zeros and infinities right, which this implementation punts on. There's nothing wrong with that, but that's a bigger tradeoff for most users than the small loss of accuracy and important to note.)
So what are we actually comparing against here? Comparing against a clown-shoes baseline makes for eye-popping numbers, but it's not very meaningful.
None of this should really take away from the work presented, by the way--the techniques described here are very useful for people interested in this stuff.
[1] I don't know the current state of atan2f in glibc specifically; it's possible that it's been improved since last I looked at its performance. But the blog post cites "105.98 cycles / element", which would be glacially slow on any semi-recent hardware, which makes me think something is up here.
- rostayob 5y ago(I'm the author) You're right, I should have specified -- it is glibc 2.32-48 . This the source specifying how glibc is built: https://github.com/NixOS/nixpkgs/blob/97c5d0cbe76901da0135b05cdbdfc5b068a7942c/pkgs/development/libraries/glibc/default.nix https://github.com/NixOS/nixpkgs/blob/97c5d0cbe76901da0135b0... . I've amended the article so that it says `glibc` rather than `libc`, and added a sidenote specifying the version. I link to it statically as indicated in the gist, although I believe that shouldn't matter. Also see https://gist.github.com/bitonic/d0f5a0a44e37d4f0be03d34d47acb6cf#gistcomment-3864005 https://gist.github.com/bitonic/d0f5a0a44e37d4f0be03d34d47ac... . Note that the hardware is not particularly recent (Q3 2017), but we tend to rent servers which are not exactly on the bleeding edge, so that was my platform.
- stephencanon 5y agoThanks for clarifying! Without benchmarking, I would expect atan2f to be around 20-30 cycles per element or less with either Intel's or Apple's scalar math library, and proportionally faster for their vector libs.
- rostayob 5y agoThanks for the info. By the way, your writing on floating point arithmetic is very informative -- I even cite a message of yours on FMA in the post itself!
- floxy 5y agoThanks for the interesting writeup. I wonder if it is because glibc has a less-optimized atan2f (for floats). The double version seems quite involved in glibc anyway: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/ieee754/dbl-64/e_atan2.c;h=b77ad2dc6b9561e6396a76db11f6db686f170bb1;hb=ae37d06c7d127817ba43850f0f898b793d42aea7 https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/iee... ...where the atan2f version ends up calling atan, which doesn't seem as sophisticated: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/ieee754/flt-32/s_atanf.c;h=f61b0f5ef64866fb053a87f9c1a968165ba4de2a;hb=ae37d06c7d127817ba43850f0f898b793d42aea7 https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/iee...
- rostayob 5y agoAh, regarding edge cases: the only edge cases I do not handle are infinities and the origin. In my case these are both uninteresting: we deal with points from panoramic images, so those both make no sense. I did want to deal with 0s in either coordinates though, and to preserve NaNs. You're right that atan2 has a lot of edge cases, which is why it made for an interesting subject. I thought it was neat that the edge cases I did care about fell out fairly naturally from the efficient bit-twiddling. That said, the versions presented in the article post are _not_ conforming, as I remark repeatedly. The article is more about getting people curious about some topics that I think are neat, more than a guide on how to implement those standard functions correctly.