Killer moves?

[Don]

It's working nicely now and the improvement is noticeable. I'm still not where I want it to be but I'm moving in the right direction.

Take care not to have the same killer twice.

Here is the code I use where "mv" is the move that produced a beta (fail hi) cutoff and it's not a capture move:

Code: Select all

    
if (mv != ka[ply])  {
  kb[ply] = ka[ply];
  ka[ply] = mv;
}

Just for the record, that's not a very good way to do this. That makes kb[ply] and ka[ply] separated by sizeof(ka). Which pretty much guarantees that each killer will be in a different cache line. Much better is to put em in a structure, that is subscripted. Something like killer[ply].a and killer[ply].b so that the two killers for a single ply are in consecutive memory addresses. And generally in the same cache line.

I have been aware of this for 3 years and have never fixed it, thanks for the reminder.

I'll do it now while it's on my mind ...


Don

[bob]

It's working nicely now and the improvement is noticeable. I'm still not where I want it to be but I'm moving in the right direction.

Take care not to have the same killer twice.

Here is the code I use where "mv" is the move that produced a beta (fail hi) cutoff and it's not a capture move:

Code: Select all

    
if (mv != ka[ply])  {
  kb[ply] = ka[ply];
  ka[ply] = mv;
}

Just for the record, that's not a very good way to do this. That makes kb[ply] and ka[ply] separated by sizeof(ka). Which pretty much guarantees that each killer will be in a different cache line. Much better is to put em in a structure, that is subscripted. Something like killer[ply].a and killer[ply].b so that the two killers for a single ply are in consecutive memory addresses. And generally in the same cache line.

Speaking of this, I noticed that struct tree in crafty contains 8 arrays[MAXPLY] and 3 [MAXPLY+2] . Wouldn't it be better to combine these into structs?

I'll certainly look. "Temporal locality" would suggest you are right, assuming it is present (that the arrays are used close together in terms of time so that they are forced close together in memory to take advantage of cache line prefetching adjacent words...)

Just checked and yes, these should (and will) be combined... Some are less relevant than others. The PV array is one that should not be included since it is so rarely updated and it would spread out the other stuff significantly...