三年前の i7 950 3GHz で、128要素の float 配列に対して 400万回の std::lower_bound() を行って0.25 秒位。
VC++2008 /O2。最適化なしだと 0.7 秒程度。
ちなみに単純に8000ループごとにスレッド分割するだけで倍速以上になった。