PERF: Regression in Series.is_monotonic_increasing for categorical

[TomAugspurger]

• I have checked that this issue has not already been reported.

• I have confirmed this bug exists on the latest version of pandas.

• (optional) I have confirmed this bug exists on the master branch of pandas.

---

Code Sample, a copy-pastable example

Pandas 1.0.1

In [2]: N = 1000

In [3]: c = pd.CategoricalIndex(list("a" * N + "b" * N + "c" * N))

In [4]: s = pd.Series(c)

In [5]: %timeit s.is_monotonic_increasing
35.3 µs ± 663 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Master

In [5]: %timeit s.is_monotonic_increasing
73.6 µs ± 782 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Problem description

https://pandas.pydata.org/speed/pandas/#categoricals.IsMonotonic.time_categorical_series_is_monotonic_increasing

[rtlee9]

Looks like the regression was introduced in 2fc8559.

$ asv continuous -f 1.1 2fc85593 -b 'categoricals.IsMonotonic.time_categorical_series_is_monotonic_increasing'

before           after         ratio
     [7c5d3d52]       [2fc85593]
     <master~660>       <master~659>
+      61.8±0.8μs         99.3±4μs     1.61  categoricals.IsMonotonic.time_categorical_series_is_mono
tonic_increasing

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE DECREASED.

There are a few ways to resolve, please see #33540 for one solution