PERF: improve performance of groupby rank (#21237)
State: closed

- [x] closes #21237
- [ ] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry


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

Comments:
what does the asv look like? eg the perf improvement
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21285?src=pr&el=h1) Report
> Merging [#21285](https://codecov.io/gh/pandas-dev/pandas/pull/21285?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/ab668b0a56a9f2aee959bde787e9a0af4068d7a7?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `n/a`.

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

```diff
@@            Coverage Diff             @@
##           master   #21285      +/-   ##
==========================================
- Coverage   91.89%   91.89%   -0.01%     
==========================================
  Files         153      153              
  Lines       49600    49600              
==========================================
- Hits        45580    45578       -2     
- Misses       4020     4022       +2
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.29% <ø> (-0.01%)` | :arrow_down: |
| #single | `41.86% <ø> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21285?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/21285/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `84.6% <0%> (-0.21%)` | :arrow_down: |

------

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

The following is the output of ```asv continuous -f 1.1 upstream/master HEAD -b groupby.GroupByMethods```
> · Discovering benchmarks
> ·· Uninstalling from conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
> ·· Installing into conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
> · Running 4 total benchmarks (2 commits * 1 environments * 2 benchmarks)
> [  0.00%] · For pandas commit hash cb3f7788:
> [  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
> [ 25.00%] ··· Running groupby.GroupByMethods.time_dtype_as_field                                                                          53.5±4μs;...
> [ 50.00%] ··· Running groupby.GroupByMethods.time_dtype_as_group                                                                          56.5±0μs;...
> [ 50.00%] · For pandas commit hash 4274b840:
> [ 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
> [ 75.00%] ··· Running groupby.GroupByMethods.time_dtype_as_field                                                                          55.8±0μs;...
> [100.00%] ··· Running groupby.GroupByMethods.time_dtype_as_group                                                                          55.8±0μs;...
>             before           after         ratio
>      [4274b840]       [cb3f7788]
>           1.16s            1.00s     0.86  groupby.GroupByMethods.time_dtype_as_field('int', 'describe', 'transformation')
> 
> SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
When a single value occur many times , the current function is very slow, due constant writing to the array ``out``
_Master:_
``` Python
df = pd.DataFrame({"A":[1,2,3]*10000 ,"B":[1]*30000})

In [31]: %%timeit
    ...: t = df.groupby("B").rank()

608 ms ± 1.58 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```
_After:_
``` Python
In [2]: df = pd.DataFrame({"A":[1,2,3]*10000 ,"B":[1]*30000})

In [3]: %%timeit
   ...: t = df.groupby("B").rank()
   ...:
4.03 ms ± 32.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```
can we add this as an asv?
Here is the output of newly added asv bench groupby.RankWithTies

```bash
· Creating environments
· Discovering benchmarks
·· Uninstalling from conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pyta
bles-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
·· Installing into conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytabl
es-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
· Running 2 total benchmarks (2 commits * 1 environments * 1 benchmarks)
[  0.00%] · For pandas commit hash 690fac2f:
[  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
[ 50.00%] ··· Running groupby.RankWithTies.time_rank_ties          1.61±0ms;
...
[ 50.00%] · For pandas commit hash 0c65c57a:
[ 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
[100.00%] ··· Running groupby.RankWithTies.time_rank_ties          46.8±0ms;
...       before           after         ratio
     [0c65c57a]       [690fac2f]
-        31.2±3ms       1.71±0.1ms     0.05  groupby.RankWithTies.time_rank_ti
es('datetime64', 'dense')
-        31.2±3ms         1.65±0ms     0.05  groupby.RankWithTies.time_rank_ti
es('int64', 'dense')
-        31.2±2ms      1.61±0.09ms     0.05  groupby.RankWithTies.time_rank_ti
es('float64', 'max')
-        31.2±2ms         1.61±0ms     0.05  groupby.RankWithTies.time_rank_ti
es('float64', 'min')
-        33.8±3ms      1.73±0.09ms     0.05  groupby.RankWithTies.time_rank_ti
es('float32', 'max')
-        31.2±3ms       1.59±0.1ms     0.05  groupby.RankWithTies.time_rank_ti
es('float32', 'dense')
-        31.2±2ms       1.53±0.1ms     0.05  groupby.RankWithTies.time_rank_ti
es('float64', 'dense')
-        31.2±0ms       1.51±0.1ms     0.05  groupby.RankWithTies.time_rank_ti
es('float32', 'min')
-        33.8±3ms         1.61±0ms     0.05  groupby.RankWithTies.time_rank_ti
es('int64', 'min')
-        33.8±3ms      1.56±0.03ms     0.05  groupby.RankWithTies.time_rank_ti
es('datetime64', 'min')
-        35.1±2ms         1.61±0ms     0.05  groupby.RankWithTies.time_rank_ti
es('datetime64', 'max')
-        33.8±3ms         1.49±0ms     0.04  groupby.RankWithTies.time_rank_ti
es('int64', 'max')
-        46.8±0ms       1.76±0.1ms     0.04  groupby.RankWithTies.time_rank_ti
es('datetime64', 'first')
-        46.8±0ms         1.71±0ms     0.04  groupby.RankWithTies.time_rank_ti
es('int64', 'first')
-        46.8±0ms         1.61±0ms     0.03  groupby.RankWithTies.time_rank_ti
es('float64', 'first')
-        46.8±0ms       1.56±0.1ms     0.03  groupby.RankWithTies.time_rank_ti
es('float32', 'first')
-         203±0ms       1.76±0.1ms     0.01  groupby.RankWithTies.time_rank_ti
es('int64', 'average')
-         203±6ms         1.61±0ms     0.01  groupby.RankWithTies.time_rank_ti
es('datetime64', 'average')
-         203±0ms       1.59±0.1ms     0.01  groupby.RankWithTies.time_rank_ti
es('float64', 'average')
-         203±6ms         1.59±0ms     0.01  groupby.RankWithTies.time_rank_ti
es('float32', 'average')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```
thanks @peterpanmj