logo标签列表

Rust中的函数式编程是否零成本？

functional-programmingrust
7

我在Rust中进行了一些函数式编程性能测试:

extern crate rand; // 0.5.5

use rand::Rng;

fn time(f: impl FnOnce()) -> std::time::Duration {
    let s = std::time::Instant::now();
    f();
    s.elapsed()
}

fn main() {
    let iteration = 10000000;

    let mut rng = rand::thread_rng();
    println!(
        "while: {:?}",
        time(|| {
            let mut i = 0;
            let mut num = 0i64;
            while i < iteration {
                num += rng.gen::<i64>();
                i += 1;
            }
        })
    ); // 29.116528ms

    println!(
        "for: {:?}",
        time(|| {
            let mut num = 0i64;
            for _ in 0..iteration {
                num += rng.gen::<i64>();
            }
        })
    ); // 26.68407ms

    println!(
        "fold: {:?}",
        time(|| {
            rng.gen_iter::<i64>().take(iteration).fold(0, |x, y| x + y);
        })
    ); // 26.065936ms
}

我已将优化标志设置为编译它。

这三种情况所花费的时间几乎相同，这是否意味着Rust中的函数式编程是零成本的？

“Zero-cost”在什么意义上？与手动编译的命令式代码等效相比，零额外成本？这将假定编译器始终可以内联和专门化高阶函数，包括多态类型，这似乎很难保证。 - Don Stewart
这一切对我来说只意味着随机数生成器所需的时间比外观技术之间的任何差异都要长得多。 - dcorking
3
是的，LLVM 优化器可以将迭代器优化为正确且快速的命令式代码，并且 Rust 和 LLVM 都进行了很多内联。然而，我不太有资格告诉您使用了哪些具体的优化技术。 - Vladimir Matveev
@dcorking 这是真的。实际上，我不知道如何让这种比较更有意义。我不知道如何控制编译器只优化代码的正确部分。欢迎提出任何建议。 - Amos
2个回答
11

标准表现注意事项：像往常一样，您应该在自己的场景中对代码进行基准测试，并了解权衡。从易于理解的代码开始，并在必要时使其更快。

这里是函数，已拆分并设置为永不内联。我还防止了随机数生成器被内联，并且将迭代次数缩小以供后续使用：

extern crate rand; // 0.5.5

use rand::{distributions::Standard, Rng, RngCore};

const ITERATION: usize = 10000;

#[inline(never)]
fn add_manual(mut rng: impl Rng) -> i64 {
    let mut num = 0;

    let mut i = 0;
    while i < ITERATION {
        num += rng.gen::<i64>();
        i += 1;
    }

    num
}

#[inline(never)]
fn add_range(mut rng: impl Rng) -> i64 {
    let mut num = 0;

    for _ in 0..ITERATION {
        num += rng.gen::<i64>();
    }

    num
}

#[inline(never)]
fn add_fold(mut rng: impl Rng) -> i64 {
    rng.sample_iter::<i64, _>(&Standard)
        .take(ITERATION)
        .fold(0i64, |x, y| x + y)
}

#[inline(never)]
fn add_sum(mut rng: impl Rng) -> i64 {
    rng.sample_iter::<i64, _>(&Standard).take(ITERATION).sum()
}

// Prevent inlining the RNG to create easier-to-inspect LLVM IR
struct NoInlineRng<R: Rng>(R);

impl<R: Rng> RngCore for NoInlineRng<R> {
    #[inline(never)]
    fn next_u32(&mut self) -> u32 {
        self.0.next_u32()
    }
    #[inline(never)]
    fn next_u64(&mut self) -> u64 {
        self.0.next_u64()
    }
    #[inline(never)]
    fn fill_bytes(&mut self, dest: &mut [u8]) {
        self.0.fill_bytes(dest)
    }
    #[inline(never)]
    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand::Error> {
        self.0.try_fill_bytes(dest)
    }
}

fn main() {
    let mut rng = NoInlineRng(rand::thread_rng());
    let a = add_manual(&mut rng);
    let b = add_range(&mut rng);
    let c = add_fold(&mut rng);
    let d = add_sum(&mut rng);

    println!("{}, {}, {}, {}", a, b, c, d);
}

对应的LLVM IR，来自于在发布模式下构建的Rust 1.29.2：

; playground::add_manual
; Function Attrs: noinline uwtable
define internal fastcc i64 @_ZN10playground10add_manual17hb7f61676b41e00bfE(i64** dereferenceable(8)) unnamed_addr #4 personality i32 (i32, i32, i64, %"unwind::libunwind::_Unwind_Exception"*, %"unwind::libunwind::_Unwind_Context"*)* @rust_eh_personality {
start:
  br label %bb4

bb3:                                              ; preds = %bb4
  ret i64 %2

bb4:                                              ; preds = %bb4, %start
  %num.09 = phi i64 [ 0, %start ], [ %2, %bb4 ]
  %i.08 = phi i64 [ 0, %start ], [ %3, %bb4 ]
  %rng.val.val = load i64*, i64** %0, align 8
; call <playground::NoInlineRng<R> as rand_core::RngCore>::next_u64
  %1 = tail call fastcc i64 @"_ZN71_$LT$playground..NoInlineRng$LT$R$GT$$u20$as$u20$rand_core..RngCore$GT$8next_u6417h0b95e10cc642939aE"(i64* %rng.val.val)
  %2 = add i64 %1, %num.09
  %3 = add nuw nsw i64 %i.08, 1
  %exitcond = icmp eq i64 %3, 10000
  br i1 %exitcond, label %bb3, label %bb4
}

; playground::add_range
; Function Attrs: noinline uwtable
define internal fastcc i64 @_ZN10playground9add_range17h27ceded9d02ff747E(i64** dereferenceable(8)) unnamed_addr #4 personality i32 (i32, i32, i64, %"unwind::libunwind::_Unwind_Exception"*, %"unwind::libunwind::_Unwind_Context"*)* @rust_eh_personality {
start:
  br label %bb8

bb6:                                              ; preds = %bb8
  ret i64 %3

bb8:                                              ; preds = %bb8, %start
  %num.021 = phi i64 [ 0, %start ], [ %3, %bb8 ]
  %iter.sroa.0.020 = phi i64 [ 0, %start ], [ %1, %bb8 ]
  %1 = add nuw nsw i64 %iter.sroa.0.020, 1
  %rng.val.val = load i64*, i64** %0, align 8
; call <playground::NoInlineRng<R> as rand_core::RngCore>::next_u64
  %2 = tail call fastcc i64 @"_ZN71_$LT$playground..NoInlineRng$LT$R$GT$$u20$as$u20$rand_core..RngCore$GT$8next_u6417h0b95e10cc642939aE"(i64* %rng.val.val)
  %3 = add i64 %2, %num.021
  %exitcond = icmp eq i64 %1, 10000
  br i1 %exitcond, label %bb6, label %bb8
}

; playground::add_sum
; Function Attrs: noinline uwtable
define internal fastcc i64 @_ZN10playground7add_sum17h0910bf39c2bf0430E(i64** dereferenceable(8)) unnamed_addr #4 personality i32 (i32, i32, i64, %"unwind::libunwind::_Unwind_Exception"*, %"unwind::libunwind::_Unwind_Context"*)* @rust_eh_personality {
bb2.i.i.i.i:
  br label %bb2.i.i.i.i.i

bb2.i.i.i.i.i:                                    ; preds = %bb2.i.i.i.i.i, %bb2.i.i.i.i
  %1 = phi i64 [ 10000, %bb2.i.i.i.i ], [ %3, %bb2.i.i.i.i.i ]
  %accum.0.i.i.i.i.i = phi i64 [ 0, %bb2.i.i.i.i ], [ %4, %bb2.i.i.i.i.i ]
  %.val.val.i.i.i.i.i.i = load i64*, i64** %0, align 8, !noalias !33
; call <playground::NoInlineRng<R> as rand_core::RngCore>::next_u64
  %2 = tail call fastcc i64 @"_ZN71_$LT$playground..NoInlineRng$LT$R$GT$$u20$as$u20$rand_core..RngCore$GT$8next_u6417h0b95e10cc642939aE"(i64* %.val.val.i.i.i.i.i.i), !noalias !33
  %3 = add nsw i64 %1, -1
  %4 = add i64 %2, %accum.0.i.i.i.i.i
  %5 = icmp eq i64 %3, 0
  br i1 %5, label %_ZN4core4iter8iterator8Iterator3sum17hcbc4a00f32ac1feeE.exit, label %bb2.i.i.i.i.i

_ZN4core4iter8iterator8Iterator3sum17hcbc4a00f32ac1feeE.exit: ; preds = %bb2.i.i.i.i.i
  ret i64 %4
}

您可以看到，add_manual和add_range基本相同，除了add的位置不同。 add_sum也类似，但它是从10000开始倒数计数，而不是顺序计数。对于add_fold没有定义，因为编译器确定它与add_sum的代码完全相同并将它们合并。

在这种情况下，优化器确实可以使它们基本相同。让我们使用内置的基准测试:

#[bench]
fn bench_add_manual(b: &mut Bencher) {
    b.iter(|| {
        let rng = rand::thread_rng();
        add_manual(rng)
    });
}

#[bench]
fn bench_add_range(b: &mut Bencher) {
    b.iter(|| {
        let rng = rand::thread_rng();
        add_range(rng)
    });
}

#[bench]
fn bench_add_sum(b: &mut Bencher) {
    b.iter(|| {
        let rng = rand::thread_rng();
        add_sum(rng)
    });
}

结果如下：

test bench_add_manual ... bench:      28,058 ns/iter (+/- 3,552)
test bench_add_range  ... bench:      28,349 ns/iter (+/- 6,663)
test bench_add_sum    ... bench:      29,807 ns/iter (+/- 2,016)

对我来说，这似乎基本相同。我会说，在这种情况下，在目前的时间点上，性能没有明显差异。然而，并不是每个函数式样的代码都适用。

3

通常，fold（reduce）可以编译成等效的高效手动编译代码，因此节省程序员的时间。值得注意的是，在折叠中的递归处于尾部位置，因此它只是一种更简单的编写循环的方式。

这并不适用于您以函数式风格编写的所有程序。

我的回答很简短，但希望以后能编辑并丰富它的例子。 - dcorking
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接