[解決済み] C/C++で正のモジュロを得る最速の方法

質問

例えば、配列のサイズが100で、私のコードが要素-2を要求した場合、それは要素98を与えられるべきでしょう。Pythonのような多くの高級言語では、これを簡単に行うことができます。 my_array[index % array_size] で簡単にできますが、何らかの理由で C の整数演算は (通常は) 一貫して切り捨てずにゼロに向かって丸めるため、負の最初の引数が与えられたときにモジュロ演算子が負の結果を返します。

多くの場合、私は index よりも小さいことはありません。 -array_size よりも小さくはならないので、そのような場合は my_array[(index + array_size) % array_size] . しかし、これが保証されない場合もあります。そのような場合のために、常に正であるモジュロ関数を実装する最も速い方法を知りたいと思います。分岐なしでそれを行うには、次のようないくつかの "賢い" 方法があります。

inline int positive_modulo(int i, int n) {
    return (n + (i % n)) % n;
}

または

inline int positive_modulo(int i, int n) {
    return (i % n) + (n * (i < 0));
}

もちろん、これらをプロファイリングして自分のシステムで最速のものを見つけることはできますが、より良いものを見逃しているかもしれない、あるいは自分のマシンで速いものが別のマシンでは遅いかもしれないという心配はぬぐえません。

これを行う標準的な方法、または私が見逃している最速の方法と思われる巧妙なトリックはありますか?

また、希望的観測かもしれませんが、もしこれを自動ベクトル化できる方法があれば、それは素晴らしいことです。

どのように解決するのですか？

ほとんどの場合、コンパイラはコードを最適化するのが得意なので、通常はコードを読みやすくしておくとよいでしょう (コンパイラと他の開発者の両方にとって、あなたが何をしているのかがわかるように)。

配列のサイズは常に正であるため、商を次のように定義することをお勧めします。 unsigned . コンパイラは小さなif/elseブロックを、分岐のない条件付き命令に最適化します。

unsigned modulo( int value, unsigned m) {
    int mod = value % (int)m;
    if (mod < 0) {
        mod += m;
    }
    return mod;
}

これは、分岐のない非常に小さな関数を作成します。

modulo(int, unsigned int):
        mov     eax, edi
        cdq
        idiv    esi
        add     esi, edx
        mov     eax, edx
        test    edx, edx
        cmovs   eax, esi
        ret

例えば modulo(-5, 7) は 2 .

残念ながら、商がわからないため、整数の除算を行う必要があり、他の整数演算と比較して少し遅いです。配列のサイズが2のべき乗であることが分かっている場合は、これらの関数定義をヘッダに格納しておくことをお勧めします。そうすれば、コンパイラがそれらをより効率的な関数に最適化することができます。以下は、この関数 unsigned modulo256(int v) { return modulo(v,256); } :

modulo256(int):                          # @modulo256(int)
        mov     edx, edi
        sar     edx, 31
        shr     edx, 24
        lea     eax, [rdi+rdx]
        movzx   eax, al
        sub     eax, edx
        lea     edx, [rax+256]
        test    eax, eax
        cmovs   eax, edx
        ret

アセンブリを参照してください。 https://gcc.godbolt.org/z/DG7jMw

最も投票された回答との比較をご覧ください。 http://quick-bench.com/oJbVwLr9G5HJb0oRaYpQOCec4E4

編集：Clangは条件付き移動命令（通常の算術演算よりもコストがかかる）なしで関数を生成できることがわかりました。この違いは、積分の除算が全体の時間の約70%を占めるという事実により、一般的なケースではまったく無視できます。

基本的に、Clangはシフト value の全幅に符号ビットを拡張するために右にシフトします。 m (つまり 0xffffffff を否定し 0 それ以外の場合は) の第2オペランドをマスクするために使われます。 mod + m .

unsigned modulo (int value, unsigned m) {
    int mod = value % (int)m;
    m &= mod >> std::numeric_limits<int>::digits;
    return mod + m;
}