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

ДАНИИЛ АЛИЕВСКИЙ

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

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

Но если Perl-скрипт обрабатывает действительно большие данные,— скажем, мегабайтные текстовые файлы – проблема разумного использования памяти может стать достаточно актуальной. Особенно это важно, если скрипт исполняется под управлением mod_perl или аналогичной среды. Если всецело положиться на встроенный сборщик мусора, может неожиданно оказаться, что процессы веб-сервера, исполняющие скрипты с помощью mod_perl, с каждым вызовом начинают занимать все больше памяти – вплоть до десятков мегабайт, постепенно поглощая всю свободную RAM.

Я столкнулся с этой проблемой, когда реализовывал под mod_perl сложный скрипт, предназначенный для обработки и парсинга произвольных HTML-страниц. Основным типом данных в скрипте были обычные текстовые строки. Поначалу я обращался со строками очень свободно, как это и принято в Perl и подобных языках, не задумываясь пользовался функцией substr; конкатенацией строк; регулярными выражениями; писал функции, возвращающие в результате строку (HTML-текст веб-страницы), и т.п. Привело это к тому, что типичный HTTPD-процесс с mod_perl (веб-сервер Apache на UNIX) тратил только на обрабатываемые данные в среднем несколько мегабайт. Это при том, что типичный размер HTML-страницы, которую следовало обработать, составлял всего 20-30 Кб. А когда я попробовал «пропустить» через свою программу 10-мегабайтный HTML – HTTPD-процесс «съел» 100 Мб. При этом возникало впечатление утечки памяти – процессы, по мере своей «жизни», занимали все больше и больше обьема памяти.

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

Результаты своих исследований я предлагаю вашему вниманию.

Итак, имеют место 2 основные общие проблемы.

Проблема I

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

Проблема II

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

Это не так важно в обычном CGI-скрипте, исполняемом внешним интерпретатором Perl. По завершении скрипта процесс будет полностью уничтожен вместе со всей своей памятью. Но в mod_perl или FastCGI, или в независимых приложениях, или серверах на Perl это очень существенно.

Обратите внимание – описанная проблема не есть истинная утечка памяти. Встроенный сборщик мусора действительно обеспечивает утилизацию ненужных переменных. Просто он делает это не совсем так, как можно было бы ожидать. А именно: занятая память будет использована повторно при следующем вызове той же самой функции, т.е. многократные повторные вызовы функции не будут приводить к постепенному исчерпанию RAM – явлению, которое традиционно называется утечкой памяти. Зато многократные вызовы приведут к другому: со временем будет занят наибольший объем памяти из всех, которые были нужны при различных вариантах вызова этой функции. В моем случае, после того как мои Perl-функции один раз обработали HTML-страницу размером 10 Мб и соответствующий процесс с mod_perl «съел» 100 Мб, он так и продолжал всегда занимать 100 Мб, хотя все последующие обрабатываемые страницы были небольшими. Внешне такое поведение очень похоже на утечку – объем памяти, занятый процессом, никогда не уменьшается, но постепенно медленно увеличивается – по мере того как этому процессу случайно попадаются данные все большего размера.

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

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

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

sub a {

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

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

    #просто выходим из функции, предполагая, что сборщик мусора автоматически освободит

    #память из-под $text (как это происходит со стековыми переменными в C++ и 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." ";

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

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

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

sub a {

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

  работаем с $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] содержит ССЫЛКУ на строку

  работаем с $$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

    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 Кб. Потеря памяти при этом составляет порядка 32 Кб – столько расходует вычисление выражения «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?12?12 string.... (1 MB)";

$text=~s/^(.*??15??12?15??12)//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 Мб, то в процессе чтения в пике может израсходоваться не 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 Мб, можно изредка (именно изредка!) аккуратно выполнять самостоятельное переотведение памяти.

Для аккуратного отведения памяти можно предложить один из следующих приемов:

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

или

$text=" "; vec($text,1000000-1,8)= 32;

#код пробела; можно использовать любой другой символ

Оба способа отводят ровно 1 000 000 байтов памяти, ничего не тратя зря. Второй способ («магия lvalue» для функции vec) можно использовать также для переотведения памяти.

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

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