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

91–100 of 100 posts

Re: Fast Inverse Square Root

#91

Post by dragontamer »

fluffything wrote: post #82
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 ;)

vrsqrtps executes once-per-cycle throughput on Skylake / Icelake.

You can always compute newton's method afterwards to improve the accuracy. But getting the maximum accuracy from one cycle is probably best.

Re: Fast Inverse Square Root

#92

Post by fluffything »

dragontamer wrote: post #91
fluffything wrote: post #82

Earlier quoted context omitted.

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 ;)

vrsqrtps executes once-per-cycle throughput on Skylake / Icelake. You can always compute newton's method afterwards to improve the accuracy. But getting the maximum accuracy from one cycle is probably best.

You can create an instruction to perform X newton iterations in 1 cycle if you want, and you can pick X to give you 14-bit precision.

With such an instruction, you could exponentially increase the precision in 2 cycles by just using the same instruction twice.

You can't do that on Intel's hardware. As you mention, you'd need to roll your own multi-SIMD-instruction rsqrt newton iteration complex loop, and use it after the first SIMD call.

That's really sad. There is hardware to perform Newton iterations on Intel CPUs, that's how that instruction is implemented, but the ISA only exposes this hardware via the "do a 14-bit rsqrt operation", which means that you can't really use it to increase precision if that does not suffice for your app.

Re: Fast Inverse Square Root

#94

Post by SoSoRoCoCo »

IAmLiterallyAB wrote: post #19
SoSoRoCoCo wrote: post #18

FYI: Type punning like this doesn't work on all compilers i = * ( long * ) &y; // evil floating point bit level hacking Learned this recently with Arm AC6. [Also, this kind of genius analytic approximation of hot functions that do math makes me all tingly]

Would a union do the trick?

Yes, that was the only "portable solution". I use quotes because we had to assert() the sizeof float with uint32_t in the code prologue (it is unlikely to be an issue now, but the code is 25 years old, so we stuck to the spirit of expecting compilers where C types could be a variety of sizes, not just the "conventional" sizes of today). Unions are defined, casting is very poorly defined, especially floatint. There's a good link a few comments down.

Re: Fast Inverse Square Root

#95

Post by andrewaylett »

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 C abstract machine presents i and f as having separate locations in memory, but a compiler that knows that memcopy does can avoid actually saving the target machine registers to the stack, then avoid even copying values between registers.

Re: Fast Inverse Square Root

#96

Post by grayhatter »

nurettin wrote: post #77
grayhatter wrote: post #24

Earlier quoted context omitted.

Wow, bruh, who hurt you?

xkcd is as generic as they get. Randall goes idea -> generate numbers -> generate graph -> punchline and people milk it for as long as possible. It's like geek themed garfield. I wouldn't be surprised if he tries xkcd without stick people soon.

So it's generic and boring. But why are you really angry about it?

Re: Fast Inverse Square Root

#97

Post by adamnemecek »

grayhatter wrote: post #96
nurettin wrote: post #77

Earlier quoted context omitted.

xkcd is as generic as they get. Randall goes idea -> generate numbers -> generate graph -> punchline and people milk it for as long as possible. It's like geek themed garfield. I wouldn't be surprised if he tries xkcd without stick people soon.

So it's generic and boring. But why are you really angry about it?

Because it's everywhere.

Re: Fast Inverse Square Root

#98

Post by nurettin »

grayhatter wrote: post #96
nurettin wrote: post #77

Earlier quoted context omitted.

xkcd is as generic as they get. Randall goes idea -> generate numbers -> generate graph -> punchline and people milk it for as long as possible. It's like geek themed garfield. I wouldn't be surprised if he tries xkcd without stick people soon.

So it's generic and boring. But why are you really angry about it?

Why do you attribute anger to every criticism? This is getting weird.

Re: Fast Inverse Square Root

#99

Post by andi999 »

andrewaylett wrote: post #95
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 C abstract machine presents i and f as having separate locations in memory, but a compiler that knows that memcopy does can avoid actually saving the target machine registers to the stack, then avoid even copying values between registers.

Thanks. Does that really happen?

Re: Fast Inverse Square Root

#100

Post by account42 »

andi999 wrote: post #99
andrewaylett wrote: post #95

Earlier quoted context omitted.

The C abstract machine presents i and f as having separate locations in memory, but a compiler that knows that memcopy does can avoid actually saving the target machine registers to the stack, then avoid even copying values between registers.

Thanks. Does that really happen?

Yes.
Post reply on HN