Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have been working on a project and running into a very difficult problem. The problem can be stated simply as how to unit-test numerical algorithms. However if you just took this simple statement you would get the standard set of answer isolation of input, random processes, mocking, tolerancing, etc.
The answer (if there is one) does not reside with these.

Also, as a note, I am not concerned with testing the correctness of the algorithm. That is done with very different methods and it is assumed that the algorithm is correct. What I am using unit-testing for is to make sure that changes in other parts of the system/support algorithms do not change the output of the algorithm under test.

So, for a description of the problem: We have an algorithm which takes Gigabits of data, processing it, and generates an image with a corresponding map of which pixels are good and which ones are not. It is this map which I need to verify does not change and pixels which are not valid are not to be used in any way other than the fact that they invalid.

If this was all that was given I would have many possible solutions and in fact the method have been using for years is to look at the number of valid pixels, the average, standard deviation, peak and valley of the image. This has proven very sensitive detector for changes.

But, this year has added complications which is causing issues with this approach.

  • The number of threads being used has increased causing changes in the floating point behavior. In the past the smaller number of thread was accounted for in the tolerances used.
  • We have been using floating point (as compared to double) to increase throughput. This has caused the rounding behavior to change even more and combined with the number of threads makes it worse. This has also been made worse as we move to using SIMD processing like GPU and/or AVX instructions sets.
  • We have been enhancing the algorithms used to recover more of the pixels which would have been marked as invalid in the past are not valid. This combined with 1 and 2 above is resulting in some pixels being included on some machine and not on others. Since these are on the edge of useability these difference are handled by the algorithms with use this image and are not of concern for the system as a whole, but are causing problems with unit testing the algorithms.
  • We have also recently ran into the problem that two numbers (internal to the calculation) are the same and because of the rounding behavior one or the other is picked resulting in different outputs. . Again this is not a problem of the system as a whole, only with unit testing to flag for differences.
  • As a minor side example, we also have other non-linear algorithms with due to rounding behavior can give different outputs. Since these algorithms are self correcting the final solution is good, but has a higher variability than easily accounted for unless the tolerances are opened larger than desired.

So, my questions is how to account for these issue in unit testing.
I strongly need unit testing because we have a team of programmers working on the system and we need the ability to detect when someone makes a change which unknowingly impacts other algorithms. Yes this has happened in the past and the method being used at the time caught the change before it reached the final product. As the primary algorithm developer I can use your help. I have had many ideas, but they don’t work for all cases and it’s not clear when to use one of the different methods.

Edit: I now that this is frequently called regression testing but I also know that many time it is also generically called unit testing by many people, even if it's not completely correct.

I am not necessarily looking for a magic bullet (that would be nice) but I do need a way of handling these issues in a way which can be handled by others in the group which may not be as knowledgeable on the details. If that is a “pick” one of these methods that is fine if it the rule are clear. We do adjust the parameters when we change the algorithms, but once it is fixed the floating point behavior is still causing differences. When we see differences we always investigate why and in general we try to adjust the algorithm to reduce the difference, but there are times where these is not possible because of the additional computation time. If we stayed away from the limits this would not be an issue (as in the past) but to advance the technology we need to push the limits giving rise to the issues described.

You can see this in a simple example. Calculating an average of many numbers. If you stay with number which are close to each other, there are simple methods to make sure the results are accurate. Now when you allow for numbers which have large (orders of mag) difference, with threading, float compared to double, etc you can get very different results. Yes I know there are algorithms which can be used to fix these issue but they can be very computation expensive. While averaging is not my problem you could imagine that the difference don’t impact downstream processing but you still want to write a test to monitor the calculation.

share|improve this question
2  
That sounds very much like integration testing rather than unit testing. –  Ӎσᶎ Dec 11 '13 at 4:14
1  
@Ӎσᶎ: call it unit or integration testing, the question keeps beeing the same. –  Doc Brown Dec 11 '13 at 6:33
1  
Jim, maybe you should edit your question and replace the term "unit testing" by "automated regression testing", since that is what you describing here. –  Doc Brown Dec 11 '13 at 9:20

3 Answers 3

First of all, it is not very clear if you compare floating point numbers with exact values in your unit tests. If you do so, this is wrong and you should rely on approximate comparison of floating point numbers [1].

That being said, if your computations are sensitive to factors such as the number of threads involved, the precision of numbers used and the other things you describe, then you should question the stability of your numerical procedures. If you are lucky, you can rewrite some calculations to improve the stability without significantly change the number of operations required. But it might also happen, that writing better procedures involves more calculations, so that you will have to find an acceptable trade-off between time and precision.

[1] For instance, you can start here: http://www.gnu.org/software/gsl/manual/html_node/Approximate-Comparison-of-Floating-Point-Numbers.html

share|improve this answer
    
+1 for mentioning numerical stability, that's a good point, especially when different kind of floating point hardware is used. –  Doc Brown Dec 11 '13 at 9:39
    
No I am not comparing exact values. –  Jim Kramer Dec 11 '13 at 12:49
    
I am well aware of the idea of the possibility of changing algorithm to address this differences. However, this is not practical because of speed. The changes would cause too much of a hit, and when we see these difference we investigate for bug or impact on the system as a whole and only if this is ok do we leave it. This is just the starting point of many other calculations. The issue is the combination of all the items outlined not just one. However we still want to monitor for unexpected changes. –  Jim Kramer Dec 11 '13 at 12:56

How do you eat an elephant? One bite at a time. It sounds you are looking for a "magic bullet" to solve all of your problems at once, and that's IMHO part of the problem. There is not magic bullet, this is hard work, and you can only solve it step-by-step.

For example, you told us that you have already some fuzzy or statistical methods in place to compare the result of your tests to an expected result. I guess these fuzzy methods have some threshold parameters when to accept a result and when not. Whenever you change the behaviour of your algorithms, you will have to adept these parameters - do this for one change after another, run the tests again, make sure the new results are in the accepted range. In fact, you have to fine-tune this parameters, since it may be not ad-hoc clear which results are correct, which are incorrect and if there is a "grey area" between right and wrong.

If that does not work, you may have to look for a modification of the "fuzzy comparison" itself - each time you come across a new kind of change. Unfortunately I cannot tell you how these comparison have to look like, since one must have in-depth know-how about your problem domain to make a right decision.

EDIT: maybe image matching techniques will help in your case, see this SO post for some ideas.

And if this does not work either, this may also be a sign that your modification of the algorithm introduced too many unwanted side effects, so maybe you don't have to change the test, but the way you modify the algorithm implementation.

I have had many ideas, but they don’t work for all cases

Then don't look for a solution which works for "all cases". Use different solutions for different test cases.

share|improve this answer
    
See additions to post above. –  Jim Kramer Dec 11 '13 at 14:35

There is a contradiction in your question. First you are saying:

What I am using unit-testing for is to make sure that changes in other parts of the system/support algorithms do not change the output of the algorithm under test.

But then you list several ways the output has changed that were not the changes you wanted to catch. So "change of the output" isn't your ultimate deciding criterion, but you are using it in your unit test. Why?

You need to define which changes are meaningful to you (as the "any change" metric clearly doesn't work) and use that in your unit tests.

On the other hand, maybe you'd like to be notified for any change, but need a quicker method to approve the new results than editing source code?

share|improve this answer
    
The way I understand the question is that there is an algorithm which produces an image as a result, and the result is fine when this image "looks very similar" to an expected image. And the OP has already a formal test for "looks very similar" which worked in the past, but now it does not any more. I don't see this as a contradiction in his question, maybe only imprecise use of words. And I agree to you, this boils down to what you wrote in your answer: finding a better "change metric", or at least adjusting the acceptance thresholds for the available metrics. –  Doc Brown Dec 11 '13 at 9:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.