On Tue May 29 08:21:09 2012, PEVANS wrote:
Show quoted text> Heap is used by Ia::Internals::TimeQueue to implement an efficient queue
> of pending timer events. Without it, we could write a trivial but
> slightly less efficient implementation using an array, at a reschedule
> cost of O(n) rather than O(n log n).
Now patched as attached.
Could be made possibly slightly more efficient by using a binary search
+ splice to insert the new elements, but would require benchmarking to
see if that's actually better than the simple sort.
--
Paul Evans
=== modified file 'Build.PL'
--- Build.PL 2012-05-29 12:16:32 +0000
+++ Build.PL 2012-06-01 08:08:46 +0000
@@ -9,7 +9,6 @@
'Async::MergePoint' => '0.03',
'CPS' => 0,
'Exporter' => '5.57',
- 'Heap' => '0.80',
'IO::Poll' => 0,
'Socket' => '1.95',
'Storable' => 0,
=== modified file 'lib/IO/Async/Internals/TimeQueue.pm'
--- lib/IO/Async/Internals/TimeQueue.pm 2012-05-31 11:53:22 +0000
+++ lib/IO/Async/Internals/TimeQueue.pm 2012-06-01 08:08:46 +0000
@@ -8,22 +8,27 @@
use strict;
use warnings;
-use base qw( Heap::Fibonacci );
use Carp;
-use Heap::Fibonacci;
use Time::HiRes qw( time );
-sub next_time
-{
- my $self = shift;
-
- my $top = $self->top;
-
- return defined $top ? $top->time : undef;
+BEGIN {
+ my @methods = qw( next_time _enqueue cancel _fire );
+ if( eval { require Heap::Fibonacci } ) {
+ unshift our @ISA, "Heap::Fibonacci";
+ require Heap::Elem;
+ no strict 'refs';
+ *$_ = \&{"HEAP_$_"} for @methods;
+ }
+ else {
+ no strict 'refs';
+ *$_ = \&{"ARRAY_$_"} for "new", @methods;
+ }
}
+# High-level methods
+
sub enqueue
{
my $self = shift;
@@ -35,13 +40,97 @@
defined $params{time} or croak "Expected 'time'";
my $time = $params{time};
+ $self->_enqueue( $time, $code );
+}
+
+sub fire
+{
+ my $self = shift;
+ my ( %params ) = @_;
+
+ my $now = exists $params{now} ? $params{now} : time;
+ $self->_fire( $now );
+}
+
+# Implementation using a Perl array
+
+use constant {
+ TIME => 0,
+ CODE => 1,
+};
+
+sub ARRAY_new
+{
+ my $class = shift;
+ return bless [], $class;
+}
+
+sub ARRAY_next_time
+{
+ my $self = shift;
+ return @$self ? $self->[0]->[TIME] : undef;
+}
+
+sub ARRAY__enqueue
+{
+ my $self = shift;
+ my ( $time, $code ) = @_;
+
+ # TODO: This could be more efficient maybe using a binary search insert
+ @$self = sort { $a->[TIME] <=> $b->[TIME] } @$self, my $elem = [ $time, $code ];
+ return $elem;
+}
+
+sub ARRAY_cancel
+{
+ my $self = shift;
+ my ( $id ) = @_;
+
+ @$self = grep { $_ != $id } @$self;
+}
+
+sub ARRAY__fire
+{
+ my $self = shift;
+ my ( $now ) = @_;
+
+ my $count = 0;
+
+ while( @$self ) {
+ last if( $self->[0]->[TIME] > $now );
+
+ my $top = shift @$self;
+
+ $top->[CODE]->();
+ $count++;
+ }
+
+ return $count;
+}
+
+# Implementation using Heap::Fibonacci
+
+sub HEAP_next_time
+{
+ my $self = shift;
+
+ my $top = $self->top;
+
+ return defined $top ? $top->time : undef;
+}
+
+sub HEAP__enqueue
+{
+ my $self = shift;
+ my ( $time, $code ) = @_;
+
my $elem = IO::Async::Internals::TimeQueue::Elem->new( $time, $code );
$self->add( $elem );
return $elem;
}
-sub cancel
+sub HEAP_cancel
{
my $self = shift;
my ( $id ) = @_;
@@ -49,12 +138,10 @@
$self->delete( $id );
}
-sub fire
+sub HEAP__fire
{
my $self = shift;
- my ( %params ) = @_;
-
- my $now = exists $params{now} ? $params{now} : time;
+ my ( $now ) = @_;
my $count = 0;
@@ -74,7 +161,7 @@
IO::Async::Internals::TimeQueue::Elem;
use strict;
-use base qw( Heap::Elem );
+our @ISA = qw( Heap::Elem );
sub new
{
