Sleep, Sort, Repeat
Testing Async Code Without Losing Sleep with Kotlin and Coroutines
A few years back I stumbled upon Sleep Sort algorithm and my first thought was: this would be fun to implement using Kotlin’s coroutines.
sleep sort works by starting a separate task for each item to be sorted, where each task sleeps for an interval corresponding to the item’s sort key, then emits the item. Items are then collected sequentially in time
Since I procrastinated a bit on this article, you can already find a basic example implementation in the reference link. But here, we’ll take it a step further and show how to collect the results instead of just printing them, but most importantly, how to test it effectively.
For each element in the list, we launch a coroutine that delays for a duration corresponding to the value of the number, in seconds. For example, if a number is 3600, the coroutine will delay for an hour. This is done asynchronously for each number in the list, allowing all tasks to ‘sleep’ concurrently.
We’ll dive into the code in detail shortly, but first, let’s write a quick test to see it in action.
Take a moment to look over the test and guess how long it will take to run. We generate 100,000 random numbers between 0 and MAX_INT. At first glance, it seems like this test should take a long time — if it even finishes at all.
But here’s the output on my local laptop: BUILD SUCCESSFUL in 1s
What happened? How did a test that seemed like it should take forever finish in just one second?! This is exactly what we’re here to explore: how Kotlin coroutine testing makes it easy and fast to test asynchronous code.
If I’ve got your attention, let’s go back to the implementation and take a closer look.
Let’s evaluate sleepSort from a main function to see it in action and measure its execution time. We’ll use the measureTimedValue function, which conveniently returns both the result and the duration. But let’s not get ahead of ourselves — it’s wise to start with smaller numbers first, as we’ll actually need to wait for the delays this time…
As we might have expected from our initial reasoning, this time the execution takes approximately as long as the highest element’s value in seconds: It took 5.040657167s to sort [1, 1, 2, 2, 3, 3, 4, 5].
The secret behind the speed of our initial test lies in using the runTest scope function from kotlinx-coroutines-test. The magic of runTest comes from its ability to execute coroutine-based code using a virtual time system. When you run code in a runTest block, it uses a special scheduler, called TestCoroutineScheduler, that allows precise control over time. This means that instead of waiting for real-time delays, you can fast-forward through time to execute coroutines almost instantly. Here’s how it achieves this:
1. Virtual Time Simulation:
In a runTest block, time doesn’t move forward unless the code explicitly advances it. This is controlled by functions like advanceTimeBy(), which moves the clock forward by a specified amount, or advanceUntilIdle(), which fast-forwards until all tasks are completed.
2. Delay Skipping:
When coroutines encounter delays (like delay(1.seconds)), the virtual time system can “skip over” those delays without actually pausing the execution. This allows tests to run quickly while still respecting the intended sequence of operations.
3. Maintaining Execution Order:
Despite the ability to skip delays, runTest ensures that coroutines are executed in the correct order, as they would be in real-time. This makes it ideal for testing time-sensitive code while avoiding the usual issues with flaky or slow tests.
4. Automatic Cleanup and Timeout Handling:
By default, runTest includes a timeout for the entire test, which helps prevent hanging tests due to uncompleted coroutines. It also automatically cleans up resources and cancels coroutines when the test is completed. In my experience, runTest has been invaluable for detecting coroutine leaks that would otherwise be hard to find. These issues often cause regular tests to fail sporadically, making the root cause difficult to identify. The built-in timeout and cleanup mechanisms help catch such problems early, leading to more reliable tests.
Revisiting the initial test, I discovered some interesting limitations:
- Using delays in nanoseconds does not produce correct sorting results.
- Delays in milliseconds work correctly with virtual time but not with real-time.
- Starting from delays of seconds, the sorting behaves as expected in both virtual and real-time.
- Sorting 1,000,000 numbers takes about 12 seconds, but attempting to sort 10,000,000 numbers results in running out of memory.
This was a good exercise to learn how coroutines can be efficiently tested and to explore the power of using virtual time with Kotlin’s coroutine testing tools. The runTest function and TestCoroutineScheduler make it easy to verify asynchronous code’s behavior while keeping tests fast and consistent.
Through this example, we saw how coroutines, when combined with the right testing strategies, offer a flexible and effective approach to handling concurrency in both experimental and practical scenarios. Hopefully, this exploration has given you a deeper appreciation for Kotlin’s coroutine capabilities and the ease of testing asynchronous code.
You can find the project on GitHub, where you can see all the dependencies and the package details for the functions used.