3 ms·

> every source release produces a new wave of discoveries/press about crazy things id did in the guts of one of their engines wow, that sounds interesting! any

> every source release produces a new wave of discoveries/press about crazy things id did in the guts of one of their engines wow, that sounds interesting! any links?

getsat 15y ago
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ http://betterexplained.com/articles/understanding-quakes-fas...
reverend_gonzo 15y ago
Here's an example: Carmack's Square Root implementation, which runs four times faster than the assembly language instruction. http://www.beyond3d.com/content/articles/8/ http://www.beyond3d.com/content/articles/8/ http://www.codemaestro.com/reviews/9 http://www.codemaestro.com/reviews/9
- daeken 15y ago
  Bear in mind that this is inverse square root (a misnomer; it's really 1/sqrt, or the reciprocal), not just the square root. Square roots are decently fast as provided by the processor, but not when combined with the division needed for the reciprocal; combining the two is why FastInvSqrt is so fast.
- kmm 15y ago
  It was faster before 2000, but is it still faster now? On my computer it is indeed four times faster, but the marvellous method is on its own again four times slower than SSE, using the rsqrtps instruction, with the advantage of a way lower maximum error. To take the square root of an array of 1024 floats: Naive sqrtf() CPU cycles used: 48160, error: 0.000000 Vectorized SSE CPU cycles used: 2970, error: 0.000392 Marvellous Carmack method CPU cycles used: 11330, error: 0.002186
  - Tomek_ 15y ago
    No, it's not faster now and it's no longer really used probably (don't know if smartphones, tablets, various consoles, etc. offer access to any equivalent of rsqrtps), but it was brilliant at its time (well, still is, it's just not very useful). Remember, Quake was released in 1996, SSE came out in 1999.
  - jemfinch 15y ago
    Would you mind posting your bench framework for this?
    - kmm 15y ago
      I didn't make the code, nor do I want to take credit for it. I only changed a few lines to make it compile. The code explicitly say one can redistribute the code as one wants, so here it is http://pastebin.com/EnJi86hF http://pastebin.com/EnJi86hF Would you mind posting your results here? I'm quite interested if this has the same pattern everywhere.
      - jemfinch 15y ago
        Here's what I get: Input array size is 1024 Naive sqrtf() CPU cycles used: 54514, error: 0.000000 Vectorized SSE CPU cycles used: 900, error: inf Marvelous CPU cycles used: 21514, error: inf I'm not sure how to interpret the errors. I had to make a few changes myself for this to compile on my machine.
  - liamkf 15y ago
    Hmm, that seems a bit misleading. The SSE implementation will of course be much faster than a non-vectorized implementation... it's working on 4 floats at a time. A vectorized version of the marvelous method would be a fairer comparison. If your data is not very vectorizable and you don't need high precision, it's still fairly marvelous.
    - onan_barbarian 15y ago
deleted 15y ago
[deleted]
Arjuna 15y ago
Check out "Graphics Programming Black Book" [1] by Michael Abrash [2]. If you have not read his work, you are in for a treat. He has a wonderful writing style that is both engaging and illuminating. There are a number of chapters [3] in the book that specifically discuss technology and development related to Quake. [1] PDF: http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/graphics-programming-black-book-r1698 http://www.gamedev.net/page/resources/_/technical/graphics-p... [2] http://en.wikipedia.org/wiki/Michael_Abrash http://en.wikipedia.org/wiki/Michael_Abrash [3] Chapter 64 - Quake's Visible-Surface Determination Chapter 66 - Quake's Hidden-Surface Removal Chapter 67 - Sorted Spans in Action Chapter 68 - Quake's Lighting Model Chapter 69 - Surface Caching and Quake's Triangle Models Chapter 70 - Quake: A Post-Mortem and a Glimpse into the Future

> every source release produces a new wave of discoveries/press about crazy things id did in the guts of one of their engines wow, that sounds interesting! any links?

getsat 15y ago

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ http://betterexplained.com/articles/understanding-quakes-fas...

reverend_gonzo 15y ago

Here's an example: Carmack's Square Root implementation, which runs four times faster than the assembly language instruction. http://www.beyond3d.com/content/articles/8/ http://www.beyond3d.com/content/articles/8/ http://www.codemaestro.com/reviews/9 http://www.codemaestro.com/reviews/9

daeken 15y ago
Bear in mind that this is inverse square root (a misnomer; it's really 1/sqrt, or the reciprocal), not just the square root. Square roots are decently fast as provided by the processor, but not when combined with the division needed for the reciprocal; combining the two is why FastInvSqrt is so fast.
kmm 15y ago
It was faster before 2000, but is it still faster now? On my computer it is indeed four times faster, but the marvellous method is on its own again four times slower than SSE, using the rsqrtps instruction, with the advantage of a way lower maximum error. To take the square root of an array of 1024 floats: Naive sqrtf() CPU cycles used: 48160, error: 0.000000 Vectorized SSE CPU cycles used: 2970, error: 0.000392 Marvellous Carmack method CPU cycles used: 11330, error: 0.002186
- Tomek_ 15y ago
  No, it's not faster now and it's no longer really used probably (don't know if smartphones, tablets, various consoles, etc. offer access to any equivalent of rsqrtps), but it was brilliant at its time (well, still is, it's just not very useful). Remember, Quake was released in 1996, SSE came out in 1999.
- jemfinch 15y ago
  Would you mind posting your bench framework for this?
  - kmm 15y ago
    I didn't make the code, nor do I want to take credit for it. I only changed a few lines to make it compile. The code explicitly say one can redistribute the code as one wants, so here it is http://pastebin.com/EnJi86hF http://pastebin.com/EnJi86hF Would you mind posting your results here? I'm quite interested if this has the same pattern everywhere.
    - jemfinch 15y ago
      Here's what I get: Input array size is 1024 Naive sqrtf() CPU cycles used: 54514, error: 0.000000 Vectorized SSE CPU cycles used: 900, error: inf Marvelous CPU cycles used: 21514, error: inf I'm not sure how to interpret the errors. I had to make a few changes myself for this to compile on my machine.
- liamkf 15y ago
  Hmm, that seems a bit misleading. The SSE implementation will of course be much faster than a non-vectorized implementation... it's working on 4 floats at a time. A vectorized version of the marvelous method would be a fairer comparison. If your data is not very vectorizable and you don't need high precision, it's still fairly marvelous.
  - onan_barbarian 15y ago

deleted 15y ago

[deleted]

Arjuna 15y ago

Check out "Graphics Programming Black Book" [1] by Michael Abrash [2]. If you have not read his work, you are in for a treat. He has a wonderful writing style that is both engaging and illuminating. There are a number of chapters [3] in the book that specifically discuss technology and development related to Quake. [1] PDF: http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/graphics-programming-black-book-r1698 http://www.gamedev.net/page/resources/_/technical/graphics-p... [2] http://en.wikipedia.org/wiki/Michael_Abrash http://en.wikipedia.org/wiki/Michael_Abrash [3] Chapter 64 - Quake's Visible-Surface Determination Chapter 66 - Quake's Hidden-Surface Removal Chapter 67 - Sorted Spans in Action Chapter 68 - Quake's Lighting Model Chapter 69 - Surface Caching and Quake's Triangle Models Chapter 70 - Quake: A Post-Mortem and a Glimpse into the Future