Boost logo

Boost :

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2005-03-12 09:25:33

Jonathan Turkanis wrote:
>> Do I really say this? I don't see any place where I say or imply that
>> something can't be done because *I* couldn't think of a solution.
> Of course not. Otherwise I wouldn't have had to make up the obviously
> fake quote. Consider: "Quite a bit of effort has gone into making the
> library fast for small simple machines and scaleable at the same time
> ... the scalability does not come for free." I naturally assumed it
> was your effort you were talking about.

Yes, but I don't see how one can *imply* from the above that it can't be
done because *I* haven't found ways to do it. Anyway, this is rather OT
and I won't argue any more about this.

> I'm just arguing that the Rationale doesn't adequately explain why
> better performance is not possible. I'm willing to be convinced that
> it isn't possible, and that you've made the best possible effort to
> find more efficient alternatives.

Define best possible effort. How much time do you think should I spend
on this?

>>> - Two-dimensional array of function pointers. This explanation makes
>>> no sense to me, even as supplemented by Andreas's reply to Iain
>>> Hanson this morning. It's common for a composite component to make
>>> use of several components implemented in different TUs. For
>>> instance, the composite commonent may "know about" the other
>>> components by derivation, by containment, typelists, etc. When it
>>> needs to assemble the array of pointers, it can simply ask each of
>>> them for their contribution.
>> No, in a nutshell it cannot because it doesn't know how many or what
>> components exist.
> I'm not talking about the proposed library here.

Neither do I, I'm talking about any library satisfying the 9

> I accept that it's
> not possible in your implementation.


>> Of course, there must be links between the
>> components
>> but C++ does not allow you to follow these links in a useful way and
>> there is no way to force the components in the TUs to register
>> themselves. The only way you can guarantee the registration is by
>> requiring the programmer to register all the parts explicitly, which
>> is contrary to the scalability requirements.
> You frequently mention "manually registering" components. It would be
> helpful if you would explain what you mean by this. For example, a
> speciailization of std::pair has two components, first_type and
> second_type. When I write
> typedef std::pair<int, float> pair_type;
> does this count as "manually registering" the components of
> pair_type, since I have to know what they are and write them down?

I'm inclined to answer yes but I'm not sure whether this example isn't
too far from what we're currently discussing.

> Lots of C++ libraries allow users to construct composite components
> out of components defined in different TUs.

I think it is worth noting that "usual" C++ components consist of a
declaration and a definition. In the example above, if int and float
were user-defined types (classes), you'd need to include their header
files. In the context of this discussion this does *not* count as
multiple TUs. That's because I don't see how such a separation is
useful/feasible for states (as always: suggestions are welcome), i.e.
state declaration and definition are more or less ineviatbly in one

> I'm not trying to be
> stubborn; I really don't understand why FSM is special in this regard.

See above.

>> Looking at the code above we notice several things:
>> 1. Visibility: In the proposed FSM lib, an outer state "knows" only
>> its inner initial state (which can be an incomplete type) but none
>> of its other inner states (Active does not know that Running exists,
>> neither
>> does StopWatch). An inner state knows all its outer states. Now, that
>> it is done this way and not the other way round (outer states know
>> all their inner states but inner states don't know their outer
>> states) is
>> not a coincidence for the simple reason that the other way wouldn't
>> leave any room for parts in multiple TUs. I also think this is pretty
>> much the only sensible way how you can spread an FSM over multiple
>> TUs. I can't prove this (for me this is just obvious).
> Here you've come quite close to saying: "The requirements are X; I
> tried hard to satisfy X ...but I couldn't; therefore, it can't be
> done."

Define "quite close". I'm saying that *I* don't see other ways (you're
welcome to show such a way). I'm am *not* saying that it can't be done.
As mentioned above, I don't think such word games are very productive. I
won't argue any longer about this.

>> So, if you have any
>> objections be sure to attach a proposal on how you would select the
>> visibility to enable spreading over multiple TUs.
> Please -- I acknowledged at the beginning of my review that I hadn't
> had time to thoroughly examine the implementation and suggest
> improvements.

The visibility discussion is purely about the interface, it has nothing
to do with the implementation.

> But I do have a little experience in C++, and I wanted
> to point out what I saw as gaps in your rationale.

That's fine with me.

>> 2. Connections: The proposed FSM lib connects the parts at link time,
>> through a call to the react function. This works fine but does leave
>> you
>> with the "problem" that there is no way to have a global view at your
>> FSM, *not* *even* *at* *runtime*. When the FSM still resides inside
>> Stopped you don't have *any* way of knowing that Running even exists.
>> Likewise, when the transition to Running has been made, you cannot
>> possibly know whether there are other states because Running might
>> itself define similar custom_reactions that lead you to other states
>> when the reactions are triggered. Note that the custom reaction
>> cannot possibly have any knowledge about the target state as you
>> then can no longer hide Running in a separate TU.
> Here you're just describing your particular implementation.


>> Now, let us consider other possibilities how Running could be
>> connected
>> to Stopped (I'm neither assuming a particular lib interface nor a
>> particular lib implementation, the only thing that I assume is that
>> we have an FSM employing a hypothetical lib with the same states
>> Active, Stopped, Running spread over the TUs Running.cpp and
>> Main.cpp):
> Good, now you're going to consider alternatives.

It seems you haven't noticed that I did that in the Visibility
discussion too.

>> a) At compile time only: I don't see how that could work: Running.cpp
>> does not have any knowledge about Main.cpp and vice versa.
> As far as I'm concerned, you've just dismissed this out of hand
> because you can't see how to do it.

NO, I haven't dismissed that possiblity I've just stated a fact, namely
that *I* don't see how it could work. This also falls into the word
games category and I won't argue any more about this.

> Possibly the joints between parts of machines defined in separate TUs
> must be weaker (i.e., less known at compile time) than the
> connections between collections of states implemented in a single TU.

Yes, that occurred to me also. I don't see how I can make the link
weaker without sacrificing static checking (or other requirements). And
please: I'm NOT dismissing that possibility and concrete suggestions are
always *very* welcome.

>> b) At runtime only: State definition could contain a static instance
>> of a class, which, in its constructor, registers the state with its
>> outer state.
> This is well-known not to work, for the reasons you state.
>> c) Any combination of the above: I don't see how that could improve
>> things in any way
> If I was working on the library, I'd try a combination of your
> current technique and a)

Concrete suggestions welcome. Especially interesting would be a proof
that shows either of the following:
a) Different TUs can share (read/write) information at compile time
b) If a) isn't possible, how link-time connections can be "improved" by
CT information available from a single TU

I hope we agree that proving a) or b) is a lot less work than proving
that it can't be done.

>> 3. State-local storage: Consider what we need to do if we want to
>> give Running a new auxilary state variable, e.g. the startTime_
>> mentioned
>> in the tutorial. Because Running has its own storage, we can simply
>> add a member to its class and are done. We don't need to change
>> Active or
>> the StopWatch.
>> If the proposed FSM lib wouldn't provide storage for each state, it
>> would force people to change the state_machine each time they need to
>> introduce such a variable (or at least once when they introduce the
>> first variable).
> I never said you should omit state-local storage.

Agreed. I added this discussion because you are dissatisfied with the
overall performance and I think that state-local storage is usually the
main perf bottleneck.

>> Point 1 & 2 limit the maximum possible dispatch performance, more on
>> that later.
>> Point 3 limits the maximum possible transition performance, which
>> will typically be the main performance bottleneck.
>>> If there are order of initialization problems, the arrays can be
>>> allocated on first use.
>> No, that is not an option. Unless the allocation and the filling of
>> the array always take considerably less time than the reaction
>> itself, this would prohibit the use of such an FSM lib in real-time
>> applications. In real-time applications you mostly cannot afford to
>> do such lazy
>> init stuff, because that would raise the upper limit of the reaction
>> time to often unacceptable levels.
> You snipped the context.

The context is irrelevant, see below.

> Jonathan Turkanis wrote:
>> When it needs to assemble
>> the array of pointers, it can simply ask each of them for their
>> contribution. If there are order of initialization problems, the
>> arrays can be allocated on first use.
> The first use would be when the machine is constructing the table of
> pointers, which would presumably be when it is constructed or
> immediately after it is started.

How does the machine construct the the table of pointers when it doesn't
know how the full FSM layout looks like?

>>> In my experience, C++ provides extremely fine-grained control over
>>> which parts of a computation are performed at compile time and which
>>> at runtime. I have a strong suspicion that a FSM library could be
>>> written which satisfies the nine requirements and also provides
>>> ruthless efficiencies, at least in many common cases.
>> I believe a library satisfying the 9 requirements can at best provide
>> O(n) dispatch for an FSM using all the features, where n is the
>> number of currently active orthogonal regions. So, if you don't use
>> orthogonal states you get constant time dispatch. The reason lies in
>> the fact that, as I hope I have shown above,
> Sorry, but no.

Too bad, it's the best I can do. As I said, it is much more difficult to
prove that a certain design is the best possible than showing with a
concrete proposal that an improvement is possible. I for one don't think
that spending any more effort on the former is justified.

>> you cannot know how your
>> whole FSM looks. Dispatch must always begin with a currently active
>> innermost state and consider its reactions first. Only if there is no
>> suitable reaction for the innermost state, the next outer state can
>> be considered and so on until an outermost state is reached. Now,
>> since the innermost state knows all its outer states at compile time,
>> it could collapse all the reactions of the outer states into a single
>> STT, yielding constant time lookup for each innermost state
>> *separately*. Hence, if there are n innermost states active at the
>> same time you have O(n) lookup. In any case I don't expect dispatch
>> to be the main performance bottleneck in a typical FSM, see above.
>>> It may turn out
>>> to be necessary to sacrifice performance for some FSMs, but I
>>> believe I hybrid approach may be possible which uses fast dispatch
>>> in the majority of cases. I'm willing to be convinced that it is
>>> impossible, but I haven't seen a satisfying explanation yet.
>> A hybrid approach could indeed be possible, but I don't think it can
>> be done without requiring help from the user (i.e. complicating the
>> interface) or constraining the functionality.
> Have you tried?

No, because my instincts say the opposite of what yours say.

> My instinct says it can be done.

Suggestions welcome.

>> For example you could
>> require the user to somehow (at CT or RT) register all the possible
>> states of a machine or you could prohibit custom_reactions (i.e.
>> require the implementation of the whole FSM in one TU).
> Again, I don't know what you mean by "registering all possible
> states". If it just means listing them in a typelist, for instance, I

Yes, that is one possibility.

> don't see why this can't be done separately for each TU that contains
> part of the state machine implementation. The definition of the whole
> machine doesn't necessarily have to enumerate all the states.

You seem to be ignoring orthogonal states.

> And I'm not suggesting you prohibit custom reactions.


>> Both would
>> give you O(1) lookup. But let's not forget that lookup is typically
>> not the main performance bottleneck! Neither of these measures would
>> speed up transition execution.
> As far I can see, you have not explained why state local storage is
> expensive, even in your implementation. Is it dynamic allocation?


> Why
> not construct small states into a properly aligned buffer?

You can do that with the current version by overloading operator new of
each state.
Construction is inefficient because that involves various book-keeping
tasks. I think it is best if you have a look at the code.

>> Transition execution can only be sped up by prohibiting state-local
>> storage, i.e. by further constraining the functionality.
>> "Why not?"
>> you might ask.
> Of course.
>> It seems that this can only be done if you complicate
>> the interface for everyone, including the users who need the full
>> functionality. A user requiring state- local storage would be forced
>> to somehow associate a state idenitifier with a type, which she can
>> then use as a container to hold the auxillary variables.
> I can't see why this would be necessary. Honestly, I really don't
> understand what you're talking about here. As I said at the beginning
> I accept the requirements, including state local storage.

See above, because it is the main performance hog.

>> I guess here probably lies our main disagreement: For me the users
>> requiring the full functionality have the priority. Why? Because I
>> think that in a certain class of applications most non-trivial FSMs
>> will hugely benefit from state-local storage (at least some users
>> have confirmed that).
> Nothing I said in my review implied that you should sacrifice
> features for performance; all I want is a detailed explanation why
> this would be necessary.

Ok, it was just a guess.

> Others have suggested that the library might be accepted but renamed
> to indicate that it did not pretend to be the definitive C++
> implementation of FSMs. For instance, the proposed library would be
> "Boost.UMLStatecharts," while a separate library might cover faster
> state machines with fewer features.
> I'm against this unless it can be shown that the better perfomance
> can only be obtained by sacrificing functionality. I want to emphase
> again that I phrased my review as an objection to the Rationale
> section of the documentation.

As I said, I can't explain it any better than I already did. This
doesn't mean that I won't answer questions.
I have to accept the consequences.

>> To conclude the above:
>> 2. I agree that it is theoretically possible to implement a hybrid
>> library that supports both classes, but *only* at the cost of a much
>> more complex interface *and* a much more complex implementation. I
>> would even go as far as saying that two separate libraries optimized
>> for each class would have very little in common (interface or
>> implementation). I don't see any benefits in a hybrid approach other
>> than being able to say: "This is *the* solution for all your FSM
>> problems". And it could very well turn out that the hybrid interface
>> is so complex that users would not consider using it.
> My guess is that a smooth interface might be possible.

A concrete proposal is welcome.

>>> - The restriction on event deferral -- one must pass an event
>>> pointed to by an instance of intrusive_ptr -- is extremely
>>> inelegant:
>>> int main()
>>> {
>>> myMachine.process_event(
>>> *boost::intrusive_ptr<Event>( new Event() )
>>> );
>>> }
>>> I'm sure there is a good reason for this restriction, but there must
>>> be a cleaner way to accomplish the same thing.
>> Have you read the rationale for this?
>> (Limitations, Deferring and posting events)
> You don't explain why a pointer to a dynamically allocated event
> can't be passed.

I could offer such an interface, but that would leave users guessing who
will be deleting the event after consumption.

>>> - I don't understand why it is necessary to pass a type as a
>>> length-one mpl::list simply because it is a class template
>>> instantiation. The docs say it is "due to some template-related
>>> implementation details", but this sounds fishy to me.
>> This is the example in the docs:
>> struct NotShooting : fsm::simple_state< NotShooting, Camera,
>> /* ... */, mpl::list< fsm::deep_history< Idle > >,
>> fsm::has_deep_history >
>> {
>> // ...
>> };
>> Internally, I use mpl::is_sequence to find out whether we already
>> have a list of inner initial states. If there's none I need to make
>> such a list. At the point of definition of NotShooting, Idle is an
>> incomplete type. Now the problem is that mpl::is_sequence triggers an
>> instantiation of the deep_history template and I have not found a way
>> how I can prevent access to Idle inside that template. When you wrap
>> that in a list the deep_history template is not instantiated and Idle
>> is not accessed. I'm sure there is a solution but the problem simply
>> never made it to the top of my to-do list.
> Perhaps you could automatically wrap the template argument at that
> position in a sequence-wrapper which turns most types into length-one
> sequences but is specialized for mpl::list to pass through the
> intrinsic operations.

That might work, yes.


Andreas Huber
When replying by private email, please remove the words spam and trap
from the address shown in the header. 

Boost list run by bdawes at, gregod at, cpdaniel at, john at