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:
There was a job which was supposed to run in 100s (like all the others) and when run with 200 parallel processes, it took 6500s (this was the worst case but still the majority of jobs took way longer to run then they should). When I ran the worst-case process alone, it took 100s as expected. There is no data being passed/pickled and sent between processes. So I really do not see, how the overhead of parallel processing can be 6400 seconds. But sure, I can try what you suggest over the weekend.

Labels: Bug, Needs Investigation