Rank categorical perf
State: closed

 - [x] closes #15498 
 - [x] tests added / passed
 - [x] passes ``git diff upstream/master | flake8 --diff``
 - [x] whatsnew


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

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15518?src=pr&el=h1) Report
> Merging [#15518](https://codecov.io/gh/pandas-dev/pandas/pull/15518?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/d0a281fd60a2099c932151280af88d5392ea9a84?src=pr&el=desc) will **decrease** coverage by `-0.71%`.
> The diff coverage is `100%`.


```diff
@@            Coverage Diff             @@
##           master   #15518      +/-   ##
==========================================
- Coverage   91.06%   90.36%   -0.71%     
==========================================
  Files         136      136              
  Lines       49099    49556     +457     
==========================================
+ Hits        44714    44783      +69     
- Misses       4385     4773     +388
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15518?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.48% <ø> (ø)` | :white_check_mark: |
| [pandas/core/categorical.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY2F0ZWdvcmljYWwucHk=) | `96.92% <100%> (+0.01%)` | :white_check_mark: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `16.46% <0%> (-70.21%)` | :x: |
| [pandas/util/decorators.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvZGVjb3JhdG9ycy5weQ==) | `68.6% <0%> (-0.63%)` | :x: |
| [pandas/tools/merge.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL3Rvb2xzL21lcmdlLnB5) | `91.78% <0%> (-0.35%)` | :x: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `91.02% <0%> (-0.34%)` | :x: |
| [pandas/types/cast.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2Nhc3QucHk=) | `85.42% <0%> (-0.24%)` | :x: |
| [pandas/core/groupby.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ3JvdXBieS5weQ==) | `94.98% <0%> (-0.02%)` | :x: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.83% <0%> (-0.01%)` | :x: |
| [pandas/core/generic.py](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...f7eab32aed9d59547abba263cf084d29627e8290?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ2VuZXJpYy5weQ==) | `96.31% <0%> (-0.01%)` | :x: |
| ... and [5 more](https://codecov.io/gh/pandas-dev/pandas/pull/15518?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15518?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/15518?src=pr&el=footer). Last update [d0a281f...30b49b9](https://codecov.io/gh/pandas-dev/pandas/compare/d0a281fd60a2099c932151280af88d5392ea9a84...30b49b9726e2a3b9c8f3194ab29f687821067a03?el=footer&src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
can you add an asv similar to from the issue (ideally tests multple dtypes as well)
also a whatsnew (in Performance) entry would be great. code lgtm.
I have made all the minor changes but can't seem to run the asv benchmarks. Tried running them on upstream/master as well but the tests fail with the following error

TypeError: unbound methods must have non-NULL im_class

I used the following command to run asv benchmarks

 asv continuous -f 1.1 -E virtualenv upstream/master HEAD -b ^categorical

Googling for a solution hasn't helped. If you can point me towards a solution i will run the benchmarks and push my changes.

Here's a complete trace

````
� Creating environments
� Discovering benchmarks
�� Uninstalling from virtualenv-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytest-scipy-sqlalchemy-tables-xlrd-xlsxwriter-xlwt
�� Installing into virtualenv-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytest-scipy-sqlalchemy-tables-xlrd-xlsxwriter-xlwt..
�� Error running /home/jeet/Projects/pandas/asv_bench/env/dbb8113eac34359a9ef26b93e54a1d03/bin/python /home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmark.py discover /home/jeet/Projects/pandas/asv_bench/benchmarks /tmp/tmpklwg1xod
             STDOUT -------->
             
             STDERR -------->
             Traceback (most recent call last):
               File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmark.py", line 818, in <module>
                 commands[mode](args)
               File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmark.py", line 763, in main_discover
                 list_benchmarks(benchmark_dir, fp)
               File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmark.py", line 748, in list_benchmarks
                 for benchmark in disc_benchmarks(root):
               File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmark.py", line 653, in disc_benchmarks
                 for name, class_attr in inspect.getmembers(module_attr):
               File "/usr/lib/python2.7/inspect.py", line 253, in getmembers
                 value = getattr(object, key)
               File "/home/jeet/Projects/pandas/asv_bench/env/dbb8113eac34359a9ef26b93e54a1d03/local/lib/python2.7/site-packages/pandas/util/decorators.py", line 265, in __get__
                 return types.MethodType(self, instance)
             TypeError: unbound methods must have non-NULL im_class
Traceback (most recent call last):
  File "/home/jeet/.virtualenvs/pandas-dev/bin/asv", line 11, in <module>
    load_entry_point('asv==0.3.dev1099+a95b68de', 'console_scripts', 'asv')()
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/main.py", line 38, in main
    result = args.func(args)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/commands/__init__.py", line 48, in run_from_args
    return cls.run_from_conf_args(conf, args)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/commands/continuous.py", line 61, in run_from_conf_args
    quick=args.quick, **kwargs
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/commands/continuous.py", line 86, in run
    _returns=run_objs, _machine_file=_machine_file)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/commands/run.py", line 185, in run
    benchmarks = Benchmarks(conf, repo, environments, regex=bench)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmarks.py", line 336, in __init__
    benchmarks = self.disc_benchmarks(conf, repo, environments)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmarks.py", line 385, in disc_benchmarks
    dots=False)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/plugins/virtualenv.py", line 192, in run
    return self.run_executable('python', args, **kwargs)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/environment.py", line 556, in run_executable
    return util.check_output([exe] + args, **kwargs)
  File "/home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/util.py", line 571, in check_output
    raise ProcessError(args, retcode, stdout, stderr)
asv.util.ProcessError: Command '/home/jeet/Projects/pandas/asv_bench/env/dbb8113eac34359a9ef26b93e54a1d03/bin/python /home/jeet/.virtualenvs/pandas-dev/lib/python3.6/site-packages/asv/benchmark.py discover /home/jeet/Projects/pandas/asv_bench/benchmarks /tmp/tmpklwg1xod' returned non-zero exit status 1

````
@ikilledthecat Can you push your changes anyway (regardless whether you get asv running), so we can already review (and getting the asv benchs running is not a blocker for merging this PR in this case).

Regarding the asv, I don't have experience with running it using virtualenv, only used it with conda and never saw such an error. 
As the error seems to come from asv itself, you may want to raise an issue on their tracker (https://github.com/spacetelescope/asv)
@ikilledthecat something went wrong with your rebase, as you have many other commits included now as well. Doing

```
git fetch upstream
git checkout rank_categorical_perf
git rebase upstream/master
git push -f origin rank_categorical_perf
```

should normally always do the right thing
@jorisvandenbossche sorry, pushed after re-mergeing upstream/master.
you'll want to rebase on master as travis was having some issues
thanks @ikilledthecat