NSan: a floating-point numerical sanitizer | Hacker News Reader

NSan: a floating-point numerical sanitizer

dl.acm.org

86 pointsKatydid21 comments

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 [1]: https://github.com/edf-hpc/verrou [2]: https://tel.archives-ouvertes.fr/tel-03116750

People here might also be interested in the Julia implementation of Shaman: https://gitlab.com/numerical_shaman/shaman_julia

Loved your thesis. Will implement it in Haskell for use in hgeometry (https://hgeometry.org).

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.

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

Here's the documentation: https://noinia.github.io/hgeometry/doc/hgeometry-combinatori...

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.

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.

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.

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

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.

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.

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?

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.

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

[2] https://en.wikipedia.org/wiki/Householder_transformation

[3] https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobi...

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.

Is there a pdf available or just the abstract?

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/842f6f91029e6d956cb287d6...

Perhaps you weren’t in the sudoers file.

> March 2021

I don't think the journal is actually published yet.

Makes sense now, thanks.

Reply on news.ycombinator.com