Устранение сборщика мусора: путь RAII

Вначале был C. В C есть три типа распределения памяти: статическое, автоматическое и динамическое. Статические переменные — это константы, встроенные в исходный файл, и, поскольку они имеют известные размеры и никогда не меняются, они не так уж и интересны. Автоматическое выделение можно рассматривать как выделение стека — пространство выделяется при входе в лексический блок и освобождается при выходе из этого блока. Его важнейшая особенность напрямую связана с этим. До версии C99 для автоматически выделяемых переменных требовалось, чтобы их размеры были известны во время компиляции. Это означает, что любая строка, список, карта и любая производная от них структура должны жить в куче, в динамической памяти.

Динамическая память явно выделялась и освобождалась программистом с помощью четырех основных операций: malloc, realloc, calloc и free. Первые два из них не выполняют никакой инициализации, память может содержать мусор. Все они, кроме бесплатных, могут выйти из строя. В этом случае они возвращают нулевой указатель, доступ к которому является неопределенным поведением; в лучшем случае ваша программа взорвется. В худшем случае ваша программа какое-то время работает, обрабатывая мусорные данные перед взрывом.

Делать что-то таким образом довольно болезненно, потому что вы, программист, несете единоличную ответственность за поддержку набора инвариантов, которые заставляют вашу программу взрываться при нарушении. Перед доступом к переменной должен быть вызов malloc. Вы должны убедиться, что malloc успешно вернулся, прежде чем использовать вашу переменную. В пути выполнения должен существовать ровно один свободный вызов для каждого malloc. Если ноль, утечка памяти. Если их больше одного, ваша программа взорвется. Попыток доступа к переменной после ее освобождения может не быть. Давайте посмотрим на примере, как это выглядит на самом деле:

 int main() { char *str = (char *) malloc(7); strcpy(str, "toptal"); printf("char array = \"%s\" @ %u\n", str, str); str = (char *) realloc(str, 11); strcat(str, ".com"); printf("char array = \"%s\" @ %u\n", str, str); free(str); return(0); }

 $ make runc gcc -oc cc ./c char * (null terminated): toptal @ 66576 char * (null terminated): toptal.com @ 66576

Этот код, каким бы простым он ни был, уже содержит один антипаттерн и одно сомнительное решение. В реальной жизни вы никогда не должны записывать количество байтов как литералы, вместо этого используйте функцию sizeof. Точно так же мы выделяем массив char * точно по размеру строки, которая нам нужна дважды (на одну больше, чем длина строки, для учета нулевого завершения), что является довольно дорогой операцией. Более сложная программа может создать буфер строк большего размера, что позволит увеличить размер строки.

Изобретение RAII: новая надежда

Все это ручное управление было, мягко говоря, неприятно. В середине 80-х Бьерн Страуструп изобрел новую парадигму для своего совершенно нового языка C++. Он назвал это «Получение ресурсов — это инициализация», и основные идеи заключались в следующем: можно указать, что объекты имеют конструкторы и деструкторы, которые автоматически вызываются компилятором в соответствующее время, это обеспечивает гораздо более удобный способ управления памятью данного объекта. требуется, и этот метод также полезен для ресурсов, которые не являются памятью.

Это означает, что приведенный выше пример на C++ намного чище:

 int main() { std::string str = std::string ("toptal"); std::cout << "string object: " << str << " @ " << &str << "\n"; str += ".com"; std::cout << "string object: " << str << " @ " << &str << "\n"; return(0); }

 $ g++ -o ex_1 ex_1.cpp && ./ex_1 string object: toptal @ 0x5fcaf0 string object: toptal.com @ 0x5fcaf0

Никакого ручного управления памятью не предвидится! Строковый объект создается, вызывается перегруженный метод и автоматически уничтожается при выходе из функции. К сожалению, та же самая простота может привести к другим осложнениям. Рассмотрим пример более подробно:

 vector<string> read_lines_from_file(string &file_name) { vector<string> lines; string line; ifstream file_handle (file_name.c_str()); while (file_handle.good() && !file_handle.eof()) { getline(file_handle, line); lines.push_back(line); } file_handle.close(); return lines; } int main(int argc, char* argv[]) { // get file name from the first argument string file_name (argv[1]); int count = read_lines_from_file(file_name).size(); cout << "File " << file_name << " contains " << count << " lines."; return 0; }

 $ make cpp && ./c++ makefile g++ -o c++ c++.cpp File makefile contains 38 lines.

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

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

 vector<string> * read_lines_from_file(string &file_name) { vector<string> * lines; string line; ifstream file_handle (file_name.c_str()); while (file_handle.good() && !file_handle.eof()) { getline(file_handle, line); lines->push_back(line); } file_handle.close(); return lines; }

 $ make cpp && ./c++ makefile g++ -o c++ c++.cpp Segmentation fault (core dumped)

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

 vector<string> * lines = new vector<string>;

 $ make cpp && ./c++ makefile g++ -o c++ c++.cpp File makefile contains 38 lines.

К сожалению, хотя кажется, что это работает отлично, у него все же есть недостаток: утечка памяти. В C++ указатели на кучу должны быть удалены вручную после того, как они больше не нужны; в противном случае эта память становится недоступной, как только последний указатель выходит за пределы области действия, и не восстанавливается до тех пор, пока ОС не будет управлять ею при завершении процесса. Идиоматический современный C++ будет использовать здесь unique_ptr, который реализует желаемое поведение. Он удаляет объект, на который указывает, когда указатель выходит за пределы области видимости. Однако такое поведение не было частью языка до C++11.

В этом примере это легко исправить:

 vector<string> * read_lines_from_file(string &file_name) { vector<string> * lines = new vector<string>; string line; ifstream file_handle (file_name.c_str()); while (file_handle.good() && !file_handle.eof()) { getline(file_handle, line); lines->push_back(line); } file_handle.close(); return lines; } int main(int argc, char* argv[]) { // get file name from the first argument string file_name (argv[1]); vector<string> * file_lines = read_lines_from_file(file_name); int count = file_lines->size(); delete file_lines; cout << "File " << file_name << " contains " << count << " lines."; return 0; }

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

«В сборщик мусора, летун!»

Сборщики мусора — не новая технология. Они были изобретены в 1959 году Джоном Маккарти для Lisp. С выходом Smalltalk-80 в 1980 году сборка мусора стала мейнстримом. Однако настоящий расцвет техники пришелся на 1990-е годы: между 1990 и 2000 годами было выпущено большое количество языков, все из которых в той или иной степени использовали сборку мусора: Haskell, Python, Lua, Java, JavaScript, Ruby, OCaml. , и C# являются одними из самых известных.

Что такое сбор мусора? Короче говоря, это набор методов, используемых для автоматизации ручного управления памятью. Он часто доступен в виде библиотеки для языков с ручным управлением памятью, таких как C и C++, но гораздо чаще используется в языках, которые требуют этого. Большим преимуществом является то, что программисту просто не нужно думать о памяти; это все абстрагировано. Например, Python-эквивалент нашего вышеприведенного кода для чтения файлов выглядит просто так:

 def read_lines_from_file(file_name): lines = [] with open(file_name) as fp: for line in fp: lines.append(line) return lines if __name__ == '__main__': import sys file_name = sys.argv[1] count = len(read_lines_from_file(file_name)) print("File {} contains {} lines.".format(file_name, count))

 $ python3 python3.py makefile File makefile contains 38 lines.

Массив строк возникает при первом назначении и возвращается без копирования в вызывающую область. Сборщик мусора очищает его через некоторое время после того, как он выходит из этой области, поскольку время не определено. Интересно отметить, что в Python RAII для ресурсов, не связанных с памятью, не идиоматичен. Это разрешено — мы могли бы просто написать fp = open(file_name) вместо использования блока with , а затем позволить сборщику мусора очиститься. Но рекомендуется использовать контекстный менеджер, когда это возможно, чтобы их можно было выпустить в детерминированное время.

Как бы ни было приятно абстрагироваться от управления памятью, за это приходится платить. При сборке мусора с подсчетом ссылок все назначения переменных и выходы из области действия получают небольшую стоимость для обновления ссылок. В системах пометки и очистки через непредсказуемые промежутки времени выполнение всей программы останавливается, пока сборщик мусора очищает память. Это часто называют событием остановки мира. Такие реализации, как Python, использующие обе системы, страдают от обоих штрафов. Эти проблемы снижают пригодность языков со сборкой мусора для случаев, когда производительность критична или необходимы приложения реального времени. Можно увидеть снижение производительности в действии даже на этих игрушечных программах:

 $ make cpp && time ./c++ makefile g++ -o c++ c++.cpp File makefile contains 38 lines. real 0m0.016s user 0m0.000s sys 0m0.015s $ time python3 python3.py makefile File makefile contains 38 lines. real 0m0.041s user 0m0.015s sys 0m0.015s

Версия Python требует почти в три раза больше реального времени, чем версия C++. Хотя не всю эту разницу можно отнести к сборке мусора, она все же значительна.

Право собственности: RAII пробуждается

Значит, это конец? Должны ли все языки программирования выбирать между производительностью и простотой программирования? Нет! Исследования языков программирования продолжаются, и мы начинаем видеть первые реализации языковых парадигм следующего поколения. Особый интерес представляет язык под названием Rust, который обещает эргономику, подобную Python, и скорость, подобную C, но делает невозможными висячие указатели, нулевые указатели и тому подобное — они не будут компилироваться. Как он может делать такие заявления?

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

Владение

Вспомните, когда мы обсуждали указатели в C++, мы коснулись понятия права собственности, которое в грубом смысле означает «кто несет ответственность за удаление этой переменной». Rust формализует и усиливает эту концепцию. Каждая привязка переменной владеет ресурсом, к которому она привязывается, а средство проверки заимствования гарантирует, что существует только одна привязка, которая полностью владеет ресурсом. То есть следующий фрагмент из Rust Book не скомпилируется:

 let v = vec![1, 2, 3]; let v2 = v; println!("v[0] is: {}", v[0]);

 error: use of moved value: `v` println!("v[0] is: {}", v[0]); ^

Присваивания в Rust по умолчанию имеют семантику перемещения — они передают право собственности. Типу можно придать семантику копирования, и это уже сделано для числовых примитивов, но это необычно. Из-за этого, начиная с третьей строки кода, v2 владеет рассматриваемым вектором, и к нему больше нельзя обращаться как к v. Почему это полезно? Когда у каждого ресурса есть только один владелец, у него также есть единственный момент, когда он выходит из области видимости, который можно определить во время компиляции. Это, в свою очередь, означает, что Rust может выполнять обещания RAII, детерминировано инициализируя и уничтожая ресурсы в зависимости от их области действия, никогда не используя сборщик мусора и не требуя от программиста освобождения чего-либо вручную.

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

Заимствование

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

 fn foo(v1: Vec<i32>, v2: Vec<i32>) -> (Vec<i32>, Vec<i32>, i32) { // do stuff with v1 and v2 // hand back ownership, and the result of our function (v1, v2, 42) } let v1 = vec![1, 2, 3]; let v2 = vec![1, 2, 3]; let (v1, v2, answer) = foo(v1, v2);

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

 fn foo(v1: &Vec<i32>, v2: &Vec<i32>) -> i32 { // do stuff 42 } let v1 = vec![1, 2, 3]; let v2 = vec![1, 2, 3]; let answer = foo(&v1, &v2);

v1 и v2 возвращают свое владение исходной области после возврата fn foo, выпадают из области видимости и автоматически уничтожаются при выходе из содержащей области.

Здесь стоит упомянуть, что существуют ограничения на заимствование, накладываемые проверкой заимствования во время компиляции, которые очень кратко сформулированы в Rust Book:

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

одна или несколько ссылок (&T) на ресурс

ровно одна изменяемая ссылка (&mut T)

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

Проверка заимствования в практических терминах

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

 fn read_lines_from_file(file_name: &str) -> io::Result<Vec<String>> { // variables in Rust are immutable by default. The mut keyword allows them to be mutated. let mut lines = Vec::new(); let mut buffer = String::new(); if let Ok(mut fp) = OpenOptions::new().read(true).open(file_name) { // We enter this block only if the file was successfully opened. // This is one way to unwrap the Result<T, E> type Rust uses instead of exceptions. // fp.read_to_string can return an Err. The try! macro passes such errors // upwards through the call stack, or continues otherwise. try!(fp.read_to_string(&mut buffer)); lines = buffer.split("\n").map(|s| s.to_string()).collect(); } Ok(lines) } fn main() { // Get file name from the first argument. // Note that args().nth() produces an Option<T>. To get at the actual argument, we use // the .expect() function, which panics with the given message if nth() returned None, // indicating that there weren't at least that many arguments. Contrast with C++, which // segfaults when there aren't enough arguments, or Python, which raises an IndexError. // In Rust, error cases *must* be accounted for. let file_name = env::args().nth(1).expect("This program requires at least one argument!"); if let Ok(file_lines) = read_lines_from_file(&file_name) { println!("File {} contains {} lines.", file_name, file_lines.len()); } else { // read_lines_from_file returned an error println!("Could not read file {}", file_name); } }

Помимо элементов, уже прокомментированных в исходном коде, стоит просмотреть и проследить время жизни различных переменных. file_name и file_lines до конца main(); их деструкторы вызываются в это время без дополнительных затрат, используя тот же механизм, что и автоматические переменные C++. При вызове read_lines_from_file file_name неизменно предоставляется этой функции на время ее действия. Внутри read_lines_from_file buffer действует точно так же, уничтожаясь, когда он выходит за пределы области видимости. lines , с другой стороны, сохраняется и успешно возвращается в main . Почему?

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

«Только в конце вы осознаете истинную силу RAII».

Ручное управление памятью — это кошмар, которого программисты изобретали, чтобы избежать с момента изобретения компилятора. RAII был многообещающим шаблоном, но не работал в C++, потому что он просто не работал для объектов, размещенных в куче, без каких-то странных обходных путей. Следовательно, в 90-х произошел взрыв языков со сборкой мусора, призванных сделать жизнь программиста более приятной даже за счет производительности.

Однако это не последнее слово в языковом дизайне. Используя новые и строгие понятия владения и заимствования, Rust удается объединить шаблоны RAII, основанные на области видимости, с безопасностью памяти при сборке мусора; и все это без необходимости использования сборщика мусора для остановки мира, при этом обеспечивая гарантии безопасности, которых нет ни в одном другом языке. Это будущее системного программирования. В конце концов, «человеку свойственно ошибаться, но компиляторы никогда не забывают».

Дальнейшее чтение в блоге Toptal Engineering:

• Учебник по WebAssembly/Rust: идеальная обработка звука
• Поиск утечек памяти в Java