How do you test nondeterministic code?


Jay posted some of the code we wrote on the lazy loader and weak references.  An astute reader pointed out that there was a flaw in my implementation.  Specifically I was messing up how I interacted with “null” and “None<A>.Instance”.  None<A>.Instance is both a singleton and an example of Fowler’s “Null Object” (see Introduce Null Object).  However, I didn’t catch it because it passed all testing that I put it through.  The issue was non of the testing ever hit the WeakReference when it had actually released it’s hold on the object.  I wanted to add tests to make sure that works, but I wasn’t sure how.  Not only are weak references out of my control as the class is provided by the BCL but its highly dependent on how the GC works which is basically a non deterministic beast that i don’t have enough control enough.  (Even if the BCL provided a “collect all weakreferences method”, I’d just extend this question to any non-deterministic code).  So how do I test this?  How do you test code like this?


Note: this also applies to multi-threaded code.  The best I’ve been able to come up with is doing something like spawning tons of threads and having tehm go nuts and then verifying validaity of state every so often.  Bleagh. 


Comments (5)

  1. David Levine says:

    For the weak reference you could inject some test code that would manually set the target of the weak reference to a value of null. Not ideal but it would at least test the code path. You could hide access to the WR through an interface – the default implementation simply returns the real WR, and the unit test implementation allows you to modify the target.

    I’ve worked on execution engines and multi-threaded code is very difficult to get correct and even harder to test in a rigorous manner. It’s not enough to spawn tons of threads (though that is good), you must also spawn tons of threads and vary their priorities, because some threading issues only become noticeable when threads of different priority levels are in contention.

    This gets even harder to test when you combine this with thread interrupts. This is more of an issue with device drivers then application code, but given that a ThreadAbort is asynchronous and can arbitrarily interrupt managed code, for complete coverage you should include that too.

    Ultimately, some types of code can only be proven to be correct in a statistical sense.

  2. dls says:

    starting with the badly obvious *smirks* testing nondeterministc code is hard because it means that you can’t rely on equivalence classes to minimize the number of test cases required to do thorough black box testing. I think the best we usually do is to put the non deterministic component on bad behavior (collect all weak references often, make with lots of context swapping, etc). And even that is just a way of breaking the non deterministic behavior (usually, always? by breaking the black-boxness).

  3. Joe Duffy says:

    Mock objects are great ways to test functions which are outside of the control of your application (e.g., the GC). However, this particular case is difficult because as you mentioned you’d be trying to mock an object from the BCL. Typically, one would refactor the class whose object is to be mocked into an interface, and provide your "real" implementation for runtime and your "mock" implementation for those test cases that need the mocked functionality. Coverage begins to get tricky at this point, as you might then have to test certain portions of your real implementation in isolation, etc., etc.

    So in this instance maybe you could refactor your code to use some internal wrapper around WeakReference so you have more wiggle room? Then you can mock this wrapper class.

    I’d recommend checking out some of the stuff by Dave Thomas on this topic — definitely pretty interesting.

    http://www.google.com/search?q=Dave+Thomas+mock+objects

    <joe/>

  4. Joe: WeakReference<T> is my internal wrapper around WeakReference :-)

    I have no wiggle room :(

  5. Thinking more about it, it seems that you didn’t have much of a choice. WeakReference changes the value back to "null" when it gets collected, not to "None<T>.Instance"…

    For the unittesting part, you need to make it deterministic one way or another, preferrably without having to fill up the memory of your computer 😉 You can simulate the collection by setting the WeakReference to null maybe.