Author: Robert Hyatt
Date: 19:48:17 01/30/03
Go up one level in this thread
On January 30, 2003 at 19:57:51, Matt Taylor wrote:
>On January 30, 2003 at 17:16:44, Robert Hyatt wrote:
>
>>On January 30, 2003 at 14:32:37, Ed Schröder wrote:
>>
>>>On January 30, 2003 at 13:03:49, Robert Hyatt 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.
>>>>
>>>>I would hope *not*.
>>>
>>>
>>>>it should generate:
>>>>
>>>> mov eax, piece_type
>>>> cmp eax,0
>>>> jb skip
>>>> cmp eax,12
>>>> jna table[eax]
>>>> skip:
>>>
>>>Of course, but no need to go into ASM details. The point is its speed, replacing
>>>a whole block of c-code into a few ASM instructions.
>>>
>>>Also in ASM I don't have to do the 0-12 range check because I already know the
>>>range is valid, so just 2 instructions :)
>>
>>The advantage of doing it in ASM. However, trying to make it happen in C is
>>not so easy, although a few compilers have a #pragma you can use to turn off the
>>range checking...
>>
>>
>>>
>>>
>>>>Somebody had _better check the switch values.
>>>
>>>>BTW the jna table[eax] is not particularly efficient from a prediction point of
>>>>view.
>>>
>>>???
>>>
>>>Please explain.
>>>
>>
>>When you fetch the branch, you don't yet know where it is going. So there is no
>>way to
>>predict anything except "it will fall through" even though the branch is
>>unconditional, so
>>you stuff the pipeline up a bit until it can evaluate table[eax] into an
>>address, and then
>>check that against the BTB for a match.
>>
>>I haven't tried to study intel's stuff on how this effects the PIV pipeline, but
>>I suspect it is at least a bit "messy"...
>
>Though this is irrelevant to your point, I am perfectionist. There is no
>conditional indirect branch instruction. It ends up being this:
>
> ja nojmp
> jmp [table+eax*4]
>nojmp:
>
You are right. I have tried that more than once, but do it so infrequently
that I don't recall until the assembler pukes. :)
I had forgotten the *4 also, and was thinking that maybe Ed had already scaled
the thing which means my cmp would have had the wrong value in that case.
>You are quite right that it is "messy." It grows increasingly messy with every
>new processor as they always increase pipeline length. A pipeline flush on P4 is
>more than 20 clocks lost. (I can't recall an exact figure, but it is in that
>arena.)
>
>-Matt
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.