Kmeans Elkans deteriorates with different cores settings

### Describe the bug

Currently I'm trying to run Kmeans Elkan on a large-scale dataset. I have tried to run it with 2 configuration: 8-thread setting and 16-thread setting. While the former one seems to work normally, the running time for the later surge surprisingly. I do not understand why this behavior happens (I have tried with different datasets but have not encountered any issue like this one). 

Link to datasets: https://drive.google.com/file/d/1q8A1Xo-kFSKpZCCawbuObg8sG9o9baFr/view?usp=sharing

CPU Info
```
Description: Ubuntu 22.04.5 LTS
Model name: AMD Ryzen 9 5950X 16-Core Processor
RAM: 128 GB
```

Please kindly help me to check this one. Thank you so much for your consideration. 

### Steps/Code to Reproduce

```python
import numpy as np

from sklearn.cluster import KMeans
from sklearn.utils._openmp_helpers import _openmp_effective_n_threads

import time
import pickle as pkl


np.random.seed(42)  # RandomState
random_state = np.random.randint(2**31 - 1)

dataset_name = "Wiki500K-AttentionXML"
n_clusters = 500
n_iter = 300
n_threads = _openmp_effective_n_threads()

print("------------------Running clustering------------------")
print("Dataset: ", dataset_name, flush=True)
print("#Cluster: ", n_clusters, flush=True)
print("#Threads: ", n_threads, flush=True)

with open(f"./data/pkl/{dataset_name}.pkl", "rb") as f:
    label_representation = pkl.load(f)


print(dataset_name)
print(label_representation.shape)
nnz = label_representation.count_nonzero()
print(f"Total non-zero in label_representation", nnz)

start = time.time()
metalabels = (
    KMeans(
        n_clusters,
        random_state=random_state,
        n_init=1,
        max_iter=n_iter,
        tol=0.0001,
        algorithm="elkan",
    )
    .fit(label_representation)
    .labels_
)
end = time.time()

print("Total clustering runtime: ", end - start)
```

### Expected Results

Running with command
```
OMP_NUM_THREADS=8 python run_cluster.py --dataset Wiki500K-AttentionXML --n_clusters 500
```

Result:
```
------------------Running clustering------------------
Dataset:  Wiki500K-AttentionXML
#Cluster:  500
#Threads:  8
Total clustering runtime:  14531.516061782837
```

### Actual Results

Running with command
```
OMP_NUM_THREADS=16 python run_cluster.py --dataset Wiki500K-AttentionXML --n_clusters 500
```

Result:
```
------------------Running clustering------------------
Dataset:  Wiki500K-AttentionXML
#Cluster:  500
#Threads:  16
Total clustering runtime:  83970.27724099159
```

### Versions

```shell
System:
    python: 3.8.0 (default, Nov  6 2019, 21:49:08)  [GCC 7.3.0]
executable: /home/khoinpd/anaconda3/envs/clustering/bin/python
   machine: Linux-5.15.0-131-generic-x86_64-with-glibc2.10

Python dependencies:
      sklearn: 1.3.2
          pip: 24.2
   setuptools: 75.1.0
        numpy: 1.24.4
        scipy: 1.10.1
       Cython: None
       pandas: 2.0.3
   matplotlib: 3.7.5
       joblib: 1.4.2
threadpoolctl: 3.5.0

Built with OpenMP: True

threadpoolctl info:
       user_api: openmp
   internal_api: openmp
    num_threads: 32
         prefix: libgomp
       filepath: /home/khoinpd/anaconda3/envs/clustering/lib/python3.8/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 32
         prefix: libopenblas
       filepath: /home/khoinpd/anaconda3/envs/clustering/lib/python3.8/site-packages/numpy.libs/libopenblas64_p-r0-15028c96.3.21.so
        version: 0.3.21
threading_layer: pthreads
   architecture: Zen

       user_api: blas
   internal_api: openblas
    num_threads: 32
         prefix: libopenblas
       filepath: /home/khoinpd/anaconda3/envs/clustering/lib/python3.8/site-packages/scipy.libs/libopenblasp-r0-41284840.3.18.so
        version: 0.3.18
threading_layer: pthreads
   architecture: Zen
```

COMMENT:
> Just to make sure, you have recompiled scikit-learn before re-running it ?

Yes, I have recompiled scikit-learn before running the exps with new settings (following the tutorial building from source: https://scikit-learn.org/stable/developers/advanced_installation.html).

> I don't have much more intuition about what's hurting the scalability of elkan. Out of curiosity, why are you using elkan ? Have you tested lloyd on the same dataset ? lloyd has specific optimizations that elkan can't have and benefit from platform/cpu specific optimizations that usually make it faster than elkan and better scale with the number of cores.

I have tried both Elkan and Lloyd. For my usecases, the datasets is often extremely large one with high-dimensional features. I dont know if I have missed any specific configuration for lloyd, but running it by default leads to a worse performance compared to Elkan's.

Labels: Bug, Performance