In my decades long quest to find ever slower but more interesting ways to calculate fibonacci numbers I came up with this solution, which is a recursive fibonacci algorithm but spawning a Tokio task for each recursion, sending parameters and results over channels rather than making recursive calls.
use async_recursion::async_recursion;
type Sender = mpsc::UnboundedSender<u64>;
type Receiver = mpsc::UnboundedReceiver<u64>;
pub struct FiboTokio {
par_rx: Receiver,
res_tx: Sender,
}
impl FiboTokio {
pub fn new(par_rx: Receiver, res_tx: Sender) -> Self {
Self { par_rx, res_tx }
}
pub async fn fibo(n: u64) -> u64 {
// Create parameter and result passing channels.
let (par_tx, par_rx) = mpsc::unbounded_channel::<u64>();
let (res_tx, mut res_rx) = mpsc::unbounded_channel::<u64>();
// Create new fibo calculator object.
let f1 = FiboTokio::new(par_rx, res_tx);
// Run the fibo calculator on a task
tokio::spawn(async move {
f1.calc().await;
});
// Send the parameter to the fibo calculator.
par_tx.send(n).unwrap();
// Collect the results from the return channel.
res_rx.recv().await.unwrap()
}
#[async_recursion]
async fn calc(mut self) {
// Get the number we want the fibo of from the parameter channel.
let n = self.par_rx.recv().await.unwrap();
let f = match n {
0 => 0u64,
1 => 1u64,
_ => {
let f1 = Self::fibo(n - 1);
let f2 = Self::fibo(n - 2);
let (f1, f2) = join!(f1, f2);
f1 + f2
}
};
// Return the resulting fibonacci number on the result channel.
self.res_tx.send(f).unwrap();
}
}
Running this on my MacBook Pro m1 for fibo(29) takes ~6.6 seconds and shows ~400% CPU. Timed crudely with time.
Now, here is the thing, when I replace that join! with separate `awaits like so:
let f1 = Self::fibo(n - 1).await;
let f2 = Self::fibo(n - 2).await;
f1 + f2
it runs much faster. Completes in only 0.5 seconds and only uses 100% CPU.
This is somewhat surprising. We get concurrency, we get tasks spread over cores, it runs significantly more slowly!
The Asynchronous Programming in Rust book: join! - Asynchronous Programming in Rust specifically says not to do the latter "To correctly run the two futures concurrently, use futures::join!:"
In this case, weird as it is, that advice is not good!
What do you thing about this?
Edit: Oops for got the --release. Didn't make such a huge difference though. Timings above edited.
