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

81–90 of 100 posts

Re: Fast Inverse Square Root

#81

Post by [deleted] »

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

[deleted]

Re: Fast Inverse Square Root

#82

Post by fluffything »

jedbrown wrote: post #4

It may be useful to mention that modern architectures often have vectorized instructions like vrsqrt14ps (accessible via the _mm512_rsqrt14_ps intrinsic) that provides a 14-bit approximation (there are more accurate variants too) in every lane with an inverse throughput of 2. These are faster than the integer bit hacks. https://software.intel.com/sites/landingpage/IntrinsicsGuide...

I prefer architectures that have a vector instruction for computing one or two Newton iterations instead.

That way you can quickly get the precision that you want ;)

Re: Fast Inverse Square Root

#83

Post by balddenimhero »

zeroonetwothree wrote: post #20

To me "inverse square root" means "square" so it makes the title of this kind of funny.

Here, "inverse" is an abbreviation of "multiplicative inverse" (aka. the reciprocal). Granted, shortening it to just "inverse" is misleading, but the name has stuck.

Re: Fast Inverse Square Root

#84

Post by hurrrrrrrr »

andi999 wrote: post #62
colejohnson66 wrote: post #27

Earlier quoted context omitted.

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 always thought the memcopy is optimized out, but can you explain how in int i; float f; memcopy (&i, &f,4) the memcopy can be optimized out? Probably I am misunderstanding the statement.

The compiler is not beholden to the standard library but the standard. So all modern compilers come with a bit of knowledge of how standard library functions like memcpy are supposed to behave and as long as the visible effect is the same it's allowed to do anything it wants. So instead of calling the function memcpy for a size of 4, it can e.g. just use a mov instruction to move the value from a float to an integer register. [1] It does additional analysis on how the values are used and maybe it doesn't even need to move the value at all, but that's the gist of it.

[1] https://gcc.godbolt.org/z/x4P7jE

Re: Fast Inverse Square Root

#85

Post by hurrrrrrrr »

nurettin wrote: post #76
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.

> 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. If you can do 10,000 things with 1% cpu time, and you are now able to do 5,000 more things, is it still not worth it?

In isolation, no. You could instead spend your time optimizing something else that's currently slower and speed that up instead.

Re: Fast Inverse Square Root

#86

Post by rustybolt »

unwind wrote: post #80
rustybolt wrote: post #54

A little self-promotion: I've written a blog post to answer the question that this one ends with (how to optimize divisions by constant integers): https://rubenvannieuwpoort.nl/posts/division-by-constant-uns... https://ridiculousfish.com/blog/posts/labor-of-division-epis... and https://ridiculousfish.com/blog/posts/labor-of-division-epis... also explain this (and are probably better written than my blogpost).

Very nice page! Minor nit, there's a typo here in the power-of-two example: uint divide(uint n) { return n the shifts should be to the right, obviously.

Thanks! I have a completely rewritten version in the pipeline, where I use easier versions of the theorems/proofs and fix some mistakes (in fact, the proof of lemma 1 is quite nonsensical if you look closely).

Re: Fast Inverse Square Root

#87

Post by dragontamer »

jedbrown wrote: post #4

It may be useful to mention that modern architectures often have vectorized instructions like vrsqrt14ps (accessible via the _mm512_rsqrt14_ps intrinsic) that provides a 14-bit approximation (there are more accurate variants too) in every lane with an inverse throughput of 2. These are faster than the integer bit hacks. https://software.intel.com/sites/landingpage/IntrinsicsGuide...

AMD Vega has "V_RSQ_F32" (Reciprocal Square Root"), and NVidia has rsqrt.approx.f32. ARM has vrecpsq_f32.

So all the major platforms, CPUs and GPUs, implement the fast reciprocal square root to decent amounts of accuracy, without any need of bit-twiddling anymore.

Re: Fast Inverse Square Root

#88

Post by colejohnson66 »

hurrrrrrrr wrote: post #84
andi999 wrote: post #62

Earlier quoted context omitted.

I always thought the memcopy is optimized out, but can you explain how in int i; float f; memcopy (&i, &f,4) the memcopy can be optimized out? Probably I am misunderstanding the statement.

The compiler is not beholden to the standard library but the standard. So all modern compilers come with a bit of knowledge of how standard library functions like memcpy are supposed to behave and as long as the visible effect is the same it's allowed to do anything it wants. So instead of calling the function memcpy for a size of 4, it can e.g. just use a mov instruction to move the value from a float to an integer…

A good example of this is the string functions in the C stdlib. I’ve reverse engineered some programs where the compiler used x86’s built-in “string” instructions instead of calling out to, say, `strlen`.

Re: Fast Inverse Square Root

#89

Post by augustk »

The implementation can be more concisely written (and without reassigning variables) as

  float InvSqrt(float x)
  {
     long yl;
     float y;

     yl = 0x5f3759df - ((*(long *) &x) >> 1);
     y = *(float *) &yl;
     return y * (1.5F - (x * 0.5F * y * y));
  }

Re: Fast Inverse Square Root

#90

Post by izackp »

thdrdt wrote: post #69
matsemann wrote: post #64

> Games calculate square roots and inverse square roots all the time to find the lengths of vectors A trick here is that one often doesn't have to do the square root. For instance, if you want something to happen when an object is 5 units away from another object, it's normal to do if sqrt( (x2-x1)^2 - (y2-y1)^2 ) but instead you can do if (x2-x1)^2 - (y2-y1)^2 trading a sqrt for a squaring. And often the square of t…

Sometimes you can even get away by dropping the square completely: if (x2-x1) - (y2-y1) I once used this in a path tracer to speed things up a little. The results where less accurate but sometimes this can be used as trade-off.

https://gist.github.com/izackp/5ae96a740678946d8763c198b0e54... I have a list of functions for distance calculation with metrics on speed and accuracy. If anyone would find it useful.
Post reply on HN