ENH: Arrow backed string array - implement factorize() method without casting to objects
xref https://github.com/pandas-dev/pandas/issues/35169#issuecomment-727217462, follow-on to #35259

This is moreless copy/paste from https://github.com/xhochy/fletcher with a slight tidy for initial review feedback

still to do

- [x] benchmarking
- [x] return type for chunked array with more than 1 chunk
- [x] maybe update tests.

we don't have failing tests, but the return type should be `Tuple[np.ndarray, ExtensionArray]` while we have  `return factorize(np_array, na_sentinel=na_sentinel)` if more than 1 chunk and the return type of pd.factorize is `Tuple[np.ndarray, Union[np.ndarray, ABCIndex]]` (mypy doesn't report this as an error since np.ndarray resolves to `Any`)

since we don't have failing tests, we probably should paramatrize data for the base extension tests with an array with one chunk and a array with multiple chunks.

cc @jorisvandenbossche @xhochy 


This pull request is stale because it has been open for thirty days with no activity. Please update or respond to this comment if you're still interested in working on this. this should yield a perf improvement yes? can you add an asv for this. There is an existing benchmark in algorithms.py::Factorize.time_factorize() which has a "string" case -> can rename this to "str", and add an actual "string" dtype version. This pull request is stale because it has been open for thirty days with no activity. Please update or respond to this comment if you're still interested in working on this. status here? > status here?

benchmarks added but pyarrow not added to env. this is OK for local testing with `asv dev`. I'm not sure whether we want to add pyarrow to asv env.

extensions tests updated for arrays with more than 1 chunk. good news is that we now see the factorize failures

these will be fixed by incorporating latest changes from fletcher next and other comments addressed. @simonjayhawkins did you check what difference it gives in performance for the benchmark case compared to object dtype? (just that single case, no need to run the full suite) with changes in this PR to compare with String(Index)

```
[ 25.00%] ··· algorithms.Factorize.time_factorize                                                                            ok
[ 25.00%] ··· ======== ======= ==================== ==========
               unique    sort         dtype                   
              -------- ------- -------------------- ----------
                True     True          int           3.66±0ms 
                True     True          uint          4.55±0ms 
                True     True         float          15.1±0ms 
                True     True         string         59.8±0ms 
                True     True     datetime64[ns]     182±0μs  
                True     True   datetime64[ns, tz]   185±0μs  
                True     True         Int64          5.07±0ms 
                True     True        boolean         900±0μs  
                True     True      string_arrow      63.4±0ms 
                True    False          int           3.04±0ms 
                True    False          uint          2.78±0ms 
                True    False         float          2.49±0ms 
                True    False         string         8.48±0ms 
                True    False     datetime64[ns]     182±0μs  
                True    False   datetime64[ns, tz]   183±0μs  
                True    False         Int64          3.19±0ms 
                True    False        boolean         603±0μs  
                True    False      string_arrow      7.00±0ms 
               False     True          int           8.14±0ms 
               False     True          uint          8.45±0ms 
               False     True         float          20.9±0ms 
               False     True         string         75.7±0ms 
               False     True     datetime64[ns]     10.8±0ms 
               False     True   datetime64[ns, tz]   9.70±0ms 
               False     True         Int64          9.70±0ms 
               False     True        boolean         3.04±0ms 
               False     True      string_arrow      68.8±0ms 
               False    False          int           6.43±0ms 
               False    False          uint          6.28±0ms 
               False    False         float          8.13±0ms 
               False    False         string         20.4±0ms 
               False    False     datetime64[ns]     8.89±0ms 
               False    False   datetime64[ns, tz]   6.56±0ms 
               False    False         Int64          5.61±0ms 
               False    False        boolean         2.53±0ms 
               False    False      string_arrow      11.6±0ms 
              ======== ======= ==================== ==========
```

without `factorize` to compare with `_from_factorized`

```
[ 25.00%] ··· algorithms.Factorize.time_factorize                                                                            ok
[ 25.00%] ··· ======== ======= ==================== ==========
               unique    sort         dtype                   
              -------- ------- -------------------- ----------
                True     True          int           3.25±0ms 
                True     True          uint          4.36±0ms 
                True     True         float          14.9±0ms 
                True     True         string         59.6±0ms 
                True     True     datetime64[ns]     174±0μs  
                True     True   datetime64[ns, tz]   175±0μs  
                True     True         Int64          3.49±0ms 
                True     True        boolean         858±0μs  
                True     True      string_arrow      73.9±0ms 
                True    False          int           1.81±0ms 
                True    False          uint          1.50±0ms 
                True    False         float          2.45±0ms 
                True    False         string         7.45±0ms 
                True    False     datetime64[ns]     179±0μs  
                True    False   datetime64[ns, tz]   174±0μs  
                True    False         Int64          2.80±0ms 
                True    False        boolean         584±0μs  
                True    False      string_arrow      16.5±0ms 
               False     True          int           8.34±0ms 
               False     True          uint          9.37±0ms 
               False     True         float          21.1±0ms 
               False     True         string         75.0±0ms 
               False     True     datetime64[ns]     10.7±0ms 
               False     True   datetime64[ns, tz]   11.8±0ms 
               False     True         Int64          8.35±0ms 
               False     True        boolean         3.27±0ms 
               False     True      string_arrow      125±0ms  
               False    False          int           7.07±0ms 
               False    False          uint          6.18±0ms 
               False    False         float          8.71±0ms 
               False    False         string         23.1±0ms 
               False    False     datetime64[ns]     7.16±0ms 
               False    False   datetime64[ns, tz]   6.87±0ms 
               False    False         Int64          6.39±0ms 
               False    False        boolean         2.95±0ms 
               False    False      string_arrow      74.2±0ms 
              ======== ======= ==================== ==========
``` @jorisvandenbossche @jreback anything else to be done here? > Can you merge latest master to be sure?

greenish. Thanks!