home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / arch / 8902 < prev    next >
Encoding:
Text File  |  1992-08-14  |  18.4 KB  |  409 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!mcsun!Germany.EU.net!Urmel.Informatik.RWTH-Aachen.DE!martin
  3. From: martin@math.rwth-aachen.de (  Martin Schoenert)
  4. Subject: Re: Threaded Code
  5. Message-ID: <martin.713808550@bert>
  6. Sender: news@Urmel.Informatik.RWTH-Aachen.DE (Newsfiles Owner)
  7. Nntp-Posting-Host: bert.math.rwth-aachen.de
  8. Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
  9. References: <55535@mentor.cc.purdue.edu> <13910@goanna.cs.rmit.oz.au> <GLEW.92Aug7185506@pdx007.intel.com> <1992Aug10.141731.10007@email.tuwien.ac.at>
  10. Date: 14 Aug 92 16:09:10 GMT
  11. Lines: 396
  12.  
  13. I tried to experiment a little bit with the functions written by Anton
  14. Ertl.  However, I had lots of problems, because they are so small that
  15. they are subject to all kinds of strange optimizations.
  16.  
  17. So I wrote my own tests.  First I defined a virtual (stack) machine with
  18. 28 instructions (not just 2 as in Anton's tests).  For this virtual
  19. machine I wrote a small test program, which computes the number of primes
  20. less than 40000 in a very straightforward way.  Then I wrote and tested
  21. the following 6 implementations of this virtual machine.
  22.  
  23. Bytecode with switch statement (swi.c):
  24.     The instructions of the virutal machine are encoded by the integers
  25.     [0..27].  This bytecode is interpreted by a 'switch' statement, where
  26.     each case implements one instruction.  After the code of a case has
  27.     done its work it performs a 'goto' to a label immediately before the
  28.     'switch'.
  29.  
  30. Bytecode with switch statement, handoptimized (swo):
  31.    This is the same code as above, execpt that the assembler file
  32.    produced by the compiler was edited to remove the unnecessary range
  33.    check of the 'switch'.
  34.  
  35. Bytecode with label pointers (inb.c):
  36.     The instructions are again encoded by the integers [0..27].  There is
  37.     an array that contains for each instruction the label pointer of the
  38.     code for this instruction.  To execute the next instruction the code
  39.     fetches the bytecode, looks it up in the array, and jumps to the
  40.     address found there.  Of course this works only with gcc.
  41.  
  42. Subroutine threading (sub.c):
  43.     For each instruction there is a (C) function which implements this
  44.     instruction.  The instructions are encoded with the addresses of
  45.     those functions.  Each function returns after it has done its work,
  46.     and there is a central dispatcher in 'main', which looks as follows
  47.     'while (1) (**pc++)();'
  48.  
  49. Direct threading (dir.c):
  50.     Again the instructions are encoded by addresses of code that
  51.     implements them.  However, this time all code that is in 'main' and
  52.     the addresses are addresses of labels in 'main'.  To execute the next
  53.     instruction the code fetches the address and jumps there.  So this is
  54.     similar to ``Bytecode with label pointers'', except no indirection is
  55.     needed.  Again, this works only with gcc.
  56.  
  57. Indirect threading (ind.c):
  58.     This lies between ``Direct threading'' and ``Bytecode with label
  59.     pointers''.  Each instruction is encoded by the address of the place
  60.     in an array where the address of the code implementing this
  61.     instruction is stored.  So to go to the next instruction this
  62.     executes 'goto ***pc++;' instead of 'goto *instr[*pc++];', which
  63.     saves one shift and one add.  I included this because it corresponds
  64.     to Anton's indirect method.
  65.  
  66. On a DECstation 5000/120 this gave the following results:
  67.  
  68.     Compiler    swi     swo     inb     sub     dir     ind
  69.     GCC 2.2.2   11.2    9.0     8.2     8.0     6.2     7.3
  70.     MIPS CC     10.9    8.8     -       10.3    -       -
  71.  
  72. Note the rather large performance gain one gets by removing the range
  73. check from the switch code.  With both compilers it gives approx. 20%.
  74. It would be really nice if a comiler could do this on his own.  This
  75. shouldn't be very hard.  (Maybe somebody who knows gcc better than I do
  76. wants to try this? ;-)
  77.  
  78. The remaining difference between 'swo' and 'inb' is due to the fact that
  79. the code for 'swo' jumps back to the dispatch code at the top of the
  80. 'switch' statement.  Yes, one jump accounts for 7%!  This is because the
  81. code that implements the individual instructions is so simple (between 3
  82. and 12 machine instructions).
  83.  
  84. The time for 'sub' compiled with gcc is much better than the time for
  85. 'sub' compiled with cc because gcc allows to declare the two global
  86. variables 'pc' and 'sp' (the virtual machines program counter and stack
  87. pointer) as register variables.  Note that gcc still writes the value of
  88. those register variables from time to time to the memory.  If one removes
  89. one of those stores by hand (in the assembler output) the time drops to
  90. 7.4 seconds.
  91.  
  92. The remaining difference between 'sub' and 'dir' is due to the jumps to
  93. and returns from the subroutines, which are not present in 'dir'.  Thus,
  94. if a C compiler could be relied upon to eliminate tail calls, then 'sub'
  95. could be made as fast as 'dir'.
  96.  
  97.    (Side note, *Eliminating tail calls* means that in the following
  98.     situation:
  99.  
  100.         f ( ... ) { ...; g(); }
  101.  
  102.     the compiler generates the following code
  103.  
  104.         deallocate stack frame
  105.         *jump* to 'g'
  106.         ; we will never reach this point because 'g' returns to 'f's caller
  107.  
  108.     instead of
  109.  
  110.         *call* 'g'
  111.         deallocate stack frame
  112.         return
  113.  
  114.     A special case of tail call elimination is the elimination of *tail
  115.     recursive* function calls.  A function is tail recursive if its last
  116.     statement is a call to itself.  If this call of a tail recursive
  117.     function is eliminated, such a function only uses a constant amount
  118.     of stack space for all its invocations.  I understand that gcc does
  119.     tail recursive call elimination.)
  120.  
  121. You may of course draw your own conclusions, however mine are as follows.
  122.  
  123. Label pointers are an interesting feature that allow the efficient
  124. implementation of bytecode and direct threaded interpreters.
  125.  
  126. However, rather than relying on nonstandard extensions of C to implement
  127. bytecode and direct threaded interpreters, I would like to see the
  128. following optimizations in C compiler.
  129.  
  130. 1.  Detecting that the expression in a switch statement can only have a
  131.     small number of values (e.g., if the expression is an unsigned char
  132.     variable), and compiling the switch using a jump table but no range
  133.     check.
  134.  
  135. 2.  Allowing (e.g., with an option or a pragma) that a goto to a
  136.     dispatcher is inlined.  I am not certain how one would define what a
  137.     dispatcher is, but one possible optimization that would handle this
  138.     is to replace each unconditional branch by the code it branches to,
  139.     up to (and including) the first (conditional or unconditional)
  140.     branch.
  141.  
  142. 3.  Perform (again under the control of an option or pragma) tail call
  143.     elimination.
  144.  
  145. If a compiler performed those optimizations the implementations of
  146. bytecode and direct threaded interpreters such as 'swi' and 'sub' would
  147. be just as efficient as the implementations using gcc's label pointers.
  148. Such optimizations might also be worthwile in other situations where
  149. label pointers would not help at all.
  150.  
  151. Martin.
  152.  
  153. --
  154. Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
  155. Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
  156.  
  157. Here is the code, so you can make your own experiments.
  158.  
  159. /** prog *******************************************************************/
  160. INST    LD0,                    /* n = 0;                                  */
  161. INST    LD2,                    /* i = 2;                                  */
  162. INST    DUP,                    /* while ( i <= 40000 ) {                  */
  163. INST    LDL, CONST 200,
  164. INST    LDL, CONST 200,
  165. INST    MUL,
  166. INST    BGT, CONST 27,
  167. INST    LD2,                    /*     j = 2;                              */
  168. INST    DUP,                    /*     while ( j*j <= i ) {                */
  169. INST    DUP,
  170. INST    MUL,
  171. INST    DUP2,
  172. INST    BGT, CONST 11,
  173. INST    DUP1,                   /*         if ( i % j == 0 ) goto next_i   */
  174. INST    DUP1,
  175. INST    MOD,
  176. INST    LD0,
  177. INST    BEQ, CONST 9,
  178. INST    LD1,                    /*         j++;                            */
  179. INST    ADD,
  180. INST    BRA, CONST -15,         /*     }                                   */
  181. INST    DUP2,                   /*     n++;                                */
  182. INST    LD1,
  183. INST    ADD,
  184. INST    PUD2,
  185. INST    DRP,                    /*     next_i: (drop j)                    */
  186. INST    LD1,                    /*     i++;                                */
  187. INST    ADD,
  188. INST    BRA, CONST -33,         /* }                                       */
  189. INST    DRP,                    /* print n;                                */
  190. INST    PRINT,
  191. INST    STOP                    /* exit                                    */
  192.  
  193. /** swi.c ******************************************************************/
  194. #include        <stdio.h>
  195.  
  196. int             main ()
  197. {
  198.     enum {
  199.         LD0,    LD1,    LD2,    LD3,    LD4,    LD5,    LD6,    LDL,
  200.         DUP,    DUP1,   DUP2,   DUP3,   PUD,    PUD1,   PUD2,   PUD3,   DRP,
  201.         ADD,    SUB,    MUL,    QUO,    MOD,    BRA,    BEQ,    BNE,    BGT,
  202.         PRINT,  STOP };
  203.  
  204.     static unsigned char    prog [] = {
  205. #define INST
  206. #define CONST
  207. #include "prog"
  208.         };
  209.     unsigned char           * pc = prog;
  210.  
  211.     static long             stack [64];
  212.     long                    * sp = stack;
  213.  
  214.  dispatch:
  215.     switch ( *pc++ ) {
  216.     case LD0:   sp++; *sp = 0;                                 goto dispatch;
  217.     case LD1:   sp++; *sp = 1;                                 goto dispatch;
  218.     case LD2:   sp++; *sp = 2;                                 goto dispatch;
  219.     case LD3:   sp++; *sp = 3;                                 goto dispatch;
  220.     case LD4:   sp++; *sp = 4;                                 goto dispatch;
  221.     case LD5:   sp++; *sp = 5;                                 goto dispatch;
  222.     case LD6:   sp++; *sp = 6;                                 goto dispatch;
  223.     case LDL:   sp++; *sp = *pc++;                             goto dispatch;
  224.     case DUP:   sp++; *sp = sp[-1];                            goto dispatch;
  225.     case DUP1:  sp++; *sp = sp[-2];                            goto dispatch;
  226.     case DUP2:  sp++; *sp = sp[-3];                            goto dispatch;
  227.     case DUP3:  sp++; *sp = sp[-4];                            goto dispatch;
  228.     case PUD:   sp[-1] = *sp; sp--;                            goto dispatch;
  229.     case PUD1:  sp[-2] = *sp; sp--;                            goto dispatch;
  230.     case PUD2:  sp[-3] = *sp; sp--;                            goto dispatch;
  231.     case PUD3:  sp[-4] = *sp; sp--;                            goto dispatch;
  232.     case DRP:   sp--;                                          goto dispatch;
  233.     case ADD:   sp--; *sp += sp[1];                            goto dispatch;
  234.     case SUB:   sp--; *sp -= sp[1];                            goto dispatch;
  235.     case MUL:   sp--; *sp *= sp[1];                            goto dispatch;
  236.     case QUO:   sp--; *sp /= sp[1];                            goto dispatch;
  237.     case MOD:   sp--; *sp %= sp[1];                            goto dispatch;
  238.     case BRA:          pc += *(signed char*)pc;                goto dispatch;
  239.     case BEQ:   sp-=2; pc+=(sp[1]==sp[2]?*(signed char*)pc:1); goto dispatch;
  240.     case BNE:   sp-=2; pc+=(sp[1]!=sp[2]?*(signed char*)pc:1); goto dispatch;
  241.     case BGT:   sp-=2; pc+=(sp[1] >sp[2]?*(signed char*)pc:1); goto dispatch;
  242.     case PRINT: printf("%d\n",*sp--);                          goto dispatch;
  243.     case STOP:  return;
  244.     }
  245.  
  246. }
  247.  
  248. /** ind.c ******************************************************************/
  249. #include        <stdio.h>
  250.  
  251. int             main ()
  252. {
  253.     enum {
  254.         LD0,    LD1,    LD2,    LD3,    LD4,    LD5,    LD6,    LDL,
  255.         DUP,    DUP1,   DUP2,   DUP3,   PUD,    PUD1,   PUD2,   PUD3,   DRP,
  256.         ADD,    SUB,    MUL,    QUO,    MOD,    BRA,    BEQ,    BNE,    BGT,
  257.         PRINT,  STOP };
  258.  
  259.     static void             * instr [] = {
  260.         &&ld0,  &&ld1,  &&ld2,  &&ld3,  &&ld4,  &&ld5,  &&ld6,  &&ldl,
  261.         &&dup,  &&dup1, &&dup2, &&dup3, &&pud,  &&pud1, &&pud2, &&pud3, &&drp,
  262.         &&add,  &&sub,  &&mul,  &&quo,  &&mod,  &&bra,  &&beq,  &&bne,  &&bgt,
  263.         &&print, &&stop };
  264.  
  265.     static unsigned char    prog [] = {
  266. #define INST
  267. #define CONST
  268. #include "prog"
  269.         };
  270.     unsigned char           * pc = prog;
  271.  
  272.     static long             stack [64];
  273.     long                    * sp = stack;
  274.  
  275.     goto *instr[*pc++];
  276.  
  277.     ld0:   sp++; *sp = 0;                                 goto *instr[*pc++];
  278.     ld1:   sp++; *sp = 1;                                 goto *instr[*pc++];
  279.     ld2:   sp++; *sp = 2;                                 goto *instr[*pc++];
  280.     ld3:   sp++; *sp = 3;                                 goto *instr[*pc++];
  281.     ld4:   sp++; *sp = 4;                                 goto *instr[*pc++];
  282.     ld5:   sp++; *sp = 5;                                 goto *instr[*pc++];
  283.     ld6:   sp++; *sp = 6;                                 goto *instr[*pc++];
  284.     ldl:   sp++; *sp = *pc++;                             goto *instr[*pc++];
  285.     dup:   sp++; *sp = sp[-1];                            goto *instr[*pc++];
  286.     dup1:  sp++; *sp = sp[-2];                            goto *instr[*pc++];
  287.     dup2:  sp++; *sp = sp[-3];                            goto *instr[*pc++];
  288.     dup3:  sp++; *sp = sp[-4];                            goto *instr[*pc++];
  289.     pud:   sp[-1] = *sp; sp--;                            goto *instr[*pc++];
  290.     pud1:  sp[-2] = *sp; sp--;                            goto *instr[*pc++];
  291.     pud2:  sp[-3] = *sp; sp--;                            goto *instr[*pc++];
  292.     pud3:  sp[-4] = *sp; sp--;                            goto *instr[*pc++];
  293.     drp:   sp--;                                          goto *instr[*pc++];
  294.     add:   sp--; *sp += sp[1];                            goto *instr[*pc++];
  295.     sub:   sp--; *sp -= sp[1];                            goto *instr[*pc++];
  296.     mul:   sp--; *sp *= sp[1];                            goto *instr[*pc++];
  297.     quo:   sp--; *sp /= sp[1];                            goto *instr[*pc++];
  298.     mod:   sp--; *sp %= sp[1];                            goto *instr[*pc++];
  299.     bra:          pc += *(signed char*)pc;                goto *instr[*pc++];
  300.     beq:   sp-=2; pc+=(sp[1]==sp[2]?*(signed char*)pc:1); goto *instr[*pc++];
  301.     bne:   sp-=2; pc+=(sp[1]!=sp[2]?*(signed char*)pc:1); goto *instr[*pc++];
  302.     bgt:   sp-=2; pc+=(sp[1] >sp[2]?*(signed char*)pc:1); goto *instr[*pc++];
  303.     print: printf("%d\n",*sp--);                          goto *instr[*pc++];
  304.     stop:  return;
  305.  
  306. }
  307.  
  308. /** sub.c ******************************************************************/
  309. #include        <stdio.h>
  310.  
  311. #ifdef __GNUC__
  312. register void            (* * pc)() asm("$22");
  313. register long            * sp       asm("$23");
  314. #else
  315.          void            (* * pc)();
  316.          long            * sp;
  317. #endif
  318.  
  319. void    LD0   () { sp++; *sp = 0;                         }
  320. void    LD1   () { sp++; *sp = 1;                         }
  321. void    LD2   () { sp++; *sp = 2;                         }
  322. void    LD3   () { sp++; *sp = 3;                         }
  323. void    LD4   () { sp++; *sp = 4;                         }
  324. void    LD5   () { sp++; *sp = 5;                         }
  325. void    LD6   () { sp++; *sp = 6;                         }
  326. void    LDL   () { sp++; *sp = *(int*)pc++;               }
  327. void    DUP   () { sp++; *sp = sp[-1];                    }
  328. void    DUP1  () { sp++; *sp = sp[-2];                    }
  329. void    DUP2  () { sp++; *sp = sp[-3];                    }
  330. void    DUP3  () { sp++; *sp = sp[-4];                    }
  331. void    PUD   () { sp[-1] = *sp; sp--;                    }
  332. void    PUD1  () { sp[-2] = *sp; sp--;                    }
  333. void    PUD2  () { sp[-3] = *sp; sp--;                    }
  334. void    PUD3  () { sp[-4] = *sp; sp--;                    }
  335. void    DRP   () { sp--;                                  }
  336. void    ADD   () { sp--; *sp += sp[1];                    }
  337. void    SUB   () { sp--; *sp -= sp[1];                    }
  338. void    MUL   () { sp--; *sp *= sp[1];                    }
  339. void    QUO   () { sp--; *sp /= sp[1];                    }
  340. void    MOD   () { sp--; *sp %= sp[1];                    }
  341. void    BRA   () { pc += *(int*)pc;                       }
  342. void    BEQ   () { sp-=2; pc+=(sp[1]==sp[2]?*(int*)pc:1); }
  343. void    BNE   () { sp-=2; pc+=(sp[1]!=sp[2]?*(int*)pc:1); }
  344. void    BGT   () { sp-=2; pc+=(sp[1] >sp[2]?*(int*)pc:1); }
  345. void    PRINT () { printf("%d\n",*sp--);                  }
  346. void    STOP  () { exit(0);                               }
  347.  
  348. int             main ()
  349. {
  350.     static void             (* prog [])() = {
  351. #define INST
  352. #define CONST   (void *)
  353. #include "prog"
  354.         };
  355.     static long             stack [64];
  356.  
  357.     pc = prog;
  358.     sp = stack;
  359.     while ( 1 ) (**pc++)();
  360. }
  361.  
  362. /** dir.c ******************************************************************/
  363. #include        <stdio.h>
  364.  
  365. int             main ()
  366. {
  367.     static void             * prog [] = {
  368. #define INST    &&
  369. #define CONST   (void *)
  370. #include "prog"
  371.         };
  372.     void                    * * pc = prog;
  373.  
  374.     static long             stack [64];
  375.     long                    * sp = stack;
  376.  
  377.     goto **pc++;
  378.  
  379.     LD0:   sp++; *sp = 0;                         goto **pc++;
  380.     LD1:   sp++; *sp = 1;                         goto **pc++;
  381.     LD2:   sp++; *sp = 2;                         goto **pc++;
  382.     LD3:   sp++; *sp = 3;                         goto **pc++;
  383.     LD4:   sp++; *sp = 4;                         goto **pc++;
  384.     LD5:   sp++; *sp = 5;                         goto **pc++;
  385.     LD6:   sp++; *sp = 6;                         goto **pc++;
  386.     LDL:   sp++; *sp = *(int*)pc++;               goto **pc++;
  387.     DUP:   sp++; *sp = sp[-1];                    goto **pc++;
  388.     DUP1:  sp++; *sp = sp[-2];                    goto **pc++;
  389.     DUP2:  sp++; *sp = sp[-3];                    goto **pc++;
  390.     DUP3:  sp++; *sp = sp[-4];                    goto **pc++;
  391.     PUD:   sp[-1] = *sp; sp--;                    goto **pc++;
  392.     PUD1:  sp[-2] = *sp; sp--;                    goto **pc++;
  393.     PUD2:  sp[-3] = *sp; sp--;                    goto **pc++;
  394.     PUD3:  sp[-4] = *sp; sp--;                    goto **pc++;
  395.     DRP:   sp--;                                  goto **pc++;
  396.     ADD:   sp--; *sp += sp[1];                    goto **pc++;
  397.     SUB:   sp--; *sp -= sp[1];                    goto **pc++;
  398.     MUL:   sp--; *sp *= sp[1];                    goto **pc++;
  399.     QUO:   sp--; *sp /= sp[1];                    goto **pc++;
  400.     MOD:   sp--; *sp %= sp[1];                    goto **pc++;
  401.     BRA:          pc += *(int*)pc;                goto **pc++;
  402.     BEQ:   sp-=2; pc+=(sp[1]==sp[2]?*(int*)pc:1); goto **pc++;
  403.     BNE:   sp-=2; pc+=(sp[1]!=sp[2]?*(int*)pc:1); goto **pc++;
  404.     BGT:   sp-=2; pc+=(sp[1] >sp[2]?*(int*)pc:1); goto **pc++;
  405.     PRINT: printf("%d\n",*sp--);                  goto **pc++;
  406.     STOP:  return;
  407.  
  408. }
  409.