Bug #41736 for Graph: getting predecessors is unreasonably slow for large graphs

Mon Dec 15 19:14:10 2008 jonathanmoorephd [...] gmail.com - Ticket created

Subject:

getting predecessors is unreasonably slow for large graphs

When getting predecessors for a node, the code appears to loop over all edges and so the time required is proportional to the number of edges rather than the degree of nodes, which is what one would reasonably expect. This makes the module very slow to use on large graphs.

Sat Dec 20 14:21:47 2008 JHI [...] cpan.org - Correspondence added

Could you point out the loop you mention and/or provide me with a test case? I tried creating large test graphs of various sizes and then asking for predecessors, and the response time didn't see to be a function of the number of edges.

Sat Dec 20 14:21:47 2008 The RT System itself - Status changed from 'new' to 'open'

Sun Dec 21 18:16:35 2008 jonathanmoorephd [...] gmail.com - Correspondence added

Subject:	Re: [rt.cpan.org #41736] getting predecessors is unreasonably slow for large graphs
Date:	Sun, 21 Dec 2008 18:16:22 -0500
To:	bug-Graph [...] rt.cpan.org
From:	"Jonathan Moore" <jonathanmoorephd [...] gmail.com>

Thanks for your reply. It seems that the behavior does not occur with a minimal directed graph but does occur when you add attributes to the edges. The inner loop, I think, is at Graph::_edges_to beginning at line 836 as below: while (my ($ei, $ev) = each %{ $Ei }) { next unless @$ev; push @e, [ $ei, $ev ] if $ev->[-1] == $vi && !$ev{$ei}++; The attached file gives a test case and you should be able to see the dependence on number of edges with the calls below, e.g. perl -d:DProf ./testPred.pl 100 1000 10000 perl -d:DProf ./testPred.pl 100 3000 10000 Thanks, Jonathan On Sat, Dec 20, 2008 at 2:21 PM, Jarkko_Hietaniemi via RT <bug-Graph@rt.cpan.org> wrote: Show quoted text

> <URL: https://rt.cpan.org/Ticket/Display.html?id=41736 > > > Could you point out the loop you mention and/or provide me with a test case? I tried creating > large test graphs of various sizes and then asking for predecessors, and the response time > didn't see to be a function of the number of edges. > > >

-- 617 413 6423

Message body is not shown because sender requested not to inline it.

Fri Dec 26 21:44:42 2008 jhi [...] iki.fi - Correspondence added

Subject:	Re: [rt.cpan.org #41736] getting predecessors is unreasonably slow for large graphs
Date:	Fri, 26 Dec 2008 21:44:26 -0500
To:	bug-Graph [...] rt.cpan.org
From:	Jarkko Hietaniemi <jhi [...] iki.fi>

Jonathan Moore via RT wrote: Show quoted text

> Queue: Graph > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=41736 >

Please try with Graph 0.87. Show quoted text

> Thanks for your reply. It seems that the behavior does not occur > with a minimal directed graph but does occur when you add attributes > to the edges. The inner loop, I think, is at Graph::_edges_to > beginning at line 836 as below: > while (my ($ei, $ev) = each %{ $Ei }) { > next unless @$ev; > push @e, [ $ei, $ev ] > if $ev->[-1] == $vi && !$ev{$ei}++; > > The attached file gives a test case and you should be able to see the > dependence on number of edges with the calls below, e.g. > > perl -d:DProf ./testPred.pl 100 1000 10000 > perl -d:DProf ./testPred.pl 100 3000 10000 > > Thanks, > Jonathan > > > On Sat, Dec 20, 2008 at 2:21 PM, Jarkko_Hietaniemi via RT > <bug-Graph@rt.cpan.org> wrote:

>> <URL: https://rt.cpan.org/Ticket/Display.html?id=41736 > >> >> Could you point out the loop you mention and/or provide me with a test case? I tried creating >> large test graphs of various sizes and then asking for predecessors, and the response time >> didn't see to be a function of the number of edges. >> >> >>

> > >

Tue Dec 30 12:59:44 2008 jonathanmoorephd [...] gmail.com - Correspondence added

From:

jonathanmoorephd [...] gmail.com

When I profiled again using Graph 0.89, the overall performance was much better and the previous bottleneck in _edges_to was no longer apparent. I think this can be closed now. Thanks very much for your help. On Fri Dec 26 21:44:42 2008, jhi@iki.fi wrote: Show quoted text

> Jonathan Moore via RT wrote:

> > Queue: Graph > > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=41736 >

> > Please try with Graph 0.87. >

Tue Dec 30 13:49:16 2008 jhi [...] iki.fi - Correspondence added

Subject:	Re: [rt.cpan.org #41736] getting predecessors is unreasonably slow for large graphs
Date:	Tue, 30 Dec 2008 13:48:57 -0500
To:	bug-Graph [...] rt.cpan.org
From:	Jarkko Hietaniemi <jhi [...] iki.fi>

Jonathan Moore via RT wrote: Show quoted text

> Queue: Graph > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=41736 > > > When I profiled again using Graph 0.89, the overall performance was much > better and the previous bottleneck in _edges_to was no longer apparent. > > I think this can be closed now. Thanks very much for your help. > > On Fri Dec 26 21:44:42 2008, jhi@iki.fi wrote:

>> Jonathan Moore via RT wrote:

>>> Queue: Graph >>> Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=41736 >

>> Please try with Graph 0.87. >>

> >

Great, thanks. The 0.90 is out now.

Tue Dec 30 19:23:06 2008 JHI [...] cpan.org - Correspondence added

Closing this ticket.

Tue Dec 30 19:23:07 2008 JHI [...] cpan.org - Status changed from 'open' to 'resolved'