latest contify.fun

[Stephen Weeks]

> I added some Control.traceCalls to get a breakdown of where time is being spent
> in the new contifier.  They show that most of the time (~ 90%) is spent in the
> dominator analysis, and most of that (~ 90%) is spent in the Vector.foreach that
> builds the graph that is the argument to Graph.dominators.  That seems very
> weird to be spending time there.  It should be a simple pass over the program
> (i.e. < 1 second).  If we can get rid of all that we should be back down close
> to the old time.  I am investigating.

The only nonlinear thing I see is the addEdge function that includes the
(linear) check for if the edge is already in the graph.

	  fun addEdge edge
	    = if Node.hasEdge edge
		then ()
		else (Graph.addEdge (G, edge); ())

My bet is that the problem is due to all of the (Root, j) edges.
						  (* {(Root, j) | j in Jump} *)
						  addEdge {from = Root,
							   to = j_node};
There are ~50,000 jumps.  Doing lots of linear lookups in a 50,000 element list
is not a very good idea :-).  I bet that removing this will solve the problem.
The easiest thing to do would be to keep a bool flag associated with the jump
that lets you tell in constant time if the edge has been added.  You should
probably do the same for funcs as well.

It wouldn't hurt to go through all uses of addEdge with an eye towards this
problem, and avoid the linear lookup if possible.