Question

Я слежу за треком Rust на Exercism.io .У меня достаточно опыта работы с 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
}

Я заметил, что один из ответов с самым высоким рейтингом выглядел больше так:

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()
}

Мне нравится решение с самым высоким рейтингом;это просто, функционально и элегантно.Это то, что они обещали мне, что Руст будет всем.Мой, с другой стороны, грубый и полон изменчивых переменных.Вы можете сказать, что я привык к C ++.

Моя проблема в том, что функциональный стиль оказывает ЗНАЧИТЕЛЬНОЕ влияние на производительность.Я протестировал обе версии с одинаковыми 4 МБ случайных данных, закодированных 1000 раз.Мое императивное решение заняло менее 10 секунд;функциональное решение составляло ~ 2 минуты 30 секунд.

Почему функциональный стиль намного медленнее императивного стиля?
Есть ли какая-то проблема с функциональной реализацией, которая вызывает такое огромное замедление?
Если я хочу написать высокопроизводительный код, должен ли я когда-либо использовать этот функциональный стиль?

Shepmaster · Answer 1 · 14 апреля 2019

TL; DR

Функциональная реализация может * в некоторых случаях быть быстрее вашей исходной процедурной реализации.

Почему функциональный стиль так важенмедленнее, чем императивный стиль?Есть ли какая-то проблема с функциональной реализацией, которая вызывает такое огромное замедление?

Как Мэтью М. уже указал , важно отметить, что алгоритм имеет значение.Как этот алгоритм выражается (процедурный, императивный, объектно-ориентированный, функциональный, декларативный), как правило, не имеет значения.

Я вижу две основные проблемы с функциональным кодом:

Выделение множества строк снова и снова неэффективно.В исходной функциональной реализации это делается с помощью 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()
}

Эталон 4МБ случайных буквенно-цифровых данных, скомпилированный с 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 за указание на то, что стремление получить первое значение помогает прогнозировать переходы.

Тест 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

Я полагаю, что это более четко показывает основную фундаментальную разницу между двумя реализациями:Решение на основе итераторов Resumable .Каждый раз, когда мы вызываем next, нам нужно посмотреть, был ли предыдущий символ, который мы прочитали (self.saved).Это добавляет ответвление к коду, которого нет в процедурном коде.

С другой стороны, решение на основе итераторов является более гибким - теперь мы можем составлять все виды преобразований в данных, илизапись непосредственно в файл вместо String и т. д. Пользовательский итератор может быть расширен для работы с универсальным типом вместо char, что делает его очень гибким.

См. Также:

Как добавить новые методы в Iterator?

Если я хочу написать высокопроизводительный код, следуетЯ когда-либо использовал этот функциональный стиль?

Я хотел бы, пока сравнительный анализ не покажет, что это узкое место.Затем оцените почему это узкое место.

Вспомогательный код

Всегда должен показывать свою работу, верно?

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);
    }
}

Matthieu M. · Answer 2 · 14 апреля 2019

Давайте рассмотрим функциональную реализацию!

Распределение памяти

Одной из больших проблем предлагаемого здесь функционального стиля является закрытие, переданное методу map, который выделяет aсерия .Каждый отдельный символ сначала сопоставляется с 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 точно так же, как ваше решение и не использует механизм format.

Я ожидал бы значительного выигрыша в производительности по сравнению с полнофункциональным решением, в то же время все еще используя group_by для дополнительной читаемости по сравнению с полным императивным решением.Иногда нужно смешивать и сочетать!

Какое влияние оказывает производительность на «функциональный» Rust?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Вспомогательный код

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Распределение памяти

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Какое влияние оказывает производительность на «функциональный» Rust?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Вспомогательный код

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Распределение памяти

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы