| Subject: | Performance problem: source_vertices in compat02 mode |
Greetings Jarkko
I realize you may not want to waste time fixing compat02 mode problems, but I'm reporting this anyway for form sake. The problem came to my attention via the BioPerl mailing list.
The source_vertices method runs quite slowly on graphs created in compat02 mode: 1000x (!!) slower on the real graph of interestto the guy who reported the problem in BioPerl (a DAG with 1396 nodes and 1755 edges). The timings for this graph on my test program (below) are
v05: 74.061ms
v02: 89.737s
Here's the test program
----------
use strict;
use Benchmark::Timer;
use Graph::Directed;
my $T; # global timer
my($nodes,$edges)=@ARGV;
defined $nodes or $nodes=10;
defined $edges or $edges=int(1.5*$nodes);
my $g05=new Graph::Directed();
my $g02=new Graph::Directed(compat02=>1);
# make random DAGs
for (my $new=1; $new<$nodes; $new++) {
my $old=int rand $new; # grab a random node < $new
$g05->add_edge($old,$new);
$g02->add_edge($old,$new);
}
timer("\$g05->source_vertices: nodes=$nodes, edges=$edges");
my @roots=$g05->source_vertices;
stop();
timer("\$g02->source_vertices: nodes=$nodes, edges=$edges");
my @roots=$g02->source_vertices;
stop();
done();
sub timer {
my($test)=@_;
if ($T) {
$T->stop; $T->report; $T->reset;
} else {
$T=new Benchmark::Timer;
}
$T->start($test);
}
sub stop {$T->stop; $T->report; $T=undef;}
sub done {if ($T) {$T->stop; $T->report;} print STDERR "Done\n";}
----------
All the best,
Nat