Jonathan Turkanis wrote:

...

http://article.gmane.org/gmane.comp.lib.boost.devel/119246

Sorry I missed this. I think I missed the whole message.

...

Let me know whether that's convincing or not.

Okay. Let me see if I understand you correctly:

Andreas Huber wrote:

...

... What I want to say here is that it is a bad idea to use this library for parsing, as it is so general that performance tradeoffs are inevitable.

This seems to be a restatement of the performance vs. scalability part of the rationale, correct?

Yes.

...

For parsing, one is much better off with a parser framework, which is optimized for the task.

...

The IMO important observation is the following: Parsers like Spirit only need to return when they have finished processing all "events" (characters). An FSM however must return after processing each event. can exploit this fact and store state with recursive calls, which is of course much faster (some stuff can even be inlined) than any super-clever double-dispatch scheme. There is often a hard limit for stack space which - I think - is the reason why FSMs do make sense in parsers nevertheless.

Here are you talking about any FSM framework or about your library in particular?

I'm talking about any FSM framework.

At any rate, I don't understand why recursion is more efficient.

Recursion can be implemented with simple (non-virtual) function calls. Moreover, if recursion depth is known at compile time, you can inline such calls. I believe double-dispatch needs at least one indirection (virtual call, function pointer, whatever). I might be wrong.

In the case I mentioned -- non-blocking filters -- there is a strong resemblence with FSMs because the filter may be interrupted at any point during its processing if input is temporarily unavailable or if output buffers are full. Filter writers must categorize the various points at which the filtering algorithm might be interupted and save this information so that when processing begins again the algorithm can continue correctly. These categories correspond to states. Furthermore, there is often auxilliary information that must be stored; e.g., if a filter was interupted after it had consumed a character but before it could pass it downstream, the character must be stored together with the state. This auxilliary information varies from state to state; it would therefore seem to correspond to state-local storage.

Ok.

...

However, all the FSM-employing parsers I know are of the dynamic variant (e.g. regex) and these FSMs are not directly designed by humans but computed by an algorithm.

I don't see the relevance of this.

It's a real-world data point that supports (only weakly, admittedly) my view that you not normally implement parsers-FSMs manually but you use a tool to do that for you.

...

Last but not least I think it would be tedious for a human to implement a parser on the state- level

It's also tedious to write a non-blocking filter by hand; being able to use FSMs could help bring some order to the chaos.

I can't really comment on this, I'm not knowledgeable about these things. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Andreas Huber wrote:

...

* Introduction. The nine requirements are well-stated, and I accept them.

Good. That's a start.

[snip]

...

* Speed versus scalability tradeoffs.

...

In order to accept this performance gap I would need a very convincing explanation. Instead, the explanation seems to be of this form: "The requirements are X; I tried hard to satisfy X without compromising performance, but I couldn't; therefore, it can't be done."

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. 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.

...

- 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. 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? Lots of C++ libraries allow users to construct composite components out of components defined in different TUs. I'm not trying to be stubborn; I really don't understand why FSM is special in this regard.

I can only show this with an example:

<snip detailed example>

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."

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. But I do have a little experience in C++, and I wanted to point out what I saw as gaps in your rationale.

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.

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. 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.

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)

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.

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. 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.

...

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.

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? My instinct says it can be done.

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 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. 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?

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.

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. 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.

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.

...

- 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?

http://tinyurl.com/6xbo2 (Limitations, Deferring and posting events)

You don't explain why a pointer to a dynamically allocated event can't be passed. Even if there is a reason this can't be done, there's got to be a better way than having users write *boost::intrusive_ptr<Event>( new Event() ) Was this just a toy example? What would a real-word use look like?

...

- The procedure for posting events from inside entry actions looks messy; this is noted in the docs, and it's not nearly as bad as the syntax for event deferral, but I'd like to see it improved.

I don't see how. Suggestions welcome.

Okay.

...

- 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.

...

I ran the regression tests on seven compilers, with the following results:

1. VC7.1 -- passed all tests 2. VC8.0 -- passed all tests 3. VC7.0 -- ...failed updating 36 targets.. ...skipped 144 targets... ...updated 506 targets... 4. GCC 3.4.1 (Cygwin) -- passed all tests 4. GCC 3.2 (MinGW) -- passed all tests 5. Intel 8.0 ...failed updating 4 targets... ...skipped 4 targets... ...updated 678 targets... 6. CW 8.3 ...failed updating 28 targets... ...skipped 112 targets... ...updated 546 targets... 7. Borland 5.6.4 ...failed updating 36 targets... ...skipped 144 targets... ...updated 506 targets...

I'd be happy to send the full error messages.

Please do, thanks for the testing!

Okay, I will. Jonathan

Hi Andreas, Instead of replying point by point, let me summarize your message and reply in general. 1. My one sentence summary of your rationale was unfair 2. If I object to part of your library I should offer a concrete proposal to fix it 3. If I want to understand where the performance bottlenecks are, I should examine the code. I'm still not sure what part of my summary was wrong, but I'm sorry I offended you. What I would like to see in the rationale is a comparison of a small handful (2-5) of alternate implementation technique, either approaches taken by other libraries or approaches you tried yourself early in development, together with an explanation of why they fail to satisfy the requirements. I realize you do mention some other frameworks, but you don't sketch their design/implementation or show how they fail to satisfy the requirements. Furthermore, readers wishing to understand the performance limitations of your library should not have to be told to examine the code. You should provide a section giving a fairly detailed presentation of the implementation, explaining where the performance problems arise. Andreas Huber wrote:

Jonathan Turkanis wrote:

...

Andreas Huber wrote:

...

Jonathan Turkanis wrote:

...

...

...

- The restriction on event deferral -- one must pass an event pointed to by an instance of intrusive_ptr -- is extremely inelegant:

...

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.

Jonathan

Andreas Huber wrote:

Jonathan Turkanis wrote:

...

2. If I object to part of your library I should offer a concrete proposal to fix it

Either that or prototypes of techniques of which I said I can't see how they will work. I said that because I have invested considerable time in discussing things that might come to mind when one wants to improve performance. I can't think of much else I can say in support of the current design performance-wise. So I thought it would be more productive if you or anyone else could make concrete proposals. Such a proposal would either send me back to the drawing board or I would need to argue convincingly why it doesn't work.

I've read the documentation and most if not all of the review discussion, and still I do not find your explanations satisfying. It's very tempting to try to design an FSM library with better performance characteristics, but I don't have anywhere near enough time, esp. because I'd have to start out by becoming an FSM expert. I don't think I should have to do this before writing a review.

...

3. If I want to understand where the performance bottlenecks are, I should examine the code.

No, I didn't mean that in the generality your summary suggests. In *one* *specific* case I thought it is better if *you* (Jonathan) look at the code before I explain all the details in text. I did that because I *assumed* (maybe wrongly) that you want a very detailed description for which I really don't have the time at the moment.

But this one specific case -- the expense of implementing state local storage -- forms the basis for your argument that dispatch time is not so important, right? Jonathan

Andreas Huber wrote:

...

I've read the documentation and most if not all of the review discussion, and still I do not find your explanations satisfying.

It helps if you explain exactly what you don't find satisfying, see below.

Of course. I was just summarizing my previous messages.

...

It's very tempting to try to design an FSM library with better performance characteristics, but I don't have anywhere near enough time, esp. because I'd have to start out by becoming an FSM expert. I don't think I should have to do this before writing a review.

Certainly not. However, I do expect that people questioning the performance (and along with it the implementation) are able to ask concrete questions why some things are the way they are. You partially did that in your previous posts but only partially.

I think it is difficult to respond to statements like:

<quote> 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. </quote>

Why should it be easy to respond? What I found shocking in your documentation was the statement that hand-written machines can be much faster than framework-generated machines. To accept a library with such poor performance (even if it is adequate in many cases) requires a very convincing justification, which I believe is obviously absent from the documentation. As a reviewer, I could have done my job simply by pointing to the absence of justification, and left it at that. (This is similar to a motion for summary judgment by the defense in an American trial: if the plaintiff hasn't presented evidence, you just point out that fact and you're done.) All my other vague suggestions were attempts to suggest either (i) how the library could have been redesigned to yield better performance or (ii) how you might have documented the impossibility of achieving better performance given your requirements. I'm aware they were not fully fleshed-out proposals. I was hoping you would try to meet me half-way, by trying to figure out what I was getting at and explaing why it wouldn't work. At the very least, you could have asked me what I meant.

As I said before, I think it is close to impossible to prove that a certain design is the best performance-wise. Also, I don't claim that there isn't any room in the current implementation for improvements, rather I think it has reached a stage where substantial (>= 2x faster) optimizations are non-trivial. I can only describe why common optimizations don't work or why they would violate one ore more of the requirements.

All I wanted is a succint description of the various known approaches to implementing FSMs -- including existing frameworks and stuff you tried in the early stages of developing your framework -- together with an explanation of the performance tradeoffs.

Things that I *consciously* avoided or unsuccessfully tried are described in the rationale.

If all the things you unsuccessfully tried are described in the rationale, then you didn't try very much. I was giving you the beneift of the doubt by assuming you had omitted describing your alternate designs.

Moreover, during any programmer career a bag of knowledge is acquired that is unconsciously applied to every programming job. Naturally, this bag of knowledge is not the same for everyone

This is obviously true.

which is probably the main reason why the rationale seems to be sufficient for some people while others find it unsatisfying.

This is just funny. People who find your rationale satisfying could be people who don't care about performance as long as it's good enough for their application or people who failed to consider the same design alternatives you failed to consider.

Ergo, the only thing I can do is listen to the questions people ask and either add explanations to the rationale or change the implementation.

...

...

...

3. If I want to understand where the performance bottlenecks are, I should examine the code.

No, I didn't mean that in the generality your summary suggests. In *one* *specific* case I thought it is better if *you* (Jonathan) look at the code before I explain all the details in text. I did that because I *assumed* (maybe wrongly) that you want a very detailed description for which I really don't have the time at the moment.

But this one specific case -- the expense of implementing state local storage -- forms the basis for your argument that dispatch time is not so important, right?

Right. Here's a description of the relevant parts of the implementation:

<snip detailed description> This sort of stuff should be in the docs. Jonathan

David Abrahams wrote:

"Jonathan Turkanis" <technews@kangaroologic.com> writes:

...

All I wanted is a succint description of the various known approaches to implementing FSMs -- including existing frameworks and stuff you tried in the early stages of developing your framework -- together with an explanation of the performance tradeoffs.

That does seem like a reasonable request. Rationales and comparisons with alternate designs are very important in Boost documentation.

FWIW, I also think such a request is reasonable. I questioned the expectations Jonathan seems to have regarding such documentation. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Andreas Huber wrote:

Jonathan Turkanis wrote:

...

Andreas Huber wrote:

...

I think it is difficult to respond to statements like:

<quote> 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. </quote>

Why should it be easy to respond?

I'm not saying responding should be easy. My point was that such statements are not likely to bring up useful answers.

Since you apparently don't know what I was suggesting, and you didn't bother to ask, I don't see how you can say this.

...

What I found shocking in your documentation was the statement that hand-written machines can be much faster than framework-generated machines.

One could probably produce an equally shocking case for just about any non-trivial library out there. My "mistake" was to measure it and publish the numbers.

This is ridiculous. Consider, for example, the iterators library, or Andrei and Dave's smart pointer library. If incrementing an iterator constructed using the framework could take up to twenty times as long as incrementing a hand-written iterator, or if copying a framework-generated smart pointer was twenty times as expensive as copying a hand-written smart pointer, these libraries would be dead in the water. A case closer to home is the iostreams library. I conducted measurements showing that a stringstream constructed using the library was essentially indistinguishable from Dinkumware stringstream, and that a library-generated fstream was slightly faster (See http://lists.boost.org/MailArchives/boost/msg71285.php for caveats) I couldn't honestly recommend that somebody use a library-generated socket_stream, say, if it would involve any significant slowdown.

...

To accept a library with such poor performance (even if it is adequate in many cases) requires a very convincing justification, which I believe is obviously absent from the documentation.

That became sufficiently apparent during the review. My hope was that people would understand that the provided functionality must have a significant overhead. I was obviously wrong and there will be better documentation in this direction.

...

As a reviewer, I could have done my job simply by pointing to the absence of justification, and left it at that.

Fortunately, there are many other things that matter in a review.

My objection to your library was based on a deficiency in the rationale. I don't know if this deficiency could be remedied without exposing fundamental problems in your library. The only way to find out would be to try to fix it.

...

(This is similar to a motion for summary judgment by the defense in an American trial: if the plaintiff hasn't presented evidence, you just point out that fact and you're done.)

This seems to imply that in a review the library author is the plaintiff and the reviewers are the defendants.

Yes. Metaphorically, of course.

I don't think the roles in a review regarding evidence are usually as clear-cut as they are in a trial.

Hah! You should read a few trial transcripts. But we digress.

...

All my other vague suggestions were attempts to suggest either (i) how the library could have been redesigned to yield better performance or (ii) how you might have documented the impossibility of achieving better performance given your requirements.

This is exactly something that I don't think I will ever be able to prove. I can only provide evidence that hints in this direction. New C++ techniques and idioms are discovered almost on a monthly basis and there's always the possibility that such a technique enables a much better implementation (e.g. I wouldn't have imagined that it is possible to enumerate overloads like Alexander does or I couldn't possibly have conceived the technique that makes possible the FOREACH macro). I think it is close to impossible for an individual to be proficient in all the currently known techniques, not to mention the ones that have yet to be discovered.

Okay, I shouldn't have said "impossibility"; maybe "impossibility, using known methods" or "unliklihood, using known methods" would have been more accurate. But seriously, you must know that I'm not insisting you prove that you're library could not possibly be improved by yet-to-be-discovered-techniques.

...

I'm aware they were not fully fleshed-out proposals. I was hoping you would try to meet me half-way, by trying to figure out what I was getting at and explaing why it wouldn't work.

... which I did in the cases where I could imagine candidate solutions. I the cases where I couldn't see one I said so. Since the latter usually didn't lead to a follow-up on your part I assumed that you don't have a solution either. There's no meeting half-way in such a situation.

This is getting very vague.

...

...

Things that I *consciously* avoided or unsuccessfully tried are described in the rationale.

If all the things you unsuccessfully tried are described in the rationale, then you didn't try very much. I was giving you the beneift of the doubt by assuming you had omitted describing your alternate designs.

What else should I have tried?

Normally, in designing a framework one considers a small handful (say two to six) of alternate designs which view the subject matter from completely different perspectives. In your case, what were those alternate designs?

...

...

Moreover, during any programmer career a bag of knowledge is acquired that is unconsciously applied to every programming job. Naturally, this bag of knowledge is not the same for everyone

This is obviously true.

...

which is probably the main reason why the rationale seems to be sufficient for some people while others find it unsatisfying.

This is just funny. People who find your rationale satisfying could be people who don't care about performance as long as it's good enough for their application or people who failed to consider the same design alternatives you failed to consider.

Which alternatives did I fail to consider?

Note the subjunctive mood. Let me make one last attempt to explain what should be in the rationale. Look at section 16.2 of "The C++ Programming Language", 3d ed. Here Stroustrup gives two design criteria for a containers library, and then discusses three designs: "Specialized containers and iterators" - satisfies the first criterion "Based Containers" - satisfies the second criterion "STL" - satifies both criteria I'm not suggesting that you give such a detailed treatement as Stroustrup. However, if you were to give a similar overview of the landscape of possible FSM frameworks, and thoughtfully discuss the tradeoffs in flexibility and performace which each involves, reviewers might have some confidence that you are aware of the techniques which might be used to construct a fast, flexible FSM framework, and have carefully considered the design. This type of overview would probably be a useful component of any library's documentation; in your case it is made absolutely essential by the performance figures you cite. Jonathan

Jonathan Turkanis wrote:

Andreas Huber wrote:

...

Jonathan Turkanis wrote:

...

Andreas Huber wrote:

...

I think it is difficult to respond to statements like:

<quote> 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. </quote>

Why should it be easy to respond?

I'm not saying responding should be easy. My point was that such statements are not likely to bring up useful answers.

Since you apparently don't know what I was suggesting, and you didn't bother to ask, I don't see how you can say this.

I believe I know very well what you were suggesting and I think - please correct me if I'm wrong - that should be apparent from my answer to the quote above: <answer> 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. </answer> I assume that you would have followed up on that had my answer shown any signs of misunderstanding. You didn't.

...

...

What I found shocking in your documentation was the statement that hand-written machines can be much faster than framework-generated machines.

One could probably produce an equally shocking case for just about any non-trivial library out there. My "mistake" was to measure it and publish the numbers.

This is ridiculous. Consider, for example, the iterators library, or Andrei and Dave's smart pointer library. If incrementing an iterator constructed using the framework could take up to twenty times as long as incrementing a hand-written iterator, or if copying a framework-generated smart pointer was twenty times as expensive as copying a hand-written smart pointer, these libraries would be dead in the water.

A much more adequate comparison would be measuring dumb C++ pointers vs. reference-counted smart pointers. IIRC, the overhead for copying was way beyond a few percentage points for shared_ptr. [snip]

...

...

As a reviewer, I could have done my job simply by pointing to the absence of justification, and left it at that.

Fortunately, there are many other things that matter in a review.

My objection to your library was based on a deficiency in the rationale. I don't know if this deficiency could be remedied without exposing fundamental problems in your library. The only way to find out would be to try to fix it.

Fix the documentation or the library? [snip]

Hah! You should read a few trial transcripts. But we digress.

Indeed.

...

...

All my other vague suggestions were attempts to suggest either (i) how the library could have been redesigned to yield better performance or (ii) how you might have documented the impossibility of achieving better performance given your requirements.

This is exactly something that I don't think I will ever be able to prove. I can only provide evidence that hints in this direction. New C++ techniques and idioms are discovered almost on a monthly basis and there's always the possibility that such a technique enables a much better implementation (e.g. I wouldn't have imagined that it is possible to enumerate overloads like Alexander does or I couldn't possibly have conceived the technique that makes possible the FOREACH macro). I think it is close to impossible for an individual to be proficient in all the currently known techniques, not to mention the ones that have yet to be discovered.

Okay, I shouldn't have said "impossibility"; maybe "impossibility, using known methods"

Even that is close to impossible.

or "unliklihood, using known methods"

I would agree if you replaced the last three words with: "using methods known to me and to people who studied the implementation". But I guess that's what you meant anyway.

But seriously, you must know that I'm not insisting you prove that you're library could not possibly be improved by yet-to-be-discovered-techniques.

Given your previous comments I couldn't be sure. To me those comments always had the air that something close to a proof is feasible. I must have misunderstood you.

...

...

I'm aware they were not fully fleshed-out proposals. I was hoping you would try to meet me half-way, by trying to figure out what I was getting at and explaing why it wouldn't work.

... which I did in the cases where I could imagine candidate solutions. I the cases where I couldn't see one I said so. Since the latter usually didn't lead to a follow-up on your part I assumed that you don't have a solution either. There's no meeting half-way in such a situation.

This is getting very vague.

I don't think so, but let's leave it at that then.

...

...

...

Things that I *consciously* avoided or unsuccessfully tried are described in the rationale.

If all the things you unsuccessfully tried are described in the rationale, then you didn't try very much. I was giving you the beneift of the doubt by assuming you had omitted describing your alternate designs.

What else should I have tried?

Normally, in designing a framework one considers a small handful (say two to six) of alternate designs which view the subject matter from completely different perspectives.

I agree with this general statement but I'm still wondering how you came to the conclusion that I haven't tried very much.

In your case, what were those alternate designs?

The documentation contains fairly visible hints that I considered: 1. GOF Visitor 2. Two-dimensional table of function pointers 3. Acyclic visitor Moreover, I also considered: 4. GOF FSM-like implementation (where subclassing is used for substates) 5. Herb Sutters function pointer FSM 6. Alekseys FSM 7. Dave's FSM variants I didn't bother to implement any of these with the exception of 3, because it became very apparent very soon that the other approaches would not satisfy my requirements and that it would be very difficult or impossible to modify them to suit. So, I really tried only one other approach. If you are still of the opinion this is not much I'd be interested in your *concrete* suggestions what else I should have tried.

...

...

...

Moreover, during any programmer career a bag of knowledge is acquired that is unconsciously applied to every programming job. Naturally, this bag of knowledge is not the same for everyone

This is obviously true.

...

which is probably the main reason why the rationale seems to be sufficient for some people while others find it unsatisfying.

This is just funny. People who find your rationale satisfying could be people who don't care about performance as long as it's good enough for their application or people who failed to consider the same design alternatives you failed to consider.

Which alternatives did I fail to consider?

Note the subjunctive mood.

Ah yes, now that you mention it.

Let me make one last attempt to explain what should be in the rationale. Look at section 16.2 of "The C++ Programming Language", 3d ed. Here Stroustrup gives two design criteria for a containers library, and then discusses three designs:

"Specialized containers and iterators" - satisfies the first criterion "Based Containers" - satisfies the second criterion "STL" - satifies both criteria

I'm not suggesting that you give such a detailed treatement as Stroustrup. However, if you were to give a similar overview of the landscape of possible FSM frameworks, and thoughtfully discuss the tradeoffs in flexibility and performace which each involves, reviewers might have some confidence that you are aware of the techniques which might be used to construct a fast, flexible FSM framework, and have carefully considered the design.

I'm not sure how this is relevant (I already agreed to add such documentation). -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Andreas Huber wrote:

Jonathan Turkanis wrote:

I forgot to respond to part of your message.

...

What I would like to see in the rationale is a comparison of a small handful (2-5) of alternate implementation technique, either approaches taken by other libraries or approaches you tried yourself early in development, together with an explanation of why they fail to satisfy the requirements.

That's interesting. I was under the impression that exactly such a list of alternate implementation techniques would not satisfy you, because it would in no way show that the design I chose is the best performance-wise.

Why not? That would be the main point.

And performance was your biggest concern, wasn't it?

Yes. Jonathan

Andreas Huber wrote:

Jonathan Turkanis wrote:

...

Andreas Huber wrote:

...

...

That's interesting. I was under the impression that exactly such a list of alternate implementation techniques would not satisfy you, because it would in no way show that the design I chose is the best performance-wise.

Why not? That would be the main point.

I don't understand. A list of alternate techniques would show that none of these techniques satisfies the requirements but it doesn't say anything why the current FSM implementation performs worse than any of these techniques.

You don't just list the techniques. You explain them and summarize their performance characteristics. Jonathan

Andreas Huber wrote:

Jonathan Turkanis wrote:

...

...

...

...

That's interesting. I was under the impression that exactly such a list of alternate implementation techniques would not satisfy you, because it would in no way show that the design I chose is the best performance-wise.

Why not? That would be the main point.

I don't understand. A list of alternate techniques would show that none of these techniques satisfies the requirements but it doesn't say anything why the current FSM implementation performs worse than any of these techniques.

You don't just list the techniques. You explain them and summarize their performance characteristics.

That's what I meant. This will still not show how "good" the current design is. It will only show that the current design satisfies requirements that other designs don't and explain the techniques (and performance characteristics) I have chosen to satisfy the requirements. Whether those techniques are the best performance-wise is a completely different matter.

I don't understand the destinction you're trying to make. Jonathan

Jonathan Turkanis wrote:

Andreas Huber wrote:

...

Jonathan Turkanis wrote:

...

...

...

...

That's interesting. I was under the impression that exactly such a list of alternate implementation techniques would not satisfy you, because it would in no way show that the design I chose is the best performance-wise.

Why not? That would be the main point.

I don't understand. A list of alternate techniques would show that none of these techniques satisfies the requirements but it doesn't say anything why the current FSM implementation performs worse than any of these techniques.

You don't just list the techniques. You explain them and summarize their performance characteristics.

That's what I meant. This will still not show how "good" the current design is. It will only show that the current design satisfies requirements that other designs don't and explain the techniques (and performance characteristics) I have chosen to satisfy the requirements. Whether those techniques are the best performance-wise is a completely different matter.

I don't understand the destinction you're trying to make.

We've discussed that in the other thread... -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.