4 ms·
Actually, if the thread runtime maintains its own concept of time, the algorithm doesn't even need to sleep in real time. Once all the threads have been created
by Arnavion 3y ago
Actually, if the thread runtime maintains its own concept of time, the algorithm doesn't even need to sleep in real time. Once all the threads have been created, the thread runtime can notice that all threads are idle and that the next thread to be scheduled is the one at time N, so it can simply update the current time to N and start executing that thread. Repeat for each thread and you'll have your sorted array out without any sleeps.
After all, all the sorting work was already done when the threads started sleeping, having registered themselves with the orchestrator (timer wheel etc) that will eventually wake them up. Actually performing the sleep is not necessary.
I don't know about Haskell, but with Rust the tokio runtime lets you do this using start_paused ( https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.html#method.start_paused https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht... )
- tikhonj 3y agoMy understanding is that this is basically how discrete-event simulations work under the hood. You have a frontier of future events in an appropriate data structure (say, a heap) and then alternate between adding future events into the heap and pulling the next event off the heap. So, modulo several layers of abstraction and a bunch of implementation details I'm glossing over, using a scheduler like this to sort values is just a heapsort :)
- johnday 3y agoActually, if you start working out which one is the next to run, you have reinvented selection-sort and you are no longer linear time. (Hence why this is not a sensible sorting algorithm in reality :) )
- Arnavion 3y agoWhich is why I wrote: >After all, all the sorting work was already done when the threads started sleeping, having registered themselves with the orchestrator (timer wheel etc) that will eventually wake them up.