PERF: vectorize _interp_limit
State: closed

xref https://github.com/pandas-dev/pandas/issues/16584

Here are the timings vs. master

```
       before           after         ratio
     [ff0d1f4d]       [6b1552f1]
-      12.3±0.3ms      2.28±0.04ms     0.18  frame_methods.Interpolate.time_interpolate_some_good_infer
-      12.6±0.7ms      1.15±0.01ms     0.09  frame_methods.Interpolate.time_interpolate_some_good
-           1.30s         53.8±1ms     0.04  frame_methods.Interpolate.time_interpolate

```

I still need to time vs 0.20.1 (will post those timings later, have to run for a bit now). I may have one more spot to optimize.

Labels:
name: Missing-data
description: np.nan, pd.NaT, pd.NA, dropna, isnull, interpolate
name: Performance
description: Memory or execution speed performance

Comments:
Also, the master and 0.20.1 versions scale poorly with `limit`, but that's not benchmarked anywhere. Here's some timings

limit / version | 0.20.1  | master | interp-perf
--------------- | ------- | ------ | -----------
None            | 42.2 ms | 1.37 s | 43.8 ms
50              | 1.45 s  | 1.33 s | 66.2 ms
500             | 1.40  s  | 1.36 s | 62.5 ms

So we're slightly slower than 0.20.1 for the default, but much faster with any limit (notice the units).

I'll add a benchmark for `limit` and `direction`. Anyone know if there's a way to run new benchmarks against old commits in asv?
Just finished vs. 0.20.1, and they're essentially the same (I think the first one is my branch, 0.20.1 is second).

```
· Running 6 total benchmarks (2 commits * 1 environments * 3 benchmarks)
[  0.00%] · For pandas commit hash b2bbd1bf:
[  0.00%] ·· Building for conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt...........................................................................................
[  0.00%] ·· Benchmarking conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 16.67%] ··· Running frame_methods.Interpolate.time_interpolate                                                                                  44.8±0.3ms
[ 33.33%] ··· Running frame_methods.Interpolate.time_interpolate_some_good                                                                       1.09±0.03ms
[ 50.00%] ··· Running frame_methods.Interpolate.time_interpolate_some_good_infer                                                                 2.41±0.01ms
[ 50.00%] · For pandas commit hash 20baf972:
[ 50.00%] ·· Building for conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt...
[ 50.00%] ·· Benchmarking conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 66.67%] ··· Running frame_methods.Interpolate.time_interpolate                                                                                  46.7±0.9ms
[ 83.33%] ··· Running frame_methods.Interpolate.time_interpolate_some_good                                                                       1.08±0.02ms
[100.00%] ··· Running frame_methods.Interpolate.time_interpolate_some_good_infer                                                                 2.44±0.07ms
BENCHMARKS NOT SIGNIFICANTLY CHANGED.
```
Oh sorry that's not used anymore. Just left it around for testing that my new implementation was the same. I'll remove it. 

> On Jun 3, 2017, at 13:17, Jeff Reback <notifications@github.com> wrote:
> 
> @jreback commented on this pull request.
> 
> In pandas/core/missing.py:
> 
> > @@ -630,3 +632,65 @@ def fill_zeros(result, x, y, name, fill):
>              result = result.reshape(shape)
>  
>      return result
> +
> +
> +def _interp_limit0(invalid, fw_limit, bw_limit):
> +    "Get idx of values that won't be filled b/c they exceed the limits."
> +    for x in np.where(invalid)[0]:
> +        if invalid[max(0, x - fw_limit):x + bw_limit + 1].all():
> should rewrite this as well
> 
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub, or mute the thread.
> 

# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=h1) Report
> Merging [#16592](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/31e67d5d834bd1754e1ce5cdf6725c54bf06a01d?src=pr&el=desc) will **increase** coverage by `0.17%`.
> The diff coverage is `90.9%`.

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

```diff
@@            Coverage Diff             @@
##           master   #16592      +/-   ##
==========================================
+ Coverage   90.75%   90.92%   +0.17%     
==========================================
  Files         161      161              
  Lines       51097    49265    -1832     
==========================================
- Hits        46372    44795    -1577     
+ Misses       4725     4470     -255
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.68% <90.9%> (+0.09%)` | :arrow_up: |
| #single | `40.22% <9.09%> (+0.05%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/missing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvbWlzc2luZy5weQ==) | `84.54% <90.9%> (+0.27%)` | :arrow_up: |
| [pandas/core/computation/expressions.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tcHV0YXRpb24vZXhwcmVzc2lvbnMucHk=) | `0% <0%> (-90.48%)` | :arrow_down: |
| [pandas/io/msgpack/\_version.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2lvL21zZ3BhY2svX3ZlcnNpb24ucHk=) | `44.65% <0%> (-0.22%)` | :arrow_down: |
| [pandas/io/formats/style.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvc3R5bGUucHk=) | `100% <0%> (+4.07%)` | :arrow_up: |
| [pandas/core/util/hashing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdXRpbC9oYXNoaW5nLnB5) | `98.34% <0%> (+5.37%)` | :arrow_up: |
| [pandas/io/json/json.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2lvL2pzb24vanNvbi5weQ==) | `100% <0%> (+9.63%)` | :arrow_up: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `100% <0%> (+19.01%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/16592?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/16592?src=pr&el=footer). Last update [31e67d5...b2bbd1b](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=h1) Report
> Merging [#16592](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/31e67d5d834bd1754e1ce5cdf6725c54bf06a01d?src=pr&el=desc) will **increase** coverage by `0.17%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #16592      +/-   ##
==========================================
+ Coverage   90.75%   90.93%   +0.17%     
==========================================
  Files         161      161              
  Lines       51097    49261    -1836     
==========================================
- Hits        46372    44794    -1578     
+ Misses       4725     4467     -258
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.69% <100%> (+0.1%)` | :arrow_up: |
| #single | `40.22% <6.89%> (+0.05%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/missing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvbWlzc2luZy5weQ==) | `85.25% <100%> (+0.97%)` | :arrow_up: |
| [pandas/core/computation/expressions.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tcHV0YXRpb24vZXhwcmVzc2lvbnMucHk=) | `0% <0%> (-90.48%)` | :arrow_down: |
| [pandas/io/msgpack/\_version.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2lvL21zZ3BhY2svX3ZlcnNpb24ucHk=) | `44.65% <0%> (-0.22%)` | :arrow_down: |
| [pandas/io/formats/style.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvc3R5bGUucHk=) | `100% <0%> (+4.07%)` | :arrow_up: |
| [pandas/core/util/hashing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdXRpbC9oYXNoaW5nLnB5) | `98.34% <0%> (+5.37%)` | :arrow_up: |
| [pandas/io/json/json.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL2lvL2pzb24vanNvbi5weQ==) | `100% <0%> (+9.63%)` | :arrow_up: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `100% <0%> (+19.01%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/16592?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/16592?src=pr&el=footer). Last update [31e67d5...bf88fc7](https://codecov.io/gh/pandas-dev/pandas/pull/16592?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

> i suspect a pure cython impl might be easier to read though (maybe even faster)

Yeah, it's kind of unreadable, and I have no idea what that striding stuff is doing.

I'll leave this open if you want to take a look. I'll tag 0.20.2 early tomorrow morning.
We can also do the cython for 0.21
no this is all fine maybe make an issue for 0.21 to have a look