I had a chess program years ago that was blindingly fast on some computers, very slow on others. It was all about the cache. The move generator was hard coded for each piece on each square. For instance a white pawn on d7 had it's very own move specialized move generator. There was a function for each piece of each color on each square.
By doing this I avoided the majority of conditional tests. I did not have to test for board edge, pawn on 7th, pawn on the second rank, etc. All the logic was unrolled and I basically had to write a program to write the move generator. The machine I developed this program on had a lot of cache and it was not a problem. But when running on, for instance a laptop, it would slow down enormously - something like 4 to 1 where other cache friendly programs would slow down perhaps 25%. I don't keep up much with processor technologies now and I don't know how much data vs instruction cache modern setups have, but I know it is far better than it used to be. I bet that old program would run well on modern computers. One trick, which you are probably doing, is to keep data structures together in memory. For instance it is better to have children next to each other so that you are not accessing memory all over the place, perhaps incurring several cache misses instead of one. On Wed, 2008-12-03 at 11:24 -0200, Mark Boon wrote: > On 3-dec-08, at 10:31, Heikki Levanto wrote: > > > > Having said that, I can't help responding to one detail: > > > >> I had seen people write about memory usage of the tree, but never > >> understood the concerns. > > > > One thing to remember is that more memory use means more cache > > misses, and > > more access to the main memory. On modern computers, those can cost > > as much > > as executing a thousand instructions! So memory optimizing can > > often pay off, > > also with respect to time! > > > > Of course, Java does a lot of memory management behind the scenes, so > > optimizing such can be harder... But when writing in C or C++, it > > does make > > sense. > > > > I've seen this stated often. But color me skeptical. If what you say > is true, then the MC-AMAF bot, which hardly uses any memory at all > and which fits in the secondary cache entirely, code and data > combined, should show an enormous speed-up in terms of number of > playouts per second. Instead it does only about twice the number of > playouts per second as the tree-search version, which can be almost > if not entirely explained by the extra work that needs to be done to > traverse and maintain the tree. If this is because I use Java, then > Don's concise C implementation of the MC-AMAF bot should be a lot > faster than my bloated Java version. Which, ahem, is not the case at > all. I think a well-crafted C program can be up to twice as fast as a > similar Java program. But I doubt that has much to do with cache misses. > > I think in computer-Go, trying to control cache misses is futile no > matter the language. Maybe you can do it for a relatively trivial, > well-understood and stable sub-part. But then you risk losing the > gain again as soon as it gets incorporated into a larger whole. So > your efforts go to waste. > > So this is in the "show me" category for me. You can use C or C++ if > you like, but show me a tree-search bot that speeds up the number of > playouts significantly by reducing the node-size. Maybe it's > possible, but I don't believe it until I see it. This could be > different for Chess programs, at least I've seen it claimed often. > But I don't envy them, it must be excruciatingly frustrating to deal > with. > > Mark > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/
signature.asc
Description: This is a digitally signed message part
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
