Programming Servo: the incredibly shrinking timer.
There are a few things programmer are supposed to love to write. Compilers are an absolute number one(I’ve never looked into any). Next, one could perhaps place text editors(again, zero experience). And third only to text editors and compilers, one can presumably find timers.
The Web comes with the infamous setTimeout and setInterval, and so Servo also needs a way to schedule timers.
This is the story of the timer implementation in Servo, and the changes it went through over the years.
And since Servo is probably the oldest still-standing large Rust code-base, it’s also a story of evolution of the Rust ecosystem of libraries, and of the painful lack of libraries in the early days.
So, let’s see how one can build a timer in Rust in five easy evolutionary steps.
The beginning: horribly_inefficient_timers.rs
Our starting point is 2014:
As you can see, each timer spawns a thread, that sleeps for a given time and then sends on a channel. Intervals do so in a loop until the other end of the channel disconnects.
The author, forever lost to git history, named the file horribly_inefficient_timers.rs, so we’ll have to assume spawning a thread for each timer was inefficient in the author’s opinion.
On the other end, one thing can be said in favor of that implementation: it’s short and simple.
The real problem there was the fact that there was no way to cancel the timer, and no way to ensure ordering of timers based on their value, highlighted in the below issue:
What followed was a courageous effort in 2015 by two people, pgonda and benschulz, culminating in a PR fixing the lack of ordering and cancel-ability.
The one thread per timer model remained, as can be seen below:
Variations on a theme(I): two long-running threads
About a year later, in 2016, another PR emerged by asajeffrey, which would switch the threading model to using two long-lived threads, handling as many timers as needed, and still relying on thread::park and thread::Thread::unpark for scheduling.
The benefits there was not spawning one thread per scheduled timer anymore, and the problem was that it still relied on a developer acrobatics to ensure scheduling, as can be seen from the snippet below(which is simply too long to include in its entirety inside a screenshot):
In particular, note the comment at:
referring to the at-the-time-yet-to-merge std::sync::mpsc::Receiver::recv_timeout
The implementation also required a second thread to handle incoming request to schedule new timers:
It also required shut-down related logic, which was added separately by ferjm.
So, at that point, progress was made in terms of the cost of the implementation, at least we can assume so since “one thread per timer” was replaced by “two threads for all timers”, yet the code was still fairly complicated due to a lack of higher-level tools available in libraries. Also, with the timer being a set of separately running threads, one had to worry about eventually shutting those down.
Variations on a theme(II): no (additional) threads
In the meantime,crossbeam_channel ended-up replacing std::sync::mpscalmost everywhere in Servo, including in the timer, however the full capabilities of Crossbream weren’t used yet.
The latest twist to this saga came in the form of a PR by yours truly, that basically removed the entire custom scheduling logic, used crossbeam’s features instead, and collapsed the whole structure into an existing thread, that of the constellation.
By then, what was left of the timer scheduler? Only the below, essentially a struct containing a priority queue, with a few methods to interact with it:
Note that the timer logic consists entirely of what was there before, and what has disappeared is the scheduling of timers via parking/unparking of two threads, as well as the need to shut those threads down eventually.
So where did the scheduling go then?
Thanks to the excellent crossbeam channel and surrounding utilities, we can express our scheduling logic using standard tools without having to implement it ourselves.
First, what is the constellation? As you might know from other articles, the constellation is a thread found in the “main-process” of Servo, that basically works as a stateful broker of messages to various other parts of the system. It is supposed to never block, with some exceptions.
The constellation runs an event-loop inside a thread, consisting of calling handle_request in a loop, until a shutdown flag has been set.
The full select inside handle_request looks something like:
As you can see, this is big and 90% has nothing to do with the current discussion, so let’s take a look at the changes introduced in the PR instead:
First of all, we’ve moved the “state” of the timer onto the Constellation struct, over at:
Inside handle_request, before blocking on the select call, at the beginning of each “turn” of the event-loop, we call into check_timers at:
This will dispatch any timers that are due, and return an optional timeout, thereby scheduling a wake-up for the thread corresponding to the earliest scheduled timer, if necessary. The scheduling is done by calling the Crossbeam utilities after(timeout), or never() depending on whether a timer needs to be scheduled and therefore a timeout is returned.
The trick is then to include the channel returned by either of these utilities into the main select! , thereby ensuring the thread will wake-up to dispatch the next timer, or simply block until the next message comes-in, which could be a message requesting the scheduling of a new timer.
Where did cancel-ability go? It seems to have gotten lost along the way, although I suspect that logic was moved into the script side of things somewhere in component/script/timers.rs.
What about shutdown? That is now a non-issue as the timer isn’t running independently from the constellation anymore.
And that’s it really, Servo got itself a timer consisting of only some minimal mutable state and some logic around a select!.
Thank you Crossbeam.
