NEP 53 — Deciding on adoption Google Highway to underpin NumPy's SIMD functionality

--- tags: NumPy --- # NEP 53 — Deciding on adoption Google Highway to underpin NumPy's SIMD functionality :Author: <list of authors' real names and optionally, email addresses> :Status: <Draft | Active | Accepted | Deferred | Rejected | Withdrawn | Final | Superseded> :Type: <Standards Track | Process> :Created: <date created on, in yyyy-mm-dd format> :Resolution: <url> (required for Accepted | Rejected | Withdrawn) Abstract -------- We are moving the SIMD intrinsic framework, Universal Intrinsics, from C to C++. We are also moving to meson as a build system. The Google Highway intrinsics project is proposing we use Highway instead of our Universal Intrinsics as describe in `NEP 38`_. and this NEP is an attempt to describe what needs to be done. Motivation and Scope -------------------- In addition to moving to the meson build system, we want to refactor the C-based Universal Intrinsics from NEP 38 to C++. Along the way the Google Highway people proposed using Highway rather than our Universal Intrinsics. The move from C to C++ is motivated by (a) code readability and ease of development, (b) the need to add support for sizeless SIMD instructions (e.g., ARM SVE). Usage and Impact ---------------- N/A Backward compatibility ---------------------- There will be no changes in user-facing APIs: all the methods to control compilation and runtime CPU feature selection should remain, although there may be some changes due to moving to meson and C++ without regards to the Highway/Universal Intrinsics choice. On Windows, MSVC may have to be avoided. This means that we have to build our wheels with Clang-cl or Mingw-w64. It may also impact other redistributors or end users who build from source on Windows. High-level considerations ------------------------- Development effort and long-term maintainability ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ While moving to Highway may be quite an effort, it should increase the bus factor of SIMD support. There is also more of an opportunity to share work with other people and projects, like JPEG XL and Firefox. TODO: link of projects who adopted Highway. Migration strategy - can it be gradual? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Universal intrinsics could be done gradually, as already seen in `GH-24018`_. However, adopting the runtime dispatching has to be done in one go - we can't have two ways of doing that. Highway policies for compiler and platform support ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - Fairness across architectures - Not subject to Google's "no longer supported" strategy - Multiple maintainers in Google, one outside it (as of now) - Jan proposed to add "...." to the documented policy - As long as it runs under an up-to-date version of QEMU, it will remain supported. Compilation strategy for multiple targets ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Highway compiles once while using preprocessing tricks to generate multiple stanzas for each cpu feature within the same compilation unit. Universal Intrinsics generate multiple compilation units, one for each cpu feature group, and compiles multiple times, linking them all together (with difference names) for dispatch. The Highway technique may not work reliably on MSVC, the Universal Intrinsic technique does work on MSVC. Which one is more robust? Our experience for the past four years says that bugs with "invalid instruction" type crashes are invariably due to issues with feature detection - most often because users are running under emulation, and sometimes because there are actual issues with our CPU feature detection code. There is no risk of the linker pulling in a function which is compiled multiple times for different architectures and picking the one with unsupported instructions. C++ refactoring considerations ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We want to refactor to C++ for two main reasons: - get rid of the NumPy-specific templating language for more expressive C++ - this would make using sizeless intrinsics (like for SVE) easier. - If we use Highway, we would need to switch the C++ wrappers from universal intrinsics to Highway, but in any case the work to move to C++ is not complete. - rewriting existing kernels using Highway intrinsics, but in any case we need to refactor to use C++. - Use of tags (Sayed's concern) - Obtaining a function pointer instead of calling a function directly, so that we can be sure that calling 1-D inner loop many times for a single Python API invocation does not incur the dispatching overhead many times. Investigated: can be done with Highway too. Runtime dispatch ~~~~~~~~~~~~~~~~ specifying features for runtime dispatch or more to the point to prevent runtime dispatch on certain features dispatching inner loops on selected features: a desire to setup dispatching only once and not on every kernel call - Granularity of instruction set groups: NumPy has a more granular set of architectures than Highway. We'd lose this - but that is probably fine, we don't need this level of granularity. ``_simd`` testing module ~~~~~~~~~~~~~~~~~~~~~~~~ - rewriting the ``_simd testing`` module to use C++ and/or to Highway - would be good to do earlier rather than later for kernel rewriting - nicer than `googletest` Math routines ~~~~~~~~~~~~~ - Highway has a few, but not precise enough for Numpy's needs. - SLEEF does, but no longer maintained - JPEG XL and some other Highway-using libraries may have some (e.g., convolutions) - etc. Help Highway be more complete ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - missing IBM-Z support - prototyping kernels via a Python interface Meson changes to be upstreamed (if no Highway runtime dispatching) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Build time detection needs a new module in meson to detect all the CPU features at build time. If we use Highway, we only need to know the CPU family, the baseline, and the extended features. Meson already has what we need for this purpose, e.g. using `host_machine.cpu_family()` (see [here](https://mesonbuild.com/Reference-tables.html#cpu-families)). TODO: Ralf Timing of releases: 1.26 and 2.0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Aug 4th: 3.12.0rc1 - need NumPy 1.26.0b1 release, doesn't need SIMD support (performance doesn't matter yet for a beta) Oct 4th: 3.12.0 final - Need NumPy 1.26.0 release including SIMD support Dec 31, 2023: NumPy 2.0.0 If we go the Highway route `````````````````````````` If we go with Universal Intrinsics translated to C++ ``````````````````````````````````````````````````` Current plan is to branch `maintenance/1.26.x` off of ``maintenance/1.25.x``. Meson build system changes need to be backported to that branch. On ``main`` we already changed C API/ABI, hence we want to avoid branching a new 1.X release off of it. Related Work ------------ - NEP 38 (xref its related work section) - Google Highway - Xsimd - OpenCV Implementation -------------- TODO Alternatives ------------ Xsimd SLEEF Discussion ---------- References and Footnotes ------------------------ .. [1] Each NEP must either be explicitly labeled as placed in the public domain (see this NEP as an example) or licensed under the `Open Publication License`_. .. _Open Publication License: https://www.opencontent.org/openpub/ .. _`NEP 38`: https://numpy.org/neps/nep-0038-SIMD-optimizations.html .. _`GH 24018`: https://github.com/numpy/numpy/pull/24018 Copyright --------- This document has been placed in the public domain. [1]_

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.