Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / Fast Inverse Square Root?

Author
Message
Virtual Nomad
Moderator
18
Years of Service
User Offline
Joined: 14th Dec 2005
Location: SF Bay Area, USA
Posted: 7th Oct 2021 04:32 Edited at: 7th Oct 2021 04:55
can someone code THIS as a function for us?

early in this vid, it offers that it's triple the speed of SQRT with max 1% inaccuracy.

otherwise, i don't expect we'll get the same (any?) benefit as a function compared to it being a native AppGameKit command? if not, i'll post a request on the github.

and, if you're not familiar with the "original" code (in both links), don't click if certain "language" might offend.

meanwhile, it doesn't save much (~5%), but if i have tons of distance() calls per loop, this:


any better solutions vs SQRT out there (other than the title of this thread)?
[My Itch.io Home] [AGK on Itch.io]
[AGK Resource Directory] [TGC @ GitHub]
[CODE lang=agk] YOUR CODE HERE [/CODE]
[VIDEO=youtube] VIDEO ID [/VIDEO]
[AGK Showcase][Google Forum Search]
blink0k
Moderator
11
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 7th Oct 2021 05:02 Edited at: 7th Oct 2021 19:42
The idea for all those methods is to redefine a float as an integer. As far as i can tell that can only be done using a memblock which might mitigate your speed increase.
One thing we used to do is compare distance (without sqrt) to the distance^2
Virtual Nomad
Moderator
18
Years of Service
User Offline
Joined: 14th Dec 2005
Location: SF Bay Area, USA
Posted: 7th Oct 2021 05:35 Edited at: 7th Oct 2021 05:38
Quote: "One thing we used to do is compare distance (without sqrt) to the distance^2"

already doing that (2nd for/next in the code above).

i wouldnt mind a win plugin, then. but, that should be just as easy (read "no more difficult") to implement natively, right?
[My Itch.io Home] [AGK on Itch.io]
[AGK Resource Directory] [TGC @ GitHub]
[CODE lang=agk] YOUR CODE HERE [/CODE]
[VIDEO=youtube] VIDEO ID [/VIDEO]
[AGK Showcase][Google Forum Search]
Scraggle
Moderator
21
Years of Service
User Offline
Joined: 10th Jul 2003
Location: Yorkshire
Posted: 7th Oct 2021 10:07 Edited at: 7th Oct 2021 10:11
As Blink mentioned the real problem here is the conversion of a binary representation of a float into an integer.
But if you are just looking for the fastest native way of performing a distance check then you should lose the ^ it is almost is bad as a SQRT

Try this:
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 7th Oct 2021 19:13
Squaring the distance for comparison will be faster than using the inverse sqrt. So unless you need the actual distance for other calculations, I don't see a need for it.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Raven
19
Years of Service
User Offline
Joined: 23rd Mar 2005
Location: Hertfordshire, England
Posted: 7th Oct 2021 19:57
Quote: "early in this vid, it offers that it's triple the speed of SQRT with max 1% inaccuracy."


As encouraging as that might seem., unless you're ignoring support for the Vector Unit (SSE / VMX) then you're not going to see a such a dramatic improvement in performance.
This is because the Vector Unit (CU, SSE, VMX) have (since 2005) included a "Special Instruction" Path for Sqrt or Exponent Instructions.

I think this is showcased well with Scraggle' example code... as that in DBP (which doesn't use SSE for it's Maths Functions, for understandable reasons), his approach would provide up to 6.0 - 7.0x Faster Execution.
Compare this to AppGameKit Script., where we're instead seeing it perform at 0.6 - 0.7x what Sqrt does.
That's the difference of Vector Accelerated Maths.

And as noted in your original post., the Fast Inverse Square (approx.) was when Quake 3 released., just an incredibly performance uplift (up to 3.0x Faster).
But again keep in mind that most Maths Libraries at the time didn't support SSE., which had only been implemented in 1997 with the Pentium 2 Processors... and Pentium III didn't use a "New" Version; on top of that AMD Processors had 3DNow! (their own version of Maths Extensions) and Cyrix had MX (which was a Cutdown implementation of VMX that had been proposed for PowerPC Processors., this makes more sense when you realise Cyrix was bought by IBM who produced PowerPC)

As such the Maths Libraries at the time only supported the x86 FPU Instructions., which were slow; and thus a Fast Approx. was useful to support all Processor Architectures.
Today however... SSE is a Standard Feature., or at the very least is Translated into a Native Vector Instruction Set (cough:Ryzen:cough)
Because these have dedicated and accelerated Instruction Paths for things like Log, Sqrt, Mod, Pow, etc. well this means it's generally going to be better to just use the built-in Maths Functions; as they're going to be the fastest execution path.

Game_Code_here
4
Years of Service
User Offline
Joined: 2nd Jun 2020
Location:
Posted: 7th Oct 2021 21:11
Quote: "The algorithm accepts a 32-bit floating-point number as the input and stores a halved value for later use. Then, treating the bits representing the floating-point number as a 32-bit integer, a logical shift right by one bit is performed and the result subtracted from the number 0x5F3759DF, which is a floating point representation of an approximation of {\displaystyle {\sqrt {2^{127}}}}{\displaystyle {\sqrt {2^{127}}}}.[3] This results in the first approximation of the inverse square root of the input. Treating the bits again as a floating-point number, it runs one iteration of Newton's method, yielding a more precise approximation."
blink0k
Moderator
11
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 7th Oct 2021 22:10
If you populate a table of all the locations of your enemies you might be able to implement it in a shader
Virtual Nomad
Moderator
18
Years of Service
User Offline
Joined: 14th Dec 2005
Location: SF Bay Area, USA
Posted: 8th Oct 2021 13:09 Edited at: 8th Oct 2021 13:13
Quote: "lose the ^"

thanks. will do.

Quote: "If you populate a table "

doing that already for some kinda culling.

Quote: "implement it in a shader"

ah. i'll have a look at this. might be ideal?
[My Itch.io Home] [AGK on Itch.io]
[AGK Resource Directory] [TGC @ GitHub]
[CODE lang=agk] YOUR CODE HERE [/CODE]
[VIDEO=youtube] VIDEO ID [/VIDEO]
[AGK Showcase][Google Forum Search]
SFSW
22
Years of Service
User Offline
Joined: 9th Oct 2002
Location:
Posted: 9th Oct 2021 06:40
This is more of just a side note. One approach that has helped me in trying to squeeze every bit of performance out of AppGameKit that I can has been minimizing the number of operations in loops, rather than just contending with the type of operators. If you can do that wherever possible, you might be able to gain a few extra ticks here and there. And when combined across a codebase, such an approach can make a big overall difference. Just to illustrate with your example above, if we move the number of operations outside of the loop, but leave the core critical operations inside, we can gain nearly 200% performance:



While this doesn't necessary solve the issue of performing any required operations within a loop, if you can move any fixed calculations to outside any nested loop everywhere you can, such an approach can achieve very solid gains in performance as a whole.
Arch-Ok
AGK Developer
5
Years of Service
User Offline
Joined: 11th Jul 2019
Location: Bursa/TÜRKIYE
Posted: 19th Nov 2021 12:36
Fast inverse sqr was faster so long ago.

I tested it in x86 asm;


versus;




Ofcourse it gets worse in AGK;


maybe you should try making your distance comparisions in 'squared_length's so you will get rid of sqrt?

Login to post a reply

Server time is: 2024-11-21 12:28:19
Your offset time is: 2024-11-21 12:28:19