为何Rust中将嵌套循环拆分到函数比单函数实现更快？

问题背景 #

学习Rust时，我编写计算某数值以内质数的程序，发现一个奇怪现象：将嵌套循环的内层拆分到独立函数调用，比单个函数内直接嵌套循环的速度更快。

算法说明 #

程序实现三种质数计算算法：

• algo_a：暴力算法，用每个数除以所有更小的数判断质数
• algo_b：优化算法，仅用已找到的质数判断，内层循环封装在is_prime_reg函数中
• algo_c：与algo_b数学逻辑完全一致，但内层循环直接写在主函数内

测试代码 #

// 获取系统时间
use std::time::{SystemTime};
// 读取输入
use std::io;

fn main() {
    println!("欢迎来到质数计算程序，请输入一个数字，程序将计算2到该数字之间的质数数量。");
    let mut target_input = String::new();
    io::stdin().read_line(&mut target_input).expect("错误：读取数字失败！");
    let target: u64 = target_input.trim().parse().unwrap();
    println!("正在计算直到 {} 的质数。", target);
    println!("使用算法 A。");
    let a = || {
        algo_a(target.clone())
    };
    println!("找到 {} 个质数。", execute_with_timer(a));
    // 算法 B
    println!("使用算法 B。");
    let b = || {algo_b(target.clone())};
    println!("找到 {} 个质数。", execute_with_timer(b));
    // 算法 C
    println!("使用算法 C。");
    let c = || {algo_c(target.clone())};
    println!("找到 {} 个质数。", execute_with_timer(c));
}

fn execute_with_timer<F: Fn()->u64>(closure:F)-> u64 {
    let time_start = SystemTime::now();
    let result = closure();
    let time_end = SystemTime::now();
    let time_passed = time_end.duration_since(time_start).expect("时钟可能回退");
    println!("耗时 {:?}。", time_passed);
    return result;
}

// 无外部函数调用的algo_b版本
fn algo_c(target:u64)->u64{
    let mut counter: u64 = 0;
    // 存储已找到的质数
    let mut found_primes: Vec<u64> = Vec::new();
    let mut is_prime_bool: bool;
    // 包含目标值的范围
    for i in 2u64..=target {
        is_prime_bool = true;
        for p in found_primes.iter() {
            // 如果i能被任意已找到的质数p整除，则不是质数
            if i % p == 0 {
                is_prime_bool = false
            }
        }
        if is_prime_bool {
            counter = counter + 1;
            // 添加到已找到质数列表
            found_primes.push(i);
        }
    }
    return counter;
}

// 使用已找到质数记录的算法
fn algo_b(target:u64)->u64 {
    let mut counter: u64 = 0;
    // 存储已找到的质数
    let mut found_primes: Vec<u64> = Vec::new();
    // 包含目标值的范围
    for i in 2u64..=target {
        if is_prime_reg(i, &found_primes) {
            counter = counter + 1;
            // 添加到已找到质数列表
            found_primes.push(i);
        }
    }
    return counter;
}

// 基于质数记录的判断函数
// 警告：必须按递增顺序循环调用此函数，且需传入已找到的质数列表
fn is_prime_reg(number:u64, found_primes: &Vec<u64>)->bool{
    // 先检查能否被已知质数整除
    for p in found_primes.iter() {
        if number % p == 0 {
            return false;
        }
    }
    return true;
}

// 最慢的暴力算法
fn algo_a(target: u64)->u64{
    let mut counter: u64 = 0;
    // 包含目标值的范围
    for i in 2u64..=target {
        if is_prime_simplest(i) {
            counter = counter + 1;
        }
    }
    return counter;
}
// 简单暴力算法：用每个数除以所有更小的数判断质数
fn is_prime_simplest(number: u64) -> bool{
    // 尝试寻找能整除的数，找到则不是质数
    // 不包含自身的范围
    for i in 2u64..number {
        if number % i == 0 {
            return false;
        }
    }
    return true;
}

测试结果 #

两种编译模式下，algo_c运行速度远慢于algo_b，甚至调试编译时比暴力的algo_a还慢：

• 调试编译（cargo run）：algo_a耗时5.447s，algo_b耗时1.091s，algo_c耗时12.764s
• 发布编译（cargo build -r）：algo_a耗时1.663s，algo_b耗时169.89ms，algo_c耗时1.833s

更换u32、u16等数值类型后，algo_c仍为最慢算法。

原因解析 #

核心差异在于循环终止的提前退出逻辑：

1. algo_b的is_prime_reg函数：一旦找到能整除的质数，就通过return false直接终止内层循环并返回结果，完全避免后续不必要的迭代。
2. algo_c的内层循环：即使找到能整除的质数，仅将is_prime_bool设为false，但循环会继续遍历整个found_primes列表直到结束。随着已找到质数的数量增加，这种无用迭代的次数会急剧上升，直接拖慢整体速度。

举个实例：判断15是否为质数时，algo_b在检查到3能整除15后立即返回false，循环结束；而algo_c会继续遍历5、7、11、13等所有已找到的质数，完全是做无用功。

此外，Rust编译器的优化也会放大这种差异：is_prime_reg的提前返回逻辑更容易被编译器识别并优化，而algo_c中is_prime_bool的赋值操作可能让编译器难以判断是否可以提前终止循环，优化效果远不如algo_b。

内容的提问来源于stack exchange，提问作者algo