Improve np.histogram performance for uniform bins

[astrofrog]

For the use case where the number of bins is specified by an integer in np.histogram, the use of searchsorted etc. is very inefficient. It's possible to get at least a factor of 5x speedup by being smarter about this case just with Python + Numpy code, and I can get a factor of 30 speedup with Cython.

Would it be worth implementing a more efficient version of that special (yet common) case? If so, I'd be happy to turn this issue into a pull request.

[jaimefrio]

Yes, certainly, do send that PR, please!

Someone suggested somewhere making it a C function not that long ago, but I can't find the a link. If I remember well, my position was to try and make as much as possible of Python + NumPy by special casing the all-bins-are-equal case, before going the C way.

I think using Cython for a single function in a module is not that straightforward, but others more in the know may want to chip in.

[swails]

I have a use-case that would benefit immediately. See mdtraj/mdtraj#734. Synopsis of that PR: np.histogram is the rate-limiting step (computing a radial distribution function) and implementing "our own" histogramming code in Cython gets a 10x performance boost. The resistance to merging the PR comes from not wanting to add maintenance overhead if possible, and making numpy.histogram faster would be much appreciated!

[astrofrog]

I'll try and get a pull request in today for a Python + Numpy implementation, but I do think that we then want to think about adding a C/Cython routine, since it's such a common use case and we can improve the performance a fair bit.

[jaimefrio]

If it can get it from x5 to x30, implementing all or (i'd say preferably) part of it in C is more than welcome. There are several functions in the numnpy.lib module implemented in C. The right place for that code would be numpy/core/src/multiarray/compiled_base.c.

[astrofrog]

Ok - I'll have a PR ready very soon for the pure-Python changes (I can get x10) and then later I can open another PR to switch to C if there is still a net benefit.

[astrofrog]

@jaimefrio see #6100 - let me know what you think!

@swails - the pure-Python/Numpy version in #6100 should provide a speedup of ~10x. Could you try it out and let me know if it works for you?

[ctk3b]

Thanks for implementing this! Just FYI, I also get a 10x speedup for the histogram itself which translate to roughly a 3-4x speedup for the actual radial distribution function calculation.

[jaimefrio]

Closed by #6100.