please add it in the list here: .github/workflows/benchmarks.yml

GNU testsuite comparison:

Skipping an intermittent issue tests/tail/overlay-headers (passes in this run but fails in the 'main' branch)

Added to the list!

GNU testsuite comparison:

Skip an intermittent issue tests/misc/tee (fails in this run but passes in the 'main' branch)

CodSpeed Performance Report

Merging #9182 will not alter performance

_{Comparing asder8215:factor_benchmarking (d977e29) with main (1074071)}

Summary

✅ 123 untouched
🆕 3 new
⏩ 2 skipped¹

Benchmarks breakdown

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)

I didn't expect it to take this long to run the benchmark. I think I'll reduce the range of numbers to iterate through for multiple_big_uint.

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)
Skipping an intermittent issue tests/tail/overlay-headers (passes in this run but fails in the 'main' branch)

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)

GNU testsuite comparison:

Skipping an intermittent issue tests/tail/overlay-headers (passes in this run but fails in the 'main' branch)

please change the input sizes.
#9182 (comment)
benchmarks should be around 100 to 400 ms

also, 6 benchmarks seem a bit big, can we have 2 or 3 instead? thanks

I took off the single benchmark tests and kept the multiple u64/u128/BigUint benchmark tests (with smaller range of numbers to factorize) since it would be easier to notice any improvement on the factor command from those cases. In total, those 3 benchmark tests take about 350-400 ms to run (when run locally).

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)

thanks

seems that it is quite an unstable bench
#9174 (comment)
#9198 (comment)
etc
could you please have a look? thanks

I took a closer look at the num_prime crate source code and there is a bit of randomization going on for factorize128() and factors() (the same goes for factorize64(), but the docs denotes the primality check for u64s to be faster and deterministic). This might be the cause for why benchmarking for factors is a bit unstable, especially with the small range of numbers I'm using for u128/>u128 integers.

In fact, now that I look at it, factors() calls on factorize128() if the number is within the u128 range, which that function then calls on factorize64() if it sees that the number is within u64 range. Previous to the change in #9171, I think the overhead of calling factorize128() and then factorize64() from factors() made a small difference for the u64 case (which adds up as you increase the range of values piped to factors command via seq).

Do you want me to comment out the u128 and BigUint benchmark cases? I'm not sure if I can show a stable result with this small range of values (and possibly not within the range of millisecond benchmarking).

Do you want me to comment out the u128 and BigUint benchmark cases? I'm not sure if I can show a stable result with this small range of values (and possibly not within the range of millisecond benchmarking).

if possible, yes, we really need something stable here
do you know it is random ?

The piece of randomization I see is over here:

let divisor = loop {
            // try various factorization method iteratively, sort by time per iteration
            const NMETHODS: usize = 3;
            match i % NMETHODS {
                0 => {
                    // Pollard's rho
                    let start = MontgomeryInt::new(random::<u128>(), &target);
                    let offset = start.convert(random::<u128>());
                    let max_iter = max_iter_ratio << (target.bits() / 6); // unoptimized heuristic
                    if let (Some(p), _) = pollard_rho(
                        &SmallMint::from(target),
                        start.into(),
                        offset.into(),
                        max_iter,
                    ) {
                        break p.value();
                    }
                }
                1 => {
                    // Hart's one-line
                    let mul_target = target.checked_mul(480).unwrap_or(target);
                    let max_iter = max_iter_ratio << (mul_target.bits() / 6); // unoptimized heuristic
                    if let (Some(p), _) = one_line(&target, mul_target, max_iter) {
                        break p;
                    }
                }
                2 => {
                    // Shanks's squfof, try all mutipliers
                    let mut d = None;
                    for &k in SQUFOF_MULTIPLIERS.iter() {
                        if let Some(mul_target) = target.checked_mul(k as u128) {
                            let max_iter = max_iter_ratio * 2 * mul_target.sqrt().sqrt() as usize;
                            if let (Some(p), _) = squfof(&target, mul_target, max_iter) {
                                d = Some(p);
                                break;
                            }
                        }
                    }
                    if let Some(p) = d {
                        break p;
                    }
                }
                _ => unreachable!(),
            }
            i += 1;

            // increase max iterations after trying all methods
            if i % NMETHODS == 0 {
                max_iter_ratio *= 2;
            }
        };

Whenever factorize128() and factors() aren't able to find prime factors of the given number using small primes table it has in: https://docs.rs/num-prime/latest/src/num_prime/tables.rs.html, it iterates through various factorization methods to compute the prime factor for these numbers. Pollard's rho has a bit of randomization with the start and offset, so my assumption is that sometimes this iterative loop could end early or later than normal if Pollard's rho finds a good start/offset value.

This isn't an issue for u64 integers because the small primes table fits for the numbers within the 64 bit range (especially with the sequence of 2-2502 I'm using for u64), but when you have u128 or >u128 integers, it seems like it will often drop to this loop of various factorization methods num_prime crate uses.

I'm not certain on how to reason about this in a stable manner for multiple u128/>u128 integers.