Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: The need to unmake move

Author: Robert Hyatt

Date: 07:45:11 08/22/03

Go up one level in this thread


On August 22, 2003 at 02:53:06, Johan de Koning wrote:

>On August 21, 2003 at 11:29:49, Robert Hyatt wrote:
>
>>On August 21, 2003 at 03:16:35, Johan de Koning wrote:
>>
>>>On August 20, 2003 at 14:27:57, Robert Hyatt wrote:
>>>
>>>>On August 20, 2003 at 03:59:38, Johan de Koning wrote:
>>>>
>>>>>On August 19, 2003 at 22:11:14, Robert Hyatt wrote:
>>>>>
>>>>>>On August 19, 2003 at 20:06:58, Mathieu Pagé wrote:
>>>>>>
>>>>>>>Hi,
>>>>>>>
>>>>>>>The fact:
>>>>>>>
>>>>>>>I have this question i read at some place that it is faster to unmake a move
>>>>>>>than to save the state of the game before moving then restoring it when we want
>>>>>>>to unmake the move.
>>>>>>>
>>>>>>>For the moment my engines did not implement unmake() (it is still buggy).
>>>>>>>
>>>>>>>My thougth:
>>>>>>>
>>>>>>>Since bitboard computation are slow (on 32 hardware) i think that it can be
>>>>>>>slower to unmake the move than to save the state. I friend of me that is lot
>>>>>>>better than me at optimizing code also think that.
>>>>>>>
>>>>>>>My questions:
>>>>>>>
>>>>>>>Are you all using unmake() function or there is some of you that found that
>>>>>>>saving the state is better ?
>>>>>>
>>>>>>
>>>>>>
>>>>>>read the comments from Crafty in main.c.  I started out using what is
>>>>>>commonly called "copy/make" as that worked well in Cray Blitz.  But it
>>>>>>didn't work well in the PC.  The PC has very limited memory bandwidth,
>>>>>>when you compare the speed of memory to the speed/demands of current
>>>>>>processors.  If you keep the board in cache, and update it there, it is
>>>>>>more efficient than to copy it from real memory to real memory...
>>>>>
>>>>>I hate to play Vincent here, but real memory is not an issue.
>>>>>
>>>>>If you manage to keep the deepest few plies worth of position structs in L1
>>>>>cache, then bandwith is pretty decent on the PC. And it has been ever since them
>>>>>PCs were endowed with cache.
>>>>
>>>>Sure, but look at what happens.  You copy a couple of hundred bytes.  You
>>>>update it _once_.  Then you copy it again for the next ply.  And so on.  Not
>>>>only are you not re-using what you moved around early, you are displacing good
>>>>stuff from the cache as well.
>>>
>>>You *are* re-using the stuff that you didn't change, by skipping the unmake()
>>>while backing up. And yes, you are claiming more cache space. But only the very
>>>few most active copies are relevant.
>>
>>Not quite.  I regularly hit 50+ plies deep.  By the time I back up to ply
>>20, that is long-gone from cache.  And it gets re-loaded.
>
>And this happens quite often.
>Particularly if you have a branching factor of 1.01 or something. :-)

It doesn't take much.  the PIV has 512K L2 cache.  128 bytes per line,
which turns into 4096 lines.  My bitmap stuff is about 256 bytes, or two
lines.  50 plies deep racks up 100 of those cache lines, a big chunk.  Of
course there are other things that need to be in cache at the same time.

However, the q-search is a good case in point.  It is easy to zap back and
forth for 20 plies with a 1.01 branching factor there...


>
>>  As I said, I'm
>>not guessing here.  I originally did it via copy/make and looked at the
>>performance after changing to make/unmake.  For the data structure size I am
>>using in Crafty, Copy/Make hurt performance.  Note that I do a small bit of
>>copy/make now, but not for the big bitboard structures, just for hash signatures
>>and the like.
>>
>>
>>>
>>>>I'm not really guessing here.  I did it both ways.  My bitmap stuff was, at the
>>>>time, something like 168 bytes.  When I got rid of copy/make and went to
>>>>make/unmake, I gained over 25% in raw speed, because _all_ of the bitmaps sit
>>>>in cache and stay there.
>>>
>>>It does of course depend on the amount and nature of the changes, as well as on
>>>the copy size and cache size. More importantly, would it influence performance
>>>at all? For a "slow" engine like mine 168 bytes is peanuts, since would be
>>>copied in (eg Athlon Thunderbird) 168/4*3 cycles.
>>>
>>>Hence I dare to ask: 25% of what?
>>
>>NPS went _up_ by 25%+.  So total engine speed.
>>
>>This was changed in Crafty version 9.16, which dates back many years.
>
>Whoah! This is *very* hard to believe.
>There must have been something severely wrong with 9.15 then (continuing chache
>trashing comes to mind, but that's just guessing). More likely, this number does
>not come from a clean comparison of copy/make versus make/unmake.

The _only_ change made was to replace copy/make with make/unmake.  Think about
the math.  Copy/make copies 256 bytes+.  Once _every_ node.  On today's
hardware, my dual xeon 2.8, I search about 2.4M nodes per second.  or about
400ns per node.  Copying 256 bytes is certainly going to show up on the radar
in a significant way, when it gets done once every 400 ns.  Yes, when you do
a copy, it will start off cache-to-cache.  But once you do that cache-to-cache
copy you are committed to eventually doing a cache-to-memory write-back.

Copy/Make came from Cray Blitz (for Crafty) because on the Cray, the cost is
near zero.  But dropping it on the PC resulted in a big  bottleneck that went
away when I changed to make/unmake.



>
>I'd love to see a comparison with system, compiler, and all other code being
>equal. Unfortunately that's impossible without a major rewrite. But if all your
>move dependent position data is in 1 struct it is easy to add copy() to make().
>That would provide an estimate of copy time and data cache trashing.
>If you're bored enough to try this, of course. :-)

The sad thing is the old source was lost several years ago with a disk crash
and bad backup tapes.  Otherwise going back to the version before/after the
change would be easy.  However, I could make an array of structs and copy them
in Make() just to see how much it slows things down.  Report will come later...


>
>... Johan



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