PERF: Cache hashing of categories
State: closed

Hashing of the dtype is used in numerous places of the code base. For example it is used in concat operations to determine whether all objects have the same dtype. For `CategoricalDtype` this operation can be extremely costly since it requires hashing the array/list of categories.

The following example shows the impact of this caching operation nicely since `pd.concat` hashes all dtypes at least twice

```python
import string
import pandas as pd


def make_df():
    return pd.DataFrame(
        {
            "A": [
                string.ascii_letters[ix : (ix + 10) % len(string.ascii_letters)]
                for ix in range(10000)
            ],
            "B": [
                string.ascii_lowercase[ix : (ix + 10) % len(string.ascii_lowercase)]
                for ix in range(10000)
            ],
        }
    ).astype({"A": "category", "B": "category"})


dfs = [make_df() for _ in range(100)]

```


```python
# without caching
%time pd.concat(dfs)
CPU times: user 74.1 ms, sys: 6.32 ms, total: 80.4 ms
Wall time: 80.2 ms

# with caching
%time pd.concat(dfs)
CPU times: user 46.1 ms, sys: 6.65 ms, total: 52.7 ms
Wall time: 52.1 ms
```

Note: On an earlier version (I believe it was 1.1.X but I need to check again) this caching brought this concat down to ~30ms but I haven't identified this _regression_, yet


- [x] closes N/A
- [x] N/A
- [x] Ensure all linting tests pass, see [here](https://pandas.pydata.org/pandas-docs/dev/development/contributing.html#code-standards) for how to run them
- [x] whatsnew entry


Labels:
name: Performance
description: Memory or execution speed performance
name: Categorical
description: Categorical Data Type

Comments:
this is hit by existing asvs? 
Yes, there are `categoricals.Concat`

before
```
asv run --show-stderr --python=same --bench=categoricals.Concat       


· Running 6 total benchmarks (1 commits * 1 environments * 6 benchmarks)
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda3_envs_pandas-dev_bin_python
[  8.33%] ··· Running (categoricals.Concat.time_append_non_overlapping_index--)......
[ 58.33%] ··· categoricals.Concat.time_append_non_overlapping_index                  6.82±0.2ms
[ 66.67%] ··· categoricals.Concat.time_append_overlapping_index                      2.73±0.1ms
[ 75.00%] ··· categoricals.Concat.time_concat                                       2.66±0.05ms
[ 83.33%] ··· categoricals.Concat.time_concat_non_overlapping_index                  7.69±0.1ms
[ 91.67%] ··· categoricals.Concat.time_concat_overlapping_index                      3.34±0.2ms
[100.00%] ··· categoricals.Concat.time_union                                         2.90±0.1ms
```

and after

```
· Running 6 total benchmarks (1 commits * 1 environments * 6 benchmarks)
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda3_envs_pandas-dev_bin_python
[  8.33%] ··· Running (categoricals.Concat.time_append_non_overlapping_index--)......
[ 58.33%] ··· categoricals.Concat.time_append_non_overlapping_index                  1.35±0.3ms
[ 66.67%] ··· categoricals.Concat.time_append_overlapping_index                       78.7±30μs
[ 75.00%] ··· categoricals.Concat.time_concat                                       2.03±0.06ms
[ 83.33%] ··· categoricals.Concat.time_concat_non_overlapping_index                 2.03±0.05ms
[ 91.67%] ··· categoricals.Concat.time_concat_overlapping_index                        405±80μs
[100.00%] ··· categoricals.Concat.time_union                                         3.11±0.5ms
```

The improvements here (e.g. `categoricals.Concat.time_append_overlapping_index`) seem to be a bit too spectacular to be true. That's probably due to the caching since the benchmark iterations do not invalidate the cache. Do we have some experience with this kind of thing? I'll happily change the implementation if there are some recommendations to avoid this problem
I believe the test failures are unrelated. I receive a lot of import errors regarding `html5lib`
also wouldn't mind the example you have above as an additional concat asv
> also wouldn't mind the example you have above as an additional concat asv

The existing benchmarks already clearly cover this case nicely, so I wouldn't add more benchmarks if not needed.
@fjetter can you merge master and update
rebased and builds are green. Added a whatsnew entry but kept the logic for the caching as is (see comment above)

@jreback 
can you merge master and we'll see if we can push this through
can you merge master (the previous PR changes are stil here)
also if you'd re-run the asv's and post to make sure
Reran both master and this branch


## master
```python
asv run --show-stderr --python=same --bench=categoricals.Concat
· Discovering benchmarks
· Running 6 total benchmarks (1 commits * 1 environments * 6 benchmarks)
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_mambaforge_envs_pandas-dev-39_bin_python
[  8.33%] ··· Running (categoricals.Concat.time_append_non_overlapping_index--)......
[ 58.33%] ··· categoricals.Concat.time_append_non_overlapping_index  4.23±0.08ms
[ 66.67%] ··· categoricals.Concat.time_append_overlapping_index         1.78±0ms
[ 75.00%] ··· categoricals.Concat.time_concat                            467±8μs
[ 83.33%] ··· categoricals.Concat.time_concat_non_overlapping_index  4.39±0.01ms
[ 91.67%] ··· categoricals.Concat.time_concat_overlapping_index      2.01±0.04ms
[100.00%] ··· categoricals.Concat.time_union                         1.68±0.08ms
```

## This branch
```python
· Discovering benchmarks
· Running 6 total benchmarks (1 commits * 1 environments * 6 benchmarks)
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_mambaforge_envs_pandas-dev-39_bin_python
[  8.33%] ··· Running (categoricals.Concat.time_append_non_overlapping_index--)......
[ 58.33%] ··· categoricals.Concat.time_append_non_overlapping_index     585±20μs
[ 66.67%] ··· categoricals.Concat.time_append_overlapping_index       21.3±0.6μs
[ 75.00%] ··· categoricals.Concat.time_concat                           371±20μs
[ 83.33%] ··· categoricals.Concat.time_concat_non_overlapping_index     886±60μs
[ 91.67%] ··· categoricals.Concat.time_concat_overlapping_index          162±1μs
[100.00%] ··· categoricals.Concat.time_union                         1.59±0.06ms
```

Note the drop in e.g. `time_concat_overlapping_index` is only that large because we do not invalidate the cache during benchmarks. realistic performance gains should be in the two digit percentages.

Using the above `make_df` functions with one-time execution gives something like a 20% drop

## master
```python
%time pd.concat(dfs)
CPU times: user 50.2 ms, sys: 2.08 ms, total: 52.3 ms
Wall time: 51.2 ms
```


## this branch
```python
%time pd.concat(dfs)
CPU times: user 36.2 ms, sys: 4.37 ms, total: 40.6 ms
Wall time: 39.4 ms
```
thanks @fjetter