The Startup
Published in

The Startup

Playing with Virtual Time

Automated tests should be:

  • specific, ie. testing only one thing,
  • fast, and
  • deterministic, ie. running them twice gives the same result.

(for more properties see Kent Beck’s excellent post Test Desiderata).

We achieve these properties by using unit tests characterized by the fact that we mock out anything that is not under test, such as databases, or other parts of the code tested separately. But what if our code depends on timing? Or have multiple threads interacting?

Thread scheduling is famously not deterministic. Relying on timing can prevent tests from running fast. Using concurrency means that we are at least testing the code and the concurrency itself. Do we have to forgo these three properties?

It turns out the answer is “no”, and in an amazing twist we have already revealed the solution above; we need to mock out time!

In its simplest form, the idea is to skip any sleep in our applications and instead keep track of the order of the threads. This can have the side effect that we serialize some parts of the program that will run in parallel with real-time.

In the code examples below I spare you from a lot of distracting “lock house-keeping”.

No Sleep

First, we need to replace the normal sleep function. Our mock introduces a new sleep function. Instead of sleeping we lock the thread and put the lock into a queue with a timestamp of when it “wants” to wake up. Then when there are no other active threads we release the lock with the smallest timestamp.

sleep(long millis) {
var sem = new Semaphore(0);
_queue.put(_clock + millis, sem);
wakeUpNextIfNoneActive();
sem.acquire();
}

The queue of locks and timestamps have a few interesting properties. We always only look at the element with the smallest timestamp. We also only ever remove this element. An efficient data structure supporting polling the minimum element is min-heap.

Thread Count

To wake up the next thread when there are no other active threads, we need to keep track of how many threads there are. Note that this might change during execution as threads finish their tasks and new ones get created.

Our mock introduces a new method to create threads. This allows us to keep track of the thread count without the user ever having to know about it. We increment the thread count, and return a new thread who’s run method calls the desired code and then decrements the thread count. If the last active thread finishes we again need to start a new thread from the queue.

freshThread(Runnable r) {
registerThread();
return new Thread(() -> {
r.run();
unregisterThread();
});
}

Locks

Sleeping is not the only way methods stop being active they can also be locked by someone other than us. Therefore we also need to replace the locks of the source program with ones we have control over. As I am a strong supporter of semaphores this is the only mechanism I have included.

Our library introduces a new method for creating semaphores. These directly call a regular semaphore in all cases but when they are about to block the thread. If we are about to block the last active thread we first wake up the next thread in the queue, ensuring that there is always at least one active thread.

acquire() {
if (_sem.availablePermits() == 0)
_time.releaseNext();
_sem.acquire();
}

Virtual Time

Finally, our code may depend on the clock for timing, so our library also provides a new method for this. This time is set to every time we take something off the queue to simulate that the next timestamp is now the current time.

wakeUpNext() {
LongEntry<Semaphore> v;
do {
v = _queue.pollFirstEntry();
v.getValue().release();
} while (_queue.size() > 0 && _queue.firstKey() == v.getKey());
_clock = v.getKey();
}

Library vs Tool

I have built this inside Java instead of as an external tool. This has several advantages, my personal favorites are:

  1. It allows us to continue writing our tests like we normally would when we mock things. Familiar looking code is important.
  2. We don’t introduce a dependency on an external tool that needs to be downloaded, installed, and learned.
  3. We can choose to ship it with our code and potentially use it in production if it makes sense. We can even switch during runtime.

Conclusion

Using virtual time our tests can become deterministic even in the presence of multiple threads. Virtual time can also make our tests fast by stripping out any sleep our application might want to do. Finally, using virtual time means that we can focus our test on the functionality and ignore the concurrency.

Keep in mind that my library was made to explore the concepts, not to be efficient or complete. If you want to have a look at the source code for the library it is available on my GitHub (@maxpaxi). If you want to learn more about how to extract code so it can be mocked out, then consider checking out my book:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Christian Clausen

Christian Clausen

I live by my mentor’s words: “The key to being consistently brilliant is: hard work, every day.”