Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: typical nps on single cpus

Author: Dave Gomboc

Date: 08:34:37 02/15/00

Go up one level in this thread


On February 15, 2000 at 03:16:29, Dan Newman wrote:

>On February 15, 2000 at 02:03:28, Dave Gomboc wrote:
>
>>On February 15, 2000 at 01:53:43, Dan Newman wrote:
>>
>>>On February 14, 2000 at 22:53:03, Dave Gomboc wrote:
>>>
>>>>On February 14, 2000 at 22:18:18, Dan Newman wrote:
>>>>
>>>>>On February 14, 2000 at 15:25:24, Dave Gomboc wrote:
>>>>>
>>>>>>On February 14, 2000 at 14:38:14, José de Jesús García Ruvalcaba wrote:
>>>>>>
>>>>>>>On February 14, 2000 at 03:16:33, Dave Gomboc wrote:
>>>>>>>
>>>>>>>[big snip]
>>>>>>>>
>>>>>>>>How much faster do you think a switch is than using virtual dispatch?
>>>>>>>>
>>>>>>>>Dave
>>>>>>>
>>>>>>>What is a virtual dispatch?
>>>>>>>José.
>>>>>>
>>>>>>What you get if you went OO-crazy and had a piece class with descendents for
>>>>>>pawn, knight, bishop, etc., then called a member function.
>>>>>>
>>>>>>Dave
>>>>>
>>>>>I've tried to go OO-crazy once or twice, but the one thing that seemed to
>>>>>get in the way and require some really hairy solution was pawn promotion.
>>>>>The only thing I could think of doing was to maintain a pool of extra
>>>>>promotion pieces and perhaps overload new and delete in the piece class to
>>>>>get the new piece from this pool.  But all that extra mechanism seemed like
>>>>>too much...
>>>>>
>>>>>-Dan.
>>>>
>>>>I'm not suggesting that going OO-crazy is a good idea (hence my name: OO-crazy
>>>>:-).  I'm just wondering how much longer do you think a virtual dispatch would
>>>>take than a standard switch statement.
>>>>
>>>>(Assuming there are no classes being loaded dynamically at run-time, there
>>>>doesn't seem to be a reason that it should be any slower at all, in this
>>>>particular case.  Do C++ compilers usually know that classes at the bottom of >an inheritance hierarchy are amenable to optimizations that would be unsafe on
>>>>classes that are higher up?)
>>>>
>>>>Dave
>>>
>>>Well, if you put the move generator into one function (and it does no function
>>>calls itself except those that are inlined) then you get the cost of one
>>>function call.
>>
>>Okay.
>>
>>>               But if you go the virtual function route, then you get a
>>>call for each piece.  I suppose the virtual function mechamism will cost a
>>>little extra too--maybe a couple of instructions.
>>
>>You shouldn't get a function call for each piece -- that should all be inlined,
>>no?  I'm thinking that virtual dispatch in this situation should actually >reduce to a switch that is guaranteed to not have a default case -- thanks to >the wonders of static type checking.  Maybe I'm missing something.
>
>I don't know; it might be me...  My idea was that there would be an abstract
>base class Piece from which is derived Pawn, Knight, etc.  There would be
>a virtual function GenerateMoves().  The piece list might be an array of
>pointers to Piece.  Then the main move generator function would perhaps have
>something like this inside:
>
>        for( int i = 0; i < npieces; i++ )
>            plist[i]->GenerateMoves( &movelist);
>
>So the compiler couldn't know statically which object type was going to
>be involved.
>
>Now if the compiler could somehow know exactly how many child classes of
>Piece were involved and if there were some RTTI stuff inside each object
>that could be used to select the case, I guess it could do something like
>that--that is, inline all the virtual functions and put in a switch-like
>dispatch mechanism.
>
>If, however, there were a piece list for each piece type, then it could
>certainly inline them, but they wouldn't have to be virtual then either...
>
>-Dan.

I think our particular example doesn't make too much sense, because we need a
board state, etc. :-) but let's go with it anyway because the particular example
doesn't matter that much.

If we take your loop

>        for( int i = 0; i < npieces; i++ )
>            plist[i]->GenerateMoves( &movelist);

then based on the typeof(plist[i]), a different GenerateMoves will be called.
Let's assume Piece is an abstract class (defined as = 0, so the compiler knows
that).  Certainly the compiler can know how many child classes of piece there
are, unless classes are being loaded in dynamically at runtime (which isn't
possible with most C++ compilers that I know of. :-)  Then the compiler _could_
do something switch-like.  Okay, we agree on that.

So, two questions:

1) QoI: How likely is it that a compiler will do these optimizations?
2) Was there a better method than using a
switch-including-telling-the-compiler-that-the-default-never-happens?

Dave



This page took 0.01 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.