PERF: MultiIndex._engine use smaller dtypes
State: closed

Use smaller dtypes in `MultiIndex._engine` if possible.
Reduce both loading time and memory (peak and used).
The improvement should be more relevant when working with big indices.
Below there are 2 examples.

- [ ] 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.

### Improvement when `engine.values` uses `uint32` instead of `uint64`:

- `idx._engine`:  from 8.53 s to 2.45 s
- `_engine.values.nbytes`: from 800000000 to 400000000
- `_engine`:
  - from: peak memory: 5805.98 MiB, increment: 5218.30 MiB
  - to: peak memory: 2794.02 MiB, increment: 2193.25 MiB


#### Time, Pandas 2.2.2:
```python
In [4]: %time idx = pd.MultiIndex.from_product([np.arange(1000), np.arange(1000), np.arange(100)], names=["x0", "x1", "x2"])
   ...: 
CPU times: user 250 ms, sys: 191 ms, total: 442 ms
Wall time: 457 ms

In [5]: %time idx._engine
   ...: 
CPU times: user 2.83 s, sys: 4.01 s, total: 6.84 s
Wall time: 8.53 s
Out[5]: <pandas.core.indexes.multi.MultiIndexUIntEngine at 0x117363d50>

In [6]: idx._engine.values.dtype
Out[6]: dtype('uint64')

In [7]: idx._engine.values.nbytes
Out[7]: 800000000
```

#### Time, PR branch:
```python
In [3]: %time idx = pd.MultiIndex.from_product([np.arange(1000), np.arange(1000), np.arange(100)], names=["x0", "x1", "x2"])
CPU times: user 282 ms, sys: 192 ms, total: 474 ms
Wall time: 565 ms

In [4]: %time idx._engine
CPU times: user 963 ms, sys: 838 ms, total: 1.8 s
Wall time: 2.45 s
Out[4]: <pandas.core.indexes.multi.MultiIndexUInt32Engine at 0x10ab54f90>

In [5]: idx._engine.values.dtype
Out[5]: dtype('uint32')

In [6]: idx._engine.values.nbytes
Out[6]: 400000000

```

#### Memory, Pandas 2.2.2:
```python
In [4]: %memit idx = pd.MultiIndex.from_product([np.arange(1000), np.arange(1000), np.arange(100)], names=["x0", "x1", "x2"])
peak memory: 587.48 MiB, increment: 477.49 MiB

In [5]: %memit idx._engine
peak memory: 5805.98 MiB, increment: 5218.30 MiB

```

#### Memory, PR branch:
```python
In [4]: %memit idx = pd.MultiIndex.from_product([np.arange(1000), np.arange(1000), np.arange(100)], names=["x0", "x1", "x2"])
peak memory: 600.49 MiB, increment: 477.43 MiB

In [5]: %memit idx._engine
peak memory: 2794.02 MiB, increment: 2193.25 MiB

```

### Improvement when `engine.values` still needs to use `uint64`:

- `idx._engine`:  from 17.6 s to 4.56 s
- `_engine.values.nbytes`: from 390625000 to 390625000 (unchanged since the dtype is the same)
- `_engine`:
  - from: peak memory: 9106.29 MiB, increment: 8472.42 MiB
  - to: peak memory: 5325.37 MiB, increment: 4674.05 MiB


#### Time, Pandas 2.2.2:
```python
In [3]: %time idx = pd.MultiIndex.from_product([np.arange(5)] * 11)
CPU times: user 265 ms, sys: 104 ms, total: 369 ms
Wall time: 371 ms

In [4]: %time idx._engine
CPU times: user 5.28 s, sys: 9.4 s, total: 14.7 s
Wall time: 17.6 s
Out[4]: <pandas.core.indexes.multi.MultiIndexUIntEngine at 0x11bde3cd0>

In [5]: idx._engine.values.dtype
Out[5]: dtype('uint64')

In [6]: idx._engine.values.nbytes
Out[6]: 390625000
```

#### Time, PR branch:
```python
In [3]: %time idx = pd.MultiIndex.from_product([np.arange(5)] * 11)
CPU times: user 268 ms, sys: 112 ms, total: 380 ms
Wall time: 381 ms

In [4]: %time idx._engine
CPU times: user 2.24 s, sys: 1.75 s, total: 3.99 s
Wall time: 4.56 s
Out[4]: <pandas.core.indexes.multi.MultiIndexUInt64Engine at 0x1209d0e40>

In [6]: idx._engine.values.dtype
Out[6]: dtype('uint64')

In [7]: idx._engine.values.nbytes
Out[7]: 390625000

```

#### Memory, Pandas 2.2.2:
```python
In [4]: %memit idx = pd.MultiIndex.from_product([np.arange(5)] * 11)
peak memory: 633.76 MiB, increment: 523.95 MiB

In [5]: %memit idx._engine
peak memory: 9106.29 MiB, increment: 8472.42 MiB

In [6]: idx._engine
Out[6]: <pandas.core.indexes.multi.MultiIndexUIntEngine at 0x117505750>

```

#### Memory, PR branch:
```python
In [4]: %memit idx = pd.MultiIndex.from_product([np.arange(5)] * 11)
peak memory: 651.32 MiB, increment: 523.31 MiB

In [5]: %memit idx._engine
peak memory: 5325.37 MiB, increment: 4674.05 MiB

In [6]: idx._engine
Out[6]: <pandas.core.indexes.multi.MultiIndexUInt64Engine at 0x117323290>

```


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

Comments:
I executed the asv benchmarks for `multiindex_object` (on a Linux workstation, although not tuned for benchmarking) with these results:
```
asv continuous -f 1.1 41014db0e8 20f3bc015b -b '^multiindex_object'
```
```
| Change   | Before [41014db0] <improve_index_engine~4>   | After [20f3bc01] <improve_index_engine~1>   |   Ratio | Benchmark (Parameter)                                                                                      |
|----------|----------------------------------------------|---------------------------------------------|---------|------------------------------------------------------------------------------------------------------------|
| +        | 7.14±0.05μs                                  | 8.44±0.08μs                                 |    1.18 | multiindex_object.GetLoc.time_string_get_loc                                                               |
| +        | 7.31±0.04μs                                  | 8.58±0.2μs                                  |    1.17 | multiindex_object.GetLoc.time_med_get_loc                                                                  |
| +        | 7.19±0.07ms                                  | 8.38±0.2ms                                  |    1.16 | multiindex_object.GetLoc.time_med_get_loc_warm                                                             |
| +        | 7.15±0.1ms                                   | 8.22±0.2ms                                  |    1.15 | multiindex_object.GetLoc.time_small_get_loc_warm                                                           |
| -        | 1.37±0.01ms                                  | 1.23±0.01ms                                 |    0.9  | multiindex_object.Isin.time_isin_small('datetime')                                                         |
| -        | 1.36±0.04ms                                  | 1.22±0ms                                    |    0.9  | multiindex_object.Isin.time_isin_small('int')                                                              |
| -        | 1.37±0.01ms                                  | 1.23±0.01ms                                 |    0.9  | multiindex_object.Isin.time_isin_small('string')                                                           |
| -        | 4.10±0.3ms                                   | 3.59±0.03ms                                 |    0.88 | multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'union', None)                      |
| -        | 4.35±0.04ms                                  | 3.62±0.02ms                                 |    0.83 | multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'intersection', None)               |
| -        | 2.86±0.08ms                                  | 2.34±0.02ms                                 |    0.82 | multiindex_object.SetOperations.time_operation('monotonic', 'int', 'symmetric_difference', None)           |
| -        | 4.76±0.4ms                                   | 3.89±0.2ms                                  |    0.82 | multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'intersection', None)          |
| -        | 3.10±0.09ms                                  | 2.46±0.01ms                                 |    0.8  | multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'intersection', False)               |
| -        | 2.93±0.2ms                                   | 2.34±0.03ms                                 |    0.8  | multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'symmetric_difference', False) |
| -        | 4.72±0.4ms                                   | 3.77±0.2ms                                  |    0.8  | multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'intersection', None)            |
| -        | 5.03±0.1ms                                   | 3.99±0.07ms                                 |    0.79 | multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'intersection', None)                |
| -        | 3.09±0.1ms                                   | 2.45±0.01ms                                 |    0.79 | multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'symmetric_difference', None)        |
| -        | 4.40±0.3ms                                   | 3.48±0.2ms                                  |    0.79 | multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'union', None)                 |
| -        | 2.94±0.09ms                                  | 2.33±0.01ms                                 |    0.79 | multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'symmetric_difference', False)   |
| -        | 4.47±0.4ms                                   | 3.51±0.2ms                                  |    0.79 | multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'union', None)                   |
| -        | 3.14±0.04ms                                  | 2.44±0.02ms                                 |    0.78 | multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'intersection', False)             |
| -        | 3.14±0.03ms                                  | 2.44±0.03ms                                 |    0.78 | multiindex_object.SetOperations.time_operation('monotonic', 'string', 'intersection', False)               |
| -        | 5.33±0.5ms                                   | 4.16±0.06ms                                 |    0.78 | multiindex_object.SetOperations.time_operation('monotonic', 'string', 'intersection', None)                |
| -        | 3.35±0.1ms                                   | 2.61±0.04ms                                 |    0.78 | multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'symmetric_difference', None)  |
| -        | 3.38±0.1ms                                   | 2.65±0.01ms                                 |    0.78 | multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'symmetric_difference', None)    |
| -        | 3.27±0.2ms                                   | 2.54±0.04ms                                 |    0.78 | multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'symmetric_difference', None)       |
| -        | 2.81±0.2ms                                   | 2.16±0.02ms                                 |    0.77 | multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'symmetric_difference', False)       |
| -        | 3.16±0.03ms                                  | 2.42±0.01ms                                 |    0.77 | multiindex_object.SetOperations.time_operation('monotonic', 'int', 'intersection', False)                  |
| -        | 3.16±0.01ms                                  | 2.44±0.02ms                                 |    0.77 | multiindex_object.SetOperations.time_operation('monotonic', 'string', 'symmetric_difference', None)        |
| -        | 3.28±0.2ms                                   | 2.52±0ms                                    |    0.77 | multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'intersection', False)              |
| -        | 3.03±0.1ms                                   | 2.33±0.03ms                                 |    0.77 | multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'symmetric_difference', False)      |
| -        | 4.68±0.4ms                                   | 3.55±0.02ms                                 |    0.76 | multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'intersection', None)              |
| -        | 2.77±0.2ms                                   | 2.06±0.01ms                                 |    0.75 | multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'symmetric_difference', False)     |
| -        | 4.71±0.4ms                                   | 3.51±0.02ms                                 |    0.75 | multiindex_object.SetOperations.time_operation('monotonic', 'int', 'intersection', None)                   |
| -        | 2.71±0.2ms                                   | 1.99±0ms                                    |    0.74 | multiindex_object.SetOperations.time_operation('monotonic', 'int', 'symmetric_difference', False)          |
| -        | 3.45±0.03ms                                  | 2.55±0.01ms                                 |    0.74 | multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'intersection', False)         |
| -        | 3.46±0.04ms                                  | 2.58±0.03ms                                 |    0.74 | multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'intersection', False)           |
| -        | 1.64±0.02ms                                  | 1.19±0.01ms                                 |    0.73 | multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'union', False)                  |
| -        | 3.34±0.2ms                                   | 2.41±0.01ms                                 |    0.72 | multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'symmetric_difference', None)      |
| -        | 1.53±0.02ms                                  | 1.10±0.01ms                                 |    0.72 | multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'union', False)                    |
| -        | 1.61±0.02ms                                  | 1.16±0.01ms                                 |    0.72 | multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'union', None)                       |
| -        | 5.86±0.1ms                                   | 4.19±0.07ms                                 |    0.71 | multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'intersection', None)            |
| -        | 3.41±0.2ms                                   | 2.41±0.03ms                                 |    0.71 | multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'symmetric_difference', False)   |
| -        | 1.57±0.02ms                                  | 1.10±0.01ms                                 |    0.7  | multiindex_object.SetOperations.time_operation('monotonic', 'int', 'union', None)                          |
| -        | 3.76±0.3ms                                   | 2.62±0.02ms                                 |    0.7  | multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'intersection', False)           |
| -        | 3.83±0.3ms                                   | 2.68±0.01ms                                 |    0.7  | multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'symmetric_difference', None)    |
| -        | 1.64±0.05ms                                  | 1.12±0.01ms                                 |    0.68 | multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'union', False)                      |
| -        | 1.77±0.02ms                                  | 1.20±0.01ms                                 |    0.68 | multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'union', False)                |
| -        | 5.41±0.03ms                                  | 3.67±0.04ms                                 |    0.68 | multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'union', None)                   |
| -        | 1.67±0.1ms                                   | 1.12±0.01ms                                 |    0.67 | multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'union', False)                     |
| -        | 1.18±0.03ms                                  | 770±10μs                                    |    0.66 | multiindex_object.Isin.time_isin_large('datetime')                                                         |
| -        | 1.17±0.02ms                                  | 772±2μs                                     |    0.66 | multiindex_object.Isin.time_isin_large('string')                                                           |
| -        | 3.25±0.2ms                                   | 2.15±0.05ms                                 |    0.66 | multiindex_object.SetOperations.time_operation('monotonic', 'string', 'symmetric_difference', False)       |
| -        | 1.16±0.04ms                                  | 754±5μs                                     |    0.65 | multiindex_object.Isin.time_isin_large('int')                                                              |
| -        | 1.78±0.02ms                                  | 1.15±0ms                                    |    0.65 | multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'union', None)                     |
| -        | 1.66±0.03ms                                  | 1.05±0.01ms                                 |    0.63 | multiindex_object.SetOperations.time_operation('monotonic', 'int', 'union', False)                         |
| -        | 1.89±0.1ms                                   | 1.20±0.01ms                                 |    0.63 | multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'union', False)                  |
| -        | 4.46±0.3ms                                   | 2.77±0.01ms                                 |    0.62 | multiindex_object.SetOperations.time_operation('monotonic', 'string', 'union', None)                       |
| -        | 1.99±0.02ms                                  | 1.11±0.01ms                                 |    0.56 | multiindex_object.SetOperations.time_operation('monotonic', 'string', 'union', False)                      |
| -        | 30.3±5μs                                     | 16.6±2μs                                    |    0.55 | multiindex_object.GetLoc.time_large_get_loc                                                                |
| -        | 24.9±1ms                                     | 13.4±1ms                                    |    0.54 | multiindex_object.GetLoc.time_large_get_loc_warm                                                           |
| -        | 1.84±0.2ms                                   | 897±40μs                                    |    0.49 | multiindex_object.Integer.time_get_indexer                                                                 |
| -        | 29.8±0.6ms                                   | 14.2±0.4ms                                  |    0.48 | multiindex_object.Integer.time_get_indexer_and_pad                                                         |
| -        | 29.4±0.5ms                                   | 13.5±0.5ms                                  |    0.46 | multiindex_object.Integer.time_get_indexer_and_backfill                                                    |

```

All of them improved, except `GetLoc` with small and medium index. It doesn't seem a big change but it could be worth investigating.

Side note, I also tried to move the class `BaseMultiIndexCodesEngine` from cython to python in [this commit](https://github.com/GianlucaFicarelli/pandas/commit/28282c0cbb1964a74f5ab28adcf5fe62e279c2df), and I didn't notice any visible decrease of performance.

Thanks @GianlucaFicarelli