9 ms·

Matrix inversion requires taking the reciprocal of a determinant. I don't have the D3D binary to disassemble it, but chances are that they used the RCPSS/RCPPS

Matrix inversion requires taking the reciprocal of a determinant. I don't have the D3D binary to disassemble it, but chances are that they used the RCPSS/RCPPS instructions to get an approximate reciprocal. The precision of the approximation is specified. Both Intel and AMD satisfy the specification, but with different results.

ajross 6y ago
That seems likely. Per the SDM the required precision is to within 1.5*2^-12, which is quite low and allows a lot of slop in the implementation. One possibility is that there's an accidental equality test on the path of a runtime (AMD) value vs. a value that is computed at compile time (presumably on an Intel CPU).
withinrafael 6y ago
Yep, RCPSS is present in d3dx9_31!intelsse2_D3DXMatrixInverse.
graycat 6y ago
deleted
- wtallis 6y ago
  I think you've lost sight of the fact that this entire discussion is constrained to the 4x4 matrices used in computer graphics. How to best invert a matrix of a particular small fixed size is a very different question from how to best invert matrices in general.
  - graycat 6y ago
    deleted
    - TJSomething 6y ago
      While true, there is a reason that the GLSL standard includes builtin data types for matnxm for all n,m in {2, 3, 4}. The single most common matrix operations in computer graphics are related to linear transforms on color spaces and geometry. Both of those max out at transforms on 4D vectors, for RGBA and 3D projective geometry.
nwallin 6y ago
In case anyone is wondering why RCP[PS]S and RSQRT[PS]S are specified to give only a relatively small number of digits of accuracy (I think only 7 or 14 bits?) it's because they use the fast inverse square root algorithm in hardware. The IEEE754 floating point representation gives you an easy way to roughly approximately convert between the log2 of it. The exponent gives you exactly the integer log2 of the number, and the mantissa gives you a fractional linear term that you can drop onto the integer part to make it closer to the actual log2 version. This lets you do some fun things fairly easily. x -> log2(x) -> -log2(x) -> 1/x x -> log2(x) -> -0.5 log2(x) -> 1/sqrt(x) x -> log2(x) -> 0.5 log2(x) -> sqrt(x) The lossiness of the conversion limits your precision, but there's a lot of times you don't give a shit. So the instructions are still valuable even if they're only approximately correct. For the reciprocal case, it will do something like this: https://godbolt.org/z/n6M4az https://godbolt.org/z/n6M4az I'm not sure where the nondeterminism comes in between AMD and Intel. As you can see, with the reciprocal, there's no magic constant like there is with inverse square root. Maybe they're fudging something, or have a different form of Newton's method, I dunno.
- cwzwarich 6y ago
  Approximations implemented in HW generally use different techniques than ones in SW. They typically start with a lookup table, possibly followed by some other steps. Someone reverse-engineered the old AMD 3DNow implementations here: https://pdf.sciencedirectassets.com/272990/1-s2.0-S1571066100X03003/1-s2.0-S1571066105806218/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEGQaCXVzLWVhc3QtMSJGMEQCICwKfD203SBZBd3fqRnYqbvYvw8mwpNvZWIaihKpJg3qAiBopfL0aXKGeOX%2BTTw5oDhX%2B%2B98Njksg6lttBMw98R6mCq0AwgdEAMaDDA1OTAwMzU0Njg2NSIM5hU7%2BSTHKQxhZN5TKpEDqGg7MWVWrPw%2FBVTkSSlxcfuhmQIbX9N8fnBomJuZ9dJ7aJCV7LmzlNNZ0ayrnsg761EoixuLdvrLl13pspAplqkH9U0p1Lto0hnmF23WddSVmZ9thKi9AB7ZFfFCm7Osz2nvxlMRjTY5LH%2BUd02U%2BYZ%2BwGv5jnnEMj8E9JKXE3qiHPNB%2FgZxxnrKRwKx3wPyKAymhQSrJ8XL8sGuKWJZiPfg4yw6ViH8kO2S9EQ4LiIgYS5eGg7NYtLQ9dhXd%2FDJdIRPaeWK2olhGAe4O7TaEbmJuWicCwahC64JE25AAT0Os821%2BDWPmymc79d2ei%2FNIpqGDrZHIF9Q04M2Ahf9DQ1fTy6MIpnWF4Rt1nD9rMgMhE3xOs6flHjMwzQ%2B%2BsGFTeArH0py0wPGho%2FJBTZp%2BKaNyYYnJbBMJJeRznS%2FTiTO6rajfnFqKTwDK7CfQCIF62inyFI1s6yzNrXeLpmdev6WAoIcsDRLMVF7Illf0R3xbQfiEqRGtn2NAIc8501ng9yrF%2FpEwTBmEQ7oaTAZPWkwqL3S%2BAU67AFZoeB6%2FHWd0vd1Bx2f%2Bh1ozD8U7bOwRb%2FFWAxW%2BkkbEgX%2FK5QlECQkupMCwF1jL3%2FAh4xBMs8l5ISVlI4kxpBt%2Bsqdjjg1ZMawXNHfe2CvxuPy4nhHsH1SIksHS09%2FfVRTHIL57H%2BFceUo%2F7xj%2FY%2F0M2frY4LL2%2FxO3yvHvysF%2F5IrwBc14kh2LwhgDOdqfb8l2sBLO3PFJDirphrY58L2gf6VZwP%2FOwxImTe65HzELe4XJFzPzK8LPCd1qkVTm6wjLFypvUTS3N16Nwo%2BEqlIyeRP7%2Fvu%2BELhlatpuTPisgY%2BOL%2FKCPdD%2BaFQrw%3D%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20200719T202425Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTY6VANJVM7%2F20200719%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=878e5ec642f7bda638a00e15a0a5bb8edb7ea41580697f1751e3596ae83b4a3f&hash=6b98019b6d605be41d6c28452c549493cbc5a9595cbd2bb81f908dfae7b8578b&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S1571066105806218&tid=spdf-2c223970-dd92-45f5-b165-285a4ceaff1a&sid=9261bf9637b9864ec838be27274d35b43cabgxrqa&type=client https://pdf.sciencedirectassets.com/272990/1-s2.0-S157106610...
Const-me 6y ago
Here’s Intel versus AMD relative error of RCPPS instruction: http://const.me/tmp/vrcpps-errors-chart.png http://const.me/tmp/vrcpps-errors-chart.png AMD is Ryzen 5 3600, Intel is Core i3 6157U. Over the complete range of floats, AMD is more precise on average, 0.000078 versus 0.000095 relative error. However, Intel has 0.000300 maximum relative error, AMD 0.000315. Both are well within the spec. The documentation says “maximum relative error for this approximation is less than 1.5*2^-12”, in human language that would be 3.6621E-4. Source code that compares them by creating 16GB binary files with the complete range of floats: https://gist.github.com/Const-me/a6d36f70a3a77de00c61cf4f6c17c7ac https://gist.github.com/Const-me/a6d36f70a3a77de00c61cf4f6c1...
- dvt 6y ago
  This is great (I was actually just toying with the _mm_rcp_ss intrinsic)! It would also indicate that RCPSS is not the culprit.
  - Const-me 6y ago
    > It would also indicate that RCPSS is not the culprit. I’m not sure about that. I think it might be. Despite both are within specs, the results are numerically different. Modern DirectXMath doesn‘t use these approximated instruction for inverting matrices, it’s open source, there: https://github.com/microsoft/DirectXMath/blob/83634c742a85d1027765af53fbe79506fd72e0c3/Inc/DirectXMathMatrix.inl#L983 https://github.com/microsoft/DirectXMath/blob/83634c742a85d1...
    - dvt 6y ago
      > Despite both are within specs, the results are numerically different. True, but it's quite common that floating point ops throwaway bits (i.e. beyond the epsilon) will be numerically different between vendors. > Modern DirectXMath doesn‘t use these approximated instruction for inverting matrices, it’s open source, there: https://github.com/microsoft/DirectXMath/blob/83634c742a85d1.. https://github.com/microsoft/DirectXMath/blob/83634c742a85d1.... Good find, neither does Wine, actually: https://doxygen.reactos.org/dc/dd8/d3dx9math_8h.html#a3870c69a57318daf46180e01c9c20594 https://doxygen.reactos.org/dc/dd8/d3dx9math_8h.html#a3870c6... Would be interesting to see if this bug also happens on Linux.

ajross 6y ago

That seems likely. Per the SDM the required precision is to within 1.5*2^-12, which is quite low and allows a lot of slop in the implementation. One possibility is that there's an accidental equality test on the path of a runtime (AMD) value vs. a value that is computed at compile time (presumably on an Intel CPU).

withinrafael 6y ago

Yep, RCPSS is present in d3dx9_31!intelsse2_D3DXMatrixInverse.

graycat 6y ago

deleted

wtallis 6y ago
I think you've lost sight of the fact that this entire discussion is constrained to the 4x4 matrices used in computer graphics. How to best invert a matrix of a particular small fixed size is a very different question from how to best invert matrices in general.
- graycat 6y ago
  deleted
  - TJSomething 6y ago
    While true, there is a reason that the GLSL standard includes builtin data types for matnxm for all n,m in {2, 3, 4}. The single most common matrix operations in computer graphics are related to linear transforms on color spaces and geometry. Both of those max out at transforms on 4D vectors, for RGBA and 3D projective geometry.

nwallin 6y ago

In case anyone is wondering why RCP[PS]S and RSQRT[PS]S are specified to give only a relatively small number of digits of accuracy (I think only 7 or 14 bits?) it's because they use the fast inverse square root algorithm in hardware. The IEEE754 floating point representation gives you an easy way to roughly approximately convert between the log2 of it. The exponent gives you exactly the integer log2 of the number, and the mantissa gives you a fractional linear term that you can drop onto the integer part to make it closer to the actual log2 version. This lets you do some fun things fairly easily. x -> log2(x) -> -log2(x) -> 1/x x -> log2(x) -> -0.5 log2(x) -> 1/sqrt(x) x -> log2(x) -> 0.5 log2(x) -> sqrt(x) The lossiness of the conversion limits your precision, but there's a lot of times you don't give a shit. So the instructions are still valuable even if they're only approximately correct. For the reciprocal case, it will do something like this: https://godbolt.org/z/n6M4az https://godbolt.org/z/n6M4az I'm not sure where the nondeterminism comes in between AMD and Intel. As you can see, with the reciprocal, there's no magic constant like there is with inverse square root. Maybe they're fudging something, or have a different form of Newton's method, I dunno.

cwzwarich 6y ago
Approximations implemented in HW generally use different techniques than ones in SW. They typically start with a lookup table, possibly followed by some other steps. Someone reverse-engineered the old AMD 3DNow implementations here: https://pdf.sciencedirectassets.com/272990/1-s2.0-S1571066100X03003/1-s2.0-S1571066105806218/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEGQaCXVzLWVhc3QtMSJGMEQCICwKfD203SBZBd3fqRnYqbvYvw8mwpNvZWIaihKpJg3qAiBopfL0aXKGeOX%2BTTw5oDhX%2B%2B98Njksg6lttBMw98R6mCq0AwgdEAMaDDA1OTAwMzU0Njg2NSIM5hU7%2BSTHKQxhZN5TKpEDqGg7MWVWrPw%2FBVTkSSlxcfuhmQIbX9N8fnBomJuZ9dJ7aJCV7LmzlNNZ0ayrnsg761EoixuLdvrLl13pspAplqkH9U0p1Lto0hnmF23WddSVmZ9thKi9AB7ZFfFCm7Osz2nvxlMRjTY5LH%2BUd02U%2BYZ%2BwGv5jnnEMj8E9JKXE3qiHPNB%2FgZxxnrKRwKx3wPyKAymhQSrJ8XL8sGuKWJZiPfg4yw6ViH8kO2S9EQ4LiIgYS5eGg7NYtLQ9dhXd%2FDJdIRPaeWK2olhGAe4O7TaEbmJuWicCwahC64JE25AAT0Os821%2BDWPmymc79d2ei%2FNIpqGDrZHIF9Q04M2Ahf9DQ1fTy6MIpnWF4Rt1nD9rMgMhE3xOs6flHjMwzQ%2B%2BsGFTeArH0py0wPGho%2FJBTZp%2BKaNyYYnJbBMJJeRznS%2FTiTO6rajfnFqKTwDK7CfQCIF62inyFI1s6yzNrXeLpmdev6WAoIcsDRLMVF7Illf0R3xbQfiEqRGtn2NAIc8501ng9yrF%2FpEwTBmEQ7oaTAZPWkwqL3S%2BAU67AFZoeB6%2FHWd0vd1Bx2f%2Bh1ozD8U7bOwRb%2FFWAxW%2BkkbEgX%2FK5QlECQkupMCwF1jL3%2FAh4xBMs8l5ISVlI4kxpBt%2Bsqdjjg1ZMawXNHfe2CvxuPy4nhHsH1SIksHS09%2FfVRTHIL57H%2BFceUo%2F7xj%2FY%2F0M2frY4LL2%2FxO3yvHvysF%2F5IrwBc14kh2LwhgDOdqfb8l2sBLO3PFJDirphrY58L2gf6VZwP%2FOwxImTe65HzELe4XJFzPzK8LPCd1qkVTm6wjLFypvUTS3N16Nwo%2BEqlIyeRP7%2Fvu%2BELhlatpuTPisgY%2BOL%2FKCPdD%2BaFQrw%3D%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20200719T202425Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTY6VANJVM7%2F20200719%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=878e5ec642f7bda638a00e15a0a5bb8edb7ea41580697f1751e3596ae83b4a3f&hash=6b98019b6d605be41d6c28452c549493cbc5a9595cbd2bb81f908dfae7b8578b&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S1571066105806218&tid=spdf-2c223970-dd92-45f5-b165-285a4ceaff1a&sid=9261bf9637b9864ec838be27274d35b43cabgxrqa&type=client https://pdf.sciencedirectassets.com/272990/1-s2.0-S157106610...

Const-me 6y ago

Here’s Intel versus AMD relative error of RCPPS instruction: http://const.me/tmp/vrcpps-errors-chart.png http://const.me/tmp/vrcpps-errors-chart.png AMD is Ryzen 5 3600, Intel is Core i3 6157U. Over the complete range of floats, AMD is more precise on average, 0.000078 versus 0.000095 relative error. However, Intel has 0.000300 maximum relative error, AMD 0.000315. Both are well within the spec. The documentation says “maximum relative error for this approximation is less than 1.5*2^-12”, in human language that would be 3.6621E-4. Source code that compares them by creating 16GB binary files with the complete range of floats: https://gist.github.com/Const-me/a6d36f70a3a77de00c61cf4f6c17c7ac https://gist.github.com/Const-me/a6d36f70a3a77de00c61cf4f6c1...

dvt 6y ago
This is great (I was actually just toying with the _mm_rcp_ss intrinsic)! It would also indicate that RCPSS is not the culprit.
- Const-me 6y ago
  > It would also indicate that RCPSS is not the culprit. I’m not sure about that. I think it might be. Despite both are within specs, the results are numerically different. Modern DirectXMath doesn‘t use these approximated instruction for inverting matrices, it’s open source, there: https://github.com/microsoft/DirectXMath/blob/83634c742a85d1027765af53fbe79506fd72e0c3/Inc/DirectXMathMatrix.inl#L983 https://github.com/microsoft/DirectXMath/blob/83634c742a85d1...
  - dvt 6y ago
    > Despite both are within specs, the results are numerically different. True, but it's quite common that floating point ops throwaway bits (i.e. beyond the epsilon) will be numerically different between vendors. > Modern DirectXMath doesn‘t use these approximated instruction for inverting matrices, it’s open source, there: https://github.com/microsoft/DirectXMath/blob/83634c742a85d1.. https://github.com/microsoft/DirectXMath/blob/83634c742a85d1.... Good find, neither does Wine, actually: https://doxygen.reactos.org/dc/dd8/d3dx9math_8h.html#a3870c69a57318daf46180e01c9c20594 https://doxygen.reactos.org/dc/dd8/d3dx9math_8h.html#a3870c6... Would be interesting to see if this bug also happens on Linux.