Interview : function pointers vs switch case

7
votes

During my Interview, I was asked to implement a state machine for a system having 100 states where each state in turn has 100 events, I answered 3 following approaches:

  • if-else
  • switch-case
  • function pointers

If-else is obviously not suited for such a state machine, hence main comparison was between switch-case vs function pointers, here is the comparison as per my understanding:

  • Speed wise both are almost same.
  • Switch-case is less modular than function-pointers
  • Function-pointers has more memory overhead.

Could someone confirm if above understanding is correct ?

3
cswitch-statementfunction-pointersstate-machine
Function pointers seems the only valid approach in this case. Yes, it's overhead in speed of access, but it's a modular and flexible solution. - Dmytro Sirenko
I cannot imagine hard coding 100 states, I would rather like to add them at initialisation to some state machine. This avoids 10-screens-long if-else/switch-case ladder and makes the testing and modification much easier - Jakub M.
Not sure whether that would satisfy the interviewer, but on the job I'd just use Ragel. You get blazing speed (eg. goto based) and easier debugging (Ragel can dump the state transition graph into dot format to consume by Graphviz). - unthought
Thanks for metioning Ragel, dude, it looks really awesome! - kralyk

3 Answers

1
votes

There might be a variant of the function pointer approach: a struct which includes a function pointer as well as other information. So you could let one function handle several cases.

Beside of this, I think you are right. Plus, I would consider the overhead concerning memory and speed worth to be considered, but hopefully small enough to be ignored at the end.

0
votes

I don't know what your interviewers wanted to hear and I hope this is not too off topic but if I were interviewing someone I would give points for knowing of the pros and cons of existing frameworks before justifying rolling your own, especially at that scale.

C++ alternatives (if you can use them, thanks to glglgl for pointing out that you seem to want C) would be:

Boost.MSM although blazingly fast is out of the question at that scale. Reasons are compile time, mpl::vector/list constraints and because you would have one gigantic source file.

Boost.Statecharts can work with 100 states but 100 events per state would max out the mpl::vector/list constraints. Personally if I had 100 events in a state I would try to group them anyway and use custom reactions but that obviously depends on the application.

I don't see any reason why Qt's state machine wouldn't scale that big (please correct me if I'm wrong) but its orders of magnitude slower so I never use it.

The only good C alternative I know of is:

QP which is available in C and C++ and can scale that big, has good organization and is "more than a state-machine" in that it handles event queues, concurrency and memory management etc. Rolling your own may yield better performance (depending on your skill and how much time you put into it) but it should be noted that the memory management of the events is probably going to end up needing more optimization than the state machine implementation it's self. QP does this for you and quite well.

0
votes

You could specify more detail about your states and events. Assume your state is continuous integer number. Then you can

  1. Write a table to contain all states and per state handler function on it. When receiving an event, reference this table and call corresponding handler function.

  2. For each state, write a table that contain all events and its event handler function. Look up this table when processing event on the state.

The time complexity of these 2 table looking up is O(1), and space complexity is O(m*n)

However, how can you have FSM with 100 states and event with 100 types? I suggest you to simplify your FSM design and the 1~100 number may be parameter of one particular event.