Truly parallel execution of pairwise_kernels and pairwise_distances

### Describe the workflow you want to enable

Both `pairwise_kernels` and `pairwise_distances` functions call `_parallel_pairwise` function, which is (contrary to its name) not parallel as it enforces the threading backend. Therefore, these functions are terribly slow, especially for computationally expensive user-defined metrics. I understand that the reasons for the threading backend are possibly large memory demands and data communication overhead but I suggest a different approach. Also, the documentation for these functions talks about parallel execution and processes which is currently simply not true.

### Describe your proposed solution

The memory and data communication issues can be reduced by a smarter distribution of the input data to individual processes. Right now, only `Y` is sliced in the `_parallel_pairwise` function which is suboptimal for parallel processing. Both `X` and `Y` should be sliced to lower the demands for multiprocessing. For example for 100x100 `X` and `Y` distributed to 100 processes, we have to copy 100+1 inputs to every process when slicing only `Y` while only 10+10 when slicing both `X` and `Y`. As a result, multiprocessing can be allowed. Also, joblib does automatic memmapping in some cases.

Alternatively, at least the documentation for  `pairwise_kernels` and `pairwise_distances` should be corrected.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
> which is (contrary to its name) not parallel as it enforces the threading backend.
> ... Therefore, these functions are terribly slow, especially for computationally expensive user-defined metrics.

Some CPU intensive operations in numpy or pandas do release the GIL, so the threading backend might be a good choice.

Furthermore, CPython 3.13 will come with an optional build flag that should a allow to run without any GIL (also known as the "free threading" mode of Python). It's not yet operational (it can cause segfaults in some cases) but @ngoldbaum, @lesteve and others are making progress at identifying and fixing the remaining problems. See #28978 for a tracking issue on the scikit-learn side.

It could be interesting to see if that can help with your specific workload.

More generally, before deciding to embark on a specific refactoring strategy for `_parallel_pairwise`, it would be interesting to see working code for typical uses of `pairwise_kernels` and `pairwise_distances` where you identified performance problems, and maybe report some quick benchmark results on the impact of varying the `n_jobs` parameter.

> Also, joblib does automatic memmapping in some cases.

I am worried about relying on this too much. In retrospect I have the feeling that it's a bit of brittle black magic that is complex to debug and maintain and reason about its performance implications (both in terms of memory usage and computational overhead).

More generally, process based parallelism can lead to hard to debug situations (see the recently opened #29579 for instance), so I would rather rely more on thread-based parallelism than process-based parallelism for scikit-learn in the future.

Labels: New Feature