Performance issues with large graphs

[jameshanlon]

Some recent work looking at the performance of 'path exists' queries shows that the runtime of netlist-paths falls behind Fusion Compiler in large designs. See the following results, where at <= 256 nodes performance is better but >256 nodes performance is worse:

In each test the netlist is loaded once, and a path exists query is performed for each node.

The following table shows the time to execute the query is linearly related to the number of vertices:

The code that is timed in the above table:

waypoint = py_netlist_paths.Waypoints(egr_port, ing_port)
path_exists = netlist.path_exists(waypoint)

Using valgrind --tool=callgrind to profile the execution of netlist-paths highlights the following:

• 55% Boost DFS.
• 25% Waypoints and vertex search.

The first may be explained by the boost::graph algorithm incurring overheads for being a libary routine, and there being potential for optimisations specific to the netlist-paths use case.

The second is due mainly to there being a loop over all vertices in the graph.

Callgrind output:
callgrind.out.8165.txt