|
Compilers will generate jump statements. I don't mind, as long as I don't have to trace them, and maintain the code at that level.
Other generators may generate source format goto statements. I don't mind, as long as I don't have to trace them, and maintain the code at that level.
If the gotos and labels you presented are created by a generator, and you never will have to trace them and maintain the code at that level, I do not consider them "your" gotos. Not any more than I consider the conditional and unconditional jumps generated from your source code to be "your" jmp instructions.
I'd be curious to also see your input to Visual FA to generate this code, as well as the table driven code generated by Visual FA!
If you have any reason at all to relate to the generated code: Trading readability and maintainability for "slightly faster code" is generally a bad move. Besides: From the snippet you presented, I am surprised that a table driven variety generated from the same input can be even "slightly" slower. I really wonder what that generator generates! (That is why I'd like to see it.)
I have never been using Visual FA, but from what I gather from a quick net search, it looks like you are not at all using SM as a development too. You are just generating code for different virtual machines, one with a state oriented execution model, one with a C/C++ oriented execution model. A comparison between them is like compiling some (arbitrary language) source code for x64 and for AArch64 and observing that the x64 is "slightly faster".
To me, the SM table is not the result delivered by a generator - it is a modeling tool for the human developer. The driver is typically a score code statements, independent of the model (a.k.a. transition table). I certainly agree that an editor tailored to transition table editing is a great thing to have. I have tried to maintain a compile time initialized C++ array for a transition table, using Np++. Even for trivial SMs, that is almost impossible (unless you just copy the table from e.g. a standard document and it will be carved in stone).
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
trønderen wrote: If you have any reason at all to relate to the generated code. Trading readability and maintainability for "slightly faster code" is generally a bad move. . I generally agree with you. However, as we both know there are exceptions, which is why you used the word "generally" I'm sure. This is one of those cases, as lexing is always in a critical code path, and a generalized lexer must be able to handle bulk input as efficiently as possible.
My input to visual fa is one or more regular expressions. Literally just that. Here is the full input for that generated lexer, in my .rl Rolex lexer format, but it should be easy enough to discern the grammar below without knowing the format.
Object = "{"
ObjectEnd = "}"
Array = "["
ArrayEnd = "]"
FieldSeparator = ":"
Comma = ","
Number = '-?(?:0|[1-9][0-9]*)(?:\.[0-9]+)?(?:[eE][+-]?[0-9]+)?'
Boolean = 'true|false'
Null = "null"
String = '"([^\n"\\]|\\([btrnf"\\/]|(u[0-9A-Fa-f]{4})))*"'
WhiteSpace = '[ \t\r\n]+'
The table driven code is run on a flat array of integers. It might be more efficient to unflatten it in this case - maybe? I used to run a more complicated array of structs for this, and I don't remember there being a performance difference. But anyway, there is also an array of int arrays for a feature called block ends, which simulate lazy matching on a DFA. (I have the details of all of it documented in my Visual FA series). It's also simpler in operation than it looks. I do actually use gotos in a couple of places here to restart the state machine. It was much less complicated than orchestrating a while with breaks. I should state that I didn't comment the code here because it wouldn't help me. It may help others, but I didn't really care about that. This pattern is burned into my brain after writing more than half a dozen lexers that follow the same. It honestly would just clutter it for me, as the code makes immediate sense to me despite how it looks, and I didn't write it for a team.
private FAMatch _NextImpl(
#if FALIB_SPANS
ReadOnlySpan<char> s
#else
string s
#endif
)
{
int tlen;
int tto;
int prlen;
int pmin;
int pmax;
int i;
int j;
int state = 0;
int acc;
if (position == -1)
{
++position;
}
int len = 0;
long cursor_pos = position;
int line = this.line;
int column = this.column;
int ch = -1;
Advance(s, ref ch, ref len, true);
start_dfa:
acc = _dfa[state];
++state;
tlen = _dfa[state];
++state;
for (i = 0; i < tlen; ++i)
{
tto = _dfa[state];
++state;
prlen = _dfa[state];
++state;
for (j = 0; j < prlen; ++j)
{
pmin = _dfa[state];
++state;
pmax = _dfa[state];
++state;
if (ch < pmin)
{
state += ((prlen - (j + 1)) * 2);
j = prlen;
}
else if (ch <= pmax)
{
Advance(s, ref ch, ref len, false);
state = tto;
goto start_dfa;
}
}
}
if (acc != -1)
{
int sym = acc;
int[] be = (_blockEnds != null && _blockEnds.Length > acc) ? _blockEnds[acc] : null;
if (be != null)
{
state = 0;
start_be_dfa:
acc = be[state];
++state;
tlen = be[state];
++state;
for (i = 0; i < tlen; ++i)
{
tto = be[state];
++state;
prlen = be[state];
++state;
for (j = 0; j < prlen; ++j)
{
pmin = be[state];
++state;
pmax = be[state];
++state;
if (ch < pmin)
{
state += ((prlen - (j + 1)) * 2);
j = prlen;
}
else if (ch <= pmax)
{
Advance(s, ref ch, ref len, false);
state = tto;
goto start_be_dfa;
}
}
}
if (acc != -1)
{
return FAMatch.Create(sym,
#if FALIB_SPANS
s.Slice(unchecked((int)cursor_pos), len).ToString()
#else
s.Substring(unchecked((int)cursor_pos), len)
#endif
, cursor_pos, line, column);
}
if (ch == -1)
{
return FAMatch.Create(-1,
#if FALIB_SPANS
s.Slice(unchecked((int)cursor_pos), len).ToString()
#else
s.Substring(unchecked((int)cursor_pos), len)
#endif
, cursor_pos, line, column);
}
Advance(s, ref ch, ref len, false);
state = 0;
goto start_be_dfa;
}
return FAMatch.Create(acc,
#if FALIB_SPANS
s.Slice(unchecked((int)cursor_pos), len).ToString()
#else
s.Substring(unchecked((int)cursor_pos), len)
#endif
, cursor_pos, line, column);
}
while (ch != -1)
{
var moved = false;
state = 1;
tlen = _dfa[state];
++state;
for (i = 0; i < tlen; ++i)
{
++state;
prlen = _dfa[state];
++state;
for (j = 0; j < prlen; ++j)
{
pmin = _dfa[state];
++state;
pmax = _dfa[state];
++state;
if (ch < pmin)
{
state += ((prlen - (j + 1)) * 2);
j = prlen;
}
else if (ch <= pmax)
{
moved = true;
}
}
}
if (moved)
{
break;
}
Advance(s, ref ch, ref len, false);
}
if (len == 0)
{
return FAMatch.Create(-2, null, 0, 0, 0);
}
return FAMatch.Create(-1,
#if FALIB_SPANS
s.Slice(unchecked((int)cursor_pos), len).ToString()
#else
s.Substring(unchecked((int)cursor_pos), len)
#endif
, cursor_pos, line, column);
}
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
trønderen wrote: To me, the SM table is not the result delivered by a generator - it is a modeling tool for the human developer. The driver is typically a score code statements, independent of the model (a.k.a. transition table). I certainly agree that an editor tailored to transition table editing is a great thing to have. I have tried to maintain a compile time initialized C++ array for a transition table, using Np++. Even for trivial SMs, that is almost impossible (unless you just copy the table from e.g. a standard document and it will be carved in stone).
I didn't address this part of your post. I should. I don't expect transition tables to be especially readable.
Visual FA is called "Visual" because it can produce images - directed graphs of the state machines that match 1:1 with the generated tables and code. For example, q0 in the graph corresponds to the q0 : label in the goto table. It's perspicuous enough and yet concise enough that I've used the graphs as a guide to hand roll lexers when i needed the lexer to perform additional work beyond what a strict DFA could provide.
I've also used them to debug. Since the correlation is 1:1 between the graphs and the compiled code, it's easier to follow along with than the tables, but both can be followed with the graphs.
The graphs effectively become in part, documentation for the state machine, and for that they work pretty well.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
Generally you are right, usually the codewitch works on small embedded systems where performances and code footprint can be extremely stringent.
I found myself doing things I would have abhorred only a few scant years ago...
GCS/GE d--(d) s-/+ a C+++ U+++ P-- L+@ E-- W+++ N+ o+ K- w+++ O? M-- V? PS+ PE Y+ PGP t+ 5? X R+++ tv-- b+(+++) DI+++ D++ G e++ h--- r+++ y+++* Weapons extension: ma- k++ F+2 X
The shortest horror story: On Error Resume Next
|
|
|
|
|
Table driven implementations usually reduces the control code to typically a couple hundred bytes (or even less), at the expense of data space for the table.
By using data elements no larger than required in the transition table entries, each entry can be kept to a very moderate size.
One possible issue is the number of states and events. It takes some experience to control both, to keep the table size (#states * #events) under control. A common trick is to introduce 'state variables'.
Some times you can use 2+ small tables rather than a huge one, e.g. if you implement a communication protocol: One table for the connect phase, one for the data transfer phase.
Many transition tables are rather sparse anyway, but a lot of methods for space efficient storage of sparse matrices are basic data structure knowledge. E.g. non-empty entries may be factored out to a packed, linear array, and the large table contains indexes to this array. Often, several transitions are identical (typically in one state, for different events, or for one event in several different states) - then a linear table need to hold only a single copy.
Certainly, really old embedded processors (such as 8051) had very little data space; expanding code space was far easier (e.g. through banking hardware). While we would usually call the transition table 'data', it is 100% read-only, and may very well be burnt in ROM (ok, call it 'flash' nowadays) together with the driver code.
If you consider CLR for an embedded CPU (don't try that on an 8051!), then you definitely can fit a packed transition table. My guess is that the total code+data size would be significantly smaller than an equivalent implementation with switch cases and/or if/else-sequences. And faster, even if a packed table will lead to a couple more indirections.
I will maintain that table driven state machines can be a very good solution for embedded processors.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
trønderen wrote: If I were given the responsibility for a state machine implementation like that, I would immediately run to my boss asking for permission to rewrite the whole thing as a table driven machine.
... or as a state machine that returns function pointers instead of using tables and state variables:
#include <stdio.h>
#include <conio.h>
typedef void (*RT)( int input );
typedef RT (*TER)( int input );
extern TER state1( int input );
extern TER state2( int input );
extern TER state3( int input );
TER state1( int input )
{
printf( "one\t" );
return input < 10 ? (TER)&state2 : (TER)NULL;
}
TER state2( int input )
{
printf( "two\t" );
return (TER)&state3;
}
TER state3( int input )
{
printf( "three\t" );
return (TER)&state1;
}
int main(int argc, char* argv[])
{
int n;
TER state = (TER)&state1;
for ( n = 0 ; state ; ++n ) {
state = (TER)( state( n ) );
}
printf( "\n\nPress any key\n" );
getch();
return 0;
}
Type casts are useful because in C it's impossible to declare function pointers that return function pointers that return function pointers that return function pointers...
Regards
|
|
|
|
|
I hate function pointer dispatch code in general.
Because at some point you'll have to debug and maintain it, and you end up with impossible to follow pointer arrays hiding the flow of your app.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
honey the codewitch wrote: with impossible to follow pointer arrays
There are no pointer arrays in my code.
|
|
|
|
|
Sorry, I was speaking generally about dispatch function pointers. Your statement just remind me of it. Sorry I wasn't clear. I just woke up when I wrote that.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
No problem. I'm not a native English speaker so I always fear being misunderstood.
|
|
|
|
|
honey the codewitch wrote: I hate function pointer dispatch code in general. Do you refuse to use delegates at all, or don't you consider those to be function pointers? (In other words: Are function pointers OK as long as they are called delegates?)
No, when you have generated your code, you do not "at some time have to debug and maintain" the generated code. You debug and maintain your source, not the compilation result. Not even if you can, sort of, read it. Executable binaries can also be disassembled into "readable" code - the readability is no argument for random peek and poke.
You send your code through a generator/compiler, and want to patch up the complied result ("The compiled ones can be augmented in a way that the table driven ones cannot"), or complain about the instructions generated by the compiler - I haven't heard anyone saying any such thing in earnest for a decade or two. Some people still believe that they can do smarter heap management than the standard heap manager, rejecting automated garbage collection and smart pointers, but for the most part, compilers became smarter than human coders in the last millennium.
You will see a lot of function pointer dispatch code in the generated code from a plain C++ compiler. Do you hate that as well? If you accept it from a C++ compiler, why do you have problems accepting it from other compilers?
(The first C++ compiler I used didn't produce binary code - it was a machine independent compiler producing K&R C to be fed into a machine specific compiler. So we had full access to the C code for patching it up before passing it on to cc. We did not. I would not do it with any generated code, whether the compiler is called C++ or Visual FA.)
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
I was going to respond, but I think I answered all this in the post you responded to
Because at some point you'll have to debug and maintain it, and you end up with impossible to follow pointer arrays hiding the flow of your app.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
The real issue is:
honey the codewitch wrote: at some point you'll have to debug and maintain it Does that apply to the code generated by your C, C++ or C# compiler as well?
When are you going to start trusting your tools to do at least as good a job as the one you are doing yourself?
I think: If you don't trust your tools to do a good enough job, throw them away and do the job yourself!
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
It does not typically apply to generated code because the maintenance of that is moved to the generated code's input specification - in other words, whatever document or resource it uses to generate the code from. THAT is what needs to be maintained.
It does not apply to compiled code either, for exactly the same reason (the compiler being yet another code generator)
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
But if the code is generated by Visual FA rather than cc, then you will do peek and poke on the generated code.
Well, that is choice. I think you are on the wrong track. In the 1980s, I worked in a company distributing OS patches as Poke instructions. I wouldn't condone that practice today.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
then you will do peek and poke on the generated code.
I will? That's news to me.
Hell, with VisualFA.SourceGenerator you don't even see the generated code. It's hidden by visual studio.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
I took that from "at some point you'll have to debug and maintain it", along with your general focus on gotos being "yours" when they are generated by Visual FA - you clearly relate to the generated Visual FA code as something you have a right to (modify).
If you really are as ignorant of the code generated by Visual FA as you are of the code generated by the gcc compiler, why do you post it here?
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
Except with generated code. The input specification is what is maintained. Like I said.
As long as Visual FA can produce code given an input specification, there is no need to maintain the generated code.
I'm not sure how else I can put it, to be honest.
If you really are as ignorant of the code generated by Visual FA as you are of the code generated by the gcc compiler
You're reading all kinds of things into what I wrote. Don't. I didn't write that I was ignorant about the GCC compiler's generated code. You assumed that. I didn't write that I was ignorant about the code I wrote the god damned generator for, so don't assume I am.
I wrote exactly what I meant, and your assumptions are leading you to argue with me about them. They're yours. Don't make them mine.
In other words, it's not my job to unravel your assumptions for you, so maybe assume less about what I wrote.
PS: The title of my OP a reference to a famous line in a movie called Full Metal Jacket.
"There are many rifles, but this one is mine"
That is the only reason I referred to the gotos as mine - that and I wrote the code generator that produces them.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
modified 14-May-24 20:57pm.
|
|
|
|
|
"As long as Visual FA can produce code given an input specification, there is no need to maintain the generated code."
But you state that you do see a need to maintain the Visual FA generated code. So you do not trust your generator/compiler.
Why do you base this entire thread on Visual FA generated code? Because you relate closely to it, and consider the compiled code "yours" ("There are many gotos, but these ones are mine"). If you honestly have no intention of touching the generated code (any more than you touch gcc generated relocatable code), then why do you bring up properties of the generated code?
Make up your mind: Either, you are not going to maintain the code at the level generated by Visual FA, and then the use of gotos are as irrelevant (and not "yours") as a conditional or unconditional jump in binary code. OR, you think that you are more clever than the compiler, and can improve the result by random poking the generated code.
If you at all intend to follow the second alternative, modifying the code generated by Visual FA, then you are in the the "Random Poke" group. If you are not, never intending to modify the compilation result, then the compiled code is not subject to discussion. And the gotos are no more "yours" than the binary jump instructions in any binary compiled module.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
trønderen wrote: But you state that you do see a need to maintain the Visual FA generated code. So you do not trust your generator/compiler.
That would be fair, if I ever said that. However, I did not say that.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
honey the codewitch wrote: That would be fair, if I ever said that. However, I did not say that. You only said that "the maintenance of that is moved to the generated code's input specification - in other words, whatever document or resource it uses to generate the code from. THAT is what needs to be maintained" and your subject line clearly suggests that you expect to have full control over the gotos produced by your Visual FA generator.
Close your eyes for the gotos generated by your Visual FA compiler, as well as the conditional and unconditional jump instructions generated by any other compiler you use! You cannot both claim that the gotos are "your" gotos, and at the same time that you are oblivious to them!
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
It's not my fault you're fixated on the title of my post. You probably don't understand it because you never saw Full Metal Jacket, unlike most Americans here.
I said that the maintenance is moved to the input spec, and the generated code NEED NOT BE MAINTAINED.
I don't know why you refuse to understand that simple concept when I say it, but when you say it you seem to have no similar misunderstanding.
If I didn't know better I'd think I was being trolled.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
trønderen wrote: our subject line clearly suggests that you expect to have full control over the gotos produced by your Visual FA generator.
Wrong. You are simply wrong. My subject line does not suggest any such thing. You assumed that. You are trying to read my mind. You suck at it, as I tried to gently imply last time you did it.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
I'm not sure why it wouldn't be pretty straightforward to [TestCase()] for each of the branching?
I don't think this code is very cyclomatically complex?
But yeah when you say table driven state machine I'm pretty sure that's where my head is too if you're basically talking a direct map of the case statements to data.
|
|
|
|
|
There is one issue with that.
The compiled ones can be augmented in a way that the table driven ones cannot.
For example, I wrote an embedded JSON pull parser in C++. I used compiled DFA code, and then I parsed floats, ints, and bools out of the stream *as* I was lexing, making the API both easier to use and marginally more performant because you didn't have to get the string back and then reexamine it in order to call atoi() or whatever. It was a simple little surgery on the generated code, with excellent results.
I admit this isn't the most common case out there, but I have used this technique several times.
Edited to add: It's also easier in practice to debug and step through a generated lexer than it is a table driven lexer. And with my Visual FA project, it produces images of directed graphs that map one to one to the labels/jump points in the code. q0: maps to the state q0 in the graph. It makes it really easy to see what it's doing, in terms of documenting it.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|