Author: Dan Newman
Date: 00:47:56 02/16/00
Go up one level in this thread
On February 15, 2000 at 11:34:37, Dave Gomboc wrote: >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. Yeah. Every time I've tried to really package everything up into classes I've always had a problem figuring out where the put the board state. I tend to want to put it inside the piece class as a static member, but then you need to get at it elsewhere too. Making things global is usually considered rather bad, but having to pass the board state in as a function parameter doesn't thrill me too much either... > >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? I think it's unlikely that many (or perhaps any) compilers will do the inlining of virtual member functions (when called as above). The header files containing the definitions of the child classes need not be included into the move generator module for it to properly compile (since we are calling the move generation functions via the ABC pointers). Suppose you do include them. How can the compiler know that you've provided all of them? If there were some special pragma or something like that __assume() thing to tell the compiler that you're giving it all of these, I could see it working. And maybe such exists (MSVC 6.0?). But I haven't heard of it or looked for it (yet) either. Certainly it's not impossible... >2) Was there a better method than using a >switch-including-telling-the-compiler-that-the-default-never-happens? > >Dave There's always a better method :). I just don't know what it is... -Dan.
This page took 0.04 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.