| Subject: | Performance problem: edge attributes slow source_vertices |
Hi Jarkko
source_vertices() slows dramatically when attributes are present. The effect is much greater for edge attributes than vertex attributes. I only checked this in 'normal' mode, not compat02 mode. sink_vertices() also slows down (data not shown in the interest of brevity).
Here are some test runs. The program follows.
Show quoted text
> perl bug.pl 10
nodes=10 edges=9
1 trial of source_vertices: no attributes (825us total)
1 trial of source_vertices: edge attributes (6.668ms total)
1 trial of source_vertices: vertex attributes (1.296ms total)
1 trial of source_vertices: edge and vertex attributes (10.924ms total)
Done
Show quoted text> perl bug.pl 100
nodes=100 edges=99
1 trial of source_vertices: no attributes (5.399ms total)
1 trial of source_vertices: edge attributes (439.657ms total)
1 trial of source_vertices: vertex attributes (9.888ms total)
1 trial of source_vertices: edge and vertex attributes (847.151ms total)
Done
Show quoted text> perl bug.pl 200
nodes=200 edges=199
1 trial of source_vertices: no attributes (10.599ms total)
1 trial of source_vertices: edge attributes (1.756s total)
1 trial of source_vertices: vertex attributes (19.647ms total)
1 trial of source_vertices: edge and vertex attributes (3.268s total)
Done
----------
use strict;
use Benchmark::Timer;
use Graph::Directed;
my $T; # global timer
my($nodes)=@ARGV;
defined $nodes or $nodes=10;
my $g=new Graph::Directed();
my $ge=new Graph::Directed();
my $gv=new Graph::Directed();
my $gev=new Graph::Directed();
# make random DAGs
for (my $new=1; $new<$nodes; $new++) {
my $old=int rand $new; # grab a random node < $new
$g->add_edge($old,$new);
$ge->add_edge($old,$new);
$gv->add_edge($old,$new);
$gev->add_edge($old,$new);
}
map {$ge->set_edge_attribute(@$_,'EDGE','edge')} $ge->edges;
map {$gv->set_vertex_attribute($_,'VERTEX','vertex')} $gv->vertices;
map {$gev->set_edge_attribute(@$_,'EDGE','edge')} $gev->edges;
map {$gev->set_vertex_attribute($_,'VERTEX','vertex')} $gev->vertices;
print 'nodes=',scalar $g->vertices, ' edges=',scalar $g->edges,"\n";
timer("source_vertices: no attributes");
my @roots=$g->source_vertices;
stop();
timer("source_vertices: edge attributes");
my @roots=$ge->source_vertices;
stop();
timer("source_vertices: vertex attributes");
my @roots=$gv->source_vertices;
stop();
timer("source_vertices: edge and vertex attributes");
my @roots=$gev->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";}
----------
Best,
Nat