PERF: Cythonize Groupby.cummin/cummax (#15048)
State: closed

 - [x] closes #15048
 - [x] tests added / passed
 - [x] passes ``git diff upstream/master | flake8 --diff``
 - [x] whatsnew entry

```

   before     after       ratio
  [6eb705f5] [e8115142]
-     1.08s     1.74ms      0.00  groupby.groupby_cummax_cummin.time_cummax
-     1.09s     1.73ms      0.00  groupby.groupby_cummax_cummin.time_cummin

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.

```

Still need to add some tests to see if this is equivalent to the old implimentation (numpy.minimum.accumulate?). Any early feedback appreciated.

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

Comments:
Random thought, but any presumption on performance vs bottleneck? http://berkeleyanalytics.com/bottleneck/reference.html#bottleneck.move_min (with window = len)
bottleneck will be *way* slower as it will be called in a python loop. The cython grouperby routines have the indexers already and thus everything is a single cython loop.
> bottleneck will be way slower as it will be called in a python loop

Ah, you can't put the bn call in a `with nogil` context manager?
@MaximilianR no, nothing to do with that.

The point of the groupby_* routines is that they take and indexer (already been factorized), and make the results per-group.

bottleneck is for a full 1-d array. Here we have *many* variable sized (the groups) 1-d arrays.
lgtm. pls add a whatsnew note & look at the build log, linting issue with a cython file
## [Current coverage](https://codecov.io/gh/pandas-dev/pandas/pull/15053?src=pr) is 84.75% (diff: 53.84%)
> Merging [#15053](https://codecov.io/gh/pandas-dev/pandas/pull/15053?src=pr) into [master](https://codecov.io/gh/pandas-dev/pandas/branch/master?src=pr) will decrease coverage by **<.01%**

```diff
@@             master     #15053   diff @@
==========================================
  Files           145        145          
  Lines         51220      51232    +12   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43415      43421     +6   
- Misses         7805       7811     +6   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [c71f214...5e8ba63](https://codecov.io/gh/pandas-dev/pandas/compare/c71f214a7024a3a8d679f8c2eafdd4e870d7c216...5e8ba636b1980655a3457a8b14ad96695b3aa76c?src=pr)
Added a whatsnew and a test. I don't think my implementation is entirely correct yet so I am expecting the test I added to fail.

Is there a conventional way to debug cython code? Ideally, I'd like to drop a `pdb.set_trace()`-like functionality to see what's going on.  
copy this to python, debug and assert correctness, then cythonize it. note you will have to hack the calling function (to make sure it is imported / called correctly while you do this).

there are ways to debug cython code, just google. @chrisaycock may be able to elaborate a bit.
The only way I've done debugging with Cython has been to add `print()` statements and to run samples in the Python interpreter. So really _ad hoc_.
Thanks for the tips @jreback and @chrisaycock!  
Made the changes related to your comments @jorisvandenbossche, and added a whatsnew & passing tests @jreback. All green.   
Added additional tests and addressed the the val != val condition @jreback . All green. 
Thanks for the tips @chris-b1, I was able to refactor the algorithm to handle different max/min dtypes.  
@jreback Added the addtional nan test & restructured the tests to pass in min and max values.

Additionally performing cummin/max on `datetime`, `timedeta` and `object` dtypes all raise the same error: `DataError: No numeric types to aggregate`

```
In [16]: df = pd.DataFrame({'A':[5]*5+[6]*5,'B':range(10)})

In [17]: df
Out[17]: 
   A  B
0  5  0
1  5  1
2  5  2
3  5  3
4  5  4
5  6  5
6  6  6
7  6  7
8  6  8
9  6  9

In [18]: df['B'] = df['B'].astype(object)

In [19]: df.groupby('A').cummin()

DataError: No numeric types to aggregate

In [20]: df['B'] = pd.date_range(2015, freq='10min', periods=10)

In [21]: df
Out[21]: 
   A                             B
0  5 1970-01-01 00:00:00.000002015
1  5 1970-01-01 00:10:00.000002015
2  5 1970-01-01 00:20:00.000002015
3  5 1970-01-01 00:30:00.000002015
4  5 1970-01-01 00:40:00.000002015
5  6 1970-01-01 00:50:00.000002015
6  6 1970-01-01 01:00:00.000002015
7  6 1970-01-01 01:10:00.000002015
8  6 1970-01-01 01:20:00.000002015
9  6 1970-01-01 01:30:00.000002015

In [22]: df.groupby('A').cummin()

DataError: No numeric types to aggregate

In [26]: df['B'] = [pd.Timedelta(n, unit='d') for n in range(10)]

In [27]: df
Out[27]: 
   A      B
0  5 0 days
1  5 1 days
2  5 2 days
3  5 3 days
4  5 4 days
5  6 5 days
6  6 6 days
7  6 7 days
8  6 8 days
9  6 9 days

In [28]: df.groupby('A').cummin()

DataError: No numeric types to aggregate
```
thanks @mroeschke 

The other dtypes are fixed in #15054 (e.g. datetime/timedelta).

If you'd do that followup to remove accum would be great!
e.g. in #15054
 
```
In [2]: df
Out[2]: 
   group  int  float string category_string  category_int   datetime                datetimetz  timedelta
0      1    1    4.0      a               a             7 2013-01-01 2013-01-01 00:00:00-05:00   00:00:01
1      1    2    5.0      b               b             8 2013-01-02 2013-01-02 00:00:00-05:00   00:00:02
2      2    3    6.0      c               c             9 2013-01-03 2013-01-03 00:00:00-05:00   00:00:03

In [3]: df.groupby('group').cummin()
Out[3]: 
   int  float  category_int
0    1    4.0             7
1    1    4.0             7
2    3    6.0             9

In [4]: df.groupby('group').cummin(numeric_only=False)
Out[4]: 
   int  float  category_int   datetime                datetimetz  timedelta
0    1    4.0             7 2013-01-01 2013-01-01 05:00:00-05:00   00:00:01
1    1    4.0             7 2013-01-01 2013-01-01 05:00:00-05:00   00:00:01
2    3    6.0             9 2013-01-03 2013-01-03 05:00:00-05:00   00:00:03
```
@mroeschke 

the merged PR fails against master, not sure why the tests didn't catch this.

```
(pandas) bash-3.2$ nosetests pandas/tests/groupby/test_groupby.py  -m cummin_cummax -s 
F
======================================================================
FAIL: test_cummin_cummax (test_groupby.TestGroupBy)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jreback/pandas/pandas/tests/groupby/test_groupby.py", line 5798, in test_cummin_cummax
    tm.assert_frame_equal(result, expected)
  File "/Users/jreback/pandas/pandas/util/testing.py", line 1313, in assert_frame_equal
    obj='DataFrame.iloc[:, {0}]'.format(i))
  File "/Users/jreback/pandas/pandas/util/testing.py", line 1154, in assert_series_equal
    assert_attr_equal('dtype', left, right)
  File "/Users/jreback/pandas/pandas/util/testing.py", line 878, in assert_attr_equal
    left_attr, right_attr)
  File "/Users/jreback/pandas/pandas/util/testing.py", line 1018, in raise_assert_detail
    raise AssertionError(msg)
AssertionError: Attributes are different

Attribute "dtype" are different
[left]:  float64
[right]: int64

----------------------------------------------------------------------
Ran 1 test in 0.044s

FAILED (failures=1)
```

The culprit is this.
https://github.com/pandas-dev/pandas/blob/master/pandas/core/groupby.py#L1895

This only should happen if its an actual integer type on values.dtype (and NOT datetime64/timedelta64/bool)
Apologies for not flagging this last night. I made a naive assumption that travis would catch this and the build would fail:

```
In [6]: df #np.int64 type
Out[6]: 
   A                    B
0  1                    3
1  1                    4
2  1 -9223372036854775808
3  1                    2
4  2                    2
5  2                    3
6  2 -9223372036854775808
7  2                    1

In [7]: df.groupby('A').cummin()
Out[7]: 
     B
0  3.0
1  3.0
2  NaN
3  NaN
4  2.0
5  2.0
6  NaN
7  NaN

```

Thanks for pointing out the root issue. I'll look into addressing it!