YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Coverage For Random Testing - Software Testing

Get Embed Code
1 Language

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. Okay, so this is what a random test is going to look like,

  2. and now let's look at the implementation in Python.
  3. And we're going to see is that since all I have is the reference implementation,
  4. not actually going to be testing two implementations against each other,
  5. rather all I'm going to be doing is making up two random 64-bit integers
  6. and just running the high common bits and low common bits function on them.
  7. We're going to do is we're going to be able to see code coverage, but I'm not actually checking
  8. the output for correctness, and I'm running a 100,000 test cases,
  9. so let's run this under the coverage harness.
  10. As you can see, I'm asking here for branch coverage.
  11. So, that's a lot of output, and the coverage should have been computed,
  12. and we see here is out of 25 statements around 23 of them
  13. a couple of statements were missing, and we had couple of partial branch coverage results.
  14. What you can see here is we've executed the body of the loops,
  15. and we've returned out of this path, but we failed to take the exit branch from the loop,
  16. and we failed to execute the return statement.
  17. The same thing is happened over here.
  18. So, let's asked ourselves why completely random testing with valid inputs
  19. a hundred thousand times did not manage to cover this.
  20. Well, of course, this is pretty easily to see, so we're generating two totally independent
  21. random 64-bit numbers, and the only way we can reach this case is fairly the same.
  22. So what are the odds of two randomly generating 64-bit integers being the same?
  23. They're extremely low compared to a number of test cases running.
  24. We're never going to test this case, so for testing optimized
  25. implementations of these functions in such matters quite a bit more.
  26. When we do optimize implementations of these functions, we're going to use specialized instructions
  27. that modern architecture support with providing bit counts.
  28. This is going to boil down to at least before using GCC as compiler
  29. functions like this builtin clz and builtin ctz, which as you can see,
  30. clz returned a number of leading 0-bits in x starting at the most significant bit position,
  31. and we can use this to implement one of our bit functions by XORing to the other the two operands
  32. to turn common bits into leading 0 bits, and so, we can do is using XOR operation to turn
  33. high order common bits in our arguments into leading 0 bits then we can use this builtin clz
  34. to implement an extremely fast version of the high common bits function
  35. and similarly, this builtin ctz can be used to build an extremely fast low common bits.
  36. If you see here, if x is 0, that is to say, if the two inputs are equal, the result is undefined.
  37. The implementation here has allowed to do something really weird
  38. in the case where we passed in two operands that are the same, but as we saw
  39. a little random testing here has only a negligible chance
  40. of actually generating two arguments that are actually the same.
  41. It's really a bad random test for this case. Let's go back and try to do better.