Cython implementation

[chaserileyroberts]

It would be nice if the contraction algorithms (especially optimal) was written in Cython. This could give really big speed boosts to the search algorithms.

[dgasmith]

I didn't quite realize you could write:

cdef set indicies = set("abcd")

which appears to work quite nicely. This kind of implementation would be rather straightforward and would remove the Python overhead. There are likely better C representations rather than defaulting to CPython objects in the future, but this would be a much heavier project.

[chaserileyroberts]

I agree. I think just a straight port with cdefs should be the first step.

[dgasmith]

A simple test running cythonize with -O3 over the code base results in a 30-50% improvement in path finding performance.

[jcmgray]

Using pypy also gives a decent speed-up (~300% for the 'dp' algorithm in some cases), suggesting a thorough cythonization might also be pretty beneficial.

[dgasmith]

Thats pretty impressive. I think I could write up the Cython pretty quickly, my main hesitation at the moment is distribution. With ~3M/downloads a month currently, I worry that messing up the distribution part could be fairly disruptive. I would want to pull in someone with previous experience distributing Cython on PyPI to help make sure it goes off without a hitch.

As a note Cython on conda is pretty trivial and I feel comfortable with that channel.

[jcmgray]

Yeah this is not something I have experience with either.

I guess one question would be whether to maintain cython and python versions of the relevant bits (which would probably be quite stable code wise). So that e.g. opt_einsum would still run simply under pypy?

[dgasmith]

@Thenerdstation Do you have experience with this? I think we are at the point where we are to code this up, I just worry about missing a Cython gotcha and causing a lot of turmoil.

[jcmgray]

I note that one possibility now is just to type-annotate opt_einsum and then let cython do its thing in pure-python mode, though this might not maximize performance.

[chaserileyroberts]

I've actually not used cython myself yet, so I'm not sure I know any gotchas ahead of time.

[dgasmith]

Since we are keeping with the NumPy Python deprecation cycle (see here) as it is our only dependency we should be able to drop Python 3.5 on NumPy's next release which would enable us to add type annotations. Though functions like contract may have to remain Any since they rely pretty heavily on duck typing.

Adding type annotations is something I have been eyeing anyway. I now use it in my other projects and find it quite useful.

@Thenerdstation Thanks for checking in, I will ask a few groups that have such experience if they have time. With the Cython pure-python mode we can have Cython optional and only release it on Conda for now as well.