On 7/24/2012 3:33 PM, Dmitry Olshansky wrote:
On 25-Jul-12 01:40, Walter Bright wrote:
On 7/24/2012 12:50 PM, Dmitry Olshansky wrote:
are the same (same as in same number of indirections).
switch (code[pc++])
and
goto code[pc++]()
are the same, too.
It's not. Let's get to assembly then. It's an illustration as I'm no
expert and
may have made some illegal shortcuts in this listing.
goto code[pc++]() is roughly:
mov ecx, [ebx]
inc ebx
jmp [ecx]
jmp code[ecx]
There is no code just jump [ecx]. The offset is included already.
I'm not seeing where "code" is in the asm code you presented.
switch(code[pc++]) is:
mov ecx, [ebx]
inc ebx
mov ecx, [edx+ecx] // assuming jump table is at edx
jump [ecx]
jmp jumptable[ecx]
Damn, it's not the same. If in the above ecx is pc++, here it it code[pc++] i.e.
needs to be loaded. The whole point. And yes, I *didn't* object that it's still
1 JUMP. I'm more focused on extra work being done.
Sorry, I have no idea why it is not the same. jumptable is a static array, and
so does not need to be loaded into a register. And code[] needs to be loaded
from somewhere, and it looks like it's omitted from your example.
Please post source code example so I understand what you mean.
OK. It sure gets confusing.
Here is an article that shows the big picture of to what I want to do:
http://www.complang.tuwien.ac.at/anton/lvas/sem06w/revucky.pdf
It contains some advanced techniques that are out of scope of current topic but
Introduction & Background are short and full of relevant facts.
And for the sample code here it is, casts are ommited for brevity.
First one is "if I had a way to have enforced tail call to function or take
address of label".
Let's assume labels:
//GLOBALS
size_t[] bytecode = firstPassCompile("my_source.ds"); //say it's DMDscript ;)
bool jitted = false;
void run(size_t pc)
{
//so here bytecode is normal bytecode if jitted != true
//for simplicity sake it starts with some number e.g.:
// 0 - op_1
// 1 - op_2, etc.
if(!jitted)
{
int i=0;
//1:1 map of each label that servers specific opcode
static tabulated_ops[] =
[ &L_op1, &L_op2, &L_op3, ... ];
while(notEndOfProgram(bytecode[i]) )
{
size_t n = bytecode[i];
//store real target
bytecode[i] = tabulated_ops[n];
//advance by some size, skipping operands etc.
i += opSize(n);
}
}
//interpret:
goto bytecode[pc];
//<---- never gets here
L_op1:
//do my op1 thing
pc += x;
//DISPATH:
goto bytecode[pc]; // load address at pc & jump to it
L_op2:
//do some other thing
pc += y;
//DISPATH:
goto bytecode[pc]; // load address at pc & jump to it
L_op3:
//my other op, jumps back
pc -= ...;
//DISPATH:
goto bytecode[pc]; // load address at pc & jump to it
...
L_opN:
...
goto bytecode[pc]; // load address at pc & jump to it
}
Now the same thing with switches.
And before you ask -
NO! Single switch won't do as it would have successful branch prediction rate of
as bad as about 2% (see the article!). The more opcode types the worse
prediction is.
I see what you mean, but this could be done with final switch by the compiler,
as I explained to bearophile.
Anyway here it goes:
//GLOBALS
size_t[] bytecode = firstPassCompile("my_source.ds"); //say it's DMDscript ;)
void run(size_t pc)
{
//here we don't JIT to real addresses beforehand
//as jump tables somehow should be good enough
// Okay...
//interpret:
switch(bytecode[pc])
{
L_op1:
case 0:
//do my op1 thing
pc += x;
//DISPATCH:
//here comes trouble - 1st of N nearly identical tables??
switch(bytecode[pc])
{
case 0: goto L_op1;
case 1: goto L_op2;
...
}
L_op2:
case 1:
//do some other thing
pc += y;
//DISPATCH:
//here comes trouble - 2nd table?
switch(bytecode[pc])
{
case 0: goto L_op1;
case 1: goto L_op2;
...
}
L_op3:
case 2:
//my other op, jumps back
pc -= ...;
//DISPATCH:
//here comes trouble - 3rd table?
switch(bytecode[pc])
{
case 0: goto L_op1;
case 1: goto L_op2;
...
}
...
L_opN:
case N-1:
...
//DISPATCH:
//here comes trouble Nth table ... time to count overhead
switch(bytecode[pc])
{
case 0: goto L_op1;
case 1: goto L_op2;
...
}
}//end of giant switch
}
I see what you mean here, too. Thanks for the explanation. It never occurred to
me that one could write code like that, but I see the point, and doing jump
table merging could be done fairly easily. No new language feature is required.
