Write a custom Op with C code for 'roll'

[dwf]

There's a simple implementation mimicking numpy.roll contributed by @mrocklin in pull request #221. However, it uses subtensors and Join, and could probably be sped up quite a bit by writing a custom Op with C code.

This would be a pretty easy task for someone who wanted to become familiar with writing Ops, as it doesn't involve any particularly complicated logic, just permuting things and doing the inverse permutation for the gradient.

All the better if it has a flag that can operate in-place (obviously you need a temporary buffer the size of a single element on the roll axis; @nouiz may have some insight on the most efficient way to do this cache-wise)

[mrocklin]

There was some previous discussion on this topic in this thread
http://groups.google.com/group/theano-users/browse_thread/thread/8e2bb15da0ec7457/94e6aa90deb8d473?lnk=gst&q=roll#94e6aa90deb8d473
I had also implemented roll in an Op by wrapping numpy.roll. This was
faster in some cases but also more specific (see e-mail thread for speed
differences). It is available on my roll_op branch. I'm happy to issue a
pull request for this if people prefer it to the roll function.
https://github.com/mrocklin/Theano/blob/roll_op/theano/tensor/basic.py

I don't know much about making theano fast but I'll contribute my (rather
uninformed) thoughts anyway. Rather than writing a specialized C version
work could be done to make SubTensor and Join more efficient. This would
speed up roll and probably many other things as well. In my experience
excellent code is not built by creating many specialized structures.
Instead excellent code is built by creating a few very efficient and very
robust structures and having all other code rely on them. Subtensor and
Join seem like good candidates for this.

On Wed, Nov 23, 2011 at 3:12 PM, David Warde-Farley <
reply@reply.github.com

wrote:

There's a simple implementation mimicking numpy.roll contributed by
@mrocklin in pull request #221. However, it uses subtensors and Join, and
could probably be sped up quite a bit by writing a custom Op with C code.

This would be a pretty easy task for someone who wanted to become familiar
with writing Ops, as it doesn't involve any particularly complicated logic,
just permuting things and doing the inverse permutation for the gradient.

All the better if it has a flag that can operate in-place (obviously you
need a temporary buffer the size of a single element on the roll axis;
@nouiz may have some insight on the most efficient way to do this
cache-wise)

---

Reply to this email directly or view it on GitHub:
#222

[dwf]

In my experience excellent code is not built by creating many specialized structures.

Indeed, I tend to agree. However, in the specific case of optimizing for speed, which is a major part of Theano's goal, optimizing memory access patterns play a rather crucial role. It can be quite hard to write something that's uniformly fast without special casing.

[nouiz]

I would call this low priority as I think it is not a bottle neck. So what do you mean by nice-to-have tag? Should we create a "low prio" tag?

[dwf]

I meant "Nice-To-Have" as "would be nice, at some point, not necessary and certainly not critical", but yeah, a "Low Priority" tag would make this clear.

[dwf]

(Also, I mainly created this ticket in that it might work well as an exercise for a student who wants to learn to write Ops, so that they start with something simple.)