From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
Subject: Writing a super-fast PDP-8 emulator.
Date: Wed, 9 Sep 1992 21:12:25 GMT
Organization: University of Iowa, Iowa City, IA, USA

From article <1992Sep9.200035.24633@news.uiowa.edu>,
by dsiebert@icaen.uiowa.edu (Doug Siebert):
> 
> Heh!  You guys have finally succeeded where cjl failed many times
> -- you have provided a concrete example of a case where assembly will
> always produce more efficient code than C...

Try FORTRAN 66, then.  That's right, FORTRAN.  That's because FORTRAN
has a fossil in it called the assigned GOTO, a lovely bit that lets you
assign a label to an integer variable then do an indirect GOTO off that
integer.  Here's the code:

C
C The following array is used to decode instructions
C
	INTEGER I(4096)
C
C The following data structures represent the machine state
C
	INTEGER M(4096)
	INTEGER PC,AC
C
C The main program begins here by setting up the instruction decoding array
C
	ASSIGN 90000 TO I(0)
	ASSIGN 90001 TO I(1)
	ASSIGN 90002 TO I(2)
		...
	ASSIGN 97777 TO I(4095)
C
C Now, we initialize memory, the program counter, and all that
C
		...
C
C Now, we fetch and decode the first instruction
C
	GOTO M(PC)
C
C The following blocks of code interpret the machine instructions
C
C AND 0
C
90000	PC = PC + 1
	AC = IAND(AC,M[0])
	GOTO M[PC]
C
C AND 1
C
90001	PC = PC + 1
	AC = IAND(AC,M[1])
	GOTO M(PC)

And so on.  Admittedly, the code will be big, but the request was for the
flat-out fastest interpreter, and this meets that requirement.  The machine
code it generates will, on decent compilers, be identical to the code
you'd get by crafting the same gunk out of assembly code, and if you've
got megabytes to kill, it's really not a bad approach to the problem of
writing a PDP-8 interpreter.  Actually, it won't even kill megabytes!
You've got 4K cases, most of which will take around 4 instructions, so
that's only 16K instructions (or 64K bytes on a typical modern RISC),
not a bad price to pay if speed is your main objective.

In C, you'd be better off using a switch statement, along the following
lines:

for (;;) {
	switch M[pc] {
	case 00000: (* AND 0 *)
		pc = pc + 1;
		ac = ac & M[0];
		break;
	case 00001: (* AND 1 *)
		pc = pc + 1;
		ac = ac & M[1];
		break;
	...
}	}

This will generate an indirect indexed branch identical to that
generated for the assigned goto's above (because the jump-table is not
sparse), and if your compiler understands the wasted effort in doing
a jump to a jump, it'll recognize that it can replace the jump
represented by the break with the indirect indexed jump represented by
the switch statement.

So, the result I get is that FORTRAN, C and assembly -can- all produce
the same object code for this problem.  I suspect that most C compilers
-would- fail on the code re-ordering involved above because 4096 way
switch statements are likely to clog things up.  Most should, however,
manage to make all the break statements into jumps to the indirect
indexed jump at the top of the loop, which isn't that much slower.

So, this should get most PDP-8 instruction executed in about 3 to 4
instructions on the host machine, with one more required for indirect
addressing, and with some microcoded instructions requiring more.
All in all, this means that, using a DEC Alpha to simulate a PDP-8,
we should be able to get execution speeds of well over 10 MIPS.

				Doug Jones
				jones@cs.uiowa.edu