Rust — это не «memory safe C»

в 18:23, , рубрики: Rust, параллельное программирование, рефакторинг, скорость разработки, тестирование

TL;DR:
— в Rust намного больше достоинств, чем просто скорость и безопасность;
— в Rust по умолчанию CDD (compiler-driven development, разработка через компилирование). Это как TDD, только CDD;
— Rust — не сложный язык, особенно если не гнаться за максимальной производительностью.

На Rust можно смотреть с разных углов. Например, можно на него смотреть как на безопасную замену для C или C++. Многие говорят, что ниша Rust — это "mission critical" программы, а все, кто использует его для других целей — безумцы (цитата из одного из многочисленных Rust vs. Golang тредов). При этом среди людей, которые используют Rust, распространено мнение, что memory safety в Rust — это не главное его достоинство (например, тут, тут, тут или тут).

В этой статье я бы хотел рассказать:
— почему взгляд на Rust как на "memory safe C" очень сильно сужает область его возможного применения;
— почему я смотрю на Rust как на очень удобный в разработке язык высокого уровня, которому просто случайно повезло оказаться невероятно быстрым;
— почему разработка на Rust быстрее, чем многие думают;
— почему Rust — это один из лучших языков общего назначения.

Это только мое мнение, я не профессиональный Rust разработчик, если вы с чем-то не согласны, то пишите комментарии, обсудим.

Upd: не успел я эту статью выложить, как оказалось, что 27 марта 2024 года на конференции Rust Nation UK 2024 было выступление с интригующим названием Beyond Safety and Speed: How Rust Fuels Team Productivity от Lars Bergstrom, Google Android Director of Engineering. В этом выступлении есть примерно половина тем из этой статьи и чтобы в каждом пункте не писать «И в выступлении Ларс говорит то же самое!», я упомяну это выступление один раз, когда буду говорить о скорости разработки (т.к. это основная тема этого выступления и этой статьи). Рекомендую посмотреть его полностью, видео всего 30 минут, ссылка с таймкодом. Видимо, это не только мое мнение.

Часть 1. Вступление

Еще со школы меня интересовал C, было интересно разобраться, как же оно там под капотом работает. У меня до сих пор где-то лежит книга «Язык программирования С», но я её так и не дочитал до конца, не говоря уже о том, чтобы «выучить» C. Как ни странно, но «виноваты» в этом холивары на хабре. Ведь из них я узнал, что C — это жонглирование работающими бензопилами на минном поле или что-то подобное.

Даже после того, как я уже работал программистом и был уверен в своих силах, я опасался C, боялся того, что если когда-нибудь напишу что-то сложнее hello world то там через строчку будет UB, use after free, segfault, buffer overflow и т.д. и т.п. C и сам по себе очень помогает такому ощущению. Как люди без страха пишут на языке, где функцией вывода в stdout из стандартной библиотеки надо пользоваться осторожно, т.к. с помощью неё можно читать и изменять произвольную память. Для меня сейчас у C/C++ есть только 1 ниша: легаси С/С++ код, который слишком долго и дорого переписывать на Rust, и меня такая ниша не привлекает.

С первых прочитанных статей Rust меня заинтересовал. Он как C, только при этом безопасный! Что же может быть лучше возможности покопаться в железе напрямую без UB? Как оказалось потом, бывает еще лучше.

Часть 2. Rust. Начало

После Python писать на Rust было тяжело. Везде указатели, ничего не компилируется, наработанные годами подходы не работают. К счастью, меня это не остановило, я продолжал читать книжки, смотреть разнообразные ютуб-лекции и туториалы и прочие материалы. Лучший из них — курс лекций Алексея "matklad" Кладова (не уверен, что @matklad — это он, если это ты, отзовись) для Computer Science Center. В них вместо того, чтобы через 7 часов лекций объяснять, какой синтаксис у циклов, на первой лекции есть вот такое:

После такого понимаешь, что все будет серьезно
#![no_main] 
 
#[link_section=".text"] 
#[no_mangle] 
pub static main: [u32; 9] = [ 
    3237986353, 
    3355442993, 
    120950088, 
    822083584, 
    252621522, 
    1699267333, 
    745499756, 
    1919899424, 
    169960556, 
];

Или мой любимый слайд — «Модель Памяти C++ за Один Слайд» (слайд 35).

Этот курс меня сразу заинтересовал, с тех пор я пересмотрел его, наверное, раз пять и все еще нахожу новые вещи, на которые раньше не обращал внимания. В какой-то момент я узнал, что в качестве базы для домашних заданий используется статья Ray Tracing in One Weekend, и я тоже решил попробовать написать свой трассировщик лучей. Это уже не hello world и не переписывание примеров из книг, это достаточно большой проект, чтобы оценить, как язык ведет себя в реальной жизни. Это был первый момент, в который я понял, что Rust это не только «memory safe C».

Часть 3. Fearless concurrency

Из вышеупомянутых лекций я уже знал, что в safe Rust невозможны гонки данных и что писать многопоточный код в Rust намного проще. Но то были просто слова, их надо было проверить в деле. В конце "Ray Tracing in One Weekend" есть список возможных доработок, и одна из них — это параллелизм. Под конец упражнения мне хотелось отрендерить красивую 1080p картинку, но даже при 100 лучах на пиксель это занимало достаточно времени для того, чтобы меня это не устраивало. И звезды сошлись: 12-ти ядерный процессор, медленный однопоточный рендерер и Rust c бесстрашной конкурентностью.

Поначалу не особо получалось, мьютексы помогли коду скомпилироваться, но они блокировались так, что код оставался по сути однопоточным. Долго я бился в многопоточность, но ничего не получалось, пока я не вспомнил про библиотеку rayon, которая делает многопоточность проще. Я долго не мог разобраться, как же правильно и идиоматично её применять, и у меня получилось сделать только такое:

Заголовок спойлера

Полный код

...
use rayon::ThreadPoolBuilder;
use num_cpus;
...

fn main() {
    ...
    let samples_per_pixel = 100;
    let pool = ThreadPoolBuilder::new()
        .num_threads(num_cpus::get())
        .build()
        .unwrap();

    let mut img = RgbImage::new(image_width, image_height);

    ...

    let mut pixels = img.enumerate_pixels_mut().collect::<Vec<_>>();
    pool.scope(|scope| {
        …
        for chunk in pixels.chunks_mut(image_width as usize) {
            scope.spawn(move |_| {
                for (x, y, pixel) in chunk {
                    ...
                    for _ in 0..samples_per_pixel {
                        ...
                    }
                    **pixel = color.as_rgb(samples_per_pixel);
                }
                ...
            });
        }
    });

Просто пул потоков. Просто параллельная обработка пикселей. Ни одного мьютекса или какого-либо еще примитива синхронизации. И оно заработало. И заработало в 10 раз быстрее. Но суть даже не в этом; несмотря на то, что у меня было (да и сейчас) не много опыта в многопоточных приложениях, но я за пару часов смог прикрутить многопоточность без блокировок.

Тут можно сказать, что это тривиальная задача: у нас есть список задач, пул воркеров и пачка вариантов, как безопасно и быстро скармливать задачи воркерам. И я соглашусь, это действительно тривиальная задача, но в ней можно сделать достаточно большое количество ошибок. Вместо дебага гонок данных или дедлоков код просто не компилировался с подробными ошибками о том, почему я дурак, и иногда — как это исправить. Конечно, компилятор отловил не все ошибки: вначале я подумал, что в pixels.chunks_mut надо передать, сколько в конце должно быть чанков, и очень удивился, когда программа создала несколько десятков тысяч потоков. Но это было легко заметить и исправить.

Кстати, потом я все же разобрался, как правильно использовать rayon, и получилось еще более понятно (но не так интересно; насколько я помню, где-то внутри там есть мьютекс):

Заголовок спойлера
...
use rayon::prelude::*;
...

let mut img = RgbImage::new(image_width, image_height);

...

img.enumerate_rows_mut().par_bridge().into_par_iter().for_each(
    |(_, chunk)| {
        ...
        chunk.for_each(
        |(x, y, pixel)| {
            ...
            for _ in 0..samples_per_pixel {
                ...
            }
            *pixel = color.as_rgb(samples_per_pixel);
        });
        ...
    }
);

И это самый главный плюс Rust (имеется в виду safe Rust): в нем тяжело написать программу так, чтобы она компилировалась, работала неправильно, но как-то неочевидно. Если код скомпилировался и получается ожидаемый результат, то в подавляющем большинстве случаев код делает именно то, что от него хотят (и обычно не только в позитивном случае).

Ошибки, которые Rust не находит

Больше всего времени я потратил на баг, где написал - вместо +. Из результата вычислялся квадратный корень, который с этим багом иногда возвращал NaN. NaN в свою очередь заражал все, чего он коснется, и в конце концов на финальном рендере это были небольшие группы черных пикселей в неожиданных местах. К сожалению, о signaling NaN я узнал только после того, как нашел причину и поправил код.

Увы, не думаю, что когда-либо будет существовать такая система типов (или какой-то другой механизм), который мог бы предотвратить подобные ошибки. Логические ошибки останутся с нами до тех пор, пока будет программирование. Но все же возможность избавиться от огромного числа ошибок, оставив только логические, сама по себе стоит того.

Часть 4. Обработка ошибок

Кстати, о логических ошибках. В Rust лучшая система обработки ошибок.

Паники

Паники именно к обработке ошибок я не отношу, перехватывать их стоит в достаточно небольшом количестве случаев, и если расценивать их как «вместо паники тут была бы дыра в безопасности», то, мне кажется, с ними все в порядке.

Подход Rust не уникальный, монады сами по себе существуют давно, и языки, которые их используют, тоже. Их слабая распространенность иногда не дает мне заснуть в 3 утра. Я могу понять, почему в старых языках, например C, нет монад. Как бы я ни относился к C, все же ему больше 50 уже, не те времена были.

Лирическое отступление или почему Golang вызывает у меня только разочарование

Я недоумеваю, почему в относительно новых языках их нет? Я не могу без смеха (а иногда слез) читать эту цитату:

This is cleaner, even compared to the use of a closure, and also makes the actual sequence of writes being done easier to see on the page. There is no clutter anymore. Programming with error values (and interfaces) has made the code nicer. ... In fact, this pattern appears often in the standard library

Заголовок спойлера
type errWriter struct {
    w   io.Writer
    err error
}

func (ew *errWriter) write(buf []byte) {
    if ew.err != nil {
        return
    }
    _, ew.err = ew.w.Write(buf)
}

ew := &errWriter{w: fd}
ew.write(p0[a:b])
ew.write(p1[c:d])
ew.write(p2[e:f])
// and so on
if ew.err != nil {
    return ew.err
}

Тяжело не согласиться, все правда. Только проблема в том, что это монада. Буквально, это монада error, только хуже сразу в нескольких местах:

  1. она самописная, её надо для всего реализовывать самостоятельно;

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

  3. можно спокойно проигнорировать ошибку, и компилятор (подозреваю, и линтеры) по этому поводу даже не пискнут.

Может быть, раз уж "this pattern appears often in the standard library», стоило бы его в отдельную абстракцию вынести? Или это бы сделало Golang слишком "brilliant"? Последняя часть относится к известной цитате Роба Пайка:

The key point here is our programmers are Googlers, they’re not researchers. They’re typically, fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt

Сколько я ни видел эту цитату, я никак не могу понять часть про "they’re not researchers". Не нужно быть "researcher", чтобы пользоваться языком, но желательно, чтобы те, кто язык придумывал, были как раз ими, чтобы потом простым людям жилось лучше и не приходилось код копипастить.

Это было небольшое превью возможной статьи «Почему Golang вызывает у меня только разочарование», если вам вдруг интересно было бы почитать, то пишите в комментариях. С одной стороны, мне больно от мыслей об упущенных возможностях в языке, а с другой, — уже давно хочется поделиться со светом этой болью, а то чего я один страдаю.

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

Заголовок спойлера
let installed_apps: HashSet<String> = fs::read_dir(steam_library)?
    .map_ok(|entry| entry.path())
    .filter_ok(|path| path.is_file())
    .filter_map_ok(|path| {
        path
            .file_name()
            .and_then(|file_name| file_name.to_str())
            .and_then(|name| name.strip_prefix("appmanifest_"))
            .and_then(|name| name.strip_suffix(".acf"))
            .map(|app_id| app_id.to_string())
    })
    .collect::<Result<_, _>>()?;

Это часть простого скрипта, который удаляет ярлыки уже удаленных с компьютера игр из стим. Ни скорости, ни низкоуровневого доступа тут вот вообще не нужно, но я все равно написал его на Rust, т.к. хотел попрактиковаться в идиоматичной обработке ошибок. Мне кажется, получилось неплохо. Да, количество разных методов поражает воображение, часть из них еще и не из стандартной библиотеки, но при этом этот код учитывает:

  1. что fs::read_dir может вернуть ошибку;

  2. что объекты, которые возвращает итератор по результату fs::read_dir, могут быть ошибкой;

  3. что path.file_name() возвращает Option, т.к. path — совсем не обязательно путь именно к файлу;

  4. что file_name.to_str возвращает Option, т.к. путь к файлу не обязан быть UTF-8;

  5. что .strip_prefix возвращает Option, т.к. строка может не начинаться на prefix;

  6. что .strip_suffix возвращает Option, т.к. строка может не заканчиваться на suffix.

Скажу сразу: не всегда получается вот так хорошо, бывает и что-то более... кхм... в общем, сами смотрите:

Осторожно, 38+! Беременным детям не смотреть!
let mut buffer = String::new();

let _ = fs::read_dir(shortcuts)?
    .map_ok(|entry| entry.path())
    .filter_ok(|path| {
        path.extension()
            .and_then(|ext| ext.to_str())
            .and_then(|ext| ext.strip_suffix("url"))
            .is_none()
    })
    .map_ok(|p| -> anyhow::Result<Option<PathBuf>> {
        buffer.clear();
        let mut file = fs::File::open(&p)?;
        file.read_to_string(&mut buffer)?;
        let app_id = buffer
            .find(template)
            .and_then(|url_position| buffer.get((url_position + template.len())..))
            .map(|app_id_start| {
                app_id_start
                    .chars()
                    .take_while(char::is_ascii_digit)
                    .collect::<String>()
            });
        let Some(id) = app_id else {
            return anyhow::Result::Ok(None)
        };
        if installed_apps.contains(&id) {
            return anyhow::Result::Ok(None)
        };
        anyhow::Result::Ok(Some(p))
    })
    .flatten()
    .filter_map_ok(|path| path)
    .map_ok(|p| trash::delete(p))
    .flatten()
    .collect::<anyhow::Result<(), _>>()?;

Если честно, я сам с трудом понимаю, что тут вообще происходит (особенно без подстановки типов из IDE). Возможно есть вариант, как это сделать более читаемо, но, когда я писал этот код, он мне в голову не пришел. Не уверен, что этот код работает правильно (я проверил, что он компилируется). Я его даже не запускал т.к. сразу понятно, что это не то, что хочется. Переписать его в более императивном стиле получилось заметно лучше:

Заголовок спойлера
let mut buffer = String::new();

for entry in fs::read_dir(shortcuts)? {
    let path = entry?.path();
    if path
        .extension()
        .and_then(|ext| ext.to_str())
        .and_then(|ext| ext.strip_suffix("url"))
        .is_none()
    { continue }

    let mut file = fs::File::open(&path)?;
    buffer.clear();
    file.read_to_string(&mut buffer)?;

    let Some(app_id) = buffer
        .find(template)
        .and_then(|url_position| buffer.get((url_position + template.len())..))
        .map(|app_id_start| {
            app_id_start
                .chars()
                .take_while(char::is_ascii_digit)
                .collect::<String>()
        }) else { continue };

    if !installed_apps.contains(&app_id) {
        trash::delete(path)?;
    }
}

В этом случае код стало гораздо легче читать, но если присмотреться, то в изначальном варианте много проблем вызывало то, что я очень хотел написать оптимальный код и переиспользовать 1 буфер для чтения всех строк. Без этого все было бы гораздо проще. Это абсолютно не играло никакой роли для этого приложения, но хотелось сделать быстрее просто потому, что можно. Об этом явлении мы поговорим немного позже, а дальше у нас...

Часть 5. Скорость разработки

Это все, конечно, замечательно, но у нас 152 релиза в день, надо фичи пилить, нам некогда воевать с компилятором. Да, наш код регулярно ломается от NullPointerException (или его вариации в других языках), от неправильной обработки некритичных ошибок, от гонок данных, от куста проблем, которые связанных с памятью и т.д., но зато мы делаем это быстро! Пока вы там ошибки компилятора исправляете, мы уже на рынок выйдем и захватим его!

И вот теперь мы подошли к тому, что стало поводом для написания этой статьи. Подобные мысли у меня уже давно, и я регулярно рассуждаю на подобные темы с друзьями и коллегами, но вдохновение на эту статью мне дала одна недавняя череда событий, о которой чуть-чуть позже. Но для начала нам надо поговорить про Python.

Вообще я python бэкенд разработчик. Python как язык мне скорее нравится, чем не нравится, но у него точно есть очевидные проблемы, которые нет смысла отрицать (хотя понемногу их исправляют, что дает надежду на будущее). Не могу сказать, что делал какую-то ракетную хирургию, в основном обычные «получи json, сохрани json в базе, преобразуй json, переправь json дальше».

Мне приходилось дебажить все это очень много раз. Когда несмотря на 100% покрытие типами, в sentry появляется AttributeError: 'NoneType' object has no attribute '...', когда по какой-то причине половина бизнес-процесса для какого-то запроса не применилась и пытаешься по логам понять: это клиент врет о том, что он на самом деле сделал или это какая-то редкая бага из-за того, что оказалось, что ТЗ двух разных фич, которые были сделаны в разное время и разными людьми, противоречат друг другу, и это произошло первый раз за год работы сервиса. Много веселых (и не очень) историй у меня есть про дебаг и рефакторинг Python кода.

Нет повести печальнее на свете, чем повесть о питоне и рефакторинге. Рефакторить код в Python очень трудно, типизация и тесты делают этот процесс немного проще, но все равно огромное количество времени тратится на «Да что ж за тип у этой хрени такой», «А это-то тут откуда появилось?», «Откуда еще это исключение выползло» и т.д. и т.п.

Личный опыт рефакторинга Python кода

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

История первая:
Как-то я работал в месте, где спокойно функционировал и развивался один сервис. Все было с ним хорошо, он работал, приносил деньги компании, даже фичи новые в него добавляли. Но была у него проблема. Это был сервис на Python 2.7. А поддержка Python 2.7 закончилась. И сервис практически без тестов (и естественно, без типов). И еще надо зависимости обновить до актуальных. И по-хорошему — код отрефакторить под новые зависимости. И тесты написать. К счастью, все это прошло мимо меня, но я видел, насколько долгий и мучительный был этот процесс.

История вторая:
Наши сервисы использовали внутренний протокол (ничего такого, просто стандартизированный XML, стандартизированные URLs). Он использовался во многих сервисах, но в каждом его приходилось писать заново (или копипастить из другого сервиса). Нам это положение вещей не нравилось, и, когда пришлось писать новый сервис, мы решили заодно вынести этот протокол в отдельную библиотеку. Само по себе это было дело несложное, но я решил потратить время на то, чтобы пользоваться библиотекой было удобно.

Немного контекста

У нас были свои внутренние библиотеки, но некоторыми из них было либо тяжело пользоваться, например для работы одной из них нужно было скопипастить пару сотен строк кода из другого сервиса (а сначала понять, какой код специфичен для сервиса, а какой нужен всем). Мне хотелось этого избежать, и я потратил примерно неделю на тестирование различных вариантов, перед тем как определился. В конце концов, мне кажется, у меня получилось выполнить эту задачу, и для работы (хотя и самой простой, вместо 404 ответить 200) хватало 10 строк кода.

И казалось бы, все хорошо: роутинг, парсинг и многое другое инкапсулировано в библиотеке, она отлично работает в новом сервисе, никаких проблем. Но теперь надо было переводить старые сервисы на эту библиотеку. И несмотря на то, что библиотека была типизирована, и в сервисах были тесты заменяемой логики, рефакторинг все равно занимал очень много времени. Я руками проверял каждый возможный путь, дописывал недостающие по покрытию кода тесты, но все равно несколько раз находил новые ошибки уже после того, как думал, что закончил. То объект не тот передается, и у него нет нужного метода, то импорта не хватает, то еще что-нибудь.

Я бы с радостью рассказал о рефакторинге Golang, но, к моему счастью, мне никогда не приходилось этого делать. Наверно, это немного лучше, чем Python, но тот факт, что если при добавлении нового поля в структуру забыть её проинициализировать, и компилятор даже warning не покажет и просто подставит zero value, говорит само за себя (наверняка на этот счет есть линтер, но такой код просто не должен компилироваться. А про очевидность поведения zero value для разных типов мне даже говорить не хочется).

В отличие от Python (и многих других языков) Rust дает подходящие инструменты для рефакторинга кода, например система типов, обработка ошибок и перечисления, требующие обработки всех вариантов. Эти инструменты помогают чинить, дополнять или полностью переписывать код гораздо быстрее и с меньшими усилиями. В Rust рефакторинг намного проще, и из-за этого на нем можно разрабатывать не медленнее, а иногда даже быстрее, чем во многих других языках, которые «проще» и для «быстрой разработки».

Опыт рефакторинга Rust кода

Вернемся к моему трассировщику лучей. Через несколько лет, как я его написал, мне в голову вдруг пришла идея использовать для цвета не f64 (double), а u8 (unsigned char), который при этом будет валиден в любой момент работы программы (в оригинальной статье цвета за каждую итерацию складывались и потом делились на samples_per_pixel, а мне хотелось поддерживать актуальный цвет).

Но проблема! Код написан под f64, никаких дженериков там нет (немного есть, например вот такой ужас. Это не то, как надо писать дженерики в Rust, мне просто было интересно, как далеко можно зайти. Как оказалось, достаточно далеко). И я начал рефакторинг. Просто фиксил код, пока компилятор не перестал выдавать ошибки. И код заработал. Без тестов, без ничего. С первого раза после того, как код скомпилировался, он заработал.

Заголовок спойлера

На самом деле я немного преувеличиваю: получилось очень смешно, и в первый раз заработал только... красный канал. Как я потом выяснил, пока я проверял ошибки от компилятора, захардкодил нули в зеленый и синий каналы, и они никак не менялись. Вместо нулей надо было просто использовать todo!(). Для компилятора проблем бы не было, все типы сходятся, но при этом, если код запустить, он запаникует, и будет сразу понятно, что и почему не работает.

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

И вот теперь, спустя я уж не знаю сколько времени, мы добрались до того повода, который и сподвиг меня написать эту статью.

Я решил разобраться в том, как работает Алгоритм Ахо — Корасик. Даже нашел вроде бы неплохую статью, сижу, пишу. Дошел до части с функциями go и get_link и врезался в бетонную стену компилятора. Половина строк функций помечена как ошибки. Все выглядит очень невесело. Сижу я и думаю: да, тяжело на Rust писать всякие деревья, связные списки, рекурсивные обходы и прочее подобное. Вот примерно тот код, который у меня получился:

Заголовок спойлера
fn go(&mut self, curr_node_idx: usize, ch: char) -> usize {
    let curr_node = &mut self.nodes[curr_node_idx];
    if let Entry::Vacant(all_links) = curr_node.all_links.entry(ch) {
        if let Entry::Occupied(next) = curr_node.next.entry(ch) {
            all_links.insert(*next.get());
        } else {
            let new_link = if curr_node_idx == 0 {
                0
            } else {
                let next_link = self.get_link(curr_node.parent);
                self.go(next_link, ch)
            };
            all_links.insert(new_link);
        }
    }
    curr_node.all_links[&ch]
}

fn get_link(&mut self, curr_node_idx: usize) -> usize {
    let curr_node = &mut self.nodes[curr_node_idx];
    *curr_node.suffix_link.get_or_insert_with(|| {
        if curr_node_idx == 0 || curr_node.parent == 0 {
            0
        } else {
            let next_link = self.get_link(curr_node.parent);
            let next_node = self.go(next_link, curr_node.ch.expect("cannot be empty, only root node.ch is empty"));
            next_node
        }
    })

Как нетрудно заметить, я сразу пытался сделать максимально быструю реализацию. Entry API для доступа к элементам словаря, чтобы не перехеэшировать и не искать место для вставки лишний раз! Вынести доступ к массиву отдельно, чтобы избежать повторных проверок выхода за границы массива! get_or_insert_with чтобы красиво поменять Option на вычисленное значение и сразу вернуть его! Все замечательно, только не работает, зараза такая.

И самое то страшное в том, что компилятор-то прав. Если all_links из Entry::Vacant(all_links) используется после рекурсивного вызова self.go, то во время этого вызова в curr_node.all_links может быть добавлен новый ключ, в словаре может закончиться место, он может быть переалоцирован, и теперь all_links указывает непонятно куда.

И мне вспомнилась статья Fast Development In Rust, Part One. И я переписал все максимально прямолинейным и дуболомным способом. Никакого entry, .get().is_some(). Копипаста self.nodes[curr_node_idx] везде. .expect для получения значения из Option. И код скомпилировался.

Компилятор Rust достаточно умный. У него в заначке есть, например, Non-lexical lifetimes. И он понял, что некоторые ссылки на самом деле живут недостаточно долго для того, чтобы на самом деле вызвать проблемы. И вот теперь с компилирующимся кодом я решил попробовать вернуть что-то назад. И уже минут через 5-10 я вернул примерно половину оптимизаций назад!

Заголовок спойлера
fn go(&mut self, curr_node_idx: usize, ch: char) -> usize {
    assert!(curr_node_idx < self.nodes.len());
    let curr_node = &mut self.nodes[curr_node_idx];
    if let Entry::Vacant(all_links) = curr_node.all_links.entry(ch) {
        if let Entry::Occupied(next) = curr_node.next.entry(ch) {
            all_links.insert(*next.get());
        } else {
            let new_link = if curr_node_idx == 0 {
                0
            } else {
                let next_link = self.get_link(self.nodes[curr_node_idx].parent);
                self.go(next_link, ch)
            };
            self.nodes[curr_node_idx].all_links.insert(ch, new_link);
        }
    }
    self.nodes[curr_node_idx].all_links[&ch]
}

fn get_link(&mut self, curr_node_idx: usize) -> usize {
    assert!(curr_node_idx < self.nodes.len());
    if let Some(link) = self.nodes[curr_node_idx].suffix_link {
        link
    } else {
        let new_link = if curr_node_idx == 0 || self.nodes[curr_node_idx].parent == 0 {
            0
        } else {
            let next_link = self.get_link(self.nodes[curr_node_idx].parent);
            self.go(next_link, self.nodes[curr_node_idx].ch.expect("cannot be empty, only root node.ch is empty"))
        };
        self.nodes[curr_node_idx].suffix_link = Some(new_link);
        new_link
    }
}

Для меня не была важна скорость работы, я просто изучал, как алгоритм работает. Вряд ли бы я стал его реализовывать самостоятельно для какой-нибудь реальной задачи. Он уже реализован и оптимизирован так, что мне с вот этим смехом и не снилось. Но вот хотелось. Сэкономить аллокацию, лишнее хэширование, проверку выхода за границу массива. Но это все были преждевременные оптимизации, которые при этом помешали мне написать рабочий код.

После этого я решил еще попробовать реализовать построение суффиксных ссылок с помощью BFS т.к. так и не смог понять, что же в этой горе рекурсивных вызовов go и get_link происходит и, вооружившись новыми знаниями, написал самую простую и прямолинейную реализацию BFS, которая пришла мне в голову.

Заголовок спойлера
fn bfs_suffix_links(&mut self) {
    let mut queue = VecDeque::new();
    queue.push_back(0);
    while let Some(curr_node_idx) = queue.pop_front() {
        queue.extend(self.nodes[curr_node_idx].next.values());

        if self.nodes[curr_node_idx].ch.is_none() || self.nodes[curr_node_idx].parent == 0 {
            continue;
        }

        let current_node_char = self.nodes[curr_node_idx].ch.expect("only root node has empty .ch");

        let parent_node = self.nodes[curr_node_idx].parent;
        let parent_suffix_link = *self.nodes[parent_node].suffix_link.get_or_insert(0);

        if self.nodes[parent_suffix_link].next.get(&current_node_char).is_some() {
            let new_suffix_link = *self.nodes[parent_suffix_link].next.get(&current_node_char).expect("already checked");
            self.nodes[curr_node_idx]
                .all_links
                .insert(current_node_char, new_suffix_link);
        }
    }
}

И она скомпилировалась. Правильно с первого раза не заработала, пришлось поискать и исправить логические ошибки. Но потом код стал и компилироваться, и работать, как надо.

Если бы это был код на Python, который мне надо проверить перед мерджем, я бы сказал переделать многое из этого. В Rust же, скорее всего, нет. Если этот код будет бутылочным горлышком и потребует оптимизации — это будет несложно. Что я и сделал:

Заголовок спойлера
fn bfs_suffix_links(&mut self) {
    let mut queue = VecDeque::new();
    queue.push_back(0);
    while let Some(curr_node_idx) = queue.pop_front() {
        assert!(curr_node_idx < self.nodes.len());
        let curr_node = &mut self.nodes[curr_node_idx];
        queue.extend(curr_node.next.values());

        // Root node
        let Some(current_node_char) = curr_node.ch else {
            curr_node.suffix_link = Some(0);
            continue;
        };

        // Root children
        if curr_node.parent == 0 {
            curr_node.suffix_link = Some(0);
            continue;
        }

        let parent_node = curr_node.parent;
        let parent_suffix_link = *self.nodes[parent_node].suffix_link.get_or_insert(0);

        if let Some(&new_suffix_link) =
            self.nodes[parent_suffix_link].next.get(&current_node_char)
        {
            self.nodes[curr_node_idx]
                .all_links
                .insert(current_node_char, new_suffix_link);
        }
    }
}

Как я и говорил выше, после того, как код скомпилировался и начал правильно работать, его рефакторинг становится невероятно простым. Просто меняешь строчку за строчкой и смотришь, как на это реагирует компилятор. Если ошибок нет, то все отлично практически на 100%. Если ошибки есть, то, может быть, это небезопасно, а может, надо просто использовать что-то другое. В этот момент я понял, что мне это напоминает. Это же TDD!

По сути, в Rust по умолчанию TDD (наверно, в данном случае это должно быть CDD — compiler-driven development, разработка через компилирование), просто вместо тестов — компилятор. Сначала пишешь достойную фильма ужасов кучу как-то работающего кода, а потом приводишь её в нормальный вид. Такой подход позволяет писать и быстро, и качественно одновременно. Именно в этот момент в моей голове возникла структура этой статьи, и мне захотелось её написать. Если это будет единственное, что из этой статьи останется у вас в голове, то, прошу, запомните эту часть, все остальное было просто очень длинной подводкой к этой мысли.

Как оказалось, не только у меня такие мысли по поводу Rust. Во время дописывания этой статьи я нашел выступление Beyond Safety and Speed: How Rust Fuels Team Productivity от Lars Bergstrom, Google Android Director of Engineering на конференции Rust Nation UK 2024. Рекомендую его посмотреть полностью, это всего 30 минут. Вот несколько фактов:
— Rust-команды настолько же продуктивны (как в разработке кода, так и в поддержке), как и Golang команды и более чем в 2 раза более продуктивны, чем C++ команды;
— 2/3 опрошенных разработчиков сообщили, что спустя 2 месяца (или меньше) были достаточно уверены в знании Rust для участия в проектах;
— 85% опрошенных разработчиков сообщили, что у них выросла уверенность в корректности кода по сравнению с другими языками программирования.

Я даже не уверен, что тут можно еще добавить, выступление говорит само за себя.

С чем действительно сложно спорить, так это с тем, что большие Rust-проекты компилируются долго. Иногда очень долго.

Примеры инструментов для ускорения компиляции

cargo-wizard, который позволяет удобно настраивать профили для компиляции;
Cranelift — альтернативный компилятор, который в некоторых случаях ускоряет дебаг компиляцию.

Но даже со всем этим (и тем, что появится в будущем) я не думаю, что Rust будет компилироваться так же быстро, как Golang. И если вы Google (или компания схожего размера) то суммарно на все десятки тысяч программистов вы платите за время компиляции очень много. Для простоты даже давайте проигнорируем тот факт, что если программист ждет компиляции, то это не значит, что он не работает над чем-то другим. Задайте себе вопрос: «А влияет ли на вашу компанию скорость компиляции?» Или еще лучше: «А что больше: время, потраченное на компиляцию корректного кода, или время, потраченное на дебаг быстроскомпилированного кода?» У меня нет однозначного ответа на эти вопросы, у всех свои приоритеты.

Часть 6. Сложность

Основная часть статьи закончена, поздравляю, вы смогли дочитать до «сцены после титров». И раз уж мы все тут собрались, то давайте я заодно расскажу, почему я не считаю, что «Rust сложный». И я даже не имею в виду «Rust простой, это окружающий мир сложный», хотя в этом есть своя доля правды (пример с обработкой возможных ошибок IO выше наглядно это показывает). Я считаю, что Rust — простой язык. Я даже больше скажу: я считаю, что Rust скучный (надеюсь далее переход простой -> скучный станет понятнее).

В коде на Rust практически нет неожиданностей. А если есть, то обычно это что-то вроде «О, оказывается и для этого есть специальный метод» или «линтеры даже такое теперь подсказывают». А вот когда я пытаюсь разобраться в коде, то редко удивляюсь (хотя исключения бывают). Практически с одного взгляда понятно, что где в памяти находится, что с этим можно сделать, почему вот это возможно, почему вот этот код не работает. Даже самый ужас для всех новичков в Rust — аннотации лайфтаймов — на самом деле несложные, да и нужны только тогда, когда надо связать лайфтаймы друг с другом.

Писать корректный и безопасный код на Rust несложно, особенно с учетом помощи компилятора. Я уже рассказал про CDD, но это можно сравнить еще с одним подходом — парным программированием. Часто для ошибок, которые типичны для новичков, компилятор пишет, как исправить код прямо в тексте ошибки (это не на 100% правильно, иногда бывает так: в этом конкретном случае надо сделать что-то другое, а компилятор предлагает решение не той проблемы).

В доказательство того, что Rust простой, я предлагаю вам статью Grading on a Curve: How Rust can Facilitate New Contributors while Decreasing Vulnerabilities.

A first-time contributor to a C++ project was approximately 70 times as likely to introduce a vulnerability as a first-time contributor to an equivalent Rust project. This provides strong evidence that even if one were to accept that Rust is a more difficult language to learn than C++, it can still provide a sizable net benefit to new contributors to such projects

Заголовок спойлера

Для протокола: в статье есть график зависимости вероятности добавления уязвимости к «опыту», опыт там — это количество коммитов в проект, а не общий опыт использования конкретного языка.

Мне кажется, что это невероятное достижение! Может быть, кривая обучения в Rust — это такая ступенька, высота которой равна сложности скомпилировать код. Это позволяет новичкам в проекте (или новичкам в Rust) быть более уверенными в качестве своего кода и не бояться его писать. В Rust, если код скомпилировался, (а еще лучше и тесты прошли и новые написаны) то это достаточно хороший индикатор того, что код можно смотреть ревьюеру, и совсем неработающим он не будет.

Но тогда почему многие люди (в том числе из тех, кто пишет на Rust профессионально) говорят, что он сложный? Мне кажется, тут 2 основных момента:
— если изучать Rust как «быстрый и низкоуровневый» (т.е. как безопасный C), то появляется подсознательное желание писать производительно. Экономить аллокации, избегать .clone(), Rc<RefCell> и Arc<Mutex> и т.д. Выше я показал, что если начинать с простого кода, то можно быстро писать быстрый код.
— если все же надо выжимать каждый такт процессора, то тогда все становится сложно очень быстро.

Как и в классической схеме «быстро, качественно, дешево» в Rust есть «просто, корректно, производительно». Можно еще четвертым пунктом добавить «удобно для использования», но как в анекдоте «добавить-то можно, но выбрать все равно можно только 2».

Про «просто, корректно и непроизводительно» (скорее не максимально производительно, Rust все равно будет быстрее большинства других языков) написано выше, про «просто, производительно и некорректно» все понятно. Давайте еще рассмотрим «корректно, удобно и сложно» и «корректно, производительно и сложно» с unsafe.

Корректно, удобно и сложно

Давайте разберем аргументы функции read_dir (функция открытия папки). Единственный аргумент у этой функции — это путь, так какой же нам выбрать для этого тип?

Начнем с простого: в Rust есть строки, т.е. String. Но это плохой вариант. В Rust строки гарантированно UTF-8, а путь — совсем необязательно (эта часть вдохновлена статьей I want off Mr. Golang's Wild Ride и почему просто UTF-8 строки — это плохой выбор для пути, можете почитать там, а мы идем дальше).

Хорошо, в Rust есть OsString, он как строка, только никаких гарантий кодировки там нет, просто вектор байт. Подождите, но вектор же должен аллоцироваться в куче! Это что, нам, чтобы папку открыть, надо еще и в куче что-то аллоцировать? Звучит как-то не очень. Идем дальше.

Дальше мы находим &OsStr, который относится к OsString, как &str относится к String, т.е. это просто толстый указатель (указатель + длина в данном случае) на последовательный набор байт. А эта самая последовательность может быть где угодно: в куче, на стеке, зашита в нашем исполняемом файле и т.д. Но это все равно не идеальный вариант, это все еще строка, т.е. для &OsStr определены методы +- как у строки, а мы же не первобытные люди, мы живем в 21 веке, кто в 2024 году конструирует пути форматированием строк?

Точно не мы; нам нужно что-то еще, а именно тип Path. Это уже совсем путь, с методами для путей, внутри у него знакомый нам &OsStr, так что тут все тоже хорошо. Но и это еще не конец, мы можем сделать еще лучше!

Представьте, что нам надо открыть папку с константным путем, который будет представлен как &str. И что, нам теперь надо как минимум импортировать Path, а может, еще и OsStr, чтобы этот Path собрать? Это же ужас как неудобно, давайте в качестве пути передавать не просто Path, а AsRef<Path>, т.е. дженерик. Сам по себе AsRef дает метод as_ref(), который нужен для того, чтобы делать дешевые конвертации указателей.

Давайте посмотрим еще раз на всю нашу цепочку:
String -> OsString всегда валидно, т.к. данные у них одинаковые, и у String строго больше гарантий;
OsString -> &OsStr тоже всегда валидно, т.к., по сути, если у OsString выбросить поле capacity, то у нас и получится &OsStr;
&OsStr -> Path очевидно валидно, т.к. Path просто содержит &OsStr как единственное поле, разница у них только в методах.

Тогда получается, что мы можем все эти типы (а еще и &str) дешево конвертировать в Path. А значит, мы можем принять в нашу функцию все вышеперечисленное и внутри это привести к нужному нам виду.

Фух, это было долго, но это показывает, насколько авторы стандартной библиотеки задумывались над тем, как же ей будут пользоваться. Во многих языках нет даже намека на подобное внимание к деталям, причем даже в гораздо более фундаментальных аспектах (Golang и zero values). Во многих языках путь — это просто строка. Ведь это так удобно — собирать пути по кускам с помощью форматирования строк.

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

Unsafe

Писать корректный unsafe код действительно трудно. Труднее, чем писать на C, т.к. в Rust необходимо поддерживать больше инвариантов. Почему наличие unsafe не проблема, а достоинство Rust, почему писать unsafe код сложно, почему даже простое изменение поля структуры может быть unsafe и многое другое гораздо лучше расскажет уже упомянутый Алексей Кладов. Я только скажу: если считаете, что Rust сложный из-за того, что в нем надо писать unsafe код, то его можно не писать, нужных применений у него очень ограниченное количество. Если же считаете, что сам факт наличия unsafe делает Rust сложным (или небезопасным), то используйте либо 100% safe или проверенные временем популярные библиотеки в своем коде.

Еще возможно, что когда говорят о сложности имеют в виду "размер" языка. Обычно про что-то подобное говорят в контексте C или Golang, мол, вон какое все маленькое, все можно быстро выучить и ты уже весь язык знаешь! Этот аргумент я не понимаю совсем. Что под размером подразумевается тоже от меня ускользает. Количество ключевых слов? Размер стандартной библиотеки? Что бы это ни значило, подобная метрика не выглядит полезной. Ни C, ни Golang не являются простыми, размер им тут не помогает. Ядро атома тоже маленькое и состоит из небольшого (относительно) количества элементов, но простым это его не делает.

По такой логике Brainfuck является одним из самых простых языков. На весь язык всего 8 команд; если захотеть, все «обучение» можно скомпоновать в одно предложение, проще некуда. Проверку того, насколько легко Brainfuck писать, дебажить и рефакторить, я оставляю заинтересовавшимся читателям в качестве домашней работы, моей нервной системы на это не хватит.

Rust же не пытается быть маленьким. У одного Result я сейчас насчитал 39 методов. Мне не кажется, что это делает его сложным для понимания. Посмотреть описание метода — дело от силы 30 секунд, зато дальше знаешь, что это и зачем (про IDE я просто молчу, максимум надо курсор навести).

Кстати о Result. Монады — это не сложно. Сколько раз я читал статьи про монады, смотрел видео про них, но я до сих пор не помню, кто такой функтор и куда он морфирует. Что абсолютно не мешает использовать их в коде. Это же просто контейнер с методами! Или это интерфейс взаимодействия с данными. Никто, вроде, еще от шока при виде структуры или класса еще не умер, а чем монады-то сложнее? Слово разве что сложное, на этом сложность и заканчивается.

Часть 7. Заключительная

Если кто-то дожил до этих строк — большое вам спасибо за ваше время. Надеюсь, вы не посчитаете, что потратили его зря. Я не ожидал, что у меня получится написать 40к символов текста, но как-то это получилось.

Если у вас есть какие-то вопросы, пишите их в комментариях, постараюсь ответить.

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

Автор:
Lex98

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js