Add interpolation options to rolling quantile
State: closed

It version 0.21.0 rolling quantile started to use linear interpolation, it broke backward compatibility.

Regular (not rolling) quantile supports these interpolation options: `linear`, `lower`, `higher`, `nearest` and `midpoint`.
This commit adds the same options to moving quantile.

Performance issues of this commit (note: I re-run benchmarks, see message below) 
This code has 15% worse performance on benchmarks with small values of window (`window=10`). This is because loop inside `roll_quantile` now contains switch.
I tried to replace switch with callback but it led to even worse performance. Even if I move some of the code to new function (without any change in logic) it still makes performance much worse.
How bad is it? Could you please give me an advice on how to arrange the code such that it has the same performance?

- [ ] closes #xxxx
- [ ] tests added / passed
- [ ] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry


Labels:
name: Enhancement
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode

Comments:
what issue are you addressing here? if its about performance, pls show representative benchmarks (or run the asv)

> it version 0.21.0 rolling quantile started to use linear interpolation, it broke backward compatibility.

if you read this: https://github.com/pandas-dev/pandas/pull/16247/files not sure what to say here, it had different defaults.
re-reading your changes I see that you are trying to fix perf. can you run the asv's here and show the results. (you *may* need to add one if the case you are addressing is not covered).
@jreback, hi,

There is no issue related to this pull request. Do I need to create an issue first?

I am aware about the BUG that you referenced. Company at which I work uses rolling quantile without interpolation, when we updated pandas version, we discovered that behavior of rolling quantile has changed and there is no way to get non-interpolated results.

I re-ran asv benchmarks for rolling quantile (default version uses linear interpolation) and it did not show significant changes, sorry for confusing you.
```
BENCHMARKS NOT SIGNIFICANTLY CHANGED
```
I added new benchmarks for different interpolation options. I cannot compare them with previous results because interpolation options were not supported (supporting them is the purpose of this commit). Here are new benchmarks:
```
[ 20.00%] ··· Running rolling.Quantile.time_quantile             1.37±0.2ms;...
[ 40.00%] ··· Running rolling.Quantile.time_quantile_higher      1.38±0.2ms;...
[ 60.00%] ··· Running rolling.Quantile.time_quantile_lower       1.37±0.2ms;...
[ 80.00%] ··· Running rolling.Quantile.time_quantile_midpoint    1.38±0.2ms;...
[100.00%] ··· Running rolling.Quantile.time_quantile_nearest     1.37±0.2ms;...
```
I am not sure if I should add this new benchmarks to the commit. Should all the code be covered by benchmarks?
@kornilova-l some linting issues: https://travis-ci.org/pandas-dev/pandas/jobs/358799956#L3014
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=h1) Report
> Merging [#20497](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/0ae19a156e3d0307bbb5c022b40ef49186e995bc?src=pr&el=desc) will **increase** coverage by `0.06%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/20497/graphs/tree.svg?height=150&src=pr&token=eZ4WkYLtcO&width=650)](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #20497      +/-   ##
==========================================
+ Coverage   91.77%   91.83%   +0.06%     
==========================================
  Files         153      153              
  Lines       49263    49320      +57     
==========================================
+ Hits        45213    45295      +82     
+ Misses       4050     4025      -25
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.23% <100%> (+0.06%)` | :arrow_up: |
| #single | `41.87% <60%> (+0.01%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `93.9% <ø> (ø)` | :arrow_up: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.17% <ø> (ø)` | :arrow_up: |
| [pandas/core/window.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvd2luZG93LnB5) | `96.3% <100%> (ø)` | :arrow_up: |
| [pandas/core/dtypes/concat.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZHR5cGVzL2NvbmNhdC5weQ==) | `99.16% <0%> (-0.02%)` | :arrow_down: |
| [pandas/core/strings.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc3RyaW5ncy5weQ==) | `98.32% <0%> (-0.02%)` | :arrow_down: |
| [pandas/api/extensions/\_\_init\_\_.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2FwaS9leHRlbnNpb25zL19faW5pdF9fLnB5) | `100% <0%> (ø)` | :arrow_up: |
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `84.14% <0%> (ø)` | :arrow_up: |
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `96.63% <0%> (ø)` | :arrow_up: |
| [pandas/core/indexes/datetimelike.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9kYXRldGltZWxpa2UucHk=) | `96.72% <0%> (+0.01%)` | :arrow_up: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `92.04% <0%> (+0.02%)` | :arrow_up: |
| ... and [2 more](https://codecov.io/gh/pandas-dev/pandas/pull/20497/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=footer). Last update [0ae19a1...9cc7a71](https://codecov.io/gh/pandas-dev/pandas/pull/20497?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

@kornilova-l 

> There is no issue related to this pull request. Do I need to create an issue first?

Generally create an issue first. Since you already created a PR no need then.

Ok so perf is basically unchanged on small series. If you want to add an asv for that is ok.



linting issue:

```pandas/core/window.py:1289:1: W293 blank line contains whitespace```

you can run
``LINT=TRUE ci/lint.sh`` to see
@TomAugspurger comments?
@WillAyd if you'd have a look
@WillAyd I tried to replace `range` with `prange` but it does not compile because calling `skiplist.get` requires gil: `Calling gil-requiring function not allowed without gil` did I miss something?
ok we don't / can't use ``prange`` anywhere in the codebase. only you can use ``nogil``
@jreback but still using `nogil` is not possible because there are `gil-requiring` function calls
The only gil-requiring function call at the time of that comment was `int` which is why I asked if it was possible to use the C-style cast instead. I think if you did those in combination it would work. I see that you since added the `round` built-in so to get `nogil` to work you'd have to use a C-style version of that as well. 

I did something similar in https://github.com/pandas-dev/pandas/pull/20405/files which you may be able to reference
About `nogil`: I changed `int()` to `<int>` and also removed `round()` function, but after adding `nogil` compiler still complains about `skiplist` methods (`skiplist.insert`, `skiplist.remove`, `skiplist.get`).

One of compiler messages:
```
Error compiling Cython file:
------------------------------------------------------------
...
                        elif idx_with_fraction - idx < 0.5:
                            output[i] = skiplist.get(idx)
                        else:
                            output[i] = skiplist.get(idx + 1)
                    elif interpolation_type == MIDPOINT:
                        vlow = skiplist.get(idx)
                                          ^
------------------------------------------------------------

pandas/_libs/window.pyx:1474:43: Calling gil-requiring function not allowed without gil
```
Finally code works with `nogil`

There is another problem:
Some tests in python 2.7 environment fail. All failed tests use `midpoint` interpolation. I am almost sure that it is related to https://github.com/numpy/numpy/issues/7163 
Tests compare results of `quantile` and `rolling_quantile`. `quantile` uses `np.percentile` which used to have a bug in 'midpoint' interpolation.

What should I do with failed tests? Is it okay to test `midpoint` separately and not compare it to `quantile`?
just skip if < numpy 1.12 on those tests
In ASV benchmarks I added `interpolation` as a parameter to `setup`. Performance is the same compared to results that I posted earlier 
```
[100.00%] ··· Running rolling.Quantile.time_quantile                 1.38±0.2ms;...
```
I will rebase branch
Now there are lots of commits from master :( hope I did rebasing correctly
Shouldn't be including the commits of other contributors - how did you rebase this? Need to figure out how to undo that and only replay your commits on top of master
Finally I did rebasing correctly (I hope)
Should I squash these 13 commits into one?
thanks @kornilova-l nice patch!

generally you don't need to squash, you can do it if you want to make things more readable / easier if you want. but not necessary to merge.