Выпуск 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 →