“函数式”Rust对性能有什么影响？

Question

我正在Exercism.io上学习Rust编程语言。我有相当多的C/C++经验。我喜欢Rust的“函数式”元素，但我对其相对性能有所担忧。

我解决了'run length encoding' problem问题：

pub fn encode(source: &str) -> String {
    let mut retval = String::new();
    let firstchar = source.chars().next();
    let mut currentchar = match firstchar {
        Some(x) => x,
        None => return retval,
    };
    let mut currentcharcount: u32 = 0;
    for c in source.chars() {
        if c == currentchar {
            currentcharcount += 1;
        } else {
            if currentcharcount > 1 {
                retval.push_str(&currentcharcount.to_string());
            }
            retval.push(currentchar);
            currentchar = c;
            currentcharcount = 1;
        }
    }
    if currentcharcount > 1 {
        retval.push_str(&currentcharcount.to_string());
    }
    retval.push(currentchar);
    retval
}

我注意到最受欢迎的答案更像这样：

extern crate itertools;

use itertools::Itertools;

pub fn encode(data: &str) -> String {
    data.chars()
        .group_by(|&c| c)
        .into_iter()
        .map(|(c, group)| match group.count() {
            1 => c.to_string(),
            n => format!("{}{}", n, c),
        })
        .collect()
}

我喜欢这个最高评价的解决方案；它简单、功能强大且优雅。这就是他们向我承诺的 Rust 的全部特点。然而我的代码却很粗糙，充满了可变变量。你可以看出我习惯于 C++。

我的问题是函数式编程风格对性能有巨大影响。我用相同的 4MB 随机数据进行了 1000 次编码测试两个版本。我的命令式解决方案只花费不到 10 秒钟；函数式解决方案需要 ~2 分 30 秒。

• 为什么函数式编程风格比命令式风格慢那么多？
• 函数式实现是否存在某些问题导致了如此巨大的减速？
• 如果我想写高性能代码，我是否应该 永远 使用这种函数式编程风格？

- David Copernicus Bowie

---

对我来说，差异看起来非常惊人；那是x15的因素！你已经检查了两个实现是否产生相同的结果吗？ - Matthieu M.

@MatthieuM。是的，或者至少两个函数都通过了exercism定义的所有单元测试。 - David Copernicus Bowie

我在思考是否有一种方法可以用flat_map步骤替换map步骤，并使用特殊目的的迭代器实现来获取字符和计数并输出所需的字节流。正向编码整数有点棘手，但是使用count_leading_zeroes可以给出数量级的提示（clz(i) * 77 / 256给出了log 10）。 - Matthieu M.

Answer 1

TL;DR

在某些情况下，函数式实现可以比原始的过程式实现更快。

为什么函数式风格比命令式风格慢得多？函数式实现有什么问题导致了如此巨大的减速？

正如Matthieu M.已经指出的那样，需要注意的重要事情是算法。如何表达该算法（过程式、命令式、面向对象、函数式、声明式）通常并不重要。

我认为函数式代码存在两个主要问题：

• 反复分配大量字符串是低效的。在原始的函数式实现中，这是通过to_string和format!完成的。

• 使用group_by的开销很大，它存在于嵌套的迭代器中，你不需要这个迭代器就能获得计数。

使用更多的itertools (batching, take_while_ref, format_with)可以使这两种实现更加接近:

pub fn encode_slim(data: &str) -> String {
    data.chars()
        .batching(|it| {
            it.next()
                .map(|v| (v, it.take_while_ref(|&v2| v2 == v).count() + 1))
        })
        .format_with("", |(c, count), f| match count {
            1 => f(&c),
            n => f(&format_args!("{}{}", n, c)),
        })
        .to_string()
}

使用RUSTFLAGS='-C target-cpu=native'编译的4MiB随机字母数字数据基准测试：

encode (procedural)     time:   [21.082 ms 21.620 ms 22.211 ms]

encode (fast)           time:   [26.457 ms 27.104 ms 27.882 ms]
Found 7 outliers among 100 measurements (7.00%)
  4 (4.00%) high mild
  3 (3.00%) high severe

如果您有兴趣创建自己的迭代器，可以将过程式代码与更多的函数式代码混合使用：

struct RunLength<I> {
    iter: I,
    saved: Option<char>,
}

impl<I> RunLength<I>
where
    I: Iterator<Item = char>,
{
    fn new(mut iter: I) -> Self {
        let saved = iter.next(); // See footnote 1
        Self { iter, saved }
    }
}

impl<I> Iterator for RunLength<I>
where
    I: Iterator<Item = char>,
{
    type Item = (char, usize);

    fn next(&mut self) -> Option<Self::Item> {
        let c = self.saved.take().or_else(|| self.iter.next())?;

        let mut count = 1;
        while let Some(n) = self.iter.next() {
            if n == c {
                count += 1
            } else {
                self.saved = Some(n);
                break;
            }
        }

        Some((c, count))
    }
}

pub fn encode_tiny(data: &str) -> String {
    use std::fmt::Write;

    RunLength::new(data.chars()).fold(String::new(), |mut s, (c, count)| {
        match count {
            1 => s.push(c),
            n => write!(&mut s, "{}{}", n, c).unwrap(),
        }
        s
    })
}

1 — 感谢Stargateur提出，急切地获取第一个值有助于分支预测。

使用RUSTFLAGS='-C target-cpu=native'编译的4MiB随机字母数字数据基准测试：

encode (procedural)     time:   [19.888 ms 20.301 ms 20.794 ms]
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe

encode (tiny)           time:   [19.150 ms 19.262 ms 19.399 ms]
Found 11 outliers among 100 measurements (11.00%)
  5 (5.00%) high mild
  6 (6.00%) high severe

我认为这更清楚地显示了两种实现之间的主要基本区别：基于迭代器的解决方案是可恢复的。每次调用next，我们需要查看是否有先前读取的字符（self.saved）。这在过程式代码中不存在，因此它会向代码添加一个分支。

另一方面，基于迭代器的解决方案更加灵活 - 我们现在可以对数据进行各种转换，或者直接写入文件而不是字符串等。自定义迭代器也可以扩展为对通用类型而不是char进行操作，使其非常灵活。

另请参见：

- 如何向迭代器添加新方法？ 如果我想编写高性能代码，我应该使用这种函数式风格吗？

我会使用，直到基准测试表明它是瓶颈。然后评估为什么它是瓶颈。

支持代码

总是要展示你的工作，对吧？

benchmark.rs

use criterion::{criterion_group, criterion_main, Criterion}; // 0.2.11
use rle::*;

fn criterion_benchmark(c: &mut Criterion) {
    let data = rand_data(4 * 1024 * 1024);

    c.bench_function("encode (procedural)", {
        let data = data.clone();
        move |b| b.iter(|| encode_proc(&data))
    });

    c.bench_function("encode (functional)", {
        let data = data.clone();
        move |b| b.iter(|| encode_iter(&data))
    });

    c.bench_function("encode (fast)", {
        let data = data.clone();
        move |b| b.iter(|| encode_slim(&data))
    });

    c.bench_function("encode (tiny)", {
        let data = data.clone();
        move |b| b.iter(|| encode_tiny(&data))
    });
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

lib.rs

use itertools::Itertools; // 0.8.0
use rand; // 0.6.5

pub fn rand_data(len: usize) -> String {
    use rand::distributions::{Alphanumeric, Distribution};
    let mut rng = rand::thread_rng();
    Alphanumeric.sample_iter(&mut rng).take(len).collect()
}

pub fn encode_proc(source: &str) -> String {
    let mut retval = String::new();
    let firstchar = source.chars().next();
    let mut currentchar = match firstchar {
        Some(x) => x,
        None => return retval,
    };
    let mut currentcharcount: u32 = 0;
    for c in source.chars() {
        if c == currentchar {
            currentcharcount += 1;
        } else {
            if currentcharcount > 1 {
                retval.push_str(&currentcharcount.to_string());
            }
            retval.push(currentchar);
            currentchar = c;
            currentcharcount = 1;
        }
    }
    if currentcharcount > 1 {
        retval.push_str(&currentcharcount.to_string());
    }
    retval.push(currentchar);
    retval
}

pub fn encode_iter(data: &str) -> String {
    data.chars()
        .group_by(|&c| c)
        .into_iter()
        .map(|(c, group)| match group.count() {
            1 => c.to_string(),
            n => format!("{}{}", n, c),
        })
        .collect()
}

pub fn encode_slim(data: &str) -> String {
    data.chars()
        .batching(|it| {
            it.next()
                .map(|v| (v, it.take_while_ref(|&v2| v2 == v).count() + 1))
        })
        .format_with("", |(c, count), f| match count {
            1 => f(&c),
            n => f(&format_args!("{}{}", n, c)),
        })
        .to_string()
}

struct RunLength<I> {
    iter: I,
    saved: Option<char>,
}

impl<I> RunLength<I>
where
    I: Iterator<Item = char>,
{
    fn new(mut iter: I) -> Self {
        let saved = iter.next();
        Self { iter, saved }
    }
}

impl<I> Iterator for RunLength<I>
where
    I: Iterator<Item = char>,
{
    type Item = (char, usize);

    fn next(&mut self) -> Option<Self::Item> {
        let c = self.saved.take().or_else(|| self.iter.next())?;

        let mut count = 1;
        while let Some(n) = self.iter.next() {
            if n == c {
                count += 1
            } else {
                self.saved = Some(n);
                break;
            }
        }

        Some((c, count))
    }
}

pub fn encode_tiny(data: &str) -> String {
    use std::fmt::Write;

    RunLength::new(data.chars()).fold(String::new(), |mut s, (c, count)| {
        match count {
            1 => s.push(c),
            n => write!(&mut s, "{}{}", n, c).unwrap(),
        }
        s
    })
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn all_the_same() {
        let data = rand_data(1024);

        let a = encode_proc(&data);
        let b = encode_iter(&data);
        let c = encode_slim(&data);
        let d = encode_tiny(&data);

        assert_eq!(a, b);
        assert_eq!(a, c);
        assert_eq!(a, d);
    }
}

- Shepmaster

---

很棒的迭代器！ - Matthieu M.

顺便提一下，当恢复迭代器时引入分支，可以直接实现try_fold而不是依赖于默认实现（调用next）。当优化器无法优化掉分支时，这很有帮助。 - Matthieu M.

Answer 2

让我们回顾一下函数实现方法！

内存分配

这里提出的函数式风格的一个重要问题是传递给 map 方法的闭包会分配很多内存。每个字符在被收集之前都会首先映射到一个 String。

它还使用了相对较慢的 format 机制。

有时候，人们过分努力地想要得到一个“纯粹”的函数式解决方案，但其实：

let mut result = String::new();
for (c, group) in &source.chars().group_by(|&c| c) {
    let count = group.count();
    if count > 1 {
        result.push_str(&count.to_string());
    }

    result.push(c);
}

和你的解决方案一样，count > 1时才分配内存，但输出的信息比较冗长。

我预计与完整功能解决方案相比，将会获得显著的性能优势，同时仍然利用group_by可读性比完整的命令式解决方案更好。有时候，你需要混搭使用！

- Matthieu M.

---

这确实给我们带来了速度提升，但它仍然比命令式版本慢大约3倍（在我的测试中是30秒而不是10秒）。事实上，即使我只在那个for循环中推送一个常量字母，它仍然需要大约14秒，因此比命令式版本慢约50%。这让我相信，在这种情况下，group_by可能不是零成本的。无论如何，答案已被接受！ - David Copernicus Bowie

我如何将格式化的字符串附加到现有字符串？ - Shepmaster