Довольно много усилий было потрачено на то, чтобы сделать библиотеку быстрой для небольших простых машинимасштабируемой одновременно (это относится только к<state_machine<>>, все еще есть место для оптимизации<fifo_scheduler<>>, особенно для многопоточных сборок). Хотя я считаю, что он должен работать разумно в большинстве приложений, масштабируемость не предоставляется бесплатно. Таким образом, небольшие, тщательно обработанные государственные машины легко превзойдут эквивалентный Boost. Статистические машины. Чтобы получить представление о том, насколько велик разрыв, я реализовал простой бенчмарк в примере BitMachine. Пример ручной работы - это ручной вариант 1-битной машины, реализующий тот же бенчмарк.
Я пытался создать справедливый, но несколько нереалистичный сценарийв худшем случае:
Для обеих машин перед началом испытания выделяется ровно один объект единственного события. Этот же объект затем посылается машинам снова и снова.
Машина ручной работы использует двойную отправку GOF-посетителя. Государства распределяются таким образом, что отправка события; переход составляет не более двух виртуальных вызовов и одного назначения указателя.
The Benchmarks - работает на 3,2 ГГц Intel Pentium 4 - произведено следующее время отправки и перехода на событие:
Рукоделие:
MSVC7.1: 10n
GCC3.4.2: 20n
Intel9.0: 20ns
1-bit-BitMachine с индивидуальным управлением памятью:
MSVC7.1: 150ns
GCC3.4.2: 320ns
Intel9.0: 170н
Хотя это большая разница, я все еще думаю, что она не будет заметна в большинстве приложений реального мира. Независимо от того, используется ли приложение ручной работы или Boost. Государственные карты будут...
Почти никогда не сталкивайтесь с ситуацией, когда государственная машина завалена таким количеством событий, как в бенчмарках. Государственная машина почти всегда проводит много времени в ожидании событий (которые обычно происходят от человека-оператора, от машин или от электронных устройств по сравнительно медленным каналам ввода-вывода). Парсеры — это единственное применение FSM, где это не так. Тем не менее, парсерные ФСМ обычно не указываются непосредственно на уровне государственной машины, а на более высоком, который лучше подходит для этой задачи. Примерами таких более высоких уровней являются Boost.Regex, Boost.Spirit, XML. Схемы и т.д. Кроме того, характер парсеров позволяет проводить ряд оптимизаций, которые невозможны в рамках FSM общего назначения. Нижняя строка: хотя с помощью этой библиотеки можно реализовать парсер, это почти никогда не рекомендуется делать, потому что другие подходы приводят к лучшей производительности и более выразительному коду.
Часто запускают государственные машины в собственных нитях. Это добавляет значительную блокировку и переключение потоков над головой. Тесты производительности на примере PingPong, где два асинхронных состояния машины обмениваются событиями, дали следующие времена для обработки одного события и выполнения результирующей реакции состояния (с использованием библиотеки сboost::fast_pool_allocator<>):
Однопоточность (без блокировки и ожидания): 840n / 840ns
Многопоточность с одним потоком (планировщик использует блокировку mutex, но никогда не должен ждать событий): 6500ns / 4800ns
Многопоточность с двумя нитями (оба планировщика используют блокировку mutex и точно один всегда ждет события): 14000ns / 7000ns
Как упоминалось выше, определенно есть возможность улучшить сроки для асинхронных машин. Кроме того, это очень грубые ориентиры, предназначенные для демонстрации накладных расходов на блокировку и переключение контекста резьбы. Накладные расходы в реальном приложении, как правило, будут меньше, и другие операционные системы, безусловно, могут работать лучше в этой области. Тем не менее, я твердо верю, что на большинстве платформ накладные расходы на резьбу обычно больше, чем время, которое увеличивается. Statechart расходует средства на отправку событий и переход. Машины ручной работы неизбежно будут иметь одинаковые накладные расходы, что сделает необработанную однопоточную скорость отправки и перехода гораздо менее важной.
Почти всегда выделяйте событияnewи уничтожайте их после потребления. Это добавит несколько циклов, даже если управление памятью событий настроено.
Часто используют государственные машины, которые используют ортогональные состояния и другие расширенные функции. Это заставляет ручные машины использовать более адекватную и более трудоемкую бухгалтерию.
Поэтому в реальных приложениях отправка событий и переход обычно не являются узким местом и относительным разрывом между ручной работой и ростом. Машины Statechart также становятся намного меньше, чем в худшем случае.
Detailed performance data
В попытке выявить основное узкое место производительности была написана примерная программа «Performance». Он измеряет время, затрачиваемое на обработку одного события в разных вариантах BitMachine. В отличие от примера BitMachine, в котором используются только переходы, Performance использует различное количество реакций в состоянии вместе с переходами. Единственное различие между внутригосударственными реакциями и переходами состоит в том, что первые не входят и не выходят из каких-либо государств. Кроме того, необходимо запустить такое же количество кода, чтобы отправить событие и выполнить полученное действие.
Следующие диаграммы показывают среднее время, которое библиотека тратит на обработку одного события, в зависимости от процента используемых реакций в состоянии. 0% означает, что все запущенные реакции являются переходами. 100% означает, что все запущенные реакции являются реакциями в состоянии. Я делаю следующие выводы из этих измерений:
Довольно линейный ход кривых говорит о том, что измерения со 100% коэффициентом реакции в состоянии являются точными, а не просто продуктом оптимизации в компиляторе. Такая оптимизация могла быть возможна из-за того, что в 100% случае известно, что текущее состояние никогда не изменится.
Точки данных со 100% коэффициентом реакции в состоянии и оптимизированной скоростью RTTI показывают, что современные компиляторы, по-видимому, настолько агрессивно встраивают сложный код отправки, что отправка сводится к немного большему, чем на самом деле, одному вызову виртуальной функции, за которым следует линейный поиск подходящей реакции. Например, в случае с 1-битной Bitmachine, Intel9.0, похоже, производит код отправки, который одинаково эффективен, как два вызова виртуальной функции в ручной машине.
На всех компиляторах и во всех вариантах время, затраченное на отправку событий, затмевается временем, затраченным на выход из текущего состояния и вход в целевое состояние. Стоит отметить, что BitMachine является плоской и неортогональной государственной машиной, представляющей собой практически худший случай. Машины реального мира часто выходят и входят в несколько состояний во время перехода, что еще больше затмевает чистое время отправки. Это делает осуществление постоянной отправки (по просьбе нескольких человек во время официального рассмотрения) делом с небольшими заслугами. Вместо этого будущие усилия по оптимизации будут сосредоточены на вводе государства и выходе из него.
Intel9.0, по-видимому, испытывает проблемы с оптимизацией кода, как только количество кода превышает определенный порог. В отличие от двух других компиляторов, мне нужно было собрать тесты для 1, 2, 3 и 4-битной BitMachine в отдельные исполняемые файлы, чтобы получить хорошую производительность. Даже тогда производительность была слишком плохой для 4-битной BitMachine. Было намного хуже, когда я собрал все 4 теста в один и тот же исполняемый файл. Это выглядит как ошибка в компиляторе.
Out of the box
Библиотека используется как есть, без каких-либо оптимизаций и модификаций.
В основе каждой государственной машины лежит реализация двойной диспетчеризации. Это связано с тем, что входящее событиеиактивное состояние определяют точно, какую реакциюпроизведет государственная машина. Для каждой отправки события один виртуальный вызов сопровождается линейным поиском соответствующей реакции с использованием одного сравнения RTTI на реакцию. Были рассмотрены, но отвергнуты следующие альтернативы:
Ациклический посетитель: Этот вариант двойной диспетчеризации удовлетворяет всем требованиям масштабируемости, но плохо работает из-за дорогостоящих перекрёстных транскастов дерева наследования. Кроме того, государство должно хранить один v-указатель длякаждой реакции, что замедляет конструкцию и делает настройку управления памятью неэффективной. Кроме того, C++ RTTI неизбежно должен включаться, что негативно сказывается на исполняемом размере. Повышаю. В Statechart изначально использовался ациклический посетитель и был примерно в 4 раза медленнее, чем сейчас (MSVC7.1 на Intel Pentium M). Скорость отправки может быть лучше на других платформах, но другие негативные последствия останутся.
Гость: Модель GOF Visitor неизбежно делает всю машину зависимой от всех событий. То есть всякий раз, когда добавляется новое событие, невозможно перекомпилировать всю государственную машину. Это противоречит требованиям масштабируемости.
Единый двухмерный массив указателей функций: Для удовлетворения требования 6 должна быть возможность распространения одной государственной машины на несколько переводческих единиц. Это, однако, означает, что диспетчерская таблица должна быть заполнена во время выполнения, и различные переводческие единицы должны каким-то образом сделать себя «известными», чтобы их часть государственной машины могла быть добавлена в таблицу. Это невозможно сделать автоматическии. Единственный портативный способ, которым государственная машина, распределенная по нескольким единицам перевода, может использовать двойную отправку на основе таблицы, зависит от пользователя. Программисту (программистам) каким-то образом пришлось бывручнуюсвязывать различные части государственной машины. Мало того, что эта шкала плохо, но и довольно подвержена ошибкам.
Из коробки все (объекты событий, объекты состояний, внутренние данные и т.д.) распределяется через<std::allocator< void >>(по умолчанию для параметра шаблона Allocator). Это должно быть удовлетворительным для заявок, удовлетворяющих следующим предпосылкам:
Не существует детерминированного времени реакции (твердого реального времени).
Приложение никогда не будет работать достаточно долго, чтобы фрагментация кучи стала проблемой. Это, конечно, проблема для всех долго работающих программ, а не только тех, которые используют эту библиотеку. Однако следует отметить, что проблемы фрагментации могут появиться раньше, чем при использовании традиционных фреймворков FSM.
Если заявка не соответствует этим предпосылкам, увеличить. Управление памятью Statechart можно настроить следующим образом:
Передавая модель стандартного концепта Allocator шаблонам классов, поддерживающим соответствующий параметрevent<>,state_machine<>,asynchronous_state_machine<>,fifo_scheduler<>,fifo_worker<>. Это перенаправляет все ассигнования на переданный пользовательский распределитель и должно удовлетворять потребности практически любого проекта.
Кроме того, можноотдельнонастроитьсостояниеуправление памятью путем перегрузкиoperator new()иoperator delete()для всех классов состояний, но это, вероятно, полезно только в редких случаях.
Когда государственная машина (или ее части) компилируются в DLL, могут возникнуть проблемы из-за использования внутреннего механизма RTTI (см. пункт FAQ «Как я могу компилировать государственную машину в библиотеку динамических ссылок (DLL)?". Использование варианта 2 является одним из способов обойти такие проблемы (на некоторых платформах это кажется единственным способом).
Объекты состояния и события должны хранить один указатель меньше, а это означает, что в лучшем случае след памяти объекта машины состояния может уменьшиться на 15% (пустое событие обычно на 30% меньше, что может быть преимуществом, когда есть всплески событий, а не постоянный поток). Однако на большинстве платформ исполняемый размер увеличивается при включении C++ RTTI. Таким образом, учитывая небольшую экономию на объекте машины, это имеет смысл только в приложениях, где выполняются оба следующих условия:
Отправка событий никогда не станет узким местом
Существует необходимость сокращения памяти, выделяемой во время выполнения (за счет большего исполняемого файла).
Очевидными кандидатами являются встроенные системы, в которых исполняемый файл находится в ПЗУ. Другими кандидатами являются приложения, работающие на большом количестве машин с одинаковым состоянием, где эта мера может даже уменьшить общий объем памяти.
В 32-битной коробке для одного пустого активного состояния обычно требуется менее 50 байт памяти. Даже очень сложные машиныобычно имеют менее 20 одновременно активных состояний, поэтому почти каждая машина должна работать с менее чем одним килобайтом памяти (не считая очередей событий). Очевидно, что отпечаток памяти на машину компенсируется любыми локальными членами, добавленными пользователем.
Processor cycles
Следующий рейтинг должен дать приблизительную картину того, какая функция будет потреблять, сколько циклов:
state_cast<>(): На сегодняшний день наиболее трудоемкая функция. Поиск линейно подходящего состояния с использованием одногоdynamic_castна каждое посещенное состояние
Профилирование полностью оптимизированной 1-битной машины показало, что примерно 3 четверти общего времени обработки событий тратится на разрушение выходящего состояния и построение введенного состояния. Очевидно, что переходы, в которыхнаиболее распространенный контекст«далеко» от состояний листьев и/или с большим количеством ортогональных состояний, могут легко вызвать разрушение и конструирование довольно многих состояний, что приводит к значительному количеству времени, затрачиваемому на переход.
state_downcast<>(): Поиск линейно для запрашиваемого состояния с использованием одного виртуального вызова и одного сравнения RTTI для посещаемого состояния
Глубокая история: Для всех внутренних состояний внутри состояния, проходящего либоhas_deep_history, либоhas_full_historyк его базовому классу состояния, на каждом выходе должен выполняться двоичный поиск по (обычно небольшой) карте истории. История выделения слота выполняется ровно один раз, при первом выходе
Маленькая история: Для всех прямых внутренних состояний состояния, проходящих либоhas_shallow_history, либоhas_full_historyк его базовому классу состояния, на каждом выходе должен выполняться двоичный поиск по (обычно небольшой) карте истории. История выделения слота выполняется ровно один раз, при первом выходе
Диспетчер событий: Один виртуальный вызов, за которым следует линейный поиск подходящей реакции, с использованием одного сравнения RTTI на каждую посещенную реакцию
Ортогональные состояния: Один дополнительный виртуальный вызов для каждого выходящего состояния, еслиперед переходом имеется более одного активного состояния листа. Следует также отметить, что в наихудшем случае время отправки события умножается в присутствии ортогональных состояний. Например, если два ортогональных состояния листьев добавлены в заданную конфигурацию состояния, время в худшем случае утроится
Пересмотрено03 Декабря 200603 December, 2006[ORIG_END] -->
