I've been delving into finite state machines and at this time it seems that
the best way to implement them is through an intense use of the goto
statement. Yet, everyone plus their granmother is constantly cursing at the
goto statement, accusing it of being some sort of spawn of satan. So it
seems we have a pickle here.
The thing is, at first thought it seems that there aren't any viable
alternatives which are better suited for this task. Yes, probably the end
result will be an entangled mess but as far as I know a set of nested if
and switch statements will not improve much on the subject.
So, what are your views on this subject? Is the use of goto statements in
this application really the best possible solution to this problem or is it
unjustified and there is some godsend method which I'm missing out on?
Thanks in advance
Rui Maiel
--
Running Kubuntu 6.10 with KDE 3.5.6 and proud of it.
jabber:ru********@jabber.org
Feb 9 '07
67  7287  we******@gmail.com wrote:
Yes, I did have some examples that were not parsable for severe
conditions testing purposes. I'm one of these people who doesn't
think "Undefined Behaviour at the least provocation" is an acceptable
state of affairs.
Alright, I ended up taking it out of the large test file I created (which was
just a concatenation).
I cannot find a copy of Michael B. Allen's version, referenced in this post: http://groups.google.com/group/comp....78074cf0c7861d
Getting a 404 on his provided URL. Do you have a copy of it laying around? we******@gmail.com wrote, On 11/02/07 03:16:
On Feb 10, 6:25 pm, Ian Collins <ian-n...@hotmail.comwrote:
>websn...@gmail.com wrote:
>>On Feb 10, 5:34 pm, Ian Collins <ian-n...@hotmail.comwrote:
websn...@gmail.com wrote:
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
What's wrong with nested switch statements or tables of function
pointers?
Well, nothing if you don't care about performance. You can use bubble
sorts too if you like. Have a blast.
Assuming the branch logic dominates over the state actions, which would
appear to be both a premature and speculative optimisation.
Sure, sometimes 15 clocks doesn't matter. So your per-state
operations needs to be 300-1000 clocks (or about 600 to 3000 pipelined
x86 instructions) before you decide that state transition performance
isn't that important. (Just like bubble sort for 25 elements is
probably good enough.) Of course, its easy to find examples where the
the per-state operations are way less than that (any parser). I can't
think of a single counter example where the state transition is really
high like that off the top of my head though. Perhaps you can?
I've done a few state machines where in each state the software is
collecting information from a number of HW devices and displaying it
with the change of state being on a specific key press. I did not do
timings, but I would be surprised if the minimum possible execution time
for one state was below several thousand clock cycles.
Currently I have a finite state machine implemented in an XML based
language which I have implemented in C where each run of the state
machine is a minimum of 1 minute apart (I was allowed to make it 10
seconds, but since it did not need to be that "fast" I slowed it down to
a more sensible one minute).
I've also done a fair bit or programming on processors without cache
where a conditional branch is either 1 or 3 clock cycles (due to
pipeline break) depending on whether the branch is taken or not, so the
overhead is a lot lower.
>I may well be wrong, I've only ever implemented FSMs (using function
pointers) on CPUs without an instruction cache.
Care to post an example?
In my response to Christopher Layne you have direct examples of two
users implementing "for() switch()" based state machines, and myself
who made a goto dominated state machine implementation. You can go
download those and see for yourself. They complained that my
implementation was obfuscated, because of the gotos, but of course
that was as a cover for the fact that my solution comes out faster
precisely because of this.
So you measured and the performance using gotos was better. It's not a
premature optimisation when you have measurements that say the
performance will be significantly better.
I would have no problem with a decently commented FSM implemented with
gotos where required for performance reasons. I also have no problem
with well commented hairy assembler where required (I've had to do it
myself where C code was measured to be nowhere near fast enough).
--
Flash Gordon
On Feb 10, 7:33 pm, Christopher Layne <cla...@com.anodizedwrote:
websn...@gmail.com wrote:
Yes, I did have some examples that were not parsable for severe
conditions testing purposes. I'm one of these people who doesn't
think "Undefined Behaviour at the least provocation" is an acceptable
state of affairs.
Alright, I ended up taking it out of the large test file I created (which
was just a concatenation).
I cannot find a copy of Michael B. Allen's version, referenced in this
post:
http://groups.google.com/group/comp....frm/thread/4fb...
Getting a 404 on his provided URL. Do you have a copy of it laying around?
Hmm ... no; though it doesn't surprise me that he chucked that code
since it was so bug ridden and slow. I found an update of his general
csv parser here: http://www.ioplex.com/~miallen/libmba/dl/src/csv.c
I don't know if it fits in the same code hoist, however. He's still
making the same performance mistake though (its amazing how
obstinantly stupid people can be about performance.)
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com wrote:
On Feb 10, 5:26 pm, Christopher Layne <cla...@com.anodizedwrote:
websn...@gmail.com wrote:
In the C language? I'm afraid so. The cleaner *LOOKING* solution is
a switch() inside of a for(), but its not *that* much cleaner and it
is a *HELL* of a lot slower.
I know you know your stuff Paul, but don't you think "a hell of a lot
slower" is a bit of an overstatement?
We're talking a single compare here within the switch and then a jump.
And that's not even considering what the compiler might optimize it to in
the long run.
There's not really anything the compiler can do unless its a forever
for (as in for(;;)) and the compiler is willing and able to do some
really serious optimizations for switches (something I have never
seen.)
It's something at least both Intel's compiler and GCC do.
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
>such general statements are, by definition, false
What definition would that be?
see Joe Wright's post ^^
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
>Why analyze the whole program? a label does not have complete program
scope
so you know you got there from within the same function.
True.
Of course, in the *worst* case the whole program is one function.
8-)}
my psychic powers told me you'd say that!
On Sat, 10 Feb 2007 15:54:53 -0800, in comp.lang.c , Keith Thompson
<ks***@mib.orgwrote:
>"Serve Laurijssen" <se*@n.tkwrites:
>"Christopher Layne" <cl****@com.anodizedwrote in message
>>And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
What definition would that be?
The definition contained within the statement. Thats what "by
definition" means.
--
Mark McIntyre
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan we******@gmail.com wrote:
Hmm ... no; though it doesn't surprise me that he chucked that code
since it was so bug ridden and slow. I found an update of his general
csv parser here:
http://www.ioplex.com/~miallen/libmba/dl/src/csv.c
I don't know if it fits in the same code hoist, however. He's still
making the same performance mistake though (its amazing how
obstinantly stupid people can be about performance.)
This code is still using fgetc().
Without his workable code, there's not much one can do. I wrangled it around
to use fread on one huge ass buffer because I wasn't going to refactor his
entire code.
Anyways, in both of your code, the jumping around with gotos, and in his case,
inside the switch isn't even the majority of the cpu bandwidth at all. In
your case, it was where you predicted it "performance critical path here."
Kcachegrind showed 22% or so of instruction fetches resting on just that one
line:
11.33% 178 for (; n < len; n++) { /* Performance critical path is here. */
22.53% 179 if (!charSet[x[n]]) {
In his case, it was obviously on the memset() and getc() taking the majority
of the time. After I took those out of the equation it was the ctype
functions as expected. While trying to make his code do *something*, I got it
to parse in around .900 sec, and yours .800 sec. But I wouldn't put any
weight on that whatsoever - because I cannot verify anything his code is
really doing. Although I know it is sitting inside that switch and changing
state/calling ctype functions/setting variables, etc. for atleast the number
of bytes in the huge file I fed it. In both cases I turned off any kind of
stdio output to reduce it's cpu time.
We really just need his improved code. But from what I can see, the bottleneck
isn't in the switch or gotos. Even with my chopped up version of his code
that was doing some kind of parsing inside the switch cascade, the switch
itself accounted for only around 4%.
"Serve Laurijssen" <se*@n.tkwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
>>such general statements are, by definition, false
What definition would that be?
see Joe Wright's post ^^
I had to go to Google to find it. If you had told me that Joe Wright
had written:
| Bertrand Russell said (among other things)..
| "All generalizations are false, including this one."
it would have saved me some time.
I think Voltaire said it first; it's also been attributed to Mark
Twain.
But in any case, it's an observation, not a definition.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Mark McIntyre <ma**********@spamcop.netwrites:
On Sat, 10 Feb 2007 15:54:53 -0800, in comp.lang.c , Keith Thompson
<ks***@mib.orgwrote:
>>"Serve Laurijssen" <se*@n.tkwrites:
>>"Christopher Layne" <cl****@com.anodizedwrote in message
And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
What definition would that be?
The definition contained within the statement. Thats what "by
definition" means.
I see no definition in the statement. If there is one, what term is
being defined?
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
On Sun, 11 Feb 2007 13:59:28 -0800, in comp.lang.c , Keith Thompson
<ks***@mib.orgwrote:
>Mark McIntyre <ma**********@spamcop.netwrites:
>On Sat, 10 Feb 2007 15:54:53 -0800, in comp.lang.c , Keith Thompson
<ks***@mib.orgwrote:
>>>"Serve Laurijssen" <se*@n.tkwrites:
"Christopher Layne" <cl****@com.anodizedwrote in message
And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
What definition would that be?
The definition contained within the statement. Thats what "by
definition" means.
I see no definition in the statement. If there is one, what term is
being defined?
Ok, I'll play: the statement "the one with unconditional jumps will
end up being faster" is a defintion of the behaviour of unconditional
jumps.
Why are you persisting at this point? I'm sure you knew precisely what
Serve meant, and it seems bizarre.
--
Mark McIntyre
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan
Eric Sosman wrote:
Rui Maciel wrote On 02/09/07 14:47,:
>>Ben Pfaff wrote:
>>>How about a switch statement or an array of function pointers?
As far as I can tell, to use the switch instead of the goto statement would
end up generating a nested mess inside continuous loops. [...]
If there's nothing going on during a state transition except
the transition itself, then switch-in-a-loop has no benefit that
I can see, aside from evading the wrath of the goto police. If
you just change `goto state42' to `state = 42', all you've done
is change the spelling.
However, lots of applications of state machines perform some
additional action at each transition: They consume the next input
character or emit the next output message or something of the
sort. In that setting, switch-in-a-loop is very attractive
because it provides convenient places for the "transitional"
actions, to wit, before and after the big switch block:
for (;;) {
/* "prefix" actions ... */
switch (state) {
...
}
/* "suffix" actions ... */
}
If both "prefix" and "suffix" are empty, though, there
seems little point to this structure.
Very well put, Eric.
Often, for me, the state machine is a subprocess used within a program.
There may be a large processing loop for the program, one item of
which is to call a function to run a particular state machine. In that
case, the state is a static variable. The function does a switch which
processes the state and possibly updates the state, then exits.
--
Thad
Mark McIntyre <ma**********@spamcop.netwrites:
On Sun, 11 Feb 2007 13:59:28 -0800, in comp.lang.c , Keith Thompson
<ks***@mib.orgwrote:
>>Mark McIntyre <ma**********@spamcop.netwrites:
>>On Sat, 10 Feb 2007 15:54:53 -0800, in comp.lang.c , Keith Thompson
<ks***@mib.orgwrote:
"Serve Laurijssen" <se*@n.tkwrites:
[...]
>>>>such general statements are, by definition, false
What definition would that be?
The definition contained within the statement. Thats what "by
definition" means.
I see no definition in the statement. If there is one, what term is
being defined?
Ok, I'll play: the statement "the one with unconditional jumps will
end up being faster" is a defintion of the behaviour of unconditional
jumps.
Why are you persisting at this point? I'm sure you knew precisely what
Serve meant, and it seems bizarre.
I'll just drop this; there's no point in discussing it further.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
On Sat, 10 Feb 2007 17:18:46 -0800, websnarf wrote:
On Feb 9, 8:14 am, Rui Maciel <rui.mac...@gmail.comwrote:
>I've been delving into finite state machines and at this time it seems
that the best way to implement them is through an intense use of the goto
statement. Yet, everyone plus their granmother is constantly cursing at
the goto statement, accusing it of being some sort of spawn of satan. So
it seems we have a pickle here.
Correct. The C language standard itself creates this problem, for
really, no good reason. The simplest way to improve the C standard
for finite state machines is to extend either the continue or goto
statements to be able to go to a specific case label. In that way a
FSM can be implemented inside of a switch statement without paying the
exorbitant cost of rerunning a literal switch operation on every state
transition. This kind of thinking is basically beyond what the C
standards committee is capable of conceiving.
For awhile I got into the practice of pairing switch case's with
equivalently named labels:
struct foo {
struct { enum foo_states this, next; } state;
};
switch (foo->state.this) {
one:
foo->state.this = one;
case one:
...
foo->state.next = two;
do_something_asynchronously(&fsm_callback);
break;
two:
foo->state.this = two;
case two:
...
goto one;
break;
}
Ultimately I stopped and fell back to just using switch. With network
server development most of the switch cases end up initiating some
asynchronous operation which will need to call back into the function, so
the optimization just clutters things up. Though, being able to do `goto
(state.this = two)' would be nice.
Tail call optimization would be even nicer. One my of I/O libraries
implements a type of trampoline, otherwise the stack grows too big. Though
in that case the C compiler would really need to be smart since it's
mutually recursive among many functions.
On Sat, 10 Feb 2007 19:06:14 -0800, websnarf wrote:
<snip>
That's actually a follow up involving Michael B. Allen. (It all
started when he made the ridiculous claim that the C std library could
not be beat in terms of performance on strings.)
This is the original thread that I was thinking of:
http://groups.google.com/group/comp....3b05cfb3818d7/
Ridiculous? Michael's comments echo exactly my experience. I write network
servers day-in and day-out. The standard library functions work great
for strings, memcpy() in particular. snprintf() is also very useful, but
like Michael pointed out I often deal with string parsing in situ, using
FSMs. I've written stateful base64, base16, base32, URL
percent decoders/encoders. Instead of allocating memory willy-nilly, as
much as possible I write all of my code to deal with "strings" terms of
streams, not discrete objects. I've even written a streaming MIME parser.
Actually, if a committee wanted to standardize something they'd be better
off standardizing a vector structure (not unlike the bstring package, just
less distasteful). Like was discussed in the above thread, the problem
with C strings is that everybody and their grandmother has invented some
kind of wrapper which does the same thing using different names.
Personally, of late I often make use of the iovec structure from POSIX's
sys/uio.h. If I were to revamp string handling in C I'd make two modifications.
1) Add an svec structure. struct svec { unsigned char *sv_base;
size_t sv_len; }.
2a) Mandate that (char) was unassigned (very radical), or
2b) Mandate that (char) and (unsigned char) were interchangeable without
maddening signedness compiler warnings in GCC-4.1, and add a new type
uchar (typedef unsigned char uchar), 'cause I'm lazy.
Then, if I wanted to push my luck, I'd deprecate all the wide-character
interfaces, and include a small suite of functions for manipulating UTF-8
encoded Unicode strings. I might start by adding a struct uvec, something
like: struct uvec { uchar *uv_base, [a bunch of opaque members,
noticeably and intentionally missing uv_len] }.
William Ahern wrote:
Ridiculous? Michael's comments echo exactly my experience. I write network
servers day-in and day-out. The standard library functions work great
for strings, memcpy() in particular. snprintf() is also very useful, but
I'd shorten that to say that the mem* stdlib functions work great. The str*
functions are just about useless for network code.
Personally, of late I often make use of the iovec structure from POSIX's
sys/uio.h. If I were to revamp string handling in C I'd make two
modifications.
1) Add an svec structure. struct svec { unsigned char *sv_base;
size_t sv_len; }.
2a) Mandate that (char) was unassigned (very radical), or
2b) Mandate that (char) and (unsigned char) were interchangeable without
maddening signedness compiler warnings in GCC-4.1, and add a new type
uchar (typedef unsigned char uchar), 'cause I'm lazy.
BTW: I have an iovec based buffer tokenizer that utilizes a source,
source_len, delimiter array, and optional character class flags (the standard
ctypes) if you're interested. Approx 3M iovec/sec tokenization on a P
(celeron) without modifying any of the source buffer. Basically, it's like
this:
const char *delim = " \t\n\r";
struct iovec v[16]; /* or whatever you feel is appropriate */
struct iovec *vp;
c = vtok(v, NE(v), buf, buf_len, delim, VT_SPACE | VT_CNTRL);
/* or */
c = vtoka(&vp, 0, buf, buf_len, delim, VT_SPACE | VT_CNTRL);
v[0..c - 1].iov_base = token
v[0..c - 1].iov_len = token_len
Returns c (count of vectors) when either len has been consumed, or max iovecs
have been used. Last iovec is the tail if len has been consumed.
Then, if I wanted to push my luck, I'd deprecate all the wide-character
interfaces, and include a small suite of functions for manipulating UTF-8
encoded Unicode strings. I might start by adding a struct uvec, something
like: struct uvec { uchar *uv_base, [a bunch of opaque members,
noticeably and intentionally missing uv_len] }.
Absolutely do NOT remove the length.
On Mon, 12 Feb 2007 22:16:26 -0800, Christopher Layne wrote:
William Ahern wrote:
<snip>
>Personally, of late I often make use of the iovec structure from
POSIX's sys/uio.h. If I were to revamp string handling in C I'd make
two modifications.
1) Add an svec structure. struct svec { unsigned char *sv_base; size_t
sv_len; }.
2a) Mandate that (char) was unassigned (very radical), or 2b) Mandate
that (char) and (unsigned char) were interchangeable without maddening
signedness compiler warnings in GCC-4.1, and add a new type uchar
(typedef unsigned char uchar), 'cause I'm lazy.
BTW: I have an iovec based buffer tokenizer that utilizes a source,
source_len, delimiter array, and optional character class flags (the
standard ctypes) if you're interested. Approx 3M iovec/sec tokenization
on a P (celeron) without modifying any of the source buffer. Basically,
it's like this:
I have something similar (almost exact, actually), which i call splitv()
(from the example split() function included in the strtok man page on many
Unices). But, I never put in character class support; it just takes an
optional (1 << CHAR_BIT)-character map for selecting delimiters.
I'd still be interested to see yours. I had a flag in mine to return empty
fields, but it's broken, meaning something in my loop should be smarter.
I've never gone back to it because so far I've never wanted to have the
empty fields.
>Then, if I wanted to push my luck, I'd deprecate all the wide-character
interfaces, and include a small suite of functions for manipulating UTF-8
encoded Unicode strings. I might start by adding a struct uvec, something
like: struct uvec { uchar *uv_base, [a bunch of opaque members,
noticeably and intentionally missing uv_len] }.
Absolutely do NOT remove the length.
Well, the notion is that given the history of C strings, the terminology
is overloaded. Is the "length" the "sizeof" of the object, where the units
are C's notion of bytes, or are we talking about the number of graphemes,
etc. I would remove something like uv_len and replace it with
two or more members or functions, each with more precise, less
ambiguous names. The problem with Unicode string processing is that it
violates many of the supposed intrinsic properties of strings that have
variously benefited and plagued programmers for years. Take the tokenizer
above, for instance. In written Thai there generally isn't any word or
symbol delimiters at all. Just one long string of syllables. To
tokenize you actually need a language dictionary, and you parse from right
to left trying to form words; when the next syllable couldn't
possible result in a legitimate word, you break. So with Thai it's an all
or nothing proposition; you either manipulate the text using a
sophisticated and capable interface, or you treat it as an opaque chunk of
memory. All this "wide-char" non-sense is completely and utterly useless.
We must permanently put to rest this practice in text processing
of conflating "characters" and "bytes" (indeed, at many levels remove the
notion of characters altogether; in one sense the usefulness rests solely
with parsing so-called human readable network protocols which employ
ASCII, but then that's not really "text").
Thus, this is also why I'd deprecate the wide-character support. It
fails to provide any sort of usefulness at the memory management level,
nor does it comprehensively solve the internationalization issue (heck,
technically if doesn't even allow you the privilege of conflating
characters and bytes if you so choosed, which will always be useful
for historical and technical reasons, as mentioned above). Also, the
whole notion of environment locale's is broken. But I digress. In any
event, I think the answer to both of those is to standardize on Unicode
strings, and a UTF-8 encoding specifically, so when you need to you can
fallback to more traditional string and memory management, while also
opening the door to sophisticated and comprehensive internationalized text
processing. This, I think, proceeds from and enhances the best qualities
of C. And if the idea of including such a large string interface with C was
too repugnant, I'd still implement everything else: rip out
wide-characters, fixed char signedness headaches, etc. They stand on
their own merits.
William Ahern wrote:
I have something similar (almost exact, actually), which i call splitv()
(from the example split() function included in the strtok man page on many
Unices). But, I never put in character class support; it just takes an
optional (1 << CHAR_BIT)-character map for selecting delimiters.
I'd still be interested to see yours. I had a flag in mine to return empty
fields, but it's broken, meaning something in my loop should be smarter.
I've never gone back to it because so far I've never wanted to have the
empty fields.
Give me a chance to clean it up some and finish up some remaining
functionality. And I hear you on the empty field, delimiters only, etc.
business.
>Absolutely do NOT remove the length.
Well, the notion is that given the history of C strings, the terminology
is overloaded. Is the "length" the "sizeof" of the object, where the units
are C's notion of bytes, or are we talking about the number of graphemes,
Length being purely bytes.
It's a structure member that should always be accessible to facilitate any
additional external handling of data.
Thus, this is also why I'd deprecate the wide-character support. It
fails to provide any sort of usefulness at the memory management level,
nor does it comprehensively solve the internationalization issue (heck,
technically if doesn't even allow you the privilege of conflating
characters and bytes if you so choosed, which will always be useful
for historical and technical reasons, as mentioned above). Also, the
Unicode, UTF-8, and UTF-16 and how they relate to C. I wonder if these will
ever be solved honestly. This thread has been closed and replies have been disabled. Please start a new discussion. |
