5 ms·

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.

taneq 6y ago
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.
- Kranar 6y ago
  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.
  - taneq 6y ago
    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.
longemen3000 6y ago
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
gruez 6y ago
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.
- smcl 6y ago
  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
grecy 6y ago
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.
- jleahy 6y ago
  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.
nwallin 6y ago
> 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 https://en.wikipedia.org/wiki/X87#Performance
nurettin 6y ago
> 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?
- hurrrrrrrr 6y ago
  In isolation, no. You could instead spend your time optimizing something else that's currently slower and speed that up instead.

taneq 6y ago

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.

Kranar 6y ago
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.
- taneq 6y ago
  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.

longemen3000 6y ago

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

gruez 6y ago

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.

smcl 6y ago
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

grecy 6y ago

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.

jleahy 6y ago
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.

nwallin 6y ago

> 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 https://en.wikipedia.org/wiki/X87#Performance

nurettin 6y ago

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

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