?

Log in

No account? Create an account
 

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

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

Previous Entry Весёлые приключения одной аллокации 12 апр, 2015 @ 22:10 Next Entry
В рамках производной второго порядка от флешмоба, изначально стартовавшего тут, получившего продолжение тут, и форкнувшегося здесь, мной был написан небольшой код на расте: репо.

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

Я уже говорил, что вижу в 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++. Ну, по крайней мере, я в это верю :)
Оставить комментарий
[User Picture Icon]
From:thedeemon
Date:Апрель, 12, 2015 20:21 (UTC)
(Link)
Отлично расписано! :)

> Мало того, у нас в наличии ситуация, когда строка аллоцируется в одном потоке, а освобождается в другом (в Си это считается страшным грехом).

И ведь не зря считается, хоть в Си может и по другой причине. При таком подходе в каждом потоке аллокатор должен быть очень thread-safe, позволять параллельную аллокацию и деаллокацию (или лочить мутексы на каждый чих). Это все хорошей скорости не очень способствует.

А в языке с GC Зинаида была бы создана быстрым bump-the-pointer способом (например) и прожила бы счастливо до конца работы данной программы. Передавался бы так же один указатель (возможно толстый, шоб длину не пересчитывать), расходов на деаллокацию могло бы быть на одну Зинаиду меньше.
[User Picture Icon]
From:swizard
Date:Апрель, 12, 2015 20:57 (UTC)
(Link)
Ну, скажем, в си/с++ я редко вижу, чтобы использовалось что-то кроме штатного аллокатора, который использует libc-шный, который, в свою очередь, тред-сейфный. Сам rust использует jemalloc.

К тому же, используя параллельную аллокацию, нам, как правило, придётся копировать данные, чтобы передавать их между потоками :)

Что касается gc и бессмертной Зинаиды -- она же у нас не одна такая, их там может полчища породиться в цикле с read_line (он потенциально бесконечный). Периодически нужно будет грохнуть всю эту армию, что повлечёт за собой лаг на сборку мусора. Ну, как бы, все за и против гц хорошо известны. Как и плюсы и минусы ручного управления памятью.

В том или ином случае, Rust, в отличие от всех остальных языков, запрещает тебе пользоваться Зинаидой, если ты её кому-то отдал насовсем, например, в другой поток. И что-то сделать (например, распечатать на экран) можно будет только после того, как (если) тебе её вернули обратно -- это автоматически гарантирует, что data races исключены (причём, без всякой явной синхронизации).

И при таких мощных гарантиях под капотом там оказывается просто тупое присваивание указателей, без всяких memcpy, с количеством аллокаций/деаллокаций не чаще (почти всегда реже), чем в с++.
[User Picture Icon]
From:Lazin
Date:Апрель, 15, 2015 09:28 (UTC)
(Link)
Реализация malloc в libc сейчас основывается на ptmalloc, который мало в чем уступает jemalloc. Оба эти аллокатора используют tread local кэши объектов и per-thread арены. Если объект создается в одном потоке и разрушается в том же потоке (допустим мы используем jemalloc) - то никакой синхронизации не потребуется. Если объект создается в одном потоке и разрушается в другом, то вызов free залочит арену того потока, который создавал объект.
[User Picture Icon]
From:swizard
Date:Апрель, 15, 2015 10:47 (UTC)
(Link)
> Реализация malloc в libc сейчас основывается на ptmalloc, который мало в чем уступает jemalloc

"Сейчас" -- это когда? :) Полтора года назад glibc-шный аллокатор сильно хуже был: https://github.com/rust-lang/rust/issues/6897#issuecomment-18807015

> Если объект создается в одном потоке и разрушается в другом, то вызов free залочит арену того потока, который создавал объект.

Понятно, спасибо, буду иметь в виду.
[User Picture Icon]
From:Lazin
Date:Апрель, 15, 2015 12:01 (UTC)
(Link)
Сейчас это сейчас (а когда еще может быть сейчас?). Я не утверждал что стоковый аллокатор лучше или на одном уровне с jemalloc, он лишь мало в чем уступает. Для большинства приложений эта разница значения не имеет, но важно то, что стоковый аллокатор а) многопоточный (как jemalloc) б) реализует simple segregated storage для оптимизации распределения памяти под маленькие объекты (как jemalloc). Вообще, jemalloc обычно выбирают не за результаты в синтетических тестах, а за другие возможности - диагностика, возможность более точного управления аренами и тд.
[User Picture Icon]
From:dmitry_vk
Date:Апрель, 13, 2015 11:30 (UTC)
(Link)
Ну и не надо забывать, что GC тянет за собой рантайм, что сразу создает проблемы при уживании в одном процессе/адресном пространстве с другими рантаймами.
[User Picture Icon]
From:_winnie
Date:Апрель, 12, 2015 20:22 (UTC)
(Link)
Возможно, я не до конца понял написаное, но умный указатель std::unique_ptr (std::auto_ptr в предыщих версиях C++) в C++ вроде обладает похожими свойствами - там нет никаких счетчиков, его можно перемещать между всякими потоками и возвращать из функций, перемещение - это копирование одного указателя (в регистры процессора, не трогая память).

Отличие - в том, что borowing не контролируется (а именно, передача обычного сишного указателя из этого умного в другую функцию), но функции в C++ обычно не сохраняют себе переданный указатель.

Второе отличие, что если используем не std::uniq_ptr, а std::string (который сам себе unique_ptr в том смысле, что есть move-конструктор), то очень легко случайно вместо перемещения использовать копирование. Тем не менее, чаще всего по умолчанию строчка текста скорее всего тоже будет протащена без всяких memcpy и alloc, и без reference counting.

Edited at 2015-04-12 20:24 (UTC)
[User Picture Icon]
From:swizard
Date:Апрель, 12, 2015 21:05 (UTC)
(Link)
Да, всё правильно :) Наверно, если совсем грубо, то Rust + ownership -- это с++, где вообще всё (включая параметры функций и поля структур) объявляется через uniq_ptr, и нет никакого другого способа объявить переменную заданного типа. И передавать их можно только по значению.

Но там есть второй важный момент: в с++ ты можешь вызвать функцию, передав параметром uniq_ptr, и потом совершенно свободно продолжить им пользоваться. Поэтому в многопоточной среде нужно обязательно наворачивать синхронизацию. В Rust, после того, как ты отдал ownership, язык тебе просто запретит пользоваться переменной, что даёт тебе мощные гарантии даже в многопоточной среде, при этом сохраняя максимальную производительность.

Я же не случайно упомянул в тексте про масштабные проекты. В микробенчмарках, само собой, практически всегда можно догнать и обогнать Rust любым языком :)
From:Yauheni Akhotnikau
Date:Апрель, 13, 2015 12:00 (UTC)
(Link)
> в с++ ты можешь вызвать функцию, передав параметром uniq_ptr, и потом совершенно свободно продолжить им пользоваться.

Не совсем так. У unique_ptr нет оператора копирования. Поэтому вот такая конструкция просто так не скомпилируется:

auto dyn_obj = make_unique< T >(...);
call_something( dyn_obj );
call_something_else( dyn_obj );

Нужно явно определять передачу владения содержимым unique_ptr:

call_something( move( dyn_obj ) );

Конечно, после этого dyn_obj все равно останется в области видимости. Но это уже не так страшно, как в свое время с auto_ptr.
[User Picture Icon]
From:thedeemon
Date:Апрель, 13, 2015 06:02 (UTC)
(Link)
std::unique_ptr это двойное издевательство. Во-первых, потому что компилятор не проверяет, что мы что-то отдали и больше не владеем, разрешает дальше обращаться. Тут Rust это огромнейший шаг вперед. Во-вторых, потому что много писанины и читанины, std::unique_ptr<X> вместо простого X*. И вообще все с ног на голову перевернуто, выглядит будто X это свойство unique_ptr, а не уникальность это свойство указателя.
[User Picture Icon]
From:antilamer
Date:Апрель, 13, 2015 05:27 (UTC)
(Link)
Меня тоже здорово привлекла эта фича. Вообще, кажется, замечательный язык, C++ done right - и ownership/lifetime management правильный, и алгебраические типы есть, и эксепшнов нету, и макросы есть на всякий случай, и traits да еще с associated types, и лямбды. Читать туториал - прямо бальзам на душу. Думаю попробовать поиграться с ним на ICFPC. Жаль только, говорят, скорость компиляции паршивая пока.
[User Picture Icon]
From:thedeemon
Date:Апрель, 13, 2015 05:55 (UTC)
(Link)
По ощущениям, не медленнее хаскеля компилируется.
[User Picture Icon]
From:maxim
Date:Апрель, 13, 2015 09:53 (UTC)
(Link)
Говорят, что скорость компиляции не имеет значения и приводят в пример Scala и Haskell.

Edited at 2015-04-13 09:53 (UTC)
[User Picture Icon]
From:afiskon
Date:Апрель, 13, 2015 10:19 (UTC)
(Link)
На самом деле конечно же имеет. И очень большое. Мы тут в мире Scala сильно страдаем из-за медленной компиляции. И fat jar'ов на 100-150 Мб.
[User Picture Icon]
From:swizard
Date:Апрель, 15, 2015 10:53 (UTC)
(Link)
> Думаю попробовать поиграться с ним на ICFPC.

Только я рекомендовал бы до контеста чуток потренироваться, чтобы осознать его идеоматические подходы к стандартным задачам. Там сильно неочевидно поначалу с какой стороны заходить, потому что и сишный подход в лоб не работает (borrow checker постоянно мешается), и фп-подход тоже (без gc лямбдами (и вообще композицией функций) очень непривычно пользоваться, и далеко не всегда удобно). Там некий свой стиль должен выработаться.
[User Picture Icon]
From:afiskon
Date:Апрель, 13, 2015 10:20 (UTC)
(Link)
Спасибо, очень интересный пост. Пишите больше про Rust!
[User Picture Icon]
From:dmitry_vk
Date:Апрель, 13, 2015 11:20 (UTC)
(Link)
Мои впечатления от rust примерно совпадают - очень уж удачная комбинация получается.
Помимо языка, у rust уже есть замечательное коммьюнити и всякого рода инструменты и обвязки (например, чего только стоит rust-bindgen).
From:(Anonymous)
Date:Апрель, 29, 2015 15:37 (UTC)
(Link)
С гринтредами в Rust пока все плохо и не ясно когда будет лучше.

Пробовал полгода назад сравнивать Rust green (уже вынесенный тогда из стандартного рантайма) и goroutines - go порвал rust раза в четыре по времени.

Пока в rust гринтреды не сделают на уровне рантайма, он малопригоден для серверных приложений и модных веб-фреймворков.
[User Picture Icon]
From:si14
Date:Май, 1, 2015 09:09 (UTC)
(Link)
Я обожаю такие утверждения. Каждый раз, когда читаю, вспоминаю, что автор утверждения, скорее всего, пишет вебмагазины на 2.5 инвалида в сутки, и смеюсь про себя. Но да, если так посмотреть, в интернетах каждый первый ЛОРД ХАЙЛОАДА.
From:(Anonymous)
Date:Май, 2, 2015 12:19 (UTC)
(Link)
ad hominem - ок. а что насчет гринтредов в расте?
[User Picture Icon]
From:si14
Date:Май, 2, 2015 12:24 (UTC)
(Link)
Это не адхоминем, это (немного агрессивная, признаю) насмешка над фетишизацией некого абстрактного «перформанса» и «совершенно необходимых для вебсерверов» зелёных тредов. Напомню, что до сих пор гигантское количество людей пользуется threaded апачем и вполне довольны жизнью.

Поэтому даже не важно, «чо там в расте». Важно не поддаваться хайпу и не делать странных утверждений.
From:(Anonymous)
Date:Май, 2, 2015 23:26 (UTC)
(Link)
У нас свобода мнений. Не надо объявлять точку зрения отличную от вашей ересью. Нравится вам писать на пыхах и руби - пишите на здоровье.
(Оставить комментарий)
Top of Page Разработано LiveJournal.com