Talip7/scikit-learn-issues-multilabel huggingface dataset:
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
> i think the main resistance would be to adding new c/c++ code to the codebase due to the maintenance burden on new contributors. (not sure how our stance on that changed since ive last been active though!)

We're working on a plugin API for these usecases, but it's still early on in the development.

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
I think C/C++/SyCL implementations (cc @fcharras, who is working on GPU implementations for scikit-learn) with Python bindings (done with Cython, PyBind11 or nanobind) is adapted.

Yet, I think we need to consider current performance bottlenecks, complexity which is currently handled by Cython first (e.g. how to compile and link against BLAS?), the number of people interested by such development, and ongoing work on performance (algorithm redesign, Array API support, Cython implementations, GPU implementations, etc.).

Currently, I do not know what people think about exploring such alternatives for scikit-learn.

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
I think at this point I agree that there are better ways to handle this than natively supporting/_requiring_ `SSE3`. In particular, what do people think about the following strategy:
1. Update some `metric` arguments to accept `DistanceMetric` objects directly
2. Provide separate SIMD-accelerated implementations of different distance metrics in perhaps a `scikit-learn-contrib` package
3. Offer them as an alternative option in the documentation for those users looking to squeeze out more performance

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
>  2. Provide separate SIMD-accelerated implementations of different distance metrics in perhaps a scikit-learn-contrib package

I would prefer exploring the notion of plugin, that we have already started exploring elsewhere to add optimized code.

While plugins are a slightly longer-term option, I believe that they can provide the user much more value, as they can open the door to speeding up larger codebases, made of chains of operations, without modifying the user-level code.

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
AFAIC, apache arrow C++ uses xsimd. More generally, can we ask some libraries for their experience with xsimd? A second point is that we then would officially allow more C++. I personally would be fine with this. C++ templates, for instance, seem ways cleaner and more future proof than Cython tempita templating. The point is that this should be a deliberate decision.

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
> AFAIC, apache arrow C++ uses xsimd

Yes, the developers of Firefox also recently have chosen [to vendor xsimd](https://hg.mozilla.org/integration/autoland/rev/cc85c70a650f) and [to use it for their webaudio engine](https://hg.mozilla.org/integration/autoland/rev/cacbaf94a69e).

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
> I personally would be fine with this. C++ templates, for instance, seem ways cleaner and more future proof than Cython tempita templating. The point is that this should be a deliberate decision.

What do you think of first starting to develop a plugin to isolate C++ implementations from scikit-learn's code-base, coming up with a comparison of execution time and maintainability, and deciding on a solution?

Labels: Enhancement, Needs Decision, cython
Introduce SIMD intrinsics for `_dist_metrics.pyx`

# Context
Pairwise distance computation is an essential part of many estimators in scikit-learn, and can take up a significant portion of run time in certain workflows. I believe that we may achieve significant performance gains in several (perhaps most) distance metric implementations by leveraging SIMD intrinsics.

# Proof of Concept

I built a quick proof of concept just to see what kinds of performance gains we could observe with a potentially-naive implementation of SIMD intrinsics. I chose to optimize the `ManhattanDistance.dist` function. This implementation uses intrinsics found in `SSE{1,2,3}`. To ensure that the instructions are supported, it checks for the presence of the `SSE3`  instruction set (`SSE3` implies `SSE{1,2}`) and provides the optimized implementation if so. Otherwise it provides a dummy implementation just to appease Cython, and the main function falls back to the current implementation on `main`. Note that on most modern hardware, support for `SSE3` is a reasonable expectation (indeed numpy assumes it is always present when optimization is enabled). For the specific implementation referred to here, please take a look at this PR: https://github.com/Micky774/scikit-learn/pull/11

Note that the full benefit of the intrinsics are gained when compiling with `-march="native"`, however the benefit is still significant when compiling with `-march="nocona"`, as is often default (e.g when following the scikit-learn development instructions on linux).

# Benchmarks
The following benchmarks were produced by this gist: https://gist.github.com/Micky774/567a5fa199c05d90c4c08625b077840e

### **Summary: The SIMD implementations are ~2x faster than the current implementation for `float32` and 1.5x faster for `float64`.**

<details>
<summary>Plots</summary>

![f2b1f1e8-59b0-4ec5-b91c-fe1d19abd9ec](https://user-images.githubusercontent.com/34613774/228374474-99ee13b3-228d-4c53-9dcc-3a8f8b639a9f.png)
</details>

# Discussion
I haven't looked too deeply into this yet, as first I wanted to see whether there was interest in the venture. I would love to hear what the other maintainers' thoughts are regarding exploring this route in a bit more detail. Obviously SIMD implementations will bring with them added complexity, but the performance gains are pretty compelling. In my opinion, the tradeoff is worth it.

CC: @scikit-learn/core-devs

COMMENT:
Just for info: numpy went with [google‘s Highway](https://github.com/google/highway) in https://github.com/numpy/numpy/pull/24018.

Labels: Enhancement, Needs Decision, cython