PERF: Improve drop_duplicates for bool columns (#12963)
State: closed

 - [x] closes #12963
 - [x] tests passed
 - [x] passes ``git diff upstream/master | flake8 --diff``
 - [x] whatsnew entry

Converts `bool` columns to `int` when calling `drop_duplicates()` so the factorization does not go down the `object` path.
 
```
      before           after         ratio
     [9ab57dc5]       [4b05fccb]
-     10.2±0.01ms      4.68±0.01ms     0.46  reindex.Duplicates.time_frame_drop_dups_bool

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```


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

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


```diff
@@            Coverage Diff             @@
##           master   #15738      +/-   ##
==========================================
- Coverage   91.02%      91%   -0.02%     
==========================================
  Files         143      143              
  Lines       49392    49395       +3     
==========================================
- Hits        44957    44951       -6     
- Misses       4435     4444       +9
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15738?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/compare/bff47f2302a0be4dcbf7e5055e525d5652e08fb5...a020c1081f86948a3f9332ad05ab35d8b6bf46d3?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.5% <100%> (+0.02%)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/compare/bff47f2302a0be4dcbf7e5055e525d5652e08fb5...a020c1081f86948a3f9332ad05ab35d8b6bf46d3?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `25% <0%> (-58.34%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/compare/bff47f2302a0be4dcbf7e5055e525d5652e08fb5...a020c1081f86948a3f9332ad05ab35d8b6bf46d3?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.86% <0%> (-0.1%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15738?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/15738?src=pr&el=footer). Last update [bff47f2...a020c10](https://codecov.io/gh/pandas-dev/pandas/compare/bff47f2302a0be4dcbf7e5055e525d5652e08fb5...a020c1081f86948a3f9332ad05ab35d8b6bf46d3?el=footer&src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
@mroeschke ping when you have made those changes.

I suspect we are incorrectly handling bool in other algos as well (do as separate issues), e.g. ``value_counts``, ``duplicated``, ``rank``
This looks OK to me (w/ @jreback change)

Can be a separate issue, but I think bool handling throughout these algos could made a lot faster by skipping the hashing altogether?  We could define a `BoolHashTable` to dispatch to, where the factorization is simply the `uint8` view on the data, and the other methods could take various shortcuts.  E.g. `unique` could be something like below.  

That said, may not be worth the added complexity.

```python
%%cython
from numpy cimport uint8_t
cimport cython

import numpy as np

@cython.boundscheck(False)
@cython.wraparound(False)
def unique(uint8_t[:] data):
    cdef:
        bint seen_true = False
        bint seen_false = False
        Py_ssize_t i, N = len(data)
        uint8_t val
    with nogil:
        for i in range(N):
            val = data[i]
            if val == 0:
                seen_false = True
            elif val == 1:
                seen_true = True
            if seen_true and seen_false:
                break
    if seen_true and seen_false:
        return np.array([True, False])
    elif seen_true:
        return np.array([True])
    elif seen_false:
        return np.array([False])
    else:
        return np.array([], dtype=bool)

In [35]: bools = np.array([False, True] * 100000)

In [36]: %timeit pd.unique(bools.view('uint8')).astype(bool)
1000 loops, best of 3: 1.74 ms per loop

In [37]: %timeit unique(bools.view('uint8'))
100000 loops, best of 3: 3.47 µs per loop

```
@chris-b1 It would be pretty easy to do this and maybe not too much extra code. can you hack up the ``.drop_duplicates`` from the issue and see how substantive that perf difference is? (my naive tests indicates that it should be *way* faster FYI).
hacked up impl

```python
def bool_factorize(values):
    values = values.view('uint8')
    return values, unique(values)

def drop_duplicates_bool(df):
    # 0.19.2 imports
    from pandas.core.groupby import get_group_index
    from pandas.hashtable import duplicated_int64
    keep = 'first'
    def f(vals):
        labels, shape = bool_factorize(vals)
        return labels.astype('i8', copy=False), len(shape)

    vals = (df[col].values for col in df)
    labels, shape = map(list, zip(*map(f, vals)))

    ids = get_group_index(labels, shape, sort=False, xnull=False)
    duplicated = pd.Series(duplicated_int64(ids, keep), index=df.index)
    return df[-duplicated]
```

I get another 2x speedup over casting to int.
```
In [67]: %timeit drop_duplicates_bool(df)
1 loop, best of 3: 362 ms per loop

In [68]: %timeit df.astype('uint8').drop_duplicates().astype(bool)
1 loop, best of 3: 868 ms per loop

In [69]: from pandas.util.testing import assert_frame_equal
In [70]: assert_frame_equal(drop_duplicates_bool(df), df.drop_duplicates())
```




It doesn't - apparently `numpy` doesn't respect `copy=False` between bool / uint8?

```python
In [84]: %timeit df.values.astype('uint8', copy=False)
10 loops, best of 3: 34.8 ms per loop

In [85]: %timeit df.values.astype('uint8', copy=True)
10 loops, best of 3: 34.9 ms per loop

In [86]: %timeit df.values.view('uint8')
100000 loops, best of 3: 8.37 µs per loop
```

@chris-b1 yeah I erased that as soon as I wrote it :<

the uint8 -> int64 for duplicated -> bool

so it probably does copy.

you might want to do a hacked duplicated_bool and see how much that makes a difference (if too much work don't, though that impl should be much like unique)
this looks good.

@chris-b1 going to merge this. But certainly can look at a ``BoolHashTable`` in a future issue. (pls create one).
@jreback before you merge, I think this can use some tests
@jorisvandenbossche hmm, we are already testing drop_duplicates quite thoroughly
https://github.com/pandas-dev/pandas/blob/master/pandas/tests/test_base.py#L775 tests all dtypes
Well, but the comment I made was not catched by any test?
> Well, but the comment I made was not catched by any test?

hmm, that's a good point. The tests I pointed, check the index.

and tests in ``pandas/tests/series/test_analytics`` are pretty minimal. hmm don't even have datetime tests...ok will create an issue.
@jorisvandenbossche Looks like tests passed even without `dtype=bool` because `duplicated` (which calls `factorize`) only uses the len of the uniques i.e. `len([True, False]) == len([1, 0])` https://github.com/pandas-dev/pandas/blob/master/pandas/core/frame.py#L3229

Nonetheless, good to add more test to `drop_duplicates()` and maybe a `factorize` test for the bool data in `pandas/tests/test_algos.py`