Re: Emulator Project Question

[Colin Klipsch <klipsch@mail630.gsfc.nasa.gov>]

Steve Mentzer wrote:

> Keeping a cache of "dirty" bytes would be really expensive, as you would
> have to do it byte-by-byte. That would not only be very inefficient, but
> time consuming.  Which is why I was noting that while it is feasible to
> perform a code-translation to x86, it is propably going to be a
> rube-goldberg algorithm!

Oh, I agree entirely.

> > There seems little advantage in Java's JITC unless the compiled
> > routine is likely to be executed more than once, regardless of any
> > loops.  [...]  This is my impression at least, having just
> > scanned the JVM architecture specs; the bytecodes represent very
> > simple operations on a stack-based machine.  (True?)

> The MS .Net CLR is similar in architecture to a java VM. It is essentially a
> "rich cpu", where exception handling and standard types are built in, and
> the instruction architecture is relatively limited and simple to port to
> various environments.

Incidentally, does the CLR architecture prohibit self-modifying code,
like the JVM?  And does it support security verification?  (That would
be a welcome change of stripes for Microsoft.)

> > > > Each element points to a function that handles that particular opcode.
> > > > Simply do a array[opcodenumber]; and you can call the emulated CPU.
> >
> > Actually, I recommend using a dense "switch" statement, not a function
> > pointer table.  A *dense* (all case values from 0 and N are present,
> > even if some of them do nothing) and *large* (N is at least ten or so;
> > 256 is certainly plenty) switch statement will be optimized into a
> > relative branch using an inline lookup table, indexed by the switch
> > expression.  Any C/C++ compiler with the sense that God gave a kitten
> > will do this, and you can avoid the function call overhead that you
> > are otherwise *very* likely to incur.

> This makes *alot* of sense. A table of function pointers, while probably
> retained in the data working set, still would have to make a long jump in
> most cases, depending on how the code segments are linked. I suspect that
> transition would be expensive!

Yes, the linker is yet another dragon waiting for its chance to
immolate your lovingly crafted code.  I suppose you might hope to foil
it by defining all your opcode implementation functions in the same
compilation unit as your main interpreter function.  You'd then hope
that the compiler and linker would cooperate to produce "near" calls
rather than "far" in the final executable, whatever that might mean
for the host architecture.  (On the 680x0 Mac for example, there are
several grades of near and far function calls, depending on all sorts
of things that no one wants to contemplate anymore.)

Still, best not to give the linker the temptation to scatter your
functions hither and yon in the address space, or to link them up in
the most general and costly way possible.

> A case statement, while not being pretty to look at (understatement) ...

Pretty non-pretty, to be sure.  Although, by using macros to factor
out redundant bits of code -- e.g. the computation of the
Absolute-X-Indexed effective address is the same for every opcode that
needs it -- and, by putting multiple short statements on the same
line, you can keep the humongous switch statement relatively tame and
compact.  (Also note that the "case" statements don't need to be in
numerical order; they can be grouped by common behavior, making the
interpreter's source code _almost_ readable to people other than the author.)

Of course, after adding comments so that you can remember what the
h*ll you were thinking last year when you wrote this big mess, the
switch bloats out again to a few hundred lines.  Ah well.

Anyway, don't you have the same "ugliness" problem when implementing
each opcode as an external function?

> ... would
> allow the compiler to perform heavy optimization and most likely retain the
> vast majority of the code to benefit from the integral branch prediction on
> the P3/P4/K7 processors.

Right.  Or on the PowerPC, or any of the modern processors that have
branch prediction.

Also, keeping the opcode interpreter as one self-contained function
_guarantees_ (well, more or less) that certain high traffic variables
can be held in registers.  For example, the 6502's PC and P registers
are read and modified in all, or nearly all, opcodes.  If you choose
to tally instruction cycle times, then your "clock" variable is also
modified after every opcode.  Best therefore to put such values in
C/C++ "register" variables and keep them there for as long as you're interpreting.

In contrast, calling external functions to execute the opcodes will
likely defeat this opportunity for speed improvement, and it is a
_tremendous_ improvement, worth fighting for.  Depending on the
architecture's conventions and the compiler's whim, a function call
will perhaps shuffle registers around -- pointlessly, as a human can
tell but the compiler often can't -- or it will waste time saving and
restoring registers on the stack, or writing and reading variables
from memory.

(For example, _you_ know that your external CLC function doesn't
modify the Intel's BX register.  The compiler doesn't however, and it
uselessly pushes and pops BX from the stack before and after the
function call, or if it's really dumb, inside the function's prolog
and epilog.  Or, _you_ know that the 6502's PC value is in high demand
and should be kept in a single register during opcode interpretation. 
But the compiler doesn't figure this out, and wastes time writing PC
to memory after every modification, and reading it from memory before
every use.)


Doug Kwan wrote:

> I once did an Apple II emulator that does dynamic translation from
> 6502 instructions to RISC instructions. Naively, I did the translation
> in a page unit (256 byte). I ran into the problem of finding the
> start of an instruction. Unlike RISC processors, 6502 instructions
> need not to be aligned. They could start everywhere. Worst, sometimes
> people wrote codes that jump into the middle of one instruction because
> the operand can be used an another instruction.

Ah!  I had forgotten that trick.  (Not sure that I'm happy to remember it.)

>> Actually, I recommend using a dense "switch" statement [...]

> If you use gcc, you could use labels and store them into an array.
> This is not portable though as it is a gcc feature.

I believe Metrowerks' Codewarrior also supports this now, as an
extension, along with other gcc goodies.  Also, I believe that gcc
supports case _ranges_, which can save some typing.

... if, as you say, you're willing to sacrifice portability.

> This is just like you what you suggest, expect you don't need
> to do the bound check. If you want to write a really tight
> dispatch loop, every cycle counts.

Agreed.  And yes, useless range checking is one drawback of employing
a C/C++ switch statement as the opcode interpreter.  However, I've
found that you can coax most compilers into eliminating _one_ of the
comparisons if you do the following:

  (1) Switch on an unsigned, not signed, value.
  (2) Be sure to include a "case 0", even if its body is empty.

This forces the compiler to ponder a ">=" comparison of an unsigned
integer against zero, which it happily optimizes away.  (Yes,
_happily_.)  You're still stuck with the upper bound check though,
even if that bound is 255 and the switch expression is of type
"unsigned char" -- and there is therefore no way the upper bound could
ever be exceeded.  This is a frustating result, but you can live with
it.  (Well, I can anyway.)

In fact, I've been disappointed to observe that no C/C++ compiler I've
worked with (not that that's a large number) can recognize a fully
dense switch on an unsigned character as a perfect opportunity to
eliminate the range checking entirely.  Perhaps I'm just not feeding
the right combination of options to these compilers.

> : What specifically do I mean by function call overhead?  On most
> [...]
> : entry the same, after all.)
> 
> Plus you cannot store important variables into registers.

Exactly.  (See above discussion.)

> : Mind you, on today's processors, which are so much faster than the
> : 1-MHz 6502 inside the Apple II, you can get away with a lot of casual
> : attitude.

> Nah... You don't really want the emulator to be a CPU hog. Most
> people are running multi-tasking operating system today. There
> are usually other programme running on your computer.

> As a programmer, I always think that one should write codes that
> are efficient.

Hard to argue with that as a guiding principle, for any undertaking.

Perhaps I shouldn't have said "a lot" of casual attitude.  I certainly
wouldn't advocate writing an Apple II emulator in Perl (or Hypercard,
as someone has actually proposed), even on today's machines.  Nor
would I make use of the "clever" features of C++, like functors or
virtual methods, precisely because of their runtime cost.

> For performance tuning, you may still want to write a _small_ part
> of your emulator in assembly of the host.

Ah, now you have _definitely_ sacrificed portability!

> : or (B) writing a JIT : compiler for 6502-to-native machine code.

> But it is a fun thing to do :)

Gaaah!

> I will go by the 80/20 or 90/10 rule. Speed up only the 20% that
> account for the 80% of the run time. If it is a hot and small routine
> you may want to rewirte the assembly, or rethink the implementation
> to get better codes in C/C++ as least.

We largely agree here.  My thinking though is that today's computers
-- in fact even yesterday's computers, going back ten years -- are
easily fast enough to emulate an Apple II at its authentic speed, if
you code the emulator in C/C++ and if you write the big bottlenecks
(like the instruction interpreter, and the video renderer) in a style
_resembling_ assembly language.  Here, it certainly helps to have
programmed in assembly language before, preferably in one's reckless
youth, and to know what sorts of practical jokes compilers like to
play when they generate code.

As a personal choice, I wouldn't bother with assembly language
anymore, except maybe at gunpoint.  (And even then, you'd have to give
me a minute.)  It's just so time consuming to get right, to keep free
of bugs, and of course, it doesn't port well at all.


Paul Schlyter wrote:

> Some emulators even introduce delay loops to
> slow down the emulated Apple II which otherwise woiuld run too fast
> for e.g. some Apple II games.  And it makes little sense to work hard
> to make your emulator as fast as possible, only to later find out that
> it runs _too_ fast and needs to be slowed down....

Such "problems" will only get worse, of course, as times goes on and
computers keep getting faster.  This just means of course that you
have to pace the emulation with real time somehow, and allow running
"as fast as possible" as an option.

Just for fun: on a 1 GHz machine, if we spend about 25 cycles worth of
host-CPU instructions for each emulated 6502 instruction, then the
effective emulation speed will be about 40:1.  (I'm ignoring all kinds
of complications.)

A forty to one speed ratio!  How many Apple II programs would actually
benefit from that?  (Well, that "waking up" phase in The Prisoner is a
good case...)


-- Colin K.