Анализ производительности программного обеспечения при помощи математического планирования эксперимента

«Преждевременная оптимизация есть корень всех зол»
Энтони Хоар

Приветствую всех пользователей Хабра!
Данная статья возникла как полезный побочный продукт моих научных изысканий. Буду рад, если идеи, изложенные ниже, покажутся для вас интересными и полезными, а еще лучше, если получат своё применение и дальнейшее развитие в реально существующих проектах.

Производительность программного обеспечения (ПО) является важным аспектом в разработке любого программного продукта. Актуальность вопроса объясняется постоянно возрастающей сложностью и значимостью программных средств. Особое внимание производительности уделяется:
  • в инженерных и научных разработках, где часто производятся сложные длительные вычисления, а процессорное время на кластерных системах дорого и ограничено;
  • в web-приложениях, в которых время генерации страницы критично для пользователя и напрямую зависит от объемов серверных мощностей;
  • в встраиваемых программных продуктах, и т.д.
Тщательный анализ производительности программного продукта может существенно сократить стоимость самого оборудования и затраты на поддержание работоспособности, увеличить лояльность пользователей ПО.
Понятие производительности с точки зрения ПО означает либо продуктивность, либо реактивность:
  • продуктивность – объем информации, обрабатываемой системой в единицу времени;
  • реактивность – время между предъявлением системе входных данных и появлением соответствующей выходной информации.
В данной работе в качестве меры производительности ПО будет рассматриваться именно реактивность. Такой выбор не является принципиальным и единственно возможным, а сделан лишь для упрощения измерений в экспериментах. Рассмотрение продуктивности требует усложнения процедуры проведения тестов, так как замеры объемов обрабатываемой информации возможны не всегда. Оценка времени обработки данных системой гораздо проще в реализации, в т.ч. и при автоматизации процесса тестирования.
При анализе ПО самой очевидной и логичной задачей, стоящей перед исследователем будет увеличение производительности. Формально, мы имеем задачу оптимизации, а в контексте данного исследования – задачу минимизации времени обработки входящей информации программной системой. Таким образом, критерием оптимизации является некоторая функция

, где                (1)
  • – время обработки информации;
  • – все параметры (факторы или влияющие факторы), которые прямым или косвенным образом могут влиять на производительность системы;
  • – область определения i-го фактора, являющаяся ограничением задачи.
Выбор всей совокупности факторов, влияющих на производительность программы, не является тривиальной проблемой. Как правило, современное ПО это чрезвычайно сложная система с огромным числом связей и зависимостей. И дело не только в сложности самого программного продукта. Любая программа имеет среду выполнения языка программирования (runtime), функционирует в операционной системе, взаимодействует с другими сервисами и ПО – все эти элементы также представляют собой отдельные сложные системы с не меньшим числом внутренних связей и зависимостей. Если же добавить еще и взаимные зависимости факторов (которые могут быть не только парными и / или линейными), то получим невероятное число всевозможных комбинаций факторов.
Для примера рассмотрим программу, работающую с базой данных (БД), и производящую статистическую обработку хранимой в ней информации. Примерами влияющих на производительность факторов могут быть:
  • объем оперативной памяти компьютера;
  • скорость доступа к жесткому диску;
  • максимальная частота работы и средняя загрузка процессора;
  • настройки СУБД, и т.д.
Возможность зависимостей между этими факторами очевидна. Например, увеличение объема оперативной памяти может снизить необходимость частого доступа к жесткому диску, а, следовательно, уменьшить влияние соответствующего фактора.

Для поиска оптимальных значений влияющих факторов, т.е. для решения задачи оптимизации (1) можно предложить следующие варианты:
  • полный перебор всех возможных комбинаций значений влияющих факторов;
  • случайный выбор некоторого числа комбинаций и последующий выбор самого лучшего варианта;
  • аналитическое исследование системы;
  • применение специализированных программных средств;
  • использование математических моделей.
Все перечисленные варианты имеют свои преимущества и недостатки. Используя полный перебор можно утверждать, что искомые параметры будут найдены, однако, при большом числе факторов и вариантов их значений число всех возможных комбинаций может быть слишком велико, а проведение экспериментов займет слишком много времени. Число всех возможных комбинаций N можно найти по комбинаторным правилам:

, где                (2)
  • – число вариантов значений i-го фактора.
Тогда уже при 5 факторах и 5 возможных значениях каждого фактора получим комбинаций.
При случайном выборе оптимальной комбинации велика вероятность того, что полученное решение будет очень далеко от глобального оптимума.
Аналитическое исследование системы часто или сложно или невозможно при анализе уже существующих продуктов, без исходного кода. К тому же, подобный подход требует полного понимания исследователем всех используемых в ПО алгоритмов, связей и зависимостей компонентов.
Специальные программные средства, такие как профилировщики [5] позволяют получить лишь некоторую статистическую информацию о выполнении программного кода: число вызовов методов, среднее время выполнения методов и т.д. Оптимизация в данном случае сводится к выявлению т.н. «узких мест» и оптимизации используемых алгоритмов. Подобный подход является достаточно популярным, но не позволяет получить искомое решение задачи (1).
Математические модели анализа производительности ПО неоднократно рассматривались зарубежными и отечественными авторами. Так в работах [1], [2] предложены оригинальные подходы к решению этой задачи на разных этапах разработки ПО.
Подводя итог, следует отметить, что основными недостатками предложенных методов решения являются:
  • чрезмерно большое время проведения измерений;
  • опора на способности исследователя, делающего выводы на основе анализа программы;
  • сложность применения и использования.
Для преодоления перечисленных выше сложностей и решения поставленной задачи предлагается использовать аппарат, разработанный в теории математического планирования эксперимента (МПЭ).
Остановимся подробнее на вопросе применимости МПЭ к анализу производительности ПО. Одна из основных идей планирования эксперимента состоит в использовании для исследуемого объекта кибернетической абстракции черного ящика [3] (см. рис. 1).


Рис. 1. Абстракция черного ящика.

Такая абстракция предполагает отказ от рассмотрения внутренних механизмов исследуемого явления или объекта из-за большой сложности. Анализ явления сводится к анализу входящих параметров, воздействующих на объект (факторов) и выходных характеристик (откликов) [3].
Для применимости МПЭ необходимо соблюдение ряда условий [3]:
  • воспроизводимость опытов;
  • управляемость факторов;
  • измеримость выходных характеристик и возможность выразить её одним числом;
  • однозначность и совместимость факторов и т.д.
Проанализировав аналогии можно сделать вывод о возможности рассмотрения программной системы как черного ящика. Тогда, при выполнении указанных выше требований, для исследования производительности можно использовать весь существующий аппарат МПЭ.
В качестве примера и для отработки методики использования МПЭ для анализа производительности программной системы рассмотрим web-приложение, являющееся частью проекта «Профессиональные клубы» [4].

Этап 1. Анализ априорной информации.

При анализе априорной информации о программном продукте стало известно:
  • ПО является web-приложением, написанным на языке программирования PHP;
  • ПО выполняется на web-сервере Apache, интерпретатор PHP подключен в качестве модуля;
  • ПО использует СУБД MySQL для хранения данных;
  • существует возможность включения кэширования данных средствами самого приложения.
В качестве математической модели эксперимента[3] будем использовать самую простую – линейную модель без зависимостей между факторами. Скорее всего, такое допущение и такая совокупность факторов не соответствуют действительной ситуации, но вполне может быть использовано для тестирования самой методики. Тогда данная задача сводится к отысканию значений коэффициентов уравнения регрессии

.                (3)

Факторы с самыми большими значениями будут наибольшим образом влиять на выходную характеристику.

Этап 2. Выбор влияющих факторов.

В таблице 1 представлен набор влияющих факторов, выбранных в результате анализа априорной информации о ПО.

Таблица 1.
Фактор Описание
MySQL key_buffer_size
Параметр настройки СУБД, определяющий объем памяти, выделенной для хранения индексов [6].
MySQL table_cache
Параметр настройки СУБД, определяющий число постоянно открытых таблиц базы данных [6].
MySQL query_cache_limit
Параметр настройки СУБД, определяющий максимальный объем памяти для кэширования результатов запросов [6].
Кэширование данных приложением.
Может быть или включено или выключено.
Web-сервер и метод запуска интерпретатора PHP.
Исследуемое приложение способно запускаться двумя способами:
  • web-сервер Apache + модуль PHP;
  • web-сервер Nginx + php-fpm.

Этап 3. Выбор верхнего и нижнего уровня для факторов.

Теперь необходимо выбрать верхний и нижний уровень для каждого фактора[3]. Здесь и далее будем использовать обозначения, принятые в МПЭ:
  • +1 соответствует верхнему уровню фактора;
  • -1 соответствует нижнему уровню фактора.
Таблица 2.
Фактор Верхний уровень (+1) Нижний уровень (-1)
265 Mb. 16 Mb.
300 64
64 Mb. 1 Mb.
Кэш включен. Кэш выключен.
Nginx + php-fpm. Apache + mod_php.

Этап 4. Составление матрицы планирования и проведение экспериментов.

В таблице 3 представлены результаты проведения серии экспериментов.

Таблица 3.
y y
1 -1 -1 -1 -1 -1 6,909456902 17 +1 -1 -1 -1 -1 6,956250343
2 -1 -1 -1 -1 +1 6,265920885 18 +1 -1 -1 -1 +1 6,27117213
3 -1 -1 -1 +1 -1 1,046864681 19 +1 -1 -1 +1 -1 1,049605346
4 -1 -1 -1 +1 +1 0,959287777 20 +1 -1 -1 +1 +1 0,960128005
5 -1 -1 +1 -1 -1 6,922491238 21 +1 -1 +1 -1 -1 6,94905457
6 -1 -1 +1 -1 +1 6,292138541 22 +1 -1 +1 -1 +1 6,288483698
7 -1 -1 +1 +1 -1 1,047327693 23 +1 -1 +1 +1 -1 1,048429732
8 -1 -1 +1 +1 +1 0,959178464 24 +1 -1 +1 +1 +1 0,959984639
9 -1 +1 -1 -1 -1 6,947828159 25 +1 +1 -1 -1 -1 6,944574752
10 -1 +1 -1 -1 +1 6,269961421 26 +1 +1 -1 -1 +1 6,281574535
11 -1 +1 -1 +1 -1 1,047032595 27 +1 +1 -1 +1 -1 1,047937875
12 -1 +1 -1 +1 +1 0,960076244 28 +1 +1 -1 +1 +1 0,960813348
13 -1 +1 +1 -1 -1 6,954160943 29 +1 +1 +1 -1 -1 6,952602925
14 -1 +1 +1 -1 +1 6,278223336 30 +1 +1 +1 -1 +1 6,284795263
15 -1 +1 +1 +1 -1 1,048019483 31 +1 +1 +1 +1 -1 1,047952991
16 -1 +1 +1 +1 +1 0,960559206 32 +1 +1 +1 +1 +1 0,960591927

Этап 5. Анализ результатов.

Коэффициенты уравнения регрессии (3) могут быть найдены как


.                (4)

Результаты представлены в таблице 4 и на рис. 2.

Таблица 4.
3,97361211 0,0519711 0,0245041 0,0034686 -2,9182692 -0,2483070



Рис. 2. Коэффициенты уравнения регрессии.

Этап 6. Вывод.

Из рис. 2 видно, что основной вклад в время генерации web-страницы вносит фактор , характеризующий кэширование данных в приложении. Отрицательное значение коэффициента регрессии означает, что данный параметр уменьшает функцию отклика черного ящика. В нашем примере это означает уменьшение времени генерации страницы.
Строго говоря, такие результаты являются очевидными, так как включение кэширования данных приложением влечет за собой минимальное число запросов к СУБД. Таким образом, влияние параметров настройки СУБД становится несущественным. Полученные результаты подтверждают возможность использования МПЭ применительно к анализу производительности ПО.

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

Спасибо за внимание!

Список литературы

  1. Дубаков С.А. Информационная технология анализа производительности в процессе разработки программного обеспечения: дис. канд. техн. наук / Дубаков С.А. – Томск, 2005. – 135 с.
  2. Мойсейчук Л.Д. Разработка моделей и методов анализа производительности программного обеспечения на основе строго иерархических стохастических сетей Петри: дис. канд. техн. наук / Мойсейчук Л.Д. – Санкт-Петербург, 2002. – 152 с.
  3. Адлер Ю.П., Маркова Е.В., Грановский Ю.В. Планирование эксперимента при поиске оптимальных условий. – М.: Наука, 1976. – 279 с.
  4. ООО «Профессиональные Клубы». – URL:http://prof-club.ru/. Дата обращения: 25.09.2011.
  5. Касперски К. Техника оптимизации программ. Эффективное использование памяти. – СПб.: БХВ-Петербург, 2003. – 464 с.
  6. MySQL Server System Variables. – URL:http://dev.mysql.com/doc/refman/5.0/en/server-system-variables.html. Дата обращения: 25.09.2011.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 16

    0
    Вы занимаетесь этим в рамках курсового?
      +1
      Читаю студентам планирование эксперимента. Появилась идея — написал статью.
        0
        Просто интересно было бы посмотреть на эту модель с большим количеством значимых факторов.
      0
      Статья познавательна, спору нет. Но есть один вопрос: Когда исследуемых параметров 5-10 штук — все достаточно очевидно и доступно… А что если таких параметров сотни? А из них радикально влияющих на производительность — единицы, как в вашем примере с кешированием. Есть какие то методики, позволяющие хотя бы в первом приближении вычленить эти самые важные параметры, не строя матрицу гигантских размеров?
        +5
        Разумеется. Для сокращения матрицы планирования применяют т.н. дробные реплики. Если интересно, напишу отдельно.
          0
          Да, было бы неплохо.
        +1
        Кстати, хотел сказать насчет большого числа факторов. Тут можно было бы применить МГК и строить модель на основе только значимых, так сказать, произвести структурный анализ, хотя это не совсем то. А на основе регресионной модели хотелось бы иметь не только анализ коэффициентов регрессии, но и саму регресионную прямую. Просто мы да, получили тут явно высокий коэффициент регрессии по факту включения кеша, но это видно и сразу из экспериментальных данных. Дальше интересно было бы построить зависимость времени от размера кеша, откинув лишние факторы вообще (потому что они только отвлекают).
          +5
          Подход интересен, но мне кажется не отражает реальности. Линейная регрессия — это ооооочень сильное упрощение. Мне кажется что классические подходы теории массового обслуживание и имитационное моделирование даст картину более приближенную к реальности.
            0
            Линейная регрессия это, разумеется, очень сильное упрощение. Но если мы проведем проверку статистической гипотезы и докажем, что наша модель (линейная) адекватна (в пределах требуемой нам точности), то почему мы не можем ее использовать?
            Дело в том, что в ИТ, как правило, немного другие задачи перед экспериментатором. К примеру, в естественных науках планирование эксперимента используют для оптимизации некоторой выходной характеристики, например выход продукта химической реакции. В этом случае особенно важен вид уравнения регрессии, т.к. его мы используем для движения к оптимуму по градиенту.
            В нашем случае все немного проще. Выявление главных влияющих факторов это уже хорошее дополнение к профайлингу. Плюс возможность выявить зависимости между факторами.
            В конце концов, никто не заставляет использовать линейные модели. Пример в работе лишь показывает возможность применения МПЭ.
            Про ТМО, спасибо, подумаю.
            • UFO just landed and posted this here
              0
              А я вот только сегодня думал о подобном подходе… только вот не линейно все… далеко не линейно… Но может попробую попозже реализовать. Вы случайно не знаете ПО, которое автоматизирует это дело? А то написать все можно и самому, но есть много других задач.
                0
                А что именно вы хотите автоматизировать?
                Если автоматическое проведение серии опытов, то вам будет необходимо менять свои, специфические для приложения факторы.
                  0
                  Я хочу протестировать разные наборы параметров и найти оптимальный набор. Само собой, что параметры будут специфические, я могу составить список параметров, сделать интерфейс для их выбора и отдать их внешнему приложению. Как-то читал я о такой штуке как OpenAutomate, но оно занимается только интерфейсом, но не анализом.
                  Собственно думал я о немного другом подходе, я могу отдавать не один параметр, а довольно много. Т.е. например рендерится кадр, я на выход могу отдать время каждого этапа обработки и хочется мне найти зависимости между каждым из параметров и временем обработки каждого этапа рендеринга. Тогда было бы гораздо проще искать глобальный оптимальный результат.
                  Пока сделаю интерфейс для получения статистики, а там возможно появится кто-нибудь, кто сможет анализ реализовать… вообще интересно было бы анализировать всю статистику всегда и подстраиваться на ее основе под каждую ситуацию, но до этого пока далеко.
                +1
                +
                Но по-моему вы пропустили самую «соль» метода — составление матрицы планирования.
                  0
                  Мне тоже так показалось. И еще мне показалось, что в статье эксперимент просто перебирает все 32 двоичные комбинации пяти переменных. Немного похоже не полный перебор.

                  Насколько я помню, планирование эксперимента позволяет добиться экспоненциального снижения количества требуемых экспериментов по сравнению с полным перебором (вернее, сложность задачи оптимального перебора вариантов пропорциональна логарифму от числа вариантов при полном переборе). Кстати, генетические алгоритмы оптимизации, похоже, имеют аналогичную производительность.
                • UFO just landed and posted this here

                  Only users with full accounts can post comments. Log in, please.