Cython vs C++
Edit (2008-11-09): Robert Bradshaw posted a patch to my code and the Cython implementation is now a lot faster. Click here to read more.
In a comment on a recent post, Robert Samal asked how Cython compares to C++. The graph below shows a comparison of a greedy critical set solver written in Cython and C++ (both use a brute force, naive, non-randomised implementation of a depth first search):
So things look good until n = 10. In defence of Cython, I must point out that my implementation was a first attempt and I am by no means an expert on writing good Cython code. Also, the Cython code is probably fast enough - in my experience, solving problems (computationally) for latin squares of order 10 is futile, so the code is more convenient for testing out small ideas.
edit: the code is here
edit: Robert's code is here http://sage.math.washington.edu/home/robertwb/cython/scratch/cython-latin/
2008-03-04 05:40:32 UTC
You should post the Cython and C++ code because it looks like there maybe some obvious fixes to the Cython to make it behave better.
2008-03-04 21:01:39 UTC
Does somebody else have some experience in how cython compares
with C/C++? Every once in a while I need to do some computation (something NP-complete or worse in general, so it
usually ends up as an ugly backtracking). I'd be happy to do everything from within Sage (and using python/cython), but I'm not sure, if it is fast enough (or if it getting fast enough, I suppose that cython is improving gradually).
2008-07-07 11:59:22 UTC
After looking quickly into the code, I'm pretty sure some overhead is caused by the __getitem__ and __setitem__ methods, you use to override the  operator.
When calling L[i, j] (or L[i, j] = x), those special methods are resolved at runtime and hence involve additional python mechanism. While they make the code readable, you lose the interest of "cdef" methods which are called much faster.
IMO, a good compromise would be to put the code in __getitem__ into a regular 'cdef getitem()' method, then make __getitem__ as a wrapper of the regular method:
def __getitem__(self, rc):
i, j = rc
return self.getitem(i, j)
cdef int getitem(int i, int j):
... # Put your code here
and replace the L[i, j] by L.getitem(i, j) in your cython code.
Also put "void" return type on cdef method that returns nothing could help a bit.
I'll try to make these changes and run the benchmark again.
2008-11-08 15:12:21 UTC
This graph looked pretty depressing, so I made some optimizations to your code (basically the ones suggested above, and a couple of other glaring things that stood out). The algorithm is still completely the same, and I didn't do any code re-factoring other than __getitem__/__setitem__, just mostly typing things here and there. It's now faster than c++ on my machine for the whole range graphed above (and much faster for small inputs).
Code and diff up at http://sage.math.washington.edu/home/robertwb/cython-latin/
2008-11-11 17:24:47 UTC
Any chance that we might see a plot of the improved data... wouldn't want people to come here and only see the 'depressing' data.
2008-11-11 17:27:12 UTC
Nevermind, I now see the new results up one level.
2011-09-14 02:19:56 UTC
The link to the improved data is dead:
Same for the link to the motivation ("recent post"):
Are these viewable elsewhere?
Thanks a lot for doing this and posting it! Very helpful in any case.
2011-09-14 02:22:59 UTC
Found it! Here's the post with the improved data:
2011-09-14 03:47:40 UTC
Code link is still broken:
2015-10-10 08:12:16.866201 UTC
nice challenge. I've been using cython for a couple of years. it really sucks
Comments are closed.