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