Author: Eugene Nalimov
Date: 13:28:30 01/30/03
Go up one level in this thread
On January 30, 2003 at 14:34:34, Ed Schröder wrote:
>On January 30, 2003 at 08:36:55, Russell Reagan wrote:
>
>>On January 30, 2003 at 07:02:39, Ed Schröder wrote:
>>
>>>On January 29, 2003 at 23:29:36, Russell Reagan wrote:
>>>
>>>>http://members.home.nl/matador/chess840.htm#INTRO
>>>>
>>>>From Ed's page...
>>>>
>>>>switch (piece_type) { case 0 : goto empty;
>>>> case 1 : goto white_pawn; // evaluate white pawn
>>>> case 2 : goto white_knight; // evaluate white knight
>>>> case 3 : goto white_bishop;
>>>> case 4 : goto white_rook;
>>>> case 5 : goto white_queen;
>>>> case 6 : goto white_king;
>>>> case 7 : goto black_pawn; // evaluate black pawn
>>>> case 8 : goto black_knight;
>>>> case 9 : goto black_bishop;
>>>> case 10 : goto black_rook;
>>>> case 11 : goto black_queen;
>>>> case 12 : goto black_king; }
>>>
>>>Any reasonable compiler will translate the above into 2 assembler statements,
>>>someling like:
>>>
>>> mov EAX, dword ptr piece_type
>>> JMP TABLE [EAX]
>>>
>>>Nothing can beat that. Just generate an ASM file to see it work.
>>>
>>>Explanation: the trick is that the compiler will generate an internal table (not
>>>visible for the programmer) where it calculates all the effective addresses of
>>>the labels mentioned in the switch/case statement.
>>>
>>>Then using the "piece_type" in register EAX it does an "indirect jump", only a
>>>few cycles.
>>>
>>>Of course, the sequence must be in reasonable order otherwise the compiler will
>>>not recognize the possibility.
>>>
>>>Ed
>>
>>
>>Hi Ed,
>>
>>Let me see if I understand. It is an indirect jump, which will be at least as
>>slow as a mispredicted conditional. The reason this is faster is because since
>>you have 13 possible values for piece_type, you do ONE indirect jump as opposed
>>to (potentially) 12 mispredicted conditionals. Is this your reasoning?
>
>You got it!
>
>Ed
Source file:
int foo (int i)
{
switch (i) {
case 0:
return 100;
case 1:
return 101;
case 2:
return 102;
case 3:
return 103;
case 4:
return 104;
case 5:
return 105;
case 6:
return 106;
case 7:
return 107;
case 8:
return 108;
case 9:
return 109;
case 10:
return 110;
case 11:
return 111;
default:
__assume(0);
}
}
Code emitted by the compiler:
; Listing generated by Microsoft (R) Optimizing Compiler Version 13.10.2179
TITLE s.c
.386P
include listing.inc
if @Version gt 510
.model FLAT
else
_TEXT SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT ENDS
_DATA SEGMENT DWORD USE32 PUBLIC 'DATA'
_DATA ENDS
CONST SEGMENT DWORD USE32 PUBLIC 'CONST'
CONST ENDS
_BSS SEGMENT DWORD USE32 PUBLIC 'BSS'
_BSS ENDS
$$SYMBOLS SEGMENT BYTE USE32 'DEBSYM'
$$SYMBOLS ENDS
_TLS SEGMENT DWORD USE32 PUBLIC 'TLS'
_TLS ENDS
FLAT GROUP _DATA, CONST, _BSS
ASSUME CS: FLAT, DS: FLAT, SS: FLAT
endif
INCLUDELIB LIBC
INCLUDELIB OLDNAMES
PUBLIC @foo@4
; Function compile flags: /Ogty
_TEXT SEGMENT
@foo@4 PROC NEAR
; _i$ = ecx
; File c:\repro\s.c
; Line 3
jmp DWORD PTR $L568[ecx*4]
$L546:
; Line 5
mov eax, 100 ; 00000064H
; Line 31
ret 0
$L547:
; Line 7
mov eax, 101 ; 00000065H
; Line 31
ret 0
$L548:
; Line 9
mov eax, 102 ; 00000066H
; Line 31
ret 0
$L549:
; Line 11
mov eax, 103 ; 00000067H
; Line 31
ret 0
$L550:
; Line 13
mov eax, 104 ; 00000068H
; Line 31
ret 0
$L551:
; Line 15
mov eax, 105 ; 00000069H
; Line 31
ret 0
$L552:
; Line 17
mov eax, 106 ; 0000006aH
; Line 31
ret 0
$L553:
; Line 19
mov eax, 107 ; 0000006bH
; Line 31
ret 0
$L554:
; Line 21
mov eax, 108 ; 0000006cH
; Line 31
ret 0
$L555:
; Line 23
mov eax, 109 ; 0000006dH
; Line 31
ret 0
$L556:
; Line 25
mov eax, 110 ; 0000006eH
; Line 31
ret 0
$L557:
; Line 27
mov eax, 111 ; 0000006fH
; Line 31
ret 0
npad 1
$L568:
DD $L546
DD $L547
DD $L548
DD $L549
DD $L550
DD $L551
DD $L552
DD $L553
DD $L554
DD $L555
DD $L556
DD $L557
@foo@4 ENDP
_TEXT ENDS
END
Thanks,
Eugene
>
>
>>Thanks,
>>Russell
>>
>>
>>
>>>
>>>>On one portion of Ed's discussion of Rebel (see above), he talks about using
>>>>"indirect addressing". I get the impression from Ed's words that this method is
>>>>supposed to fast. I understand his discussion to mean that if you create a
>>>>switch statement like he does, you create a jump table and avoid a bunch of
>>>>conditionals.
>>>>
>>>>However, in past discussions, I recall hearing that using a function pointer is
>>>>going to be at least as slow as conditional, so I asked someone, and was told
>>>>that Ed's example should be no different than using a function pointer or
>>>>virtual functions.
>>>>
>>>>Ed talks about this method as if it is a good thing to use. So what is the
>>>>advantage of it? Either someone is mistaken, or Ed and the guy I talked to are
>>>>talking about different things.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.