MeanShift extremely slow when multiple processes are run in parallel

### Describe the bug

I have a script which computes clustering of points using `sklearn.cluster.MeanShift`. As a part of my pipeline, I have to run this script many times on different data. The data changes, but the number of points is roughly the same in every file (~700k). When I run the script on 1 CPU it takes approx. 100 seconds. I am not using the in-built parallelism, i.e. I use `n_jobs=1` but I am running many jobs in parallel (either with `subprocess.call` or directly from bash). I noticed, that my jobs take exceptionally long to run (some took 7000 seconds), even though all of them should take only roughly 100 seconds. I am using a very powerful machine with Dual AMD EPYC 7742 64-Core Processor (i.e. 256 CPUs are available), with 1TB of RAM, and only read intensive NVMe Samsung PM983 drives. I would be very happy if somebody knows a workaround. Thank you for your time.

### Steps/Code to Reproduce

File `debugMeanShift.py`:

```python
# SPECIFY SEED AND NPROC ENV VARIABLES WHEN RUNNING THIS FILE
import os
import time
import numpy as np
from sklearn.cluster import MeanShift

n_jobs = 1
seed = int(os.getenv('SEED', default=0))
np.random.seed(seed)

# Generate random data just for this example (therefore we can eliminate problems with I/O ops)
points = np.abs(np.random.normal(loc=0, scale=2, size=(64, 128, 128))).astype(np.int8)
points = np.array(np.nonzero(points > 0)).T

start = time.time()
clusters = MeanShift(bandwidth=5, bin_seeding=True, max_iter=5, n_jobs=n_jobs).fit(points)
end = time.time()

# Optional code to store the timings in a csv file (I only use it to plot the graphs)
print(f'Clustering of {len(points)} {points.shape[-1]}D points (seed={seed}) with n_jobs={n_jobs} took {end - start:.2f}s')
with open(f'{os.environ["NPROC"]}.csv', 'a+') as file:
    file.write(f'{seed};{end - start}\n')
```

Create a txt file with for example 1000 jobs:
```python
template = 'SEED={} python3 debugMeanShift.py'
joblist = [template.format(seed) for seed in range(1000)]
with open('dummy_queue.txt', 'w') as file:
    file.write('\n'.join(joblist))
```

Run the following use cases from the terminal:

1. Running in batches of 1
```bash
cat dummy_queue.txt | xargs --max-procs=1 --replace --verbose /bin/sh -c "NPROC=1 {}"
```

2. Running in batches of 5
```bash
cat dummy_queue.txt | xargs --max-procs=5 --replace --verbose /bin/sh -c "NPROC=5 {}"
```

3. Running in batches of 10
```bash
cat dummy_queue.txt | xargs --max-procs=10 --replace --verbose /bin/sh -c "NPROC=10 {}"
```

4. Running in batches of 50
```bash
cat dummy_queue.txt | xargs --max-procs=50 --replace --verbose /bin/sh -c "NPROC=50 {}"
```

5. Running in batches of 100
```bash
cat dummy_queue.txt | xargs --max-procs=100 --replace --verbose /bin/sh -c "NPROC=100 {}"
```
6. Running in batches of 200
```bash
cat dummy_queue.txt | xargs --max-procs=200 --replace --verbose /bin/sh -c "NPROC=200 {}"
```


### Expected Results

No matter how many processes I spawn, each job should finish in approx. the same time. In the example case above, on my aforementioned machine, it should take ~40 seconds per job. Please note, no other exhaustive processes are running on the machine and most of the RAM is free. 

### Actual Results

When running only as much as 50 jobs in parallel (on a 256 core machine), some jobs take 10x longer. With increasing number of parallel processes, the situation gets worse. With 100 processes, the worst case is 20x longer. With 200 processes, the worst case is almost 30x longer. Better overview in the plot bellow. Also, please note that  even when the process takes so abnormally long to finish, it still appears as *running* in htop and uses 99% of CPU, so it is not sleeping.

![image](https://user-images.githubusercontent.com/15421925/177211287-0d811af4-b5d2-4f63-9d1d-2a3d58e08583.png)


### Versions

```shell
System:
    python: 3.9.11 (main, Mar 29 2022, 19:08:29)  [GCC 7.5.0]
executable: /home/username/.conda/envs/projectname/bin/python
   machine: Linux-5.4.0-105-generic-x86_64-with-glibc2.31

Python dependencies:
          pip: 21.2.4
   setuptools: 58.0.4
      sklearn: 0.24.2
        numpy: 1.19.5
        scipy: 1.7.3
       Cython: None
       pandas: 1.4.2
   matplotlib: 3.5.1
       joblib: 1.1.0
threadpoolctl: 2.2.0

Built with OpenMP: True
```

COMMENT:
So I have done another experiment. I left the MeanShift out completely and instead I just randomly generated a numpy array and sorted it. And from the timing it seems the trend is similar as before. Therefore this might really just be an overhead of running multiple processes :confused:. I am sorry, I should have thought about this earlier. The new code is:
```python
# SPECIFY SEED AND NPROC ENV VARIABLES WHEN RUNNING THIS FILE
import os
import time
import numpy as np

seed = int(os.getenv('SEED', default=0))
start = time.time()
points = np.abs(np.random.normal(loc=0, scale=2, size=(500, 1000, 1000))).astype(np.int8)
srt = np.sort(points)
end = time.time()
print(f'Generating data and sorting took {end - start:.2f}s')
with open(f'{os.environ["NPROC"]}.csv', 'a+') as file:
    file.write(f'{seed};{end - start}\n')
```
![image](https://user-images.githubusercontent.com/15421925/178731119-7e7663b4-8aea-4352-95cf-c81359baafb6.png)

When I instead tried running the function with multiprocessing, the results are much better. Still there is some overhead, but less. 
```python
def func(seed, nproc):
    start = time.time()
    points = np.abs(np.random.normal(loc=0, scale=2, size=(500, 1000, 1000))).astype(np.int8)
    srt = np.sort(points)
    end = time.time()
    print(f'Generating data and sorting took {end - start:.2f}s')
    with open(f'{nproc}.csv', 'a+') as file:
        file.write(f'{seed};{end - start}\n')

with multiprocessing.Pool(processes=nproc) as p:
    p.starmap(func, zip(np.arange(1000), itertools.repeat(nproc)))
```

![image](https://user-images.githubusercontent.com/15421925/178737933-7a9a011f-093b-4ea5-9538-9827e2e96b75.png)

At the beginning, there was quite a peak in RAM usage (since each job generates a big array of random numbers), but then, as each of the jobs took different amount of time to compute, the rest of the jobs did not start in waves and the RAM usage was much smaller on average.

In conclusion, spawning a new python process for small tasks is overly expensive and one should better use multiprocessing. When I write like this, it is quite intuitive and obvious even. But I did not really expect there would be such a discrepancy. Sorry for spamming scikit-learn issues. Closing.

Labels: Bug, Needs Investigation