Thursday, May 21, 2009

Heaps made simple

This is the third post in the Perl scheduler series. We'll look at the CPAN modules that support our scheduler. As we've kept the design simple, there are only two modules involved (apart from Moose): Heap::Simple and Event.
Each scheduler must have a priority queue where tasks are kept waiting for their execution. These queues typically use a heap. Our heap is kindly provided by Heap::Simple. Heap::Simple claims to be only an interface, so you must also install one of its implementations (XS or pure Perl). The priority of a task is its scheduled execution time (represented as unix time) and Heap::Simple allows us to provide the priorites as object methods. So we initialize the heap like this:
my $heap = Heap::Simple->new( elements => [Object => 'next_time'] )
This tells the heap that its elements will be objects and the next_time method will provide the priority associated with the element. Since we use unix time which is an integer, the ordering of priorities is straightforward. In fact it's the default (numerical, less-than) order provided by the module.
We can add one or more tasks:
$heap->insert( $task, $another_task, @still_other_tasks );
And we can extract all due tasks from the queue:
$heap->extract_upto( time() );
We might also want to inspect all tasks in the queue, without extracting them (for example to save the queue to disk):
my @tasks = $heap->values;

No comments:

Post a Comment