PERF: Improve SeriesGroupBy.value_counts performances with categorical values.
State: closed

- [X] closes #46202
- [ ] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [X] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [X] Added an entry in the latest `doc/source/whatsnew/vX.X.X.rst` file if fixing a bug or adding a new feature.

The performance issue comes from the fact the categorical path relies on `GroupBy.apply`. Actually, `SeriesGroupby.value_counts` and `DataFrameGroupBy.value_counts` have different implementations, and I feel they should both rely on a single one. Typically, the Series implementation looks more complicated than the DataFrame one (which relies on `GroupBy.size`), this is why this change creates a `DataFrameGroupBy` object to rely on the DataFrame implementation. Ideally, I think the entire Series implementation could rely on the DataFrame one (not only the categorical path). Also, I have a small doubt whether creating a new `DataFrameGroupBy` object out of a `SeriesGroupBy` one is a good practice or not, so if there is a better way to do here feel free to suggest it.

Note I did not add a test in this PR as it fixes performance only, but I manually tested and confirmed the performance improvement.

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

Comments:
do we have asv's for this? can you show. (if not, or they are not representative of the OP can you add)
> do we have asv's for this? can you show. (if not, or they are not representative of the OP can you add)

It seems there is no asv for this. I will add one once I succeed to run the benchmark suite.
After benchmarking, I noticed that the current `DataFrameGroupBy.value_counts` implementation might be slower then the `SeriesGroupBy.value_counts` with a high number of categories. Here are the results I got for the two benchmarks I added (cf this [commit](https://github.com/pandas-dev/pandas/pull/46940/commits/cd20580c27892d22098e0027afa6738dca3ca338)).

![benchmarks](https://user-images.githubusercontent.com/44552904/168426084-cb70fccf-3918-438a-8ae1-8fa5c8b76177.png)

It shows a x30 performance boost for a small number of categories, and a x2 slow down with many categories.
I also noticed a 10x boost on OP's example (with a df size of 10_000 instead of 13_000_000).

I feel this fix is still interesting considering the slow down for many categories is negligible regarding the boost introduced for a small number of categories. I guess it depends on how many categories people use in general. @jreback do you have an opinion on it ?

Also, I profiled the `DataFrameGroupBy.value_counts` implementation to see where the time is spent, and it is mainly during sorting and `_reindex_output`.

![snakeviz](https://user-images.githubusercontent.com/44552904/168427203-b4e1f6d1-5c0a-4c5a-b116-3e3a1b0baabc.png)
This pull request is stale because it has been open for thirty days with no activity. Please [update](https://pandas.pydata.org/pandas-docs/stable/development/contributing.html#updating-your-pull-request) and respond to this comment if you're still interested in working on this.
I am no longer working on this pull request, I unassigned me of https://github.com/pandas-dev/pandas/issues/46202.
I think the follow up on this issue would be to have a common implementation for both `SeriesGroupBy` and `DataFrameGroupBy`, but this refactoring seems to be not trivial, cf [this comment](https://github.com/pandas-dev/pandas/pull/46940#discussion_r892569471).
Thanks for your efforts so far @LucasG0. I'm going to close this PR as it has gone stale, but can reopen if anyone wants to tackle in the future