swizard (swizard) wrote,
swizard
swizard

Category:

Весёлые приключения одной аллокации

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

Про сам перформанс мб в другой раз, а пока я бы поделился некоторыми наблюдениями насчёт собственно языка.

Я уже говорил, что вижу в Rust достаточно большой потенциал. И тут даже дело не в том, что за ним стоит мозилла, и что он динамично развивается, и что там дружелюбное (до приторности) коммьюнити, и что разработчики (пользуясь бета-статусом релиза) смело тащат в язык разные модные конструкции из других языков и всячески экспериментируют с ними. Этого добра (в той или иной степени) полно и в других подобных хипстерских языках из т.н. "практической ниши", типа Go, Scala, D, какой-нибудь Nim и тд. Но, в отличие от них, мне кажется, что Rust выстрелит.

Rust, в принципе, построен вокруг одной удивительно простой, но при этом, как оказалось, неожиданно удачной идеи безопасной организации управления памятью, при этом без использования сборки мусора. Основной посыл там можно кратко сформулировать в двух пунктах:

  • Ownership -- это, грубо говоря, RAII на стероидах.
  • Borrowing + lifetimes -- это концепция "безопасных" указателей, при этом в транслированном коде это обычные сишные указатели, а вся безопасность исключительно в compile-time.

Идея с ownership-ом, при этом, оказалась настолько удачной, что спустя некоторое время начали всплывать различные приятные, но при этом халявные бонусы, вроде дружелюбной многопоточности, которая при этом не завязана на immutable-state, как в других языках (более подробно можно ознакомиться в Fearless Concurrency).

И, что ещё любопытно, благодаря ownership-у, масштабный проект на Rust, потенциально, должен иметь заметно более высокую производительность, нежели на C++ или Java (включая их производные). Дело в том, что сложные абстракции в этих языка (а таковыми все крупные приложения обязательно постепенно обрастают) требуют множество аллокаций/деаллокаций и копирования. Если язык при этом поощряет активное использование неизменяемого состояния, то копирований и аллокаций будет ещё больше (да, компиляторы, конечно, пытаются оптимизировать эти места по-максимуму, но, в среднем, тенденция сохраняется). За всё это нужно расплачиваться либо паузами GC, либо пониженной производительностью C++ приложения (при массированной нагрузке на аллокатор можно получить фрагментацию памяти).

В идиоматической программе на Rust физических аллокаций и копирований заметно меньше, за счёт того, что, благодаря ownership-y, жизненный цикл объектов получается достаточно длинным. Я попробую сейчас продемонстрировать это на примере одной аллокации из моей флешмобной реализации бенчмарка.

Итак, познакомимся с хорошо знакомым всем объектом "строка". Предположим, её зовут Зинаида, и впервые она рождается в функции read_line_loop в этом куске кода:

            let mut line = String::new();
            match try!(reader.read_line(&mut line)) {
                0 => return Ok(()),
                _ => manager.feed_workload(line),
            }

В отличие от языков со сборкой мусора, здесь у нас всё детерминировано: я могу точно сказать, что первый malloc будет вызван в String::new(), и затем, в методе read_line, скорее всего, будет выполнен realloc. Далее Зинаида, а равно как и всевозможные права на неё отдаются в метод Manager::feed_workload(), после чего в рассматриваемом куске кода мы про неё забываем. Это называется "ownership transferring". Всё, далее вызовов free здесь в радиусе функции нигде сгенерировано не будет, а Зинаида будет прибита где-то в feed_workload, вместе со своими аллокациями в куче.

Идём дальше, в метод Manager::feed_workload().

impl Manager {
    // ... some code
    fn feed_workload(&mut self, line: String) {
        // ... some code
        self.pool.slave_mut(ready_slave_idx).tx.send(Command::Workload(line)).unwrap();
        // ... some more code
    }

Зинаида (переменная "line") оборачивается в алгебраический тип Command::Workload, формируя тем самым новый объект. Физически, никаких дополнительных аллокаций и деаллокаций кучи здесь не происходит: выделяется небольшой объект на стеке, и присваиваются несколько переменных (указатели внутри объекта Vec, который является составной частью String). Зинаида всё ещё жива, хотя теперь она является частью другого объекта, вот такого типа:

enum Command {
    Workload(String),
    Terminate,
}

Далее, все права на Зинаиду (в составе объекта Workload) полностью передаются в метод send объекта типа mpsc::Sender<Command>. Деаллокаций всё ещё нет, содержимое строки, вычитанное из stdin лежит без изменений в регионе памяти, который всё ещё валиден и доступен по старому указателю.

Пропустив некоторое количество магии, которое происходит в кишках mpsc, мы переходим к следующему месту, где мы встречаемся с Зинаидой. Это функция slave_loop, результат Receiver::recv:
        match rx.recv() {
            Ok(Command::Workload(line)) => {
                match SlaveTask::parse(&line) {
                    Ok(task) => {
                        // some code skipped
                    },
                    Err(error) => {
                        tx.send(TaskResult::Error(line, error)).unwrap();
                        // some code skipped
                    },
                }
            },
            Ok(Command::Terminate) | Err(..) =>
                break,
        }

Тут уже ситуация любопытней. Сначала следует осознать, что вот это место, где мы щас находимся, на минутку, контекст другого треда. Ок, ладно. Итак, Зинаида возвращается нам нетронутой в составе объекта Workload, который деструктурируется в первой ветви паттерн-матчинга. Собственно, Зинаида в этом блоке теперь доступна под биндингом "line", тип которого String (не ссылка, а именно что ownership). Дальше происходит вот что:

  • Сначала, мы "одалживаем" Зинаиду методу SlaveTask::parse (это borrowing), то есть, по выходу из этой функции она всё ещё наша.
  • Если парсинг завершён успешно, Зинаида будет, наконец, уничтожена на выходе из блока ветви Ok. Здесь произойдёт долгожданный вызов free.
  • Если же мы попали в ветвь Err, то мучения Зинаиды на этом не заканчиваются. Она снова оборачивается в тип TaskResult::Error (это снова, напоминаю, zero copy), и права на неё передаются в send.

Допустим, так и произошло. Тогда возвращаемся в контекст первого треда и начинаем отматывать стек функций, где мы снова встречаемся с Зинаидой, в обратном порядке:

    fn recv_any(&mut self) -> (usize, TaskResult) {

Здесь мы получаем её в составе TaskResult::Error из recv и возвращаем во втором элементе тупла (это ownership transfer). Далее:

    fn poll(&mut self) -> TaskResult {

Ничего интересного, передаём власть над результатом выше по стеку.

fn read_line_loop(manager: &mut Manager) -> Result<(), io::Error> {
    // code skipped
    loop {
        // code skipped
        process_result(manager.poll());

Получаем из одного места и сразу отдаём в process_result. Зинаида всё ещё путешествует в составе TaskResult::Error.

fn process_result(result: TaskResult) {
    match result {
        // code skipped
        TaskResult::Error(input, error) => { 
            let _ = writeln!(&mut io::stderr(), "Input data: [ {} ], error: {:?}", input.trim_right_matches(|c: char| c.is_whitespace()), error); 
        },

Зинаида прилетает в параметре result, в ветви паттерн-матчинга он деструктурируется, и Зинаида оказывается в биндинге input. Это ownership, поэтому, после того, как мы даём временно попользоваться нашей Зинаидой функции печати, нам её необходимо прибить. Та-дам, это второе место в программе, где для нашего объекта вызывается free.

А теперь можно проскроллить экран наверх и посмотреть, сколько всего пережила Зинаида (а, соответственно, и аллоцированный регион памяти в куче), прежде чем оказаться напечатаной на экран в составе рапорта об ошибке. Имеет смысл обратить внимание, что объект дважды переходил границу потоков операционной системы. Мало того, у нас в наличии ситуация, когда строка аллоцируется в одном потоке, а освобождается в другом (в Си это считается страшным грехом). Вдобавок, у нас есть ситуация, когда один поток аллоцирует объект, которым пользуется другой поток, затем снова первый, и освобождает его. Учитывая то, что физически это тупо указатель на память (тоесть, вообще, самое низкоуровневое и производительное, что может быть), полагаю, очень редкие программисты Си/С++ смогут с первого раза написать эквивалентную программу, в которой не возникнет ситуаций "free after use" или "segmentation fault".

И да, при этом в нашей программе нет мусорщика, и все аллокации/деаллокации детерменированы.

Короче, в качестве итога. Концепция Ownership в Rust, на мой взгляд, настолько удачная (и, при этом, достаточно простая для понимания), что язык просто обязан забрать нишу C++. Ну, по крайней мере, я в это верю :)
Tags: allocator, code, flashmob, multithreading, ownership, programming language, rust
Subscribe

  • У нас есть Rust, поэтому C++ больше не нужен.

    Просто чудесный пост у thesz, наглядно демонстрирующий мой лозунг из сабжа. Давайте пройдёмся по пунктам: > Большое неудобство,…

  • а вот, например, ещё вакансии

    Собственно, образовалась ещё вакансия. Нам нужно несколько человек, задач много, они все (как это водится) инновационные и интересные, минимум…

  • Вернуть итератор

    А между тем, зацените, в nightly rust научились делать вот так: #![feature(conservative_impl_trait)] fn numbers() -> impl…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments

  • У нас есть Rust, поэтому C++ больше не нужен.

    Просто чудесный пост у thesz, наглядно демонстрирующий мой лозунг из сабжа. Давайте пройдёмся по пунктам: > Большое неудобство,…

  • а вот, например, ещё вакансии

    Собственно, образовалась ещё вакансия. Нам нужно несколько человек, задач много, они все (как это водится) инновационные и интересные, минимум…

  • Вернуть итератор

    А между тем, зацените, в nightly rust научились делать вот так: #![feature(conservative_impl_trait)] fn numbers() -> impl…