Kendall tau implementation uses Python mergesort

[iskandr]

I just noticed that the implementation of scipy.stats.kendalltau implements its own mergesort. I suspect that any sorting algorithm, especially one that performs recursive function calls, would be orders of magnitude faster using a C implementation.

[rgommers]

Is this a bottleneck for you? If so, shouldn't be hard to move mergesort to Cython (that's preferred over C here).

[argriffing]

numpy has a few sorts including mergesort I think, but notice that the kendalltau mergesort is instrumented to track the number of exchanges. This exchange count is an ingredient in the tau calculation. Although it wouldn't make sense to switch to an existing non-exchange-counting mergesort implementation, the instrumented mergesort could indeed be implemented in Cython for more speed.

[josef-pkt]

@argriffing Yes, I remember the algorithm was quite tricky. I wouldn't change anything except literal translation into cython.

[iskandr]

It's not a serious bottleneck, the statistic took long enough that I
noticed the delay but it's happening at the end of a much larger
computational pipeline. If the sorting logic is nontrivial then please
leave it as is!
On Nov 24, 2015 5:09 PM, "Josef Perktold" notifications@github.com wrote:

@argriffing https://github.com/argriffing Yes, I remember the algorithm
was quite tricky. I wouldn't change anything except literal translation
into cython.

—
Reply to this email directly or view it on GitHub
#5533 (comment).

[rgommers]

If you noticed it was slow, then it can be sped up. Let's leave this issue open and see if someone feels like moving the thing to Cython without changing the algorithm. Should be a lot faster then.

[behzadnouri]

I opened a pull-request which removes the exchange counting mergesort entirely: #5548

[sturlamolden]

When kendalltau was written we actually experimented with different implementations (three versions, IIRC). One of them was in Cython (which I wrote). I don't recall exactly the reason, but @josef-pkt decided to go with the current. So just a friendly warning, Cython has been tried, but it was not any better when we did.

[josef-pkt]

@sturlamolden One of the reasons not to go with the cython version was that I was the only stats maintainer, and without any experience with cython I didn't want to get the extra maintenance work. Plus, this was supposed to be a computationally efficient implementation.
Otherwise, I don't remember much of the details. IIRC, there should still be somewhere your cython version for the contingency tables version, or Kendall's D, or something like that.

Now, there several maintainers and they have enough experience with cython to implement or maintain whatever works best.

(Aside, I'm currently in a corner with power and sample size calculations where I just want to get the things to work, without expanding any effort on high performance in large samples. But in that case, we can at least resort to fast asymptotic results for large sample data.)

[josef-pkt]

(Another aside:
I have currently no intuition for high speed. I partially following the Julia user mailing list, and they are very strongly into using loops with JIT speedup to avoid temporaries and memory allocation. Some examples here seem to indicate that keeping things in numpy with smarter algorithms can still improve performance quite a bit.)

[sturlamolden]

I suggested some improvements for #5548

[sturlamolden]

For the record, here are the Cython versions I wrote in 2009. They cannot be used as they stand (e.g. using C int instead of intp_t), but we can look at them for comparison with the current implementations:
http://projects.scipy.org/scipy/attachment/ticket/893/tau.pyx