TSNE performance regression in 1.5

### Describe the bug

The performance of TSNE transformation reduces when using n_jobs as 25 for the newer version w.r.t. 1.3.1. 
version 1.3.1
```
df = np.random.rand(30000, 3)
tsne = TSNE(n_components=2, random_state=42, n_jobs=25, verbose=10, n_iter=1500)
```
1.5.1
```
df = np.random.rand(30000,3)
tsne = TSNE(n_components=2, random_state=42, n_jobs=25, verbose=10,max_iter=1500)
```
Time 1.3.1 vs 1.5.1 :: 59 vs 223

Is this a intended behavior?

### Steps/Code to Reproduce

```
df = np.random.rand(30000, 3)
tsne = TSNE(n_components=2, random_state=42, n_jobs=25, verbose=10, n_iter=1500)
```
1.5.1
```
df = np.random.rand(30000,3)
tsne = TSNE(n_components=2, random_state=42, n_jobs=25, verbose=10,max_iter=1500)
```

### Expected Results

Minimal time discrepancy 

### Actual Results

Similar time

### Versions

```shell
1.5.1

System:
    python: 3.12.3 (main, Jul 31 2024, 17:43:48) [GCC 13.2.0]
executable: /home/gagan/PycharmProjects/scikit_tsne_test/.venv/bin/python
   machine: Linux-6.8.0-40-generic-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.5.1
          pip: 23.2.1
   setuptools: 72.2.0
        numpy: 1.26.4
        scipy: 1.14.0
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.4.2
threadpoolctl: 3.5.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 28
         prefix: libscipy_openblas
       filepath: /home/gagan/PycharmProjects/scikit_tsne_test/.venv/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-c128ec02.so
        version: 0.3.27.dev
threading_layer: pthreads
   architecture: Haswell


1.3.1
System:
    python: 3.12.3 (main, Jul 31 2024, 17:43:48) [GCC 13.2.0]
executable: /home/gagan/PycharmProjects/scikit_tsne_test/.venv/bin/python
   machine: Linux-6.8.0-40-generic-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.3.1
          pip: 23.2.1
   setuptools: 72.2.0
        numpy: 1.26.4
        scipy: 1.14.0
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.4.2
threadpoolctl: 3.5.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 28
         prefix: libopenblas
       filepath: /home/gagan/PycharmProjects/scikit_tsne_test/.venv/lib/python3.12/site-packages/numpy.libs/libopenblas64_p-r0-0cf96a72.3.23.dev.so
        version: 0.3.23.dev
threading_layer: pthreads
   architecture: Prescott

       user_api: openmp
   internal_api: openmp
    num_threads: 28
         prefix: libgomp
       filepath: /home/gagan/PycharmProjects/scikit_tsne_test/.venv/lib/python3.12/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 28
         prefix: libscipy_openblas
       filepath: /home/gagan/PycharmProjects/scikit_tsne_test/.venv/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-c128ec02.so
        version: 0.3.27.dev
threading_layer: pthreads
   architecture: Haswell
```

COMMENT:
Looking at the `git blame` and our related PRs, I'm struggling to find the relevant change causing this regression.

cc @scikit-learn/core-devs for help.

Labels: Performance, Regression, module:manifold