C/C++에서 양의 모듈로를 얻는 가장 빠른 방법

C/C++에서 양의 모듈로를 얻는 가장 빠른 방법

내부 루프에서는 어레이 크기가 100이고 코드가 요소 -2를 요구하는 경우 요소 98을 지정할 수 있도록 "랩 어라운드" 방식으로 어레이를 인덱싱해야 하는 경우가 많습니다.Python과 많은 에서는 Python을 사용하여 이 할 수 .my_array[index % array_size]그러나 어떤 이유에서인지 C의 정수 산술(보통)은 일관되게 반올림하는 대신 0을 향해 반올림하고 결과적으로 그 모듈로 연산자는 음의 첫 번째 인수를 지정하면 음의 결과를 반환합니다.

는 종종 있다.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));
}

물론 시스템에서 가장 빠른 것을 찾기 위해 프로파일을 작성할 수 있지만, 더 나은 것을 놓쳤거나 다른 시스템에서 더 빠른 것이 더 느릴 수 있다는 우려를 금할 수 없습니다.

그럼 표준적인 방법이나 제가 놓친 가장 빠른 방법이 있을까요?

또 희망사항일 수도 있지만 자동벡터화할 수 있는 방법이 있다면 정말 좋을 것 같습니다.

제가 배운 표준적인 방법은

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

으로는 처음 입니다.abs(어느쪽이든)최적화 컴파일러가 이 패턴을 인식하고 "서명되지 않은 모듈로"를 계산하는 기계 코드로 컴파일할 수 있다고 해도 나는 놀라지 않을 것이다.

편집:

변종으로 넘어가겠습니다.. - 입니다.n < 0should be i < 0.

한 것처럼 수많은 에서 이 배리언트는 된 것처럼 보입니다.i < 0이치노경우든, 이 빠를 것입니다.(n * (i < 0))i < 0? n: 0이것은 곱셈을 회피합니다.게다가 부울을 int로 재해석하는 것을 회피하기 때문에, 「단순」입니다.

이 두 가지 변형 중 어느 것이 더 빠른지에 대해서는 컴파일러와 프로세서 아키텍처에 따라 달라집니다.이 두 변형 중 어느 것이 더 빠른지 시간을 두고 확인할 수 있습니다.하지만 이 두 변종보다 더 빠른 방법은 없을 것 같습니다.

대부분의 경우 컴파일러는 코드를 최적화하는 데 매우 능숙하기 때문에 보통 코드를 판독 가능한 상태로 유지하는 것이 좋습니다(컴파일러와 다른 개발자가 모두 사용자가 무엇을 하고 있는지 알 수 있습니다).

어레이 사이즈는 항상 플러스이므로, 다음과 같이 지수를 정의할 것을 권장합니다.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%를 차지하기 때문에 일반적인 경우 완전히 무시할 수 있다.

꽝은 꽝, 꽝, 꽝, 꽝, 꽝, 꽝, 꽝.value m, (실제)0xffffffff 및 부정의 0 않은 경우의 두 위해 사용됩니다.mod + m.

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

2의 거듭제곱을 곱하면 다음과 같은 작업이 수행됩니다(2가 보형 표현이라고 가정).

return i & (n-1);

C/C++에서 양의 모듈로를 얻는 가장 빠른 방법

다음과 같은 속도가 빠른가요? - 다른 제품보다 빠르지 않을 수 있지만, 모든 고객에게¹ 심플하고 기능적으로 적합합니다. a,b과 달리

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: -b is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

---

에도 여러 가지 이 있습니다.mod(a,b) 약점b < 0.

에 대한 아이디어는 유클리드 나눗셈을 참조하십시오.b < 0

---

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

「」의 경우에 한다.i % n + ni, n - 되지 않은 동작 「 」 。

---

return i & (n-1);

의존하다n2의 거듭제곱이 됩니다. (정답에 이런 말이 있는 것은 당연합니다.)

---

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

「 」의 경우에 하는 경우가 .n < 0 e, g,positive_mod(-2,-3) --> -5

---

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

2개의 정수폭을 사용해야 합니다.(답변에서 이에 대해 언급하는 것이 적절합니다.)
가 발생하다에서 실패하다modulo < 0positive_modulo(2, -3)--> -1.

---

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

「 」의 경우에 하는 경우가 .n < 0 e, g,positive_modulo(-2,-3) --> -5

---

¹ 예외:주식회사,a%b되어 않다a/ba/0 ★★★★★★★★★★★★★★★★★」INT_MIN/-1.

모든 조건부 경로(위에서 생성된 조건부 이동 포함)를 회피하려면(예를 들어 이 코드를 벡터화하거나 일정한 시간에 실행해야 하는 경우) 기호 비트를 마스크로 사용할 수 있습니다.

unsigned modulo(int value, unsigned m) {
  int shift_width = sizeof(int) * 8 - 1;
  int tweak = (value >> shift_width);
  int mod = ((value - tweak) % (int) m) + tweak;
  mod += (tweak & m);
  return mod;
}

다음은 Quickbench 결과입니다.gcc에서는 일반적인 케이스가 더 낫다는 것을 알 수 있습니다.clang의 경우 일반 케이스와 같은 속도입니다.clang은 일반 케이스에서 브랜치프리 코드를 생성하기 때문입니다.컴파일러가 특정 최적화를 수행할 때 항상 신뢰할 수 있는 것은 아니며 벡터 코드를 위해 수동으로 컴파일러를 롤링해야 할 수도 있기 때문에 이 기술은 어떤 경우에도 유용합니다.

보다 큰 타입으로 프로모트 할 수 있는 경우(및 보다 큰 타입으로 modulo를 실행할 수 있는 경우), 이 코드는 단일 modulo를 실행하고 다음 경우 no를 수행합니다.

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

2개의 보완 부호 비트의 전파를 사용하여 옵션의 애드엔드를 입수하는 구식 방법:

int positive_mod(int i, int m)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int r = i%m;
    return r+ (r>>shift & m);
}

array[(i+array_size*N) % array_size]여기서 N은 양의 인수를 보증하기에 충분한 정수이지만 오버플로하지 않도록 충분히 작습니다.

array_size가 일정할 경우 계수를 분할하지 않고 계산하는 기술이 있습니다.두 가지 접근법의 검정력 외에도 비트그룹의 가중치 합계에 2^i % n을 곱한 값을 계산할 수 있다. 여기서 i는 각 그룹에서 최하위 비트이다.

예: 32비트 정수 0xaabbccd % 100 = dd + cc*[2]56 + bb*[655]36 + aa*[167772]16, 최대 범위는 (1+56+36+16)*255 = 27795입니다.반복적인 적용과 다른 세분화를 통해 연산을 몇 가지 조건부 감산으로 줄일 수 있습니다.

일반적인 관행은 또한 2^32/n의 역수를 갖는 나눗셈의 근사치를 포함하며, 이는 일반적으로 상당히 넓은 범위의 인수를 처리할 수 있다.

 i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...)

당신의 두 번째 예가 첫 번째 예보다 낫다.곱셈은 if/else 연산보다 더 복잡한 연산이므로 다음을 사용하십시오.

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

언급URL : https://stackoverflow.com/questions/14997165/fastest-way-to-get-a-positive-modulo-in-c-c