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:
> @saichatla I need to wait a bit until no other users are on the machine. Most probably over the weekend. Meanwhile, could you please enlighten me why testing it with so many processes would help us in finding out what is going on? I have ~3000 job and I have problem computing them in reasonable time with 200 processes (which should in theory take around 25 minutes), now I have to run them in batches of 10 parallel jobs, which takes around 10h to finish. So I am not sure what information I will get when I try to spawn 500k of those jobs at once. Thanks for your patience.

What I am trying to get at is the overhead for multiprocessing might be greater than the advantages of parallelization. Like it is not free to put jobs in parallel it requires your OS to do work.  Could you also try maybe another clustering algorithm and if it follows similar pattern.

Labels: Bug, Needs Investigation