PERF: Cythonize groupby transforms #4095
State: closed

closes - #4095 - adding Cythonized versions of `shift`, `cumprod` and `cumsum`, along with a helper `GroupBy._cython_transform` that other cythonized transform-ops could be added to.

I'm using fused types here instead of adding to `generated.pyx` - as far as I can tell that is working well, looking back through the old issues (#255) it looks like that wasn't done originally because of older versions of Cython?
### 0.16.2

```
In [17]: df = pd.DataFrame({'i':range(1000) * 1000, 
                            'f':np.linspace(0, 2000, 1000000),    
                            'f2':np.linspace(1, 2, 1000000)})

In [18]: %timeit df.groupby('i').cumsum()
1 loops, best of 3: 614 ms per loop

In [19]: %timeit df.groupby('i').shift()
1 loops, best of 3: 499 ms per loop
```
### PR

```
In [2]: %timeit df.groupby('i').cumsum()
10 loops, best of 3: 58.6 ms per loop

In [3]: %timeit df.groupby('i').shift()
10 loops, best of 3: 73.4 ms per loop
```


Labels:
name: Groupby
name: Performance
description: Memory or execution speed performance

Comments:
Travis build is failing with the message below - which seems like it might be an out of memory error?

```
 gcc: internal compiler error: Killed (program cc1)
 Please submit a full bug report, with preprocessed source if appropriate.
```

@jreback - any guesses on why the Travis build is failing?  It builds fine locally on windows, also worked in a linux vm.

I think this doesn't build under cython 0.19.1 (our min version).

@jreback I'm not sure that's the problem, I just downgraded and it built locally.

looks pretty odd: https://travis-ci.org/pydata/pandas/jobs/77861783, `gcc kill`, no idea :<

This could indicate a gcc memory problem.  Refactoring into smaller files should make it easier to compile. 

@jreback - this is actually building ok now; I didn't do anything but rebase.

why don't we put this in generate_code.py so all the groupby code is together (I know this doesn't actually need generation as it uses the fused types)

as an aside I suspect we can use fused types with quite a bit of the existing groupby code

need some asv benches for this

@jreback - updated for your comments, moved the cython into generated.pyx, added some benches, and refactored `BaseGrouper` to put the cythonized `transform` methods alongside `aggregation`.

```
  [b2a547e8] [d94947e]
-    10.37s     8.38ms      0.00  groupby.groupby_transform_cythonized.time_groupby_transform_shift
-    13.68s     6.76ms      0.00  groupby.groupby_transform_cythonized.time_groupby_transform_cumsum
-    13.59s     6.70ms      0.00  groupby.groupby_transform_cythonized.time_groupby_transform_cumprod
```

@jreback, is there a standardized way to deal with integer overflows?  running into that on `cumprod` - in 0.17.0 the overflowed values were just passed back through.

``` python
In [26]: pd.__version__
Out[26]: u'0.17.0'

In [27]: df = pd.DataFrame({'key': ['b'] * 100, 'value': 2})

In [32]: df.groupby('key').cumprod().dtypes
Out[32]: 
value    int64
dtype: object

In [28]: df.groupby('key').cumprod()
Out[28]: 
         value
0            2
1            4
2            8
3           16
4           32
5           64
6          128
7          256
8          512
9         1024
10        2048
11        4096
12        8192
13       16384
14       32768
15       65536
16      131072
17      262144
18      524288
19     1048576
20     2097152
21     4194304
22     8388608
23    16777216
24    33554432
25    67108864
26   134217728
27   268435456
28   536870912
29  1073741824
..         ...
70           0
71           0
72           0
```

In this case one of the overflowed values happens to be `iNaT` so the existing cython logic wants to promote this float (but still the wrong answer because it happens after the calc).  

``` python
In [24]: pd.__version__
Out[24]: '0.17.0+21.g37ea209.dirty'

In [25]: df.groupby('key').cumprod().tail()
Out[25]: 
    value
95      0
96      0
97      0
98      0
99      0

In [26]: df.groupby('key').cumprod().dtypes
Out[26]: 
value    float64
dtype: object
```

Is the right thing just to define the calculation in terms of floats, and then try to convert back if we can?  Or try to match the 0.17.0 behavior?

this should always be a float calc

@jreback, if you want to take another look, I think I've got your comments addressed.  

The reference tests (e.g. `gb.cumsum() ==  gb.apply(lambda x:x.cumsum()`) have gotten pretty complex - I probably need to add some simpler ones with hard-coded output too.

@chris-b1 ok, looks reasonable. pls rebase / squash. ping when green.

@chris-b1 if you could update would be gr8. trying to get this in for 0.17.1

@jreback - this is updated (also added whatsnew) - let me know if it needs anything else.

merged via https://github.com/pydata/pandas/commit/b07dd0cbd6d18c55aaa0043d85f42a483eab7dbb

thanks!