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:
Hi @ogrisel,
thanks for your reply.

> Some CPU intensive operations in numpy or pandas do release the GIL, so the threading backend might be a good choice.

True, that's why wrote that it is especially severe for user-defined CPU-bound metric functions. I will try to put together some benchmark for a common sklearn kernel to see the effect there.

> 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.

That would be super nice to have. The question is how long it might take to make it practically usable in sklearn.

> 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.

I observed a huge impact for my user-defined CPU-intensive metric function but for most people, predefined sklearn metrics are more relevant so I will benchmark that first.

> > 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).

Totally agree, automatic memmapping was just a side note

> 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.

Sure, threading is better if it provides the same speed-up, it is just very often not the case with python. That's why many sklearn functions use the default joblib backend based on multiprocessing. If the free threading proves to work well and will be available in sklearn, it might help a lot. But as of now, multiprocessing is the only way to get full parallelism.

I will soon provide some benchmark data.

Labels: New Feature