Xpoint
   [напомнить пароль]

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

2001-02-10 21:32:43 [обр] Даниил Алиевский [досье]

Уважаемые коллеги,

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

Моя Perl-программа обрабатывает HTML-страницы, которые надо скачать из Web, отыскать и скорректировать некоторые теги, сжать gzip-ом, записать в кэш (иил прочитать из него), отправить клиенту. На Perl большинство из этих задач решаются без труда.

Поначалу я не слишком задумывался о расходе памяти - свободно пользовался функцией substr, конкатенацией строк, писал функции, результат которых - строка (весь HTML-текст), и т.п. Привело это к тому, что типичный HTTPD-процесс с mod_perl'ом тратил только на обрабатываемые данные в среднем несколько мегабайт. А когда я недавно попробовал посмотреть через мою программу 10-мегабайтный текстовый файл - мой же собственный отчет :-) - HTTPD-процесс "скушал" 100 MB. И я понял, что надо принимать меры.

Вот к чему я пришел.
Допустим, нам нужно работать с текстовой строкой $text, для примера, размером 1 MB.
Имеют место две общие проблемы.

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

II) Если не предпринять специальных усилий, то после завершения главной функции память НЕ БУДЕТ освобождена! Это неважно в обычном CGI-скрипте, исполняемом внешним интерпретатором Perl: по завершении скрипта процесс будет полностью уничтожен вместе со всей своей памятью. Но в mod_perl или FastCGI, или в независимых приложениях или серверах на Perl это существенно.
То, о чем я говорю, не есть истинная утечка памяти. Занятая память будет использована повторно при следующем вызове главной функции, и многократные вызовы функции к постоянной утечке памяти не приведут. Но многократные вызовы приведут к другому: будет занят наибольший объем памяти из всех, которые были нужны при различных вариантах вызова. В моем случае, после того как я один раз посмотрел страницу размером 10 MB и соответствующий HTTPD "съел" 100 MB, он так и продолжал занимать 100 MB, пока не "скончался" из-за MaxRequestsPerChild в httpd.conf

Вот конкретные проблемы и найденные мной способы борьбы.

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

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

  1. Допустим, функция должна создать огромную строку и вернуть ее в результате. Если сделать так:

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

то этот код съест не 1, а 2 мегабайта. Мегабайт, занятый $v, можно потом освободить вызовом undef $v, но мегабайт, занятый при вычислении строкового выражения в правой части, по-моему, не освободить никак. (Может быть, кто-нибудь знает способ?) Проблема на самом деле общая: никогда не следует писать выражение, результат которого - огромная строка. Нельзя делать даже так:
my $v= $text."";
Если функция должна вернуть огромную строку, правильное решение - вернуть ссылку:

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

Этот код съест только 1 мегабайт, который освободится при вызове undef.

  1. Как передать гигантскую строку в функцию? Банальный подход будет неоптимален:

sub a {
my $text= $_[0];
работаем с $text;
undef $text;
}

В этом примере общей проблемы II) нет, но память расходуется напрасно. Если есть возможность, лучше работать непосредственно с $_[0] - т.е. с алиасом внешней переменной.
Еще лучше (нагляднее) всегда передавать гигантские строки по ссылке:

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

  1. Как соорудить конкатенацию нескольких строк, одна из которых - гигантская?

my $newtext= "$a$text$b"
(где $text огромен) съест память, которую нельзя освободить - см. 2)
Правильное решение - конкатенировать по очереди:

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

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

$text= substr($text,10);
неверно - см. 2). Правильное решение - использовать "магию lvalue":
substr($text,0,10)= "";
Правда, в документации написано, что Perl 5.004 в этом случае работал неэффективно. Но начиная с Perl 5.005 это работает прекрасно: лишняя память не расходуется.
Эквивалентное решение - 4-й параметр substr:
substr($text,0,10,"");
Но если первый вариант в Perl 5.004 работает неэффективно, то этот в Perl 5.004 вообще не скомпилируется.

  1. При использовании с громадной строкой регулярных выражений нельзя генерировать переменные $1,$2 и пр. Скажем,

$text=~s/^(.*?\015?\012\015?\012)//s;
- неверно! Хотя нам нужно от этого, очевидно, только префикс строки $1, который может быть и небольшим, Perl все равно заполнит переменные $&, $` и $'. А одна из них будет громадной! И автоматически не освободится.
"Статические" регулярные выражения, не использующие скобок (или использующие только (?:...) ), память не расходуют.

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

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

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 econimical 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;
   }
}
При отсутствии комментария, смотрится довольно загадочно :-))

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

Есть еще одна проблема, с которой я бороться не научился. Если в цикле потихоньку считывать мегабайтную строку, скажем, из сокета или файла, небольшими кусочками по 32 KB, то в процессе чтения в пике может израсходоваться не 1, а 2 мегабайта. Второй мегабайт потом обычно освобождается - но не гарантированно! Код примерно такой:
my $text= "";
for (;есть что читать;) {
   my $buf= очередные 32 KB;
   $text.= $buf;
   undef $buf;
}
работаем с $text;
undef $text;

Вот, пока все на эту тему. Буду очень рад, если кто-нибудь прокомментирует. Может быть, все это вообще решается куда проще? Я поначалу довольно долго искал в документации функцию, которая попросту выполнила бы сборку всего "мусора". Не нашел.

Жду Ваших комментариев.

спустя 16 часов [обр] Михаил Писарев :: Miker
Ну ты замонстрил ;)
Вообще-то спасибо.
Надо это выложить как статью после обсуждения.
спустя 2 часа 21 минуту [обр] Даниил Алиевский [досье]

Я тоже думаю, что надо выложить как статью :-) Но обсудить хотелось бы.

По поводу самой последней проблемы - кажется, я нашел причину. В цикле

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

"плохой" оператор - $text.= $buf
Он приводит к многократному переотведению памяти под растущую строку $text, а механика этого переотведения, очевидно, достаточно "хитрая", и действительно в некоторые моменты приводит к двойному расходу памяти. Если такой момент придется на конец цикла - значит, останется неосвобожденный мегабайт.
Правильное решение было бы такое:

пусть к этому моменту под $text уже отведен 1 MB;
for ($n=0;есть что читать;$n+=32768) {
my $buf= очередные 32 KB;
substr($text,$n,32768)= $buf;
}
если прочитано несколько меньше 1 MB, очищаем "хвост" $text вызовом substr($text,$n)="";

Но возникает законный вопрос - А КАК, собственно, в самом начале отвести под $text 1 MB памяти? Тупой вызов типа $text= " "x1000000 - это расход 2 MB. Неужели придется сочинять процедуру "отвести память", которая будет "максимально экономно" собирать длинную строку конкатенациями из серии, скажем, 100-килобайтных строк? Да и удастся ли при этом гарантированно избежать двойного расхода памяти?

спустя 3 дня [обр] Даниил Алиевский [досье]
Сам себе отвечу. Кажется, я нашел решение. Либо
$text=" "; $text x= 1000000;
либо
$text=" "; vec($text,1000000,8)= 32;
- оба способа отводят ровно 1 MB памяти, ничего не тратя зря.
Powered by POEM™ Engine Copyright © 2002-2005