Uninformed: Informative Information for the Uninformed

Vol 1» 2005.May


Problems with new approach

In every algorithm there can exists small problems, that make the algorithm far from optimal. This problem applies to the new approach presented above. The algorithm presented above has not been optimized for performance. The algorithm runs in a time of O(N2), which carries quite a load if there are more than 600 or so nodes.

The reason that the algorithm is so time consuming is that instead of implementing a Breadth First Search (BFS), a Depth First Search (DFS) was implemented, in the is_path_to function which computes all possible paths to and from a given node. Depth First Search is much more expensive than Breadth First Search, and because of that the algorithm may in some rare cases suffer. If the reader is interested in how to implement a more efficient algorithm for finding the dominators, the reader should check out Compiler Design & Implementation by Steven S. Muchnick.

It should be noted that in future of this plug-in there will be optimizations made to the code. The optimizations will specifically deal new implementations of a Breadth First Search instead of the Depth First Search, as well as other small optimizations.