6 ms·

NSan: a floating-point numerical sanitizer

86 points by Katydid 6y ago

ggm 6y ago
I basically failed the numerical analysis part of my CS degree forty years ago so forgive me if I misunderstand. The abstract implies by holding and calculating a shadow higher precision version of the fp value the nsan logic can detect faults in code. The specific faults we were taught about back then, would seem to be accumulated, loop embedded rounding error. Is there some other calls of merit it can handle? I took (40 years ago) a message that precision and repetition went hand in hand in this problem. I could see that eg incorrect precision handling across function call boundaries could promote ints to speciously accurate floats maybe, but that's a trivially detected type problem surely? Not saying this isn't good work. Seeking clue about its scale and applicability.
- kevingadd 6y ago
  One real-world example: All the textbook algorithms for triangulation by ear-clipping (i.e. turning a convex shape into a bunch of triangles) are broken if executed using IEEE floats, some formulations of them are worse than others. Typically they loop forever. If you take an implementation that appears to work on x86 and compile it for powerpc, it might break. In general you can be taking textbook accurate math based on rock solid proofs and then when you turn it into code it's busted, so nsan seems like it could be really valuable for flushing out some of those problems.
  - ggm 6y ago
    I honestly thought the numerical algorithm group NAG library had fixed this three decades ago. I'm not being sarcastic, I thought the numerical analysis libraries tested the living bejesus out of their code. I guess a lot more intensive FP code exists now, outside of highly tested library code, or calls made from the calls, or whatever.
    - yablak 6y ago
      You'd be surprised how many of the old, painstakingly tested fp algorithms, have been reimplemented in DL frameworks. I ported many algorithms from cephes to Eigen for use in TensorFlow. Some I was able to make simd. Then the XLA folks reimplemented some in HLO using other approximations that are easier to parallelize. Then consider that some linear algebra and simple functions like softmax and softplus have to be implemented for fast execution in float16 and bfloat16 supporting hardware. You can iterate over the entire fp16 space quite quickly but the initial version isn't usually so thoroughly tested.. performance is king anyway in NNs. Then a couple months later someone ports an old model to V100 and it turns out your softplus underflows. Guess how many weeks it takes to figure out why your model quality went to s**?
      - ggm 6y ago
        I sat next to the NAG maintenance crew at lunch sometimes, back in the 80s in Leeds university who held a contract (I think it moved around, possibly by design). They were fierce, collectivist correctness freaks. Outside code was reviewed mercilessly. Nothing anyone said about their experiences coding mattered as much as what they did to that library. If they stuffed it up, bridges fell down during construction or rockets blew up, and they knew it. I remain in awe. All those jokes about real programmers are wrong. Real programmers take great care.
    - kevingadd 6y ago
      I'm sure those libraries are good, you just tend not to encounter stuff like that in programs written casually or by people who think performance really matters. Most people doing triangulation by ear clipping are trying to rasterize shapes. In the past, cairo (the 2d graphics library) had a bug that would cause crashes/hangs in Firefox because a VPN driver was changing the floating point state on random threads... which would cause one of those geometric algorithms to break.
      - gpderetta 6y ago
        That must have been extremely painful to debug. Let me guess, on Windows it was resetting the x87 fpu precision from 64 bits to 80?
- hansvm 6y ago
  As one example, FP is prone to a huge loss of precision from subtraction. Let X be huge and E be tiny, then (X+E)-X could be nowhere near E. Linear algebra routines usually have a severe trade-off between speed and accounting for those sorts of errors (such accounting is usually implemented as some kind of search for the best order to do a set of operations), when they can even be handled. If your inputs are nice enough (which is often the case) then it could very well be that none of the above matters and you can go full speed ahead with the fastest and most error prone solutions, but feasibly I could see something like this allowing you to detect early on which snippets might need extra attention due to the nature of typical inputs in those locations.
- deleted 6y ago
  [deleted]
- sn41 6y ago
  As pointed out by others, subtraction is very sensitive. The following are also important examples. 1. The problem of small denominators. This is analogous to the subtraction issue, but it was observed and well-studied in the 19th century itself, in the context of celestial mechanics. It is fundamentally difficult to implement these numerically [1]. 2. Whenever there are algorithms which depend on a "discontinuous" choice of a pivot in order to proceed, numerical instability may follow. This is why Gaussian elimination and Gram-Schmidt orthonormalization are numerically unstable, and other algorithms like Householder transformation are preferred instead [2]. A very detailed reference on stability issues is the book by Higham [3]. Some of these are floating point issues. [1] http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=6441&option_lang=eng http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm... [2] https://en.wikipedia.org/wiki/Householder_transformation https://en.wikipedia.org/wiki/Householder_transformation [3] https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobileUi=0& https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobi...
- nestorD 6y ago
  I am not familiar with NSan but other shadow value implementations will keep a higher precision copy of the numbers and follow them in the computation. They detect local errors but also take propagation (amplification and dampening of error) into account to evaluate the numerical accuracy of the final result.
lrossi 6y ago
Is there a pdf available or just the abstract?
- remexre 6y ago
  Bizarrely, using institutional access gives me [0]... EDIT: Though it does note that it is for publication in March, so it might not be intended to be generally available yet. [0]: https://cdn.remexre.xyz/screenshots/842f6f91029e6d956cb287d65cc32693b1385141.png https://cdn.remexre.xyz/screenshots/842f6f91029e6d956cb287d6...
  - saagarjha 6y ago
    Perhaps you weren’t in the sudoers file.
- viraptor 6y ago
  > March 2021 I don't think the journal is actually published yet.
  - lrossi 6y ago
    Makes sense now, thanks.
lstamour 6y ago
See also: https://conf.researchr.org/details/CC-2021/cc-research-papers/7/NSan-A-Floating-Point-Numerical-Sanitizer https://conf.researchr.org/details/CC-2021/cc-research-paper...
nestorD 6y ago
I am not familiar with NSan (and impatient to read the paper) but a common problem with tools based on higher precision shadow values is that they can be easily defeated by a large cancelation (`(1e200 + 1) - 1e200` will return 0 in both 64 and 200 bits arithmteic). My solution to this problem (which also has performance benefits) is to use an error-free transform based arithmetic (they give you roughly doubled precision but are also very resilient to cancelation). See Shaman [0] for a C++ reference implementation, you can change your types and it will display only the significant digits of your results. If you want something that does not require modifying your source code, I would recommend Verrou [1], a Valgrind-based tool using stochastic arithmetic. For those interested in the subject, my PhD [1] (which is written in English despite the French title) gives further information on all those methods, their pros and cons. [0]: https://gitlab.com/numerical_shaman/shaman https://gitlab.com/numerical_shaman/shaman [1]: https://github.com/edf-hpc/verrou https://github.com/edf-hpc/verrou [2]: https://tel.archives-ouvertes.fr/tel-03116750 https://tel.archives-ouvertes.fr/tel-03116750
- nestorD 6y ago
  People here might also be interested in the Julia implementation of Shaman: https://gitlab.com/numerical_shaman/shaman_julia https://gitlab.com/numerical_shaman/shaman_julia
- Lemmih 6y ago
  Loved your thesis. Will implement it in Haskell for use in hgeometry (https://hgeometry.org https://hgeometry.org).
  - nestorD 6y ago
    Great! Don't hesitate to contact me if you have any question or roadblock. I would be happy to give a link to your implementation in the readme of the C++ reference implementation.
    - Lemmih 6y ago
      No roadblocks but I did find something I didn't expect. Turns out that 'sinl(pi)' differs on Linux and macosx. I'm getting error-bounds that are slightly different. Here's the PR for my Haskell implementation: https://github.com/noinia/hgeometry/pull/120 https://github.com/noinia/hgeometry/pull/120 Here's the documentation: https://noinia.github.io/hgeometry/doc/hgeometry-combinatorial-0.11.0.0/Data-Double-Shaman.html https://noinia.github.io/hgeometry/doc/hgeometry-combinatori...

86 points by Katydid 6y ago

ggm 6y ago

I basically failed the numerical analysis part of my CS degree forty years ago so forgive me if I misunderstand. The abstract implies by holding and calculating a shadow higher precision version of the fp value the nsan logic can detect faults in code. The specific faults we were taught about back then, would seem to be accumulated, loop embedded rounding error. Is there some other calls of merit it can handle? I took (40 years ago) a message that precision and repetition went hand in hand in this problem. I could see that eg incorrect precision handling across function call boundaries could promote ints to speciously accurate floats maybe, but that's a trivially detected type problem surely? Not saying this isn't good work. Seeking clue about its scale and applicability.

kevingadd 6y ago
One real-world example: All the textbook algorithms for triangulation by ear-clipping (i.e. turning a convex shape into a bunch of triangles) are broken if executed using IEEE floats, some formulations of them are worse than others. Typically they loop forever. If you take an implementation that appears to work on x86 and compile it for powerpc, it might break. In general you can be taking textbook accurate math based on rock solid proofs and then when you turn it into code it's busted, so nsan seems like it could be really valuable for flushing out some of those problems.
- ggm 6y ago
  I honestly thought the numerical algorithm group NAG library had fixed this three decades ago. I'm not being sarcastic, I thought the numerical analysis libraries tested the living bejesus out of their code. I guess a lot more intensive FP code exists now, outside of highly tested library code, or calls made from the calls, or whatever.
  - yablak 6y ago
    You'd be surprised how many of the old, painstakingly tested fp algorithms, have been reimplemented in DL frameworks. I ported many algorithms from cephes to Eigen for use in TensorFlow. Some I was able to make simd. Then the XLA folks reimplemented some in HLO using other approximations that are easier to parallelize. Then consider that some linear algebra and simple functions like softmax and softplus have to be implemented for fast execution in float16 and bfloat16 supporting hardware. You can iterate over the entire fp16 space quite quickly but the initial version isn't usually so thoroughly tested.. performance is king anyway in NNs. Then a couple months later someone ports an old model to V100 and it turns out your softplus underflows. Guess how many weeks it takes to figure out why your model quality went to s**?
    - ggm 6y ago
      I sat next to the NAG maintenance crew at lunch sometimes, back in the 80s in Leeds university who held a contract (I think it moved around, possibly by design). They were fierce, collectivist correctness freaks. Outside code was reviewed mercilessly. Nothing anyone said about their experiences coding mattered as much as what they did to that library. If they stuffed it up, bridges fell down during construction or rockets blew up, and they knew it. I remain in awe. All those jokes about real programmers are wrong. Real programmers take great care.
  - kevingadd 6y ago
    I'm sure those libraries are good, you just tend not to encounter stuff like that in programs written casually or by people who think performance really matters. Most people doing triangulation by ear clipping are trying to rasterize shapes. In the past, cairo (the 2d graphics library) had a bug that would cause crashes/hangs in Firefox because a VPN driver was changing the floating point state on random threads... which would cause one of those geometric algorithms to break.
    - gpderetta 6y ago
      That must have been extremely painful to debug. Let me guess, on Windows it was resetting the x87 fpu precision from 64 bits to 80?
hansvm 6y ago
As one example, FP is prone to a huge loss of precision from subtraction. Let X be huge and E be tiny, then (X+E)-X could be nowhere near E. Linear algebra routines usually have a severe trade-off between speed and accounting for those sorts of errors (such accounting is usually implemented as some kind of search for the best order to do a set of operations), when they can even be handled. If your inputs are nice enough (which is often the case) then it could very well be that none of the above matters and you can go full speed ahead with the fastest and most error prone solutions, but feasibly I could see something like this allowing you to detect early on which snippets might need extra attention due to the nature of typical inputs in those locations.
deleted 6y ago
[deleted]
sn41 6y ago
As pointed out by others, subtraction is very sensitive. The following are also important examples. 1. The problem of small denominators. This is analogous to the subtraction issue, but it was observed and well-studied in the 19th century itself, in the context of celestial mechanics. It is fundamentally difficult to implement these numerically [1]. 2. Whenever there are algorithms which depend on a "discontinuous" choice of a pivot in order to proceed, numerical instability may follow. This is why Gaussian elimination and Gram-Schmidt orthonormalization are numerically unstable, and other algorithms like Householder transformation are preferred instead [2]. A very detailed reference on stability issues is the book by Higham [3]. Some of these are floating point issues. [1] http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=6441&option_lang=eng http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm... [2] https://en.wikipedia.org/wiki/Householder_transformation https://en.wikipedia.org/wiki/Householder_transformation [3] https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobileUi=0& https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobi...
nestorD 6y ago
I am not familiar with NSan but other shadow value implementations will keep a higher precision copy of the numbers and follow them in the computation. They detect local errors but also take propagation (amplification and dampening of error) into account to evaluate the numerical accuracy of the final result.

lrossi 6y ago

Is there a pdf available or just the abstract?

remexre 6y ago
Bizarrely, using institutional access gives me [0]... EDIT: Though it does note that it is for publication in March, so it might not be intended to be generally available yet. [0]: https://cdn.remexre.xyz/screenshots/842f6f91029e6d956cb287d65cc32693b1385141.png https://cdn.remexre.xyz/screenshots/842f6f91029e6d956cb287d6...
- saagarjha 6y ago
  Perhaps you weren’t in the sudoers file.
viraptor 6y ago
> March 2021 I don't think the journal is actually published yet.
- lrossi 6y ago
  Makes sense now, thanks.

lstamour 6y ago

See also: https://conf.researchr.org/details/CC-2021/cc-research-papers/7/NSan-A-Floating-Point-Numerical-Sanitizer https://conf.researchr.org/details/CC-2021/cc-research-paper...

nestorD 6y ago

I am not familiar with NSan (and impatient to read the paper) but a common problem with tools based on higher precision shadow values is that they can be easily defeated by a large cancelation (`(1e200 + 1) - 1e200` will return 0 in both 64 and 200 bits arithmteic). My solution to this problem (which also has performance benefits) is to use an error-free transform based arithmetic (they give you roughly doubled precision but are also very resilient to cancelation). See Shaman [0] for a C++ reference implementation, you can change your types and it will display only the significant digits of your results. If you want something that does not require modifying your source code, I would recommend Verrou [1], a Valgrind-based tool using stochastic arithmetic. For those interested in the subject, my PhD [1] (which is written in English despite the French title) gives further information on all those methods, their pros and cons. [0]: https://gitlab.com/numerical_shaman/shaman https://gitlab.com/numerical_shaman/shaman [1]: https://github.com/edf-hpc/verrou https://github.com/edf-hpc/verrou [2]: https://tel.archives-ouvertes.fr/tel-03116750 https://tel.archives-ouvertes.fr/tel-03116750

nestorD 6y ago
People here might also be interested in the Julia implementation of Shaman: https://gitlab.com/numerical_shaman/shaman_julia https://gitlab.com/numerical_shaman/shaman_julia
Lemmih 6y ago
Loved your thesis. Will implement it in Haskell for use in hgeometry (https://hgeometry.org https://hgeometry.org).
- nestorD 6y ago
  Great! Don't hesitate to contact me if you have any question or roadblock. I would be happy to give a link to your implementation in the readme of the C++ reference implementation.
  - Lemmih 6y ago
    No roadblocks but I did find something I didn't expect. Turns out that 'sinl(pi)' differs on Linux and macosx. I'm getting error-bounds that are slightly different. Here's the PR for my Haskell implementation: https://github.com/noinia/hgeometry/pull/120 https://github.com/noinia/hgeometry/pull/120 Here's the documentation: https://noinia.github.io/hgeometry/doc/hgeometry-combinatorial-0.11.0.0/Data-Double-Shaman.html https://noinia.github.io/hgeometry/doc/hgeometry-combinatori...