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

Fast Inverse Square Root

timmmm.github.io

Post reply on HN
Print view View original

31–40 of 100 posts

Re: Fast Inverse Square Root

#31

Post by qppo »

colejohnson66 wrote: post #27
qppo wrote: post #21

Earlier quoted context omitted.

That's the Linux way to do it union { int i; float f } u { .f = 1.23f }; int i = u.i; Another way is a memcpy, which I believe is the most defined way to do type punning int i; float f; memcpy(&i, &f, 4); But you also have to assume the size of those primitive types but that's pretty safe in modern C/C++.

In C++, type punning through pointers and unions is undefined behavior. Even `reinterpret_cast ` isn’t allowed because of aliasing (IIRC). The only “defined” way to do type punning is a memcpy. A compiler targeting something like x86 would optimize out the memcpy. For more information, see the C++20 final draft[0§7.6.1.9] [0]: https://isocpp.org/files/papers/N4860.pdf

There's a Torvalds rant about this specific UB and it's how they do it in the Linux kernel.

Re: Fast Inverse Square Root

#33

Post by TwoBit »

usmannk wrote: post #8
recursive wrote: post #3

Earlier quoted context omitted.

Thanks for this. I have one nit. You show `q = 1598029824 - u/2;` as being identical to `q = 0x5F400000 - u >> 1;`, but every language I know of uses a different order of operations, giving different results. It might be clearest to provide parentheses in the second case.

Interestingly enough it seems to do the shift first in Swift

All well-known programming languages will do the shift first.

Re: Fast Inverse Square Root

#34

Post by TwoBit »

colejohnson66 wrote: post #27
qppo wrote: post #21

Earlier quoted context omitted.

That's the Linux way to do it union { int i; float f } u { .f = 1.23f }; int i = u.i; Another way is a memcpy, which I believe is the most defined way to do type punning int i; float f; memcpy(&i, &f, 4); But you also have to assume the size of those primitive types but that's pretty safe in modern C/C++.

In C++, type punning through pointers and unions is undefined behavior. Even `reinterpret_cast ` isn’t allowed because of aliasing (IIRC). The only “defined” way to do type punning is a memcpy. A compiler targeting something like x86 would optimize out the memcpy. For more information, see the C++20 final draft[0§7.6.1.9] [0]: https://isocpp.org/files/papers/N4860.pdf

I really wish C and C++ had an explicit type punning operator. They are systems programming languages and this is very often needed.

Re: Fast Inverse Square Root

#35

Post by ChrisFoster »

qppo wrote: post #21
IAmLiterallyAB wrote: post #19

Earlier quoted context omitted.

Would a union do the trick?

That's the Linux way to do it union { int i; float f } u { .f = 1.23f }; int i = u.i; Another way is a memcpy, which I believe is the most defined way to do type punning int i; float f; memcpy(&i, &f, 4); But you also have to assume the size of those primitive types but that's pretty safe in modern C/C++.

Punning through the union is explicitly allowed in the GCC documentation which explains why it's reliable for use in the Linux kernel. See

https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Typ...

> you also have to assume the size of those primitive types

This usually works though there's some situations where you could still be surprised. For instance if you're programming embedded processors with avr-gcc you'll have sizeof(double)==4

Re: Fast Inverse Square Root

#36

Post by beached_whale »

recursive wrote: post #3
timhh wrote: post #2

This is an explanation of the fast inverse square root that I hope is easy to understand. I also managed to improve on it a little bit.

Thanks for this. I have one nit. You show `q = 1598029824 - u/2;` as being identical to `q = 0x5F400000 - u >> 1;`, but every language I know of uses a different order of operations, giving different results. It might be clearest to provide parentheses in the second case.

Use brackets to be explicit about your expected order of operations.

Re: Fast Inverse Square Root

#37

Post by thehobgoblin »

TwoBit wrote: post #33
usmannk wrote: post #8

Earlier quoted context omitted.

Interestingly enough it seems to do the shift first in Swift

All well-known programming languages will do the shift first.

I looked at about 20 different "popular" languages and I believe that only 2 (Go and Swift) of them have shifts at a higher precedence than addition.

I think I'm missing a reference/joke =/

Re: Fast Inverse Square Root

#39

Post by taneq »

person_of_color wrote: post #38

What was the speedup from this? If only 1% of cpu time was spent on slow square root, and this sped it up by 100%, it would be barely worth it.

I don't know how heavily it was used in Quake but I'd bet quite a lot. Carmack didn't mess around optimizing things for no reason, he was (and is) pretty focused on spending time (coder and CPU) where it will do most good.

Also, a "mere" 1% speedup seems trivial for most general coding but squeezing 1% out of optimized game code is like blood from a stone. Add a bunch of similar tricks together and you can see 10-20% overall improvement which is huge.

Re: Fast Inverse Square Root

#40

Post by longemen3000 »

person_of_color wrote: post #38

What was the speedup from this? If only 1% of cpu time was spent on slow square root, and this sped it up by 100%, it would be barely worth it.

It clearly depends on the workload. If you have tons of 3d articles or polygons on a screen, one of the most repeated operations are the calculation of norms (x/sqrt(sum(x)). John carmack came to the fast inverse sqrt root explicitly for this speed advantage
Post reply on HN