1 //! A single threaded executor that uses shortest-job-first scheduling.
2 
3 use std::cell::RefCell;
4 use std::collections::BinaryHeap;
5 use std::pin::Pin;
6 use std::task::{Context, Poll};
7 use std::thread;
8 use std::time::{Duration, Instant};
9 use std::{cell::Cell, future::Future};
10 
11 use async_task::{Builder, Runnable, Task};
12 use pin_project_lite::pin_project;
13 use smol::{channel, future};
14 
15 struct ByDuration(Runnable<DurationMetadata>);
16 
17 impl ByDuration {
duration(&self) -> Duration18     fn duration(&self) -> Duration {
19         self.0.metadata().inner.get()
20     }
21 }
22 
23 impl PartialEq for ByDuration {
eq(&self, other: &Self) -> bool24     fn eq(&self, other: &Self) -> bool {
25         self.duration() == other.duration()
26     }
27 }
28 
29 impl Eq for ByDuration {}
30 
31 impl PartialOrd for ByDuration {
partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering>32     fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
33         Some(self.cmp(other))
34     }
35 }
36 
37 impl Ord for ByDuration {
cmp(&self, other: &Self) -> std::cmp::Ordering38     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
39         self.duration().cmp(&other.duration()).reverse()
40     }
41 }
42 
43 pin_project! {
44     #[must_use = "futures do nothing unless you `.await` or poll them"]
45     struct MeasureRuntime<'a, F> {
46         #[pin]
47         f: F,
48         duration: &'a Cell<Duration>
49     }
50 }
51 
52 impl<'a, F: Future> Future for MeasureRuntime<'a, F> {
53     type Output = F::Output;
54 
poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>55     fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
56         let this = self.project();
57         let duration_cell: &Cell<Duration> = this.duration;
58         let start = Instant::now();
59         let res = F::poll(this.f, cx);
60         let new_duration = Instant::now() - start;
61         duration_cell.set(duration_cell.get() / 2 + new_duration / 2);
62         res
63     }
64 }
65 
66 pub struct DurationMetadata {
67     inner: Cell<Duration>,
68 }
69 
70 thread_local! {
71     // A queue that holds scheduled tasks.
72     static QUEUE: RefCell<BinaryHeap<ByDuration>> = RefCell::new(BinaryHeap::new());
73 }
74 
make_future_fn<'a, F>( future: F, ) -> impl (FnOnce(&'a DurationMetadata) -> MeasureRuntime<'a, F>)75 fn make_future_fn<'a, F>(
76     future: F,
77 ) -> impl (FnOnce(&'a DurationMetadata) -> MeasureRuntime<'a, F>) {
78     move |duration_meta| MeasureRuntime {
79         f: future,
80         duration: &duration_meta.inner,
81     }
82 }
83 
ensure_safe_schedule<F: Send + Sync + 'static>(f: F) -> F84 fn ensure_safe_schedule<F: Send + Sync + 'static>(f: F) -> F {
85     f
86 }
87 
88 /// Spawns a future on the executor.
spawn<F, T>(future: F) -> Task<T, DurationMetadata> where F: Future<Output = T> + 'static, T: 'static,89 pub fn spawn<F, T>(future: F) -> Task<T, DurationMetadata>
90 where
91     F: Future<Output = T> + 'static,
92     T: 'static,
93 {
94     let spawn_thread_id = thread::current().id();
95     // Create a task that is scheduled by pushing it into the queue.
96     let schedule = ensure_safe_schedule(move |runnable| {
97         if thread::current().id() != spawn_thread_id {
98             panic!("Task would be run on a different thread than spawned on.");
99         }
100         QUEUE.with(move |queue| queue.borrow_mut().push(ByDuration(runnable)));
101     });
102     let future_fn = make_future_fn(future);
103     let (runnable, task) = unsafe {
104         Builder::new()
105             .metadata(DurationMetadata {
106                 inner: Cell::new(Duration::default()),
107             })
108             .spawn_unchecked(future_fn, schedule)
109     };
110 
111     // Schedule the task by pushing it into the queue.
112     runnable.schedule();
113 
114     task
115 }
116 
block_on<F>(future: F) where F: Future<Output = ()> + 'static,117 pub fn block_on<F>(future: F)
118 where
119     F: Future<Output = ()> + 'static,
120 {
121     let task = spawn(future);
122     while !task.is_finished() {
123         let Some(runnable) = QUEUE.with(|queue| queue.borrow_mut().pop()) else {
124             thread::yield_now();
125             continue;
126         };
127         runnable.0.run();
128     }
129 }
130 
main()131 fn main() {
132     // Spawn a future and await its result.
133     block_on(async {
134         let (sender, receiver) = channel::bounded(1);
135         let world = spawn(async move {
136             receiver.recv().await.unwrap();
137             println!("world.")
138         });
139         let hello = spawn(async move {
140             sender.send(()).await.unwrap();
141             print!("Hello, ")
142         });
143         future::zip(hello, world).await;
144     });
145 }
146