PERF: slowdown in groupby/resample mean() method

[jorisvandenbossche]

See https://pandas.pydata.org/speed/pandas/#timeseries.ResampleSeries.time_resample?python=3.8&Cython=0.29.21&p-index='datetime'&p-freq='1D'&p-method='mean'&commits=812c3012-71a4cb69

It's from the period there were no benchmarks runs, so no clear indication which commit (range) would be responsible.

Reproducer:

idx = pd.date_range(start="1/1/2000", end="1/1/2001", freq="T")
s = pd.Series(np.random.randn(len(idx)), index=idx)
%timeit s.resample("1D").mean()

Last release:

In [2]: %timeit s.resample("1D").mean()
4.45 ms ± 507 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [3]: pd.__version__
Out[3]: '1.2.1'

on master:

In [2]: %timeit s.resample("1D").mean()
6.33 ms ± 430 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

So around 50% slowdown.
And it seems somewhat specific to mean (eg I don't see a similar slowdown for eg max)

[jorisvandenbossche]

cc @phofl a recent change for grouped mean is #38934. Now, since it was a fix to improve numeric stability, some performance degradation might be expected (but might still be worth checking if there is something to improve)

[phofl]

Can confirm, that this was caused by #38934. But I don't think there is much that we can do, if we want to keep using Kahan summation.

8b2ebdb

%timeit s.resample("1D").mean()
3.84 ms ± 74.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

c2c5eba

%timeit s.resample("1D").mean()
5.37 ms ± 40.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

[jorisvandenbossche]

@phofl in the new code, there is now

                        accum[lab, j] = t
                        out[i, j] = accum[lab, j]

That last line could in principle be out[i, j] = t? That would be one array lookup less, which might give something (although I suppose that might be hardly measurable improvement compared to the additional arithmetic the PR added)

[phofl]

This should be the cumsum part? The mean part updates sum directly

[jorisvandenbossche]

Ah, yes, I was just looking at the beginning of the diff of the PR, that's indeed in the cumsum code

[jorisvandenbossche]

I was googling a bit about the stability of sum in numpy, and saw the mention of pairwise summation, which is said to be almost as good as Kahan summation, but with lower computational cost (https://en.wikipedia.org/wiki/Pairwise_summation). It's also what np.sum uses in most cases.
See the code in numpy here: https://github.com/numpy/numpy/blob/ce82028409c1147a6df62d8f7437e0a9262ee2b7/numpy/core/src/umath/loops_utils.h.src#L73-L138

Now, for a plain sum, that seems quite straightforward, but for a grouped sum, I suppose that would be difficult to use? (since we don't have the numbers we want to sum in one contigous array that can easily be split up)

(to be clear, I am no expert in numerical code and stability, I am just wondering about the trade-offs here, because a 50% slowdown is not nothing for probably one of the most used groupby methods)

[mzeitlin11]

Agreed that pairwise would be best of both worlds, but don't think that could be implemented efficiently because of the issues you mention above. I'd guess that pandas users care more about 50% performance in a common method like .GroupBy.sum than floating point error - maybe we can make Kahan summation opt-in?

Would be pretty straightforward with existing groupby machinery to pass some new argument for accurate fp summation, but would probably end up inconsistent with other parts of our API where we don't allow that. NumPy doesn't even always use pairwise summation - we could also just force users to pass an agg function which will compute the sum with numerical stability if that's their priority.