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

Я пытаюсь реализовать конечный автомат на C, и мне нужно, чтобы он был очень быстрым. Поэтому я решил использовать указатели на функции как «состояния»:

void *state1(void){ /* function body here */ }
void *state2(void){ /* ... */ }
void *state3(void){ /* ... */ }

Тогда основной цикл конечного автомата может быть очень простым:

void *(*fp)(void);
fp = state1;

while(fp)
    fp = fp();

Есть вопросы:

1) Можно ли избежать использования указателя void в типах возвращаемых функций? В идеале функции состояния должны иметь определенный тип, чтобы гарантировать, что в FSM будут использоваться только функции с этим типом.

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

Спасибо.


c function-pointers fsm
person John Rivers    schedule 25.06.2012    source источник
comment
Чую микрооптимизацию? Сколько раз в миллисекундах должен работать конечный автомат?   -  person Seva Alekseyev    schedule 25.06.2012
comment
@Seva Alekseyev: некоторые состояния относительно большие и медленные, но некоторые очень маленькие и простые. Производительность не имеет значения, когда конечный автомат находится в одном из больших состояний, но маленькие состояния должны выполняться как можно быстрее.   -  person John Rivers    schedule 25.06.2012
comment
Используйте конечный автомат с горячим кодированием, если хотите, чтобы он был быстрым. Ваши преждевременные оптимизации не имеют большого значения. Лучше писать читаемый, поддерживаемый и расширяемый код, который работает. Также для C ++ - boost.org/doc/libs /1_49_0/libs/statechart/doc/index.html   -  person    schedule 25.06.2012

Ответы (5)


arrow_upward
3
arrow_downward

Чтобы создать определение рекурсивного типа, подобное этому, в C, вам нужно использовать struct где-то в строке, потому что вы не можете «пересылать объявление» typedefs. Например, вы можете заключить указатель на функцию в struct:

struct state {
    struct state (*func)(void);
};

Затем в цикле:

struct state state = { state1 };

while (state.func) {
    state = state.func();
}
person caf    schedule 25.06.2012

arrow_upward
3
arrow_downward

Здесь вы можете найти ответ на свой вопрос: http://code.google.com/p/fwprofile/

Это версия конечного автомата с открытым исходным кодом (GNU GPLv3), реализованная на C. Концепция и реализация хорошо подходят для использования в критически важных приложениях. Есть развертывания в промышленных приложениях.

person Vaclav Cechticky    schedule 12.09.2012

arrow_upward
1
arrow_downward

В C невозможно объявить функцию, которая возвращает указатель на функцию своего собственного типа. Более того, вы не можете использовать void *, потому что C не разрешает преобразование между указателями функций и объектов. Вместо этого вы можете использовать:

typedef void (*generic_func_ptr)(void);
typedef generic_func_ptr (*state_func_ptr)(void);
generic_func_ptr state1(void), state2(void), state3(void);
state_func_ptr fp;

while(fp)
    fp = (state_func_ptr)fp();

Уродливо, но работает. Вместо этого я бы подумал об использовании оператора switch. Это намного чище для реализации конечных автоматов.

person R.. GitHub STOP HELPING ICE    schedule 25.06.2012

arrow_upward
0
arrow_downward

1) typedef void(*state_fp)(void); 

state_fp state1(void) { }

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

person Keith Nicholas    schedule 25.06.2012
comment
Для этого потребуется приведение при возврате, поскольку тип, возвращаемый функцией, не совпадает с типом указателя на саму функцию (он все же лучше, чем OP, поскольку, по крайней мере, вы выполняете приведение из одного типа указателя функции в другой так что это четко определено). - person caf; 25.06.2012

arrow_upward
0
arrow_downward

Если другие хотят использовать бесплатную платформу для fsm, ознакомьтесь с http://www.block-net.de/Programmierung/cpp/fsm/fsm.html Существует среда конечных автоматов C и C ++, включая генератор диаграмм состояний с PlantUML.

person Tom    schedule 09.10.2014