Faster cycle detection during optimization

[nouiz]

Currently, the cycle detection needed for the inplace optimization can be time consuming. Her is a few different way to help that:

• More strict algo that is faster to detect
• Incremental algo. Some exists
• c/cython version. Old quick test without adding type with cython gave 25% speed up of that part.

The more strict algo is my prefered current direction (@nouiz). For example, if we allow to be inplace only on variable that have only 1 clients and aren't the result of view or inplace operation, this check can be done in constant time instead of being super linear in the number of node. We can extend this idea to be less strict and allow chain of inplace/view. It is important for many case like CuDNN and scan to allow inplace. Otherwise, the memory buffer allocated in the graph need to be copied.

[gokul-uf]

@nouiz, I believe this could become a part of the Faster optimization phase during compilation GSoC project idea

[nouiz]

Yes. Do you have question?

I would start by making a first hacky version. Just to make sure it speed
up compilation and that it don't slow down too much execution.

For this, go in the file gof/destroyhandler.py. And modify the method:
_contains_cycle()

Call io_toposort() on the graph and do the check in a loop. This will
convert the algo from greather then O(n) to O(n). Later, this can be
changed to O(1).

On Tue, Mar 15, 2016 at 7:02 PM, Gokula Krishnan notifications@github.com
wrote:

@nouiz https://github.com/nouiz, I believe this could become a part of
the Faster optimization phase during compilation GSoC project idea

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#4233 (comment)

[nouiz]

I would profile this on 2 king of example, with convolution on GPU and
another one with scan.

On Wed, Mar 16, 2016 at 1:22 PM, Frédéric Bastien <
frederic.bastien@gmail.com> wrote:

Yes. Do you have question?

I would start by making a first hacky version. Just to make sure it speed
up compilation and that it don't slow down too much execution.

For this, go in the file gof/destroyhandler.py. And modify the method:
_contains_cycle()

Call io_toposort() on the graph and do the check in a loop. This will
convert the algo from greather then O(n) to O(n). Later, this can be
changed to O(1).

On Tue, Mar 15, 2016 at 7:02 PM, Gokula Krishnan <notifications@github.com

wrote:

@nouiz https://github.com/nouiz, I believe this could become a part of
the Faster optimization phase during compilation GSoC project idea

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#4233 (comment)

[nouiz]

For the later version, you need to make a new subclass of Feature. You must implement the method on_input_change() and on_import(). This will allow to test only the nodes introduced in the graph and nodes where its inputs are changed. In those method, just record in the object that it failed and in the method validate() raise an exception (InconsistencyError) and make sure the next call won't raise that error.

[nouiz]

A start and some discussions that help explain it:

https://github.com/Theano/Theano/compare/master...nouiz:faster_topo?expand=1

What need to be done.

• Rebase that branch
• Make a Theano flag that will enable or disable it. If enabled, it should not do the normal cycle detection. To disable it, go in destroy_handler.py, in the validate() method, don't call the cycle detection.
• Run Theano tests while enabling it. There could be failure, they must be investigated to know if this is expected. Some acceptable failure, is if a test check if a node is an inplace node, but that node end up being not inplace, then it is fine.
• Test it with DLT and sb_rnn and make sure it still train well and show optimization and computation time comparison.

[nouiz]

Now it is working in master, so I'll close this issue.
Follow up: #6310