那些遇到过的问题

“功能性” Rust对性能有何影响？

Dav*_*wie 41 functional-programming imperative-programming rust

我遵循Exercism.io上的Rust轨道。我有大量的C / C ++经验。我喜欢Rust的“功能性”元素，但我担心相对性能。

我解决了“游程编码”问题：

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
}
Run Code Online (Sandbox Code Playgroud)

我注意到最受好评的答案之一看起来像这样： 

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()
}
Run Code Online (Sandbox Code Playgroud)

我喜欢最受好评的解决方案；它简单，实用且优雅。这就是他们向我保证Rust将会实现的一切。另一方面，我的是总的，充满了可变的变量。您可以说我已经习惯了C ++。

我的问题是功能样式会对性能产生重大影响。我使用相同的4MB随机数据进行了1000次编码，测试了这两个版本。我的命令性解决方案花了不到10秒的时间；功能解决方案约为2分钟30秒。

  • 为什么功能样式比命令式样式慢得多？
  • 功能实现是否存在一些问题，从而导致如此巨大的速度下降？
  • 如果我想编写高性能的代码，我应该永远使用这个功能的风格？

She*_*ter 46

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()
}
Run Code Online (Sandbox Code Playgroud)

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

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()
}
Run Code Online (Sandbox Code Playgroud)

如果您对创建自己的迭代器感兴趣，可以将过程代码与更多功能代码混合搭配：

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
    })
}
Run Code Online (Sandbox Code Playgroud)

1-感谢Stargateur指出，急于获得第一个值有助于分支预测。

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

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
Run Code Online (Sandbox Code Playgroud)

我相信，这更清楚地表明了这两种实现之间的主要根本区别：基于迭代器的解决方案是可恢复的。每次调用时next，我们都需要查看是否已读取（self.saved）之前的字符。这将向过程代码中不存在的代码添加一个分支。

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

也可以看看：

如果我想编写高性能代码，是否应该使用这种功能样式？

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

配套代码

总是要展示你的作品，对不对？

基准

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);
Run Code Online (Sandbox Code Playgroud)

库

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);
    }
}
Run Code Online (Sandbox Code Playgroud)

  • 很棒的迭代器！ (2认同)

Mat*_* M. 19

让我们回顾一下功能实现！

内存分配

这里提出的功能风格的主要问题之一是传递给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);
}
Run Code Online (Sandbox Code Playgroud)

大约是冗长的，但是仅在count > 1您的解决方案使用和不使用format机制时才分配。

与完整功能的解决方案相比，我希望性能会大获成功，与此同时，group_by与完整的命令性解决方案相比，我仍然会利用更多的可读性。有时，您应该混搭！

归档时间：

查看次数：

1668 次

最近记录：

6 年，6 月 前
如何将格式化字符串附加到现有String？ 22
如何向Iterator添加新方法？ 20
更多相关链接
相关归档
指定仅二进制依赖项 25
用cont无法完成的callCC我该怎么办？ 8
ocaml中模式匹配的问题 5
haskell中的代码内省是什么？ 5
rustc/cargo 未被识别为内部或外部命令 5
从闭包调用异步函数 4
使用“let”进行赋值是否不违背 Clojure 中函数式编程的思想 4
约束:两个类型变量可以与运算符一起使用 2
有效地提取前缀子串 2
Diesel：BoxableExpressions 在表及其连接上通用吗？ 2
难疑归档
在git中推送提交时,src refspec master与any不匹配 2472
是否有标准函数来检查JavaScript中的null,undefined或blank变量？ 2088
如何使用java.net.URLConnection来触发和处理HTTP请求 1903
打印Java数组最简单的方法是什么？ 1852
我在哪里将'assets'文件夹放在Android Studio中？ 1366
如何用"喜欢"查询MongoDB？ 1331
如何在正则表达式中使用变量？ 1250
window.onload vs $(document).ready() 1205
Git:如何在项目提交历史中找到已删除的文件？ 1183
功能编程是否取代了GoF设计模式？ 1028