[MUD-Dev] Storing tokens with flex & bison

Jon A. Lambert jlsysinc at ix.netcom.com
Mon Jan 17 23:38:28 New Zealand Daylight Time 2000


Chris Gray wrote:
>[Jon A. Lambert:]
>

>> Hmm, I was thinking in terms of how many instructions my VM will be traversing
>> rather than how the hardware is going to handle those instructions.
>> Now I could implement my VM class as a 3 register machine using the
>> members:
>
>Ah, OK. That makes sense. If your register count is small, that works fine.
>Now reminded, my 8080 emulator on x86 simply used the one-byte opcode as
>a direct index into a 256 entry dispatch table.
>

I'm familiar with the Z-80, though I'm not sure how closely related it was to the
8080.  I know the Z-80 had over 400 instructions (if you count the modes), a
much much larger set than the 6502.
In particular, I recall the 'RST n'  opcode, which is pretty much the way I
implement calls to built-in functions/library calls in my bytecode.  It allows
me to add new built-in functions without recompiling old bytecode, as long
as I don't change 'n' which is the index into a definition table.  BTW, this
technique might have been useful in the DevMUD project for dynamically
loading and registering new function libraries (DLLs).

>> >From the bytecode angle the register is an intrinsic part of the opcode, that is
>> it is determined at compilation time.  Now push() and pop() operations
>> in the VM are going to be to checking for a stack overflow or underflow, no?
>
>Actually, no. If you don't allow users to directly generate byte-code, and
>you are careful with your compiler, there is never any need to check for
>stack underflow. (Well, my interpreter checks the SP after a 'return'
>instruction to see if it should return from this level of execution.)
>Stack overflow can be handled by a combination of a few checks at run-time
>(e.g. at function entry), and compilation checks. This is the exact code for
>integer addition from my sources:
>
> CASE(bc_add) {
>     ULONG_T ul;
>
>     ul = *sp++;
>     *sp += ul;
>     BREAK;
> }
>
>Macros 'CASE' and 'BREAK' allow the code to compile either using the
>gcc dynamic goto stuff, or not. Note: use lots of small scopes and very
>local variables like this, so that the compiler can do maximum re-use of
>the limited X86 register set.
>


Good point.  I could probably remove my check for underflow!  I'm dubious
about removing the stack overflow check since I allow infinite recursion,
theoretically at least.  My VM will timeout and cancel task long before any
ridiculously huge stack size is reached.

I'm not familiar with how the gcc dynamic goto stuff works.  I've included
my Borland output near the end of this post.  Usually I do include locals
at the very top of routines, for personal readability.  The only time I embed
locals in block scope is with the C++ for-loop counters and those that have
a high construction cost (classes).   I know that it is not necessarily optimal.

>> I guess this might lead to the question of whether it is better to have more
>> or less opcodes for your VM's instruction set.  I will note that the Java VM
>> has quite a boatload of special case opcodes, it even distinguishes between
>> pushing an int and pushing a constant one or zero.  So is it better to accomplish
>> something by generating a longer series of simple bytecode operations, or
>> implement a lot of special purpose bytecodes?
>
>I say go for the special-case ones. I have some like 'pshz', 'psh1', etc.
>They are very easy to do and use, and can have a noticeable speedup. I'm
>real tempted to go add 'add1' and 'sub1', as in our earlier discussion,
>to see what effect they have. Should take about 15 minutes.

I tend to agree.  I would note that my weak-typeing of variables prevents
my use of specialized bytecodes except in the case of constants.  :(

>> I don't think speed of compilation is really an issue at least in the context of
>> a mud server's internal programming language.  Typically in an LP, Moo, Cold,
>> Muck, etc. you are compiling rather small pieces of method code or single objects
>> so you can add as many phases or passes to the compilation as you need.
>> Of course online compilation should be multitasked and handled just like any
>> other mud event especially if you have a user programmable setup.
>
>Well, when you have a system that works well, you tend to use it a lot.
>I've gotten into the habit of changing one line of scenario source and then
>recompiling all 20,000 lines, rather than making the change online! Too
>many times I've forgotten to make the change in the master sources.
>

Actually I have been doing this also, but primarily because I'm still making
low-level changes in the way the bytecode is generated that require it.
Much of my test mudlib is really just a massive test script hitting all the
language features.

> My point, however,
>is that if the overheads of non-static typing are significant, then going
>to byte-code could be rather pointless, since it might gain only a few
>percent speedup. With strong typing, there is virtually no run-time
>overhead for type-checking sorts of things, so going from direct
>interpration to byte-code is almost certainly a big win. This is just
>a case of one of the general rules concerning speeding programs up: fix
>the big things first, then the little things.
>

Sure, but there are other considerations beyond a small(?) performance
gain that make it "sensible".   Design goals for instance.  Like providing a
common target for multiple languages.  Implementing and debugging a new
parser is half the cost of a new interpreter, since the execution piece is
reusable.  Multi-tasking for another.  It's a good deal easier to interrupt a
running VM externally and save its state than an executing Interpreter.
Although I must admit using threads might simplify it.

Or perhaps the idea of safely unwinding the native stack in an interpreter in
order to flag an error and get back to square one just frightens me, and I find
it easier to debug something after it has been be decomposed into the
simplest of functions.  For some reason I associate interpreters with
monolithic code.


>> It looks like what one would do with a strongly-typed system.  All the
>> complexity and overhead is hiding under the covers of C++.
>>
>> Var& Var::operator=(const Var& value);
>> friend Var operator+(const Var& v1,const Var& v2) throw(TypeError);
>>
>> You'll find all the switches, if-else chains, and conversion exceptions in
>> those functions.  Yes it's overhead but it is not complex.  Maintenance,
>> debugging and readability are very good.  At least I think so.
>
>Any idea how much overhead? Just guessing, comparing my snippet of source
>against what you are showing here, I'd guess a factor of 25 or more. That
>is actually *more* than I had thought.


Ok, I'll pull back the covers.  And your guess is pretty accurate.  ;)

TMVar operator+(const TMVar& v1,const TMVar& v2) throw(Error)
{
  if ((v1.type != v2.type) && (v1.type != LIST)) {
    throw (E_TYPE);
  }
  if ((v1.type == ARRAY) || (v1.type == ERROR) || (v1.type == OBJECT)) {
    throw (E_TYPE);
  }

  TMVar ret(v1.type);
  switch (v1.type) {
    case NUM:
       *((int*)ret.value) = *((int*)v1.value) + *((int*)v2.value);
       break;
    case LIST:
       new(ret.v) TMList(*(TMList*)v1.value);
       ((TMList*)ret.value)->rSetAdd(v2);
       break;
    case STRING:
       new(ret.v) TMString(*(TMString*)v1.value);
       *((TMString*)ret.value) += *((TMString*)v2.value);
       break;
  }
  return ret;
}


And heres the native code.   I have register optimizations on, but I turned
off constructor inlines so it could be followed.  Pardon the line breaks.

      c:\tychomud\tmvar.cpp, 454: TMVar operator+(const TMVar& v1,const TMVar& v2) throw(Error)
      004039ED 55                       push  ebp
      004039EE 8BEC                     mov   ebp,esp
      004039F0 83C4C0                   add   esp,-0x40
      004039F3 53                       push  ebx
      004039F4 56                       push  esi
      004039F5 8B7510                   mov   esi,[ebp+0x10]
      004039F8 8B5D0C                   mov   ebx,[ebp+0x0c]
      004039FB B8FC034100               mov   eax,0x004103fc
      00403A00 E8BFA30000               call  __InitExceptBlock(void *)
      c:\tychomud\tmvar.cpp, 459: if ((v1.type != v2.type) && (v1.type != LIST)) {
      00403A05 8B5304                   mov   edx,[ebx+0x04]
      00403A08 3B5604                   cmp   edx,[esi+0x04]
      00403A0B 742A                     jz    0x403A37
      00403A0D 837B0403                 cmp   dword ptr [ebx+0x04],0x03
      00403A11 7424                     jz    0x403A37
      c:\tychomud\tmvar.cpp, 460: throw (E_TYPE);
      00403A13 6A00                     push  0x00
      00403A15 6A00                     push  0x00
      00403A17 6A00                     push  0x00
      00403A19 6A00                     push  0x00
      00403A1B 6A00                     push  0x00
      00403A1D 6A00                     push  0x00
      00403A1F C745C401000000           mov   [ebp-0x3c],0x00000001
      00403A26 8D4DC4                   lea   ecx,[ebp-0x3c]
      00403A29 51                       push  ecx
      00403A2A 6820434000               push  0x00404320
      00403A2F E821A90000               call  cw3220._ThrowException(void*,void*,void*,void*,unsigned int,unsigned
int,unsigned int,unsigned char*)
      00403A34 83C420                   add   esp,0x20
      c:\tychomud\tmvar.cpp, 462: if ((v1.type == ARRAY) || (v1.type == ERROR) || (v1.type == OBJECT)) {
      00403A37 837B0404                 cmp   dword ptr [ebx+0x04],0x04
      00403A3B 740C                     jz    0x403A49
      00403A3D 837B0405                 cmp   dword ptr [ebx+0x04],0x05
      00403A41 7406                     jz    0x403A49
      00403A43 837B0402                 cmp   dword ptr [ebx+0x04],0x02
      00403A47 7524                     jnz   0x403A6D
      c:\tychomud\tmvar.cpp, 463: throw (E_TYPE);
      00403A49 6A00                     push  0x00
      00403A4B 6A00                     push  0x00
      00403A4D 6A00                     push  0x00
      00403A4F 6A00                     push  0x00
      00403A51 6A00                     push  0x00
      00403A53 6A00                     push  0x00
      00403A55 C745C001000000           mov   [ebp-0x40],0x00000001
      00403A5C 8D45C0                   lea   eax,[ebp-0x40]
      00403A5F 50                       push  eax
      00403A60 6820434000               push  0x00404320
      00403A65 E8EBA80000               call  cw3220._ThrowException(void*,void*,void*,void*,unsigned int,unsigned
int,unsigned int,unsigned char*)
      00403A6A 83C420                   add   esp,0x20
      c:\tychomud\tmvar.cpp, 466: TMVar ret(v1.type);
      00403A6D 66C745D80800             mov   word ptr [ebp-0x28],0x0008
      00403A73 FF7304                   push  [ebx+0x04]
      00403A76 8D55F0                   lea   edx,[ebp-0x10]
      00403A79 52                       push  edx
      00403A7A E841EDFFFF               call  TMVar::TMVar(Type_spec)
      00403A7F 83C408                   add   esp,0x08
      c:\tychomud\tmvar.cpp, 468: switch (v1.type) {
      00403A82 8B4B04                   mov   ecx,[ebx+0x04]
      00403A85 83E901                   sub   ecx,0x01
      00403A88 720C                     jb    0x403A96
      00403A8A 746F                     jz    0x403AFB
      00403A8C 83E902                   sub   ecx,0x02
      00403A8F 7413                     jz    0x403AA4
      00403A91 E9A1000000               jmp   0x403B37
      c:\tychomud\tmvar.cpp, 470: *((int*)ret.v) = *((int*)v1.v) + *((int*)v2.v);
      00403A96 8B4308                   mov   eax,[ebx+0x08]
      00403A99 034608                   add   eax,[esi+0x08]
      00403A9C 8945F8                   mov   [ebp-0x08],eax
      c:\tychomud\tmvar.cpp, 471: break;
      00403A9F E993000000               jmp   0x403B37
      c:\tychomud\tmvar.cpp, 476: new(ret.v) TMList((*(TMList*)v1.v));
      00403AA4 8D55F8                   lea   edx,[ebp-0x08]
      00403AA7 8955EC                   mov   [ebp-0x14],edx
      00403AAA 85D2                     test  edx,edx
      00403AAC 7422                     jz    0x403AD0
      00403AAE 66C745D82000             mov   word ptr [ebp-0x28],0x0020
      00403AB4 83C308                   add   ebx,0x08
      00403AB7 53                       push  ebx
      00403AB8 FF75EC                   push  [ebp-0x14]
      00403ABB E885090000               call  TMList::TMList(const TMList &)
      00403AC0 83C408                   add   esp,0x08
      00403AC3 A1EC4B4100               mov   eax,[__DestructorCountPtr]
      00403AC8 FF08                     dec   [eax]
      00403ACA 66C745D81400             mov   word ptr [ebp-0x28],0x0014
      c:\tychomud\tmvar.cpp, 477: ((TMList*)ret.v)->rSetAdd(v2);
      00403AD0 83C4F0                   add   esp,-0x10
      00403AD3 66C745D83800             mov   word ptr [ebp-0x28],0x0038
      00403AD9 56                       push  esi
      00403ADA 8D542404                 lea   edx,[esp+0x04]
      00403ADE 52                       push  edx
      00403ADF E8D6F1FFFF               call  TMVar::TMVar(const TMVar &)
      00403AE4 83C408                   add   esp,0x08
      00403AE7 8D4DF8                   lea   ecx,[ebp-0x08]
      00403AEA 51                       push  ecx
      00403AEB 66C745D82C00             mov   word ptr [ebp-0x28],0x002c
      00403AF1 E8070D0000               call  TMList::rSetAdd(TMVar)
      00403AF6 83C414                   add   esp,0x14
      c:\tychomud\tmvar.cpp, 478: break;
      00403AF9 EB3C                     jmp   0x403B37
      c:\tychomud\tmvar.cpp, 480: new(ret.v) TMString(*((TMString*)v1.v));
      00403AFB 8D45F8                   lea   eax,[ebp-0x08]
      00403AFE 8945E8                   mov   [ebp-0x18],eax
      00403B01 85C0                     test  eax,eax
      00403B03 7422                     jz    0x403B27
      00403B05 66C745D85000             mov   word ptr [ebp-0x28],0x0050
      00403B0B 83C308                   add   ebx,0x08
      00403B0E 53                       push  ebx
      00403B0F FF75E8                   push  [ebp-0x18]
      00403B12 E87E220000               call  TMString::TMString(const TMString &)
      00403B17 83C408                   add   esp,0x08
      00403B1A A1EC4B4100               mov   eax,[__DestructorCountPtr]
      00403B1F FF08                     dec   [eax]
      00403B21 66C745D84400             mov   word ptr [ebp-0x28],0x0044
      c:\tychomud\tmvar.cpp, 481: *((TMString*)ret.v) += *((TMString*)v2.v);
      00403B27 83C608                   add   esi,0x08
      00403B2A 56                       push  esi
      00403B2B 8D45F8                   lea   eax,[ebp-0x08]
      00403B2E 50                       push  eax
      00403B2F E8EC270000               call  TMString::operator +=(const TMString &)
      00403B34 83C408                   add   esp,0x08
      c:\tychomud\tmvar.cpp, 484: return ret;
      00403B37 66C745D85C00             mov   word ptr [ebp-0x28],0x005c
      00403B3D 8D55F0                   lea   edx,[ebp-0x10]
      00403B40 52                       push  edx
      00403B41 FF7508                   push  [ebp+0x08]
      00403B44 E871F1FFFF               call  TMVar::TMVar(const TMVar &)
      00403B49 83C408                   add   esp,0x08
      00403B4C 8B4508                   mov   eax,[ebp+0x08]
      00403B4F 66C745D86800             mov   word ptr [ebp-0x28],0x0068
      00403B55 50                       push  eax
      00403B56 6A02                     push  0x02
      00403B58 8D55F0                   lea   edx,[ebp-0x10]
      00403B5B 52                       push  edx
      00403B5C E896F2FFFF               call  TMVar::~TMVar()
      00403B61 83C408                   add   esp,0x08
      00403B64 58                       pop   eax
      00403B65 66C745D85C00             mov   word ptr [ebp-0x28],0x005c
      00403B6B FF45E4                   inc   [ebp-0x1c]
      00403B6E 8B55C8                   mov   edx,[ebp-0x38]
      00403B71 64891500000000           mov   fs:[0x00000000],edx
      c:\tychomud\tmvar.cpp, 485: }
      00403B78 5E                       pop   esi
      00403B79 5B                       pop   ebx
      00403B7A 8BE5                     mov   esp,ebp
      00403B7C 5D                       pop   ebp
      00403B7D C3                       ret

So to add two integers, there's 50 some odd instructions (gasp!) that are
executed, and that's assuming I have inlined the constructors.
Now if I were strongly typed, I wouldn't be checking for exceptions or
providing a wrapper for variables, so I'd have maybe 10-13 instructions
for my add_op(), assuming a standard function call.   So it's about 5 times
slower.   Inlining add_op() could would of course reduce that to maybe 3-4
instructions and be 20 times faster!   Any thoughts?  crummy code? ;_)

>And heaven help you if you end
>up with some temporary copies of variables because of problems with
>reference parameters! I have practically zero experience with C++, so
>the presense of all those '&'s would make me *very* nervous about that.
>


Passing by reference is the same as passing by pointer as far as the
machine code that is generated by the compiler.  Of course, as a general rule,
I only use const reference parameters for safety.    BTW there is an excellent
shareware tool for BC++, Builder and Delphi called MemProof which
performs many of the same functions as Purify does.  It even finds memory
leaks in Windows API functions.  I'd still be crashing and burning without it.  :)

--
--*     Jon A. Lambert - TychoMUD Email: jlsysinc at nospam.ix.netcom.com     *--
--*     Mud Server Developer's Page <http://jlsysinc.home.netcom.com>      *--
--* "No Free man shall ever be debarred the use of arms." Thomas Jefferson *--





_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev



More information about the MUD-Dev mailing list