再帰関数は地雷？

一生懸命最適化したつもりでまたベンチマークをとってみたが，やはり非常に遅い．
4-5Mnps程度の速度しかでない．
この原因として思い当たるのが，探索関数の再帰呼び出しだ．
関数を再帰的に呼び出すと，そのとき使用していた変数をメモリに待避させなければならない．
この操作がSPUでは重いのではないかと予想した．
先日擬似乱数関数を書いた理由は，いきなり再帰呼び出しでない形に変更するより，再帰呼び出しでない場合どの程度のパフォーマンスがでるかを調べるため，ランダムに盤面を生成する速度を見るためだった．
その結果，1Mのランダムな盤面を初期配置から終了まで生成した場合，かかる時間は12-13secであった．
各盤面ごとに60手が作成されるので，この場合5Mnps程度となり，同じような速度となる．
ところがこの関数には内部で条件分岐があるので，それを除いてみると，この速度は8-9Mnpsになった．
従って，むしろ性能の足かせになっているのは，以前から感じていた通り条件分岐であり，プログラムを複雑にしてまで再帰呼び出しを内部化するよりも，いかに条件分岐を減らすかということを考えた方がよいようだ．

条件分岐のヒントを明示的に与える方法として__builtin_expectがあるのだが，これを使ってこれまで性能が1%向上したことはまれだ．しかし分岐ミスは16cycle程度だと聞くので，どうしてここまで重くなってしまうのか腑に落ちない気持ちが残っている．

といってもこれは非常に難しい．現在でも最低限のことしか行っていないのにこれ以上の単純化をしろと言われてもかなり無理がある．
やはりこの程度であることは諦めて，並列化による効率化を目指すしかないのだろうか．