[kw-pm] [CHALLENGE] Fastest timers

[Matt Sergeant]

I've been working on some code to add timers to Danga::Socket. The 
basic premise is you add a timer with a subroutine of this signature:

   AddTimer( $timeout_in_seconds, $coderef );

And then at some point in time we need to run all the timers that have 
"expired".

It would be nice to be just as fast whether you're using a few timers, 
or thousands.

Here's the current code, using a global array @Timers:

sub AddTimer {
     my $class = shift;
     my ($secs, $coderef) = @_;
     my $timeout = time + $secs;

     # optimise tail insertion
     if (!@Timers || ($timeout >= $Timers[-1][0])) {
         push @Timers, [$timeout, $coderef];
         return;
     }

     # Now where do we insert...
     for (my $i = 0; $i < @Timers; $i++) {
         if ($Timers[$i][0] > $timeout) {
             splice(@Timers, $i, 0, [$timeout, $coderef]);
             return;
         }
     }

     die "Shouldn't get here.";
}

And the code to run the timers is simple:

         my $now = time;
         # Run expired timers
         while (@Timers && $Timers[0][0] <= $now) {
             my $to_run = shift(@Timers);
             $to_run->[1]->($now);
         }

It has been suggested that a binary search might be faster to do the 
inserts, which also leaves the code to run the timers nice and quick, 
but the challenge is to create a simple binary search without using 
recursion.

Can you make it faster? Use Benchmark.pm to prove your methods. 
Remember though that the running of the expired timers needs to be fast 
too, so a hash insert of new timers followed by a linear scan to run 
the timers isn't going to cut it.

Entries should be posted to the list for discussion. The winning entry 
gets either a copy of Advanced Perl Programming, or if the last one of 
those is already gone you can have any (used) book from my bookshelves 
(I'll post a photo of the bookshelves somewhere so you can pick).

Matt.