Fascinating new switch mechanism in assembler

[Dan Lewis]

Hi guys,
I've been working on a lexical analyzer for my new scripting engine, and I
stumbled upon an interesting algorithm.

Essentially:

goto ((charCode << 2)+subroutinePointerArray);

The advantage of this strategy is the elimination of some 90% of the conditional
testing for each character in a string being interpreted (Yay for code that runs
in 40% the time!).  The disadvantage is that you need a table of pointers; if
your cache requirements get too big you can suffer cache thrashing in the
scanner loop which will slow it down even more (-900%?) so you need to keep the
rest of the scanner relatively compact.

Provided with a table of 256 pointers, we would have a single-jump unconditional
branch to get to the correct handler for each character.  Further refining the
process, I'm skipping characters >0x7F, and masking 0x60-0x7F onto 0x40-0x5F;
which gives you essentially the same handler functions (provided you still
preserve the original character somewhere, it makes no difference)  Then instead
of taking 1kb of cache, it only takes 380 bytes for the table at a cost of
introducing two conditional branches; one of which is often mispredicted.

So I have:

// ...
asm
{
naked;
cld;
mov	ECX,	len;
mov	ESI,	p;
xor	EAX,	EAX;
L1:	lodsb;
jecxz	short LX;
mov	EBX,	EAX;
and	EBX,	0xFFFF_FF80;
jnz	BAIL;
mov	EDX,	EAX;
mov	EBX,	EAX;
shr	EDX,	5;
cmp	EDX,	3;
je	short J1;
J2:	shl	EBX,	2;
add	EBX,	jumpGateP;
jmp	[EBX];
J1:	sub	EBX,	byte 0x20;
jmp	short J2; // ...

I'm hoping for some feedback and progression of the idea; and if it's already
been out there for ages, perhaps a link or two on the subject?

I'm just waddling through D, so right now I'm struggling to figure out how to
get my jumpGate table variables to point to functions.  :p  Once I'm done that,
I'll write the rest of it.

(c) Dan Lewis, 2006 (contact me, I'm typically cooperative)
http://murpsoft.com