Theano/Theano — pull request #914 by mrocklin (2012-09-10 19:01:21+00:00)
Title: WIP - New Toposort

This is a work in progress. Do not merge.

I would like to replace gof.graph.io_toposort with something a bit more declarative. In the future I would like to be able to control the order of computation of nodes within a graph at a high level. I've changed around io_toposort to enable this. I have some concerns

1. As it is written it is undoubtedly much slower than the old version. I think we can get it to close to the same speed with memoization/caching
2. Much of the time that toposort is used it seems to be to just get a list of nodes. I've added a list_of_nodes function that should be just as fast for this common case. This function does not guarantee an order.
3. There was a mechanism called orderings to specify additional constraints explicitly. Some FGraph features used this. I have a hack around this but I suspect that I would need to change the orderings code so that it uses functions rather than dicts.
4. new_io_toposort fails lots of tests. This is because the old tests hard-coded the exact order that came out of toposort.

So why would we want the new io_toposort? First, it looks cool and does exactly what it says

return sorted(list_of_nodes(inputs, outputs), cmp=dependence)

Second, we can specify additional orderings just by adding more comparator functions. If you wanted to prefer to schedule GPUOps before CPUOps when possible then you would write the following cmp-function

def gpu_first(a, b):
aval = -1 if isinstance(a.op, GpuOp) else 1
bval = -1 if isinstance(b.op, GpuOp) else 1
return cmp(aval, bval)

And then call

io_toposort(inputs, outputs, [gpu_first])

And we still get a valid topological sort but with gpu ops coming before cpu ops

I'm putting this up as a PR before its ready because
1. It's a lot of work to redo the tests
2. I'm not sure this is something that you all want. It might be slower and it's not tried-and-true.