6 ms·

It's very easy to do FMA's using .mul_add() on floats in Rust, which the author didn't seem to know about.

by dhruvdh 7y ago

magicalhippo 7y ago
Ideally the compiler should be able to do this by itself though, at least with the appropriate flag to enable it.
- jacobolus 7y ago
  If you’re doing fiddly numerical work, this must definitely be optional, as swapping separate multiplication and addition for FMA (or vice versa) can compromise correctness. In some cases you need two different algorithms if FMA is present or absent.
  - fluffything 7y ago
    Do you have concrete examples of such algorithms?
    - jacobolus 7y ago
      Some algorithms guarantee that some arithmetic operation(s) applied to 2+ floating point inputs will result in a list of floating point outputs which when summed have exactly the correct result. This gets all screwed up if you mess with the order of operations or the rounding of intermediate results. e.g. https://www.cs.cmu.edu/~quake/robust.html https://www.cs.cmu.edu/~quake/robust.html Some keywords to look for: “compensated arithmetic”, “error-free transformations”. FMAs generally speed up these tools, but you need to be careful and deliberate about how they are used. (Disclaimer: I am not an expert on this, just some guy on the internet.)
      - fluffything 7y ago
        Fair, I think it would be very helpful for Rust if some expert actually knows of a specific example for which this is the case. I think there is an RFC about enabling floating-point contraction by default, that would "silently" be able to do some of these transformations depending on the optimization level.
        nestorD 7y ago
        The one very important thing that often get destroyed by compiler using associativity is the TwoSum Error free transform which is a vital composant of several algorithms that deal with numerical error (most notably the Kahan Summation). The problem is mentionned in the Wikipedia page of the Kahan summation (and I have been able to reproduce it with gcc) : https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Possible_invalidation_by_compiler_optimization https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Poss... This is actually my area of research, I could contribute if you point me to an RFC.
        fluffything 7y ago
        I think the key issue with the optimizations that ICC is performing for C++ but Rust is not doing in this case is just FP-contraction, which is related to, but not the same as, assuming associativity. The RFC about that is https://github.com/rust-lang/rfcs/pull/2686 https://github.com/rust-lang/rfcs/pull/2686 , where you see users kind of split into the "I want faster binaries" and "I want more deterministic execution" camps. Neither are wrong TBH. Some people have tried to show there that enabling FP-contraction by default isn't always better / more precise, but I'm not sure if they succeeded.
        tom_mellior 7y ago
        > I think the key issue with the optimizations that ICC is performing for C++ but Rust is not doing in this case is just FP-contraction, which is related to, but not the same as, assuming associativity. I think associativity is necessary to vectorize reduction operations like: r+=(c[i]-a[i]*b[i])*a[i]*(c[i]-a[i]*b[i]); I haven't looked at the code generated by ICC, but I would expect it to vectorize this by computing tuples of "partial sums", roughly as follows: r0 += (c[i+0]-a[i+0]*b[i+0])*a[i+0]*(c[i+0]-a[i+0]*b[i+0]); r1 += (c[i+1]-a[i+1]*b[i+1])*a[i+1]*(c[i+1]-a[i+1]*b[i+1]); r2 += (c[i+2]-a[i+2]*b[i+2])*a[i+2]*(c[i+2]-a[i+2]*b[i+2]); ... and then doing a horizontal sum r = r0 + r1 + r2 + ... in the end. But this requires associativity. (And commutativity, but that's a given.)
- paulddraper 7y ago
  FMA isn't a safe optimization as it can give different results. C++ compilers have flags to enable it globally. gcc and clang include the optimization in -Ofast. Rust allows you to choose at a code level (but usually people don't know about it). Perhaps it should also have a global fast-math flag that would automatically optimize it. Pros and cons to that.
  - magicalhippo 7y ago
    I wasn't trying to imply it should be on by default. Often one does not care about the lower bits of the floats, but do want the speed. For some tasks it's very much the opposite. Being able to specify a global option with local override is a great combo.
    - mratsim 7y ago
      FMA is not always faster, it has a high latency: 5-6 cycles depending on the CPU while Add and MUL have very low-latency. This means that to fully utilizes FMA you need to unroll a loop more. Sometimes yyou just can't, and the other time you use more instructions, use more cache. In short it's not always better. Also as other said, FMA has better accuracy than separate Add + Mul
  - nwallin 7y ago
    FMA is "safe" in that if it breaks your code, it was already broken. It can only make the results slightly more accurate, unlike for instance the rsqrt instruction which is less accurate. (and as such is not a safe optimization) GCC emits FMA instructions at -O2 without -ffast-math.
    - lilyball 7y ago
      Well, it could "break" your code in that it might make your code produce different results than a separate equivalent implementation that didn't use FMA. Edit: Ok actually it sounds like it could literally break some algorithms, see https://news.ycombinator.com/item?id=21342974 https://news.ycombinator.com/item?id=21342974
ibotty 7y ago
Care to rewrite the program with `.mul_add()`?
- lovasoa 7y ago
  I did rewrite the code with mul_add, and didn't see any significant performance improvement. See my comment above.
  - ibotty 7y ago
    very appreciated! Thank you.

It's very easy to do FMA's using .mul_add() on floats in Rust, which the author didn't seem to know about.

magicalhippo 7y ago

Ideally the compiler should be able to do this by itself though, at least with the appropriate flag to enable it.

jacobolus 7y ago
If you’re doing fiddly numerical work, this must definitely be optional, as swapping separate multiplication and addition for FMA (or vice versa) can compromise correctness. In some cases you need two different algorithms if FMA is present or absent.
- fluffything 7y ago
  Do you have concrete examples of such algorithms?
  - jacobolus 7y ago
    Some algorithms guarantee that some arithmetic operation(s) applied to 2+ floating point inputs will result in a list of floating point outputs which when summed have exactly the correct result. This gets all screwed up if you mess with the order of operations or the rounding of intermediate results. e.g. https://www.cs.cmu.edu/~quake/robust.html https://www.cs.cmu.edu/~quake/robust.html Some keywords to look for: “compensated arithmetic”, “error-free transformations”. FMAs generally speed up these tools, but you need to be careful and deliberate about how they are used. (Disclaimer: I am not an expert on this, just some guy on the internet.)
    - fluffything 7y ago
      Fair, I think it would be very helpful for Rust if some expert actually knows of a specific example for which this is the case. I think there is an RFC about enabling floating-point contraction by default, that would "silently" be able to do some of these transformations depending on the optimization level.
      - nestorD 7y ago
        The one very important thing that often get destroyed by compiler using associativity is the TwoSum Error free transform which is a vital composant of several algorithms that deal with numerical error (most notably the Kahan Summation). The problem is mentionned in the Wikipedia page of the Kahan summation (and I have been able to reproduce it with gcc) : https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Possible_invalidation_by_compiler_optimization https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Poss... This is actually my area of research, I could contribute if you point me to an RFC.
        fluffything 7y ago
        I think the key issue with the optimizations that ICC is performing for C++ but Rust is not doing in this case is just FP-contraction, which is related to, but not the same as, assuming associativity. The RFC about that is https://github.com/rust-lang/rfcs/pull/2686 https://github.com/rust-lang/rfcs/pull/2686 , where you see users kind of split into the "I want faster binaries" and "I want more deterministic execution" camps. Neither are wrong TBH. Some people have tried to show there that enabling FP-contraction by default isn't always better / more precise, but I'm not sure if they succeeded.
        tom_mellior 7y ago
        > I think the key issue with the optimizations that ICC is performing for C++ but Rust is not doing in this case is just FP-contraction, which is related to, but not the same as, assuming associativity. I think associativity is necessary to vectorize reduction operations like: r+=(c[i]-a[i]*b[i])*a[i]*(c[i]-a[i]*b[i]); I haven't looked at the code generated by ICC, but I would expect it to vectorize this by computing tuples of "partial sums", roughly as follows: r0 += (c[i+0]-a[i+0]*b[i+0])*a[i+0]*(c[i+0]-a[i+0]*b[i+0]); r1 += (c[i+1]-a[i+1]*b[i+1])*a[i+1]*(c[i+1]-a[i+1]*b[i+1]); r2 += (c[i+2]-a[i+2]*b[i+2])*a[i+2]*(c[i+2]-a[i+2]*b[i+2]); ... and then doing a horizontal sum r = r0 + r1 + r2 + ... in the end. But this requires associativity. (And commutativity, but that's a given.)
paulddraper 7y ago
FMA isn't a safe optimization as it can give different results. C++ compilers have flags to enable it globally. gcc and clang include the optimization in -Ofast. Rust allows you to choose at a code level (but usually people don't know about it). Perhaps it should also have a global fast-math flag that would automatically optimize it. Pros and cons to that.
- magicalhippo 7y ago
  I wasn't trying to imply it should be on by default. Often one does not care about the lower bits of the floats, but do want the speed. For some tasks it's very much the opposite. Being able to specify a global option with local override is a great combo.
  - mratsim 7y ago
    FMA is not always faster, it has a high latency: 5-6 cycles depending on the CPU while Add and MUL have very low-latency. This means that to fully utilizes FMA you need to unroll a loop more. Sometimes yyou just can't, and the other time you use more instructions, use more cache. In short it's not always better. Also as other said, FMA has better accuracy than separate Add + Mul
- nwallin 7y ago
  FMA is "safe" in that if it breaks your code, it was already broken. It can only make the results slightly more accurate, unlike for instance the rsqrt instruction which is less accurate. (and as such is not a safe optimization) GCC emits FMA instructions at -O2 without -ffast-math.
  - lilyball 7y ago
    Well, it could "break" your code in that it might make your code produce different results than a separate equivalent implementation that didn't use FMA. Edit: Ok actually it sounds like it could literally break some algorithms, see https://news.ycombinator.com/item?id=21342974 https://news.ycombinator.com/item?id=21342974

ibotty 7y ago

Care to rewrite the program with `.mul_add()`?

lovasoa 7y ago
I did rewrite the code with mul_add, and didn't see any significant performance improvement. See my comment above.
- ibotty 7y ago
  very appreciated! Thank you.