PERF: lexsort_depth
State: closed

- [ ] closes #xxxx (Replace xxxx with the Github issue number)
- [ ] [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
- [ ] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [ ] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [ ] Added an entry in the latest `doc/source/whatsnew/vX.X.X.rst` file if fixing a bug or adding a new feature.

Currently, to find the lexsort_depth, `is_lexsorted` is repeatedly called.

This is unnecessary, it should be possible to keep track of the lexsort depth whilst looping through the elements. In particular, if the first level isn't lexsorted, and there are many levels, the repeatedly calling `is_lexsorted` is slow

Timing example:
```python
import pstats, cProfile

import pandas as pd
import numpy as np

n = 200
df = pd.DataFrame(np.ones((3, n)))
df.loc[1, 1] = 2
df = df.set_index(df.columns.tolist()).copy()

def main():
    df.index._lexsort_depth


cProfile.runctx("main()", globals(), locals(), "Profile.prof")

s = pstats.Stats("Profile.prof")
s.strip_dirs().sort_stats('time').print_stats()
```

On main:
```
         221516 function calls in 0.647 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    20100    0.155    0.000    0.562    0.000 _dtype.py:328(_name_get)
    20100    0.102    0.000    0.264    0.000 numerictypes.py:356(issubdtype)
    40200    0.097    0.000    0.142    0.000 numerictypes.py:282(issubclass_)
    80400    0.087    0.000    0.087    0.000 {built-in method builtins.issubclass}
      200    0.083    0.000    0.644    0.003 {pandas._libs.algos.is_lexsorted}
    20100    0.063    0.000    0.327    0.000 _dtype.py:314(_name_includes_bit_suffix)
    20100    0.033    0.000    0.033    0.000 {method 'format' of 'str' objects}
    20100    0.026    0.000    0.026    0.000 _dtype.py:24(_kind_name)
        1    0.001    0.001    0.647    0.647 multi.py:3841(_lexsort_depth)
      200    0.001    0.000    0.001    0.000 {pandas._libs.algos.ensure_int64}
```
On this branch:
```
         2417 function calls in 0.008 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      200    0.002    0.000    0.006    0.000 _dtype.py:328(_name_get)
      200    0.001    0.000    0.003    0.000 numerictypes.py:356(issubdtype)
      400    0.001    0.000    0.001    0.000 numerictypes.py:282(issubclass_)
        1    0.001    0.001    0.007    0.007 {pandas._libs.algos.lexsort_depth}
      800    0.001    0.000    0.001    0.000 {built-in method builtins.issubclass}
      200    0.001    0.000    0.001    0.000 {pandas._libs.algos.ensure_int64}
      200    0.001    0.000    0.003    0.000 _dtype.py:314(_name_includes_bit_suffix)
      200    0.000    0.000    0.000    0.000 {method 'format' of 'str' objects}
        1    0.000    0.000    0.001    0.001 multi.py:3843(<listcomp>)
      200    0.000    0.000    0.000    0.000 _dtype.py:24(_kind_name)
```

Note that if the index's codes are already lexsorted (e.g. by commenting out `df.loc[1, 1] = 2`), this doesn't make a difference (`0.008 seconds` in both cases)

I think there's alraedy a whatsnew note that could cover this, but I'll check again later

EDIT might be better to use this instead of is_lexsorted to avoid duplication, will check this soon

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

Comments:
Do we still need is_lexsorted?
> Do we still need is_lexsorted?

is_lexsorted would still be more efficient if all we're checking is whether something is lexsorted, as opposed to
what the depth is
example:
```
In [11]: list_of_arrays = [np.ones((100_000,), dtype='int64') for _ in range(2)]

In [12]: list_of_arrays[1][1] = 2

In [13]: %%timeit
    ...: lexsort_depth(list_of_arrays)
    ...: 
    ...: 
655 µs ± 17.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [14]: %%timeit
    ...: is_lexsorted(list_of_arrays)
    ...: 
    ...: 
15.2 µs ± 17 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```
does this help with any algos generally? e.g. try some indexing / multiindex benchs and see if any change
It makes a noticeable difference if there's a wide multiindex, the rest doesn't change much. ASV runs (with a wide multiindex benchmark added):
```
asv continuous -f 1.1 upstream/main 39d90f729b7b3b94bedccb2b1930b6d50f5d6827 -b ^multiindex_object
```

run 1:
```
       before           after         ratio
     [e915b0a4]       [39d90f72]
     <main>           <perf-lexsort-depth>
-        49.2±1μs         26.2±1μs     0.53  multiindex_object.GetLoc.time_wide_get_loc

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
```

run 2:
```
       before           after         ratio
     [e915b0a4]       [39d90f72]
     <main>           <perf-lexsort-depth>
-        52.0±1μs       26.9±0.2μs     0.52  multiindex_object.GetLoc.time_wide_get_loc

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
```

run 3:
```
       before           after         ratio
     [e915b0a4]       [39d90f72]
     <main>           <perf-lexsort-depth>
-      50.6±0.7μs       27.2±0.7μs     0.54  multiindex_object.GetLoc.time_wide_get_loc

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
```

Reckon it's worth it, or is it too little benefit to justify adding code?
> Reckon it's worth it, or is it too little benefit to justify adding code?

TBH I think this is too little benefit - #47459 already improved `is_lexsorted`, and MultiIndexes don't typically have many levels, so this isn't worth adding extra code to have to maintain

Apologies for having taken up your time with this