Hello:
On 06 Nov 2010, at 21:42, Levente Uzonyi wrote:
On Sat, 6 Nov 2010, Igor Stasenko wrote:
I suppose its related to fact, that with small number of cases (like up to 16) its not worth using indirect jump, because with branch prediction you can achieve same or even better performance. That's why i think, modern compilers do not using jump tables. Having more than 16 number of cases, is an edge case. Not saying about 256.
I expect a compiler to generate the fastest possible code, if I ask for that. I think we agree, that gcc doesn't do this.
I don't really follow this discussion. Are you assuming that GCC is not using jumptables? Well, if I read the assembly code correctly, it does. See below.
However, Levente assumed that using jumptables is threaded code. But, no, threaded code is something different: http://en.wikipedia.org/wiki/Threaded_code Michael Haupt has a few nice slides visualizing what threaded code is about :) The idea is that you try to avoid the jump back to the switch/case and chain the bytecode implementations for a given method.
Best regards Stefan
void Squeak_Interpreter::dispatch(u_char currentByte) { if (Check_Prefetch) have_executed_currentBytecode = true; switch (currentByte) { case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: case 10: case 11: case 12: case 13: case 14: case 15: pushReceiverVariableBytecode(); break; case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23: case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31: pushTemporaryVariableBytecode(); break;
GCC 4.2 -O3
0x00013b50 <+0000> push %ebp 0x00013b51 <+0001> mov %esp,%ebp 0x00013b53 <+0003> mov 0x8(%ebp),%edx 0x00013b56 <+0006> movb $0x1,0x4171(%edx) 0x00013b5d <+0013> movzbl 0xc(%ebp),%eax 0x00013b61 <+0017> jmp *0xc32ec(,%eax,4) 0x00013b68 <+0024> mov %edx,0x8(%ebp) 0x00013b6b <+0027> leave 0x00013b6c <+0028> jmp 0x42d50 <_ZN18Squeak_Interpreter15unknownBytecodeEv> 0x00013b71 <+0033> mov %edx,0x8(%ebp) 0x00013b74 <+0036> leave 0x00013b75 <+0037> jmp 0x46e10 <_ZN18Squeak_Interpreter20pushNewArrayBytecodeEv> 0x00013b7a <+0042> mov %edx,0x8(%ebp) 0x00013b7d <+0045> leave 0x00013b7e <+0046> jmp 0x43950 <_ZN18Squeak_Interpreter25pushActiveContextBytecodeEv> 0x00013b83 <+0051> mov %edx,0x8(%ebp) 0x00013b86 <+0054> leave 0x00013b87 <+0055> jmp 0x44450 <_ZN18Squeak_Interpreter20duplicateTopBytecodeEv> 0x00013b8c <+0060> mov %edx,0x8(%ebp) 0x00013b8f <+0063> leave 0x00013b90 <+0064> jmp 0x42ec0 <_ZN18Squeak_Interpreter16popStackBytecodeEv> 0x00013b95 <+0069> mov %edx,0x8(%ebp) 0x00013b98 <+0072> leave 0x00013b99 <+0073> jmp 0x45f50 <_ZN18Squeak_Interpreter26secondExtendedSendBytecodeEv> 0x00013b9e <+0078> mov %edx,0x8(%ebp) 0x00013ba1 <+0081> leave
Levente
Btw, I was also thinking that compilers generating jump tables for case statements.