Repository navigation
Threshold issue for flint_mpn_sqr on raptorlake-pc-linux-gnu #2873
Description
Describe the bug
The cutoff for flint_mpn_sqr seem to use the wrong algorithm around 42k limbs on my system.
Steps to reproduce
Here is a minimal example :
/* flint_mpn_sqr throughput dip around 42k-48k limbs */
#include <stdio.h>
#include <time.h>
#include <gmp.h>
#include <flint/flint.h>
#include <flint/mpn_extras.h>
static double secs(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + 1e-9 * t.tv_nsec; }
int main(void)
{
static ulong a[60000], r[120000];
for (slong i = 0; i < 60000; i++) a[i] = 0x9E3779B97F4A7C15UL * (i + 1);
printf("%8s %14s %14s\n", "limbs", "flint ns/limb", "gmp ns/limb");
for (slong n = 36000; n <= 54000; n += 2000)
{
double t0 = secs(); for (int k = 0; k < 20; k++) flint_mpn_sqr(r, a, n);
double t1 = secs(); for (int k = 0; k < 20; k++) mpn_sqr(r, a, n);
double t2 = secs();
printf("%8ld %14.1f %14.1f\n", n, (t1 - t0) / 20 / n * 1e9, (t2 - t1) / 20 / n * 1e9);
}
return 0;
} limbs flint ns/limb gmp ns/limb
36000 52.5 118.4
38000 44.1 115.7
40000 43.8 127.1
42000 166.9 122.5
44000 166.2 112.9
46000 165.9 108.7
48000 165.2 101.5
50000 50.8 127.2
52000 50.3 125.1
54000 50.0 119.0
Expected behavior
From 42k to 48k limbs, we should also expect around 50 ns/limbs...
System (please complete the following information):
Using latest commit of the git main branch on
13th Gen Intel Core i7-13850HX, AVX2, no AVX-512
Linux 7.0.0-38-generic, gcc 15.2.0, GMP 6.3.0
FLINT 3.7.0-dev @ abb92f3, with FLINT_HAVE_FFT_SMALL 1
FLINT_FFT_SMALL_MUL_THRESHOLD and FLINT_FFT_SMALL_SQR_THRESHOLD are both 500
architecture recognized as raptorlake-pc-linux-gnu
Activity
vneiger commentedon Oct 7, 2026
Many parameters for Raptor Lake are copied directly from values determined for skylake, which can be quite off. See the comments in
https://github.com/flintlib/flint/blob/main/src/mpn_extras/x86_64/raptorlake/flint-mparam.h
If you do measurements that allow you to improve these thresholds (all of the wrong ones, or some of them), feel free to open a PR that improves this
raptorlake/flint-mparamfile! Putting the same values in other files from CPUs similar to RaptorLake (instead of Skylake values that are likely to be less relevant) could be good too.Ideally, at some point, we would have some easy way to determine good values for most of the thresholds in these
flint-mparamfiles (at least those that don't require to run several hours of benchmarks). Currently, you should locate the right profile files (possibly create some profile files), and do things by hand for every value.vneiger commentedon Oct 7, 2026
(My previous message is assuming that the issue only comes from wrongly tuned thresholds in
flint-mparam, but it is maybe more complicated than this?)maelhos commentedon Oct 7, 2026
Can you test that this affect only my architecture ? (if you have time) How about zen 3/4/5 and true skylake with my small example ?
fredrik-johansson commentedon Oct 7, 2026
On Zen 3:
vneiger commentedon Oct 7, 2026
I guess zen4 will be similar to zen3. Here is on two servers, broadwell first and then cascade lake:
maelhos commentedon Oct 7, 2026
Ok, so apparently this has something to do with the number of primes in FFT_SMALL. Honestly, I don't know enough about it to tell why, but in the mpn_mul.c line 1300, replacing
by
Fixes the issue...
fredrik-johansson commentedon Oct 7, 2026
I wonder if this is the same as #2693/#2692, the 8-prime CRT not having enough registers and spilling to memory. If that's the case, it's curious that Zen 3 doesn't suffer the same slowdown.
albinahlback commentedon Oct 7, 2026
It seems like it does slow down for Zen 3, just not as much.