ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

performance of dynamically allocated move lists
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Rein Halbersma



Joined: 22 May 2007
Posts: 477

PostPost subject: performance of dynamically allocated move lists    Posted: Mon Aug 01, 2011 6:24 pm Reply to topic Reply with quote

Code:
 
container   enhancement   time   penalty      
array<128>               29359         
vector    "reserve(0)"   42046   43,2%      
           reserve(1)    41828   42,5%      
           reserve(2)    39531   34,6%      
           reserve(4)    37313   27,1%      
           reserve(8)    35328   20,3%      
           reserve(16)   33062   12,6%      
           reserve(32)   32875   12,0%      
           reserve(64)   35437   20,7%      
           reserve(128)  35688   21,6%      
           reserve(256)  40734   38,7%      
deque      "reserve(4K)" 48969   66,8%   


The above table (with a somewhat mangled layout) shows the timings for a 15-ply search with my draughts engine on the initial position in international draughts. I tested against the baseline of stack-allocated move lists of a fixed size of 128 moves. For this baseline, I used the STL container std::array<Move, 128>. Then I tested the exact same search with the dynamically allocated STL containers std::vector<Move> and std::deque<Move>. For each run, I varied the amount of pre-allocated memory with a reserve(X) statement, where X ran from 0 to 256 moves for std::vector, and to 4K bytes for std::deque (this is done implicitly by the STL provided allocator).

Whenever more than X moves are generated when reserve(X) has been called, the STL will automatically re-allocate about twice as much memory and copy the old vector into the new vector. For this 15-ply search, the average branching factor was a little less than 16. I didn't try to collect more detailed statistics on the distribution of the branching factor. Note that my Move struct is 24 bytes, so that there could be some cache alignment issues (perhaps padding to 32 bytes would be an idea). I didn't try to address this.

The performance results are quite surprising to me. It "only" costs 12% in the total time to depth (29 vs 33 seconds) when I use std::vector with reserved space for 32 moves, instead of doing a stack-based std::array. The 12%, of course, buys you full insurance against any crashes for positions with more than the maximum amount of stack-reserved moves. For chess engines, with Move structs of 4 bytes and average branching factor of 32, I would expect similar performance differences when moving to dynamically allocated move lists. Using incremental move generation (which I can't use in draughts because of capture rules) the performance in chess could be even slightly better.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
performance of dynamically allocated move lists Rein Halbersma Mon Aug 01, 2011 6:24 pm
      Re: performance of dynamically allocated move lists Wylie Garvin Mon Aug 01, 2011 6:51 pm
            Re: performance of dynamically allocated move lists Rein Halbersma Mon Aug 01, 2011 8:58 pm
                  Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 12:28 am
                        Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 12:43 am
                              Re: performance of dynamically allocated move lists Rein Halbersma Tue Aug 02, 2011 6:26 am
                                    Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 7:03 am
                                          Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 7:27 am
                                          Re: performance of dynamically allocated move lists Rein Halbersma Tue Aug 02, 2011 4:59 pm
                                                Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 6:11 pm
                                    Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 7:45 am
                                          Re: performance of dynamically allocated move lists Rein Halbersma Tue Aug 02, 2011 8:00 am
                                                Re: performance of dynamically allocated move lists Wylie Garvin Tue Aug 02, 2011 6:15 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads