PERF: performance regression in Series.asof
State: closed

Fix performance regression in Series.asof by avoiding pre-computing nulls and returning value by indexing the underlying ndarray.
- [x] closes #14461 
- [x] add asv benchmark


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

Comments:
@jreback you mean we should always pre-compute nulls for DataFrame?

the answer is probably yes
but you need some perf testing in several scenarios to see that is an asv

## [Current coverage](https://codecov.io/gh/pandas-dev/pandas/pull/14476?src=pr) is 85.26% (diff: 100%)

> Merging [#14476](https://codecov.io/gh/pandas-dev/pandas/pull/14476?src=pr) into [master](https://codecov.io/gh/pandas-dev/pandas/branch/master?src=pr) will increase coverage by **<.01%**

``` diff
@@             master     #14476   diff @@
==========================================
  Files           140        140          
  Lines         50667      50670     +3   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43203      43206     +3   
  Misses         7464       7464          
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [d1d75d7...2e4daba](https://codecov.io/gh/pandas-dev/pandas/compare/d1d75d7fcb6b5d090cf96d328d0136c3959a82b8...2e4daba87fdc99e9d1d65c2bc6a452b993c82dea?src=pr)

@jreback what's asv?

http://pandas.pydata.org/pandas-docs/stable/contributing.html#running-the-performance-test-suite

There are some benchmarks for the series case already: https://github.com/pandas-dev/pandas/blob/master/asv_bench/benchmarks/timeseries.py#L283. We should indeed add for DataFrame.

For Series I suspect that the approach in this PR will also be faster with lots of NaNs, as the indexing of Series is much slower that the isnull checking on single values. For DataFrame not directly sure, so there is may make sense to precompute the NaNs (should be checked).

asv ...  -b ^timeseries

```
    before     after       ratio
  [233d51dd] [4836cdfd]
+  232.75μs   263.67μs      1.13  timeseries.timeseries_custom_bmonthend_incr.time_timeseries_custom_bmonthend_incr
+   14.06ms    15.68ms      1.11  timeseries.datetime_algorithm.time_dti_factorize
+   24.23μs    26.87μs      1.11  timeseries.timeseries_year_apply.time_timeseries_year_apply
+  338.21μs   374.77μs      1.11  timeseries.timeseries_custom_bmonthend_decr_n.time_timeseries_custom_bmonthend_decr_n
+  687.57ms   761.01ms      1.11  timeseries.timeseries_semi_month_offset.time_semi_month_begin_decr_rng
-   27.32ms    24.70ms      0.90  timeseries.timeseries_iter_periodindex_preexit.time_timeseries_iter_periodindex_preexit
-    3.12ms     2.77ms      0.89  timeseries.dataframe_resample_mean_numpy.time_dataframe_resample_mean_numpy
-    3.45ms     2.99ms      0.87  timeseries.dataframe_resample_max_string.time_dataframe_resample_max_string
-  314.65μs   271.87μs      0.86  timeseries.datetimeindex_add_offset.time_datetimeindex_add_offset
-  409.15μs    24.12μs      0.06  timeseries.timeseries_asof_single.time_timeseries_asof_single
```

@laudney You can selectively run only the asof ones with `-b asof` (in this case that is enough, as you do not touch code related to other functionality).

asv ... -b asof

```
    before     after       ratio
  [233d51dd] [4836cdfd]
-  454.34μs    22.44μs      0.05  timeseries.timeseries_asof_single.time_timeseries_asof_single
```

need several more asvs

I've updated my pull request code to refactor existing asv tests for Series.asof and add new ones for DataFrame.asof.

The main findings are:
1. Avoid pre-computation of nulls for Series if _where_ is a scalar because the _while_ loop is always faster than the pre-computation.
2. Always pre-compute nulls for DataFrames. The _while_ loop is extremely expensive. Given pre-computation is always available, even if _where_ is a scalar, should avoid the _while_ loop and use the same code path as when _where_ is list-like.

asv results below:

```
    before     after       ratio
  [233d51dd] [4cd64641]
+   15.63ms    20.19ms      1.29  timeseries.timeseries_dataframe_asof.time_asof_single
-  429.14μs    22.11μs      0.05  timeseries.timeseries_asof.time_asof_single
-     1.28s    21.10ms      0.02  timeseries.timeseries_dataframe_asof.time_asof_nan_single
-     1.24s     3.56ms      0.00  timeseries.timeseries_asof.time_asof_nan_single
```

@jreback I've added comment in the PR. Please check and let me know. Off to bed.

I will add two more asv tests and more detailed comment tonight. I will ping you when ready.

lgtm. pls add a whatsnew entry in the performance section. ping on green.

@jreback @jorisvandenbossche I've updated the PR: more comment and more asv tests. It's ready. Please review and merge.

impact as below:

```
-   87.33μs    18.44μs      0.21  timeseries.timeseries_asof.time_asof_single_early
-  390.14μs    21.42μs      0.05  timeseries.timeseries_asof.time_asof_single
-     1.20s     3.34ms      0.00  timeseries.timeseries_asof.time_asof_nan_single
-     1.26s    21.55ms      0.02  timeseries.timeseries_dataframe_asof.time_asof_nan_single
-   14.65ms    20.11μs      0.00  timeseries.timeseries_dataframe_asof.time_asof_single_early
```

@laudney pls add a whatsnew note

@jreback whatsnew updated for 0.19.1

@jreback @jorisvandenbossche It's all green on my side. Let me know if you need anything else.

@laudney Thanks!