Hello monks!
I'm facing some performance issues with my algorithm so I ask for your help. I'm using the
Graph module to implement a graph that represents the Linux filesystem. Each vertex is a directory/file/link path from root and each edge is the "relationship" between them. For example for
/a/b/c (assuming
c is a file) you will get 3 vertices
a and
/a/b (dirs) and
/a/b/c (file) and two edges a->/a/b and /a/b->/a/b/c (Actually there is another vertex "/" which is a directory and points to "/a").
The way I initialize the graph is:
my $graph = Graph->new;
$graph->set_vertex_attributes("/", { "type" => "dir" });
my $self = {
graph => $graph
};
Once I fill the graph, I want to have a sub that returns all the possible paths, including links. So for example, assume you have
/a/b/c again and
/p->/a/b then I want it to return
/a,/a/b,/a/b/c,/p,/p/c.
So what I tried to do: after going over all the vertices, I want to find all the links and check if I can replace the target with the link. I also need to support recursive links so if I found changes, I'll do another iteration. The code:
sub extract_paths_from_graph {
my ($self,$paths_href) = @_;
foreach my $vertex ($self->{"graph"}->unique_vertices) {
$paths_href->{$vertex}++;
}
while (1) {
my $found_changes = 0;
foreach my $vertex ($self->{"graph"}->unique_vertices) {
my $type = $self->{"graph"}->get_vertex_attribute($vertex,
+ 'type');
if (index($type,"link") != -1) {
# Ignore cycle in graph to prevent infinite loop
my $target = ($self->{"graph"}->successors($vertex))[0
+];
if (path($target)->subsumes($vertex)) {
next;
}
foreach my $subpath (keys(%{$paths_href})) {
if ($subpath =~ /^$target\// || $subpath =~ /^$tar
+get$/) {
my $new_vertex = $subpath =~ s/^$target/$verte
+x/gr;
$found_changes = 1 unless (defined($paths_href
+->{$new_vertex}));
$paths_href->{$new_vertex}++;
}
}
}
}
last unless ($found_changes);
}
}
My code was very slow and I managed to see that it comes from this method. I used NYTProf to create a profiling report and you can find it
here. It looks like the problem is with the following line which takes to much time:
if ($subpath =~ /^$target\// || $subpath =~ /^$target$/) {
My assumptions are correct? Can you please suggest a better alternative way to perform the check? I though regex here will be the fastest.