Курилка

Использование памяти в Perl при работе с большими строками

From: Даниил Алиевский
Date: Mon, 17 Dec 2008 14:31:37 +0000 (UTC)
Subject: Использование памяти в Perl при работе с большими строками

Статья была опубликована в 10.2002 номере журнала «Системный администратор», затем взята с OpenNET и отформатирована для удобства чтения.

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

Но если Perl-скрипт обрабатывает действительно большие данные, скажем, мегабайтные текстовые файлы, проблема разумного использования памяти может стать достаточно актуальной. Особенно это важно, если скрипт исполняется под управлением mod_perl или аналогичной среды. Если всецело положиться на встроенный сборщик мусора, может неожиданно оказаться, что процессы Web-сервера, исполняющие скрипты с помощью mod_perl, с каждым вызовом начинают занимать все больше памяти — вплоть до десятков мегабайт, постепенно поглощая всю свободную RAM. Я столкнулся с этой проблемой, когда реализовывал под mod_perl сложный скрипт, предназначенный для обработки и парсинга произвольных HTML-страниц. Основным типом данных в скрипте были обычные текстовые строки. Поначалу я обращался со строками очень свободно, как это и принято в Perl и подобных языках, не задумываясь пользовался функцией substr; конкатенацией строк; регулярными выражениями; писал функции, возвращающие в результате строку (HTML-текст Web-страницы), и т.п. Привело это к тому, что типичный HTTPD-процесс с mod_perl'ом (Web-сервер Apache на Unix) тратил только на обрабатываемые данные в среднем несколько мегабайт. Это при том, что типичный размер HTML-страницы, которую следовало обработать, составлял всего 20–30 KB. А когда я попробовал «пропустить» через свою программу 10-мегабайтный HTML HTTPD-процесс «съел» 100 MB. При этом возникало впечатление утечки памяти — процессы, по мере своей «жизни», занимали все больше и больше объёма памяти. В процессе тестирования и экспериментов я выявил общие проблемы, возникающие в Perl при работе с большими данными, и нашел способы их решения. После соответствующего переписывания, мой скрипт стал потреблять адекватное количество памяти, а утечка памяти прекратилась. Результаты своих исследований я предлагаю вашему вниманию. Итак, имеют место 2 основные общие проблемы.

ПРОБЛЕМА I

Свободное употребление Perl средств для работы со строками regexp'ов, substr, конкатенаций типа $a.$b или "$a$b" — приводит к порождению лишних копий строки, т.е. там, где по логике вещей алгоритму должно хватить 2 MB, будет потрачено 5 или 10 MB.

ПРОБЛЕМА II

Если не предпринять специальных усилий, то после завершения Perl-функции рабочая память, израсходованная в этой функции, НЕ БУДЕТ освобождена!

(Ситуация совершенно отличная от традиционной практики в языках без сборки мусора типа C++ или Pascal, когда все рабочие переменные, созданные внутри функции, уничтожаются при выходе из функции.) Это не так важно в обычном CGI-скрипте, исполняемом внешним интерпретатором Perl. По завершении скрипта процесс будет полностью уничтожен вместе со всей своей памятью. Но в mod_perl или FastCGI, или в независимых приложениях, или серверах на Perl это очень существенно. Обратите внимание — описанная проблема НЕ ЕСТЬ истинная утечка памяти. Встроенный сборщик мусора действительно обеспечивает утилизацию ненужных переменных. Просто он делает это не совсем так, как можно было бы ожидать. А именно: занятая память будет использована повторно ПРИ СЛЕДУЮЩЕМ ВЫЗОВЕ той же самой функции, т.е. многократные повторные вызовы функции не будут приводить к постепенному исчерпанию RAM — явлению, которое традиционно называется утечкой памяти. Зато многократные вызовы приведут к другому: со временем будет занят наибольший объем памяти из всех, которые были нужны при различных вариантах вызова этой функции. В моем случае, после того как мои Perl-функции один раз обработали HTML-страницу размером 10 MB и соответствующий процесс с mod_perl «съел» 100 MB, он так и продолжал всегда занимать 100 MB, хотя все последующие обрабатываемые страницы были небольшими. Внешне такое поведение очень похоже на утечку — объем памяти, занятый процессом, никогда не уменьшается, но постепенно медленно увеличивается — по мере того как этому процессу случайно попадаются данные все большего размера. Теперь рассмотрим конкретные типовые задачи, возникающие при обработке данных в Perl. Я приведу примеры традиционного решения этих задач — неправильного в свете описанных проблем — и возможные варианты аккуратного решения, не приводящие к перерасходу памяти.

1. Как завести внутри функции большую временную текстовую переменную, а перед выходом из функции освободить память из-под нее?

Неправильное решение:

sub a {
    my $text = "very large string.... (1 MB)";

    .... работаем с $text;

    # Просто выходим из функции, предполагая, что сборщик мусора
    # автоматически освободит память из-под $text (как это происходит
    # со стековыми переменными в С++ и Pascal)
}

Правильное решение — добавить undef перед выходом:

sub a {
    my $text = "very large string.... (1 MB)";

    .... работаем с $text;

    undef $text;
}

Вызов undef освободит память, занятую переменной $text. Без такого вызова получаем общую проблему II).

2. Функция должна создать большую строку и вернуть ее в результате. Неправильное решение:

sub a {
    my $text = "very large string.... (1 MB)";
    return $text;
}
my $v = a();

... работаем с $v;

Такой Perl-код «съест» не 1 мегабайт, действительно необходимый для сохранения переменной $v, а 2 мегабайта. Лишний мегабайт будет занят интерпретатором Perl при вычислении строкового выражения «a()» для последующего копирования этих данных в переменную $v.

Мегабайт, занятый $v, можно впоследствии освободить вызовом «undef $v», но мегабайт, занятый при вычислении строкового выражения в правой части, по-моему, уже не освободить никак.

Правильное решение — функция должна вернуть ссылку на созданную большую строку:

sub a {
    my $text = "very large string.... (1 MB)";
    return \$text;
}
my $v= a();

... работаем с $$v;

undef $$v; # освобождаем память, отведенную функцией a

Такой код «съест» только 1 мегабайт, который освободится при вызове undef. Проблема на самом деле довольно общая: никогда не следует писать выражение, результат которого — большая строка. Нельзя писать даже так:

my $v = $text."\n";

если строка $text потенциально может быть большой (десятки килобайт или больше).

3. Как передать большую строку в функцию?

Неправильное решение:

sub a {
    my $text = $_[0]; # параметр $_[0] содержит строку длинной 1 Мб

    ... работаем с $text;

    undef $text;
}
my $text = "very large string.... (1 MB)";
a($text);

В этом примере общей проблемы II нет, но память расходуется напрасно. Оператор присваивания $text = $_[0] расходует второй мегабайт под копию $text переменной $_[0] (который освобождается в конце вызовом «undef»).

Если есть возможность, лучше работать непосредственно с $_[0] — т.е. с алиасом внешней переменной. А еще лучше — нагляднее — всегда передавать большие строки по ссылке.

Предлагаемое правильное решение:

sub a {
    my $text = $_[0]; # параметр $_[0] содержит строку длинной 1Мб

    ... работаем с $$text;
}
my $text= "very large string.... (1 MB)";
a(\$text);

4. Как выполнить конкатенацию нескольких строк, одна из которых может быть очень большой?

Неправильное решение:

my $newtext = "$a$text$b";

или

my $newtext = $a.$text.$b;

Если строка $text велика, то подобный код «съест» память, которую нельзя освободить (см. задачу 2).

Правильное решение — конкатенировать по очереди:

my $newtext = $a;
$newtext .= $text;
$newtext .= $b;

5. Как удалить/заместить небольшую подстроку в очень большой строке?

Неправильное решение:

my $text = "very large string.... (1 MB)";
$text = substr($text, 10);

Такой код потратит лишний неосвобождаемый мегабайт при вычислении выражения substr($text, 10) — см. задачу 2. Правильное решение — использовать так называемую «магию lvalue»:

my $text = "very large string.... (1 MB)";
substr($text, 0, 10) = "";

Правда, в документации написано, что Perl 5.004 в этом случае работал неэффективно. Но начиная с Perl 5.005 это работает прекрасно: лишняя память не расходуется. Эквивалентное правильное решение — использовать 4-й параметр substr:

my $text = "very large string.... (1 MB)";
substr($text, 0, 10, "");

Но если предыдущий вариант в Perl 5.004 работает неэффективно, то такой вариант в Perl 5.004 вообще не скомпилируется.

6. Как выделить в большой строке большую подстроку? Скажем, как в мегабайтной строке выделить полумегабайтную подстроку, начиная со смещения 100,000?

По описанным выше причинам следующий очевидный код неправилен:

my $text = "very large string.... (1 MB)";
$text = substr($text, 100000, 500000);

В таком решении при вычислении «substr($text, 100000, 500000)» расходуются лишние полмегабайта, которые впоследствии невозможно освободить. Для этой задачи я не нашел краткого и изящного решения. Возможный корректный подход использует следующую функцию substrlarge:

sub substrlarge {
    # - Returns a reference to substr($_[0], $_[1], $_[2])
    # and doesn't use extra memory when $len is very large
    # Example:
    # my $ps = substrlarge($text, 500, 1000000);
    # some actions with $$ps;
    # undef $$ps;
    # - it is an economical equivalent for
    # my $s = substr($text, 500, 1000000);
    # some actions with $s;
    my $offset = $_[1];
    my $len = $_[2];
    $len = length($_[0]) - $offset unless defined $len;
    if ($len * 2 < length($_[0])) {
        my $k = 0;
        my $r = "";
        for (; $k < $len; $k += 32768) {
            $r .= substr($_[0], $offset + $k, $k + 32768 <= $len ? 32768 $len - $k);
        }
        return \$r;
    }
    else {
        my $r = $_[0];
        substr($r, 0, $offset) = "";
        substr($r, $len) = "" if defined $_[2];
        return \$r;
    }
}

Если нужно выделить сравнительно небольшой фрагмент исходной строки (в данной реализации — меньше половины общей длины), то нужный фрагмент конструируется циклом, блоками по 32 KB. Потеря памяти при этом составляет порядка 32 KB столько расходует вычисление выражения «substr($_[0], ...)» внутри цикла.

Если же требуется получить большой фрагмент — больше половины исходной строки — то используется иной, более быстрый алгоритм. Создается полная копия исходной строки, после чего у нее обрезаются конец и начало, как описано в задаче 5. При этом временно занимается память под целую копию, но затем — при обрезании — занятый объем уменьшается. Так как требуемый объем памяти под конечный результат в данной ветке сравним с размером полной копии, то кратковременный расход памяти под полную копию представляется разумной платой за более высокую скорость.

Обратите внимание: функция substrlarge работает непосредственно с аргументом $_[0], не копируя его во временную переменную — как это обычно делается в начале Perl-функций. Копирование типа «my $s = $_[0]» привело бы к напрасному расходу памяти под лишнюю копию исходной строки (см. также задачу 3).

С использованием функции substrlarge правильное решение будет таким:

my $text = "very large string.... (1 MB)";
my $v = substrlarge($text, 100000, 500000);
... работаем с $$v;

7. При использовании регулярных выражений с большой строкой нельзя генерировать переменные $1, $2 и пр. Скажем, следующий код неэффективен:

my $text = "very large\012\012 string.... (1 MB)";
$text =~ s/^(.*?\015?\012\015?\012)//s;
my $prefix = $1; # предполагается, что этот префикс невелик

Хотя от этого регулярного выражения нам требуется, очевидно, только префикс строки $1, который может быть и небольшим, Perl все равно заполнит переменные $&, $` и $'. А одна из них будет большой — сравнимой с самой $text. Причем память из-под этих переменных автоматически не освободится.

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

Можно также пользоваться «статическими» регулярными выражениями не использующими скобок (или использующими только (?:...)). Такие регулярные выражения не заполняют переменных $1, $2, ..., $&, $`, $' и соответственно не расходуют много памяти.

8. Нужно прочитать из файла или сокета большой текст.

Типичное решение выглядит примерно так:

my $text = "";
for (; есть что читать;) {
    my $buf = читаем очередные 32 KB;
    $text .= $buf;
    undef $buf;
}
.... работаем с $text;
undef $text;

Хотя на вид этот код вполне аккуратный и следует приведенным выше рекомендациям, на самом деле он все-таки может привести к проблеме. А именно, если общий объем читаемого текста порядка 1 MB, то в процессе чтения в пике может израсходоваться не 1, а 2 мегабайта. Второй мегабайт потом обычно освобождается, но не гарантированно.

Эта тонкая проблема, по-видимому, связана с механикой переотведения памяти в Perl. Оператор «$text .= $buf» время от времени увеличивает память, занятую переменной $text. В процессе такого переотведения интерпретатору Perl, вероятно, требуется двойной объем памяти: под прежнюю строку $text и под новый, увеличенный буфер для этой переменной. В этот момент процесс и занимает лишний мегабайт. Видимо, если переотведение происходит в конце цикла, второй мегабайт может и не освободиться: в соответствии в общей идеологией Perl «запасать буфера памяти на будущее повторное использование».

Правильное решение описанной задачи — взять отведение памяти на себя. Например:

... аккуратно отвести под $text 1 MB (1000000 байтов);
for ($n = 0; есть что читать; $n += 32768) {
    my $buf = читаем очередные 32 KB;
    substr($text, $n, 32768) = $buf; # магия lvalue
}
if ($n < 1000000) {
    substr($text, $n) = ""; # очищаем ненужный «хвост» $text
}

Если заранее неизвестно, что предстоит читать именно 1 MB, можно изредка (именно изредка!) аккуратно выполнять самостоятельное переотведение памяти. Для аккуратного отведения памяти можно предложить один из следующих приемов:

$text = " "; $text x= 1000000;

либо

$text = " "; vec($text, 1000000 - 1, 8) = 32; # код пробела, можно использовать другой символ

Оба способа отводят ровно 1000000 байтов памяти, ничего не тратя зря. Второй способ («магия lvalue» для функции vec) можно использовать также для переотведения памяти. Все вышеописанное протестировано и неплохо работает в ActivePerl 5.005 на NT 4.0 и в стандартном Perl из FreeBSD 4.2. Под ActivePerl 5.6 в Windows 2000 все оказалось несколько хуже: undef не освобождает память. (По крайней мере, TaskManager не показывает сокращения памяти у процесса Perl, пока длится 10-секундный sleep, следующий за вызовом undef.) Впрочем, к моменту, когда вы будете читать эту статью, возможно, этот недостаток уже будет исправлен фирмой ActiveState.

В завершение хотелось бы сделать небольшое замечание. Если вас действительно интересует эффективность работы вашей программы — в плане экономии памяти, в плане быстродействия или в любом другом смысле — никогда не стоит полностью полагаться на документацию, общие рекомендации и советы. В том числе, приведенные в этой статье. Всегда измеряйте эффективность сами! Если реальная эффективность программы не соответствует вашим априорным оценкам, ищите «узкое место» — тот «плохой оператор», который отвечает за перерасход памяти или долгое выполнение. После чего создайте тест — минимальную программу, в которой «плохой оператор» проявляет свои скверные качества, — и ищите более качественное эквивалентное решение. Именно так были найдены все описанные выше приемы.