On Mon, May 10, 2010 at 6:33 PM, Petr Baudis <[email protected]> wrote: > Hi! > > On Mon, May 10, 2010 at 06:05:58PM -0400, Don Dailey wrote: > > As far as the caching issue is concerned, (to answer Peter) I assumed > that > > all goes out the window with any of these schemes. I don't know what > Peter > > is proposing as an alternative. Tree's with pointers are not exactly > cache > > friendly and in Mark's scheme he has trees with pointers and an > additional > > non-cache friendly hash table with lists of pointers. Are those lists > of > > pointers also linked lists? > > Trees with pointers are pretty cache friendly since usually you expand > the node in a single go, yielding continuous memory space for all the > children instead of the children being spread uniformly over all the > memory as in case of hash tables. > > (Note that by "cache friendly" I mean not only "fitting and staying in > the cache", but also "getting into the cache" - continuous region means > automatic prefetching works great.) > > > With heavy playouts, I believe accessing the child nodes using ANY > scheme > > is relatively cheap - when compared to the time you spend playing an > entire > > game using heavy playouts. It might start to matter if you are using a > > really fast uniform random super light playout, but no strong program > does > > that anymore. > > My profiles of Pachi show that I spend about 30% of time on RAVE > descend and propagation. I have just started optimizing again after > some time though so I didn't have time to oprofile this in detail yet. > My tree data structure actually rather sucks, though. >
Yes, I agree with everything you said. Fitting in cache is an issue too of course. If you spend 30% of the time on the tree the issue is whether you have a good or bad implementation (performance-wise) and how much this would improve (or worsen) relative to some other data structure. I suspect that most of this time is constant and that it probably would only make a small difference doing any other reasonable scheme. I could be wrong but this is usually how it works with me unless I actually identify a real issue that I can fix. > > -- > Petr "Pasky" Baudis > When I feel like exercising, I just lie down until the feeling > goes away. -- xed_over > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
