Friday, February 22, 2008

Improved alarms library

Until now, Factor has had several means of scheduling recurring tasks and timeouts:
  • You could just spawn a thread and call sleep
  • Recurring UI timers, with 10ms resolution
  • One-off alarms, with 100ms resolution
  • I/O timeouts system with 5 second resolution

None of these were satisfactory. The thread approach is fine for the most part, except there was no way to interrupt a sleeping thread. The other two approaches had low resolution because they relied on a thread which would poll some kind of timer queue for events.

Alarms


I unified all these approaches with a new alarms vocabulary which does not rely on polling, instead an alarm thread is woken up when alarms are added. To achieve this, I added a new word to the threads vocabulary named nap. It is like sleep except other threads can interrupt the sleep with interrupt; the nap word returns a boolean indicating whether it was interrupted or not.

The alarm thread naps until the next alarm is set to go off, however if a new timer is added in the mean time which would go off sooner, the thread is interrupted. This means it no longer has to poll regularly, and also increases accuracy.

The alarm API is straightforward:
  • add-alarm ( quot time frequency -- alarm ) adds an alarm which first fires at time and then every frequency time units thereafter. The timestamp and time deltas are the timestamp and dt types defined in the calendar vocabulary; no need to mess around with integers represeting milliseconds.
  • cancel-alarm ( alarm -- ) cancels a pending alarm.
  • later ( quot delay -- alarm ) runs a quotation once, a fixed delay from now. Code which calls it looks almost like English:
    [ "Hello world" print ] 5 minutes later

Alarms are stored in a min-heap for efficiency, and the cancel-alarm word uses a new feature of heaps, namely the ability to remove an entry in O(log n) time.

Strongly-typed timeouts


Until now the set-timeout word for streams, as well as timeouts for the process launcher took integers denoting time counts in milliseconds. That is so 1970's. Instead the new style is strongly-typed time units from the calendar library:
1 minutes stdio get set-timeout

The sleep word is generic, and if calendar is loaded it has methods which accept time units as well:
5 minutes sleep
30 seconds sleep
10 milliseconds sleep

Timeouts for locks, semaphores, promises, futures, message sends


The concurrency.messaging library for Erlang-style message passing finally supports timeouts (strongly-typed, as above). The other concurrency abstractions do as well. All of this is implemented on top of the same underlying framework which in turn sits on top of alarms, which in turn use nap.

1 comment:

_ said...

I once had an interview where I was asked how I would implement something similar. I suggested a min-heap but the interviewer insisted on a sorted linked list. His reasoning was that you can remove all expired timers in O(1) but he missed the fact that finding the first unexpired timer was O(n).

Good to know that I'm not alone ;-)