Lazy SMP Better than YBWC?

[bob]

My NextMove() function has always been a big switch. Idea came from Cray Blitz in fact. But there, there is no duplicated code. For the search, you either use goto's here and there or you duplicate code. I consider goto's to be the lesser of two evils there, as duplicating code causes so many "oops, forgot to update this in all 10 different places..."

I'm not sure I understand about any need for duplicated code in absence of goto statements. In Symbolic's current TABS (Traditional A/B Search), there are eigteen states, none of which duplicate code.

Code: Select all

// Tabs Search State

typedef enum
{
  TssNil = -1,
  TssExit,
  TssIterBegin,
  TssIterEnd,
  TssMoveExecute,
  TssMoveRetract,
  TssNodeBegin,
  TssNodeEnd,
  TssPick,
  TssPickGainTest,
  TssPruning0,
  TssPruning1,
  TssScanBegin,  // Move scan start
  TssScanEnd,    // Move scan finish
  TssSeqBegin,   // Sequence of iterations start
  TssSeqEnd,     // Sequence of iterations finish
  TssTestWindow,
  TssTrackSelect,
  TssTranProbe
} Tss;

Of course, there are no goto statements or continue statements in the entire program. Nor are there any break statements other than case body terminators.

What do you do for parallel search? There are things you do in the normal search that you avoid in the parallel part (trans/ref storing for example.) Ditto if you do singular extensions, you want to exclude the move you think is singular when doing the singular test on the rest, you probably want to handle hashing differently as well since a reduced depth search should not overwrite a deeper one, even if it is the identical position. And there is the issue of how the compiler does this for large N states. Chained ifs? Jump table? etc...

I don't see how you avoid the goto's or duplicated code unless you do a BUNCH of really fine-grained states which would seem to be pretty slow...

Then there is the issue that the switch jump (assuming the compiler will produce a jump table for a list that long) will ALWAYS be mis-predicted on intel since the jump address will be changing frequently as the states change...

[sje]

What do you do for parallel search? There are things you do in the normal search that you avoid in the parallel part (trans/ref storing for example.) Ditto if you do singular extensions, you want to exclude the move you think is singular when doing the singular test on the rest, you probably want to handle hashing differently as well since a reduced depth search should not overwrite a deeper one, even if it is the identical position. And there is the issue of how the compiler does this for large N states. Chained ifs? Jump table? etc...

I don't see how you avoid the goto's or duplicated code unless you do a BUNCH of really fine-grained states which would seem to be pretty slow...

Then there is the issue that the switch jump (assuming the compiler will produce a jump table for a list that long) will ALWAYS be mis-predicted on intel since the jump address will be changing frequently as the states change...

The parallel search is not yet finished and has a long way to go, but it will work much the same way as does the parallel movepath enumeration (perft), and that has no duplicate code.

I am not concerned about jump table branch prediction rates, as not having any recursive call save/restore overhead will more than make up for missed predictions.