Michael Sherwin wrote: So I am not so sure that the case statements suffer that heavily from misprediction penalties!
Well, that depends on if there is one case that is far more likely than others. The problem with the branch-prediction logic is that it might predict taken vs non-taken, but that fot taken it also has to remeber where it jumps to. An indirect jump is obviously always taken, but the logic can only remember a single target. So it will speculatively start execution at the previous target, which has a good chance of being the one needed now if the target changes slowly, or one case occurs more frequently than others.
Of course a misprediction doesn't immediately kill you. I have no idea where Crafty is on the scale of speedy move generators. Bob doesn't seem to consider it an important speed issue...
A sequence of nested ifs has the advantage that you can structure it as a tree, rather than a list, so that 64 cases need only 6 compares. And you can try to organize them such that the ones that are hard to predict go in an unlikely branch of one that is easy to predict. This is why I avoid switch statements wherever speed is an issue.
Bob has been called the maestro of speed, and given the huge size of Crafty's eval, Crafty has a very good node rate. And Bob does not use case statements very much, if at all, in Crafty. Still my intuition says that you are probably right about carefully designed nested if 'trees' being faster than 'indirect jump tables'.
If only someone would make a 4GHZ quad core 80486 with superfast instructions, life could be good again!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Michael Sherwin wrote:Bob has been called the maestro of speed, and given the huge size of Crafty's eval, Crafty has a very good node rate. And Bob does not use case statements very much, if at all, in Crafty. Still my intuition says that you are probably right about carefully designed nested if 'trees' being faster than 'indirect jump tables'.
If only someone would make a 4GHZ quad core 80486 with superfast instructions, life could be good again!
I must retract. The MSVC 6 compiler uses a 'chained if' method if a case statement has 3 cases or less, but switches to the 'indirect jump table' method if there are 4 or more cases. So I imagine that the break even point is there.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Indirect jump table is only possible if the case numbers span a reasonable range. And you can't really draw general conclusions like you do, as what is more efficient is totally dependent on the frequency of the cases, and how well they can be predicted. This is information a compiler in general does not know. (With PGO you might be able to get the frequencies, but I doubt if it could take predictability into account.)
