Как обеспечить максимальную производительность конечного автомата Qt

Если вы используете Qt для разработки приложений и используете конечные автоматы, то вполне вероятно, что вы используете структуру конечных автоматов Qt. Итак, вы определите конечный автомат, используя простой C ++ или SCXML. Альтернативный подход - создание кода C ++ из диаграмм конечных автоматов. В этой статье сравниваются эти подходы с учетом функциональности, применимости и производительности.

Готов поспорить, что как разработчик программного обеспечения вы уже реализовали множество более или менее сложных операторов switch case. По крайней мере, это верно для меня, и большая часть этого кодирования с переключателем, по сути, была не чем иным, как реализацией различных конечных автоматов. Это самый простой способ начать программирование конечных автоматов, если у вас нет ничего другого, кроме языка программирования по вашему выбору. Хотя начать легко, такой код становится все менее и менее обслуживаемым по мере увеличения сложности конечного автомата. В конце вы убедитесь, что не хотите продолжать реализацию конечных автоматов вручную таким образом. (Между прочим - я предполагаю, что вы знаете, что такое конечный автомат.)

Реализация конечных автоматов

Существуют разные альтернативы реализации конечных автоматов. Один из лучших способов, особенно когда вы используете объектно-ориентированный язык программирования, такой как C ++, - это применение шаблона состояний. В этом подходе используются классы состояний, а также часто переходные классы. Затем определяется конечный автомат путем создания экземпляров классов состояний и их связывания с использованием экземпляров классов перехода. В этом случае фреймворк очень помогает уменьшить размер кода и усилия по реализации.

Структура конечного автомата Qt - хороший пример. Этот API позволяет «настраивать» конечный автомат с помощью компактного кода. Вам не нужно беспокоиться о деталях семантики выполнения конечного автомата, поскольку они уже реализованы фреймворком. Вам все равно придется писать код, и по мере того, как ваш конечный автомат станет более сложным и будет содержать несколько десятков или даже сотен состояний, будет очень сложно получить обзор. Картинка стоит тысячи слов, и хорошо известная концепция диаграмм состояний помогает преодолеть это ограничение. Сам Qt обеспечивает поддержку State Chart XML (SCXML), который является стандартом W3C. Поскольку писать XML вручную - неинтересно, Qt Creator также включает простой графический редактор диаграмм состояний.

Независимо от конкретного подхода к реализации, использование графического синтаксиса - лучший выбор для редактирования и понимания конечных автоматов. Такие графические модели могут быть не только представлены в текстовом виде с помощью таких языков, как SCXML, но также могут использоваться для генерации любого вида исходного кода на языке программирования, например, конечного автомата с регистром переключателей на простом C ++ или кода C ++, который устанавливает экземпляры QStateMachine. Используя инструмент, который выполняет такое преобразование за вас, вы можете избежать боли, связанной с написанием кода конечного автомата от руки. Он поднимает все три подхода к реализации на один и тот же уровень удобства использования. Тем не менее, реализации по-прежнему принципиально разные. Эта статья посвящена сравнению их поведения во время выполнения и особенно их производительности.

UnsplashФото:Austris Augusts на Unsplash

Конкуренты

Так что насчет производительности? Чем различаются доступные подходы в отношении требуемых циклов ЦП? Чтобы получить некоторые конкретные цифры, я создал набор тестов производительности. В первой части сравниваются различные стратегии реализации. Это конкуренты:

1. Интерпретатор SCXML - конечный автомат теста определяется с помощью SCXML и выполняется QSCXMLStateMachine Qt. класс.
2. Шаблон состояния - конечный автомат тестирования реализован с использованием QStateMachine классы.
3. Простой код C ++ - конечный автомат тестирования реализован классом C ++, который применяет базовый подход, основанный на переключении регистра.

Примечание. Код для этих примеров можно найти здесь.

Первые два варианта подразумевают использование таких концепций Qt, как сигналы и слоты, а также использование очереди событий Qt, в то время как для простой реализации C ++ эта инфраструктура не требуется. Чтобы сделать подходы более сопоставимыми, набор тестов включает еще два тестовых сценария:

• Простой код C ++ с сигналами и слотами - конечный автомат тестирования имеет ту же реализацию, что и описанный выше, но использует сигналы и слоты для интеграции в приложение.
• Простой код C ++ с QEvent - использует подход с использованием простого кода C ++, но использует очередь событий Qt для обработки в и вне события.

Это позволяет сравнить влияние использования сигналов и слотов, с одной стороны, и использования QEvents с другой стороны, по сравнению с простой реализацией C ++, поскольку код выполнения конечного автомата идентичен во всех случаях, но только по-разному оформлен.

Тестовый конечный автомат

Для тестирования всех пяти конкурентов я определил конечный автомат, показанный на рис. 1 для базового сценария тестирования.

Рис. 1. Тестовый конечный автомат, созданный с помощью YAKINDU Statechart Tools. (Источник:автор)

Тестовый конечный автомат - это простой плоский конечный автомат. Он определяет шесть состояний A в F и циклически перебирает состояния. Два события ввода e1 и e2 определены, которые поочередно запускают переходы между состояниями. Когда происходит переход состояния, также выполняется простое действие. Каждое действие перехода просто добавляет 10 к переменной диаграммы состояний с именем x . Переход из состояния F в A дополнительно поднимает (или излучает) из событие o .

Рисунок 2:Тестовый конечный автомат как модель SCXML в Qt Creator. (Источник:автор)

Этот конечный автомат был определен с помощью YAKINDU Statechart Tools, который поддерживает генерацию SCXML. Этот SCXML можно добавить в проект Qt и отредактировать в Qt Creator. Как видно на рис. 2, конечный автомат имеет такую ​​же структуру, как и на рис. 1, но некоторые детали, такие как действия перехода, не видны в Qt Creator. Инструменты диаграммы состояний YAKINDU предоставляют еще несколько преимуществ, но я не буду их здесь обсуждать.

Более важным здесь является тот факт, что YAKINDU Statechart Tools также может генерировать простые классы конечного автомата C ++ на основе case-case. Он также предоставляет возможность генерировать классы с поддержкой Qt с сигналами и слотами, так что это очень удобно. Используя этот инструмент, мне нужно было реализовать конечный автомат на основе шаблона состояний с помощью QStateMachine рукой. Для этого варианта не было генератора кода. Тем не менее, мне удалось сэкономить много усилий при реализации, получив при этом семантически эквивалентные конечные автоматы для тестов производительности, просто используя одно определение диаграммы состояний.

Все тестовые примеры выполняются по одной схеме. Поскольку я хотел измерить среднее время, затрачиваемое на обработку отдельных событий, каждый тест захватил миллион итераций одного цикла состояний. Каждый цикл состояний выполняет все события, необходимые для посещения всех состояний и обработки всех переходов и действий перехода. Итак, цикл состояний начинается и заканчивается состоянием A . будучи активным. Это означает, что для каждого тестового примера 6 миллионов в события и действия перехода и 1 миллион out обрабатываются события с соответствующими действиями перехода. Тесты выполнялись как приложение командной строки и записывали время итераций как единый пакет. Затем можно просто определить затраты времени на событие, разделив измеренное время на сумму количества в события и вне Мероприятия. Тесты проводились несколько раз, и были выбраны результаты измерений с самыми низкими значениями.

Тесты проводились с использованием оптимизированного кода без отладочной информации на моем старом (середина 2014 года) MacBook Pro с четырехъядерным процессором Core i7 с тактовой частотой 2,4 ГГц. Конечно, конкретные цифры будут отличаться на разных машинах и в разных операционных системах. Однако это не актуально, поскольку я хотел сравнить различные подходы к реализации относительно друг друга. Эти относительные различия будут сопоставимы на разных аппаратных средствах и платформах ОС.

Давайте посмотрим на показатели эффективности

Да, я думаю, почти каждый ожидал, что простая реализация на C ++ будет быстрее, чем другие альтернативы, но масштабы различий действительно поразительны.

Рис. 3. Сравнение времени обработки одного события. (Источник:автор)

Обработка отдельных событий с использованием простого C ++ занимала в среднем 7 наносекунд. Использование SCXML потребовало 33 850 наносекунд - это примерно 4800 раз и огромная разница! Для сравнения, свет проходит более 10 километров, в то время как конечный автомат SCXML обрабатывает только один переход, в то время как тот же переход в простом конечном автомате C ++ оставляет лишь столько времени, чтобы свет прошел чуть более 2 метров. Это подразумевает очень разные порядки циклов ЦП и энергопотребления.

Конечно, конкретные цифры зависят от машины и от использованной процедуры испытаний. Обсуду эту тему позже. Но давайте сначала обсудим другие числа. Все первые три тестовых сценария включают в себя идентичную логику перехода между состояниями, которая была сгенерирована YAKINDU Statechart Tools, но каждый из них реализован по-разному.

Использование сигналов и слотов для обработки событий занимало в среднем 72 нс при использовании прямых подключений. Таким образом, этот механизм требует минимальных накладных расходов ~ 90% по сравнению с реальной логикой конечного автомата. На этом этапе я не хочу утверждать, что использование сигналов и слотов замедляет работу приложений. Вместо этого я бы предпочел утверждать, что реализация конечных автоматов в виде простого кода выполняется очень быстро .

Сравнение этого с третьим сценарием дает хорошее представление об издержках производительности, вызванных использованием очереди событий. В этом сценарии все события диаграммы состояний маршрутизируются через очередь событий. При 731 нс на событие требуется фактор ~ 10 по сравнению с сигналами и слотами и ~ 100 по сравнению с обычным C ++.

Мы можем предположить, что сопоставимые накладные расходы также применимы к двум другим сценариям «простой QStateMachine »И« Конечный автомат SCXML »- оба требуют наличия активной очереди событий. Итак, когда предполагаемые накладные расходы очереди событий вычитаются из 5200 нс на событие, мы получаем приблизительное потребление времени QStateMachine рамки 4500нс на событие. По сравнению с подходом с использованием простого кода, реализация конечного автомата на основе QStateMachine медленная. Это примерно в 635 раз по сравнению с реализацией простого кода C ++.

Наконец, давайте взглянем на интерпретатор SCXML. Он включает в себя интерпретацию кода JavaScript и добавляет еще фактор ~ 7. По сравнению с подходом с использованием простого кода, реализация конечного автомата на основе SCXML выполняется очень медленно .

А как насчет иерархических и ортогональных конечных автоматов?

Пока что я только что профилировал простую машину с плоским состоянием. Но диаграммы состояний предоставляют гораздо больше возможностей, и две наиболее важные структурные особенности - это иерархия и ортогональность. Итак, какое влияние использование этих функций оказывает на время выполнения конечного автомата?

Во-первых, чтобы измерить влияние иерархий, я определил иерархический вариант конечного автомата, который нужно профилировать, показанный на рис. 4.

Рисунок 4:Иерархическая диаграмма состояний теста. (Источник:автор)

Он обеспечивает точно такое же поведение, что и машина с плоскими состояниями, но добавляет несколько составных состояний. Сохранение идентичной функциональности, но простое изменение структуры позволяет определить, сколько накладных расходов предполагает структурный вариант, если таковые имеются.

Во-вторых, чтобы измерить влияние ортогональности, я воспроизвел плоский конечный автомат в виде четырех ортогональных областей. Все они имеют одинаковую функциональность. Таким образом, конечный автомат (см. Рис. 5) будет выполнять в четыре раза больше работы, чем простой конечный автомат.

Рисунок 5:Диаграмма состояний ортогонального теста. (Источник:автор)

Для профилирования я выбрал простые реализации C ++ и SCXML, потому что это были самые быстрые и самые медленные варианты. Схема на рис. 6 показаны результаты. Очень обнадеживает то, что использование иерархий в диаграммах состояний не оказывает заметного влияния на производительность в обоих вариантах реализации.

Рисунок 6. Влияние иерархии и ортогональности на производительность. (Источник:автор)

Еще один положительный результат заключается в том, что использование ортогональности также не оказывает отрицательного воздействия. Напротив, хотя можно было ожидать, что время обработки по крайней мере в четыре раза больше, чтобы выполнить четырехкратную работу, эффективное увеличение времени выполнения с коэффициентами ~ 2,4 и ~ 3,1 значительно меньше, чем 4.

Почему это так? Причина этого в том, что существует общая часть обработки конечного автомата, которая не зависит от обработки отдельных состояний и событий. Эта часть занимает 52% (или 3,5 нс на событие) для простого конечного автомата C ++ по сравнению с 28% (или 9300 нс на событие) для SCXML. Наконец, ортогональные состояния имеют меньшее влияние при использовании сгенерированного кода C ++ по сравнению с SCXML.

Заключение

Обычный C ++ намного эффективнее всех альтернатив. Использование сигналов и слотов или очереди событий Qt - это механизмы инфраструктуры, упрощающие реализацию и поддержку сложных приложений конечного автомата. Каркас конечного автомата Qt требует обоих этих механизмов. Используя сгенерированный код C ++, у вас есть выбор.

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