【算術演算小話 その一】 倍数への切り上げ

C++

パイプライン処理といった技術の発達した最近のCPUでは、条件分岐を減らすことで最適化が可能な場面があります。

こういった場合に稀に利用されるのが、算術演算を利用したテクニックです。 算術演算を上手く利用することで、場合によっては必要だった条件分岐も削減可能なことがあります。 そんな算術演算の重要性の高まりを受け、今日から3回に分けて算術演算に関する話をしたいと思います。

まぁ、そういったこじつけ的な背景説明はともかく、@machyさんに教わったテクニックを僕の中だけにおさめておくには勿体無いなぁと思ったのが本当の動機です。

例えばプロセスのメモリ使用量をKB単位で表示したいとします。 こういった場合、実際のメモリ使用量は1500バイトでも、多めに見積った方が好まれるため、1024の倍数に切り上げて2048/1024で2KBと表示します。 ではこの倍数への切り上げ処理を素直に書いてみます。

//nをmの倍数に切り上げる関数
size_t _ceil(size_t n, size_t m){
    if(n % m == 0)
      return n;
    else
      return (n / m + 1) * m;
}

条件分岐が入ってしまいましたし、ちょっと関数化しないとこの処理を毎回書くのは面倒です。 一応次のように一行で簡素には書けますが……条件分岐を消すことができません。

1.    n = (n % m) ? (n / m + 1) * m : n;
2.    if(n % m) n = (n / m + 1) * m;

で、教えてもらったのが以下のイディオムです。

size_t _ceil(size_t n, size_t m){
    return (n + m - 1) / m * m;
}

パフォーマンスとしては、条件分岐を使った場合と結局あまり変わらないかもしれませんが、あらかじめm-1を足してやるだけで条件分岐がなくなるスマートな解だと思います。

次回、次々回は以下の記事を書く予定です。 ・【算術演算小話 その二】 負の剰余について ・【算術演算小話 その三】 コンパイラの除算最適化