是`iter().map().sum()`和`iter().fold()`一样快？

Question

编译器是否为iter().map().sum()和生成相同的代码iter().fold()？最终他们实现了相同的目标,但第一个代码将迭代两次,一次为map一次,一次为sum.

这是一个例子.哪个版本更快total？

pub fn square(s: u32) -> u64 {
    match s {
        s @ 1...64 => 2u64.pow(s - 1),
        _ => panic!("Square must be between 1 and 64")
    }
}

pub fn total() -> u64 {
    // A fold
    (0..64).fold(0u64, |r, s| r + square(s + 1))
    // or a map
    (1..64).map(square).sum()
}

什么是看待装配或基准测试的好工具？

Answer 1

为了让他们生成相同的代码,他们首先必须做同样的事情.你的两个例子不是:

fn total_fold() -> u64 {
    (0..64).fold(0u64, |r, s| r + square(s + 1))
}

fn total_map() -> u64 {
    (1..64).map(square).sum()
}

fn main() {
    println!("{}", total_fold());
    println!("{}", total_map());
}

18446744073709551615
9223372036854775807

让我们假设你的意思

fn total_fold() -> u64 {
    (1..64).fold(0u64, |r, s| r + square(s + 1))
}

fn total_map() -> u64 {
    (1..64).map(|i| square(i + 1)).sum()
}

有几种方法可以检查:

1. 生成的LLVM IR
2. 生成的程序集
3. 基准

IR和组装的最简单来源是游乐场之一(官方或备用).这两个都有按钮来查看组件或IR.您也可以传递--emit=llvm-ir或--emit=asm编译器来生成这些文件.

确保在释放模式下生成装配或IR.该属性#[inline(never)]通常用于保持函数分离,以便在输出中更容易找到它们.

基准测试记录在Rust编程语言中,因此无需重复所有有价值的信息.

在Rust 1.14之前,这些不会生成完全相同的程序集.在我担心之前,我会等待基准测试/分析数据,看看是否会对性能产生任何有意义的影响.

从Rust 1.14开始,他们确实生产相同的组件!这是我爱Rust的原因之一.您可以编写清晰且惯用的代码,聪明的人也可以同样快速地编写代码.

但是第一个代码将迭代两次,一次为map一次,一次为sum.

这是不正确的,我很想知道消息来源告诉你什么,所以我们可以在那时纠正它,防止将来的误解.迭代器以拉取为基础运行; 一次处理一个元素.核心方法是next产生单个值,运行足够的计算来产生该值.

Answer 2

首先,让我们修复这些示例以实际返回相同的结果:

pub fn total_fold_iter() -> u64 {
    (1..65).fold(0u64, |r, s| r + square(s))
}

pub fn total_map_iter() -> u64 {
    (1..65).map(square).sum()
}

现在,让我们开始吧fold.A fold只是一个循环和一个累加器,大致相当于:

pub fn total_fold_explicit() -> u64 {
    let mut total = 0;
    for i in 1..65 {
        total = total + square(i);
    }
    total
}

然后,让我们去map和sum,并打开第sum一个,这大致相当于:

pub fn total_map_partial_iter() -> u64 {
    let mut total = 0;
    for i in (1..65).map(square) {
        total += i;
    }
    total
}

它只是一个简单的累加器!现在,让我们打开map图层(只应用一个函数),获得大致相当于的东西:

pub fn total_map_explicit() -> u64 {
    let mut total = 0;
    for i in 1..65 {
        let s = square(i);
        total += s;
    }
    total
}

如您所见,它们两者非常相似:它们以相同的顺序应用相同的操作并具有相同的总体复杂性.

哪个更快？我不知道.而微观基准测试可能只能说出一半的真相:只是因为微基准测试中的某些东西更快并不意味着它在其他代码中更快.

然而,我可以说,它们都具有相同的复杂性,因此应该表现得相似,即彼此相互影响.

而且我个人会选择map+ sum,因为它更清楚地表达了意图,而fold方法的"厨房水槽" Iterator因此信息量更少.