'functional' Rust 对性能有何影响?
What are the performance impacts of 'functional' Rust?
我正在关注 Exercism.io 上的 Rust 轨道。我有相当多的 C/C++ 经验。我喜欢 Rust 的 'functional' 元素,但我担心相对性能。
我解决了 '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(¤tcharcount.to_string());
}
retval.push(currentchar);
currentchar = c;
currentcharcount = 1;
}
}
if currentcharcount > 1 {
retval.push_str(¤tcharcount.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 秒。
- 为什么函数式风格比命令式风格慢这么多?
- 功能实现是否存在问题导致如此巨大的减速?
- 如果我想编写高性能代码,我是否应该曾经使用这种函数式风格?
让我们回顾一下功能实现!
内存分配
这里提出的函数式风格的一个大问题是传递给 map
方法的闭包,该方法分配 很多 。每个字符在被收集之前首先映射到 String
。
它还使用了 format
机器,众所周知这种机器速度相对较慢。
有时,人们为了获得 "pure" 实用的解决方案过于努力,相反:
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
时分配,就像您的解决方案一样,并且也不使用 format
机制。
与完整的功能解决方案相比,我预计会获得显着的性能提升,同时与完整的命令式解决方案相比,仍然利用 group_by
获得额外的可读性。有时候,你应该混搭!
TL;DR
在某些情况下,功能实现可以比原始程序实现更快。
Why is the functional style so much slower than the imperative style? Is there some problem with the functional implementation which is causing such a huge slowdown?
与一样,需要注意的重要一点是算法很重要。该算法的表达方式(过程的、命令的、面向对象的、功能的、声明的)通常无关紧要。
我发现功能代码有两个主要问题:
一遍又一遍地分配大量字符串是低效的。在最初的功能实现中,这是通过 to_string
和 format!
.
完成的
使用 group_by
有开销.
使用 itertools (batching
, take_while_ref
, format_with
) 的 more 使两个实现更加接近:
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()
}
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
如果您有兴趣创建自己的迭代器,可以将过程代码与更多功能代码混合搭配:
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 for pointing out 急切地获得第一个值有助于分支预测。
4MiB 随机字母数字数据的基准,使用 RUSTFLAGS='-C target-cpu=native'
:
编译
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
)。这会向程序代码中不存在的代码添加一个分支。
另一方面,基于迭代器的解决方案更加灵活——我们现在可以对数据进行各种转换,或者直接写入文件而不是 String
等。自定义迭代器也可以扩展为对通用类型而不是 char
进行操作,使其 非常 灵活。
另请参阅:
If I want to write high performance code, should I ever use this functional style?
我愿意,直到基准测试表明这是瓶颈。然后评估为什么是瓶颈
支持代码
总是要展示你的作品,对吧?
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(¤tcharcount.to_string());
}
retval.push(currentchar);
currentchar = c;
currentcharcount = 1;
}
}
if currentcharcount > 1 {
retval.push_str(¤tcharcount.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);
}
}
我正在关注 Exercism.io 上的 Rust 轨道。我有相当多的 C/C++ 经验。我喜欢 Rust 的 'functional' 元素,但我担心相对性能。
我解决了 '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(¤tcharcount.to_string());
}
retval.push(currentchar);
currentchar = c;
currentcharcount = 1;
}
}
if currentcharcount > 1 {
retval.push_str(¤tcharcount.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 秒。
- 为什么函数式风格比命令式风格慢这么多?
- 功能实现是否存在问题导致如此巨大的减速?
- 如果我想编写高性能代码,我是否应该曾经使用这种函数式风格?
让我们回顾一下功能实现!
内存分配
这里提出的函数式风格的一个大问题是传递给 map
方法的闭包,该方法分配 很多 。每个字符在被收集之前首先映射到 String
。
它还使用了 format
机器,众所周知这种机器速度相对较慢。
有时,人们为了获得 "pure" 实用的解决方案过于努力,相反:
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
时分配,就像您的解决方案一样,并且也不使用 format
机制。
与完整的功能解决方案相比,我预计会获得显着的性能提升,同时与完整的命令式解决方案相比,仍然利用 group_by
获得额外的可读性。有时候,你应该混搭!
TL;DR
在某些情况下,功能实现可以比原始程序实现更快。
Why is the functional style so much slower than the imperative style? Is there some problem with the functional implementation which is causing such a huge slowdown?
与
我发现功能代码有两个主要问题:
一遍又一遍地分配大量字符串是低效的。在最初的功能实现中,这是通过
to_string
和format!
. 完成的
使用
group_by
有开销.
使用 itertools (batching
, take_while_ref
, format_with
) 的 more 使两个实现更加接近:
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()
}
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
如果您有兴趣创建自己的迭代器,可以将过程代码与更多功能代码混合搭配:
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 for pointing out 急切地获得第一个值有助于分支预测。
4MiB 随机字母数字数据的基准,使用 RUSTFLAGS='-C target-cpu=native'
:
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
)。这会向程序代码中不存在的代码添加一个分支。
另一方面,基于迭代器的解决方案更加灵活——我们现在可以对数据进行各种转换,或者直接写入文件而不是 String
等。自定义迭代器也可以扩展为对通用类型而不是 char
进行操作,使其 非常 灵活。
另请参阅:
If I want to write high performance code, should I ever use this functional style?
我愿意,直到基准测试表明这是瓶颈。然后评估为什么是瓶颈
支持代码
总是要展示你的作品,对吧?
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(¤tcharcount.to_string());
}
retval.push(currentchar);
currentchar = c;
currentcharcount = 1;
}
}
if currentcharcount > 1 {
retval.push_str(¤tcharcount.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);
}
}