Выпуск 11. Январь 2014

Впечатления от Saint Perl 5 | Содержание | Асинхронное программирование с IO::Async

Про опыт разработки на Perl под Raspberry PI

В статьей представлен расширенный вариант доклада на воркшопе Saint Perl 2013

Задача

Как-то раз на одном из фрилансерских сайтов я нашел такой проект: разработать на Perl программу для поиска объявлений, релевантных для соответствующих пользователей. Данные объявлений и профилей пользователей хранятся в XML-файлах и имеют примерно следующий вид:

Профили (profiles.xml):

<?xml version="1.0" encoding="utf-8"?>
<xml>
  <profiles>
    . . .
    <profile>
      <name>David Brown</name>
      <gender>Male</gender>
      <age>34</age>
      <likes>
        <like>Music</like>
        <like>Sports</like>
        <like>Movies</like>
      </likes>
      <timestamp>2013-10-25 13:34:45</timestamp>
    </profile>
    . . .
  </profiles>
</xml>

Объявления (media.xml):

<?xml version="1.0" encoding="utf-8"?>
<xml>
  <Playlist PlayerId="1000001">
    <Content id="23" type="image" location="/Content/a2/1w3ewsed.jpg" ageMin="23" ageMax="35" gender="male" likes="music;movies" />
    <Content id="237" type="image" location="/Content/0f/gtfrddsed.jpg" ageMax="35" gender="all" likes="sports" />
    <Content id="21" type="image" location="/Content/bf/1w3ewsed.jpg" ageMin="40" gender="female" />
    <Content id="33" type="video" location="/Content/9b/jiuhnnj.mp4" gender="male" likes="music;movies" />
  </Playlist>
</xml>

Для определения релевантности объявления используется следующий алгоритм: каждое объявление сравнивается с каждым профилем; если у объявления и профиля совпали такие параметры как возраст, пол, каждая из пар предпочтений (поле likes), то объявлению в каждом случае добавляется одно очко. Затем выбирается объявление с максимальным числом очков или, если таких объявлений несколько, случайным образом выбираем одно из них.

Основным условием задачи было то, что программа должна работать на Raspbery Pi — время поиска наиболее релевантного объявления для файлов из 100 профилей и 100 объявлений не должно превышать двух секунд. Как оказалось, последнее условие и стало самым сложным для выполнения. Также необходимо было записывать устаревшие профили в отдельный файл profiles_outdated.xml, а в оригинальном файле оставлять только те, у которых timestamp имеет значение не раньше, чем «10 секунд назад».

Raspberry Pi

Это компьютер размером с кредитную карту на платформе ARM11 с процессором частотой 700 МГц (я говорю о Raspberry Pi model B) и графическим ядром, которое поддерживает OpenGL ES 2.0 и может декодировать Full HD видео, 512 Мб ОЗУ, парой разъемов USB 2.0, разъемом Ethernet, HDMI, RCA Video, Audio, GPIO и разъемом для SD-карты, с которой и загружается ОС.

Питать его можно от зарядного устройства смартфона, способного выдавать 5В x 750 мА (ток лучше больше) через разъем Micro USB, ну или от других аналогичных девайсов (коллега запитывал от USB-разъема Mac Mini через переходник).

Для него существует несколько «официальных» дистрибутивов на базе Linux, доступных на странице http://www.raspberrypi.org/downloads (в их числе и нашумевшая в рунетах Pidora) и много неофициальных. Как правило, систему можно установить простым копированием образа на карту памяти формата SD. Лично мне для первоначальной настройки не понадобились даже клавиатура или монитор — девайс после загрузки сразу стал доступен по сети по доменному имени raspberrypi.

Стоимость такого устройства официально $35 — но это в Англии, а в российской рознице мне пришлось купить его за 2200 руб (примерно $66).

Для работы мы выбрали Raspbian — это дистрибутив, основанный на Debian, который из коробки содержит Perl v5.14.2, много модулей в пакетах системы, а также на него можно установить все необходимые дополнения типа perlbrew, cpanminus, local::lib и т.д.

Написание программы

Первоначальный вариант программы был написан довольно быстро — в нем использовались модули, которые я привык использовать при работе на быстрых серверах при низкой нагрузке и в предварительно загружаемой среде (т.е. время загрузки модулей не имело для меня значения). Для парсинга XML я использовал потоковый парсер XML::Rules в предположении, что мне будет удобно асинхронно обрабатывать устаревшие профили. Также я активно использовал отладку, а для отображения структур данных использовал функции модуля Data::Dump. Начало программы выглядело примерно так:

use common::sense;
use local::lib;
use Const::Fast;
use DateTime;
use Data::Dump qw(pp);
use File::Temp ();
use File::Copy qw(mv);
use List::UtilsBy qw(max_by);
use Time::HiRes qw(gettimeofday tv_interval);
use XML::Rules;

Используемый алгоритм был довольно прост: сначала файл профилей целиком считывался в память, значение атрибута likes приводилось к нижнему регистру и преобразовывалось в массив предпочтений. Затем в процессе парсинга файла профилей для каждого профиля код обходил все объявления и искал совпадающие атрибуты — пол, возраст, предпочтения. Для каждого совпадения объявлению добавлялось одно очко. Разумеется, это выполнялось только для достаточно свежих профилей (не старше 10 секунд), устаревшие профили отсеивались.

Правило для XML::Rules выглядело таким образом:

# Parse profiles file
my $profile_parser = XML::Rules->new(
style         => ‘filter’,
rules         => {
    _default  => 'raw',
    profile   => sub {
        my ($tag_name, $attr, undef, undef, $parser) = @_;

        my $profile = extract_tags({ %{ $attr } }->{_content});
        $profile->{likes}
            = [map { lc $_->[1]->{_content} } @{ $profile->{likes} }];

        if (is_profile_outdated($profile->{timestamp})) {
            mark_as_outdated($profile);
            return ();
        }

        for my $ad (@{ $parser->{parameters}->{ads} }) {
            my $score = calc_score($ad, $profile);
            $ad->{scores}->{ $profile->{name} } = $score;
            $ad->{scores}->{total} += $score;
            $parser->{parameters}->{total_scores} += $score;
        }
        return $tag_name => $attr;
    },
});
$profile_parser->filterfile($profile_file, $tmp_fh->filename, $playlist);

Здесь можно увидеть, что XML::Rules используется в режиме фильтра, а не парсера и сохраняет результат (только свежие профили) во временный файл $tmp_fh.

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

Оптимизация

Шаг 1. Используем быстрые модули

Первые мои действия по оптимизации были немного наивными и основывались не на точном расчете, а, скорее, на интуиции. Для определения возраста профилей я использовал модуль DateTime. Я знал, что модуль DateTime::TimeZone довольно долго определяет локальную временную зону при первом запуске (это написано и в его документации), и поэтому решил заменить DateTime чем-то более быстрым. После некоторого поиска решил использовать Date::Calc, который имеет не слишком-то красивый интерфейс, безо всякого ООП, зато очень сильно оптимизирован при помощи XS. Замена DateTime на Date::Calc сократило время выполнения программы примерно на 4 секунды.

Помимо этого, так как мне не нужна была потоковая загрузка объявлений, для загрузки файла объявлений я решил использовать модуль XML::Fast, который также написан на Си и очень быстро работает на небольших файлах.

Шаг 2. Ненужная отладка

Для отладки изначально использовался следующий код:

sub debug {
    warn @_ if $DEBUG;
}

# Где-то в коде…
debug('ads with scores: ' . pp($playlist));

Может это и незаметно на первый взгляд, но этот код работает даже тогда, когда нам это не нужно — т.е. когда флаг $DEBUG не установлен. В том случае, когда $playlist содержит много данных, преобразование содержащейся в этой переменной структуры в читабельный вид занимает довольно много времени, поэтому, когда я изменил код для отладки на приведенный ниже, время работы программы сократилось на 19 (!) секунд.

if ($DEBUG) {
    require Data::Dump;
}

sub debug {
    return if !$DEBUG;

    warn map { ref $_ ? Data::Dump::pp($_) : $_ } @_;
}

# Где-то в коде…
debug('ads with scores: ', $playlist); # Здесь запятая!

Шаг 3. Замеряем время работы

На данный момент время работы программы составляло уже около 7 секунд, но все «интуитивные» возможности оптимизации были уже исчерпаны, поэтому я решил наконец-то взяться за точные измерения и вооружился модулем Devel::Timer от Gábor Szabó. Этот модуль позволяет сделать то же, что бы вы сделали при помощи функций Time::HiRes — измерить время выполнения каждой отдельной секции кода, но предоставляет для этого удобный интерфейс и формирует отчет на основании измеренных значений.

Понаставив везде «отметок», я получил следующие результаты для хода выполнения программы:

Devel::Timer Report -- Total time: 7.3259 secs
Count     Time    Percent
----------------------------------------------
1  3.6184  49.39%  created temp file -> profiles processed   # подсчет очков
1  1.6455  22.46%  BEGIN -> loaded           # загрузка модулей
1  1.1747  16.03%  loaded -> media file read     # чтение файла объявлений
1  0.8662  11.82%  file moved -> ad shown        # get_ad_to_show() && show_ad()
1  0.0079   0.11%  ad shown -> END
1  0.0060   0.08%  set up profile rules -> created temp file
1  0.0036   0.05%  profiles processed -> file moved
1  0.0032   0.04%  media file read -> set up profile rules
1  0.0004   0.00%  INIT -> BEGIN

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

Devel::Timer Report -- Total time: 1.6027 secs
Interval  Time    Percent
----------------------------------------------
09 -> 10  0.3867  24.13%  loaded List::UtilsBy -> loaded XML::Rules;
06 -> 07  0.3401  21.22%  loaded Data::Dump -> loaded File::Temp
02 -> 03  0.3279  20.46%  loaded common::sense; -> loaded local::lib;
10 -> 11  0.1328   8.28%  loaded XML::Rules; -> loaded XML::Fast
04 -> 05  0.1080   6.74%  loaded Const::Fast; -> loaded Date::Calc
05 -> 06  0.0851   5.31%  loaded Date::Calc -> loaded Data::Dump
11 -> 12  0.0772   4.81%  loaded XML::Fast -> loaded File::Map
03 -> 04  0.0539   3.36%  loaded local::lib; -> loaded Const::Fast;
07 -> 08  0.0521   3.25%  loaded File::Temp -> loaded File::Copy
08 -> 09  0.0265   1.65%  loaded File::Copy -> loaded List::UtilsBy
01 -> 02  0.0095   0.59%  BEGIN -> loaded common::sense;
13 -> 14  0.0024   0.15%  modules loaded -> END
00 -> 01  0.0004   0.02%  INIT -> BEGIN
12 -> 13  0.0003   0.02%  loaded File::Map -> modules loaded

Из этого отчета видно, что дольше всего загружаются модули XML::Rules, File::Temp и local::lib. От local::lib и File::Temp можно было избавиться довольно легко — прописав пути к библиотекам в переменной среды PERL5LIB и используя стандартное имя для временного файла — типа profiles.xml.tmp. Также я решил избавиться и от XML::Rules, заменив его полностью на XML::Fast. Асинхронная обработка, которую я надеялся использовать для ускорения программы, мне оказалась не нужна, и выигрыш от ее использования перекрывался необходимостью загрузки «тяжелого» модуля.

Также я избавился от модулей File::Copy, File::Map и Const::Fast — работать с файлами оказалось быстрее стандартными средствами Perl, а пару используемых констант можно было заменить переменными — программа получилась не настолько большой, чтобы использование констант было принципиально.

Некоторый прирост по скорости принесло то, что я решил сразу приводить к нижнему регистру при помощи функции lc() все содержимое файлов перед парсингом, а не отдельно предпочтения для каждого профиля или объявления.

После выполнения всех этих шагов я получил такой результат работы программы:

time ./parser.pl samples/profile.xml samples/media.xml

Devel::Timer Report -- Total time: 1.8889 secs
Count     Time    Percent
----------------------------------------------
1  1.3133  69.53%  calculating scores: start -> calculating scores: end
1  0.4887  25.87%  program: start -> modules loaded
1  0.0329   1.74%  read profile file: start -> read profile file: end
1  0.0157   0.83%  searching for ad to show: start -> searching for ad to show: end
1  0.0143   0.76%  write profile file: start -> write profile file: end
1  0.0126   0.67%  read media file: start -> read media file: end
1  0.0046   0.24%  convert media file: start -> convert media file: end
1  0.0027   0.14%  searching for ad to show: end -> program: end
1  0.0023   0.12%  write profile file: end -> searching for ad to show: start

real    0m2.142s
user    0m2.040s
sys 0m0.070s

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

Шаг 4. Оптимизация алгоритма

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

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

Как мы видим, ядром этой функции является вложенный цикл, который выглядит примерно так:

for my $profile (@profiles) {
    for my $ad (@ads) {
        $ad->{score} += calc_score($ad, $profile);
    }
}

Если оценить сложность этого алгоритма, то она составляет O(MxN), где M — количество объявлений, а N — количество профилей. Таким образом, для 100 объявлений и 100 профилей мы получим 10000 итераций. Можно ли уменьшить сложность алгоритма и количество итераций? В программировании одной из частых практик для достижения подобной цели является обмен процессора на память или наоборот. То есть мы должны пожертвовать неким количеством памяти, чтобы уменьшить загрузку процессора. В данном случае мы можем сделать это, проиндексировав объявления — то есть сохранив для каждого возможного значения каждого параметра (пол, возраст, предпочтения) список Id объявлений, которым соответствует значение этого параметра. И использовать впоследствии этот список при подсчете очков. Вот код, который выполняет эту работу:

my %age;    # Ads valid for given age
my %gender; # Ads scored for given gender
my %like;   # Ads scored for given preference
for my $ad (@{ $playlist->{content} }) {
    # Fill ages
    my $age_min = int($ad->{agemin}) || 0;
    my $age_max = int($ad->{agemax}) || 100;
    for my $current_age ($age_min .. $age_max) {
        push @{ $age{$current_age} }, $ad->{id};
    }
    # Fill genders
    given ($ad->{gender}) {
        when ('male') {
            push @{ $gender{male} }, $ad->{id};
        }
        when ('female') {
            push @{ $gender{female} }, $ad->{id};
        }
        when ('all') {
            push @{ $gender{male} }, $ad->{id};
            push @{ $gender{female} }, $ad->{id};
        }
    }
    # Fill likes
    for my $current_like (split /;/, $ad->{likes}) {
        push @{ $like{$current_like} }, $ad->{id};
    }
}

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

# Score of each ad
my %score;
sub calc_score {
    my ($profile) = @_;
    # Gender
    if (exists $profile->{gender}) {
        for my $ad_id (@{ $gender{$profile->{gender}} || [] }) {
            $score{$ad_id}++;
       }
    }
    # Age
    if (exists $profile->{age}) {
        for my $ad_id (@{ $age{$profile->{age}} }) {
            $score{$ad_id}++;
       }
    }
    # Likes
    if (ref $profile->{likes} && ref $profile->{likes}->{like}) {
        for my $profile_like (@{ $profile->{likes}->{like} }) {
            for my $ad_id (@{ $like{ $profile_like } || [] }) {
                $score{$ad_id}++;
           }
        }
    }
}

После этой оптимизации тайминги работы программы на имеющихся тестовых данных выглядели так:

time ./parser.pl samples/profile.xml samples/media.xml

Devel::Timer Report -- Total time: 0.8667 secs
Count     Time    Percent
----------------------------------------------
1  0.5066  58.45%  program: start -> modules loaded
1  0.1656  19.11%  calculating scores: start -> calculating scores: end
1  0.1177  13.58%  index media file: start -> index media file: end
1  0.0339   3.91%  read profile file: start -> read profile file: end
1  0.0152   1.75%  write profile file: start -> write profile file: end
1  0.0130   1.50%  read media file: start -> read media file: end

real    0m1.119s
user    0m1.070s
sys 0m0.020s

Таким образом, за счет индексации объявлений мы сэкономили около одной секунды — то есть почти вдвое уменьшили время работы программы.

Шаг 5 и последний. С ног на голову

В последний момент я решил попробовать ускорить работу программы, не трогая саму программу. Как это так? Очень просто — дело в том, что Raspberry Pi поддерживает оверклокинг, причем Raspbian из коробки предлагает инструменты для него.

Вводим команду sudo raspi-config, входим в меню Overclocking и выбираем нужную частоту из доступных: 700 (по умолчанию), 800, 900, 950, 1000 МГц. При выборе последней опции нас предупреждают, что в этом режиме может испортиться карта памяти, но нас это не страшит… В итоге при частоте 1000 МГц время выполнения программы сократилось еще на 0,3 секунды и составило около 0,8 секунд. Не то чтобы этот выигрыш нам был так уж нужен, но мы можем просто иметь его в виду на случай, если нам вдруг понадобится прибавка к скорости.

Заключение

На конференции Saint Perl 2013, где я впервые делал этот доклад, мне немного не хватило времени, и поэтому залу разрешили задать только один вопрос. Этот вопрос был: «Зачем нужна вся эта оптимизация, если можно просто переписать всё на Си?». Ответил я на него в том ключе, что изначально задача состояла в написании программы на Perl, и я действовал в рамках задания. Однако, подумав над этим вопросом хорошенько после конференции, я пришел и к другому ответу.

Во-первых, мне нравится Perl и я знаю его намного лучше, чем Си. Я бы просто не стал браться за задачу, если бы ее нужно было написать на Си. Видимо, какие-то подобные размышления руководили и заказчиком этой программы — наверное, он знал немного Perl и чувствовал себя в силах изменить или исправить как-то программу на Perl, если в ней что-то пойдет не так. А может им и экономические мотивы руководили, не знаю. В любом случае это как раз тот случай, когда не технология руководит людьми, а люди меняют технологию под себя, чтобы она служила их интересам. Кроме того, основные используемые модули, собственно, написаны на Си и вызываются из Perl при помощи XS.

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

Илья Чесноков


Впечатления от Saint Perl 5 | Содержание | Асинхронное программирование с IO::Async
Нас уже 1381. Больше подписчиков — лучше выпуски!

Комментарии к статье

Чат