goto vs switch

[Marcus]

I don't use a C compiler that supports this, but I've heard that gcc does. Has anyone tried using 'goto' with pointers to labels instead of switch/case for the instruction loop? Which one is the fastest?

Code: [Select]

do {
  switch pc[0] {
    case ADD:
      ...
    case SUB:
      ...
  }
  pc++;
} while (1);

vs

Code: [Select]

do {
  goto pc[0]
  ADD:
    ...
  SUB:
    ...
  pc++;
} while (1)

In version 4 of naalaa I stored function pointers in the instructions and called them in the loop. In version 5 (the current one) I switched to switch/case. Sadly the impact on the speed was marginal.

[jcfuller]

Marcus,
  I have not done any timing tests but currently Bcx translates this:

Code: [Select]

$ONEXIT "GCTDC.BAT $FILE$ -m32"
DIM A As Integer
A = 4
SELECT CASE A
    CASE 1
        print "A = 1"
    CASE 2
        print "A = 2"
    CASE 3
        print "A = 3"
    CASE 4
        print "A = 4"
    CASE ELSE
        print "A = ?"
        
End Select

To This:

Code: [Select]

// *********************************************************************
// Created with BCX32 - BASIC To C/C++ Translator (V) 8.8.7.0 (2012/02/06)
//                 BCX (c) 1999 - 2012 by Kevin Diggins
// *********************************************************************
//              Translated for compiling with a C Compiler
// *********************************************************************
#include <windows.h>    // Win32 Header File
#include <windowsx.h>   // Win32 Header File
#include <commctrl.h>   // Win32 Header File
#include <commdlg.h>    // Win32 Header File
#include <mmsystem.h>   // Win32 Header File
#include <shellapi.h>   // Win32 Header File
#include <shlobj.h>     // Win32 Header File
#include <richedit.h>   // Win32 Header File
#include <wchar.h>      // Win32 Header File
#include <objbase.h>    // Win32 Header File
#include <ocidl.h>      // Win32 Header File
#include <winuser.h>    // Win32 Header File
#include <olectl.h>     // Win32 Header File
#include <oaidl.h>      // Win32 Header File
#include <ole2.h>       // Win32 Header File
#include <oleauto.h>    // Win32 Header File
#include <winsock.h>    // Win32 Header File
#include <process.h>    // dos
#include <conio.h>      // dos
#include <direct.h>     // dos
#include <io.h>         // dos
#include <ctype.h>      // dos/linux
#include <fcntl.h>      // dos/linux
#include <math.h>       // dos/linux
#include <stdio.h>      // dos/linux
#include <string.h>     // dos/linux
#include <stddef.h>     // dos/linux
#include <stdlib.h>     // dos/linux
#include <setjmp.h>     // dos/linux
#include <time.h>       // dos/linux
#include <stdarg.h>     // dos/linux


// *************************************************
// Instruct Linker to Search Object/Import Libraries
// *************************************************
#if !defined( __LCC__ )
#pragma comment(lib,"kernel32.lib")
#pragma comment(lib,"user32.lib")
#pragma comment(lib,"gdi32.lib")
#pragma comment(lib,"comctl32.lib")
#pragma comment(lib,"advapi32.lib")
#pragma comment(lib,"winspool.lib")
#pragma comment(lib,"shell32.lib")
#pragma comment(lib,"ole32.lib")
#pragma comment(lib,"oleaut32.lib")
#pragma comment(lib,"uuid.lib")
#pragma comment(lib,"odbc32.lib")
#pragma comment(lib,"odbccp32.lib")
#pragma comment(lib,"winmm.lib")
#pragma comment(lib,"comdlg32.lib")
#pragma comment(lib,"imagehlp.lib")
#pragma comment(lib,"version.lib")
#else
#pragma lib <winspool.lib>
#pragma lib <shell32.lib>
#pragma lib <ole32.lib>
#pragma lib <oleaut32.lib>
#pragma lib <uuid.lib>
#pragma lib <odbc32.lib>
#pragma lib <odbccp32.lib>
#pragma lib <winmm.lib>
#pragma lib <imagehlp.lib>
#pragma lib <version.lib>
#endif
// *************************************************
// End of Object/Import Libraries To Search
// *************************************************

// *************************************************
//        User's GLOBAL ENUM blocks
// *************************************************

// *************************************************
//            System Defined Constants
// *************************************************

#define cSizeOfDefaultString 2048

// *************************************************
//            User Defined Constants
// *************************************************

// *************************************************
//          User Defined Types And Unions
// *************************************************


// *************************************************
//            User Global Variables
// *************************************************

static int     A;


// *************************************************
//            User Global Initialized Arrays
// *************************************************



// *************************************************
//                 Runtime Functions
// *************************************************


// ************************************
//       User Subs and Functions
// ************************************

// *************************************************
//                  Main Program
// *************************************************

int main(int argc, char *argv[])
{
A= 4;
if(A==1 )
  {
    printf("%s\n","A = 1");
    goto L1000;
  }
if(A==2 )
  {
    printf("%s\n","A = 2");
    goto L1000;
  }
if(A==3 )
  {
    printf("%s\n","A = 3");
    goto L1000;
  }
if(A==4 )
  {
    printf("%s\n","A = 4");
  }
else // case else
  {
    printf("%s\n","A = ?");
  }
L1000:; // SelectState[PusherSelectState].CaseFlag 4
  return 0;   /* End of main program */
}


James

[SteveA]

Sure, in the past I've used goto's in C.
I've not tested them for their performance value, but, they work just fine.
And, I've never found a reason to not use goto.

I have always looked at higher level code from the perspective of Assembler.
In other words, what does this statement translate to.
There is nothing simpler than a simple jump statement.
In Assembler you see jumps (goto's) everywhere.

[Marcus]

The question is if they are faster than the "jump tables" that most c compilers generate for switch/case. Something like:

Code: [Select]

switch (instruction) {
  case ADD:
    ...
  case SUB:
    ...
}

is translated to something like (or pretty far from, I know) this by the c compiler:

Code: [Select]

JMP the_jump_table[instruction]
the_jump_table_ADD:
  ...
  JMP end_of_the_jump_table
the_jump_table_SUB:
  ...
  JMP end_of_the_jump_table
...
end_of_the_jump_table:

But if you, directly in c, can load the memory address of a label into a variable you should be able to execute your vm instructions without the use of a jump table when translated to assembler. You'd just jump (goto) the adress stored in the instruction. It should make quite a difference in speed, I think. But I'm not sure

The difference in speed would hopefully be the difference between:

Code: [Select]

a = 10
b = 0
for (i = 0; i < 1000000; i++) {
  switch (a) {
    case 10:
       b += 1;
       break;
  }
}

and

Code: [Select]

a = 10
b = 0
for (i = 0; i < 1000000; i++) {
  goto add_code;
  add_code:
    b += 1;
    goto end_of_thing;
  end_of_thing:
}

... I'll just try something similar to that to start with.

[Charles Pegge]

Interesting question.

In OxygenBasic, goto is strictly for labels but it is possible to use the jmp instruction directly, and this will accept a label or a simple variable.

Code: [Select]



'SETUP

sys a[10],j
a<=@AA,@BB,@CC 'map labels into table

'TEST

j=a[2] : jmp j


AA:
print "AA"
jmp done
BB:
print "BB"
jmp done
CC:
print "CC"
jmp done

done:

This technique, I would say, will outperform a switch statement of more than 5 cases. But I have not tried to measure it.

Charles

[Marcus]

I wrote a test program, a more advanced version of the one above (one that the c compiler couldn't optimize in some silly way to fool me). Using switch/case was faster than just doing two FIXED branches! I've looked at the assembler output but still can't figure out how the hell the generated jump table can be faster than pure branching

Code: [Select]

#include <stdlib.h>
#include <stdio.h>
#include <windows.h>

int main(void) {
int i, j;
int b = 0;
int a = 10;
unsigned long t = timeGetTime();

printf("start\n");
for (i = 0; i < 10000000; i++) {
for (j = 0; j < 100; j++) {
a = rand()%3 + 10;
switch (a) {
case 10:
b = (b + 1)%100;
break;
case 11:
b = (b + 1)%100;
break;
case 12:
b = (b + 1)%100;
break;
}
}
}
printf("end %d\n", timeGetTime() - t);

t = timeGetTime();
printf("start\n");
for (i = 0; i < 10000000; i++) {
for (j = 0; j < 100; j++) {
a = rand()%3 + 10;
goto add_ten;
add_ten:
b = (b + 1)%100;
goto end_of_thing;
end_of_thing:
}
}
printf("end %d\n", timeGetTime() - t);


return EXIT_SUCCESS;
}
The first part, with the switch/case, takes less time than the latter.

[Marcus]

No, sorry, my bad. The name of the generated executable was changed for some reason and I was running and old version of the test program. The fixed branch version is more than twice as fast

This calls for a rewrite of the naalaa interpreter core! I figure I can do this part in assembler rather than changing compiler to gcc. Finally I can beat javascript (that uses JIT) with pure interpreted code

EDIT: Charles, I'm honoured by the fact that you even wrote something in this thread. In my world you're no less than a god.

EDIT2: Steve and jc, of course you're gods aswell Thanks for your replies.

[SteveA]

But if you, directly in c, can load the memory address of a label into a variable you should be able to execute your vm instructions without the use of a jump table when translated to assembler. You'd just jump (goto) the adress stored in the instruction. It should make quite a difference in speed, I think. But I'm not sure

I think that is a valid assumption.

Steve

[Marcus]

But if you, directly in c, can load the memory address of a label into a variable you should be able to execute your vm instructions without the use of a jump table when translated to assembler. You'd just jump (goto) the adress stored in the instruction. It should make quite a difference in speed, I think. But I'm not sure

I think that is a valid assumption.

Steve

Yes, that was my hope. But the difference is just one level of dereferencing/indirection, and as I'm lousy at the tech details I never know how much time extra these things take. I'm glad this one turned out to be a winner, because I've been searching for one