> and this sped it up by 100%

Over 1,000%.

x87 fsqrt took ~70 cycles on the Pentium MMX x87, x87 fdiv was ~39 cycles - so doing inverse square root on x87 was ~109 cycles. The fast inverse square root routine was in the vicinity of 10 cycles.

In Quake, each vertex needed to have its normal vector calculated, which resulted in... I dunno, 100,000 inverse square root calculations per second, assuming you're pushing 100,000 polygons per second. Assuming a 100MHz CPU, the x87 inverse square root calculations would consume 11% of the CPU cycles, the fast inverse square root routine would consume 1% of the CPU cycles.

https://en.wikipedia.org/wiki/X87#Performance

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.

I mean it's now ingrained in programming lore, but the reality is that Carmack has nothing to do with this and Carmack himself has never taken credit for it. The fast inverse square root dates back to the 80s and has its roots in SGI's systems. One of the developers who worked at SGI would eventually go on to work at ID developing Quake and worked on this optimization.

Oh, I didn't mean to imply Carmack invented it - he himself is pretty clear that he didn't. I just meant that incremental improvements in efficiency like this can add up surprisingly fast, and that once the low hanging fruit are taken, they're well worth doing.

> 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.

I've always wondered too if it would be possible to log all the values it's actually calculating the inverse square root for, and just save them in a lookup table. Or even just the most common x% of them if you could reliably know for which numbers its most commonly running the calculation on.

Even if you pretend it’s a few values (which it’s not, there are a lot of floats), this would be dramatically slower due to the cache miss involved.

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

It was first found in quake 3, which I believed used software rendering. Given that inverse square root is heavily used for lighting functions, and it was all done in CPU, it's reasonable to believe that this provided a non-negligible speedup overall.

iirc Quake 3 required a 3D accelerator and didn't support software rendering - but this was before graphics cards supported hardware T&L so you're right those lighting calcs would be performed on the CPU