Зависимость работы обходчика от порядка сценарных функций

В Таблице 1 показано количество переходов, выполняемое обходчиками для построения обхода графов из раздела 3 при различных упорядочениях сценарных функций. C в этой таблице обозначает операцию создания нового потока, K - уничтожение одного из имеющихся потоков, U - помещение функции в стек обработчиков завершения потока, O - выталкивание функции из этого стека.

Порядок сценарных функций Простой пример (Рис. 2)
Количество состояний - 4.
Количество дуг - 8.Сложный пример (Рис. 3)
Количество состояний - 7.
Количество дуг - 13.

	ndfsm	dfsm	ndfsm	dfsm
CKUO	16	22	31	76
CKOU	16	22	29	76
CUKO	16	25	29	76
CUOK	13	25	27	88
COKU	16	19	30	88
COUK	13	25	27	88
KCUO	16	22	31	68
KCOU	16	22	29	68
KUCO	16	22	30	60
KUOC	16	22	30	60
KOCU	16	22	31	68
KOUC	16	22	31	59
UCKO	16	25	29	64
UCOK	13	25	27	69
UKCO	16	25	29	60
UKOC	16	25	29	60
UOCK	13	25	27	69
UOKC	16	25	31	69
OCKU	16	19	30	88
OCUK	13	25	27	88
OKCU	16	19	30	61
OKUC	16	19	31	55
OUCK	13	25	27	68
OUKC	16	25	31	68

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

Таблица 1 показывает, что, меняя только порядок обращений к сценарным функциям, можно добиться следующего ускорения более 35% для dfsm (сложный пример, сравнение CUOK и OKUC) и более 10% для ndfsm (сложный пример, CKUO и CUOK).

На рассмотренных примерах ndfsm демонстрирует более высокую производительность. Далее мы рассмотрим дополнительные примеры, подтверждающие это.

Содержание раздела