Date   : Wed, 20 Jul 1994 19:26:17 +0100
From   : jfid@... (James Fidell)
Subject: Re: My 6502 now dead fast!

Stephen Quan wrote:

> I have been examining alternate ways of getting performance.  Who
> else is also using C with one big switch statement to select the
> instruction to be executed?

I've got the same sort of structure.

> I have recently found that this switch statement costs nearly the
> equivalent of 8 if statements, and have thought about using if
> statements instead of a switch statement. Something like a binary
> search.

Would you post your evidence for this ? It would be interesting to see
it. Are you saying that 8 compare/branch instruction pairs could be
executed in the time it takes to reach the code associated with any of
the individual cases in a swtich statement implementation ?

> Let's say opcode 0xa9 (I think is the LDA #immediate) instruction is
> the most frequent instruction how do we remap it so that it is at the
> root of a binary search tree?  Well you do exactly that, you remap it
> there.
> 
>     new_opcode = remap[opcode];
>     if (new_opcode == 0x80)
>       goto LDA_immediate;
>     else
         ^^^^
I think you're missing an if here.

>       goto try_above_0x80;
>     else
>       goto try_below_0x80;

I'm not sure that this will give enough improvement in speed :

       if ( new_opcode == 0x80 )
               goto do_opcode80;
       else if ( new_opcode > 0x80 )
               goto try_above80;
       else
               goto try_below80;

try_above80 :

       if ( new_opcode == 0xc0 )
               goto ...
       else if ( ... )
               goto ...
       else
               goto ...

You'd already have done 3 compare/branch pairs just to identify the
instructions at the second level of the tree.

> Anyhow, implementing this thing is a real pain, especially trying
> to obtain every case in the binary tree.  There is just too many
> goto cases to consider.  I am looking at writing a C program that
> writes the binary tree for me, as well as writing a remapping and
> profile utility that lets me interactively select which instructions
> I want to be moved to the top of the tree.  I think this technique
> is an interesting technique to implement, but I fear that it lacks
> the smoothness and elegance of a plain switch statement.

My gut feeling is that it would be difficult to implement anything in C
that is faster than the code a good compiler will produce for a switch
statement.

James.

-- 
 "Yield to temptation --             |
  it may not pass your way again"    |     jfid@...        
                                     |
        - Lazarus Long               |              James Fidell