How do you test complex transformations?
Hi, I know that my question is not directly associated to Boost, but it could be interesting to share the best techniques so we can improve the test of some Boost libraries, existing or future. A transformation complex is complex if I can not associate mentally the output associated to a given input. Think for example on dividing two bit integers. One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match. Do you know other techniques? Does some Boost libraries have such a kind of transformations? How they are tested? Thanks in advance, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/How-do-you-test-complex-transformations-t... Sent from the Boost - Dev mailing list archive at Nabble.com.
AMDG On 03/18/2011 10:23 AM, Vicente Botet wrote:
I know that my question is not directly associated to Boost, but it could be interesting to share the best techniques so we can improve the test of some Boost libraries, existing or future.
A transformation complex is complex if I can not associate mentally the output associated to a given input. Think for example on dividing two bit integers.
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Do you know other techniques? Does some Boost libraries have such a kind of transformations? How they are tested?
* Compute the inverse transformation and check that you get back the original value. e.g. q, r = div(a, b); assert(r + q * b == a); * Combine multiple transformations in different ways which should produce identical results. e.g. assert(a/b/c == a/(b * c) == a/c/b) In Christ, Steven Watanabe
Steven Watanabe-4 wrote:
AMDG
On 03/18/2011 10:23 AM, Vicente Botet wrote:
I know that my question is not directly associated to Boost, but it could be interesting to share the best techniques so we can improve the test of some Boost libraries, existing or future.
A transformation complex is complex if I can not associate mentally the output associated to a given input. Think for example on dividing two bit integers.
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Do you know other techniques? Does some Boost libraries have such a kind of transformations? How they are tested?
* Compute the inverse transformation and check that you get back the original value. e.g. q, r = div(a, b); assert(r + q * b == a); * Combine multiple transformations in different ways which should produce identical results. e.g. assert(a/b/c == a/(b * c) == a/c/b)
In Christ, Steven Watanabe
Hi Steven, I really like the two guidelines. Very clever. Thanks, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/How-do-you-test-complex-transformations-t... Sent from the Boost - Dev mailing list archive at Nabble.com.
On 1:59 PM, Vicente Botet wrote:
[...] One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
I more often verify a couple test-cases by hand and encode those, paying special attention to boundary conditions, etc. Some situations are complex enough that they warrant test hooks to verify intermediate results. And, yes, I leave the hooks in. E.g., "if (test) test->VerifyIntermdiateX(y,z);" Make sure the test-hook pointer is 0 for production.
Jim Bell wrote:
On 1:59 PM, Vicente Botet wrote:
[...] One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
I more often verify a couple test-cases by hand and encode those, paying special attention to boundary conditions, etc.
Some situations are complex enough that they warrant test hooks to verify intermediate results. And, yes, I leave the hooks in. E.g., "if (test) test->VerifyIntermdiateX(y,z);" Make sure the test-hook pointer is 0 for production.
Hi, what kind of verification do you use to do? for example if we had T complex_transformation(T a) { T tmp1 = simpler_transformation_x(a); T tmp2 = simpler_transformation_y(tmp); return tmp; } could you complete the example with the use of your test verifications? where do comes test? Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/How-do-you-test-complex-transformations-t... Sent from the Boost - Dev mailing list archive at Nabble.com.
On 1:59 PM, Vicente Botet wrote:
Jim Bell wrote:
On 1:59 PM, Vicente Botet wrote:
[...] One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
I more often verify a couple test-cases by hand and encode those, paying special attention to boundary conditions, etc.
Some situations are complex enough that they warrant test hooks to verify intermediate results. And, yes, I leave the hooks in. E.g., "if (test) test->VerifyIntermdiateX(y,z);" Make sure the test-hook pointer is 0 for production.
Hi,
what kind of verification do you use to do?
for example if we had
T complex_transformation(T a) { T tmp1 = simpler_transformation_x(a); T tmp2 = simpler_transformation_y(tmp); return tmp; }
could you complete the example with the use of your test verifications? where do comes test?
You're not using your tmp1 and tmp2 in your example. And if you can come up with simpler_transformation_<n>(), you can test those in isolation. The examples that come to my mind require looking at salient states of a variety of objects, disk files, etc. But the basic form, adapted to your example, would be... static T_test_interface *test = 0; T complex_transformation(T a) { T tmp1 = simpler_transformation_x(a); if (test) test->verify_post_x_pre_y(tmp1); T tmp2 = simpler_transformation_y(tmp1); return tmp2; } A big +1 on inverting an operation, too, when you can.
On 18/03/2011 18:23, Vicente Botet wrote:
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Checking that both implementations match is not really possible if the range of all inputs is big. What we do to validate the precision of our math functions in the NT2 project is that we perform random tests and compare the results to that obtained with a library that we know to be correct.
Mathias Gaunard-2 wrote:
On 18/03/2011 18:23, Vicente Botet wrote:
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Checking that both implementations match is not really possible if the range of all inputs is big.
What we do to validate the precision of our math functions in the NT2 project is that we perform random tests and compare the results to that obtained with a library that we know to be correct.
Hi, yes, I'm in the same situation, the samples are often generated randomly. If you are developing new algorithms, this is equivalent to implement the algorithm (possibly with less constraints) and compare the results. Of course both implementation can be wrong. If you didn't have a library that gives you the correct answer, do you think that you will find re-implementing the transformation a good practice? Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/How-do-you-test-complex-transformations-t... Sent from the Boost - Dev mailing list archive at Nabble.com.
On 18/03/2011 22:32, Vicente Botet wrote:
Mathias Gaunard-2 wrote:
On 18/03/2011 18:23, Vicente Botet wrote:
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Checking that both implementations match is not really possible if the range of all inputs is big.
What we do to validate the precision of our math functions in the NT2 project is that we perform random tests and compare the results to that obtained with a library that we know to be correct.
Hi,
yes, I'm in the same situation, the samples are often generated randomly.
If you are developing new algorithms, this is equivalent to implement the algorithm (possibly with less constraints) and compare the results. Of course both implementation can be wrong.
If you didn't have a library that gives you the correct answer, do you think that you will find re-implementing the transformation a good practice?
It is usually much easier to write a correct but slow implementation than to write a fast one. So if the code of your algorithm is complicated because it does smart things for speed purposes or is parallelized, it is useful to validate it against a simple implementation that is less likely to be wrong.
So if the code of your algorithm is complicated because it does smart things for speed purposes or is parallelized, it is useful to validate it against a simple implementation that is less likely to be wrong.
What we tried to do with Boost.Math was: * Generate test values from "known goods" where available - Mathematica or it's online sibling functions.wolfram.com are good choices. * Generate high precision test values for random testing using code we wrote ourselves, but which uses a "brain dead" implementation copied directly from the definition of the function, and enough digits precision to overcome any cancellation errors that may result. It doesn't matter how long this takes to run as long as it does get there eventually... * Then double check that the test cases actually cover all of the branches in the "real" code - sometimes it can be a real challenge to find cases that take a particular branch though! Even with the above, there is a real issue with functions taking many parameters - it's basically *impossible* to fully cover the entire domain of the function with your test cases - given that complexity grows exponentially with number of parameters. HTH, John.
Vicente Botet wrote:
Mathias Gaunard-2 wrote:
On 18/03/2011 18:23, Vicente Botet wrote:
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Checking that both implementations match is not really possible if the range of all inputs is big.
What we do to validate the precision of our math functions in the NT2 project is that we perform random tests and compare the results to that obtained with a library that we know to be correct.
Hi,
yes, I'm in the same situation, the samples are often generated randomly.
If you are developing new algorithms, this is equivalent to implement the algorithm (possibly with less constraints) and compare the results. Of course both implementation can be wrong.
If you didn't have a library that gives you the correct answer, do you think that you will find re-implementing the transformation a good practice?
I do. Typically I implement a brute force version first that can be very slow then follow that up with the real implementation. I prefer to take a known correct implementation to test against if I can get one, but if it doesn't I implement one. Also, when I comes to testing I will often test post conditions of the algorithm separate from eachother. Even if I can't programatically detect a 100% correct result, I can detect trivially wrong results with this kind of test. For example, if the result of some calculation has to be positive running it on many randomly generated inputs and checking that the result is always positive is a quick and easy way to isolate silly problems. The simplest example of this is crash testing on random data where the only thing you are looking for is that the code doesn't crash or hang. If both implementations of the algorithms match for a large set of randomly generated test cases, satisfy all checkable post conditions and are correct for several well chosen unit test inputs then you can have pretty high confidence. Of course, if your understand of the problem is wrong then both implementations are going to be wrong, but unit testing can't catch requirement bugs. I often try several alternative implementations to experiment and compare which turns out to be faster. Is a branchy algorithm faster or slower than a table lookup algorithm? Is bit twiddling faster than a switch statement? I also try to break it down into seperately testable sub pieces. For example, instead of one very large large table of size n*m mapping input to output I might break it down into two smaller tables of size n and m and then combine their results. If n*m is too large to populate the table manually, but n+m is small enough I might implement a complex transformation by a series of table lookup. Then you need to prove that your idea for how to break it down is correct, but this can be done with paper and pencil, then you just need to validate each entry in the small tables manually then validate serveral of their combinations manually and your pencil and paper proof should provide enough confidence that all combinations will come together correctly. I always try to "prove" that the idea I'm implementing is correct up front, which can be thought of as testing you do in your head before you have code. Also, if you can tell up front what will be hard to test you can steer your design decisions toward implementations that are easier to test. Regards, Luke
Simonson, Lucanus J wrote:
Vicente Botet wrote:
Mathias Gaunard-2 wrote:
On 18/03/2011 18:23, Vicente Botet wrote:
One technique could be to make the transformation by hand and keep track of the input -> output association. Another technique consist in re-implementing the algorithm and check that both implementations match.
Checking that both implementations match is not really possible if the range of all inputs is big.
What we do to validate the precision of our math functions in the NT2 project is that we perform random tests and compare the results to that obtained with a library that we know to be correct.
Hi,
yes, I'm in the same situation, the samples are often generated randomly.
If you are developing new algorithms, this is equivalent to implement the algorithm (possibly with less constraints) and compare the results. Of course both implementation can be wrong.
If you didn't have a library that gives you the correct answer, do you think that you will find re-implementing the transformation a good practice?
I do. Typically I implement a brute force version first that can be very slow then follow that up with the real implementation. I prefer to take a known correct implementation to test against if I can get one, but if it doesn't I implement one.
This seems reasonable.
Also, when I comes to testing I will often test post conditions of the algorithm separate from eachother. Even if I can't programatically detect a 100% correct result, I can detect trivially wrong results with this kind of test. For example, if the result of some calculation has to be positive running it on many randomly generated inputs and checking that the result is always positive is a quick and easy way to isolate silly problems. The simplest example of this is crash testing on random data where the only thing you are looking for is that the code doesn't crash or hang.
You are right. Most of the times there is something that can be tested even if we can not test everything and this helps.
If both implementations of the algorithms match for a large set of randomly generated test cases, satisfy all checkable post conditions and are correct for several well chosen unit test inputs then you can have pretty high confidence. Of course, if your understand of the problem is wrong then both implementations are going to be wrong, but unit testing can't catch requirement bugs.
Yes, the best is that is someone else that make the unconstrained implementation.
I often try several alternative implementations to experiment and compare which turns out to be faster. Is a branchy algorithm faster or slower than a table lookup algorithm? Is bit twiddling faster than a switch statement?
This seems reasonable for critical parts.
I also try to break it down into seperately testable sub pieces. For example, instead of one very large large table of size n*m mapping input to output I might break it down into two smaller tables of size n and m and then combine their results. If n*m is too large to populate the table manually, but n+m is small enough I might implement a complex transformation by a series of table lookup. Then you need to prove that your idea for how to break it down is correct, but this can be done with paper and pencil, then you just need to validate each entry in the small tables manually then validate serveral of their combinations manually and your pencil and paper proof should provide enough confidence that all combinations will come together correctly. I always try to "prove" that the idea I'm implementing is correct up front, which can be thought of as testing you do in your head before you have code. Also, if you can tell up front what will be hard to test you can steer your design decisions toward implementations that are easier to test.
Thanks for sharing your experience. This helps a lot, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/How-do-you-test-complex-transformations-t... Sent from the Boost - Dev mailing list archive at Nabble.com.
participants (6)
-
Jim Bell -
John Maddock -
Mathias Gaunard -
Simonson, Lucanus J -
Steven Watanabe -
Vicente Botet