nmod_vec.hSIMD kernels of the element-wise operations
On x86-64 with AVX-512 (F, DQ and VL) or AVX2, and on ARM64 with NEON, _nmod_vec_reduce, _nmod_vec_mul, _nmod_vec_scalar_mul_nmod and _nmod_vec_scalar_addmul_nmod run vector kernels chosen from the size of , and so do their lazy variants (Lazy variants). The instruction set is the one FLINT is compiled for (for instance -march=native, which configure sets by default): there is no run-time detection, and FLINT_MACHINE_VECTORS_FORCE_GENERIC or FLINT_MACHINE_VECTORS_STRICT_C turn the kernels off. Below NMOD_VEC_SIMD_MIN_LEN entries the scalar code runs: 8, or with the 512-bit kernels FLINT_NMOD_VEC_AVX512_MIN_LEN of flint-mparam.h, which is 16 on Intel processors. Inside FLINT functions, where the length varies from call to call, the kernels lost on vectors of fewer than 8 entries. On Intel, a 512-bit load of entries written just before by narrow stores waits for these stores, which cannot forward their data to it: 8 to 15 such entries ran at 0.60-0.95x (Ice Lake, Cascade Lake, Nov 2026), and Zen 4 has no such loss.
With AVX-512, the last entries are handled by one masked vector rather than a scalar tail. From 128 entries, when the output is not aligned to 64 bytes and every vector has the same offset modulo 64 bytes, one masked vector first handles the entries up to the next 64-byte boundary, so that the main loop reads and writes whole cache lines. With AVX2, under the same conditions modulo 32 bytes, the scalar code first handles the entries up to the next 32-byte boundary, so that the 256-bit loads and stores do not cross cache lines. On ARM64, from 16 entries, the NEON kernels are interleaved with the scalar code, 4 entries of each per block of 8 (the scalar multiplier runs beside the NEON one); the NEON kernels alone handle the rest.
On Intel processors up to Ice Lake (Skylake-SP, Cascade Lake, Ice Lake-SP), 512-bit multiplications lower the clock of the core for some time after they run. After the multiplying kernels the clock was 12-22% lower on Cascade Lake. The kernels remain faster than the scalar code, but the scalar code that follows them runs slower: functions that alternate short kernel calls with scalar work are slightly impacted (e.g. nmod_mpoly_gcd and the geometric evaluation and interpolation, ran at 0.80-0.90x on Cascade Lake). Intel Sapphire Rapids and AMD Zen 4 show no such fixed offset, and Ice Lake and Rocket Lake client processors little or none.
Below, has bits, , and is the constant of NMOD_RED (Barrett reduction with an nmod_t), on 64-bit machines.
Reduction of words#
_nmod_vec_reduce reduces any 64-bit words. Its kernels use products of 32-bit halves only, with the constant (Barrett reduction with an nmod_t).
| Kernel | Method | Corrections | |
|---|---|---|---|
| 64 | fullword | one | |
| 33 to 63 | top32 | , then | one (two at 33) |
| 6 to 32 | fold29 | , then and | one |
| 2 to 5 | fold32 | , then with , and | two (, then ) |
With 32-bit words, is a two-word integer and, for , is a one-word modulus: these kernels are reductions of Barrett and Lemire reduction at that word size. The top32 kernel is the estimate of NMOD_RED from the top halves of and ; the fold29 kernel is the step of NMOD_RED2_BOUNDED after a fold; the fold32 kernel folds as n_lll_mod_barrett does, where NMOD2_RED2 would reduce the high half and take a Möller–Granlund step. AVX-512 computes for with one vpmullq, AVX2 and NEON with two products of 32-bit halves (). NEON has no kernel for , where the scalar code was faster.
Lemma 1. Let , and . Then for , and for .
Proof. Write with . From ,
so , and . Both and are below , so : at most 2 for and 3 for , and is below , respectively .
Lemma 2. Let , and as in the table. Then , and .
Proof. The high part times is below , and the low part is below , so . This is the hypothesis of Theorem 4 of Barrett and Lemire reduction with 32-bit words, whose constant is and whose estimate is . That theorem assumes , so that fits a 32-bit word; its proof of only uses , which also holds for , and the kernels compute in 64 bits.
For , the fold is that of Two and three words with in place of the word base: , which exceeds the bound of Theorem 4 of Barrett and Lemire reduction. So , and the argument of Lemma 1 with gives , hence the two corrections. This constant exceeds , so the kernels compute as . Every product in these kernels has both factors below , except for , which AVX2 and NEON split into two such products.
The full Barrett step of NMOD_RED, with the high half of a product emulated from 32-bit products, was 1.3 to 1.6 times slower than these kernels.
Products of two vectors#
_nmod_vec_mul multiplies reduced entries. Its kernels:
| AVX-512 | AVX2 | NEON | |
|---|---|---|---|
| 2 to 32 | halflimb | halflimb | halflimb, hybrid from 16 entries |
| 33 to 50 | ifma50 (with AVX512-IFMA), else fp50 | fp50 | fp50 |
| 51 to 62 | red2bounded | scalar code | scalar code |
| 63, 64 | scalar code | scalar code | scalar code |
The halflimb kernels, for , take a 32-bit Barrett step on the product , which fits a word: with , or for and for , so that . For , and Theorem 4 of Barrett and Lemire reduction with 32-bit words, as in Lemma 2, gives . For the same argument gives , where the last two terms, convex in , stay below 3 on : so , and the kernels correct by , then by .
The fp50 kernels compute in with the rounded quotient, as vec4d_mulmod (Multiplication), and add to a negative result. The ifma50 kernel splits with two 52-bit products, takes and (for , , so that the constant fits 52 bits), and computes modulo as , which is exact since : for this is Theorem 4 of Barrett and Lemire reduction with 52-bit words, and for its proof still applies, since , half the bound of that theorem, leaves room for the halved constant.
The red2bounded kernel, for , forms the full product and reduces it as NMOD_RED2_BOUNDED (Two words below a bound), whose estimate leaves a remainder below ; the high word of is computed from three 32-bit products and may be up to 2 too small, so the quotient may be one less and the remainder is below : two corrections. Without AVX-512, this kernel, with its 64-bit products emulated, was slower than the scalar code.
Products by a scalar#
_nmod_vec_scalar_mul_nmod and _nmod_vec_scalar_addmul_nmod, for , use Shoup's method in several radixes, with computed once; _nmod_vec_scalar_addmul_nmod adds the result and corrects once more.
| AVX-512 | AVX2 | NEON | |
|---|---|---|---|
| 2 to 32 | shoup32 | shoup32 | shoup32 |
| 33 to 50 | shoup52 (with AVX512-IFMA), else fp50 | fp50 | fp50 (scalar_mul only) |
| 51 | shoup52 (with AVX512-IFMA), else shoup64lazy | scalar code | scalar code |
| 52 to 62 | shoup64lazy | scalar code | scalar code |
| 63 | shoup64 | scalar code | scalar code |
| 64 | scalar code | scalar code | scalar code |
In radix or , with for , Lemma 1 of Multiplication by a fixed operand (Shoup) holds for entries : the quotient is or one less, and . With 32-bit products (shoup32) the difference is computed exactly in 64 bits; with IFMA (shoup52) it is computed modulo as , which requires , hence . In shoup64lazy the high word of is computed from three 32-bit products and may be up to 2 too small, so , below for , and the kernel corrects by , then by ; in shoup64, for , it is exact.
The fp50 kernels are the doubles of Products of two vectors, with in place of the second entry; on AVX-512 without IFMA, they were faster than shoup64lazy at 33 to 50 bits. On AVX2, Shoup's method above 32 bits, with emulated 64-bit products, and on NEON, Shoup's method above 32 bits and the doubles for scalar_addmul, were slower than the scalar code.
Lazy variants#
_nmod_vec_reduce_lazy, _nmod_vec_mul_lazy, _nmod_vec_scalar_mul_nmod_lazy and _nmod_vec_scalar_addmul_nmod_lazy require , that is on the 64-bit machines that have these kernels, and run the kernels above without their last correction, so that their outputs are in . Before that correction, every kernel already has a value below :
- the remainders of top32 for , fold29, halflimb for , ifma50, shoup32 and shoup52 are below (Lemma 1, Lemma 2, Products of two vectors, Products by a scalar);
- top32 at , fold32, halflimb at , red2bounded and shoup64lazy correct by or first, which leaves a value below from a remainder below or ;
- the doubles kernels give in instead of correcting .
_nmod_vec_scalar_addmul_nmod_lazy also accepts entries of res in : the sum with a product in is below and is corrected once, by . On AVX2 this sum is corrected on 64-bit lanes, since may exceed at 31 bits; in the doubles kernels, gets added when negative. The entries of vec must be reduced, also when vec is res.
The doubles kernels of AVX-512 and AVX2 convert to an integer by adding instead of (the sum is an integer below , so it is exact), one addition fewer than adding first; NEON converts with one instruction and adds .
The lazy functions run the exact code, whose outputs are reduced, for vectors of fewer than NMOD_VEC_SIMD_MIN_LEN entries, without SIMD, for , and in the following cases:
| Function | AVX-512 | AVX2 | NEON |
|---|---|---|---|
_nmod_vec_reduce_lazy | none | none | |
_nmod_vec_mul_lazy | none | ||
_nmod_vec_scalar_mul_nmod_lazy | none | ||
_nmod_vec_scalar_addmul_nmod_lazy | none |
In these cases and without SIMD, from 8 entries and for , the products by a scalar run instead Shoup's product without its last correction, which is in (Lemma 1 of Multiplication by a fixed operand (Shoup)), and _nmod_vec_scalar_addmul_nmod_lazy adds res and corrects the sum, below , by : against the exact code, 1.05-1.66x at 8 to 12 entries and 1.06-1.53x from 16 entries (Nov 2026). For , _nmod_vec_scalar_addmul_nmod_lazy runs the one-word loop of the exact code on res in directly: fits one word.
_nmod_vec_scalar_mul_nmod_lazy also runs the exact code for (a zeroing, a copy or a negation), and _nmod_vec_scalar_addmul_nmod_lazy leaves res unchanged for . Where _nmod_vec_scalar_addmul_nmod_lazy runs the exact code, it first reduces res.
Against the exact functions, on long vectors (Nov 2026): reduce 1.11-1.64x, mul 0.99-1.29x, scalar_mul 1.08-1.60x, scalar_addmul 1.04-1.35x, NEON 1.13-1.60x; shoup52 1.10-1.21x; the fold of into 1.03-1.16x more for the doubles kernels. With the ifma50 kernel, _nmod_vec_mul_lazy gained nothing (0.87-1.10x).
The FLINT team, “SIMD kernels of the element-wise operations (nmod_vec.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_vec/simd.html (generated 2026-11-20).
@misc{flint-doc-nmod-vec-simd,
author = {{The FLINT team}},
title = {{SIMD kernels of the element-wise operations (nmod\_vec.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/nmod_vec/simd.html},
note = {Generated 2026-11-20}
}